akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE BangPatterns, MultiWayIf #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Int
import Data.Foldable
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Debug.Trace

solve :: Int -> VU.Vector Int -> Int
solve !n !an = fst $ VU.head $ V.last dp
 where
  dp :: V.Vector (VU.Vector (Int, Int))
  dp = V.constructN
    n
    (\(!vec) ->
      let i = V.length vec
          q =
            VU.map
                (\(!j) -> if i == 0
                  then let z = an VU.! j in (0, z)
                  else minimum
                    [ let (c1, s1) = vec V.! k VU.! j
                          (c2, s2) = vec V.! (i - k - 1) VU.! (j + k + 1)
                          s        = s1 + s2
                      in  (c1 + c2 + s, s)
                    | k <- [0 .. i - 1]
                    ]
                )
              $ VU.fromList [0 .. n - i - 1]
      in  q `seq` q
    )

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  n  <- (\vec -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  an <- VU.unfoldrN n readInt <$> B.getLine
  print $ solve n an


Measured memory_bytes: 7932
#include<string>
#include<vector>
#include<iostream>

#define	pb	push_back

using namespace std;

vector<string> split(string s){
	int n=s.length();

	bool d=false;
	for(int i=0;i<n;i++)	if(s[i]=='_')	d=true;

	vector<string> ans;
	if(d){
		s+='_';
		n++;
		int bef=-1;
		for(int i=0;i<n;i++){
			if(s[i]=='_' && ~bef){
				ans.pb(s.substr(bef,i-bef));
				bef=-1;
			}
			else{
				if(bef==-1)	bef=i;
			}
		}
		return ans;
	}
	else{
		s[0]=tolower(s[0]);
		s+='Q';
		n++;
		int bef=0;
		for(int i=0;i<n;i++){
			if(isupper(s[i])){
				ans.pb(s.substr(bef,i-bef));
				s[i]=tolower(s[i]);
				bef=i;
			}
		}
		return ans;
	}
}

int main(){
	while(1){
		string s;
		char c;
		cin>>s>>c;

		vector<string> part=split(s);
		int n=part.size();
		if(c=='U'){
			for(int i=0;i<n;i++){
				part[i][0]=toupper(part[i][0]);
				cout<<part[i];
			}
			cout<<endl;
		}
		else if(c=='L'){
			for(int i=0;i<n;i++){
				if(i>0)	part[i][0]=toupper(part[i][0]);
				cout<<part[i];
			}
			cout<<endl;
		}
		else if(c=='D'){
			for(int i=0;i<n;i++){
				if(i>0)	cout<<'_';
				cout<<part[i];
			}
			cout<<endl;
		}
		else	break;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main(){
    int n,m;
    while(cin >>n >>m,n){
        vector<int> a(m);
        rep(i,n){
            int d,v;
            cin >>d >>v;
            --d;
            a[d] = max(a[d], v);
        }

        int ans = 0;
        rep(i,m) ans += a[i];
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3088
#include <iostream>
using namespace std;

int main(){
  int n,m,a[100];
  cin >> n >> m;
  for(int i = 0;i < n;i++){
    cin >> a[i];
  }
  for(int i = 1;i <= m;i++){
    for(int j = 0;j < n - 1;j++){
      if(a[j] % i > a[j + 1] % i){
	int t = a[j];
	a[j] = a[j + 1];
	a[j + 1] = t;
      }
    }
  }
  for(int i = 0;i < n;i++) cout << a[i] << endl;
  return 0;
}

Measured memory_bytes: 3108
#include <iostream>
#include <algorithm>

using namespace std;

int N, a[100005];

bool com(int a, int b)
{
	return a>b;
}

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> a[i];
	}

	sort(a + 1, a + N + 1, com);

	long long len = 1;
	
	int i, j;
	int temp;

	for (i = 1; i <= N; i++)
	{
		temp = 0;
		for (j = i + 1; j <= N; j++)
		{
			if (a[j] == a[i])
			{
				temp++;
				i = j;
			}
			else
			{
				break;
			}
		}
		for (j = i+1; j <= N; j++)
		{
			if (a[i] - a[j] > 2)
			{
				break;
			}
		}

		if (j - i + temp > len)
		{
			len = j - i + temp;
		}
	}
	cout << len << endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e:t) fill_v(e, v);
}

typedef pair<int, int> P;

vector<P> G[100005];
vector<bool> visited;

P dfs(int p, int par) {

    int cost = -1;
    int res = -1;
    visited[p] = true;
    REP(i, G[p].size()) {
        auto e = G[p][i];
        int n = e.first;
        if (n == par) continue;
        if (visited[n]) continue;
        auto kv = dfs(n, p);
        if (kv.first + e.second > cost) {
            cost = kv.first + e.second;
            res = kv.second;
        }
    }

    return {cost, res};
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;
    REP(i, N - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    visited.resize(N);
    REP(i, N) visited[i] = false;

    //auto kv = dfs(0, -1);
    int s = 0;

    vector<int> res(N, -1);
    queue<P> q;
    q.push({s, 0});
    while (!q.empty()) {
        auto kv = q.front();
        q.pop();
        int cur = kv.first;
        int col = kv.second;
        if (res[cur] >= 0) continue;
        res[cur] = col;
        REP(i, G[cur].size()) {
            auto e = G[cur][i];
            if (e.second % 2 == 0) {
                q.push({e.first, col});
            }
            else {
                q.push({e.first, col ^ 1});
            }
        }

    }

    REP(i, N) cout << res[i] << endl;


    return 0;
}


Measured memory_bytes: 8704
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
typedef long long ll;
using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  if(a > b) cout << a-1 << endl;
  else cout << a << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int N, M;
	vector<int> A; 
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		A.push_back(tmp);
	}
	sort(A.begin(), A.end(), greater<int>());

	vector<pair<int, int>> vc;
	for (int i = 0; i < M; i++)
	{
		int b, c;
		cin >> b >> c;
		pair<int, int> tmp={c,b};
		vc.push_back(tmp);	
	}
	sort(vc.begin(), vc.end(), greater<pair<int,int>>());

	vector<int> buf(N, 0);
	int it = 0;
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		buf[i] = vc[it].first;
		cnt++;
		if(cnt == vc[it].second){
			cnt = 0;
			it++;
			if(it==M)break;
		}
	}
	

	ll ans=0;
	it=0;
	int it_a = 0;
	int it_b = 0;
	while(it != N){
		ans += max(A[it_a], buf[it_b]);
		(A[it_a]>buf[it_b])? it_a++:it_b++;
      	it++;
	}	
	
	cout << ans << endl;
}

Measured memory_bytes: 1784
#include <iostream>

using namespace std;

int main(void){
  int N, M;
  cin >> N >> M;
  // 入力終了

  int first_time = 1900*M + 100*(N-M);
  
  int p_inv = 1;
  for(int i=0; i<M; i++)
    p_inv = p_inv*2;
  
  cout << first_time*p_inv << endl;
  

  return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>

int main()
{
	int a,b,c;
	int d = 0;
	scanf("%d %d %d", &a, &b, &c);
	while(b >= a)
	{
		if(c % b == 0) 
		d = d + 1;
		b = b - 1;
	}
	printf("%d\n", d);
	return 0;
}


Measured memory_bytes: 2748
#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define X first
#define Y second
 
typedef long long ll;
typedef long double ld;
 
using namespace std;
 
const int N = 200010;
 
int comp = 0;
const int MODULE = 1e9 + 7;
bool wss[N];
vector <int> e[N];
ll ans = 1;
 
 
vector <int> cl[N];
vector <int> mn;
vector <pair <int, int> > b;
 
ll pw(ll a, int b) 
{
	if (b == 0) return 1;
	ll v = pw(a, b / 2);
	v = (v * v) % MODULE;
	if (b & 1) v = (v * a) % MODULE;
	return v;
}
ll fct[N];
 
int main() 
{
	ios_base::sync_with_stdio(0);
	int n, x, y;
	scanf("%d%d%d", &n, &x, &y);	
	fct[n] = 1;
	for (int i = 1; i <= n; i++) fct[n] = (fct[n] * i) % MODULE;
	fct[n] = pw(fct[n], MODULE - 2);
	for (int i = n; i >= 1; i--)
		fct[i - 1] = (fct[i] * i) % MODULE;
	for (int i = 0; i < n; i++) {
		pair <int, int> pp;
		scanf("%d%d", &pp.second, &pp.first);
		cl[pp.second].push_back(pp.first);
	}
 
	for (int i = 1; i <= n; i++) {
		sort(cl[i].begin(), cl[i].end());
		if (cl[i].size() == 0) continue;
		mn.push_back(cl[i][0]);
	}
 
	mn.push_back(y + 1);
	sort(mn.begin(), mn.end());
 
	for (int i = 1; i <= n; i++) 
	{
		if (cl[i].size() == 0) continue;
		int dv;
		if (mn[0] == cl[i][0]) dv = mn[1];
		else dv = mn[0];
		int rg = max(x - cl[i][0], y - dv);
		b.push_back(mp(cl[i][0], upper_bound(cl[i].begin(), cl[i].end(), rg) - cl[i].begin()));
	}
 
	sort(b.begin(), b.end());
	int rg = y - b[0].first;
	int cur = 1;
	for (int i = 0; i < b.size(); i++) 
	{
		if ((i != 0) && (b[i].first > rg))  break;
		
		for (int j = 0; j < b[i].second; j++) 
			ans = (ans * cur ++) % MODULE;
		ans = (ans * fct[b[i].second]) % MODULE;
	}		
	cout << ans << endl;
 
	return 0;
}


Measured memory_bytes: 18292
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 7;
vector<int> G[N];
int dfn[N], id, n, q, last[N], pos[N];
long long val[N], ans[N];

void dfs(int u, int fa) {
    dfn[u] = ++id;
    pos[id] = u;
    for (auto v: G[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
    last[u] = id;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    while (q--) {
        long long x;
        int u;
        scanf("%d%lld", &u, &x);
        val[dfn[u]] += x;
        val[last[u] + 1] -= x;
    }
    for (int i = 1; i <= n; i++) {
        val[i] += val[i - 1];
        ans[pos[i]] = val[i];
    }
    for (int i = 1; i <= n; i++)
        printf("%lld%c", ans[i], " \n"[i == n]);
    return 0;
}

Measured memory_bytes: 28160
#include <bits/stdc++.h>

#define ll long long
#define mk make_pair
#define pb push_back
#define ff first
#define sc second
#define all(x) x.begin(), x.end()

ll gcd(ll a, ll b){
   if(b == 0) return a;
   
   return gcd(b, a % b);
}

ll sum(int n){
   if(n == 0){
      return n;
   }else{
      return sum(n/10) + n%10;
   }
}
using namespace std;


int main(){
   
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   string s; cin >> s;
   int del = 0;
   int n = s.size();
   string ans = "";
   for(int i = n-1; i >= 0; i--){
      if(del < 0) del = 0;
      if(s[i] == 'B') {
         del++;
         continue;
      }
      if(del == 0){
         ans += s[i];
      }else{
         del--;
      }
      
   }

   reverse(all(ans)); 
   cout << ans; 
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
// #define int long long
struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
}IoSetup;

using Int = __int128_t;
using ll = long long;
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int SMOD = 1000000007;
constexpr int NMOD = 998244353;
constexpr int dx[]={1,0,-1,0,1,1,-1,-1};
constexpr int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T&b){if(a<b)return(a=b,1);return 0;}
template<class T>bool chmin(T &a, const T&b){if(b<a)return(a=b,1);return 0;}


signed main() {
    
	int n;
	cin >> n;

	int64_t sum = 0;

	for(int i = 1; i < n; i++) {
		sum += n / i;
		if(n%i == 0) sum--;
	}

	cout << sum << endl;

    return 0;
}


Measured memory_bytes: 3544
#include<bits/stdc++.h>
const int maxn = 2e3 + 5;
const long long mod = 1e9 + 7;
using namespace std;

char s[maxn];
int k,n,x,y,num[maxn];

int main(){
	scanf("%d %d %d", &n, &x, &y);
	int d;
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(j >= y){
				if(i <= x) d = j - y + x - i + 1;
				else if(i >= y) d = j - i;
				else d = min(i - x + j - y + 1, j - i);
			}
			else if(j <= x) d = j - i;
			else{
				if(i <= x) d = min(j - i, y - j + x - i + 1);
				else d = min(j - i, y - j + 1 + i - x);
			}
			num[d]++;
		}
	}
	for(int i = 1; i < n; i++){
		printf("%d\n",num[i]);
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n, m;
	int i;
	int stage[1024];
	int dice[1024];
	int now;
	int cnt;
	
	while (1){
		scanf("%d %d", &n, &m);
		if (n + m == 0){
			break;
		}
		for (i = 0; i < n; i++){
			scanf("%d", &stage[i]);
		}
		for (i = 0; i < m; i++){
			scanf("%d", &dice[i]);
		}
		now = 1;
		cnt = 0;
		i = 0;
		while (cnt < m){
			now += dice[i];
			now += stage[now - 1];
			cnt++;
			if (now >= n){
				break;
			}
			i++;
		}
		printf("%d\n", cnt);
	}
	
	return (0);
}

		

Measured memory_bytes: 608
#heap
import heapq
n,m = map(int, input().split( ))
J=[]
for _ in range(n):
    ai,bi =map(int,input().split( ))
    J.append((-bi,ai))###

J.sort(key = lambda x:x[1])###
J.append((0,2*m))
day_rev = 1
i = 0
lim = []
ans = 0
while day_rev<=m:
    while J[i][1]<=day_rev:
        heapq.heappush(lim,J[i])
        i+=1
    if lim:
        ch = heapq.heappop(lim)
        ans -= ch[0]
    day_rev+=1
print(ans)
    

Measured memory_bytes: 82192
#include<iostream>
using namespace std;
int main() {
	int n, k;
	int h[100000];
	int count = 0;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		if (h[i] >= k) {
			count += 1;
		}
	}
	cout << count << endl;
	
	return 0;
}

Measured memory_bytes: 640
// #include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min, std::next_permutation, std::lower_bound
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric> // std::gcd, std::lcm
#include <limits> // std::numeric_limits<long int>::max()
#include <unordered_map>
#include <map>
#include <cmath> // std::atan2

using namespace std;
typedef long long ll;
#define INF 1999999999
#define MODA 1000000007 
#define rep(i,n) for (long long i = 0; i < (n); ++i)

int main() {
  ll N;
  cin >> N;
  vector<ll> A(N), B(N);
  rep(i, N) cin >> A[i] >> B[i];

  multimap<ll, ll> jobs;
  rep(i, N) jobs.insert(make_pair(B[i], A[i]));
  ll time = 0;
  for(const auto job : jobs) {
    time += job.second;
    if (time > job.first) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 15872
Q = []
MAX = 100000
head = 0
tail = 0

class Process:
    def __init__(self):
        self.name = ''
        self.time = 0

def enqueue(x):
    global tail
    Q[tail] = x
    if tail + 1 == MAX:
        tail = 0
    else:
        tail += 1

def dequeue():
    global head
    x = Q[head]
    if head + 1 == MAX:
        head = 0
    else:
        head += 1
    return x

def main():
    input_line = input().split(" ")
    n = int(input_line[0])
    qtime = int(input_line[1])

    for _ in range(MAX):
        Q.append(None)

    for _ in range(n):
        v = input().split(' ')
        p = Process()
        p.name = v[0]
        p.time = int(v[1])
        enqueue(p)
    
    elaps = 0
    while head != tail:
        p = dequeue()
        t = min(qtime, p.time)
        p.time -= t
        elaps += t
        if p.time > 0:
            enqueue(p)
        else:
            print(p.name + " " + str(elaps))

if __name__ == "__main__":
    main()


Measured memory_bytes: 17652
def abc_134(N, D):
    gurad_cnt = 1
    range = D * 2 + 1
    while 1:
        if N <= range * gurad_cnt:
            break
        else:
            gurad_cnt += 1

    print(gurad_cnt)


if __name__ == "__main__":
    N, D = [int(i) for i in input().split()]
    abc_134(N, D)



Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;



void init();
void work();
int ca=1;
int main(){
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//    init();
//    int T;cin>>T;
//    while(T--)
    work();
    return 0;
}
void work(){
    ll A,B,N;
    cin>>A>>B>>N;
    if(N<B){
        cout<<(A*N)/B-A*(N/B);
    }else cout<<(A*(B-1))/B;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
 
int main()
{
	int x1[maxn],x2[maxn];
	int y1[maxn],y2[maxn]; 
	int h,w,a[550][550],i,j,n=0;
	scanf("%d%d",&h,&w);
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++)
			scanf("%d",&a[i][j]);
	}
	for(i=1;i<=h;i++){
		for(j=1;j<w;j++){
			if(a[i][j]%2==1){
			y1[n]=i;
			y2[n]=i;
			x1[n]=j;
			x2[n]=j+1;
			n++;
			a[i][j]--;
			a[i][j+1]++;
			}
		}
	}
	for(i=1;i<h;i++){
		if(a[i][w]%2==1){
			y1[n]=i;
			y2[n]=i+1;
			x1[n]=w;
			x2[n]=w;
			n++;
			a[i][w]--;
			a[i+1][w]++;
		}
	}
	printf("%d\n",n);
	for(i=0;i<n;i++)
		printf("%d %d %d %d\n",y1[i],x1[i],y2[i],x2[i]);
	return 0;
} 

Measured memory_bytes: 6272
import math
N = int(input())
min_= 100
for i in range(1,math.ceil(math.sqrt(N))+1,1):
    if (N % i != 0):
        continue
    a = i;
    b = int(N/a)
    min_ =min(min_,max(len(str(a)),len(str(b))))
print(min_)

Measured memory_bytes: 9020
fun main(args: Array<String>) {
    var input = readLine()!!.reversed()
    val candidate = listOf("dream".reversed(), "dreamer".reversed(), "erase".reversed(), "eraser".reversed())

    var left = 0
    var flag = true
    while(left < input.length) {
        var flag2 = true
        for (i in 0 until candidate.size) {
            val target = candidate[i]
            val right = left + target.length

            if (right <= input.length && input.substring(left, right) == target) {
                left += target.length
                flag2 = false
                break
            }
        }

        if(flag2){
            flag = false
            break
        }
    }

    if (flag) print("YES") else print("NO")
}

Measured memory_bytes: 41136
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define MAXINF 1000000005
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define repl(i,n) for(long long i = 0; i < (long long)(n); ++i)
#define repc(it, x) for(auto it = (x).begin(); it != (x).end(); ++it)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rrpel(i,n) for(long long i = (long long)(n)-1; i >= 0; --i)
#define rrepc(it, x) for(auto it = (x).rbegin(); it != (x).rend(); ++it)
#define all(x) (x).begin(), (x).end()
#define P pair<int, int>

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); srand(time(NULL));
    int n, m;
    cin >> n >> m;
    vector<bool> ok(101010, false);
    vector<int> wsum(101010, 0);
    int ac=0, wa=0;
    rep(i, m) {
    	int p; string s;
    	cin >> p >> s;
    	if(!ok[p] && s == "WA"){
    		++wsum[p];
    	} else if (!ok[p] && s == "AC") {
    		++ac;
    		wa += wsum[p];
    		ok[p] = true;
    	}
    }

    cout << ac << " " << wa << endl;
    return 0;
};


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) REP(i, 0, n)
#define REP(i, k, n) for(auto i = k; i != n; i++)
#define rrep(i, n) RREP(i, n, 0)
#define RREP(i, n, k) for(auto i = n; i != k; i--)
#define ALL(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " " << x << endl
#define in(x, data) (data).find(x) != (data).end()

typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    int a[100000 +1]; REP(i,1,n+1) cin >> a[i];
    sort(a+1,a+n+1);
    int diff = INT_MAX, ans;
    REP(i,1,n) {
        if(diff > abs(a[n] - a[i]*2)) {
            diff = abs(a[n] - a[i]*2);
            ans = a[i];
        }
    }
    cout << a[n] << " " << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

using ld = long double;
using Point = complex<ld>;
const ld pi = acos(-1);
constexpr ld eps = 1e-9;

ld dot(const Point& a, const Point& b){
    return a.real() * b.real() + a.imag() * b.imag();
}

ld cross(const Point& a, const Point& b){
    return a.real() * b.imag() - a.imag() * b.real();
}

namespace std{
    bool operator<(const Point& a, const Point& b){
        return abs(real(a) - real(b)) > eps ? real(a) < real(b) : imag(a) < imag(b);
    }
}

vector<Point> convex_hull(vector<Point>& ps){
    sort(ps.begin(), ps.end());
    int n = ps.size();
    int k = 0;
    vector<Point> res(n * 2);
    for(int i = 0; i < n; ++i){
        while(k > 1 && cross(res[k - 1] - res[k - 2], ps[i] - res[k - 1]) <= 0) --k;
        res[k++] = ps[i];
    }
    int bound = k;
    for(int i = n - 2; i >= 0; --i){
        while(k > bound && cross(res[k - 1] - res[k - 2], ps[i] - res[k - 1]) <= 0) --k;
        res[k++] = ps[i];
    }
    res.resize(k - 1);
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    if(n == 2){
        cout << 0.5 << '\n' << 0.5 << endl;
        return 0;
    }
    vector<Point> ps;
    map<Point, int> idx;
    for(int i = 0; i < n; ++i){
        int x, y;
        cin >> x >> y;
        ps.emplace_back(x, y);
        idx[ps[i]] = i;
    }

    vector<Point> table = convex_hull(ps);
    int m = table.size();
    vector<ld> ans(n, 0);
    for(int i = 0; i < m; ++i){
        ld t1 = arg(table[(i + 1) % m] - table[i]);
        if(t1 < 0)  t1 += pi * 2;
        ld t2 = arg(table[(i - 1 + m) % m] - table[i]);
        if(t2 < 0)  t2 += pi * 2;
        ld theta = abs(t2 - t1);
        ans[idx[table[i]]] = abs(pi - theta) / (pi * 2);
    }
    cout << fixed << setprecision(10);
    for(int i = 0; i < n; ++i)  cout << ans[i] << '\n';
}

Measured memory_bytes: 3884
main :: IO ()
main = interact $ solve . read

solve :: Int -> String
solve 0 = "0"
solve x = reverse $ go x
  where
    go 0 = ""
    go x
        | (q, 0) <- divMod x (-2) = '0' : go q
        | (q, -1) <- divMod x (-2) = '1' : go (q + 1)


Measured memory_bytes: 508
#include<iostream>
using namespace std;

int main(){
  int n,re[10],ans;
  while(1){
    cin >> n;
    if(n == 0) break;
    ans = 0;
    for(int i=0;i<9;i++){
      cin >> re[i];
      ans += re[i];
    }
    ans = n - ans;
    cout << ans << endl;
  }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const int MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
    int n,a,b,diff;
    cin>>n>>a>>b;
    diff=b-a;
    if(diff%2==0) cout<<"Alice"<<endl;
    else cout<<"Borys"<<endl;
}


Measured memory_bytes: 256
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

lint lcm(lint a, lint b) {
    return (a / gcd(a, b)) * b;
}

lint power(lint x, lint n, lint mod = MOD) {
    lint ret = 1;
    while(n > 0) {
        if(n & 1){
            (ret *= x) %= mod;
        }
        (x *= x) %= mod;
        n >>= 1;
    }
    return ret;
}

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    lint r, d, x;
    cin >> r >> d >> x;
    lint ans[2011];
    ans[2000] = x;
    for (int i=2000; i<2010; ++i){
        ans[i+1] = r * ans[i] - d;
        cout << ans[i+1] << endl;
    }
    return 0;
}

Measured memory_bytes: 888
/*created by tanishk gupta*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define repl(i,a,n) for(long long int i=a;i<n;i++)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef vector<int> VI;
typedef long long int ll;
typedef unsigned long long ull;
//typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll MOD=1e9+7;
const ll mod=1e9+7;
//const llint MOD;
const ll N=(ll)(1e6+1);
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll add(ll a,ll b){return ((a%MOD)+(b%MOD))%MOD;}
ll mul(ll a,ll b){return ((a%MOD)*(b%MOD))%MOD;}
ll sub(ll a,ll b){return ((a%MOD)-(b%MOD)+MOD)%MOD;}
ll binpow(ll x, ll y){ll z = 1;while(y){if(y & 1) z = mul(z, x);x = mul(x, x);y >>= 1;}return z;}
ll inv(int x){return binpow(x, MOD - 2);}
ll divide(ll x, ll y){return mul(x, inv(y));}
ll fact[N];
void precalc(){fact[0] = 1;for(ll i = 1; i < N; i++)fact[i] = mul(fact[i - 1], i);}
ll C(ll n, ll k){return divide(fact[n], mul(fact[k], fact[n - k]));}
//bool prime[N];
//void sieve() {for(int i=2;i<N;i++) {prime[i]=true;}for (int p=2; p*p<=N; p++){if (prime[p] == true){for (int i=p*p; i<=N; i += p)prime[i] = false;}}}
ll legendpow(ll n, ll p){ll total = 0;while (n){n /= p;total += n;}return total;}

//head==================================================================================


int main() {
//#ifdef _DEBUG
	//freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//#endif
string s;
cin>>s;
ll sum=0;
rep(i,0,s.size())
{
    sum+=(s[i]-'0');
}
if (sum%9==0)
{
    cout<<"Yes"<<endl;
}
else
{
    cout<<"No"<<endl;
}
}

Measured memory_bytes: 3744
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <random>
#include <utility>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
#include <vector>
 
using namespace std;
typedef long long ll;
 
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
std::vector<P> tree[100010];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
ll i,j,k;
ll n,m;
ll ans;
ll a,b;
ll x[200005],y[200005];

int main(){
	cin>>n;
	for(i=0;i<n;i++){
		cin>>x[i];
	}
	sort(x,x+n);
	a=x[n-1];
	ans=0;
	ll xx=0;
	for(i=0;i<n;i++){
		if(min(x[i],a-x[i])>ans){
			xx=x[i];
			ans=min(x[i],a-x[i]);
		}
	}
	cout<<a<<" "<<xx<<endl;

	
	
	return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll a, b;
	cin >> a >> b;
	print((a*b%2 == 0)? "Even": "Odd")
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int A, B;
	cin >> A >> B;
	if (A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0) cout << "Possible" << endl;
	else cout << "Impossible" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

const int MOD=1000000007;

int main(){
  int N; cin >> N;
  string S1,S2; cin >> S1 >> S2;
  int before=0;
  int pos=0;
  long long result=1;
  while(pos<N){
    if(S1[pos]==S2[pos]){
      if(before==0){
        result*=3;
      }else if(before==1){
        result*=2;
      }else{
        result*=1;
      }
      result%=MOD;
      before=1;
      pos++;
    }else{
      if(before==0){
        result*=6;
      }else if(before==1){
        result*=2;
      }else{
        result*=3;
      }
      result%=MOD;
      before=2;
      pos+=2;
    }
  }
  cout << result << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int x,y;
  cin>>x>>y;
  cout<<__gcd(x,y)<<endl;


}


Measured memory_bytes: 3128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
int pos;
string exp;

int solve(){
  vector<int> v;
  string num = "";
  if ( isdigit(exp[pos]) ){
    while( isdigit(exp[pos]) ){
      num += exp[pos];
      pos++;
    }
    pos++;
    int a = 0;
    for ( int i = num.size()-1, p=1; i >= 0; i--, p*=10 ){
      a += p*(num[i]-'0');
    }
    return (a+1)/2;
  }

  while(1){
    if ( exp[pos] == '[' ){
      pos++;
      v.push_back(solve());
    } else if ( exp[pos] == ']' ) break;
  }
  pos++;
  sort(v.begin(), v.end());
  int sum = 0;
  for ( int i = 0; i < v.size()/2+1; i++ ) sum += v[i];
  return sum;
}

main(){
  int t; cin >> t;
  for ( int i = 0; i < t; i++ ){
    cin >> exp;
    pos = 0;
    assert( exp[pos] == '[' ); pos++;
    cout <<  solve() << endl;
  }
}

Measured memory_bytes: 1288
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    s.push_back('R');
    vector<int> res(n, 0);
    int l = 0, r = 0, state = 0;
    int index1 = 0, index2 = 0;
    for (int i = 0; i <= n; i++) {
        if (state == 0) {
            if (s[i] == 'R') {
                r++;
            } else {
                l++;
                index2 = i;
                state = 1;
            }
        } else {
            if (s[i] == 'R') {
                // merge result
                res[index2] += (l + 1) / 2 + r / 2;
                res[index2 - 1] += (r + 1) / 2 + l / 2;

                r = 1;
                l = 0;
                state = 0;
                index1 = i;
            } else {
                l++;
            }
        }
    }
    for (auto node : res)
        cout << node << " ";
    cout << endl;
}


Measured memory_bytes: 1024
a,b,c = map(int,input().split())
d = a % b
li = [d % b]
i = 2
while True:
    e = (d * i) % b
    if e != (d % b):
        li.append(e)
    else:
        break
    i += 1
if c in li:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;

#pragma region template


// -type-
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;


// -const-
const ll MOD = 1000000007;


const ll MAX = (ll)0x3f0000003f000000;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1},
          dy[] = {1, 0, -1, 0, 1, -1, -1, 1};


// -define-
#define F first
#define S second

#define reps(i, k, n) for (int i = (k), i##_len = (n); i < i##_len; ++i)
#define rep(i, n) reps(i, 0, n)
#define all(o) begin(o), end(o)
#define sz(a) ((int)(a).size())
#define debug(x) cerr << x << " (L:" << __LINE__ << ")" << '\n';


// -functions-

inline bool in(string s, string c) {
    return (s.find(c) != string::npos);
}
inline bool in(string s, char c) {
    return (s.find(c) != string::npos);
}

template <class T>
void print(T& x) {
    cout << x << '\n';
}

struct setup_main {
    setup_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(15);
    }
} setup_main_;

#pragma endregion

ll ans = 0;

void solve(long long N, std::vector<long long> C, std::vector<long long> S,
           std::vector<long long> F) {
    reps(start, 1, N + 1) {
        // ans = 0;
        ll k = start;
        ll time = 0;
        while (k < N) {
            if (S[k] >= time) {
                time = S[k];
            } else if (time % F[k] != 0) {
                time += F[k] - (time % F[k]);
            }
            time += C[k];
            k++;
        }
        cout << time << '\n';
    }
}

signed main() {
    long long N;
    scanf("%lld", &N);
    std::vector<long long> C(N);
    std::vector<long long> S(N);
    std::vector<long long> F(N);
    for (int i = 1; i < N; i++) {
        scanf("%lld", &C[i]);
        scanf("%lld", &S[i]);
        scanf("%lld", &F[i]);
    }
    solve(N, std::move(C), std::move(S), std::move(F));

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
class Program{
    static int cnt = 0;
    static void Main(){
        int n = int.Parse(Console.ReadLine());
        int[] A = new int[n];
        for (int i = 0; i < n; i++)
        {
            A[i] = int.Parse(Console.ReadLine());
        }
        ShellSort(ref A, n);
        Console.WriteLine();
        Console.WriteLine(cnt);
        for (int i = 0; i < n; i++)
        {
            Console.WriteLine(A[i]);
        }
    }

    static void InsertionSort(ref int[] arr, int n, int g){
        for (int i = g; i <= n - 1; i++)
        {
            int tmp = arr[i];
            int j = i - g;
            while (j >= 0 && arr[j] > tmp)
            {
                arr[j + g] = arr[j];
                j = j - g;
                cnt++;
            }
            arr[j + g] = tmp;
        }
    }

    static void ShellSort(ref int[] arr, int n){
        cnt = 0;
        List<int> lg = new List<int>();
        int h = 1;
        while(h <= n){
            lg.Add(h);
            h = 3 * h + 1;
        }
        int m = lg.Count();
        Console.WriteLine(m);
        int[] G = lg.ToArray();
        for (int i = m - 1; i >= 0; i--)
        {
            if(i != m - 1) Console.Write(" ");
            Console.Write(G[i]);
            InsertionSort(ref arr, n, G[i]);
        }
    }
}

Measured memory_bytes: 16932
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	while (1) {
		int h, w;
		cin >> h >> w;
		if (h == 0) break;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3100
import math
def main():
    N = int(input())
    d = {}
    za = zb = zab = r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a, b = -a, -b
            x = math.gcd(abs(a), abs(b))
            d[(a//x, b//x)] = d.get((a//x, b//x), 0) + 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
        else:
            t = (abs(b), abs(a))
        used.add(t)
        l.append((d[x], d.get(t, 0)))
    r = pow(2, za) + pow(2, zb) - 1
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return (r - 1 + zab) % mod
print(main())


Measured memory_bytes: 100640
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>
#include<utility>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> b(n);
  for(int i = 0; i < n; i++) cin >> b[i];
  vector<int> p(m);
  for(int i = 0; i < m; i++) cin >> p[i];
  int ac = 0, bc = 0;
  for(int i = 0; i < m; i++) {
    if(i % 2 == 0) ac += p[i];
    else bc += p[i];
  }
  int b0 = 0, b1 = 0;
  for(int i = 0; i < n; i++) if(b[i] == 1) b1++;
  else b0++;
  int ans0 = 1000000, ans1 = 10000000;
  vector<int> b0p;
  for(int i = 0; i < n; i++) if(b[i] == 0) b0p.push_back(i);
  if(b0 == ac) {
    ans0 = 0;
    int c = 0, pos = 0;
    for(int i = 0; i < m; i++) {
      for(int j = 0; j < p[i]; j++) {
        if(i % 2 == 1) pos++;
        else {
          ans0 += abs(pos - b0p[c]);
          c++;
          pos++;
        }
      }
    }
  }
  if(b0 == bc) {
    ans1 = 0;
    int c = 0, pos = 0;
    for(int i = 0; i < m; i++) {
      for(int j = 0; j < p[i]; j++) {
        if(i % 2 == 0) pos++;
        else {
          ans1 += abs(pos - b0p[c]);
          c++;
          pos++;
        }
      }
    }
  }
  cout << min(ans0, ans1) << endl;
  return 0;
}

Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;

int main(){
  int N,K;
  string S;
  cin >> N >> K >> S;
  if(S.at(K-1)=='A'){
    S.at(K-1)='a';
  }
  else if(S.at(K-1)=='B'){
    S.at(K-1)='b';
  }
  else{
    S.at(K-1)='c';
  }
  cout << S << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

#define NUM1 1000000009
#define NUM2 99999883

struct Info{
	ull hash_1,hash_2;
};
ull HASH[SIZE][2],POW[SIZE][2];

ll T_length,H,digit;
ll table[SIZE],ruisekiwa[SIZE];
vector<int> V;
char T[SIZE];

bool IS_SAME(Info left,Info right){
	if(left.hash_1 == right.hash_1 && left.hash_2 == right.hash_2)return true;
	else{
		return false;
	}
}

Info calcHash(int left,int right){

	Info ret;

	int length = right-left+1;

	//indexのずれに注意:T[right]までのハッシュ値はHASH[right+1]に記録されている
	ret.hash_1 = HASH[right+1][0]-HASH[left][0]*POW[length][0];
	ret.hash_2 = HASH[right+1][1]-HASH[left][1]*POW[length][1];

	return ret;
}

//AとBの一致長さを返す
ll calc_match_len(int start_A,int start_B,int length){

	ll left = 0,right = length-1,mid = (left+right)/2;
	ll match_len = 0;
	Info tmp_A,tmp_B;

	while(left <= right){

		tmp_A = calcHash(start_A,start_A+mid);
		tmp_B = calcHash(start_B,start_B+mid);

		if(IS_SAME(tmp_A,tmp_B)){
			match_len = mid+1;
			left = mid+1;
		}else{
			right = mid-1;
		}
		mid = (left+right)/2;
	}

	return match_len;
}

bool compare(int a,int b){

	ll match_len = calc_match_len(a,b,digit);

	return T[a+match_len] < T[b+match_len];
}


int main(){

	scanf("%lld %lld",&T_length,&H);

	scanf("%s",T);

	ll num_zero = 0;
	for(int i = 0; i < T_length; ){
		if(T[i] != '0'){

			i += 1;
			continue;
		}
		ll count = 0;
		for(;i+count < T_length && T[i+count] == '0'; count++);

		num_zero += (count*(count+1))/2;
		i += count;
	}

	if(num_zero >= H){

		printf("0\n");
		return 0;
	}

	//2通りのハッシュ値を計算する
	HASH[0][0] = 0;
	HASH[0][1] = 0;
	POW[0][0] = 1;
	POW[0][1] = 1;

	//Tのハッシュ値を求める
	for(int i = 1; i <= T_length; i++){
		HASH[i][0] = T[i-1] + HASH[i-1][0]*NUM1;
		HASH[i][1] = T[i-1] + HASH[i-1][1]*NUM2;

		POW[i][0] = POW[i-1][0]*NUM1;
		POW[i][1] = POW[i-1][1]*NUM2;
	}

	for(int i = 0; i <= T_length; i++){

		ruisekiwa[i] = 0; //桁iの数がいくつあるか
	}

	table[T_length] = T_length;
	for(int i = T_length-1; i >= 0; i--){

		if(T[i] != '0'){

			table[i] = i;
		}else{

			table[i] = table[i+1];
		}

		ruisekiwa[T_length-table[i]]++;
		ruisekiwa[0]--;
	}

	for(int i = T_length-1; i >= 0; i--){

		ruisekiwa[i] += ruisekiwa[i+1];
	}

	digit = 0;
	ll sum = num_zero;

	for(int i = 1; i <= T_length; i++){

		if(sum+ruisekiwa[i] >= H){
			digit = i;
			break;
		}
		sum += ruisekiwa[i];
	}

	//printf("sum:%lld digit:%lld\n",sum,digit);

	for(int i = 0; i <= T_length; i++){

		if(table[i]+digit > T_length)break;

		V.push_back(table[i]);
	}

	sort(V.begin(),V.end(),compare);

	for(int i = 0; i < digit; i++){

		printf("%c",T[V[H-(sum+1)]+i]);
	}
	printf("\n");

	return 0;
}



Measured memory_bytes: 8004
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#include <bitset>
#include <complex>
#include <cassert>
#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define FORIT(i,c)	for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define GI(i) (scanf("%d",&i))
#define GLL(i) (scanf("%lld",&i))
#define GD(i)  (scanf("%lf",&i))
#define PB          push_back
#define MP          make_pair
#define MT          make_tuple
#define GET0(x)     (get<0>(x))
#define GET1(x)     (get<1>(x))
#define GET2(x)     (get<2>(x))
#define ALL(X)      (X).begin(),(X).end()
#define LLMAX       (1LL<<60)
#define LLMIN       -(1LL<<60)
#define IMAX        (1<<30)
#define IMIN        -(1<<30)
typedef long long LL;
using namespace std;

int H,W;
vector<string> board;
int G[50][50];

int main(void){
    cin>>H>>W;
    string s;
    REP(i,H){
        cin>>s;
        board.PB(s);
        // cout<<s<<endl;
    }
    REP(i,H)REP(j,W)G[i][j]=IMAX;
    queue<pair<int,pair<int,int> > > que;
    int numB = 0;
    REP(i,H)REP(j,W)if(board[i][j]=='#')numB++;
    que.push(MP(1,MP(0,0)));
    // printf("__LINE__ = %d\n",__LINE__);
    while(!que.empty()){
        int d = que.front().first;
        int y = que.front().second.first;
        int x = que.front().second.second;
        que.pop();
        if(d < G[y][x] && board[y][x] == '.'){
            G[y][x] = d;
            if(0<y)     que.push(MP(d+1,MP(y-1,x)));
            if(y<H-1)   que.push(MP(d+1,MP(y+1,x)));
            if(0<x)     que.push(MP(d+1,MP(y,x-1)));
            if(x<W-1)   que.push(MP(d+1,MP(y,x+1)));
        }
    }
    if(G[H-1][W-1]==IMAX){
        printf("-1\n");
    }else{
        printf("%d\n",H*W-G[H-1][W-1]-numB);
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int main(void){
  int a, b;
  int i;
  char str[10];
  char ch;
  scanf("%d", &a);
  scanf("%s", str);
  scanf("%d", &b);
  ch = str[b-1];
  for ( i = 0; i < a; i++ ) {
    if ( str[i] != ch ) {
      str[i] = '*';
    }
  }
  printf("%s", str);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>


using namespace std;

int main() {
    int a,b,c;
    cin >> a >> b >> c;

    bool ans = false;
    for (int i=a; i<=a*b; i+=a) {
        if (i % b == c) ans = true;
    }

    cout << (ans? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll INF = 1e17;
const ll MOD = 1e9+7;

int main() {
    // input, ready
    int N,M;
    cin >> N >> M;
    vector<int> A(N);
    int total = 0;
    for (int i=0; i<N; i++) {
      int a;
      cin >> a;
      A[i] = a;
      total += a;
    }
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());

    // resolve
    bool yes = true;
    for (int j=0; j<M; j++) {
      if (A[j] * 4 * M < total) {
        yes = false;
        break;
      }
    }

    // output
    if (yes) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
s = input()
n = len(s)

# 01010... か 10101...の二択

# 0...
err1 = 0
for i in range(n):
    if i % 2 == 0 and s[i] == "1":
        err1 += 1
    elif i % 2 == 1 and s[i] == "0":
        err1 += 1

# 1...
err2 = 0
for i in range(n):
    if i % 2 == 0 and s[i] == "0":
        err2 += 1
    elif i % 2 == 1 and s[i] == "1":
        err2 += 1

print(min(err1, err2))


Measured memory_bytes: 3188