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

using namespace std;

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

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  each(x,vec) is >> x;
  return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  rep(i,vec.size()) {
    if (i) os << " ";
    os << vec[i];
  }
  return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
  rep(i,vec.size()) {
    if (i) os << endl;
    os << vec[i];
  }
  return os;
}

class Segtree {
  struct Node {
    Node *lch, *rch;
    long long sum;
    Node() : sum(0), lch(nullptr), rch(nullptr) {}
    ~Node() {
      // if (lch != nullptr) delete lch;
      // if (rch != nullptr) delete rch;
    }
    void add(ll x, ll val, ll lb, ll ub) {
      if (x >= ub) return;
      Node* node = this;
      while (ub - lb > 1) {
        node->sum += val;
        ll mid = (lb + ub) / 2;
        if (x < mid) {
          if (node->lch == nullptr) node->lch = new Node();
          node = node->lch;
          ub = mid;
        }
        else {
          if (node->rch == nullptr) node->rch = new Node();
          node = node->rch;
          lb = mid;
        }
      }
      node->sum += val;
    }
    long long find(ll r, ll lb, ll ub) {
      long long res = 0;
      Node* node = this;
      while (node != nullptr) {
        ll mid = (lb + ub) / 2;
        if (ub == r) {
          res += node->sum;
          break;
        }
        else if (r < mid) {
          ub = mid;
          node = node->lch;
        }
        else {
          if (node->lch != nullptr) res += node->lch->sum;
          lb = mid;
          node = node->rch;
        }
      }
      return res;
    }
  };
  Node *root;
  const ll n;
public:
  Segtree() : Segtree(0) {}
  Segtree(ll n) : root(new Node()), n(n) {}
  void add(ll x, ll val) {
    root->add(x, val, 0, n);
  }
  long long find(ll r) {
    return root->find(r, 0, n);
  }
  ~Segtree() { delete root; }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, Q; cin >> n >> Q;
  Segtree seg(n);
  rep(q, Q) {
    ll t, x, y; cin >> t >> x >> y; --x;
    if (t == 0) seg.add(x, y);
    else cout << seg.find(y) - seg.find(x) << endl;
  }
}



Measured memory_bytes: 6896
//coded by not_surrender

#pragma GCC optimize( "Ofast" )

#include <bits/stdc++.h>

#define MAXN 3010
#define oo (1<<30)
#define MOD 1000000007
#define mid ((a+b)/2)
#define L (nod*2)
#define R (nod*2+1)
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector <int> vi;

ll N, A[MAXN], dp[MAXN][MAXN][2];

bool mk[MAXN][MAXN];

void solve( int a, int b, int turn ){
	mk[a][b] = true;
	if ( a == b ){
		dp[a][b][turn] += A[a];
		return;
	}	
	if ( !mk[a+1][b] )
		solve( a+1, b, turn^1 );
	if ( !mk[a][b-1] )
		solve( a, b-1, turn^1 );
	if ( turn ){
		if ( (dp[a+1][b][turn]+A[a])-dp[a+1][b][turn^1] > (dp[a][b-1][turn]+A[b])-dp[a][b-1][turn^1] )
			dp[a][b][turn] = dp[a+1][b][turn]+A[a], dp[a][b][turn^1] = dp[a+1][b][turn^1];
		else
			dp[a][b][turn] = dp[a][b-1][turn]+A[b], dp[a][b][turn^1] = dp[a][b-1][turn^1];	
	}
	else {
		if ( dp[a+1][b][turn^1]-(dp[a+1][b][turn]+A[a]) < dp[a][b-1][turn^1]-(dp[a][b-1][turn]+A[b]) )
			dp[a][b][turn] = dp[a+1][b][turn]+A[a], dp[a][b][turn^1] = dp[a+1][b][turn^1];
		else
			dp[a][b][turn] = dp[a][b-1][turn]+A[b], dp[a][b][turn^1] = dp[a][b-1][turn^1];	
	}
}

int main(){

    #ifndef ONLINE_JUDGE
        //~ freopen( "a.txt", "r", stdin );
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio( false );
    cin.tie( NULL ), cout.tie( NULL );
    
    cin >> N;
    
    for ( int i = 1; i <= N; ++i )
		cin >> A[i];
	
	solve( 1, N, 0 );
	
	cout << dp[1][N][0]-dp[1][N][1] << '\n';
	
return 0;
}


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

int main() {
    while(1) {
        double H,W;
        cin >> H >> W;
        if(H == 0 && W == 0) break;
        if(ceil(H/2) == floor(H/2)) {
            if(ceil(W/2) == floor(W/2)) {
                for(int a = 0; a < H/2; ++a) {
                    for(int b = 0; b < W/2; ++b) {
                        printf("#.");
                    }
                    printf("\n");
                    for(int c = 0; c < W/2; ++c) {
                        printf(".#");
                    }
                    printf("\n");
                }
                printf("\n");
            }else {
                for(int a = 0; a < H/2; ++a) {
                    for(int b = 0; b < floor(W/2); ++b) {
                        printf("#.");
                    }
                    printf("#\n");
                    for(int c = 0; c <floor(W/2); ++c) {
                        printf(".#");
                    }
                    printf(".\n");
                }
                printf("\n");
            }
        }else{
            if(ceil(W/2) == floor(W/2)) {
                for(int a = 0; a < floor(H/2); ++a) {
                    for(int b = 0; b < W/2; ++b) {
                        printf("#.");
                    }
                    printf("\n");
                    for(int c = 0; c < W/2; ++c) {
                        printf(".#");
                    }
                    printf("\n");
                }
                for(int d = 0; d < W/2; ++d) {
                        printf("#.");
                }
                printf("\n\n");
            }else {
                for(int a = 0; a < floor(H/2); ++a) {
                    for(int b = 0; b < floor(W/2); ++b) {
                        printf("#.");
                    }
                    printf("#\n");
                    for(int c = 0; c <floor(W/2); ++c) {
                        printf(".#");
                    }
                    printf(".\n");
                }
                for(int d = 0; d < floor(W/2); ++d) {
                    printf("#.");
                }
                printf("#\n\n");
            }
        }
    }
}

Measured memory_bytes: 3204
#include<bits/stdc++.h>
using namespace std;
int N;
int W[305];
int dp[305][305];
int main()
{
	while(true){
		scanf("%d",&N);
		if(N==0){break;}
		for(int i=0;i<N;i++){
			scanf("%d",&W[i]);
		}
		for(int i=0;i<305;i++){
			for(int j=0;j<305;j++){
				dp[i][j]=0;
			}
		}
		for(int i=0;i<=N-2;i++){
			if(abs(W[i]-W[i+1])<=1){dp[i][2]=2;}
		}
		for(int j=3;j<=N;j++){
			for(int i=0;i+j<=N;i++){
				//[i,i+j)
				for(int k=0;k<=j;k++){
					dp[i][j]=max(dp[i][k]+dp[i+k][j-k],dp[i][j]);
				}
				if(abs(W[i]-W[i+j-1])<=1&&dp[i+1][j-2]==j-2){
					dp[i][j]=max(dp[i][j],dp[i+1][j-2]+2);
				}
			}
		}
		/*
		for(int j=0;j<12;j++){
			for(int i=0;i+j<=12;i++){
				printf("%d ",dp[i][j]);
			}
			printf("\n");
		}*/
		/*
		for(int i=150;i>=0;i-=2){
		printf("%d\n",dp[i][299-i]);
		}*/
		printf("%d\n",dp[0][N]);
	}
	return 0;
}



Measured memory_bytes: 3564
#include<bits/stdc++.h>
#define N 300
using namespace std;
int n,l,r,a,ans;
signed main()
{
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++)
        cin>>a,ans+=(a<l or a>=r);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    cin >> N >> K;
    if (K == 1){
        cout << 0 <<"\n";
    }else{
        cout << N-K <<"\n";
    }
}

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

int main(){
    int X, Y, Z, K;

    cin >> X >> Y;

    if(X > Y){
        if(X-1 > Y) cout << X+X-1 << endl;
        else cout << X+Y << endl;
    }
    else{
        if(Y-1 > X) cout << Y+Y-1;
        else cout << X+Y << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
char s,c;
int t=1;
int main(){
    int n;
    scanf("%d\n",&n);
    for(int i=0;i<n;i++){
        scanf("%c",&c);
        if(!i)s=c;
        else if(s!=c){
            s=c;
            t++;
        }
    }
    printf("%d",t);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = sz(s);
    vi cnt(3, 0);
    rep(i, n) cnt[s[i] - 'a']++;
    int mn = 1001001001;
    rep(i, 3) chmin(mn, cnt[i]);
    rep(i, 3) cnt[i] -= mn;
    bool flag = true;
    rep(i, 3) {
        if (cnt[i] >= 2) flag = false;
    }
    cout << (flag ? "YES" : "NO") << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(){
int a[11],b,c=0,d=0,i,j,f;
char e;
while(1){
scanf("%d\n",&b);
if(b==0){
break;
}
for(i=0;i<10;i++){
a[i]=0;
}
for(i=0;i<100;i++){
scanf("%c",&e);
if(e=='S'){
c=c+a[d]+1;
a[d]=0;
}
else if(e=='L'){
a[d]=a[d]+c+1;
c=0;
}
else{
a[d]++;
}
d++;
if(d==b){
d=0;
}
}
scanf("\n");
for(i=0;i<b;i++){
for(j=b-1;j>i;j--){
if(a[j-1]>a[j]){
f=a[j];
a[j]=a[j-1];
a[j-1]=f;
}
}
}
for(i=0;i<b;i++){
printf("%d ",a[i]);
}
printf("%d\n",c);
c=0,d=0;
}
return 0;
}



Measured memory_bytes: 2052
#include<cstdio>
#include<cstring>
using namespace std;
bool b[30];
char s[30];
int l,i;
int main()
{
	scanf("%s",s);
	l=strlen(s);
	for (i=0;i<l;i++)
	{
	  if (b[s[i]-'a']) 
	  {
	  	printf("no\n");
	  	return 0;
	  }
	  else
	  {
	  	b[s[i]-'a']=1;
	  }
    }
	printf("yes\n");
}

Measured memory_bytes: 128
points = {}
n = int(input())
for _ in range(n):
    s = input()
    points.setdefault(s, 0)
    points[s] += 1
m = int(input())
for _ in range(m):
    s = input()
    points.setdefault(s, 0)
    points[s] -= 1
print(max(0, max(points.values())))

Measured memory_bytes: 9056
#include <bits/stdc++.h>
using namespace std;
int main(){
 long n;
 int cnt = 0;
 cin >> n;
 int cnt2 = 0;
 vector<pair<long,long>> v(0);
 for(long i=2;i*i<n;i++){
    while(n%i == 0){
        cnt++;
        n = n/i;
    }
     if(cnt!=0)v.push_back(make_pair(i,cnt));
     cnt = 0;
 }
 if(n!=1)v.push_back(make_pair(n,1));
     for(int i=0;i<v.size();i++){
        for(int j=0;j<1000;j++){
            if(j*(j+1)/2 > v[i].second){
                cnt2+=j-1;
                break;
            }
        }
     }
 
 cout << cnt2  << endl;
 }

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x)  (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
int main() {
    ios::sync_with_stdio(false);
    LL n;
    cin >> n;
    cout << (1ll * (1 + n - 1))*(n - 1) / 2;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    if ((a == 1) && (b == 2)){
        cout << 3;
    }
    else if ((a == 2) && (b == 1)){
        cout << 3;
    }
    else if ((a == 1) && (b == 3)){
        cout << 2;
    }
    else if ((a == 3) && (b == 1)){
        cout << 2;
    }
    else if ((a == 2) && (b == 3)){
        cout << 1;
    }
    else{
        cout << 1;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 3e3 + 5;
const int mod = 998244353;
int n, s, a[M], dp[M][M], inv2, pown;

int power(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)	
			res = (res * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return res % mod;
}

int modInv(int a)
{
	return power(a, mod - 2);
}

int solve(int i, int sum)
{
	if(sum > s)	return 0;

	if(i == n)
	{
		if(sum == s)	return pown;	// 2^n
		return 0;
	}

	if(dp[i][sum] != -1)	return dp[i][sum];

	int ans = solve(i + 1, sum);
	ans += inv2 * solve(i + 1, sum + a[i]);
	ans %= mod;

	return dp[i][sum] = ans;
}
 
int32_t main() 
{
	ios_base::sync_with_stdio(0);	cin.tie(0);	cout.tie(0);
	cin >> n >> s;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	memset(dp, -1, sizeof dp);
	inv2 = modInv(2);
	pown = power(2, n);
	cout << solve(0, 0);
    	return 0;
}

Measured memory_bytes: 74408
#include <iostream>
#include <climits>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#define MAX 1000000007


using namespace std;
#define ll long long
#define dbg if(0)
#define ISRANGE(val,lo,hi) ((lo<=val)&&(val<hi))



int main(){
    ll ans,n,k,x,y;
    cin >>n>>k>>x>>y;

    ans=min(n,k)*x+max(n-k,(ll)0)*y;


    cout <<ans<<endl;

    return 0;

}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():
    t,=pin()
    print(1000*(t//500)+5*((t%500)//5))
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じ,るの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """1024"""
        output = """2020"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1000000000"""
        output = """2000000000"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 5820
d = input()
if int(d[:4]) > 2019:
    print('TBD')
elif int(d[:4]) == 2019:
    if int(d[5:7]) > 4:
        print('TBD')
    elif int(d[5:7]) == 4:
        if int(d[-2:]) > 30:
            print('TBD')
        else:
            print('Heisei')
    else:
        print('Heisei')
else:
    print('Heisei')

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>
#include <unordered_set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define MAX(x,y) ((x)<(y)?(y):(x))

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

#define INF 1000000000

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

ll twoRow(ll a, ll b, ll mod)
{
	ll ret = 1;
	for(ll i = 1 ;i <= a+b;++i)
	{
		ret *= i;
		ret %= mod;
	}
	for(ll i = 1 ;i <= a;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	for(ll i = 1 ;i <= b;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	return ret;
}

struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};

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(ret.begin(), ret.end());
  return (ret);
}
/*
for(i=0;i<N;++i)
{
	
}
*/
int main()
{
	ll i,j,k;
	ll N,M,K;
	string S;
	ll H,W,A,B;
	cin >>N>>K;
	set<int> st;
	queue<int> q;
	int ans = 0;
	int stair_num = 0;
	int last = 0;
	int nn = 0;
	for(i=0;i<K;++i)
	{
		cin >> j;
		st.insert(j);
		q.push(j);
		if(j<last)
			stair_num++;
		last=j;
	}
	if(N==K)
	{
		cout << 1 << endl;
	}
	else
	{
		if(stair_num==0)
			nn++;
		auto pos = st.begin();
		int f;
		for(i=0;i<N-K;++i)
		{
			int ans_up = 0;
			cin >> j;
			st.insert(j);
			k=*(st.rbegin());
			f = q.front();
			if(j==k)
			{
				pos=st.find(f);
				if(pos==st.begin())
				{
					ans++;
					ans_up=1;
				}
			}
			else
			{
				pos=st.find(f);
			}
			q.pop();
			q.push(j);
			st.erase(pos);
			if(j<last)
				stair_num++;
			if(f>q.front())
				stair_num--;
			if(stair_num==0)
			{
				nn++;
				if(ans_up)
					ans--;
			}
			last = j;
		}
		cout << N-K+1-ans-(nn>0?nn-1:0) << endl;
	}

	return 0;
}




















Measured memory_bytes: 10496
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long int a, b, k; cin >> a >> b >> k;
	if(b-a+1<k*2){
		for(int i=a;i<=b;i++){
			cout << i << endl;
		}
		return 0;
	}
	if(b-a+1>=2*k){
		for(int i=a;i<a+k;i++){
			cout << i << endl;
		}
		for(int i=b-k+1;i<=b;i++){
			cout << i << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define fcout(n) cout << fixed << setprecision(n)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acosl(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<PII>;
using VTIII = vector<TIII>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> inline bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a == b)){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a == b)){ a=b; return true; } return false; }


int n, m;
int c[30];
int dp[50010];


signed main(){
    cin >> n >> m;
    rep(i, 0, m) cin >> c[i];

    fill(dp, dp+n+1, INF32);
    dp[0] = 0;
    repe(i, 0, n) rep(j, 0, m) chmin(dp[min(i+c[j], n+1)], dp[i]+1);

    cout << dp[n] << endl;

    return 0;
}


Measured memory_bytes: 3492
class ModCalc:
    mod = 10**9 + 7

    def __init__(self, n):
        self.n = n
        self.inv = [1] * (self.n + 1)
        self.fac = [1] * (self.n + 1)
        self.finv = [1] * (self.n + 1)
        self.inv[0] = 0
        self.inv_table()

    def inv_table(self):
        for i in range(2, self.n+1):
            self.inv[i] = self.inv[self.mod % i] * (self.mod - self.mod // i) % self.mod
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def comb(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * self.finv[r] % self.mod * self.finv[n-r] % self.mod

    def perm(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * self.finv[n-r] % self.mod

    def fact(self, n):
        return self.fac[n]


s = int(input())
mc = ModCalc(s+6)
mod = 10**9 + 7
y = s//3

ans = 0
for i in range(1, y+1):
    x = mc.comb(s - i * 3 + i - 1, i-1)
    ans += x
    ans %= mod

print(ans)

Measured memory_bytes: 64700
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

string S;

signed main(){
	cin >> S;
	if(S.size() >= 4 && S.substr(0, 4) == "YAKI") cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n;
int a[MAXN], dp[MAXN];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], dp[i] = inf;
    dp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (i - 1 > 0)
            dp[i] = min(dp[i], dp[i - 1] + abs(a[i] - a[i - 1]));
        if (i - 2 > 0)
            dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - a[i - 2]));
    }
    cout << dp[n];
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n;
    cin>>n;
    string s[n];
    rep(i,n)cin>>s[i];
    vector<pair<int,int>> p(n);
    rep(i,n){
        rep(j,s[i].size()){
            if(s[i][j]=='(')++p[i].first;
            else --p[i].first;
            p[i].second=min(p[i].second,p[i].first);
        }
    }
    sort(p.begin(),p.end(),[](auto x,auto y){
        return x.first-x.second > y.first - y.second;
    });
    vector<int> used(n);
    int cur=0;
    rep(_,n){
        bool ok=false;
        rep(i,n){
            if(p[i].second+cur>=0&&!used[i]){
                used[i]=true;
                cur+=p[i].first;
                ok=true;
                break;
            }
        }
        if(!ok){
            cout<<"No"<<endl;
            return 0;
        }
    }
    if(cur!=0){
        cout<<"No"<<endl;
    }
    else cout<<"Yes"<<endl;
    return 0;
}


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

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int N, M;
    cin >> N >> M;
    map<ll, int> Amap;
    vector<pair<ll, int>> cnt;

    rep(i, N)
    {
        ll a;
        cin >> a;
        Amap[a]++;
    }
    for (auto p : Amap) {
        cnt.push_back(make_pair(p.first, p.second));
    }
    rep(i, M)
    {
        ll b;
        int c;
        cin >> b >> c;
        cnt.push_back(make_pair(c, b));
    }
    sort(cnt.rbegin(), cnt.rend());
    int num = 0;
    ll ans = 0;
    for (int i = 0; i < cnt.size(); i++) {
        ans += cnt[i].first * cnt[i].second;
        num += cnt[i].second;
        if (num >= N) {
            ans -= cnt[i].first * (num - N);
            break;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 13624
import java.util.*;
import java.io.*;

import static java.lang.Character.isUpperCase;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int X =  in.nextInt();
        int Y =  in.nextInt();
        int Z =  in.nextInt();


        int t=0;

        t=X;
        X=Y;
        Y=t;
        t=X;
        X=Z;
        Z=t;
        System.out.println(X);
        System.out.println(Y);
        System.out.println(Z);

 }

    }


    







Measured memory_bytes: 35432
# AOJ 0070 Combination of Number Sequences
# Python3 2018.6.17 bal4u

vmin = [ 0, 0,  1,  4, 10,  20,  35,  56,  84, 120, 165 ]
vmax = [ 0, 9, 26, 50, 80, 115, 154, 196, 240, 285, 330 ]
lim = [ 0, 4, 13, 27, 45,  67,  94, 126, 162, 202, 247 ]
tbl = [ [ 0 ], \
	[ 1, 1, 1, 1, 1 ], \
	[ 1, 2, 1, 3, 3, 3, 4, 5, 4, 5, 5, 4, 5 ], \
	[ 1, 3, 2, 6, 5, 6, 8, 13, 8, 16, 14, 14, 16, 23, 15, 26, 22, 21, 24, 30, 19, 31, 26, 22 ], \
	[ 1, 4, 4, 9, 11, 14, 16, 25, 20, 32, 29, 38, 38, 56, 45, 70, 61, 74, 69, 92, 71, 103, 88, \
	105, 100, 136, 98, 131, 113, 131, 119, 150, 118, 150, 119, 160 ], \
	[ 1, 5, 7, 13, 22, 25, 32, 49, 52, 62, 76, 88, 91, 119, 114, 146, 160, 170, 172, 231, 223, \
	249, 269, 298, 297, 372, 326, 375, 404, 407, 424, 484, 464, 481, 514, 553, 533, 581, 554, 589, 653, \
	597, 601, 657, 630, 647, 660, 643 ], \
	[ 1, 6, 11, 19, 38, 44, 62, 88, 106, 124, 170, 188, 221, 271, 276, 323, 397, 395, 438, 533, \
	544, 568, 687, 694, 769, 861, 893, 942, 1114, 1078, 1180, 1293, 1342, 1351, 1574, 1491, 1640, 1748, \
	1775, 1764, 2029, 1920, 2026, 2162, 2178, 2191, 2430, 2292, 2383, 2552, 2488, 2488, 2709, 2583, 2598, \
	2777, 2618, 2659, 2841, 2657 ], \
	[ 1, 7, 16, 28, 59, 75, 109, 151, 206, 234, 335, 360, 467, 529, 630, 675, 896, 878, 1053, \
	1141, 1340, 1294, 1632, 1571, 1895, 1896, 2184, 2129, 2632, 2485, 2926, 2909, 3356, 3190, 3911, \
	3583, 4259, 4158, 4663, 4477, 5370, 4886, 5622, 5475, 6171, 5776, 6772, 6186, 7073, 6776, 7435, \
	6953, 8178, 7344, 8270, 7927, 8551, 8030, 9184, 8285, 9227, 8758, 9408, 8650, 9937, 8868, 9716, \
	9281, 9870, 9035, 10092 ], \
	[ 1, 8, 22, 40, 83, 122, 173, 248, 350, 408, 575, 669, 842, 963, 1211, 1264, 1652, 1767, \
	2083, 2248, 2752, 2671, 3274, 3352, 3928, 3978, 4624, 4554, 5428, 5384, 6115, 6158, 7195, 6897, 8052, \
	7886, 8928, 8772, 10083, 9670, 11309, 10830, 12110, 11865, 13681, 12871, 14740, 14098, 15900, 15138, \
	17241, 15947, 18464, 17353, 19307, 18345, 20745, 18949, 21681, 20236, 22624, 21027, 23607, 21467, \
	24536, 22553, 24793, 23187, 26012, 23373, 26355, 24094, 26581, 24463, 27187, 24377, 27453, 24768, 27006 ], \
	[ 1, 9, 28, 51, 107, 177, 234, 360, 498, 619, 819, 1040, 1252, 1528, 1824, 2010, 2533, 2837, \
	3180, 3676, 4305, 4493, 5130, 5672, 6156, 6909, 7424, 7830, 8773, 9392, 9892, 10678, 11647, 12141, \
	13026, 13918, 14519, 15611, 16278, 16780, 18686, 19280, 19586, 20795, 22385, 22896, 23948, 24970, \
	26012, 27096, 28467, 28427, 30540, 31272, 31774, 33264, 34748, 34499, 36299, 36596, 38456, 38926, \
	39984, 39386, 42068, 42848, 42424, 42925, 45044, 44584, 46040, 45496, 46890, 47036, 47341, 47646, \
	48887, 48840, 48044, 48540, 50066, 48970, 49062 ] ]

while True:
	try: n, s = list(map(int, input().split()))
	except: break

	if n > 10 or s < vmin[n] or s > vmax[n]: ans = 0
	else:
		if s > lim[n]: s = vmax[n] + vmin[n] - s
		s -= vmin[n]
		if n == 10: n = 9
		ans = tbl[n][s]
	print(ans)


Measured memory_bytes: 5832
A = [int(i) for i in input().split()]
maxA = max(A)
minA = min(A)
midA = sum(A) - maxA - minA

ans = maxA - midA
diff = maxA - (minA + ans)
if diff == 1:
    ans += 2
elif diff == 2:
    ans += 1
elif diff > 2:
    ans += diff // 2
    if diff % 2 == 1:
        ans += 2
        
print(ans)    

Measured memory_bytes: 3064
import java.util.*;

// UVa 11504

public class Main {

	static int n;
	static int answer = 0;
	static int[] visited;
	static int[][] map;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		n = in.nextInt();
		map = new int[n][n];
		visited = new int[n];
		int m = in.nextInt();
		while (m-- > 0) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			
			map[a][b] = 1;
			map[b][a] = 1;
		}
		
		dfs(0);
		
		System.out.println(answer);
	}
	
	public static void dfs(int curr) {
		visited[curr] = 1;
		
		int num = 0;
		boolean allVisited = true;
		
		for (int i = 0; i < n; i++) {
			if (visited[i] == 0) {
				allVisited = false;
			}
			if (map[curr][i] == 1 && visited[i] == 0) {
				num++;
				dfs(i);
				visited[i] = 0;
			}
		}
		
		if (num == 0 && allVisited) {
			answer++;
		}
	}
}

Measured memory_bytes: 21716
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(N) for (int i = 0; i < N; i++)

int main() {
    string str;
    vector<int> number;
    int result;
    bitset<3> combination;
    cin >> str;
    for (int i = 0; i < 4; i++){
        number.push_back(str[i] - '0');
    }
    for (int i = 0; i < (1 << 3); i++){
        combination = i;
        result = number[0];
        for (int j = 0; j < 3; j++){
            if (combination[j] == 0) result += number[j+1];
            else if(combination[j] == 1) result -= number[j+1];
        }
        if (result == 7){
            cout << number[0];
            for (int j = 0; j < 3; j++){
                if (combination[j] == 0) cout << "+";
                else if(combination[j] == 1) cout << "-";
                cout << number[j+1];
            }
            cout << "=7" << endl;
            break;
        }
    }
}


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

const int M = 1000005;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<int> cnt(M);
  for (int x : a) {
    if (cnt[x] != 0) {
      cnt[x] = 2;
      continue;
    }
    for (int i = x; i < M; i += x) cnt[i]++;
  }
  int ans = 0;
  for (int x : a) {
    if (cnt[x] == 1) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8020
package main

import (
	"fmt"
)

func stringReverse(s string) string {
	l := len(s)
	cs := make([]rune, l)
	for i, c := range s {
		cs[l-i-1] = c
	}
	return string(cs)
}

func main() {
	var s string
	fmt.Scan(&s)
	if len(s) == 3 {
		s = stringReverse(s)
	}
	fmt.Println(s)
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	rep(i,n) cin >> a[i];
	sort(a.begin(), a.end());
	int ans = 0;
	rep(i,n-1){
		if(x >= a[i]){
			x -= a[i];
			++ans;
		}
		else break;
	}
	if(x == a[n-1]) ++ans;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

int main(){
    string s;
    cin >> s;

    int ans=700;

    for(int i=0;i<3;i++){
        if(s[i]=='o') ans+=100;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
package main

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

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	p := make(pairs, n)
	y := make([]int, n)
	for i := 0; i < n; i++ {
		p[i].x = scanInt()
		p[i].y = scanInt()
		y[i] = p[i].y
	}

	sort.Sort(p)
	sort.Ints(y)
	ymap := map[int]int{}
	for i := 0; i < n; i++ {
		ymap[y[i]] = i
	}

	b1 := make(BIT, n+1)
	b2 := make(BIT, n+1)
	for i := 0; i < n; i++ {
		b2.Add(i, 1)
	}

	ans := mpow(2, n-1) * n % MOD

	for i := 0; i < n; i++ {
		num := ymap[p[i].y]
		b2.Add(num, -1)
		dl := b1.Sum(num)
		dr := b2.Sum(num)
		ul := b1.Sum(n-1) - dl
		ur := b2.Sum(n-1) - dr
		b1.Add(num, 1)

		a1 := mpow(2, dl) - 1
		a2 := mpow(2, dr) - 1
		a3 := mpow(2, ul) - 1
		a4 := mpow(2, ur) - 1

		ans += a3 * a2 % MOD * (1 + a1 + a4) % MOD
		ans += a1 * a4 % MOD * (1 + a2 + a3) % MOD
		ans += a1 * a2 % MOD * a3 % MOD * a4 % MOD
		ans %= MOD

		// debug(dl, dr, ul, ur)
	}

	fmt.Fprintln(wr, ans)

}

// MOD constant
const MOD = 998244353

type pair struct {
	x, y int
}

type pairs []pair

func (a pairs) Len() int           { return len(a) }
func (a pairs) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a pairs) Less(i, j int) bool { return a[i].x < a[j].x }

// BIT type
type BIT []int

// Sum function calculates a sum to i
func (t BIT) Sum(i int) int {
	s := 0
	for i++; i > 0; i -= i & -i {
		s += t[i]
	}
	return s
}

// Add function add x to i
func (t BIT) Add(i, x int) {
	for i++; i < len(t); i += i & -i {
		t[i] += x
	}
}

func mpow(a, n int) int {
	res := 1
	for n > 0 {
		if n&1 == 1 {
			res = res * a % MOD
		}
		a = a * a % MOD
		n >>= 1
	}
	return res
}


Measured memory_bytes: 20736
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <math.h>
#include <map>
#include <stack>
using namespace std;
static const int INF = 1e9+7;
// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i =a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define PI 3.14159265359

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

    int sum=0;
    int tmp = num;
    while(tmp > 0){
       sum += (tmp % 10);
       tmp /= 10;
    }

    if(num % sum == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3536
def cmb(n,r,mod=10**9+7):
    fac=[1,1]
    for i in range(2,n+1):
        fac.append(fac[i-1]*i%mod)
    ret=fac[n]*pow(fac[r]*fac[n-r]%mod,mod-2,mod)%mod
    return ret

mod = 10**9+7
X, Y = map(int, input().split())
Z = (X+Y) // 3

if (X + Y) % 3 != 0 or abs(X-Y) > Z:
    print(0)
else:
    print(cmb(Z, X-Z))

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

const int mod = 1e9 + 7;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
#define ll long long
#define vi vector < int >
#define vll vector < ll >
#define pii pair < int , int >
#define ff first
#define tc \
    int ttt; cin >> ttt;\
    while(ttt --)
#define ss second
#define f(i,a,b) for(int i=a;i<b;i++)
#define rev(i,a,b) for(int i=a;i>=b;i--)
#define nl '\n'
#define all(x) x.begin() , x.end()
#define mne min_element
#define mxe max_element
ll gcd(ll x, ll y) {return y == 0 ? x : gcd(y, x % y);}
int logg(ll x , ll y) {if (x == 0) return -1; return logg(x / y, y) + 1;}
ll poww(ll a, ll b, ll m) {
	if (b == 0) return 1;
	ll ans = 1;
	ans = poww(a, b >> 1, m);
	ans = (ans * ans) % m;
	if (b & 1) ans = (ans * a) % m;
	return ans;
}
// Start of code
const int N = 1e5 + 5;
int dp[105][N];
int weight[105];
int val[105];
int n, w;

int solve() {

	dp[1][0] = 0;
	dp[1][val[1]] = weight[1];
	f(i, 2, n + 1) {
		f(v, 0, 100001) {
			dp[i][v] = dp[i - 1][v];
			if (val[i] > v) continue;
			dp[i][v] = min(dp[i][v], weight[i] + dp[i - 1][v - val[i]]);
		}
	}
	int ans = -1;
	f(i, 0, 1e5 + 1) if (dp[n][i] <= w) ans = max(ans, i);
	return ans;
}

int32_t main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fast;

	memset(dp, mod, sizeof dp);
	cin >> n >> w;

	f(i, 1, n + 1) cin >> weight[i] >> val[i];
	cout << solve() << nl;
}


Measured memory_bytes: 85688
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pll pair<ll,ll>
#define v vector<ll>
#define st stack<ll>
#define pq  priority_queue <int>
#define q queue<ll>
#define mod 1000000005
using namespace std;
 char ch[1000000];
int main(){
    string s="CODEFESTIVAL2016";
    string str;
    int cnt=0;
    cin>>str;
    for(int i=0;i<16;i++){
    	if(s[i]!=str[i]){
    		cnt++;
    	}
    }
    cout<<cnt<<endl;
    return 0;
   }


Measured memory_bytes: 3624
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;
const int N_MAX = pow(10,5);

vector<pair<int, int>> v[N_MAX];
int s[N_MAX];

void dfs(int i) {
  for (auto &p: v[i]) {
    if (s[p.first]==-1) {
      s[p.first] = s[i] ^ (p.second%2);
      dfs(p.first);
    }
  }
}

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

  rep(i, N) {
    int a, b, w; cin >> a >> b >> w; w%=2;
    v[a-1].push_back(pair<int, int>(b-1, w));
    v[b-1].push_back(pair<int, int>(a-1, w));
  }

  memset(s, -1, sizeof(s)); s[0]=0;
  rep(i,N) dfs(i);
  rep(i,N) cout << s[i] << endl;
  return 0;
}

Measured memory_bytes: 7552
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s, t; cin >> s >> t;
  int n = s.size();
  map<char, vector<int>> mp;
  rep(i, n) {
    mp[s[i]].push_back(i);
  }
  int m = t.size();
  int cnt = 0;
  int pos = 0;
  rep(i, m) {
    if(!mp.count(t[i])) {
      cout << -1 << endk;
      return 0;
    }
    while(1) {
      auto itr = lower_bound(all(mp[t[i]]), pos);
      if(itr == mp[t[i]].end()) {
        cnt++; pos = 0;
        continue;
      }
      pos = *itr+1;
      break;
    }
  }
  cout << 1LL*cnt*n+pos << endk;
  return 0;
}


Measured memory_bytes: 4184
#include<iostream>
#include<cstdlib>
#include<utility>
#include<tuple>
#include<string>
#include<vector>
#include<numeric>
#include<algorithm>
#include<queue>
#include<deque>
#include<bitset>
#include<cmath>
#include<map>
#include<iomanip>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
#define rep(i, a, b) for(int i = a; i < b; i++)

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

	vector<int> p(n);
	rep(i, 0, n) cin >> p[i];

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

	int ans = 0;
	rep(i, 0, k) ans += p[i];

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define LL long long
#define N 200100
using namespace std;

int cnt[N],a[N],b[N];
int l[N],r[N];
int n,ans1,ans2,m;

int main()
{
	scanf("%d",&n); m=0;
	for (int i=1;i<=n;i++)
	{ 
		scanf("%d %d",&l[i],&r[i]); m=max(m,r[i]);
		cnt[l[i]]++; cnt[r[i]]--;
		a[l[i]]++;   b[r[i]]++;
	}
	for (int i=1;i<=m;i++) a[i]+=a[i-1],b[i]+=b[i-1],cnt[i]+=cnt[i-1];
	for (int i=1;i<=n;i++) ans1=max(ans1,n-(n-a[r[i]-1])-b[l[i]]);
	for (int i=1;i<=m;i++) ans2=max(ans2,cnt[i]);
	printf("%d %d\n",ans1,ans2);
}


Measured memory_bytes: 5956
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<tuple>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main() {
	int n;
	cin >> n;
	if (n % 2 != 0) {
		cout << (n / 2)*((n / 2) + 1) << endl;
	}
	else {
		cout << (n / 2)*(n / 2) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];

    sort(all(a));

    int tmp = 1;
    int ans = 0;

    rep(i,n-1){
        if(a[i] == a[i+1]) tmp++;
        else{
            if(tmp %2 == 1) ans++;
            tmp = 1;
        }
    }

    if(tmp != 0){
        if(tmp %2 == 1) ans++;
    }

    else ans++;

    cout << ans << endl;
}

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

int main(){
  int N,M,X,Y;
  cin>>N>>M>>X>>Y;
  vector<int> x(N);
  vector<int> y(M);
  int x_min=100;
  int x_max=-100;
  for(int i=0;i<N;i++){
    cin>>x.at(i);
    if(x_min>x.at(i))x_min=x.at(i);
    if(x_max<x.at(i))x_max=x.at(i);
  }
  int y_min=100;
  int y_max=-100;
  for(int i=0;i<M;i++){
    cin>>y.at(i);
    if(y_min>y.at(i))y_min=y.at(i);
    if(y_max<y.at(i))y_max=y.at(i);
  }
  string ans="War";
  int z_min,z_max;
  if(y_min-x_max>0){
    z_min=x_max+1;
    z_max=y_min;
    for(int i=z_min;i<z_max+1;i++){
      if(X<i&&Y>=i)ans="No War";
    }
  }

  cout<<ans<<endl;
}


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

using namespace std;

const int MOD = 1000000007;

long long mod_pow(long long a, long long n)
{
  long long ret = 1;
  while (n) {
    if (n % 2) {
      ret = (ret * a) % MOD;
    }
    a = (a * a) % MOD;
    n /= 2;
  }
  return ret;
}

int main()
{
  long long num[100001];
  
  int n, k;
  
  scanf("%d %d", &n, &k);
  
  fill(num, num + k + 1, 0);
  for (int i = k; i >= 1; i--) {
    num[i] = (num[i] + mod_pow(k / i, n)) % MOD;
    for (int j = 1; j * j <= i; j++) {
      if (i % j == 0) {
        if (j != i) num[j] = (num[j] + MOD - num[i]) % MOD;
        if (j != 1 && j * j != i) num[i / j] = (num[i / j] + MOD - num[i]) % MOD;
      }
    }
  }
  
  long long ans = 0;
  for (int i = 1; i <= k; i++) {
    ans = (ans + num[i] * i) % MOD;
  }
  
  printf("%lld\n", ans);
  
  return 0;
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;

vector<int> A;
vector<pair<int, int>> BC;
int main() {
  int N, M;
  cin >> N >> M;

  A.resize(N + 1);
  rep(i, N) scanf("%d", &A[i]);
  A[N] = INT_MAX;

  BC.resize(M);
  rep(i, M) scanf("%d %d", &BC[i].first, &BC[i].second);

  sort(A.begin(), A.end());
  sort(BC.begin(), BC.end(), [](auto const& x, auto const& y){
    return x.second == y.second ? x.first > y.first
                                : x.second > y.second;
  });

  int edited = 0;
  ll ans = 0;
  rep(i, M) {
    int b = BC[i].first, c = BC[i].second;
    int last = std::lower_bound(A.begin() + edited, A.begin() + N, c) - A.begin();
    int distance = min(b, last - edited);
    if (!distance) { break; }
    ans += (ll)distance * c;
    edited += distance;
    if (edited >= N) { break; }
  }
  REP(i, edited, N) ans += A[i];
  cout << ans << endl;
}


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

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

  int xa = abs(x - a);
  int xb = abs(x - b);

  if (xa < xb)
    cout << "A" << endl;
  else
    cout << "B" << endl;
}

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

int main() {
  int n;
  cin>>n;
  string s;
  cin>>s;
  map<char, int> m;
  for (char c: s) {
    ++m[c];
  }
  long long ans = 1;
  long long mod = 1000000007;
  for (auto i: m) {
    ans *= (i.second + 1);
    ans %= mod;
  }
  cout<< (ans + mod - 1) % mod <<endl;

}

Measured memory_bytes: 512
#include <stdio.h>

int min(int a, int b){
	if(a>b){
		return b;
	}
	return a;
}

int main(){
	int N;//入力
	scanf("%d",&N);
	long long A[100000];//入力
	int i;
	for(i=0;i<N;i++){
		scanf("%lld",&A[i]);
	}
	int j;//A[i]が何回負の数であるかをカウントする
	j=0;
	long long m;//A[i]の絶対値の最小値
	m=-min(A[0],-A[0]);
	long long S;//A[i]の絶対値の和
	S=0;
	for(i=0;i<N;i++){
		if(A[i]<0){
			j++;
			A[i]=-A[i];
		}
		m=min(m,A[i]);
		S=S+A[i];
	}
	if(j%2==0){
		printf("%lld",S);
	}else{
		printf("%lld",S-2*m);
	}
}


Measured memory_bytes: 896