akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,h,w;
	cin >> h >> w >> n;
	if(h>w)
		cout << (n+h-1)/h << "\n";
	else
		cout << (n+w-1)/w << "\n";
}
	

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
 
int main(){
  string S;
  cin >> S;
  if(S.at(0)=='a' && S.at(1)=='b' && S.at(2)=='c'){
    cout << "Yes" << endl;
  }
  else if(S.at(0)=='a' && S.at(1)=='c' && S.at(2)=='b'){
    cout << "Yes" << endl;
  }
  else if(S.at(0)=='b' && S.at(1)=='a' && S.at(2)=='c'){
    cout << "Yes" << endl;
  }
  else if(S.at(0)=='b' && S.at(1)=='c' && S.at(2)=='a'){
    cout << "Yes" << endl;
  }
  else if(S.at(0)=='c' && S.at(1)=='b' && S.at(2)=='a'){
    cout << "Yes" << endl;
  }
  else if(S.at(0)=='c' && S.at(1)=='a' && S.at(2)=='b'){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}
  
  
  
  


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);

	vector<int> res(n);
	vector<pair<int, int> > w;
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d,%d", &a, &b);
		w.push_back(make_pair(a, b));
	}

	for (int i = 0; i < n; ++i) {
		int r = i+1;
		for (int j = 0; j < m; ++j) {
			if (w[j].first == r) r = w[j].second;
			else if (w[j].second == r) r = w[j].first;
		}
		res[r-1] = i+1;
	}
	for (int i = 0; i < n; ++i) printf("%d\n", res[i]);
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <limits>
#include <cmath>
#include <cassert>

using namespace std;
using ll = long long;

const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    bool ok = false;
    for(int i = 1; i < 10; i++)
    {
        int x = n / i;
        if(n % i != 0) continue;
        if(n / i >= 1 and n / i <= 9) ok = true;
    }
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef pair<int, int>P;
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
typedef vector<vector<ll>> mat;
typedef vector<int> vec;
#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()
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll qp(ll a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };



void solve() {
    ll a, b, c, d, n, k, x,l,r;
    string s, t;
    ll ans = 0;
    double dans = 0;
    string sans = "Yes";
    vector<ll> re;
    vector<ll> de;

    cin  >> a >> b >>n;

    ll min_tmp1 = INF;
    rep(i,a) {
        ll t;
        cin >> t;
        re.push_back(t);
        min_tmp1 = min(t,min_tmp1);
    }

    ll min_tmp2 = INF;
    rep(i,b) {
        ll t;
        cin >> t;
        de.push_back(t);
        min_tmp2 = min(t,min_tmp2); 
    }

    ll mini = min_tmp1 + min_tmp2;

    rep(i,n){
        ll x, y, c;
        cin >> x >> y >> c;
        mini = min(mini, re[x-1] + de[y-1] - c);
    }

    ans = mini;

    
    std::cout << ans << endl; 
    
    // std::cout << sans << endl; 
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    solve();
    // stop
        return 0;
}

Measured memory_bytes: 2548
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()
#define sz(a) (int)a.size()

const int inf = (1ll << 30) - 1;
const int maxn = (int) 1e5 + 10;

using namespace std;

int cnt[100100];
int n, x;
void solve(){
	scanf("%d", &n);
	for(int i = 0, x; i < n; i++){
		scanf("%d", &x);
		cnt[x]++;
	}
	int ans = 0;
	for(int i = 1; i < 100010; i++)
		ans = max(ans, cnt[i] + cnt[i-1] + cnt[i+1]);
	cout << ans << endl;
}

int main () {
    //cout << "Hello world\n";
    int t=1;
    //scanf("%d", &t);
    for(int i=1; i <= t; i++){
      //printf("Case #%d\n", i);
      solve();
    }

    return 0;
}


Measured memory_bytes: 640
N = input()

half = len(N) // 2

if len(N)%2 == 0:
  left_N = N[:half]
  right_N = N[half:]
else:
  left_N = N[:half]
  right_N = N[half+1:]

for l,r in zip(left_N, right_N[::-1]):
  if l != r:
    print('No')
    exit()
    
print('Yes')

Measured memory_bytes: 3060
#include <stdio.h>
int main (void)
{
	int h[2],k[2],a,b,c,d,pointh,pointk,e,kai,moto;
	for(e=0;e<2;e++){
		scanf("%d %d",&h[e],&k[e]);
	}
	scanf("%d %d %d %d",&a,&b,&c,&d);
	moto=k[0]*b+h[0]*a;
	kai=k[1]*b+h[1]*a;
	pointh=h[0]/10*c+k[0]/20*d+moto;
	pointk=h[1]/10*c+k[1]/20*d+kai;
	if(pointh==pointk) printf("even\n");
	else if(pointh>pointk) printf("hiroshi\n");
	else if(pointh<pointk) printf("kenjiro\n");
	else printf("\n");
	return 0;
}



Measured memory_bytes: 2112
#include "bits/stdc++.h"
#define int long long

using namespace std;

signed main() {
    int a[] = {1, 1, 1, 2, 1, 2, 1, 5,  2, 2, 1, 5, 1, 2, 1, 14,
               1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K;
    cin >> K;
    cout << a[K - 1] << endl;
    return 0;
}

Measured memory_bytes: 256
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
const int N=100,M=100000;
int n,m;
int a[N+1];
int dp[N+1][M+1];
int Sum[M+1];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		Sum[0]=dp[i-1][0];
		for(int j=1;j<=m;j++)Sum[j]=(Sum[j-1]+dp[i-1][j])%mod;
		for(int j=0;j<=m;j++)dp[i][j]=((Sum[j]-(!max(0,j-a[i])?0:Sum[max(0,j-a[i])-1]))%mod+mod)%mod;
//		for(int j=0;j<=m;j++)printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
	}
	cout<<dp[n][m];
	return 0;
}
/*1
3 4
1 2 3
*/
/*2
1 10
9
*/
/*3
2 0
0 0
*/
/*4
4 100000
100000 100000 100000 100000
*/

Measured memory_bytes: 39680
# ABC 159: B – String Palindrome
S = input()
N = len(S)

conds1 = (N - 1) // 2
conds2 = (N + 3) // 2
S1 = S[:conds1]
S2 = S[conds2 - 1:]

print('Yes' if S == S[::-1] and S1 == S1[::-1] and S2 == S2[::-1] else 'No')

Measured memory_bytes: 3060
#include <iostream>
#include <queue>
using namespace std;
int h,w,n;
char map[1010][1010];
class Node{
    public:
    int x,y,cost;
    Node(int x,int y,int cost):x(x),y(y),cost(cost){}
    Node(){}
};
int bfs(char s,char e)
{
    bool flag[1010][1010]={{false}};
    queue<Node> Q;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(map[i][j]==s)Q.push(Node(j,i,0));
        }
    }
    while(!Q.empty())
    {
        Node t=Q.front();Q.pop();
        if(map[t.y][t.x]==e)return t.cost;
        if(flag[t.y][t.x])continue;
        int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
        for(int i=0;i<4;++i){
            Node next=t;
            next.cost++;
            next.x+=dx[i];next.y+=dy[i];
            if(next.x>=0&next.x<w&next.y>=0&next.y<h&map[next.y][next.x]!='X')Q.push(next);
        }
        flag[t.y][t.x]=true;
    }
}
int main()
{
    cin>>h>>w>>n;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            cin>>map[i][j];
        }
    }
    int ans=0;
    char f=n+'0';
    ans+=bfs('S','1');
    for(char i='1';i<f;++i){
        ans+=bfs(i,i+1);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3204
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
int wins[100010]={};

int main(){ _;
  string s;cin>>s;
  int sz=s.size();
  int cntp=0;
  REP(i,sz)if(s[i]=='p')cntp++;
  cout<<sz/2-cntp<<endl;
}


Measured memory_bytes: 512
n = int(input())
a = [int(input()) for _ in range(n)]


b = []

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[-1]:
            b.append(ai)
        else:
            l = -1
            r = len(b)
            mid = (l + r) // 2
            while (r - l > 1):
                mid = (l + r) // 2
                if b[mid] >= ai:
                    l = mid
                else:
                    r = mid
            b[r] = ai

print(len(b))


Measured memory_bytes: 56024
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
RC110 D
"""


n,m = map(int,input().split())

from math import sqrt
from collections import deque
def divisors(x):
    divs = deque()
    sx = int(sqrt(x))
    if x == sx**2:
        divs.append(sx)
        sx = sx-1
    for i in range(sx,0,-1):
        if x%i==0:
            divs.append(i)
            divs.appendleft(x//i)
    return(divs)

mdivs = list(divisors(m))
from collections import defaultdict
divsdict = defaultdict(list)
for d in mdivs:
    divsdict[d] = [dd for dd in mdivs if d%dd==0]

nbin = list(map(int,format(n,'b')))
nnbin = len(nbin)
dpdicts = [defaultdict(int) for i in range(nnbin)]
for d in mdivs:
    dpdicts[0][d]=1

cut = 10**9+7

for i in range(1,nnbin):
    for d in mdivs:
        dpdicts[i][d] = sum(map(lambda x:dpdicts[i-1][x]*dpdicts[i-1][d//x],divsdict[d]))%(10**9+7)

dpdictbin = defaultdict(int)
for d in mdivs:
    dpdictbin[d]=0
dpdictbin[1]=1

nbin.reverse()
for i in filter(lambda x:nbin[x]==1,range(nnbin)):
    for d in mdivs:
        dpdictbin[d] = sum(map(lambda x:dpdictbin[x]*dpdicts[i][d//x],divsdict[d]))%(10**9+7)



print(dpdictbin[m])



Measured memory_bytes: 5568
def itp_replace(stri,a,b,c):
    a = int(a)
    b = int(b)
    return stri[:a] + c + stri[b+1:]

def itp_reverse(stri,a,b):
    a = int(a)
    b = int(b)
    return stri[:a] + stri[a:b+1][::-1]+stri[b+1:]

def itp_print(stri,a,b):
    a = int(a)
    b = int(b)
    print(stri[a:b+1])

test_str = input()
test_num = int(input())
order = []
for a in range(test_num):
    temp = input().split()
    order.append(temp)

for a in order:
    if a[0] == 'replace':
        test_str = itp_replace(test_str,a[1],a[2],a[3])
    if a[0] == 'reverse':
        test_str = itp_reverse(test_str,a[1],a[2])
    if a[0] == 'print':
        itp_print(test_str,a[1],a[2])



Measured memory_bytes: 5620
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
int main() {
	int A, B;
	cin >> A >> B;
	vector<int>vec(3);
	vec.at(0) = A + B;
	vec.at(1) = A - B;
	vec.at(2) = A * B;
	sort(vec.begin(), vec.end());
	cout << vec.at(2) << endl;
}

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

using namespace std;
int main(void){
    string a,b;
    cin >> a >> b;
    for(int i=0;i<a.size();i++){int flag=0;for(int j=0;j<a.size();j++){
        if(a[(i+j)%a.size()]!=b[j])flag=1;
    }
        if(flag==0){printf("Yes");return 0;}
    }
    printf("No");
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args)
	{
		Scanner stdIn = new Scanner(System.in);
		
		while(true)
		{
			int N = stdIn.nextInt();
			
			if(N==0)
			{
				break;
			}
			
			int[][] data = new int[N][2];
			int[] data_x = new int[N];
			int[] data_y = new int[N];
			int[] move_x = {-1,0,1,0};
			int[] move_y = {0,1,0,-1};
			data_x[0] = 0;
			data_y[0] = 0;
			int min_x = 0;
			int max_x = 0;
			int min_y = 0;
			int max_y = 0;
			
			for(int i=1;i<N;i++)
			{
				data[i][0] = stdIn.nextInt();
				data[i][1] = stdIn.nextInt();
			}
			
			for(int i=1;i<N;i++)
			{
				data_x[i] = data_x[data[i][0]]+move_x[data[i][1]];
				data_y[i] = data_y[data[i][0]]+move_y[data[i][1]];
				if(min_x>data_x[i])
				{
					min_x = data_x[i];
				}
				if(max_x<data_x[i])
				{
					max_x = data_x[i];
				}
				if(min_y>data_y[i])
				{
					min_y = data_y[i];
				}
				if(max_y < data_y[i])
				{
					max_y = data_y[i];
				}
			}
			
			System.out.println(((max_x-min_x)+1)+" "+((max_y-min_y)+1));
			
		}
	}

}

Measured memory_bytes: 34184
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

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


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

long Gojo(long a)
{
  return a*a*a*a*a;
}

int main()
{
  long x;
  cin>>x;
  
  int a=0,b=0;
  for(a=-123;a<123;a++)
  {
    for(b=-122;b<122;b++)
    {
      if(Gojo(a)-Gojo(b)==x)
      {
        cout<<a<<" "<<b<<endl;
        return 0;
      }
      if(a==122&&b==121)
        cout<<"Unko"<<endl;
    }
  }

  //cout<<a<<" "<<b<<endl;
 
}

Measured memory_bytes: 3632
#include <stdio.h>
int main(void)
{
    int n, k, x, y, ans=0, i;

    scanf("%d%d%d%d", &n, &k, &x, &y);
    for(i=1;i<=n;i++){
        if(i<=k)
            ans=ans+x;
        else
            ans=ans+y;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

signed main(){
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);

  int n;
  cin >> n;
  vector<int> a(5);
  REP(i,5) cin >> a[i];
  int min = *min_element(a.begin(), a.end());

  cout << 5 + ceil((D)n / min) - 1 << endl;

  return 0;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    static char N[1000202];
    Scs(N);
    int M = strlen(N);

    vector<vi> dp(M+1,vi(2,INF));
    dp[0][0] = 0;

    Rep(i,M){
        int ri = M-i-1;
        // kiri
        dp[i+1][0] = min( dp[i+1][0], dp[i][0] + (N[ri]-'0') );
        dp[i+1][0] = min( dp[i+1][0], dp[i][1] + (N[ri]-'0'+1) );
        // 0
        dp[i+1][1] = min( dp[i+1][1], dp[i][0] + 10 - (N[ri]-'0') );
        dp[i+1][1] = min( dp[i+1][1], dp[i][1] + 10 - (N[ri]-'0'+1) );
    }

    printf ("%d\n", min( dp[M][0], dp[M][1] + 1 ));

    return 0;
}



Measured memory_bytes: 55936
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  

}

Node treeMaximum(Node x){


}

Node treeSearch(Node u, int k){


}

Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;

    if(z->key < x->key)
      x = x->left;

    else
      x = x->right;
  }

  z->parent = y;

  if(y==NIL)
    root = z;

  else if(z->key < y->key)
    y->left = z;

  else
    y->right = z;
}

void inorder(Node u){
  if(u == NIL)
    return;

  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u == NIL)
    return;
  
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      
      if ( t != NIL ) printf("yes\n");
      
      else printf("no\n");
      
    }

    else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }

    else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
      
    }

    else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



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

int main(){
    std::string S, T, U;
    int A, B;

    std::cin >> S >> T;
    std::cin >> A >> B;
    std::cin >> U;

    if(U == S){
        A--;
    }else if(U == T){
        B--;
    }

    std::cout << A << " " << B << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#define EPS 0.00000001
using namespace std;
int equals(double x,double y){ return (abs(x-y)<EPS);}
double S3(double,double,double,double,double,double);
int main(){
  double x1,x2,x3,y1,y2,y3,xp,yp;
  while(cin>>x1>>y1>>x2>>y2>>x3>>y3>>xp>>yp){
    if(equals(
	      S3(x1,y1,x2,y2,xp,yp)+S3(x2,y2,x3,y3,xp,yp)+S3(x1,y1,x3,y3,xp,yp)
	      ,S3(x1,y1,x2,y2,x3,y3)
	      
	      ))
      cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
  
  return 0;
}
double S3( double x1, double y1, double x2,double y2, double x3, double y3 ){

  double sum = 0;
  sum = ( x1*y2 - x2*y1 ) + ( x2*y3 - x3*y2 ) + ( x3*y1 - x1*y3 );
  sum = abs(sum);
  sum /= 2;
  
  return sum;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
 #define pb push_back
 #define ll long long
 using namespace std;


 const int maxn = 1e6+5;
 int main(){
     int a, b; cin >> a >> b;
     if(a >= 10|| b >= 10) cout << -1 << endl;
     else cout << a*b << endl;
     return 0;
 }


Measured memory_bytes: 256
//
// Created by 永徳泰明 on 2019-01-12.
//

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;
#define dump(x)  cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define fill(x, y) memset(x,y,sizeof(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 999999999;

void readFromInputFile() {
#ifdef LOCAL
    static std::ifstream in("/Users/hoo/CLionProjects/for_atcoder/input");
    std::cin.rdbuf(in.rdbuf());
#endif
}

int main() {
    //readFromInputFile();
    int n,h,w;
    cin>>n>>h>>w;

    cout<<(n-h+1)*(n-w+1)<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;

ll n;
vector<ll> a;

int main() {
    cin >> n;
    a.resize(n);

    rep(i, n) cin >> a[i];
    ll max_n = *max_element(a.begin(), a.end());

    ll tmp = 1e10;
    ll ans = 0;
    rep(i, n) {
        if (a[i] == max_n) continue;

        // cout << abs(max_n / 2 - a[i]) << endl;
        if (abs(max_n / 2 - a[i]) < tmp) {
            tmp = abs(max_n / 2 - a[i]);
            ans = a[i];
        }
    }
    cout << max_n << " " << ans << endl;
}

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

typedef long long int lli;

int main()
{
	/*#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif*/

	ios::sync_with_stdio(0);
	cin.tie(0);

	int a,b;
	cin>>a>>b;

	if(b==1)
		cout<<"0";
	else
	{
		if(a>=b)
			cout<<"1";
		else
		{
			int x = (b-a);
			int y = (a-1);

			if(x%y==0)
				cout<< (x/y)+1;
			else
				cout<<(x/y)+2;
		}
	}
}

Measured memory_bytes: 256
def solve():
    s = input()
    t = input()
    d0 = {}
    d1 = {}
    if len(s) != len(t):
        print('No')
        return
    for i in range(len(s)):
        if s[i] in d0:
            if t[i] != d0[s[i]]:
                print('No')
                return
        elif t[i] in d1:
            if s[i] != d1[t[i]]:
                print('No')
                return
        else:
            d0[s[i]] = t[i]
            d1[t[i]] = s[i]
    print('Yes')


solve()


Measured memory_bytes: 41584
<?php

// define('DEBUG', true);
define('DEBUG', false);

// define('MOD', 1000000007);

fscanf(STDIN, "%d", $N);
$A = explode(" ", trim(fgets(STDIN)));

$x = 1;
foreach ($A as $aa) {
    if ($aa % 2 == 0) {
        $x *= 2;
    }
}

echo pow(3, $N) - $x;
echo PHP_EOL;

Measured memory_bytes: 4728
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n, k = get_li()
    if k == 1:
        print(0)
    else:
        print(n-k)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()


Measured memory_bytes: 65516
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define oo 10000000  //1e7
#define f first 
#define s second 

using namespace std;

int p[oo];
 
int32_t main ()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	for(int i=1;i<oo;i++){
		for(int j=i;j*i<oo;j++){
			if(i!=j)p[i*j]+=2;
			else p[i*j]++;
		}
	}

	int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<n;i++){
		ans += p[i];
	}
	cout<<ans<<endl;

	return 0;
}


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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int sum;
    sum = a + b + c;
    
    if (sum % 2 != 0) cout << "No" << endl;
    
    else {
        int hf;
        hf = sum / 2;
        if ((hf == a) || (hf == b) || (hf == c)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#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) fixed << setprecision(x)
//const ll p = 1e9 + 7;
//const ll p = 998244353;
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);

	string s;
	cin >> s;
	cout << s.substr(0, 4) << " " << s.substr(4) << endl;
}


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

int main() {
	int n;
	while (cin >> n && n) {
		int a[5001], min, max_a;
		min = a[0] = 0;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			if (i == 1) max_a = a[i] - a[0];
			a[i] += a[i - 1];
			if (a[i] - min > max_a) max_a = a[i] - min;
			if (a[i] < min) min = a[i];
		}
		cout << max_a << endl;
	}
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
const auto start_time = std::chrono::high_resolution_clock::now();
void timecalculater(){
    #ifndef ONLINE_JUDGE
    auto end_time = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
    #endif
}
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define repA(i, a, n) for(int  i = a; i <= (n); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long int> vll;
typedef vector<pii> vii;
ll p=1e9+7;
const int N=2e5+5;
ll add(ll a,ll b){
    ll t=(a+b);
    if(t>=p)t-=p;
        return t;
}
ll sub(ll a,ll b){
    ll t=a-b+p;
    t=t%p;
    return t;
}
ll power(ll a,ll x){
    ll r=1;
    while(x!=0){
        if(x%2==1){
            r=r*a;r%=p;
        }
        a=a*a;a%=p;
        x=x/2;
    }
    return r;
}
ll mul(ll a,ll b){
    ll t=(a*b);
    if(t>=p)t%=p;
    return t;
}
int main() {
   
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T=1;
    // cin>>T;
    while(T--){
        ll n,k;cin>>n>>k;
        ll dp[k+1];
        ll ans=0;
        for(ll i=k;i>=1;i--){
            ll u=k/i;
            dp[i]=power(u,n);
            // cout
            for(ll j=2*i;j<=k;j=j+i){
                dp[i]=sub(dp[i],dp[j]);
            }
            ans=add(ans,mul(i,dp[i]));
            // cout<<dp[i]<<endl;
        }
        cout<<ans;
    }   
    timecalculater();
    return 0;   
} 


Measured memory_bytes: 4364
c = [tuple(map(int, input().split(" "))) for i in range(3)]

c_rotated = zip(*c)
c_rotated = [[n-min(v_line) for n in v_line] for v_line in c_rotated]
c = zip(*c_rotated[::-1])
c = [[n-min(line) for n in line] for line in c]
print("No" if any([any(c_i) for c_i in c]) else "Yes")

Measured memory_bytes: 3064
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		
		long ans = 100;
		for(long i=1; i*i<=N; i++) {
			if(N%i==0) {
				ans = Math.min(ans, getDigits(N/i));
			}
		}
		
		System.out.println(ans);
		sc.close();
	}
	
	static int getDigits(long x) {
		int ans = 0;
		while(x>0) {
			x /= 10;
			ans++;
		}
		return ans;
	}
}


Measured memory_bytes: 21844
//#define _USE_MATH_DEFINES
//#pragma comment(linker, "/stack:200000000")
//#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;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
#define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
inline int safe_mul(const int x, const int y) __attribute__ ((warn_unused_result));


int const maxn = 1000005;
int sum[maxn];

int main()
{
//    freopen("in.txt","r", stdin);
//    freopen("out.txt", "w", stdout);
//    cin.tie(0);
//    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false);
    cin.tie(0);


    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;

    for(int i = 1; i < n; ++i) {
        if (s[i] == 'C' && s[i - 1] == 'A')
            sum[i] = 1;
        sum[i] += sum[i - 1];
    }

    while (q--) {
        int l,r;
        cin >> l >> r;
        --r, --l;
        cout << sum[r] - sum[l] << '\n';
    }

}


Measured memory_bytes: 1488
import java.util.*;
public class Main{

     public static void main(String []args){
        
        Scanner sc=new Scanner(System.in);
        int x=sc.nextInt();
        int y=sc.nextInt();
        int temp=y;
        if(y%2==0 && y>=(x*2))
        {
            
            if(y<=x*4)
            System.out.print("Yes");
            else
            System.out.print("No");
        }
else
      System.out.print("No");   
     }
}

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

signed main(){
  lint N; cin >> N;
  vector<lint> a(N);
  for(lint i = 0; i < N; i++) cin >> a[i];
  lint ans = 0, sum = 0, right = 0;
  for(lint left = 0; left < N; left++){
    while(sum + a[right] == (sum ^ a[right])&& right < N){
      sum += a[right];
      right++;
    }
    ans += right - left;
    if(right == left) right++;
    else sum -= a[left];
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    cnt = min(K, i)
    for j in range(cnt):
        compare.append(dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = min(compare)

print(dp[-1])


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

int zero = 0;
int two = 0;
int four = 0;
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		if (a % 4 == 0)four++;
		else if (a % 2 == 0)two++;
		else zero++;
	}
	if (zero > four) {
		if (zero == four +1 && zero+four==n) {
			printf("Yes");
		}
		else {
			printf("No");
		}
	}
	else {
		printf("Yes");
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAXN 100010
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long
#define in_range(x, y, n) (x >= 0 and x<n and y >=0 and y<n)
using namespace std;
const int mod = 1e9 + 7;

int main (){
    int n;
    cin >> n;
    vector<int> v(n);

    for (int i=0; i<n; i++){
        cin >> v[i];
    }
    int ans = 0;
    for (int i=1; i<n-1; i++){
        if (v[i] != max(v[i], max(v[i-1], v[i+1])) and v[i] != min(v[i], min(v[i-1], v[i+1]))) ans++;
    }
    cout << ans << endl;
    return 0;
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 200001
#define maxa 2000005
#define MOD  998244353 //1000000007
#define INF 1000000000000000000

using namespace std;

#define int int64_t
#define ll long long
#define pii pair<ll, ll>
#define piii pair<pii, ll>
#define ft first
#define sd second
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n-1; i >= 0; i--)
#define mem(a, b) memset(a, b, sizeof(a))
#define all(v) v.begin(), v.end()
#define edge(v, x, y) v[x].pb(y); v[y].pb(x);
#define popcount __builtin_popcount

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout << setprecision(10) << fixed;
}
ll ceil(ll a, ll b){ return (a+ b-1)/b; }
void flaged(bool flag){
    if(flag) cout << "Yes\n";
    else cout << "No\n";
}
// power and modulo inverse
ll power(ll a, ll b = MOD-2){
    if(b == 0) return 1;
    ll r = power(a, b/2);
    r = (r*r)%MOD;
    if(b%2 == 1) r = (r*a)%MOD;
    return r;
}
// factorial
ll fact[maxa], finv[maxa];
void calf(){
    fact[0] = finv[0] = 1;
    for(ll i = 1; i < maxa; i++){fact[i] = (fact[i-1]*i) %MOD;finv[i] = (finv[i-1]*power(i))%MOD;}
}
// nCr
ll ncr(ll N, ll R){ if(R > N) return 0; return (fact[N]*((finv[R]*finv[N-R])%MOD))%MOD;}

ll n, k, a[maxn];

void solve(){
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    sort(a, a+n);
    ll l = -INF, r = INF;
    while(l+1!=r){
        ll md = (l+r)/2;
        ll sum = 0;
        rep(i, n){
            if(a[i] < 0){
                ll l1 = i, r1 = n;
                while(l1+1 != r1){
                    ll md1 = (l1+r1)/2;
                    if(a[md1]*a[i] <= md){
                        r1 = md1;
                    }
                    else l1 = md1;
                }
                sum += n-r1;
            }
            else{
                ll l1 = i, r1 = n;
                while(l1+1 != r1){
                    ll md1 = (l1+r1)/2;
                    if(a[md1]*a[i] <= md){
                        l1 = md1;
                    }
                    else r1 = md1;
                }
                sum += l1-i;
            }

        }
        if(sum < k) l = md;
        else r = md;
    }
    cout << r << " ";
}

main(){
    ll t = 1; //cin >> t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 1792
array_size = gets(chomp:true).to_i
  array = gets.split.map(&:to_i)

  swap_count = 0

  # 一番左を交換値に設定、ループ毎に右に一つ交換値をずらす
  (0...array_size).each do | left_fixed |

    # 交換値を最小値として仮定
    min_num_idx = left_fixed

    # 交換値から配列の最後までを検索値に設定
    (left_fixed...array_size).each do | sch_num_idx |

      # 仮定最小値が検索値よりも大きければ
      if array[ min_num_idx ] > array[ sch_num_idx ]

        # 仮定最小値に検索値を代入
        min_num_idx = sch_num_idx
      end
    end

    # 交換値と最小値が同じでない場合に交換
    unless array[ min_num_idx ] == array[ left_fixed ]
      array[ left_fixed ], array[ min_num_idx ] = array[ min_num_idx ], array[ left_fixed ]
      swap_count += 1
    end
  end

  puts array.join(" ")
  puts swap_count



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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;
const double eps = 1e-9;

int N, L;
vint s, t, u;

double check2(double l, double mb) {
  static const double E = 86400;
  int pt = 0;
  rep(i, N) {
    l = min((double)L, l+mb*(s[i]-pt));
    l = min((double)L, l+(mb-u[i])*(t[i]-s[i]));
    if(l < 0) return -DBL_MAX;
    pt = t[i];
  }
  return min((double)L, l+mb*(E-pt));
}

bool check(double mb) {
  double l = check2(L, mb);
  if(l == -DBL_MAX) return false;
  double r = check2(l, mb);
  if(r == -DBL_MAX) return false;
  if(fabs(l-r) < eps) return true;
  return false;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(cin >> N >> L, N || L) {
    resz(s, N);
    resz(t, N);
    resz(u, N);
    rep(i, N) cin >> s[i] >> t[i] >> u[i];
    double lb = 0, ub = 1000000;
    rep(i, 100) {
      double mb = (lb+ub)/2;
      if(check(mb)) ub = mb;
      else lb = mb;
    }
    cout << ub << endl;
  }

  return 0;
}

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

typedef long long lli;
typedef vector<int> Vi;
typedef vector<lli> Vl;
typedef pair<int, int> Pii;
typedef pair<lli, lli> Pll;


//===

template <typename WT>
class UnionFind {
private:
	Vl par;
	Vl rank;
	vector<WT> diff_weight;
public:
	UnionFind(lli n, WT SUM_UNITY = 0) : par(n), rank(n, 1), diff_weight(n, SUM_UNITY) {
		for (lli i = 0; i < n; ++i) par[i] = i;
	}

	lli root(lli x) {
		if (par[x] == x) return x;
		else {
			lli r = root(par[x]);
			diff_weight[x] += diff_weight[par[x]];
			return par[x] = r;
		}
	}

	bool unite(lli x, lli y, WT w) {
		w += weight(x) - weight(y);
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) {
			swap(x, y);
			w = -w;
		}
		if (rank[x] == rank[y]) ++rank[x];
		par[y] = x;
		diff_weight[y] = w;
		return true;
	}

	bool issame(lli x, lli y) {
		return root(x) == root(y);
	}

	lli size(lli x) {
		return rank[x];
	}

	WT weight(lli x) {
		root(x);
		return diff_weight[x];
	}

	WT diff(lli x, lli y) {
		return weight(y) - weight(x);
	}
};


int main() {
	int N;
	cin >> N;
	
	UnionFind<lli> uf(N);
	for (int i = 0; i < N - 1; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		uf.unite(--u, --v, w);
	}

	Vi colors(N);
	for (int i = 0; i < N; ++i) {
		if (uf.diff(0, i) % 2 != 0) {
			colors[i] = 1;
		}
	}

	for (const auto& val : colors) {
		cout << val << endl;
	}
}

Measured memory_bytes: 3200
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

vector< ll > divisor(ll n)
{
    vector< ll > ret;
    for(ll i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(i * i != n) ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return(ret);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> v = divisor((ll)m);
    sort(v.begin(), v.end());
    ll ans = 1;
    for (auto &&i : v) {
        if(n <= m/i) ans = max(ans, i);
    }
    cout << ans << "\n";
    return 0;
}


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


int main() {
int a,b,c,d;
cin >> a>> b >> c >>d;
int ansa,ansb;
if (c%b==0) ansa=c/b;
else ansa = c/b+1;
if(a%d==0) ansb = a/d;
else ansb = a/d+1;
if (ansa<=ansb) cout <<"Yes" <<endl;
else cout <<"No"<<endl;
}

Measured memory_bytes: 3544
n, m = gets.strip.split.map(&:to_i)
lrd = readlines.map {|line| line.split.map(&:to_i) }

graph = Array.new(n+1) { [] }
lrd.each do |l, r, d|
  graph[l] << [r, d]
  graph[r] << [l, -d]
end

check = Array.new(n+1)

def bfs(start, check, graph)
  check[start]=0
  queue = [start]

  until queue.empty?
    current_start = queue.shift
    graph[current_start].each do |goal, cost|
      if check[goal].nil?
        check[goal] = check[current_start] + cost
        queue << goal
      else
        return false if check[goal] != check[current_start] + cost
      end
    end
  end

  return true
end

if (1..n).all? {|number| check[number] || bfs(number, check, graph) } 
  puts 'Yes'
else
  puts 'No'
end


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

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

  int n, k, t, u, v, l;
  cin >> n >> k >> t >> u >> v >> l;
  VI d(n);
  VI car(l+5, 0);
  REP(i, n) cin >> d[i], car[d[i]] = 1;

  int pos = -1, c = 0;
  double res = 0;
  REP(i, l) {
    // cout << i << " " << res << " " << pos << " " << c << endl;
    // にんじんがある場所なら
    if(car[i]) {
      // 使ってる
      if(i <= pos) {
        // 使う
        if(c == k) {
          pos = i + v*t - 1;
        }
        // 使わない
        else {
          c++;
        }
      }
      // 使ってない
      else {
        // 使う
        pos = i + v*t - 1;
      }
    }

    if(i > pos && c > 0) {
      pos = i + v*t - 1;
      c--;
    }

    // 使ってるなら
    if(i <= pos) {
      // cout << "used" << endl;
      res += 1.0/v;
    }
    // 使ってないなら
    else {
      res += 1.0/u;
    }
  }

  cout << fixed << setprecision(9) << res << endl;

  return 0;
}



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

string first, second;
char hashT[30];

int intOf ( char x ) {
  return x - 'a';
}

int main () {

//  ifstream iff ( stdin, ifstream::in );
//  ofstream off ( stdout, ofstream::out );
  cin >> first >> second;

  memset ( hashT, 0, sizeof hashT );

  bool flag = true;
  int sz = first.size();
  for ( int i = 0; i < sz; ++i ) {
    if ( !hashT[ intOf(first[i]) ] )
      hashT[ intOf(first[i]) ] = intOf(second[i]) ;
    if ( hashT[ intOf(first[i]) ] != intOf(second[i])  )
      flag = false;
  }

  for ( int i = 0; i < 26; ++i )
    for ( int h = i+1; h < 26; ++h )
      if ( hashT[i] != 0 and hashT[h] != 0 and
          hashT[i] == hashT[h] )
        flag = false;

  cout << ( flag? "Yes" : "No" );

  return 0;
}


Measured memory_bytes: 776
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
// #define int ll
using namespace std;
const int INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const int MOD = 1000000007;
const int MAX = 510000;
const double pi = acos(-1);
const double eps = 1e-9;

bool compare(pll a, pll b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n,m;
    pll x[100010];
    ll cnt[100010];
    ll cntm[200010];
    cin>>n>>m;
    rep(i,n){
        ll X;
        cin>>X;
        x[i]=pll(X%m,X);
        cntm[X%m]++;
    }
    sort(x,x+n,compare);
    ll now=1;
    rep(i,n-1){
        if(x[i].sc==x[i+1].sc) now++;
        else {
            cnt[x[i].fi]+=now/2;
            now=1;
        }
    }
    if(now!=1) cnt[x[n-1].fi]+=now/2;
    ll ans=0;
    rep(i,m/2+1){
        if(i==0||(m%2==0&&i==m/2)){
            ans+=cntm[i]/2;
        }
        else {
            ll a=cntm[i],A=cnt[i];
            ll b=cntm[m-i],B=cnt[m-i];
            ll s=min(a,b),t=max(a,b);
            if(a-b<=1&&a-b>=0){
                ans+=s;
            }
            else if(a-b>1){
                ans+=s;
                if((a-s)/2<=A){
                    ans+=(a-s)/2;
                }
                else{
                    ans+=A;
                }
            }
            else if(b-a<=1){
                ans+=s;
            }
            else if(b-a>1){
                ans+=s;
                if((b-s)/2<=B){
                    ans+=(b-s)/2;
                }
                else{
                    ans+=B;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int64_t mod = 1000000007;

int main()
{
    int N;
    cin >> N;
    vector<int> list(N);
    for (int i = 0; i < N; i++)
        cin >> list[i];
    int ans = 0, count = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (list[i + 1] <= list[i])//移動可能
            count++;
        else
            count = 0;
        ans = max(ans, count);
    }
    cout << ans;
}

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

using namespace std;

int n, q;
vector<int> adjList[212123];
long long v[212123];
bool seen[212123];

void dfs(int x) {
	seen[x] = true;
	for (int y : adjList[x]) {
		if (seen[y]) continue;
		v[y] += v[x]; 
		dfs(y);
	}
}

int main() {
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		adjList[x].push_back(y);
		adjList[y].push_back(x);
	}
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		v[x] += y;
	}
	dfs(1);
	for (int i = 1; i <= n; i++) {
		cout << v[i] << '\n';
	}
	return 0;
}


Measured memory_bytes: 21632