akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int main()
{
    int n;
    cin>>n;
    int rem=n%10;
    if(rem==2 || rem==4 ||rem==5 ||rem==7 ||rem==9)
    {
        cout<<"hon";
    }
    else if(rem==0 || rem==1 ||rem==6 ||rem==8)
    {
        cout<<"pon";
    }
    else
        cout<<"bon";
}


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

using namespace std ;

#define sz(v) (int)v.size()
#define ll long long
#define all(v)  v.begin() , v.end()
#define rall(v)  v.rbegin() , v.rend()
#define pf push_front
#define pb push_back
#define fast FastInputOutput() ;
#define Clear( container , value ) memset( container , value , sizeof container )
#define PI acos( -1.0 )
#define forn( t , v , be , n ) for( t v = be ; v < n ; v++ )
#define fore( x , j ) for( auto x : j )
#define se second
#define fr first
//#define c_b fflush(stdin);

const ll Long_max = numeric_limits < ll > :: max() ;
const int Int_max = numeric_limits < int > :: max() ;
/*
void File_input( string pathIn ) {
    freopen( pathIn.c_str(), "r", stdin ) ;
}

void File_output( string pathOut ) {
    freopen( pathOut.c_str(), "w", stdout ) ;
}
*/
int main() {

  int a , b ;
  string str ;
  cin >> a >> b ;
  cin >> str ;
  if( a + b + 1 != sz( str ) ){
    cout << "No\n" ;
    return 0 ;
  }

  vector < int > pos ;
  forn( int , i , 0 , sz( str ) ) {
    if( str[ i ] == '-' ) pos.pb( i ) ;
  }

  if( sz( pos ) == 1 && pos.back() + 1 == a + 1 ){
    cout << "Yes\n" ;
  } else cout << "No\n" ;

  return 0 ;;;;;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 5050
#define mod 1000000007
typedef long long ll;
int head[N],to[N<<1],nxt[N<<1],cnt,n,siz[N];
ll f[N][N],tmp[N],g[N];
inline void add(int u,int v) {
	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void upd(ll &x,ll y) {
	x=x+y; if(x>=mod) x-=mod;
}
void dfs(int x,int y) {
	int i,j,k;
	siz[x]=1; f[x][1]=1;
	for(i=head[x];i;i=nxt[i]) {
		if(to[i]!=y) {
			dfs(to[i],x);
			for(j=0;j<=siz[x];j++) tmp[j]=f[x][j],f[x][j]=0;
			for(j=0;j<=siz[x];j++) {
				for(k=0;k<=siz[to[i]];k++) {
					upd(f[x][j+k],tmp[j]*f[to[i]][k]%mod);
				}
			}
			siz[x]+=siz[to[i]];
		}
	}
	for(k=siz[x];k>=1;k--) {
		if(k%2==0) {
			upd(f[x][0],mod-f[x][k]*g[k>>1]%mod);
		}
	}
}
int main() {
	scanf("%d",&n);
	int i,x,y;
	for(i=1;i<n;i++) {
		scanf("%d%d",&x,&y); add(x,y); add(y,x);
	}
	for(g[0]=1,i=1;i<=n/2;i++) {
		g[i]=(2*i-1)*g[i-1]%mod;
	}
	dfs(1,0);
	printf("%lld\n",mod-f[1][0]);
}

Measured memory_bytes: 198400
import collections
def div(n):
    a = []
    for i in range(2,n+1):
        while n % i == 0:
            a.append(i)
            n //= i
    return a
n = int(input())
cnt = 1
ans = 0
for i in range(1,n+1,2):
    a = collections.Counter(div(i))
    a = list(a.values())
    for j in range(len(a)):
        cnt *= (a[j]+1)
    if cnt == 8:
        ans += 1
    cnt = 1
print(ans)

Measured memory_bytes: 3316
#include <iostream>

using namespace std;

#define M 1000000007

typedef long long ll;

int n, h, d;

ll fa[1222333];
ll fs[1222333];

#define N (1<<20)
ll p[2*N];

void addVal(int k, ll x) {
    k += N;
    p[k] += x;
    p[k] %= M;
    if (p[k] < 0) p[k] += M;
    for (k /= 2; k >= 1; k /= 2) {
        p[k] = p[2*k]+p[2*k+1];
        p[k] %= M;
    }
}

ll getSum(int a, int b) {
    a += N; b += N;
    ll s = 0;
    while (a <= b) {
        if (a%2 == 1) s = (s+p[a++])%M;
        if (b%2 == 0) s = (s+p[b--])%M;
        a /= 2; b /= 2;
    }
    return s;
}

int main() {
    cin >> n >> h >> d;
    fa[0] = 1;
    fs[0] = 0;
    for (int i = 1; i <= n; i++) {
        fa[i] = (fa[i-1]*i)%M;
        fs[i] = (fs[i-1]+fa[i])%M;
    }
    addVal(0,fa[n]);
    addVal(1,-fa[n]);
    for (int i = 0; i <= h-1; i++) {
        ll s1 = getSum(0,i)%M;
        ll s2 = s1*fs[n]%M;
        addVal(i+1,s2);
        addVal(min(h,i+d+1),-s2);
        if (h-i <= d) {
            addVal(h,s1);
            addVal(h+1,-s1);
        }
    }
    cout << getSum(0,h) << "\n";
}

Measured memory_bytes: 34944
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    X = readInts()

    A = sorted(X)[n//2-1:n//2+1] # 中央値のどちらか
    #print(A)
    for x in X:
        #print(x <= A[0]) # False 0 True 1
        print(A[x <= A[0]]) # 1




if __name__ == '__main__':
  main()


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

int main(void){
	int i;	
	char s[19];
	char c;
	for(i=0; i<19; i++){
		scanf("%c",&c);
		if(i==5 || i==13){
			printf(" ");
		}else{
	//		scanf("%c", &c);
			printf("%c", c);
		}
	}

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる




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

  map<ll,int> p;
  int notz=0;;
  rep(i,n){
    ll x;
    cin>>x;
    if(p.count(x)) p.at(x)++;
    else p[x]=1;
    if(x!=0) notz++;
  }

  if(n%3!=0){
    cout << (notz==0?"Yes":"No") << endl;
  }
  else if(notz==0) cout << "Yes" << endl;
  else if(notz==2*n/3 && p.size()==2) cout << "Yes" << endl;
  else if(p.size()!=3) cout << "No" << endl;

  else {
    ll now=0;
    vector<ll> q(3);
    vector<ll> r(3);
    for(auto x : p){
      q[now]=x.fi;
      r[now]=x.se;
      now++;
    }
    cout << (((q[0]^q[1])==q[2] && r[0]==r[1] && r[1]==r[2])?"Yes":"No") << endl;
  }

}


Measured memory_bytes: 5120
import sys

N = int(sys.stdin.readline())

l = {}
for i in range(0, N):
    s, p = sys.stdin.readline().split(" ")
    p = int(p)
    if s not in l:
        l[s] = []
    l[s].append([i, p])


l = sorted(l.items(), key=lambda x: x[0])
for ll in l:
    r = sorted(ll[1], key=lambda x: x[1], reverse=True)
    for rr in r:
        print(rr[0] + 1)


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

#define pb     push_back
#define mp     make_pair
#define all(v) v.begin() , v.end()
#define allr(v) v.rbegin(), v.rend()
const ll INF =  0x3f3f3f3f;
const int MOD = 1e9+7;
const int MAX = 1e5+5;
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}

int n, a, b;
ll c, d;

int main(int argc, char const *argv[])
{
  scanf("%d %d %d %lld %lld" , &n, &a, &b, &c, &d);
  bool poss = false;
  int diff = b - a;

  for(int i = 0 ; i < n ; i++){
  	ll g = 1ll*(n - 1 - i)*d - i*c;
  	ll l = 1ll*(-i)*d + (n - 1 - i)*c;
  	if(l <= diff && diff <= g)
  		poss = true;
  } 

  if(poss)
  	printf("YES");
  else
  	printf("NO");

  return 0;
}  

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int A, B, C; cin >> A>> B >> C;
    cout << (A+B+C >= 22 ? "bust" : "win") << endl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

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

	ll n;
	cin >> n;
	vll p(n);
	for (ll i = 0; i < n; i++) cin >> p[i];
	ll ans = 0;
	for (ll i = 0; i < n - 2; i++) {
		if (p[i] < p[i + 1] && p[i + 1] < p[i + 2]) ans++;
		else if (p[i] > p[i + 1] && p[i + 1] > p[i + 2]) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main(void){
    long long N, M;
    cin >> N >> M;
    vector<long long> X = vector<long long>(M, 0);
    for (int cnt = 0; cnt < M; ++cnt){
        cin >> X[cnt];
    }
    sort(X.begin(), X.end());

    vector<long long> diff = vector<long long>(M - 1, 0);
    for (int cnt = 0; cnt < M - 1; ++cnt){
        diff[cnt] = X[cnt + 1] - X[cnt];
    }
    sort(diff.begin(), diff.end());
    int result = 0;
    for (int cnt = 0; cnt < M - N; ++cnt){
        result += diff[cnt];
    }
    cout << result << endl;
    return 0;
}



Measured memory_bytes: 1792
/*input
3
1000000000 1000000000 1000000000
*/
#include<bits/stdc++.h>
#define fn(i,n) for(long long i=0;i<n;i++)
#define fn1(i,n) for(long long  i=1;i<=n;i++)
#define ll long long int
#define mp(x,y) make_pair(x,y)
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n;cin>>n;
ll dp[n][n],a[n];
fn(i,n){cin>>a[i];dp[i][i]=0;}
fn(i,n-1)
dp[i][i+1]=a[i+1]+a[i];
fn1(i,n-1)a[i]+=a[i-1];
for(int l=2;l<n;l++)
{
	for(int k=0;k+l<n;k++)
	{
		if(k>0)
		dp[k][k+l]=a[k+l]-a[k-1];
		else
		dp[k][k+l]=a[k+l];
		ll p=1e18;
		fn(j,l)
		{
			p=min(p,dp[k][k+j]+dp[k+j+1][k+l]);
		}
		dp[k][k+l]+=p;
	}
}
//fn(i,n)
//cout<<a[i]<<" ";
/*
fn(i,n)
{
	fn(j,n)
	cout<<dp[i][j]<<" ";
	cout<<endl;
}*/
cout<<dp[0][n-1];
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
const long long INF=1000000000;
typedef long long ll;
ll dp[1000003];
ll n, k;
ll high[100005];
int main(){
   cin >> n>>k;
   for (int i = 0; i < n;i++){
       cin >> high[i];
   }
   for (int i = 0; i < n;i++){
       dp[i] = INF;
   }
    dp[0] = 0;
    for (int tmp = 0; tmp < n; tmp++){
        for (int i = 1; i <= k; i++){
            if (i + tmp >= n)
                break;
            else{
                dp[i + tmp] = min(dp[i + tmp], abs(high[tmp] - high[i + tmp]) + dp[tmp]);
            }
        }
    }
    cout << dp[n - 1];
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 55;
int N;
string S[MAX];
map<char, int> mp[MAX];

int main(void) {
    cin >> N;
    REP(i, N) {
        cin >> S[i];
        FORE(e, S[i]) mp[i][e]++;
    }
    map<char, int> mp2;
    for (char c = 'a'; c <= 'z'; ++c) {
        int cnt = INF;
        REP(i, N) {
            chmin(cnt, mp[i][c]);
        }
        if (cnt) mp2[c] = cnt;
    }
    string ans = "";
    FORE(e, mp2) REP(i, e.second) ans += e.first;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

/*
M -> 1900ms 1/2で正解
M-N -> 100ms 必ず正解
プログラムの実行時間の総和の期待値をXmsとしたとき，Xを出力せよ

N <= 5のときには M = N;
N > 5のときには M = 5;


*/

int main() {
  int n,m;
  cin >> n >> m;

  int p = (int)pow(2,m);
  int correct = n - m;
  ll ans = 0;
  ll total_n = p * correct * 100;
  ll total_m = p * m * 1900;

  ll total = total_n + total_m;

  cout << total << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
int n,m,k,mn,dist[805][805];
char s[805][805];
queue<pair<int,int> >q;
int dis(int x,int y){return (min(min(x,y),min(n-1-x,m-1-y))+k-1)/k;}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	memset(dist,-1,sizeof(dist));
	for(int i=0;i<n;i++)
	{
		scanf("%s",s[i]);
		for(int j=0;j<m;j++)
		{
			if(s[i][j]=='S')
			{
				q.push(make_pair(i,j));
				dist[i][j]=0;
				mn=dis(i,j)+1;
			}
		}
	}
	while(!q.empty())
	{
		int x=q.front().first,y=q.front().second;
		q.pop();
		if(dist[x][y]==k)break;
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>=0&&xx<n&&yy>=0&&yy<m&&s[xx][yy]=='.'&&dist[xx][yy]==-1)
			{
				dist[xx][yy]=dist[x][y]+1;
				q.push(make_pair(xx,yy));
				mn=min(mn,dis(xx,yy)+1);
			}
		}
	}
	printf("%d\n",mn);
	return 0;
}

Measured memory_bytes: 3456
#include <stdio.h>

int main() {
	int A, B, C, D;
	int left, right;

	scanf("%d", &A);
	scanf("%d", &B);
	scanf("%d", &C);
	scanf("%d", &D);

	left = A + B;
	right = C + D;

	if (left > right) {
		printf("Left\n");
	} else if (left == right) {
		printf("Balanced\n");
	} else if (left < right) {
		printf("Right\n");
	}
}


Measured memory_bytes: 128
n = int(input())
a = list(map(int, input().split()))
l = len(a)
cnt = 0
a_ = 0
x = -1
# -から
for i in range(l):
    a_ += a[i]
    if x == -1:
        if a_ > x:
            cnt += a_ -x
            a_ = -1
    else:
        if a_ < x:
            cnt += x-a_
            
            a_ = 1

    x *= -1

cnt1 = 0
a_ = 0
x1 = 1
# +から
for i in range(l):
    a_ += a[i]
    if x1 == -1:
        if a_ > x1:
            cnt1 += a_ -x1
            a_ = -1
    else:
        if a_ < x1:
            cnt1 += x1-a_
            
            a_ = 1

    x1 *= -1

if cnt >= 0 and cnt1 >=0:
    print(min(cnt, cnt1))
elif cnt < 0:
    print(cnt1)
else:
    print(cnt)

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

#define INF 100000000
#define MOD9(a) (a%1000000009)
#define MOD7(a) (a%1000000007)
#define ABS(a) (a<0?-(a):a)
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define REP(i,a) for(int i=0;i<a;i++) 

using namespace std;
int main(){

  int A, B;
  cin >> A >> B;
  int a = (A+13)%15;
  int b = (B+13)%15;
  if(a == b ){
    cout << "Draw" << endl;
  }else if(a < b){
    cout << "Bob" << endl;
  }else{
    cout << "Alice" << endl;
  }
}



Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  double n,m;
  int a[2]={0},b[2]={0},c[2]={0},d[2]={0};
  while(scanf("%lf%lf",&n,&m)==2){
    if(n>=1.1)a[0]++;
    else if(n>=0.6)b[0]++;
    else if(n>=0.2)c[0]++;
    else d[0]++;
    if(m>=1.1)a[1]++;
    else if(m>=0.6)b[1]++;
    else if(m>=0.2)c[1]++;
    else d[1]++;    
  }
  printf("%d %d\n",a[0],a[1]);
  printf("%d %d\n",b[0],b[1]);
  printf("%d %d\n",c[0],c[1]);
  printf("%d %d\n",d[0],d[1]);
  return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int x, y;

    scanf("%d %d", &x, &y);

    int score = 0;
  	if(x >= y) {
      score += x;
      x--;
    } else {
      score += y;
      y--;
    }
  	if(x >= y) {
      score += x;
      x--;
    } else {
      score += y;
      y--;
    }
  
    printf("%d\n", score);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

class Edge
{
public:
	int src, dst, flg;
	Edge(int src, int dst, int flg)
		:src(src),dst(dst),flg(flg)
	{}
};

typedef vector<vector<Edge> > Graph;

void paint(int p, int color, Graph& graph, vector<bool>& painted, vector<int>& result, vector<int>& cnt)
{
	cnt[p]++;
	painted[p] = true;
	if(color) result.push_back(p);

	for(int i=0; i<graph[p].size(); i++) {
		Edge& e = graph[p][i];
		if(painted[e.dst]) continue;

		int nc;
		if(color) nc = e.flg; else nc = (e.flg+1)%2;

		paint(e.dst, nc, graph, painted, result, cnt);
	}
}

int dp[305][605];
int bk[305][605];

int main()
{
	int N,V,A,B;
	while(cin >> N >> A >> B, (N||A||B)) {
		
		V=A+B;
		Graph graph(V);
		for(int i=0; i<N; i++) {
			int s,t,g;
			string f;

			cin >> s >> t >> f;
			s--; t--;
			if(f=="yes") g = 1; else g = 0;
			graph[s].push_back(Edge(s,t,g));
			graph[t].push_back(Edge(t,s,g));
		}

		int C=0;
		vector<int> cnt(V, 0);
		vector<vector<vector<int> > > divineList(V, vector<vector<int> > (2));
		
		for(int i=0; i<V; i++) {
			if(cnt[i] >= 2) continue;

			for(int j=0; j<2; j++) {
				vector<bool> painted(V, false);
				vector<int> result;

				paint(i, j, graph, painted, result, cnt);
				divineList[C][j] = result;
			}

			C++;
		}

		divineList.resize(C);

		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;

		for(int i=1; i<=divineList.size(); i++) {
			/*for(int j=0; j<=A; j++) {
				dp[j][i] = dp[j][i-1];
				bk[j][i] = 0;
			}*/

			for(int j=0; j<=A; j++) {

				for(int k=0; k<2; k++) {
					int p = j + divineList[i-1][k].size();
					if(p > A) continue;
					if(dp[j][i-1]==0) continue;

					dp[p][i] += dp[j][i-1];
					bk[p][i] = k+1;
				}
			}
		}

		if(dp[A][divineList.size()] != 1) {
			cout << "no" << endl;
		}
		else {
			int M = A;
			vector<int> res;
			for(int i=divineList.size(); i>0; i--) {
				if(bk[M][i]==0) continue;

				for(int j=0; j<divineList[i-1][bk[M][i]-1].size(); j++)
					res.push_back(divineList[i-1][bk[M][i]-1][j]);

				M-=divineList[i-1][bk[M][i]-1].size();

			}

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

			for(int i=0; i<res.size(); i++)
				cout << res[i]+1 << endl;

			cout << "end" << endl;
		}
	}		

}

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

int main() {
  int m, f, r;
  while (cin >> m >> f >> r, m + f + r != -3) {
    if (m == -1 || f == -1) cout << "F";
    else if (m + f >= 80) cout << "A";
    else if (m + f >= 65) cout << "B";
    else if (m + f >= 50) cout << "C";
    else if (m + f >= 30) {
      if (r >= 50) cout << "C";
      else cout << "D";
    }
    else  cout << "F";
    cout << "\n";
  }
  return 0;
}


Measured memory_bytes: 3008
"""
AtCoder :: Beginner Contest 173 :: Payment
https://atcoder.jp/contests/abc173/tasks/abc173_a
"""
import sys


def main():
    """Main program."""
    N = int(sys.stdin.readline())
    remainder = N % 1000
    if remainder:
        print(1000 - remainder)
    else:
        print(0)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9164
// Create by JJL
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <queue>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N=5010,Mod=1e9+7;
LL v[N][N],f[N][N][4];
int main(){
    IOS;
    /* START CODE */
    int n,m,k;
    memset(v,0,sizeof v);
    cin>>n>>m>>k;
    for(int i=1;i<=k;++i){
        int x,y,c;
        cin>>x>>y>>c;
        v[x][y]=c;
    }
    //memset(f,-0x3f,sizeof f);
    for(int i=1;i<=n;++i){
        for(int k=0;k<=3;++k){
            for(int j=1;j<=m;++j){
                LL &t=f[i][j][k];
                //if(k==0){
                    t=max(t,f[i-1][j][0]);
                    t=max(t,f[i-1][j][1]);
                    t=max(t,f[i-1][j][2]);
                    t=max(t,f[i-1][j][3]);
                //}
                if(k){
                    t=max(t,f[i-1][j][0]+v[i][j]);
                    t=max(t,f[i-1][j][1]+v[i][j]);
                    t=max(t,f[i-1][j][2]+v[i][j]);
                    t=max(t,f[i-1][j][3]+v[i][j]);
                }
                t=max(t,f[i][j-1][k]);
                if(k) t=max(t,f[i][j-1][k-1]+v[i][j]);
            }
        }
    }
    cout<<max(max(f[n][m][3],f[n][m][2]),max(f[n][m][1],f[n][m][0]))<<endl;
    return 0;
}

Measured memory_bytes: 492364
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using vc = vector<char>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;} 
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;

ll N, A, B;
vll h;

bool ok(ll n)
{
        vll cp(all(h));
        rep(i, 0, N) {
                cp[i] -= B * n;
        }
        ll diff = A - B;
        ll cnt = 0;
        rep(i, 0, N) {
                if (cp[i] > 0) {
                        cnt += cp[i] / diff;
                        if (cp[i] % diff != 0) ++cnt;
                }
        }
        if (cnt <= n) return true;
        else return false;
}

int main()
{
        cin >> N >> A >> B;
        h.resize(N);
        rep(i, 0, N) cin >> h[i];

        ll left = -1;
        ll right = 10000000000;
        while (right - left > 1) {
                ll mid = (left + right) / 2;
                if (ok(mid)) right = mid;
                else left = mid;
        }

        cout << right << endl;
}

Measured memory_bytes: 4828
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 3
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	ans := 1
	horobiyo := 1
	for i := 0; i < n; i++ {
		ans *= 3
		horobiyo *= odds(getNextInt(scanner))
	}
	fmt.Fprintln(writer, ans-horobiyo)
}

func odds(x int) int {
	o := 0
	for i := 0; i < 3; i++ {
		if (x+i-1)%2 != 0 {
			o++
		}
	}

	return o
}


Measured memory_bytes: 640
#include <iostream>
#include <complex>
#include <cmath>
using namespace std;
typedef complex<double> xy_t;
double cross_product(xy_t a, xy_t b){ return (conj(a)*b).imag();}
const double eps = 1e-11;
double x[4],y[4];
int N;
int main() {
	cin >> N;
	for(int t=0;t<N; ++t){
		for(int i=0; i<4; ++i){
			cin >> x[i] >>y[i];
		}
		xy_t a[2] ={
			xy_t(x[0],y[0])-xy_t(x[1],y[1]),
			xy_t(x[2],y[2])-xy_t(x[3],y[3])
		};
		bool p = abs(cross_product(a[0], a[1])) < eps;
		cout << (p ? "YES" : "NO" ) << endl;
	}
	return 0;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,P> PP;

//-----------------------------------------------------------------------------

int n,d,x,a,ans;

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

	cin>>n>>d>>x;
	
	REP(i,n) {
		cin>>a;
		for(int j=1;j<=d;j+=a) ans++;
	}
	cout<<ans+x<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

#define loop(x) for(;x>0;x--)

using namespace std;

int main(){
    vector<string> v;
    string buf;
    int n, l;
    cin >> n >> l;
    loop(n){
        cin >> buf;
        v.push_back(buf);
    }
    sort(v.begin(), v.end());
    for_each(v.begin(), v.end(), [](string s){
        cout << s;
    });
    cout << endl;
    return 0;
}

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

int main(){
    using namespace std;
    constexpr unsigned long MOD = 1000000007;
    auto f = [&MOD](auto& a, auto k){(a.second += (a.first += a.second * k) %= MOD) %= MOD; return a.first;};
    unsigned long N;
    cin >> N;
    vector<pair<pair<unsigned long, unsigned long>, unsigned long>> tapi(1048576, {{1, 0}, 0});
    unsigned long ans{0}, t{500000004}, a{0}, z{0};
    for(unsigned long i = 1, A; i <= N; ++i){
        cin >> A;
        if(a ^= A){
            ans += f(tapi[a].first, z - tapi[a].second);
            tapi[a].second = z;
        }else ++z, (t *= 2) %= MOD;
    }
    cout << (a ? tapi[a].first.first : (ans + t) % MOD) << endl;
    return 0;
}

Measured memory_bytes: 24832
#include<bits/stdc++.h>
using namespace std;
int n,b,a[100004];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b=a[i]-b;
	}
	for(int i=1;i<=n;i++){
		printf("%d ",b);
		b=2*a[i]-b;
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N ;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin >> a.at(i);}
  
  int light = 1;
  int count = 0;
  
  for(int i=0; i < N+1; i++){
    if(light == 2){cout << count << endl; break;}
    if(count >= N){cout <<-1<< endl; break;}
  count++;light = a.at(light-1);}

}


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

int main() {
  int x,h;
  double S;
  while(cin >> x >> h) {
    if((x==0)&&(h==0)) break;
    S = (double) x * x + (double) x * sqrt(h*h+x*x/4.0) / 2.0 * 4.0;
    printf("%.6f\n",S);
  }
}

Measured memory_bytes: 0
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(n): # kじゃなくn
    dp[i] = abs(h[0] - h[i])

for i in range(k, n):
    dpi = 10**9
    for j in range(1, k+1):
        dpi = min(dp[i-j]+abs(h[i]-h[i-j]), dpi)
    dp[i] = dpi

print(dp[n-1])

Measured memory_bytes: 84716
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

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

	cout << A * B - A - B + 1 << endl;

    return 0;
}


Measured memory_bytes: 764
//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  ll result = 0;
  if( a + b <= k ) {
    result += a;
    k -= a + b;
  }else{
    result += k;
    cout << result << endl;
    return 0;
  }
  result -= k;
  cout << result << endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    char c[26];
    for (int i = 0; i < 26; i++) {
        c[i] = '+';
    }
    for (int i = 0; i < s.size(); i++) {
        if (c[int(t[i] - 'a')] == '+') {
            c[int(t[i] - 'a')] = s[i];
        }
        else if (c[int(t[i] - 'a')] != s[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    for (int i = 0; i < 26; i++) {
        c[i] = '+';
    }
    for (int i = 0; i < s.size(); i++) {
        if (c[int(s[i] - 'a')] == '+') {
            c[int(s[i] - 'a')] = t[i];
        }
        else if (c[int(s[i] - 'a')] != t[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3908
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int>Vl;
typedef pair<int,int>pii;
typedef vector<pii>Vll;
typedef vector<pair<int,pair<int,int> > >Vlll;
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) cin>>n 
#define pl(n) cout<<n<<" "
const int Nx=1e5+2;
const int mod=998244353;
const int inf=(int)(1e9+10LL);
const double pI=6.28318530717958623200;
void solve()
{
	int n;
	sl(n);
    map<int,int>freq;
    for(int i=1;i<n;i++){
    	int num;
    	sl(num);
    	freq[num]++;
    }
    for(int i=1;i<=n;i++){
    	cout<<freq[i]<<endl;
    }
}

signed main(){
  int test=1;
 // sl(test);
 while(test--){
 	solve();
 }
 
}

Measured memory_bytes: 16048
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string S;
    cin >> S;
    bool esey = true;
    for(int i = 0; i<S.size() && esey; i++){
        if((i%2==0 && S.at(i)=='L') ||
           (i%2==1 && S.at(i)=='R'))
            esey = false;
    }
    
    if(esey)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=LIST()

mn=INF
cnt=0
zero=False
for i in range(N):
    mn=min(mn, abs(A[i]))
    if A[i]<0:
        cnt+=1
    if A[i]==0:
        zero=True
    A[i]=abs(A[i])

if zero:
    print(sum(A))
elif cnt%2==0:
    print(sum(A))
else:
    print(sum(A)-mn*2)


Measured memory_bytes: 14512
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> status;

int main() {
	int W,N,cnt = 1;
	while(true){
		cin >> W;
		if(W==0) return 0;
		cin >> N;
		int val[1001],weight[1001];
		memset(val,0,sizeof(val));
		memset(weight,0,sizeof(weight));
		for(int i = 0;i<N;i++){
			cin >> val[i];
			cin.get();
			cin >> weight[i];
		}
		int dp[1003];
		memset(dp,0,sizeof(dp));
		for(int i = 0;i<N;i++){
			for(int j = W;j >= weight[i];j--){
				if(j-weight[i]<0)continue;
				dp[j] = max(dp[j],dp[j-weight[i]]+val[i]);
			}
		}
		int mini;
		for(int i = W;dp[i] == dp[W];i--) mini = i;
		cout << "Case " << cnt << ":" << endl;
		cout << dp[W] << endl;
		cout << mini << endl;
		cnt++;
	}
	return 0;
}

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

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
#define REP(i, n)  for(int i = 0; i < n; ++i)
#define FOR(i, t, n)  for(ll i = t; i <= (ll)n; ++i)
struct edge {
    int from, to;
    ll cost;
};


class Eratosthenes {
public:
    vector<bool> prime;

    Eratosthenes(int size) {
        prime.resize(size + 1, 1);
        prime[0] = 0;
        prime[1] = 0;
        FOR(i, 2, size) {
            if (prime[i]) {
                for (int j = 2 * i; j <= size; j += i) {
                    prime[j] = 0;
                }
            }
        }
    }

};


class Combination {
    vector<ll> fac; //n!(mod M)
    vector<ll> ifac; //k!^{M-2} (mod M)
public:
    Combination(ll size) {
        fac.resize(size);
        ifac.resize(size);
        fac[0] = 1;
        ifac[0] = 1;
        for (ll i = 0; i < size; i++) {
            fac[i + 1] = fac[i] * (i + 1) % MOD;
            ifac[i + 1] = ifac[i] * mpow(i + 1, MOD - 2) % MOD;
        }
    }

    ll mpow(ll x, ll n) {
        ll ans = 1;
        while (n != 0) {
            if (n & 1) ans = ans * x % MOD;
            x = x * x % MOD;
            n = n >> 1;
        }
        return ans;
    }

    ll comb(ll a, ll b) {
        if (a == 0 && b == 0)return 1;
        if (a < b || a < 0)return 0;
        ll tmp = ifac[a - b] * ifac[b] % MOD;
        return tmp * fac[a] % MOD;
    }
};


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

ll N, M;

vector<int> A[101010], B[101010];
bool v[101010], t[101010];

void dfs(int x, bool b) {
    if (b) {
        for (int to:B[x]) {
            if (t[to])continue;
            t[to] = 1;
            dfs(to, !b);
        }
    } else {
        for (int to:A[x]) {
            if (v[to])continue;
            v[to] = 1;
            dfs(to, !b);
        }
    }
}


int main() {
    cin >> N >> M;
    REP(i, N) {
        int k;
        cin >> k;
        REP(j, k) {
            int c;
            cin >> c;
            A[c].push_back(i + 1);
            B[i + 1].push_back(c);
        }
    }
    v[1] = 1;
    dfs(1, 1);
    int cnt = 0;
    REP(i, N)if (v[i + 1])cnt++;
    if (cnt == N) {
        cout << "YES" << endl;
    } else cout << "NO" << endl;
    return 0;
}


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

typedef long long lint;
typedef long double louble;

#define so(a) ((int)((a).size()))

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

const char lf = '\n';

namespace ae86
{
	const int bufl = 1 << 15;

	char buf[bufl],*s=buf,*t=buf;

	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}

	inline lint ty()
	{
		lint a=0;int b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}

	template<typename T> inline int ts(T *s)
	{
		int a=0,c=fetch();
		while(c<=32 && c!=EOF)c=fetch();
		while(c>32 && c!=EOF)s[a++]=c,c=fetch();
		s[a]=0;
		return a;
	}
}
using ae86::ty;
using ae86::ts;

#define pick(a,b) (((a)>>(b))&1)

struct linegay
{
	static const int lglg = 63;

	lint val[lglg+1];

	int push(lint x)
	{
		for(int i=lglg;i>=0;i--)
		{
			if(!pick(x,i))continue;
			if(!val[i]){val[i]=x;return 1;}
			x^=val[i];
		}
		return 0;
	}

	int able(lint x)
	{
		for(int i=lglg;i>=0;i--)
		{
			if(!pick(x,i))continue;
			if(!val[i])return 0;
			x^=val[i];
		}
		return 1;
	}

	void cls()
	{
		memset(val,0,sizeof(val));
	}
	
	linegay()
	{
		memset(val,0,sizeof(val));
	}
}t;

const int _ = 207;

int n;
lint val[_]={0};int who[_]={0};

void finder()
{
	n=ty();
	for(int i=1;i<=n;i++)val[i]=ty();
	ts(who+1);

	t.cls();
	int able=0;
	for(int i=n;i>=1;i--)
	{
		if(who[i]=='1'){if(!t.able(val[i])){able=1;break;}}
		else t.push(val[i]);
	}

	cout<<able<<lf;
}

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

	int t=ty();
	while(t--)finder();
	
	return 0;
}


Measured memory_bytes: 3624
#include <iostream>

using namespace std;

bool search(int A[],int N,int key) {
  int l=-1,r=N+1;
  while(l!=r-1) {
    int mid=(l+r)/2;
    if(A[mid]==key) return true;
    else if(A[mid]<key) l=mid;
    else r=mid;
  }
  return false;
}

int S[100000]={};

int main() {
  int n; cin >> n;
  for(int i=0;i<n;++i) cin >> S[i];
  int q; cin >> q;
  int ans=0;
  while(q--) {
    int t; cin >> t;
    if(search(S,n,t)) ans++;
  }
  cout << ans << endl;
  
  return 0;
}



Measured memory_bytes: 3348
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

/*
 * dijkstra 法 O(Elog(V))
 * グラフ g において, 始点 start から各頂点への最短経路を返す
*/
struct Edge {
public:
  int to, cost;

  Edge() {}
  Edge(int to, int cost) : to(to), cost(cost) {}
};

std::vector<int> dijkstra(std::vector<std::vector<Edge> >& graph, int start) {
  std::vector<int> d(graph.size(), int(1e9));
  // (x, y) ... x : the minimum distance from start to y, y : now vertex 
  std::priority_queue<std::pair<int, int> > que;

  que.push({0, start});
  d[start] = 0;

  while(!que.empty()) {
    auto p = que.top();
    que.pop();

    for (auto e : graph[p.second]) {
      if (d[e.to] <= p.first + e.cost) continue;

      d[e.to] = p.first + e.cost;
      que.push({d[e.to], e.to});
    }
  }

  return d;
}


int main() {
  int n, u, k, v, c;
  std::vector<std::vector<Edge> > g;

  cin >> n;
  g.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> u >> k;
    for (int j = 0; j < k; ++j) {
      cin >> v >> c;
      g[u].push_back({v, c});
    }
  }

  auto d = dijkstra(g, 0);

  for (int i = 0; i < n; ++i) {
    cout << i << " " << d[i] << endl;
  }

  return 0;
}



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

long long int n ;


int main()
{
    cin>>n;
   long long  int n1=n;
    long long int s=0;
    while(1){
        s+=n%10;
    if(n/10==0)break;
    n=n/10;
    }
    if(n1%s==0)cout<<"Yes";
    else cout<<"No";
return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int n,x,y,z,temp;

    scanf("%d",&n);

    while(n--){
        scanf("%d%d%d",&x,&y,&z);

        if(x>y){
            temp = x;
            x = y;
            y = temp;
        }
        if(x>z){
            temp = x;
            x = z;
            z = temp;
        }
        if(y>z){
            temp = y;
            y = z;
            z = temp;
        }

        if((z*z) == (y*y) + (x*x)){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }

    return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
//#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using vi = vector<int>;
using Graph = vector<vi>;

set<int> pool;
set<int> sums;

vi primevec(int m, int n) {
  vi ret;
  vector<bool> num(n + 1);
  for (int i = 2; i * i < n; i++) {
    if (!num.at(i)) {
      for (int j = 2; i * j <= n; j++) {
        num.at(i * j) = 1;
      }
    }
  }
  for (int i = m; i <= n; i++) {
    if (!num.at(i) && i % 5 == 1) ret.push_back(i);
  }
  return ret;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(15); //"for float-base
  // problem"
  int N;
  cin >> N;
  vi prime = primevec(2, 55555);

  for (int i = 0; i < N; i++) cout << prime.at(i) << " ";
  cout << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<string>

using namespace std;

int main() {
	string str;
	cin >> str;
	if (str.size() >= 4 && str[0] == 'Y' && str[1] == 'A' && str[2] == 'K' && str[3] == 'I')cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#define INF 1e8
using namespace std;
int main(void){
int  n;
string s;
string a="ABC";
cin>>n>>s;

int pos=0, count=0;

while((pos= s.find(a, pos))!=std::string::npos){
    count++;
    pos= pos+ a.length();
}
cout<<count;



}



Measured memory_bytes: 3096
n,k=map(int,input().split())
x=list(map(int,input().split()))
ans=10**18
for l in range(n-k+1):
  y=min(abs(x[l])+abs(x[l+k-1]-x[l]),abs(x[l+k-1])+abs(x[l+k-1]-x[l]))
  ans=min(y,ans)
print(ans)

Measured memory_bytes: 14384
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#define rep(i, n) for(int i=0; i<n; i++)
#define rep_one(i, n) for(int i=1; i<n; i++)
using namespace std;
typedef long long ll;


int main(){
    string s; cin >> s;
    int div = 0;
    rep(i, s.size()){
        div += s[i]-'0';
        div %= 9;
    }
    if(div == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3752
s = input() + 'C'
t = s[::-1] + 'F'

# CF
# 最も左にある C 
# 最も右にある F

idx_C = s.index('C')
idx_F = len(s) - 1 - t.index('F')

if idx_C < idx_F:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 61700
/*#include <iostream>
using namespace std;
int main(){
	
	int A,B,C,D,E;
	cin >> A >> B >> C >> D  >> E;

	int answer;
	if (A < 0){
		answer = -A * C + D + B * E;
	}

	if (A > 0){
		answer = (B -A) * E;
	}

	cout << answer << endl;


		

}*/

#include <iostream>
using namespace std;
int main(){
	
	int A,B,C,D,E;
	cin >> A >> B >> C >> D >> E;

	int answer= 0;
	if (40 <= A){
		answer = answer+A;
	}

	if (40 > A ){
		answer = answer + 40;
	}

	if (40 <= B){
		answer = answer+B;
	}

	if (40 > B){
		answer = answer + 40;
	}

	if (40 <= C){
		answer = answer+C;
	}

	if (40 > C){
		answer = answer + 40;
	}
	
	if (40 <= D){
		answer = answer+D;
	}

	if (40 > D){
		answer = answer + 40;
	}

	if (40 <= E){
		answer = answer+E;
	}

	if (40 > E){
		answer = answer + 40;
	}


	cout << answer/5 << endl;


}


Measured memory_bytes: 3076
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define LL long long
#define MOD 100000
#define inf 1999999999
#define ALL(x) (x).begin(), (x).end()
#define LBi(x, n) lower_bound(ALL(x), n) - (x).begin()
#define ZIP(x) (x).erase(unique(ALL(x)), (x).end())
#define Pi pair<int, int>
#define Vi vector<int>

#define rep(n) for(int i = 0; i < n; i++)

string s, t;
char ch[10];
int n, a, b, c, d, x, m[5];

int main() {
	cin >> a >> b;
	cout << b * 2 - a << endl;
	return 0;
}


Measured memory_bytes: 256
//Resting_Prince
#include<bits/stdc++.h>
#define mod 1000000007
#define inf 1e18
#define PI 3.141592653589
#define fi first
#define se second 
#define sv(v) sort(all(v));reverse(all(v))
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mk make_pair
#define en '\n'
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double ld;

int main()
{
    map<ll,ll> m;
    ll n,i,j,k;
    cin>>n;
    rep(i,0,n-2)cin>>k,m[k]++;
    rep(i,1,n)cout<<m[i]<<en;
    return 0;
}


Measured memory_bytes: 16076
using System;
class Program
 {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] strListA = Console.ReadLine().Split(' ');
            string[] strListB = Console.ReadLine().Split(' ');
            long shortage = 0;
            for(int i = 0; i < N; i++){
                int a = int.Parse(strListA[i]);
                int b = int.Parse(strListB[i]);
                if(a > b){
                    shortage += a - b;
                }
                if(b - a >= 2){
                    shortage -= (b - a) / 2;
                }
            }
            // Console.Write("改行なし a = {0} b = {1} c = {2}", a, b, c)//改行なし出力
            // Console.WriteLine("改行あり a = {0} b = {1} c = {2}", a, b, c);//改行付き出力
            if(shortage <= 0){
                Console.WriteLine("Yes");
            } else {
                Console.WriteLine("No");
            }
        }
 }

Measured memory_bytes: 14560