akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

using namespace std;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

signed main()
{
	omajinai;

	int N, M, Q; cin >> N >> M >> Q;

	vi nxt(N), prv(N);

	vector<bool> answer(N);

	rep(i, N) {
		nxt[i] = i + 1 >= N ? 0 : i + 1;
		prv[i] = i - 1 < 0 ? N - 1 : i - 1;
	}

	int now_pos = 0;

	rep(i, M) {
		int a; cin >> a;
		if (a % 2 == 0) {
			rep(_, a) {
				now_pos = nxt[now_pos];
			}
			
			prv[nxt[now_pos]] = prv[now_pos];
			nxt[prv[now_pos]] = nxt[now_pos];

			answer[now_pos] = true;

			now_pos = nxt[now_pos];
		} else {
			rep(_, a) {
				now_pos = prv[now_pos];
			}

			prv[nxt[now_pos]] = prv[now_pos];
			nxt[prv[now_pos]] = nxt[now_pos];

			answer[now_pos] = true;

			now_pos = nxt[now_pos];
		}
	}

	rep(i, Q) {
		int q; cin >> q;
		cout << !answer[q] << endl;
	}
}

Measured memory_bytes: 2796
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int mod=998244353,maxn=3e5+10;
int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=(ll)res*x%mod;
		y>>=1;
		x=(ll)x*x%mod;
	}
	return res;
}
int fac[maxn],ifac[maxn];
int C(int n,int m){
	return (ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
	int n=read(),A=read(),B=read();
	int ans=0;
	ll Caon=readll();
	fac[0]=1;
	REP(i,1,n) fac[i]=(ll)i*fac[i-1]%mod;
	ifac[n]=ksm(fac[n],mod-2);
	DREP(i,n-1,0) ifac[i]=(ll)(i+1)*ifac[i+1]%mod;
	REP(i,0,n){
		ll res=Caon-(ll)i*A;
		if(res%B || res<0) continue;
		ll j=res/B;
		if(j>n) continue;
		ans=((ll)C(n,i)*C(n,j)+ans)%mod;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2560
//confilm 0LL and 1LL
//confilm cornercase such as 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPR(i, n, 1)
#define co(n) cout << (n) << endl
#define cosp(n) cout << (n) << ' '
#define setp(n) cout << fixed << setprecision(n);
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fs first
#define sc second
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;

int main(void){
	unordered_map<ll, ll> ump;
	rep(i, 3){
		ll a, b;
		cin >> a >> b;
		ump[a]++;
		ump[b]++;
	}

	Vec v(5);
	repn(i, 4){
		v[ump[i]]++;
	}
	if(v[1] == 2 && v[2] == 2) puts("YES");
	else puts("NO");

	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
N,K=map(int, input().split())
A=list(map(int,input().split()))
"""count=0
for l in range(N):
    if A[l]%K==1:
        count+=1
for l in range(N-1):
    sum=A[l]
    for r in range(l+1,N):
        sum+=A[r]
        if sum%K==r-l+1:
            count+=1
print(count)"""
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=(cum[i]+A[i]-1)%K
dic=defaultdict(int)
ans=0
for i in range(N+1):
    ans+=dic[cum[i]]
    dic[cum[i]]+=1
    if i-(K-1)>=0:
        dic[cum[i-(K-1)]]-=1
print(ans)


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

int main(){
  int N; cin>>N;
  int A[N+1];
  map<int,int> mp1,mp2;
  rep(i,N){
    cin>>A[i+1];
    mp1[A[i+1]]++;
  }
  int ind=1;
  for(auto m:mp1){
    mp2[m.first]=ind;
    ind++;
  }
  int ans=0;
  for(int i=1;i<=N;i+=2){
    if(mp2[A[i]]%2==0) ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 10364
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_A


def ni():
    return list(map(int, input().split()))


def permutation(A, m):
    from itertools import permutations
    for size in range(len(A)):
        for perm in permutations(A, r=size):
            print(perm)
            if sum(perm) == m:
                return True
    return False


def combination(A, m):
    if sum(A) < m:
        return False

    from itertools import combinations
    for size in range(1, len(A)+1):
        # heavy
        for comb in combinations(A, size):
            if sum(comb) == m:
                return True

    return False


def solve():
    _ = input()
    A = sorted(ni())
    _ = input()
    mi = ni()

    # print(*A)
    # print(*mi)
    # print('yes' for m in mi if permutation(A, m) else 'no')

    for m in mi:
        if combination(A, m):
            print('yes')
        else:
            print('no')


if __name__ == '__main__':
    solve()



Measured memory_bytes: 5676
#include <bits/stdc++.h>
using namespace std;
int main() {
    string S; cin >> S;
    if (S=="Sunny") cout << "Cloudy"<<"\n";
    if (S=="Cloudy") cout << "Rainy"<<"\n";
    if (S=="Rainy") cout << "Sunny"<<"\n";
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<utility>
#include<vector>
#include<set>
#define ll long long
vector<pair<ll,ll>>v[1000001];
ll dist[1000001];
char c[1001][1001];
int main()
{
    ll n,m;
    cin>>n>>m;
    ll l,r;
    cin>>l>>r;
    ll s=((l-1)*m)+r;
    cin>>l>>r;
    ll e=((l-1)*m)+r;
    for(ll i=1; i<=n; i++) {
        for(ll j=1; j<=m; j++) {
            cin>>c[i][j];
        }
    }
    for(ll i=1; i<=n; i++) {
        for(ll j=1; j<=m; j++) {
            if(c[i][j]=='.') {
                for(ll k=i-2; k<=i+2; k++) {
                    for(ll h=j-2; h<=j+2; h++) {
                        if(k>=1 && k<=n && h>=1 && h<=m) {
                            if(c[k][h]=='.') {
                                if(abs(i-k)+abs(j-h)==1)
                                    v[(i-1)*m+j].push_back({(k-1)*m+h,0});
                                else if(abs(i-k)+abs(j-h)>1)
                                    v[(i-1)*m+j].push_back({(k-1)*m+h,1});
                            }
                        }
                    }
                }
            }
        }
    }
   
    for(ll i=0; i<=n*m; i++)
     dist[i]=1e18;
    dist[s]=0;
    set<pair<ll,ll>>pq;
    pair<ll,ll>p,x;
    pq.insert({s,0});
    while(!pq.empty()) {
        p=*pq.begin();
        pq.erase(pq.begin());
        if(dist[p.first]!=p.second) continue;
        for(auto it:v[p.first]) {
            if(dist[it.first]>dist[p.first]+it.second) {
                dist[it.first]=dist[p.first]+it.second;
                pq.insert({it.first,dist[it.first]});
            }
        }
    }
    if(dist[e]==1e18) cout<<-1<<endl;
    else cout<<dist[e]<<endl;
    return 0;
}


Measured memory_bytes: 168280
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
int MOD = 1000000007;

int main() {
	int a, b; cin >> a >> b;
	printf("%d %d %f\n", a / b, a % b, (double)a / b);
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
#define ll              long long int
//#define int             int64_t
#define ff              first
#define ss              second
#define pb              push_back
#define mpair           make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define sbits(x)      __builtin_popcountll(x)
#define zbits(x)      __builtin_popcountlliltin_ctzll(x)
#define w(t)            int t;cin>>t;while(t--)
#define uset            unordered_set
#define en              cout<<endl
using namespace std;
void fast(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout<<fixed<<setprecision(10);}
int max2(int a,int b){ if(a>b) return a;return b;}
int min2(int a,int b){ if(a<b)return a;return b;}
int max3(int a,int b,int c){ return max2(a,max2(b,c));}
int min3(int a,int b,int c){ return min2(a,min2(b,c));}
void system_output(){
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
   #endif
}
int height[100001];
void solve(){
    int n,m,x,y;

    cin>>n>>m;
    memset(height,0,sizeof(height));
    for(int  i =1;i<=n;i++)
        cin>>height[i];
    vector<int>adj[n+1];
    for(int  i =1;i<=m;i++)
    {
          cin>>x>>y;
          adj[x].pb(y);
          adj[y].pb(x);
    }
    int good = 0;
    for(int  i =1;i<=n;i++)
    {
         
          if(adj[i].size()==0)
            {good++;continue;}

          //map<int,int>mp;
          bool check = true;
          for(auto x : adj[i])
          {
               if(x!= i && (height[x]>=height[i]))
               {
                 check = false;break;
               }

          }
          if(check)
            good++;
    }
    cout<<good<<endl;

}
signed main(void)
{
      fast();
      //w(t)
      solve();

}


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

using namespace std;

#define ll long long

ll maxPathUndir(int vertex, vector<vector<int>>& g)
{
    vector<ll> dist(g.size(), -1);
    dist[vertex] = 0;
    unordered_set<int> not_visited;
    for(int i = 1; i < g.size(); i++)
        not_visited.insert(i);

    ll max_dist = INT_MIN;
    while(!not_visited.empty())
    {
        int max_dist_idx = *not_visited.begin();
        ll m = dist[max_dist_idx];
        for(auto i: not_visited)
        {
            if(m < dist[i])
            {
                m = dist[i];
                max_dist_idx = i;
            }
        }
        not_visited.erase(max_dist_idx);

        for(int n: g[max_dist_idx])
        {
            if(!not_visited.count(n))
                continue;
            if(dist[n] < m + 1)
            {
                dist[n] = m+1;
                max_dist = max(max_dist, dist[n]);
            }
        }
    }

    return max_dist;
}

ll maxPath(vector<vector<int>>& g, vector<int>& order)
{
    vector<ll> dist(g.size(), -1);

    ll max_dist = -1;
    for(int v : order)
    {
        dist[v] = max(dist[v], 0ll);
        for(int n: g[v])
        {
            if(dist[n] < dist[v] + 1)
            {
                dist[n] = dist[v] + 1;
                max_dist = max(max_dist, dist[n]);
            }
        }
    }

    return max_dist;
}

void tsort_util(int u, vector<vector<int>>& g, vector<int>& order, vector<bool>& visited)
{
    if(visited[u])
        return;

    for(int v: g[u])
    {
        tsort_util(v, g, order, visited);
    }

    visited[u] = true;
    order.push_back(u);
}

vector<int> tsort(vector<vector<int>>& g)
{
    vector<bool> visited(g.size(), false);
    vector<int> res;
    for(int i = 1; i < g.size(); i++)
        tsort_util(i, g, res, visited);

    reverse(res.begin(), res.end());

    return res;
}

int main(int argc, char *argv[])
{
    int N, M;
    cin >> N >> M;

    vector<vector<int>> g(N+1);
    for(int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
    }

    ll answer = INT_MIN;

    vector<int> order = tsort(g);
//    for(int v: order)
//        cout << v << " ";
//    cout << endl;
//    for(int i = 0; i < N; i++)
//    {
//        //run dijkstra for vertex i
//        answer = max(answer, maxPath(i, g, order));
//    }

    answer = maxPath(g, order);
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 9720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; i++)
#define all(a) (a).begin(), (a).end()

int A, B, X;
int main () {
  cin >> A >> B >> X;

  cout << ((A + B >= X && X >= A) ? "YES" : "NO") << endl;
  return 0;
}


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


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

    int N,M;
    cin >> N >> M;

    priority_queue<int> que;
    for (int i=0; i<N; i++){
        int A;
        cin >> A;
        que.push(A);
    }

    for (int i=0; i<M; i++){
        int a;
        a = que.top();
        que.pop();
        a /= 2;
        que.push(a);
    }

    ll ans = 0;
    for (int i=0; i<N; i++){
        ans += que.top();
        que.pop();
    }

    cout << ans << endl;
}

Measured memory_bytes: 892
#include <cstdio>
const int N = 200005, p = 1000000007;
long long fac[N], inv[N];
int qp(int x, int y) {
	int res = 1;
	for(; y; y >>= 1, x = (long long)x*x%p) if(y&1) res = (long long)res*x%p;
	return res;
}
void init(int n){
	fac[0]=1;
	for(int i = 1; i <= n; i ++ ) fac[i] = fac[i-1]*i%p;
	inv[n] = qp(fac[n], p-2);
	for(int i = n; i >= 1; i -- ) inv[i-1] = inv[i]*i%p;
}
long long C(int n,int m) {
	return fac[n]*inv[m]%p*inv[n-m]%p;
}
int main(){
	int H, W, A, B, ans = 0;
	scanf("%d%d%d%d", &H, &W, &A, &B);
	init(H+W);
	for(int i=1;i<=H-A;i++)
		ans=(ans+C(i+B-2, i-1)*C(H+W-i-B-1, H-i))%p;
	printf("%d\n", ans);
}


Measured memory_bytes: 3328
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int i = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define MP make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1 << 30;
const ll LINF = 1LL << 61;
const int MOD = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;
    cout << (n - 1) * (m - 1) << endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;

  int min_count = 1000000000;
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;

    int count = 0;
    for (int j = A; j % 2 == 0; j /= 2) {
      count++;
    }

    if (count < min_count) {
      min_count = count;
    }
  }
  
  cout << min_count << endl;
}

Measured memory_bytes: 3596
#include <iostream>
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  if(a== 1&& b!=1)cout<<"Alice";
  if(a!= 1&& b==1)cout<<"Bob";
  if (a>b && b !=1)cout<<"Alice";
  if(b>a && a!=1)cout<<"Bob";
  if (a==b)cout<<"Draw";

  return 0;
}



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

int main() {
  int n, i, ans = 0, count = 1;
  cin >> n;
  
  vector<int> a(n);
  for(i = 0; i < n; i++){
    cin >> a.at(i);
  }
  
  sort(a.begin(), a.end());
  
  for(i = 1; i < n; i++){
    if(a.at(i - 1) == a.at(i)){
      count++;
    }
    else{
      ans += count % 2;
      count = 1;
    }
  }
  ans += count % 2;
  
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;

// #define DEBUG

class Unionfind
{
    vector<int> p;

public:
    Unionfind(int n);
    int find(int x);
    void unite(int x, int y);
    bool match(int x, int y);
};

Unionfind::Unionfind(int n)
{
    for (int i = 0; i < n; i++)
    {
        p.push_back(i);
    }
}

int Unionfind::find(int x)
{
    while (p[x] != x)
    {
        p[x] = p[p[x]];
        x = p[x];
    }
    return x;
}

bool Unionfind::match(int x, int y)
{
    return (find(x) == find(y)) ? true : false;
}

void Unionfind::unite(int x, int y)
{
    x = Unionfind::find(x);
    y = Unionfind::find(y);
    if (x != y)
    {
        p[x] = y;
    }
}

void printsubset(int x)
{
    int t;
    cout << x << ":";
    t = 0;
    while (x > 0)
    {
        if (x % 2 == 1)
            cout << " " << t;
        x /= 2;
        t++;
    }
    cout << endl;
}

int main()
{
#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, q, t, x, op;
    cin >> n >> q;
    stack<int> a[n];
    for (int i = 0; i < q; i++)
    {
        cin >> op;
        if (op == 0)
        {
            cin >> t >> x;
            a[t].push(x);
        }
        else if (op == 1)
        {
            cin >> t;
            if (!a[t].empty())
                cout << a[t].top() << endl;
        }
        else if (op == 2)
        {
            cin >> t;
            if (!a[t].empty())
                a[t].pop();
        }
    }

    return 0;
}



Measured memory_bytes: 4292
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for (int i = a; i < b; i++)
using namespace std;

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <bitset>

int main() {
	int N, K;
	cin >> N >> K;

	int ans = 1;
	rep(i, N) {
		if (ans < K) {
			ans *= 2;		
		}
		else {
			ans += K;		
		}	
	} 
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 768
#include <stdio.h>

//int load(int row,int colum,int mx[][])


int main(void)
{
	int n,m,l,i,j,k;
	
	scanf("%d %d %d",&n,&m,&l);
	
	int a[n][m],b[m][l];
	long c[n][l];
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	
	for(i=0;i<m;i++)
	{
		for(j=0;j<l;j++)
		{
			scanf("%d",&b[i][j]);
		}
	}
	
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<l;j++)
		{
			c[i][j] = 0;
			for(k=0;k<m;k++)
				c[i][j] += a[i][k]*b[k][j];
		}
	}
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<l;j++)
		{
			if(j!=l-1)
				printf("%ld ",c[i][j]);
			else
				printf("%ld",c[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 760
#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
int a[550][550];
bool v[550];
int n,m;
void dfs(int u)
{
    v[u]=1;
    for(int i=1;i<=n;i++)
        if(a[u][i]==1&&!v[i])
        dfs(i);
}
bool ok()
{
    for(int i=1;i<=n;i++)
        if(v[i]==0)return 0;
    return 1;
}
int main()
{
    int i,j;
    cin>>n>>m;
    memset(a,0,sizeof(a));
    for(i=0; i<m; i++)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=a[y][x]=1;
    }
    int s=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1)
    {
        memset(v,0,sizeof(v));
        a[i][j]=a[j][i]=0;
        dfs(1);
        if(!ok())s++;
        a[i][j]=a[j][i]=1;
    }
  cout<<s/2<<endl;
}


Measured memory_bytes: 1408
object Main extends App {
  val line1 = io.StdIn.readLine.split(' ')
  val line2 = io.StdIn.readLine.split(' ')

  val H = line1(0).toInt
  val W = line1(1).toInt

  val h = line2(0).toInt
  val w = line2(1).toInt

  val white = (H-h) * (W-w)

  println(white)
}


Measured memory_bytes: 27204
#include<bits/stdc++.h>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
li read(){
	li x = 0;
	int y = 0,c = gc;
	while(!isdigit(c)){
		y = c;
		c = gc;
	}
	while(isdigit(c)){
		x = (x << 1) + (x << 3) + (c ^ '0');
		c = gc;
	}
	return y == '-' ? -x : x;
}
void print(li q){
	if(q < 0){
		pc('-');
		q = -q;
	}
	if(q >= 10) print(q / 10);
	pc(q % 10 + '0');
}
li n,d1,d2;
bool vst[610][610][2],v2[610][610][2];
int t1[100010][2],s1,t2[100010][2],s2;
li wk(li q){
	li tp = sqrtl(q);
	while(tp * tp > q) --tp;
	while((tp + 1) * (tp + 1) <= q) ++tp;
	return tp * tp == q ? tp : -1;
}
int sl[4];
void dfs1(int i,int j){
	if(v2[i][j][0]) return;
	v2[i][j][0] = 1;
	for(int l = 1;l <= s1;++l){
		int tx = i + t1[l][0],ty = j + t1[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2){
			vst[tx][ty][0] = !vst[i][j][0];
			dfs1(tx,ty);
		} 
		ty = j - t1[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2) {
			vst[tx][ty][0] = !vst[i][j][0];
			dfs1(tx,ty);
		}
		tx = i - t1[l][0];
		ty = j + t1[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2){
			vst[tx][ty][0] = !vst[i][j][0];
			dfs1(tx,ty);
		} 
		ty = j - t1[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2) {
			vst[tx][ty][0] = !vst[i][j][0];
			dfs1(tx,ty);
		}
	}
}
void dfs2(int i,int j){
	if(v2[i][j][1]) return;
	v2[i][j][1] = 1;
	for(int l = 1;l <= s2;++l){
		int tx = i + t2[l][0],ty = j + t2[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2){
			vst[tx][ty][1] = !vst[i][j][1];
			dfs2(tx,ty);
		} 
		ty = j - t2[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2) {
			vst[tx][ty][1] = !vst[i][j][1];
			dfs2(tx,ty);
		}
		tx = i - t2[l][0];
		ty = j + t2[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2){
			vst[tx][ty][1] = !vst[i][j][1];
			dfs2(tx,ty);
		} 
		ty = j - t2[l][1];
		if(tx >= 0 && tx < n * 2 && ty >= 0 && ty < n * 2) {
			vst[tx][ty][1] = !vst[i][j][1];
			dfs2(tx,ty);
		}
	}
}
int main(){
	li i,j;
	n = read();d1 = read();d2 = read();
	for(i = 0;i * i <= d1;++i){
		j = d1 - i * i;
		if(wk(j) != -1){
			t1[++s1][0] = i;
			t1[s1][1] = wk(j);
			//cout<<i<<" "<<wk(j)<<endl;
		}
	}
	for(i = 0;i * i <= d2;++i){
		j = d2 - i * i;
		if(wk(j) != -1){
			t2[++s2][0] = i;
			t2[s2][1] = wk(j);
			//cout<<i<<" "<<wk(j)<<endl;
		}
	}
	for(i = 0;i < n * 2;++i){
		for(j = 0;j < n * 2;++j) dfs1(i,j);
	}
	for(i = 0;i < n * 2;++i){
		for(j = 0;j < n * 2;++j) dfs2(i,j);
	}
	for(i = 0;i < n * 2;++i){
		for(j = 0;j < n * 2;++j){
			++sl[(int)vst[i][j][0] * 2 + vst[i][j][1]];
		}
	}
	int nw = 0,mx = sl[0],as = 0;
	for(i = 1;i <= 3;++i) if(sl[i] > mx){
		mx = sl[i];
		as = i;
	}
	for(i = 0;i < n * 2;++i){
		for(j = 0;j < n * 2;++j){
			//cout<<i<<" "<<j<<" "<<(int)vst[i][j][0] * 2 + vst[i][j][1]<<endl;
			if((int)vst[i][j][0] * 2 + vst[i][j][1] == as){
				++nw;
				print(i);pc(' ');print(j);pc('\n');
				if(nw == n * n) break;
			}
		}
		if(nw == n * n) break;
	}
	return 0;
}

Measured memory_bytes: 30464
def main():
    H, W, K = map(int, input().split())

    dp = [[0] * (W + 5) for _ in range(H + 5)]

    dp[0][0] = 1
    MOD = 10**9 + 7

    for h in range(H):
        for j in range(1 << W-1):
            a = str(bin(j))[2:].zfill(W-1)
            if a.count('11') >= 1:
                continue
            for w in range(W):
                if w == 0:
                    # まっすぐ移動
                    if a[w] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                    # 右へ移動
                    if a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                elif w == W-1:
                    # まっすぐ移動
                    if a[w-1] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                    # 左へ移動
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                else:
                    # 左へ移動
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                    # 右へ移動
                    elif a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                    # まっすぐ移動
                    else:
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD

    print(dp[H][K-1])

                
main()

Measured memory_bytes: 42480
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
int N, K;
vector<vector<int> > ed;
vector<vector<int> > ed2;
vector<int> ok;
vector<int> v;
vector<int> c;
vector<int> c2;
vector<int> dp;
int dfs(int a, int d) {
	v[a] = 1;
	if (dp[a] != -1) {
		return dp[a];
	}
	if (c[a] == 0) {
		dp[a] = 0;
		return 0;
	}
	dp[a] = 100000000;
	for (int i = 0; i < ed[a].size(); i++) {
		if (v[ed[a][i]] == 0) {
			dp[a] = min(dp[a] , 1 + dfs(ed[a][i], d + 1));
		}
	}
	return dp[a];
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> N>>K;
	ed.resize(N);
	ok.resize(N,0);
	v.resize(N, 0);
	c.resize(N, 0);
	c2.resize(N, 0);
	dp.resize(N, -1);
	int res = 0;
	int a;

	for (int i = 0; i < N; i++) {
		cin >> a;
		a--;
		if (a == -1) {
			ok[i] = 1;
		}
		else {
			ed[a].push_back(i);
			c[a]++;
			c2[i]++;
		}

	}
	for (int i = 0; i < N; i++) {
		if (c[i] == 0) {
			ok[i] = 1;
		}
	}

	for (int i = 0; i < N; i++) {
		if (c2[i] == 0) {
			dfs(i, 0);
		}
	}
	for (int i = 0; i < N; i++) {
		if (dp[i] < K) {
			ok[i] = 1;
		}
	}
	for (int i = 0; i < N; i++) {
		if (ok[i] == 1)res++;
	}
	cout << res << endl;
}

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

using namespace std;
using ll = long long;
using vi = vector<ll>;

ll M = 998244353;

ll pow(ll a, ll b, int m) {
  ll r = 1, e = a;
  while (b) {
    if (b & 1) r = (r * e) % m;
    e = (e * e) % m;
    b >>= 1;
  }
  return r;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vi a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  if (a[0] != 0) {
    cout << "0\n";
    return 0;
  }
  if (a.size() == 1) {
    cout << "1\n";
    return 0;
  }
  sort(a.begin(), a.end());
  if (a[1] != 1) {
    cout << "0\n";
    return 0;
  }
  ll r = 1;
  int p = 1, c = 1;
  for (int i = 1; i < n; i++) {
    if (a[i] == a[i - 1]) c++;
    else if (a[i] != a[i - 1] + 1) {
      cout << "0\n";
      return 0;
    } else {
      (r *= pow(p, c, M)) %= M;
      p = c;
      c = 1;
    }
  }
  (r *= pow(p, c, M)) %= M;
  if (r < 0) r += M;
  cout << r << "\n";
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int n,d,ans; cin>>n>>d>>ans;
    vint a(n); rep(i,n)cin>>a[i];
    rep(i,n){
        for(int j = 1; j<=d; j+=a[i])ans++;
    }
    cout<<ans<<endl; return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	long long h, w;
	scanf("%lld%lld", &h, &w);
	
	if (h > 1 && w > 1) {
		printf("%lld\n", (h*w+1)/2);
		return 0;
	}
	
	puts("1");
	
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<cmath>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
set<string> cands;
int dp[55][35];
bool freeday[55][35];
bool accept[55];
ll w[55];
int us[55];
int main()
{
  int n;
  while(cin >> n && n!=0) 
    {
      bool clear=false;
      fill(dp[0],dp[52],0);
      memset(freeday,false,sizeof(freeday));
      memset(accept,false,sizeof(accept));
      for(int i=0;i<n;i++)
	{
	  int days;
	  dp[i][0]=0;
	  cin >> days;
	  for(int j=0;j<days;j++)
	    {
	      int day;
	      cin >> day;
	      freeday[i][day]=true;
	    }
	  w[i]=1LL<<i;
	}

      for(int day=1;day<=30;day++)
	{
	  ll s=0;
	  memset(us,0,sizeof(us));
	  for(int man=0;man<n;man++)
	    {
	      for(int opp=man+1;opp<n;opp++)
		{
		  if(freeday[man][day] && freeday[opp][day])
		    {
		      us[man]=us[opp]=1;
		      s |= w[man] | w[opp];
		    }
		}
	    }
	  if(s==(1LL<<n)-1)
	    {
	      cout << day << endl;
	      clear=true;
	      break;
	    }
	  for(int i=0;i<n;i++)
	    {
	      if(us[i])
		{
		  w[i]=s;
		}
	    }
	}
      if(!clear) cout << -1 << endl;
    }
}



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

typedef long long LL;
typedef double DB;

#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define R(i,n) for(int i=0;i<=(n);++i)
#define fill(a,b) memset(a,b,sizeof a)


int main()
{
//	freopen("test.txt","r",stdin);
	int a,b;
	cin >> a >> b;
	if(a <= 0 && b >= 0)
		puts("Zero");
	else if((a > 0 && b > 0) || (b - a)&1)
		puts("Positive");
	else
		puts("Negative");

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const ll inf = 1e18;const double INF = 1e12, EPS = 1e-9;

using VL = vector<ll>;
using VVL = vector<VL>;
int n, a[5000];
vector<vi> e;

const VVL rec(int c, int p){
	VVL dp(1, VL(2, inf));
	dp[0][a[c] < 0] = a[c];
	
	for(int cld : e[c]) if(cld != p){
		const VVL& tmp = rec(cld, c);
		VVL next(dp.size() + tmp.size(), VL(2, inf));
		
		rep(i, tmp.size()) rep(j, 2) if(tmp[i][j] < inf)
		rep(k, dp.size()) rep(l, 2) if(dp[k][l] < inf){
			
			next[i + k][j | l] = min(next[i + k][j | l], tmp[i][j] + dp[k][l]);
			if(j == 0 || tmp[i][j] < 0) next[i + k + 1][l] = min(next[i + k + 1][l], dp[k][l]);
		}
		
		dp.swap(next);
	}
	return dp;
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	cin >> n; e.resize(n);
	rep(i, n) cin >> a[i];
	rep(i, n - 1){
		int u, v; cin >> u >> v; u--; v--;
		e[u].pb(v);
		e[v].pb(u);
	}
	const VVL& ans = rec(0, 0);
	int res = n - 1;
	rep(i, ans.size()) rep(j, ans[i].size()) if(ans[i][j] < inf) if(j == 0 || ans[i][j] < 0) res = min(res, i);
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 2152
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	int MOD = 1000000007;

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int a[] = new int[n+1];
		int d[] = new int[n+1];
		int dup = 0;
		for(int i=0; i<n+1; i++) {
			a[i]=sc.nextInt();
			d[a[i]]++;
			if(d[a[i]]>1) {
				dup = a[i];
			}
		}
		int l = -1;
		int r = -1;
		for(int i=0; i<n+1; i++) {
			if(a[i]==dup) {
				if(l == -1) l = i;
				else r = i;
			}
		}

		init(n+1);

		for(int k=1; k<=n+1; k++) {
			long ans = ((combi(n+1, k) + MOD) - combi(l + n-r, k-1)) % MOD;
			System.out.println(ans);
		}

		sc.close();
	}

	long fact[];
	long ifact[];
	private long combi(int n, int k) {
		if(k<0 || k>n) return 0;
		return (((fact[n] * ifact[k]) % MOD) * ifact[n-k]) % MOD;
	}

	private void init(int n) {
		fact = new long[n+1];
		ifact = new long[n+1];

		fact[0]=1;
		for(int i=1; i<=n; i++) {
			fact[i] = (fact[i-1] * i) % MOD;
		}
		ifact[n] = pow(fact[n], MOD-2);
		for(int i=n; i>=1; i--) {
			ifact[i-1] = (ifact[i] * i) % MOD;
		}
	}

	private long pow(long x, int n) {
		if(n==0) return 1;
		long ret = pow(x, n/2);
		if(n%2==0) {
			ret = (ret * ret) % MOD;
		}else {
			ret = (((ret * ret) % MOD) * x) % MOD;
		}
		return ret;
	}

}


Measured memory_bytes: 62164
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
using namespace std;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
int n;
string s;
int main()
{
	cin>>n>>s;
	if(s.size()%2==1) puts("No");
	else
	{
		for(int i=0;i<s.size()/2;i++)
		{
			if(s[i]!=s[i+(s.size()/2)])
			{
				puts("No");
				return 0;
			}
		}
		puts("Yes");
	}
	return 0;
}


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

char s[100][100];
int h, w;

int main(void){
  cin >> h >> w;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> s[i][j];
    }
  }
  for(int i = 0 ; i < w + 2; i++){
    cout << "#";
  }
  cout << endl;
  for(int i = 0; i < h; i++){
    for(int j = -1; j < w + 1; j++){
      if(j == -1 or j == w){
	cout << "#";
      }
      else{
	cout << s[i][j];
      }
    }
    cout << endl;
  }
  for(int i = 0 ; i < w + 2; i++){
    cout << "#";
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int S,h,m,s,a,b;
	scanf("%d",&S);
	h=S/3600;
	S=S%3600;
	m=S/60;
	s=S%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

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

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> cnt(N, 1), red(N);
	red[0] = 1;
	for (int i = 0; i < M; ++i) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		--cnt[x]; ++cnt[y];
		if (red[x]) red[y] = 1;
		if (!cnt[x]) red[x] = 0;
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) ans += red[i];
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
using namespace std;
long long MOD = 1e9 + 7;

string S;
int K;

int main() {
	cin >> S >> K;
	while (K >= 0) {
		if (K == 1) {
			cout << S.substr(0, 1) << endl;
			return 0;
		}
		else if (S[0] == '1') {
			K--;
			S = S.substr(1);
		}
		else {
			cout << S[0] << endl;
			return 0;
		}
	}
	return 0;
}

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

int main(){
  int A,B,C,X;cin>>A>>B>>C>>X;
  int ans=0;
  for(int a=0;a<=A;a++){
    for(int b=0;b<=B;b++){
      for(int c=0;c<=C;c++){
        if(500*a+100*b+50*c==X)ans++;
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i <= (n) ; i ++ )
#define all(x) (x).begin(),(x).end()
using ll = long long;
using namespace std;

int main() {
  ll r,g,b,n;
  cin>>r>>g>>b>>n;
  int ans=0;
  rep(i,n/r){
     rep(j,n/g){
         if((n-i*r-j*g)>=0&&(n-i*r-j*g)%b==0){
           ans++;
         }
     }
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 256
from itertools import permutations
from collections import defaultdict

N = int(input())

P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
res = 0
loop = 0

d = defaultdict(int)

for perm in permutations(range(1,N+1)):
    d[perm] = loop
    loop += 1

res = abs(d[P] - d[Q])

print(res)

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

using namespace std;
int main()
{
    int m[3][3];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++) cin >> m[i][j];
    bool ans=true;
    int a[3],b[3],c[3],d[3];
    for(int i=0;i<3;i++)
    {
        a[i]=m[i][0]-m[i][1];
        b[i]=m[i][2]-m[i][1];
        c[i]=m[0][i]-m[1][i];
        d[i]=m[2][i]-m[1][i];
    }
    if(a[0]!=a[1]||a[1]!=a[2]) ans=false;
    if(b[0]!=b[1]||b[1]!=b[2]) ans=false;
    if(c[0]!=c[1]||c[1]!=c[2]) ans=false;
    if(d[0]!=d[1]||d[1]!=d[2]) ans=false;
    if(ans) printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 256
use std::cmp::Ordering;
use proconio::input;
use std::collections::BinaryHeap;

fn main() {
    input! {
        h: usize,
        w: usize,
        ch: usize,
        cw: usize,
        dh: usize,
        dw: usize,
        s: [String; h],
    }

    let (ch, cw, dh, dw) = (ch - 1, cw - 1, dh - 1, dw - 1);

    let s: Vec<Vec<char>> = s.iter().map(|line| line.chars().collect()).collect();

    let mut costs = vec![vec![None; w]; h];

    let mut queue = BinaryHeap::new();
    queue.push(Data {position: (ch, cw), cost: 0});

    while !queue.is_empty() {
        let Data {
            position: pos,
            cost,
        }  = queue.pop().unwrap();

        if s[pos.0][pos.1] == '#' {
            continue;
        }

        if let Some(prev_cost) = costs[pos.0][pos.1] {
            if prev_cost <= cost {
                continue;
            } 
        }

        costs[pos.0][pos.1] = Some(cost);

        let pos = (pos.0 as i32, pos.1 as i32);

        for dy in -2..(2 + 1) {
            let next_y = pos.0 + dy;
            
            if next_y < 0 || h <= next_y as usize {
                continue;
            }

            for dx in -2..(2 + 1) {
                let next_x = pos.1 + dx;

                if next_x < 0 || w <= next_x as usize || (dy == 0 && dx == 0) {
                    continue;
                }

                let next_cost = cost + (dx*dx + dy*dy != 1) as i32;

                queue.push(Data{
                    position: (next_y as usize, next_x as usize),
                    cost: next_cost,
                });
            }
        }

    }

    let ans = costs[dh][dw].unwrap_or(-1);
    println!("{}", ans);

}

#[derive(Debug, PartialEq, Eq)]
struct Data {
    position: (usize, usize),
    cost: i32,
}

impl Ord for Data {
    fn cmp(&self, other: &Data) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for Data {
    fn partial_cmp(&self, other: &Data) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}


Measured memory_bytes: 22136
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int64_t, int64_t>;
constexpr int64_t kInf = INT64_MAX / 2L;

// std::cout << std::setprecision(20) << 1.1 << endl;

int64_t Myxor(const int64_t x) {
  if (x < 0) {
    return 0;
  }
  int64_t result = 0;
  int64_t d = 0;
  while ((x >> d) > 0) {
    const int64_t L = (1L << d);
    if (d == 0 && (x % 4 == 1 || x % 4 == 2)) {
      result++;
    } else if ((x / L) % 2 == 1) {
      if ((x % 2) == 0) {
        result += (1LL << d);
        // cerr << "hoge " << d << ", " << (1L << d) << endl;
      }
    }
    d++;
  }
  return result;
}

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

  int64_t A, B;
  cin >> A >> B;
  cout << (Myxor(B) ^ Myxor(A - 1)) << endl;
  return 0;
}


Measured memory_bytes: 3660
import sys
readline = sys.stdin.readline

N,W = map(int,readline().split())

import numpy as np

dp = np.zeros(W + 1, dtype = int)

for i in range(N):
  w,v = map(int,readline().split())
  np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
  
print(dp.max())

Measured memory_bytes: 29060
S = list(input())
ANS = [0]*len(S)
count = 0
for i in range(len(S)):
    if S[i] == 'L':
        count = 0
    elif S[i] == 'R':
        count += 1
        if i != len(S)-1 and S[i+1] == 'L':
            ANS[i] += count//2+count%2
            ANS[i+1] += count//2
        elif i == len(S)-1:
            ANS[i] += count
count = 0
for i in range(len(S)-1,-1,-1):
    if S[i] == 'R':
        count = 0
    elif S[i] == 'L':
        count += 1
        if i != 0 and S[i-1] == 'R':
            ANS[i] += count//2+count%2
            ANS[i-1] += count//2
        elif i == 0:
            ANS[i] += count
print(*ANS)

Measured memory_bytes: 7096
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(r) r.begin(),r.end()
using namespace std;
typedef int64_t ll;
typedef vector<ll> vll;
template<typename T, typename U> static void amax(T &x, U y) { if (x < y)x = y; }
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll N;
        in >> N;
        vll a(N);
        rep(i, N) {
            in >> a[i];
        }
        sort(all(a));
        vll b(a);
        b.erase(unique(all(b)), b.end());
        ll maSum = 0;
        rep(i, b.size()-2) {
            ll sum = 0;
            ll sums[3] = {};
            sums[0] = upper_bound(all(a), b[i+0]) - lower_bound(all(a), b[i+0]);
            sums[1] = upper_bound(all(a), b[i+1]) - lower_bound(all(a), b[i+1]);
            sums[2] = upper_bound(all(a), b[i+2]) - lower_bound(all(a), b[i+2]);
            if (abs(b[i+0] - b[i+1]) <= 2 && abs(b[i + 1] - b[i + 2]) <= 2) {
                sum = sums[0] + sums[1] + sums[2];
            }
            else if (abs(b[i + 0] - b[i + 1]) <= 2) {
                sum = sums[0] + sums[1];
            }
            else if (abs(b[i + 1] - b[i + 2]) <= 2) {
                sum = sums[1] + sums[2];
            }
            else {
                sum = max({sums[0], sums[1], sums[2]});
            }
            amax(maSum, sum);
        }
        if (b.size() == 1) {
            maSum = a.size();
        }
        if (b.size() == 2) {
            if (abs(b[0]-b[1]) <= 2) {
                maSum = a.size();
            }
            else {
                ll sum = 0;
                sum = upper_bound(all(a), b[0]) - lower_bound(all(a), b[0]);
                amax(maSum, sum);
                sum = upper_bound(all(a), b[1]) - lower_bound(all(a), b[1]);
                amax(maSum, sum);
            }
        }
        out << maSum << '\n';
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <complex>
#include <ctime>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(ll i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

using Graph = vector<vector<ll>>;

#define ketasitei setprecision(15) //15桁表示

const ll MOD = 1000000007;
const double PI = 3.1415926535897932;


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

	ll n;
	cin >> n;

	vector<ll> ma(10000001, 0);

	for (ll i = 1; i <= n; i++)
	{
		ll t = 1;
		while (i*t<=n)
		{
			ma[i * t]++;
			t++;
		}
	}
	ll ans = 0;
	for (ll i = 0; i < n; i++)
	{
		ans += (i + 1) * ma[i + 1];
	}
	cout << ans << endl;

	return 0;

}

Measured memory_bytes: 81304
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b;
    cin >> a >> b;
    if(a%3==0 || b%3==0 || (a+b)%3==0) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
    return 0;
    
    
}


Measured memory_bytes: 256
def prime_table(n):
  list = [True for _ in range(n + 1)]
  list[0] = False
  list[1] = False
  i = 2
  while i * i <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1
  prime_cumsum = []
  amount = 0
  for i in range(len(list)):
    if(i == 0):
      prime_cumsum.append(0)
      continue
    if(list[i] == True and (i + 1) % 2 == 0 and list[(i+1)//2] ==True):
      amount +=1
    prime_cumsum.append(amount)
  return prime_cumsum

q = int(input())
question = [list(map(int, input().split())) for _ in range(q)]
prime = prime_table(10**5+1)
for l, r in question:
  print(prime[r] - prime[l-1])

Measured memory_bytes: 29064
#include <iostream>
using namespace std;
const int N = 100000 + 10;
int n, x[N], y[N], t[N];
bool chk(int x, int y, int t) {
    int sum = abs(x) + abs(y);
    if (sum > t) return 0;
    if ((t - sum)&1) return 0;
    return 1;
}
int main() {
    scanf("%d", &n);
    bool ok = 1;
    for (int i = 1; i <= n; i ++) {
        scanf("%d %d %d", &t[i], &x[i], &y[i]);
        ok &= chk(x[i]-x[i-1], y[i]-y[i-1], t[i]-t[i-1]);
    }
    printf("%s\n", ok?"Yes":"No");

}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
char s[100][100],t[100][100];
int main()
{
	int a,b,n,m,i,j,k,count=0,count1=0,max=-100;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%s",&s[i]);
	}
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		scanf("%s",&t[i]);
	}
	for(i=0;i<n;i++)
	{
		for(j=i;j<n;j++)
		{
			if(strcmp(s[i],s[j])==0)
			{
				count++;
			}
		}
		for(j=0;j<m;j++)
		{
			if(strcmp(s[i],t[j])==0)
			{
				count1++;
			}
		}
		count-=count1;
		if(count>max)
		{
			max=count;
		}
		count=0;
		count1=0;
	}
	if(max<0)
	{
		printf("0");
	}
	else
	{
		printf("%d",max);
	}
}

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

int main() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());

    string t;
    cin >> t;
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());

    if (s < t)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    



}


Measured memory_bytes: 3612