akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
int main() {
	int n,a[101],flag,cnt=0;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	flag = 1;
	while (flag) {
		flag = 0;
		for (int i = n - 1; i > 0; --i) {
			if (a[i] < a[i - 1]) {
				swap(a[i], a[i - 1]);
				flag = 1;
				cnt++;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (i == n - 1)cout << a[i];
		else  cout << a[i] << " ";
	}
	cout <<endl<< cnt << endl;
	return 0;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
    
int main(){
    int N;
    cin>>N;
    vector<string> S(N);
    cin>>S;
    vector<vector<LL>> h(N);
    REP(i,N){
        h[i].resize(S[i].size());
        for(auto&it:h[i])it=0;
    }
    FOR(l,1,10){
        vector<int> exist(400000,0);
        REP(i,N)FOR(j,l-1,S[i].size()){
            h[i][j-l+1]*=26;
            h[i][j-l+1]+=S[i][j]-'a';
            
            if(h[i][j-l+1]>=400000)continue;
            exist[h[i][j-l+1]]=1;
            
        }
        LL len=1;
        REP(i,l)len*=26;
        REP(i,len)if(exist[i]==0){
            string s;
            REP(j,l){
                s=string(1,'a'+i%26)+s;
                i/=26;
            }
            cout<<s<<endl;
            return 0;
        }
    }
    return 0;
}

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

int main() {
    int N; cin >> N;
    map<int, int> m;
    for (size_t i = 0; i < N; i++)
    {
        int a; cin >> a;
        m[a-1]++;
        m[a]++;
        m[a+1]++;
    }

    int ans = 0;
    for (auto iter = m.begin(); iter != m.end(); iter++)
    {
        ans = max(ans, (*iter).second);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1000000007;

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int H,W;
  cin>>H>>W;
  vector<string>a(H);
  for(int i=0;i<H;i++){
    cin>>a[i];
  }
  map<char,int>k;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      k[a[i][j]]++;
    }
  }
  if(H%2==0&&W%2==0){
    for(auto c:k){
      if(c.second%4!=0){cout<<"No"<<endl;return 0;}
    }
    cout<<"Yes"<<endl;
  }
  else if(H%2!=0&&W%2!=0){
    int cnt2=0,cnt1=0;
    for(auto c:k){
      if(c.second%4!=0&&c.second%2==0){cnt2++;}
      if(c.second%4!=0&&c.second%2!=0){cnt1++;}
    }
    if(cnt2<=(H+W-1-1)/2&&cnt1==1){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
  }
  else{
    int even;
    if(H%2==0){even=H;}
    else{even=W;}
    int cnt2=0,cnt1=0;
    for(auto c:k){
      if(c.second%2!=0){cout<<"No"<<endl;return 0;}
      if(c.second%4!=0&&c.second%2==0){cnt2++;}
    }
    if(cnt2<=even/2){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
  }
  return 0;
}

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

int main() {
    ll N, H, W;
    cin >> N >> H >> W;
    int sum = 0;
    rep(i, N) {
        ll A, B;
        cin >> A >> B;
        if (A >= H and B >= W) sum++;
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define EQ(a,b) (abs((a)-(b))<EPS)
int main()
{
	double xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2;
	while(cin >>xa1>>ya1>>xa2>>ya2>>xb1>>yb1>>xb2>>yb2)
	{
		if(xb2<xa1||xb1>xa2)
		{
			cout << "NO" << endl;
		}
		else if(yb1>ya2||yb2<ya1)
		{
			cout << "NO" << endl;
		}
		else
		{
			cout << "YES" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1220
#include <iostream>
using namespace std;
int main(void){
    int A,B,C,D;
    cin >> A >> B >> C >> D;
    
    while(A>0||C>0){
        C-=B;
        if(C<=0){
            cout << "Yes" << endl;
            return 0;
        }
        A-=D;
        if(A<=0){
            cout <<"No" << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 3636
def main():
  h, w, k = map(int, input().split())
  aaa = [list(map(int, input().replace('.', '0').replace('#', '1'))) for _ in range(h)]
  
  from itertools import combinations
  
  res = 0
  for i in range(1, 1+h):
    for j in range(1, 1+w):
      rrr = list(combinations(range(h), i))
      ccc = list(combinations(range(w), j))
      for rr in rrr:
        for cc in ccc:
          t = 0
          for r in rr:
            for c in cc:
              t += aaa[r][c]
          if t == k:
            res += 1
  print(res)


if __name__ == "__main__":
  main()


Measured memory_bytes: 68060
#include <cstdio>


using namespace std;
int lis[100000];
int tim[100000];
int main() {
    int n,r,l;
    scanf("%d %d %d",&n,&r,&l);

    int top = 0;
    int id  = 1;
    int nowtime = 0;
    int timemax = 0;
    int timemaxid = 0;
    for(int i = 0; i < r; i++) {
       
        int d,t,x;
        scanf("%d %d %d",&d,&t,&x);
        tim[id] += t - nowtime;
        if(tim[id] > timemax) {
            timemax = tim[id];
            timemaxid = id;
        }
        nowtime = t;
        lis[d] += x;
        if(id == d) {
            top += x;
        }
        if(x < 0 && d == id) {
            for(int j = 1; j < n+1; j++) {
                if(top < lis[j] || (top == lis[j] && j < id)) {
                    top = lis[j];
                    id = j;
                }
            }
            
        }
        if(x > 0 && d != id) {
            if(top < lis[d] || (top == lis[d] && d < id)) {
                top = lis[d];
                id = d;
            }
        }

    }
    tim[id] += l - nowtime;
    if(tim[id] > timemax) {
        timemax = tim[id];
        timemaxid = id;
    }
    printf("%d\n",timemaxid);
}

Measured memory_bytes: 1804
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define MP make_pair
#define pb push_back
const int INF = 1e9;
const int MOD = INF+7;
using P = pair<int,int>;

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

    int ans = 0;
    int m = 0;
    rep(i,N){
        int A;
        cin >> A;
        if(m && A) ans++,A--;
        ans += A/2;
        m = A%2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
(* O(h w) *)
let h, w = Scanf.scanf " %d %d" @@ fun a b -> a, b
let ss = Array.init h @@ fun _ -> Scanf.scanf " %s" @@ fun s -> s
let ys = Array.make_matrix h w 0
let xs = Array.make_matrix h w 0
let ans = ref 0
let _ =
  for y = 0 to h - 1 do
    let c = ref 0 in
    for x = 0 to w - 1 do
      if ss.(y).[x] = '#' then
        (for i = 1 to !c do
          xs.(y).(x - i) <- !c
        done;
        c := 0; xs.(y).(x) <- 0)
      else
        (incr c; xs.(y).(x) <- !c)
    done;
    for i = 1 to !c do
      xs.(y).(w - i) <- !c
    done
  done;
  for x = 0 to w - 1 do
    let c = ref 0 in
    for y = 0 to h - 1 do
      if ss.(y).[x] = '#' then
        (for i = 1 to !c do
          ys.(y - i).(x) <- !c
        done;
        c := 0; ys.(y).(x) <- 0)
      else
        (incr c; ys.(y).(x) <- !c)
    done;
    for i = 1 to !c do
      ys.(h - i).(x) <- !c
    done
  done;
  for y = 0 to h - 1 do
    for x = 0 to w - 1 do
      if ss.(y).[x] <> '#' then
        ans := max !ans @@ ys.(y).(x) + xs.(y).(x) - 1
    done
  done;
  Printf.printf "%d\n" !ans

Measured memory_bytes: 71928
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s, t;
    string result = "No";
    cin >> s >> t;
    
    for(int i = 0; i < s.length()-1; i++) {
        for(int j = i; j < s.length(); j++) {
            if(s[i] > s[j]){
                char c = s[i];
                s[i] = s[j];
                s[j] = c;
            }
        }
    }
    
    for(int i = 0; i < t.length()-1; i++) {
        for(int j = i; j < t.length(); j++) {
            if(t[i] < t[j]){
                char c = t[i];
                t[i] = t[j];
                t[j] = c;
            }
        }
    }

    for(int i = 0; i < max(s.length(), t.length()); i++) {
        if(i > s.length() || s[i] < t[i]) {
            result = "Yes";
            break;
        }
        else if(s[i] > t[i]) {
            break;
        }
    }
    
    cout << result << endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w=[0]*(n+1)
    v=[0]*(n+1)
    for i in range(1,n+1):
        w[i],v[i]=map(int,input().split())
    dp=[0]*(W+1)
    for i in range(1,n+1): # i番目を見る
        newdp=dp[:] # 使わない場合を先に計算したことにしておく
        for j in range(W+1):
            if(j-w[i]>=0): # i番目を使う場合(貰うDP)
                newdp[j]=max(dp[j-w[i]]+v[i],dp[j])
        dp=newdp
    print(dp[-1])
resolve()

Measured memory_bytes: 117232
n,k=gets.split.map &:to_i
s=gets.split.map &:to_i
nom=s.bsearch_index{|x|x>=0}||n
ans1=[0]
ans2=[0]
(0...nom).to_a.reverse.each{|i|
  ans1 << s[i].abs
}
(nom...n).to_a.each{|j|
  ans2 << s[j]
}
ans=10**17
kai=0
([k-nom,0].max..[k,ans2.size-1].min).to_a.each{|i|
kai=ans1[k-i]+2*ans2[i]
ans=[ans,kai].min
kai=ans2[i]+2*ans1[k-i]
ans=[ans,kai].min
}
puts ans


Measured memory_bytes: 23196
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    int H, W;
    int[][] b;
    int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};

    int INF = 1 << 28;

    void run() {
        Scanner sc = new Scanner(System.in);
        H = sc.nextInt();
        W = sc.nextInt();
        b = new int[H + 2][W + 2];
        PriorityQueue<P> q = new PriorityQueue<>();

        for (int i = 1; i <= H; i++) {
            String s = sc.next();
            for (int j = 1; j <= W; j++) {
                if (s.charAt(j - 1) == '#') {
                    b[i][j] = 0;
                    q.add(new P(j, i, 0));
                } else {
                    b[i][j] = INF;
                }
            }
        }
        int ans = 0;
        while (!q.isEmpty()) {
            P cur = q.remove();
            if (b[cur.y][cur.x] != cur.c) continue;
            ans = Math.max(ans, cur.c);
            for (int i = 0; i < 4; i++) if (b[cur.y + dy[i]][cur.x + dx[i]] > cur.c + 1) {
                q.add(new P(cur.x + dx[i], cur.y + dy[i], cur.c + 1));
                b[cur.y + dy[i]][cur.x + dx[i]] = cur.c + 1;
            }
        }
//        debug(b);
        System.out.println(ans);
    }

    class P implements Comparable<P> {
        int x, y, c;
        P(int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }

        @Override
        public int compareTo(P o) {
            return c - o.c;
        }
    }

    void debug(Object...os) {
        System.err.println(Arrays.deepToString(os));
    }

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


Measured memory_bytes: 72796
import * as fs from 'fs'
const reader = (s: string) => s.split(' ').map(t => parseInt(t, 10))

function Main(input: string) {
  const N = reader(input)
  const fil = N.sort((a, b) => a - b)

  if (fil[0] + fil[1] === fil[2]) {
    console.log('Yes')
  } else {
    console.log('No')
  }
}

Main(fs.readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 7372
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
using namespace std;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int dfs(vector<vector<int> >& vi,int i,int j);
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m,n;
	while(cin>>m>>n&&m!=0&&n!=0){
		vector<vector<int> > ice(m,vector<int>(n));
		int ans=0;
		for(int i=0; i<n; ++i){
			for(int j=0; j<m; ++j){
				cin >> ice[j][i];
			}
		}
		for(int i=0; i<n; ++i){
			for(int j=0; j<m; ++j){
				if(ice[j][i]==1) {
					ans=max(ans,dfs(ice,j,i));
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

int dfs(vector<vector<int> >& vi,int i,int j){
	int res=0;
	vi[i][j]=0;
	for(int k=0;k<4;++k){
		int nx=i+dx[k];
		int ny=j+dy[k];
		if(0<=nx&&nx<vi.size()&&0<=ny&&ny<vi[i].size()&&vi[nx][ny]==1){
			res=max(res,dfs(vi,nx,ny));
		}
	}
	vi[i][j]=1;
	return res+1;
}

Measured memory_bytes: 1256
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007
using namespace std;

int main(void) {
	long long int n, a, b;
	long long int total = 0;
	cin >> n >> a >> b;
	if (a > b) {
		total = 0;
	}
	else {
		if (n == 1 && a == b) {
			total = 1;
		}
		else if (n == 1 && a != b) {
			total = 0;
		}
		else {
			total = (b - a) * (n - 2) + 1;
		}
	}
	
	cout << total << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;
ll cnt_p[52], cnt_all[52];

ll recursion(ll n, ll x) {
  if (n == 0) {
    if (x <= 0)
      return 0;
    else
      return 1;
  }
  if (x - 1 <= cnt_all[n - 1]) {
    return recursion(n - 1, x - 1);
  } else {
    return cnt_p[n - 1] + 1 + recursion(n - 1, x - 2 - cnt_all[n - 1]);
  }
}
int main() {
  ll N, X;
  cin >> N >> X;
  cnt_p[0] = 1;
  cnt_all[0] = 1;
  for (int i = 1; i <= N; i++) {
    cnt_p[i] = 2 * cnt_p[i - 1] + 1;
    cnt_all[i] = 2 * cnt_all[i - 1] + 3;
  }
  ll ans = recursion(N, X);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3592
#include <stdio.h>

#define MAX 55

int main() {
	int x, y, i, j, h, w;
	char f[MAX][MAX];
	scanf("%d %d", &h, &w);
	for(y=1; y<=h; y++)
	    scanf("%s", f[y]+1);
	for(y=1; y<=h; y++)
	    for(x=1; x<=w; x++)
	        if(f[y][x]=='.'){
		        f[y][x] = '0';
		        for(i=-1; i<=1; i++)
		            for(j=-1; j<=1; j++)
		                if(f[y+i][x+j]=='#')
			                f[y][x]++;
	        }
	for(y=1; y<=h; y++)
	    printf("%s\n", f[y]+1);
	
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
	int n, h;
	int ans = 0;
	int hmax = 0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h;
		if (h >= hmax) {
			hmax = h;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main() {
  int N;
  double count = 0;
  cin >> N;
  vector<double> vec(N);
  for(int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  for(int i = 0; i < N; i++) {
    vec.at(i) = 1 / vec.at(i);
  }
  for(int i = 0; i < N; i++) {
    count = count + vec.at(i);
  }
  cout << 1/count << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a[6],s[6],d,f,g,h,i,j;
	while(1){
		scanf("%d %d",&a[0],&s[0]);
		f=a[0]+s[0];
		g=0;
		if(a[0]==0&&s[0]==0) break;
		for(i=1;i<5;i++){
			scanf("%d %d",&a[i],&s[i]);
			d=a[i]+s[i];
			if(f<d){
				f=d;
				g=i;
			}
		}
		if(g==0) printf("A ");
		if(g==1) printf("B ");
		if(g==2) printf("C ");
		if(g==3) printf("D ");
		if(g==4) printf("E ");
		printf("%d\n",f);
	}
	return 0;
}

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

int main() {
  int n, a;
  
  cin >> n >> a;
  
  int surplus = n % 500;
  
  if (surplus == 0 || surplus < a) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
(d,g),*a=$<.map{|s|s.split.map &:to_i}
f=[]
(0...1<<d).map{|b|
s=0
n=0
r=nil
(0...d).map{|i|b[i]>0?(n+=a[i][0];s+=a[i][0]*-~i*100+a[i][1]):r=i}
f<<n+[0,(g-s-1)/(-~r*100)+1].max if r&&g-s<=a[r][0]*-~r*100
r||f<<n
}
p f.min


Measured memory_bytes: 1916
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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 ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
// const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p.at(i);
    }

    int cnt = 0;
    for (int i = 0; i < n - 2; i++) {
        if ((p[i] < p[i + 1] && p[i + 1] < p[i + 2]) || (p[i + 2] < p[i + 1] && p[i + 1] < p[i])) {
            cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 256
//
//  main.cpp
//  Study
//
//  Created by 佐々木勇星 on 2020/03/12.
//  Copyright © 2020 佐々木勇星. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <map>

using namespace std;


int main(int argc, const char * argv[]) {

    string s, ans = "Yes";
    cin >> s;
    
    for (int i=0; i<s.size(); i++)
    {
        if ((i+1) % 2 == 0 && s[i] == 'R')
        {
            ans = "No";
            break;
        } else if ((i+1) % 2 == 1 && s[i] == 'L')
        {
            ans = "No";
            break;
        }
    }
    
    cout << ans << endl;
    
}


Measured memory_bytes: 256
// khodaya khodet komak kon
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 2e5 + 10;
const ll INF = 1e18;
const ll LOG = 20;
vpl G[N];
ll C[N], n, v, u;

void DFS(ll v, ll p = 0, ll c = 0){
	C[v] = c;
	for (auto u:G[v]){
		if (u.F == p) continue;
		if (u.S % 2 == 0){
			DFS(u.F, v, c);
		}else{
			DFS(u.F, v, 1 - c);
		}
	}
	return;
}

int main(){
	IOS;
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		ll w;
		cin >> v >> u >> w;
		G[v].pb({u, w});
		G[u].pb({v, w});
	}
	
	DFS(1);
	for (int i = 1; i <= n; i++){
		cout << C[i] << '\n';
	}
	
	
	
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




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

int main()
{
	int N,friends = 0;
	cin >> N;
	int *ai = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> ai[i];
	}

	for (int i = 1; i <= N; i++)
	{
		if (i == ai[ai[i - 1] - 1])
		{
			friends++;
		}
	}

	cout << friends / 2 << endl;
	return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <functional>
using namespace std;

typedef unsigned uint;

vector<uint> st;

void enumerate(int i, uint use, uint S){
	if(i == 8){
		st.push_back(S);
	}
	else{
		for(int j = 0; j < 9; ++j){
			if(~use >> j & 1){
				enumerate(i + 1, use | 1 << j, S | j << (4 * i));
			}
		}
	}
}

inline int index(uint S){
	return lower_bound(st.begin(), st.end(), S) - st.begin();
}

int encode(const vector<uint> &v){
	uint S = 0;
	for(int i = 0; i < 8; ++i){
		S |= v[i] << (i * 4);
	}
	return index(S);
}

void decode(int idx, vector<uint> &v){
	uint x = 36;
	uint S = st[idx];
	for(int i = 0; i < 8; ++i){
		uint y = S >> (i * 4) & 15;
		v[i] = y;
		x -= y;
	}
	v[8] = x;
}

int input(){
	uint r = 0, x = 0;
	for(int i = 0; i < 8; ++i){
		scanf("%u", &x);
		r |= x << (i * 4);
	}
	scanf("%*u");
	return index(r);
}

int solve(int ch, int cv){
	typedef pair<int,int> pii;

	int first = input();
	int last = input();
	if(first == last){ return 0; }

	vector<int> dist(st.size(), 1000000000);
	dist[first] = 0;
	priority_queue<pii,vector<pii>,greater<pii> > pq;
	pq.push(pii(0, first));
	
	int dif[4] = {1, 8, 3, 6};
	int cost[4] = {ch, ch, cv, cv};
	
	vector<uint> v1(9), v2(9);
	while(!pq.empty()){
		int idx = pq.top().second;
		int d = pq.top().first;
		pq.pop();
		if(dist[idx] != d){ continue; }
		if(idx == last){ return d; }

		decode(idx, v1);
		int zero = find(v1.begin(), v1.end(), 0u) - v1.begin();
		for(int i = 0; i < 4; ++i){
			v2 = v1;
			swap(v2[zero], v2[(zero + dif[i]) % 9]);
			int to = encode(v2);
			if(dist[to] > d + cost[i]){
				dist[to] = d + cost[i];
				pq.push(pii(dist[to], to));
			}
		}
	}
	throw 0;
}

int main(){
	enumerate(0, 0, 0);
	sort(st.begin(), st.end());

	int ch, cv;
	while(scanf("%d%d", &ch, &cv), ch){
		printf("%d\n", solve(ch, cv));
	}
}

Measured memory_bytes: 6820
#include<stdio.h>
int main(void)
{
	int i, j, h, k, map[101][101];
	char a[201];
	scanf("%d %d", &h, &k);
	for (i = 0; i < h; i++)
	{
		scanf("%s", a);
		for (j = 0; j < k; j++)
		{
			if (a[j] == 'c')
			{
				map[i][j] = 0;
			}
			else
			{
				map[i][j] = -1;
			}
		}
	}
	for (i = 0; i <h; i++)
	{
		for (j = 1; j < k; j++)
		{
			if (map[i][j] < 0)
			{
				if (map[i][j - 1] >= 0)
				{
					map[i][j] = map[i][j - 1] + 1;
				}
			}
		}
	}
	for(i = 0; i < h; i++)
	{
		for (j = 0; j < k; j++)
		{
			if (j == k - 1)
			{
				printf("%d", map[i][j]);
			}
			else
			{
				printf("%d ", map[i][j]);
			}
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1836
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef struct dice{
    int face[6];
}dice;
 
void rotate(dice *d, char dir)
{
    int temp;
    switch(dir) {
    case 'N':
        temp=d->face[0];
        d->face[0]=d->face[1];
        d->face[1]=d->face[5];
        d->face[5]=d->face[4];
        d->face[4]=temp;
        break;
    case 'E':
        temp=d->face[0];
        d->face[0]=d->face[3];
        d->face[3]=d->face[5];
        d->face[5]=d->face[2];
        d->face[2]=temp;
        break;
    case 'W':
        temp=d->face[0];
        d->face[0]=d->face[2];
        d->face[2]=d->face[5];
        d->face[5]=d->face[3];
        d->face[3]=temp;
        break;
    case 'S':
        temp=d->face[0];
        d->face[0]=d->face[4];
        d->face[4]=d->face[5];
        d->face[5]=d->face[1];
        d->face[1]=temp;
        break;
    }
}
 
int isSame(dice d1, dice d2)
{
    static const char dir[]="NNNESSSWNNNESSSWNNNESSSW";
    int i, j;
    for(i=0; i<24; i++) {
        for(j=0; j<6 && d1.face[j]==d2.face[j]; j++);
        if(j==6) return 1;
        rotate(&d2, dir[i]);
    }
    return 0;
}
 
int main()
{
    dice d[100];
    int i, j, n;
    scanf("%d", &n);
    for(i=0; i<n; i++) {
        for(j=0; j<6; j++) {
            scanf("%d", &d[i].face[j]);
        }
        for(j=0; j<i; j++) {
            if(isSame(d[i], d[j])) {
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    return 0;
}


Measured memory_bytes: 2148
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T&a,T b){if(a>b){a=b;return 1;}return 0;}
using ll = long long;

int n,m,k;
string s,t;
bool ok=true;

int main() {
  cin >> n;
  cout << n/500*1000+n%500/5*5 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int num;
	int c;
	int i;
	int j;
	int k;
	int l;


	c = 0;
	while(scanf("%d", &num) != EOF){
		for(i = 0; i < 10; i++){
			for(j = 0; j < 10; j++){
				for(k = 0; k < 10; k++){
					for(l = 0; l < 10; l++){
						if((i + j + k + l) == num){
							c++;
						}
					}
				}
			}
		}
		printf("%d\n", c);
		c = 0;
	}

	return(0);
}

Measured memory_bytes: 596
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;

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

int main() {
	llint a, b, c;
	cin >> a >> b >> c;
	a -= 2;
	llint ans = (c - b)*a + 1;
	if (ans < 0) {
		ans = 0;
	}
	cout << ans << endl;
	return 0;
}

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

int gcd(int x, int y){
    if (x % y == 0) {
        return y;
    } else if (x >= y) {
        return gcd(y, x % y);
    } else {
        return gcd(x, y % x);
    }
}

int main(){
    int x, y;

    cin >> x >> y;

    cout << gcd(x, y) << endl;
}


Measured memory_bytes: 3108
<?php
  $ary = array();
  while (true) {
    $str = trim(fgets(STDIN));
    if ($str === '') {
      $alpha = range('a','z');
      $z = join('', $ary);
      foreach ($alpha as $a) {
        print($a . " : " . substr_count(strtolower($z), $a) . "\n");
      }
      return;
    }
    $ary[] = $str;
  }
?>

Measured memory_bytes: 6604
#include"bits/stdc++.h"
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[3];
    for(int i=0;i<n;i++){
        cin >> a[0] >> a[1] >> a[2];
        sort(a,a+3);
        if(a[0]*a[0]+a[1]*a[1]==a[2]*a[2])
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}



Measured memory_bytes: 3088
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <numeric>
#include <set>
#include <unordered_set>
#include <queue>
#include <boost/math/constants/constants.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0;i < n;i++)
#define FOR(i, n, m) for(int i=n; i<m; ++i)

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e13;
const int mod = 1e9+7;
#define ll long long

signed main() {
   int a,b;
   cin >> a >> b;
   int ans = max(a+b,a-b);
   ans = max(a*b,ans);
    cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3592
import sys
sys.setrecursionlimit(10**7)

def teleport(city, end, teleportmap, count=1):

    next_city = teleportmap[city]

    if count == end:
        return next_city

    else:
        return teleport(next_city, end, teleportmap, count+1)

n, k = map(int,input().split())
a = list(map(int, input().split()))
teleportmap = dict(zip(range(1, len(a)+1), a))

if k <= n:
    print(teleport(1, k, teleportmap))

else:
    countmap = [0]*n
    countmap[0] = 1

    next_city =1
    for _ in range(1, n+1):
        next_city = a[next_city-1]
        countmap[next_city -1] += 1
        if countmap[next_city -1] == 2:
            start = next_city
            break

    roop = {}
    for j in range(1, n+1):
        roop[start] = teleportmap[start]
        start = roop[start]
    
    num_r = len(roop)

    num_until_r= 0
    for m in teleportmap.keys():
        if m not in roop and countmap[m-1] != 0:
            num_until_r += 1
    
    k_r = k - num_until_r
    num_end = k_r%num_r

    if num_end == 0:
        print(next_city)
        
    else:
        print(teleport(next_city, num_end, roop))
            


    

        


Measured memory_bytes: 214956
#include <bits/stdc++.h>
 
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>
#define debug cout << "Ok" << endl;

using namespace std;

void solve(){

	return;
}
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n,m,cont=1;

	cin >> n >> m;

	while(n>=m){
		cont++;
		n = n/m;
	}

	cout << cont << endl;


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int lcm(int a, int b){
  return a/gcd(a,b)*b;
}
int main(void){
    long long int a,b,n,x,i=0,ans=0,c=0;
    double v[200000];
    string s;
    cin >> n;
    for(i=0;i<n;i++)
    {
        cin >> v[i];
    }
    sort(v,v+n);
    for(i=0;i<n-1;i++)
    {
        v[i+1]=(v[i]+v[i+1])/2;
    }
    cout << v[n-1] << endl;
    return 0;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int X, Y; cin >> X >> Y;
    if((X+Y)%3 != 0){
        cout << 0 << endl;
        return;
    }

    int a = (2*Y-X)/3;
    int b = Y - 2*a;

    cout << comb(a+b, a) << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = 2019;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

void solve(){
   string s;

   cin >> s;
   int n = (int)(s.size());

   vector<int> freq(mod, 0);
   int ans = 0;
   for (int i = 0; i < n; ++i)
   {
      int curr = s[i] - '0';
      vector<int> X(mod, 0);
      for (int j = 0; j < mod; ++j)
      {
         if (freq[j] == 0){
            continue;
         }
         int num = j;
         num *= 10;
         num %= 2019;
         num += curr;
         num %= 2019;
         X[num] = freq[j];
      }
      X[curr]++;
      ans += X[0];
      freq = move(X);
   }

   cout<<ans;
}

int32_t main(){_
   
   int t = 1;
   //cin >> t;

   while(t--){
     solve();
     cout << endl;
   }
   

   return 0;
}

Measured memory_bytes: 3668
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
 
typedef long long ll;

#define MP make_pair
#define F first
#define S second

int main(){
  	int n,m;
    cin >> n >> m;
	vector<ll> dp(n+1,-1);
    dp[0]=1;
    dp[1]=1;
    int tmp;
    for(int i=0;i<m;i++){
        cin >> tmp;
    	dp[tmp]=0;
    }
    
    for(int i=2;i<=n;i++){
    	if(dp[i]!=0) dp[i]=(dp[i-1]+dp[i-2])%1000000007;
    }
	cout << dp[n] << endl;
}



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

//関数
    //const long INF=1000000000000000;
    
//main関数
int main() {
    
    
    //入力
    long N;
    cin>>N;
    vector<long> A(N);
    for(int i=0;i<N;i++){
        cin>>A.at(i);
    }
    
    
    
    //計算
    sort(A.begin(),A.end());
    
    long ans=1;
    long sumtili=0;
    for(int i=0;i<N;i++){
        sumtili+=A.at(i);
    }
    
    //cout<<sumtili<<endl;
    for(int i=N-2;i>=0;i--){
        sumtili-=A.at(i+1);
        if(A.at(i+1)>sumtili*2){
            break;
        }else{
            ans++;
        }
        //cout<<i<<" "<<sumtili<<" "<<ans<<endl;
    }
    
    
    //出力
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
//
//  CPlibrary
//
//  Created by Tanmay Singh on 3/03/2020.
// INDIAN INSTITUTE OF TECHNOLOGY (BHU) , VARANASI
//  Copyright © 2020 Tanmay Singh. All rights reserved.
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <climits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
#define FAST(); ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
#define mod 1000000007
typedef long long int  bigint ;
typedef std::vector< int > vi;
typedef std::vector< long long int > vll;
typedef std::vector< vi > vvi;
 
using namespace std;

int main(){
    FAST() ;
    int N ; cin >> N ;
    string A , B ; cin >> A >> B ;
    if( A == B ){
        cout << N << endl ;
        return 0 ;
    }
    int i = 1 ;
    int ma = 0 ;
    while( i <= B.length() ){
        string pref = B.substr(0 , i ) ;
        string suff = A.substr(A.length() - i , i );
        if( pref == suff )
            ma = max( ma , i ) ;
        i++ ;
    }
    cout << N + N - ma << endl ;
    return 0 ;
}


Measured memory_bytes: 256
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static final int MOD = 998244353;

	static int add(int a, int b) {
		int res = a + b;
		return res >= MOD ? res - MOD : res;
	}

	static void solve() throws Exception {
		String s = scanString();
		int n = s.length();
		boolean dyn1[][][] = new boolean[n + 1][n + 1][n + 1];
		dyn1[0][0][0] = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= n; j++) {
				for (int k = 0; k <= n; k++) {
					if (dyn1[i][j][k]) {
						dyn1[i + 1][j][k] = true;
						if (j > 0 && s.charAt(i) == '1') {
							dyn1[i + 1][j - 1][k + 1] = true;
						}
						if (k > 0 && s.charAt(i) == '0') {
							dyn1[i + 1][j + 1][k - 1] = true;
						}
						if (i + 1 < n) {
							if (s.charAt(i) == '0' || s.charAt(i + 1) == '0') {
								dyn1[i + 2][j + 1][k] = true;
							}
							if (s.charAt(i) == '1' || s.charAt(i + 1) == '1') {
								dyn1[i + 2][j][k + 1] = true;
							}
						}
					}
				}
			}
		}
		int dyn2[][][] = new int[n + 1][n + 1][n + 1];
		dyn2[n][0][0] = 1;
		int ans = MOD - 1;
		for (int i = n; i >= 0; i--) {
			for (int j = 0; j <= n; j++) {
				for (int k = 0; k <= n; k++) {
					if (dyn1[i][j][k]) {
						ans = add(ans, dyn2[i][j][k]);
					}
					if (i > 0 && s.charAt(i - 1) == '0') {
						dyn2[i - 1][j][k] = add(dyn2[i - 1][j][k], dyn2[i][j][k]);
					} else if (j < n) {
						dyn2[i][j + 1][k] = add(dyn2[i][j + 1][k], dyn2[i][j][k]);
					}
					if (i > 0 && s.charAt(i - 1) == '1') {
						dyn2[i - 1][j][k] = add(dyn2[i - 1][j][k], dyn2[i][j][k]);
					} else if (k < n) {
						dyn2[i][j][k + 1] = add(dyn2[i][j][k + 1], dyn2[i][j][k]);
					}
				}
			}
		}
		out.print(ans);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

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

#define INF 1LL << 60
#define MOD 1000000007;
#define pb push_back

#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPR(i, b, e) for (int i = (b); i <= (e); i++)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": " << endl; for (const auto& v: (a)) cout << v << endl

int N;

int main() {
    cin.tie(0);
    cin >> N;

    string s;
    int cnt = 0;
    int a = 0, b = 0, ba = 0;
    REP(i, N) {
        cin >> s;
        int L = s.size();
        REP(j, L-1) {
            if (s[j] == 'A' && s[j+1] == 'B') cnt++;
        }

        if (s[L-1] == 'A' && s[0] == 'B') {
            ba++;
        } else if (s[L-1] == 'A') {
            a++;
        } else if (s[0] == 'B') {
            b++;
        }
    }

    int ans = cnt + ba + min(a, b);
    if (ba > 0 && a + b == 0) ans--;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
//#define int long long
using namespace std;

int delta[3][2] = {{-1, -1}, {-1, 0}, {0, -1}};

int dp[3000][3000];
char carac[3000][3000];

string a, b;

int lcs(int iA, int iB){
    if (iA == -1 || iB == -1)
        return 0;
    
    if (dp[iA][iB] != -1)
        return dp[iA][iB];
    
    int rep = 0;
    int temp = 0;

    if (a[iA] == b[iB]){
        rep = lcs(iA - 1, iB - 1) + 1;
        carac[iA][iB] = a[iA];
    }
    else{
        rep = lcs(iA - 1, iB);
        temp = lcs(iA, iB - 1);

        if (temp > rep)
            rep = temp;
    }

    dp[iA][iB] = rep ;
    return rep;
}

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

    for (int i = 0; i < 3000; i++){
        for (int a = 0; a < 3000; a++){
            dp[i][a] = -1;
        }
    }

    lcs(a.length()-1, b.length() - 1);
    pair<int,int> pos = {a.length()-1, b.length() -1};

    string chaine = "";
    bool  continuer = true;
    while (continuer){
        continuer = false;

        if (pos.first >= 0 && pos.second >= 0 && carac[pos.first][pos.second]){
            chaine = carac[pos.first][pos.second] + chaine;
            --pos.first; --pos.second; 
	    continuer = (pos.first >= 0 && pos.second >= 0);
	    continue;
        }
        
        int maxi = -1;
        pair<int,int>  nextPos = {-1,-1};

        for (int i = 0; i < 3; i++){
            int dx = delta[i][0]; int dy = delta[i][1];

            bool inGrid = (0 <= pos.first + dx && 0 <= pos.second + dy);
            if (inGrid && dp[pos.first + dx][pos.second + dy] > maxi){
                maxi = dp[pos.first + dx][pos.second + dy];
                nextPos.first = pos.first + dx;
                nextPos.second = pos.second + dy;
                continuer = true;
            }
        }
        pos.first = nextPos.first;
        pos.second = nextPos.second;
    }
    cout << chaine;

}

Measured memory_bytes: 44544
#include <stdio.h>
#include <stdlib.h>
int H;
int parent(int i);
int left(int i);
int right(int i);
void swap(int *a, int *b);
void maxHeapify(int *A, int i);
void buildMaxHeap(int *A);
int main(){
  int i;
int *A;
  scanf("%d", &H);
  A = malloc(sizeof(int) * (H+1));
  for(i = 1; i <= H; i++){
    scanf("%d", &A[i]);
}
  buildMaxHeap(A);
  for(i = 1; i <= H; i++){
    printf(" %d", A[i]);
}
  printf("\n");
return 0; }
int parent(int i){
  return i/2;
}
int left(int i){
  return i*2;
}
int right(int i){
  return i*2+1;
}
void swap(int *x, int *y){
  int temp;
  temp = *x;
  *x = *y;
*y = temp; }
void maxHeapify(int *A, int i){
  int l, r, largest;
  l = left(i);
  r = right(i);
  if(l <= H && A[l] > A[i]){
    largest = l;
  } else {
    largest = i;
}
  if(r <= H && A[r] > A[largest]){
    largest = r;
  }
  if(largest != i){
    swap(&A[i], &A[largest]);
    maxHeapify(A, largest);
} }
void buildMaxHeap(int *A){
  int i;
  for(i = H/2; i > 0; i--){
    maxHeapify(A, i);
} }


Measured memory_bytes: 3656
import std;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long N, K;
    scan(N, K);
    long base = powmod(10, 100, MOD);
    long ans;
    long a;
    foreach (i; 0 .. K)
    {
        a = (a + i);
    }
    long b;
    foreach (i; 0 .. K)
    {
        b = (b + N - i);
    }
    foreach (i; K .. N + 1)
    {
        ans = (MOD + ans + b - a + 1) % MOD;
        // writefln("%s %s", i, N - i);
        // writeln(b - a + 1);
        a += i;
        b += N - i;
    }
    writeln(ans + 1);
}

/// x^^n % m
T powmod(T = long)(T x, T n, T m = 10 ^^ 9 + 7)
{
    if (n < 1)
        return 1;
    if (n & 1)
    {
        return x * powmod(x, n - 1, m) % m;
    }
    T tmp = powmod(x, n / 2, m);
    return tmp * tmp % m;
}


Measured memory_bytes: 3680
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<complex>//real().imag().
#include<cctype>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<string>
#include<utility>
#include<iterator>
#define pii pair<int,int>
#define make_pair mp
using namespace std;
typedef long long ll;
const int N = 200005;
int main()
{
	// freopen("D:\\in.txt","r",stdin);
	// freopen("D:\\out.txt","w",stdout);
	//ios::sync_with_stdio(false);
	//system("pause");
	int a[10];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	if (a[0] + a[1] == a[2])
	{
		cout << "Yes" << endl;
	}
	else
		cout << "No" << endl;
	return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
int arr[3];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>arr[0]>>arr[1]>>arr[2];

    sort(arr, arr + 3);
    if(arr[0] == arr[1] && arr[0] != arr[2]){
        cout<<"Yes"<<endl;
    }else if(arr[0] != arr[1] && arr[1] == arr[2]){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Measured memory_bytes: 256