akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

int main() {
  i64 A, B;
  cin >> A >> B;
  i64 M;
  cin >> M;
  vector<i64> a(A);
  rep(i,0,A) {
    cin >> a[i];
  }
  vector<i64> b(B);
  rep(i,0,B) {
    cin >> b[i];
  }

  i64 ans = *min_element(all(a)) + *min_element(all(b));

  rep(i,0,M) {
    i64 x, y, z;
    cin >> x >> y >> z;
    x--;
    y--;
    ans = std::min(ans, a[x] + b[y] - z);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define N 300010
using namespace std;

inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
struct edge
{
	int v,next;
}vs[N<<1];
int n,st[N],ee,fa[N],size[N];
map <int,int> Ms[N];
inline int getfa(int x)
{
	return fa[x]==x? x: fa[x]=getfa(fa[x]);
}
int main()
{
	queue <int> q; 
	while(!q.empty()) q.pop();
	n=read(); for(int i=1;i<n+n-1;i++)
	{
		int u=read(), v=read();
		Ms[u][v]++; Ms[v][u]++;
		size[u]++; size[v]++;
		q.push(u); q.push(v);
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		int y=q.front(); q.pop();
		x=getfa(x); y=getfa(y);
		if(Ms[x][y]<2) continue;
	//	cerr << x << " " << y << " " << endl;
		if(size[x]<size[y]) swap(x,y);
	//	cout << "merge:" << x << "  " << y << endl;
		for(map<int,int> :: iterator it=Ms[y].begin();it!=Ms[y].end();it++)
		{
			int d=(*it).second,z=(*it).first;
			Ms[y][z]=0; Ms[z][y]=0;
			if(z==x) continue;
			Ms[z][x]+=d; Ms[x][z]+=d;
			q.push(x); q.push(z);
			
		}
		/*for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				printf("%d ",Ms[i][j]);
			printf("\n");
		}
		cout << endl;*/
		fa[y]=x;
	}
	//for(int i=1;i<=n;i++) cout << fa[i] << " "; cout << endl;
	for(int i=1;i<=n;i++) if(fa[1]!=fa[i]) {puts("NO"); return 0;}
	puts("YES");
	return 0;
}

Measured memory_bytes: 81408
def main():
    k, n = map(int, input().split())
    a = list(map(int, input().split()))
    a.append(a[0] + k)

    max_length = 0
    for i in range(n):
        max_length = max(max_length, a[i+1] - a[i])

    print(k - max_length)


if __name__ == '__main__':
    main()
    

Measured memory_bytes: 78412
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin >> n >> m;
    int a[n],b[n],c[m],d[m];
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
    }
    for(int j=0;j<m;j++){
        cin >> c[j] >> d[j];
    }
    for(int i=0;i<n;i++){
        int dis=INT_MAX;
        int kyori = 0;
        for(int j=0;j<m;j++){
            int v = abs(a[i]-c[j]) + abs(b[i]-d[j]);
            if(dis > v){
                dis = v;
                kyori = j;
            }
        }
        cout << kyori + 1 << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int mod = 1000000007;


int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  int x;
  cin>>x;
  for(int i=1;i<=x;i++){
    int y = i * 1.08;
    if(y==x){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<":("<<endl;
  return 0;
}

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

int main() {

  int X, N;
  cin >> X >> N;
  
  vector<int> p(N);
  bool xabsence = true;
  
  for(int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  for(auto v : p){
    if(v == X){
      xabsence = false;
    }
  }
  if(N==0 || xabsence){
    cout << X << endl;
    return 0;
  }
  

  for(int i = 0; i< N; i++){
    int cand;
    bool cabsence = true;
    if( i % 2 == 0){//smaller side
      cand = X -1 - i/2;
    }else{//larger side
      cand = X + (i+1)/2;     
    }
    for(auto v : p){
      if(v == cand){
        cabsence = false;
      }
    }
    if(cabsence){
      cout << cand << endl;
      return 0;
    }
  }
  
}


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

int main(void){
	int count[4][3][10];
	for(int i = 0;i < 4;i++){
		for(int j = 0;j < 3;j++){
			for(int k = 0;k < 10;k++){
				count[i][j][k] = 0;
			}
		}
	}
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		int b,f,r,v;
		cin >> b >> f >> r >> v;
		count[b-1][f-1][r-1] += v;
	}
	for(int i = 0;i < 4;i++){
		for(int j = 0;j < 3;j++){
			for(int k = 0;k < 10;k++){
				if(k == 0){
					cout << " ";
				}
				cout << count[i][j][k];
				if(k != 9){
					cout << " ";
				}
			}
			cout << endl;
		}
		if(i == 3){
			break;
		}
		for(int sh = 0;sh < 20;sh++){
			cout << "#";
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
using namespace std;


int m,n,ans=0;
vector<vector<int>>tree(10);
vector<bool>flag(10,false);
void DFS(int x)
{
   
    flag.at(x)=1;
   // for(int x:flag){cout<<x;}cout<<endl;
    bool tf=1;
    REP(i,n)
    {
        tf&=flag.at(i);
    }
    if(tf==1)ans++;
    
        REP(i,tree.at(x).size())
        {
            if(flag.at(tree.at(x).at(i))==0)
            {
                DFS(tree.at(x).at(i));
                flag.at(tree.at(x).at(i))=0;
            }
        }
}

int main()
{
    cin>>n>>m;
    
    REP(i,m)
    {
        int a,b;
        cin>>a>>b;
        tree.at(a-1).push_back(b-1);
        tree.at(b-1).push_back(a-1);
    }
    DFS(0);
    cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
  cin >>n;
  int v[n],c[n],ans=0;
  for(int i=0;i<n;i++)cin >>v[i];
  for(int i=0;i<n;i++)cin >>c[i];
  for(int i=0;i<n;i++){
  if(v[i]-c[i]>0)ans+=v[i]-c[i];
  }
  cout << ans<<endl;
}

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;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    rep(i, N) cin >> p[i];
    sort(p.begin(), p.end());
    int ans = 0;
    rep(i, K) ans += p[i];
    cout << ans << "\n";
}

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

const int MOD = 1e9+7;
const int INF = 2147483647;

int main(){
    string S;
    cin >> S;
    rep(i, 0, 1<<3){
        int num = (S[0] - '0');
        vector<char> ans;
        ans.push_back(S[0]);
        rep(j, 0, 3){
            if ((i>>j)&1){
                num += (S[j+1] - '0');
                ans.push_back('+');
            }
            else{
                num -= (S[j+1] - '0');
                ans.push_back('-');
            }
            ans.push_back(S[j+1]);
        }
        if (num == 7){
            for (auto s: ans){
                cout << s;
            }
            cout << "=7";
            return 0;
        }
    }
    cout << -1 << endl;
}

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

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

    int pmax=0;
    int memo=-1;
    rep(i, n){
        cin >> p.at(i);
        if(pmax<p.at(i)) memo = i; 
        pmax = max(pmax, p.at(i));
    }

    ll sum = 0;
    rep(i, n){
        if(memo!=i) sum += p.at(i);
        else sum += p.at(i)/2; 
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <chrono>
#include <queue>
#include <functional>

#define out(t) cout << (t) << "\n"

using namespace std;

typedef long long ll;
typedef unsigned int uint;

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

uint tzcnt(uint x) {
    x = ~x & (x - 1);
    x -= x >> 1 & 0x55555555;
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = x + (x >> 4) & 0x0F0F0F0F;
    return x * 0x01010101 >> 24;
}

int popcount(uint x) {
    x -= x >> 1 & 0x55555555;
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = x + (x >> 4) & 0x0F0F0F0F;
    return x * 0x01010101 >> 24;
}

struct Point {
    int x, y;

    Point(int p, int q) : x(p), y(q) {}
};

int C[500];
int S[500];
int F[500];

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

    int N;
    cin >> N;

    for (int i = 0; i < N - 1; ++i) {
        cin >> C[i] >> S[i] >> F[i];
    }

    // i: 開始駅
    for (int i = 0; i < N - 1; ++i) {
        int elapsed = S[i] + C[i];

        for (int j = i + 1; j < N; ++j) {
            // 終点
            if (j == N - 1) {
                break;
            }

            // 開業前
            if (elapsed < S[j]) {
                elapsed = S[j] + C[j];
            }
            else {
                int over = elapsed % F[j];

                elapsed += F[j] - (over != 0 ? over : F[j]);

                elapsed += C[j];
            }
        }

        out(elapsed);
    }

    out(0);

    int aaa;
    cin >> aaa;
}

Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
vvi out(500,vi(500,1));
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
signed main(){
	const int M=10000;
	int sosu[M]={1,1,0};
	for(int i=2;i*i<M;i++)if(sosu[i]==0)
	for(int j=i*2;j<M;j+=i)sosu[j]=1;
	vi sos;
	rep(i,M)if(sosu[i]==0)sos.pb(i);
	
	int n;
	cin>>n;
	int t=0;
	rep(i,500){
		int x=0,y=i*2;
		while(y>=0){
			if(x<500&&y<500)out[x][y]*=sos[t];
			x++;y--;
		}
		t++;
	}
	rep(i,500){
		int x=0,y=500-2*i;
		while(x<500){
			if(0<=y&&y<500)out[x][y]*=sos[t];
			x++;y++;
		}
		t++;
	}
	rep(x,500)rep(y,500)if(out[x][y]==1){
		t=1;
		if(x<499)t=lcm(t,out[x+1][y]);
		if(x)t=lcm(t,out[x-1][y]);
		if(y<499)t=lcm(t,out[x][y+1]);
		if(y)t=lcm(t,out[x][y-1]);
		out[x][y]=t+1;
	}
	int ma=0;
	rep(i,500)rep(j,500)cmax(ma,out[i][j]);
	rep(i,n){rep(j,n)cout<<out[i][j]<<" ";cout<<endl;}
}

















Measured memory_bytes: 5248
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, M;
set<int> G[MAX_N];

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].insert(b);
		G[b].insert(a);
	}
	rep(i, 0, N) {
		if(G[i].count(0) && G[i].count(N - 1)) {
			cout << "POSSIBLE\n"; return;
		}
	}
	cout << "IMPOSSIBLE\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 42496
h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for maskR in range((1 << h) - 1):
    for maskC in range((1 << w) - 1):
        black = 0
        for i in range(h):
            for j in range(w):
                if ((maskR >> i) & 1) == 0 and ((maskC >> j) & 1) == 0:
                    if c[i][j] == '#':
                        black += 1
        if black == k:
            ans += 1
print(ans)

Measured memory_bytes: 9152
#include <bits/stdc++.h>
#define rep( i, n ) for (long long i = 0; i < ( long long )(n); i++)

using namespace std;
typedef long long ll;
typedef pair< int , int > P;

ll euclidean_gcd(ll a, ll b) {
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){
  ll n,k;
  cin>>n>>k;
  ll p=0;
  ll d = n;

if((n%k==0)&&(n>=k)){
  cout<<"0";
}
else if(n<k){
  cout<<min(abs(n-k),n);
}
else{
  cout<<min(n%k,(abs(n%k-k)));
  }
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
#define MK make_pair
const ll E=1e18+7;
const ll MOD=1000000007;




int main(){
    string s;
    cin>>s;
    bool j=true;
    ll n='z';
    ll count=0;
    if(s[0]!='A'){j=false;}
    for(int i=2;i<s.size()-1;i++){
        if(s[i]=='C'){count++;}
    }
    if(count!=1){j=false;}
    count=0;
    for(int i=0;i<s.size();i++){
        if(!('a'<=s[i] && s[i]<='z')){count++;}
    }
    if(count!=2){j=false;}
    if(j){cout<<"AC"<<endl;}
    else{cout<<"WA"<<endl;}
    
    return 0;
}


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

int main(){
    int c[3][3];
    for(int i=0; i < 3; i++){
        for(int j=0; j < 3; j++) cin >> c[i][j];
    }

    if(c[0][0] - c[0][1] == c[1][0] - c[1][1] and c[0][0] -c[0][1] == c[2][0] - c[2][1] and c[0][0] - c[0][2]
        == c[1][0] - c[1][2] and c[0][0] - c[0][2] == c[2][0] -c[2][2])
        cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


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

#define ll long long int
#define li int64_t

int main()
{
	int a,b,c,d,e;
	cin>>a>>b>>c>>d>>e;
	if(a == 0)cout<<1;
	else if(b == 0)cout<<2;
	else if(c == 0) cout<<3;
	else if(d == 0) cout<<4;
	else
	{
		cout<<5;
	}	
}

Measured memory_bytes: 3504
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    int N;
    cin >> N;
    vec<int> T(N+2),V(N+2),S(N+3);
    int tsum = 0;
    for(int i=1;i<=N;i++){
        cin >> T[i];
        T[i] *= 2;
        tsum += T[i];
        S[i+1] = S[i]+T[i];
    }
    for(int i=1;i<=N;i++) cin >> V[i];
    T[0] = 0,V[0] = 0;
    T[N+1] = tsum,V[N+1] = 0;
    S[N+2] = S[N+1];
    vec<double> mi(tsum+1,2e9);
    for(int i=0;i<=N+1;i++){
        int l = S[i],r = S[i+1];
//        cerr << l << " " << r << "\n";
        auto f = [&](int t)->double{
            if(l<=t && t<=r) return V[i];
            if(t<l) return -0.5*(t-l)+V[i];
            else return 0.5*(t-r)+V[i];
        };
        for(int j=0;j<=tsum;j++) mi[j] = min(mi[j],max(0.0,f(j)));
    }
    double ans = 0;
    for(int j=0;j<tsum;j++){
//        cerr << j << " " << mi[j] << "\n";
        ans += (mi[j]+mi[j+1])*0.25;
    }
    cout << fixed << setprecision(10) << ans << "\n";
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;

string solve(ll n)
{
    if(n==0) return "";

    n--;
    string s="";
    s += (char)('a'+(n%26)) + solve(n/26);

    return s;
}

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

  string s = solve(n);
  reverse(s.begin(),s.end());
  cout<<s<<endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n; cin >> n;
ll a[n]={};
rep(i,n){
cin>>a[i];}
ll c=0;
rep(i,n){
if(a[i]%2==1){
c++;
break;}}
if(c==1){
cout << "first" << endl;}
else{
cout << "second" << endl;}}

Measured memory_bytes: 4392
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 100000000;
using namespace std;

long long dp[51][51][2501] = {0};

int main(){
    int n, a, x[50];

    cin >> n >> a;
    rep(i,n) cin >> x[i];


    dp[0][0][0] = 1;

    rep(i,n){
        rep(k,n){
            rep(s,2501){
                dp[i + 1][k][s] += dp[i][k][s];
                if(s - x[i] < 0) continue;
                dp[i + 1][k + 1][s] += dp[i][k][s - x[i]];
            }
        }
    }
    long long sum = 0;
    for(int j = 1; j <= n; j++){
        sum += dp[n][j][a * j];
    }
    cout << sum << endl;
}


Measured memory_bytes: 50048
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdlib.h>
#include <limits.h>

void binary_search(int n,int k,int a[n],int *min,int *max);

int main(void)
{

	int n,k;
	int *a;
	int maxa=INT_MIN;
	int mina=1;
	int x;
	
	scanf("%d %d",&n,&k);
	a=(int *)malloc(sizeof(int)*(n));
	
	int i;
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	for(i=0;i<n;i++)
	{
		if(maxa<a[i])
		{
			maxa=a[i];
		}
	}
	
	binary_search(n,k,a,&mina,&maxa);
	printf("%d",mina);
	
	free(a);
	a=NULL;
	return 0;
}

void binary_search(int n,int k,int a[n],int *min,int *max)
{
	int mid=((*min)+(*max))/2;
	int b=0;
	int i;
	for(i=0;i<n;i++)
	{
		b+=((a[i]+mid-1)/mid)-1;
	}
	if(b<=k)
	{
		(*max)=mid;
	}
	else
	{
		(*min)=mid+1;
	}
	if((*min)!=(*max))
	{
		binary_search(n,k,a,min,max);
	}
	
}

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

int main() {
    int n;
    cin >> n;
    int digit = to_string(n).size();
    if (digit % 2 == 0) {
        cout << (int) ((pow(100, digit / 2) - 1) / 11) << endl;
    }
    else {
        cout << (int) ((pow(100, digit / 2) - 1) / 11 + n + 1 - pow(10, digit - 1)) << endl;
    }
}

Measured memory_bytes: 512
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new java.util.Scanner(System.in);
    String S = sc.nextLine();
    int sLength = S.length();
    for (int i = 0; i < sLength; i++) {
      System.out.print("x");
    }
  }
}


Measured memory_bytes: 21844
import numpy as np

n, k = map(int, input().split())
lst = list(map(int, input().split()))

array = np.array(lst)
po_array = array[array>=0]
ne_array = abs(array[array<0])
ne_array.sort()

if len(po_array) >= len(ne_array):
    long_array = po_array
    short_array = ne_array
else:
    long_array = ne_array
    short_array = po_array

if len(short_array) > k:
    min_len = k
else:
    min_len = len(short_array)
        
if min_len == 0:
    print(long_array[k-1])
else:
    min_dist = 10**10
    for i in range(min_len):
        dist = 10**10
        if i == k-1:
            dist = short_array[i]
        elif k-i-1 <= len(long_array): 
            dist = min(short_array[i]*2 + long_array[k-i-2], short_array[i] + long_array[k-i-2]*2)
        if min_dist > dist:
            min_dist = dist
    if len(long_array) >= k:
        if min_dist > long_array[k-1]:
            min_dist = long_array[k-1]
    print(min_dist)

Measured memory_bytes: 23124
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import floor

x = int(readline())
v = 100
for i in range(x):
    v = floor(v * 1.01)
    if v >= x:
        print(i + 1)
        exit()


Measured memory_bytes: 63484
import java.util.*;class Main{static int a,b;static boolean s;public static void main(String[]$){Scanner c=new Scanner(System.in);int k=c.nextInt(),x=c.nextInt(),y=c.nextInt();x*=a=x<0?-1:1;y*=b=y<0?-1:1;if(s=x<y)x^=y^(y=x);int n=(x+y+k-1)/k;if(k%2==0&&(x+y)%2==1){System.out.println(-1);return;}else if(x+y<k){if((x+y)%(n=2)==1){System.out.println(3);p(x,x-k);p(x+(k+x-y)/2,x-k+(k-x+y)/2);p(x,y);return;}}else if((k-(x+y)%k)%k%2==1)n++;int m=(k*n-x-y)/2,i=0;System.out.println(n);while(++i<=n)if(m>k*i)p(0,-k*i);else if(x+m>k*i)p(k*i-m,-m);else p(x,k*i-m-m-x);}static void p(int x,int y){System.out.println(a*(s?y:x)+" "+b*(s?x:y));}}

Measured memory_bytes: 43508
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]

import collections

freq = collections.Counter(A)
# d = list(zip(freq.values(), freq.keys()))
d = list(freq.items())

BC = [x[::-1] for x in BC]
BC.extend(d)
e = sorted(BC, reverse=True)

ans = 0
count = 0
for c, b in e:
#     print(c, b)
    if count + b <= N:
        count += b
        ans += c * b
    else:
        ans += c * (N - count)
        break
        
print(ans)

Measured memory_bytes: 45472
n, m = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(m)]

red = [0] * (n+1)
white = [1] * (n+1)

red[1] = 1
white[1] = 0

for x, y in X:
    if red[x] == 1:
        if white[x] >= 1:
            white[x] -= 1
        else:
            red[x] -= 1

        if red[y] == 0:
            red[y] += 1
        else:
            white[y] += 1

    else:
        white[x] -= 1
        white[y] += 1

print(sum(red))

Measured memory_bytes: 22692
import collections
import math

def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
mod = 10**9+7
ans = 1
pf = []
f = math.factorial(n)
# print('factorial:', f)

for i in range(2, n+1):
    # print(i, trial_division(i))
    pf += trial_division(i)

# print('pf:', pf)

pfMap = collections.Counter(pf)
# print('pfMap:', pfMap)

for key, value in pfMap.items():
    ans *= value + 1
    ans %= mod

print(ans % mod)




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

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

	if (S == "SAT") cout << 1 << endl;
	if (S == "FRI") cout << 2 << endl;
	if (S == "THU") cout << 3 << endl;
	if (S == "WED") cout << 4 << endl;
	if (S == "TUE") cout << 5 << endl;
	if (S == "MON") cout << 6 << endl;
	if (S == "SUN") cout << 7 << endl;
}

Measured memory_bytes: 256
n = int(input())
result = []
for x in range(1, n+1):
    if x % 3 == 0:
        result.append(x)
        continue
    i = x
    while i:
        i, r = divmod(i, 10)
        if r == 3:
            result.append(x)
            break
print(' '.join(['']+ [str(i) for i in result]))


Measured memory_bytes: 6120
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int A=sc.nextInt();
		int B=sc.nextInt();
		if(Math.abs(A-B)%2==0) {
			System.out.println("Alice");
		}
		else if(Math.abs(A-B)%2==1) {
			System.out.println("Borys");
		}
	}
}

Measured memory_bytes: 23764
N, D = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for i in range(N):
    R = XY[i][0]**2 + XY[i][1]**2
    if R <= D**2:
        ans += 1
    else:
        pass

print(ans)

Measured memory_bytes: 45380
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
    int x[4],y[4];
    scanf("%d%d%d%d",&x[0],&y[0],&x[1],&y[1]);
    int dx = (int)abs(x[0]-x[1]);
    int dy = (int)abs(y[0]-y[1]);

    if( x[0] <= x[1] && y[0] <= y[1] ){
        printf("%d %d %d %d\n",x[1]-dy,y[1]+dx,x[1]-dy-dx,y[1]+dx-dy);
    }else if( x[0] > x[1] && y[0] <= y[1] ){
        printf("%d %d %d %d\n",x[1]-dy,y[1]-dx,x[1]-dy+dx,y[1]-dx-dy);
    }else if( x[0] > x[1] && y[0] > y[1] ){
        printf("%d %d %d %d\n",x[1]+dy,y[1]-dx,x[1]+dy+dx,y[1]-dx+dy);
    }else{
        printf("%d %d %d %d\n",x[1]+dy,y[1]+dx,x[1]+dy-dx,y[1]+dx+dy);
    }

    return 0;
}

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

using namespace std;

#define fo(i,n) for(int i=0; i<n; i++)
#define Fo(i,k,n) for(int i=k; i<n; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, a) for(auto it=a.begin(); it!=a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

int n,W;
vvl dp,wi;

void printt(){
    // dp[1][0] = 0;
    Fo(i,1,n+1){
        Fo(j,0,W+1){
            if(j==0){
                dp[i][j]=0;
            }else{
                if(i==1){
                    if(j>=wi[i][0]){
                        dp[i][j] = wi[i][1]; 
                    }
                }else{
                    if(j>wi[i][0]){
                        dp[i][j] = max(dp[i-1][j-wi[i][0]]+wi[i][1], dp[i-1][j]);
                    }else{
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
        }
    }
    cout<<dp[n][W]<<endl;
}

void take_inp() {
    cin>>n>>W;
    wi.resize(n+1, vl(2));
    dp.resize(n+1, vl(W+1));
    Fo(i,1,n+1){
        ll a,b;
        cin>>a>>b;
        wi[i][0] = a;
        wi[i][1] = b;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    take_inp();
    printt();
    return 0;
}

Measured memory_bytes: 80256
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int l = max(A, C);
  int u = min(B, D);
  int s = max(0, u-l);
  cout << s << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

long long pow_mod(long long n, long long p, long long m)
{
    if (p == 0) {
        return 1;
    }

    if (p % 2 == 0) {
        long long t = pow_mod(n, p / 2, m);
        return t * t % m;
    }
    return n * pow_mod(n, p - 1, m) % mod;
}

long long nCr_mod(long long n, long long r)
{
    long long x = 1;
    for (long long i = n - r + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }

    long long a = 1;
    for (long long i = 1; i <= r; i++) {
        a *= i;
        a %= mod;
    }

    long long y = pow_mod(a, mod - 2, mod) % mod;

    return x * y % mod;
}

int main()
{
    long long k;
    std::cin >> k;

    std::queue<long long> q;
    for (long long i = 1; i <= 9; i++) {
        q.push(i);
    }

    for (int i = 0; i < k - 1; i++) {
        long long val = q.front();
        q.pop();
        if (val % 10 != 0) {
            q.push(val * 10 + val % 10 - 1);
        }

        q.push(val * 10 + val % 10);

        if (val % 10 != 9) {
            q.push(val * 10 + val % 10 + 1);
        }
    }

    std::cout << q.front() << std::endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
typedef long long ll;

int main(){
    
    ll n, ans = 1e15;
    scan(n);
    for(ll i = 1; i*i <= n; i++){
        if(n%i == 0){
            ll j = n/i;
            ans = min(ans, i+j-2);
        }
    }
    
    print(ans);
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AOJ
{
	class Program
	{
		static void Main(string[] args)
		{
			var n = 0;
			while ((n = int.Parse(Console.ReadLine())) != 0)
			{
				var r = 0;
				while (n != 1)
				{
					if (n % 2 == 0)
					{
						n /= 2;
					}
					else
					{
						n *= 3;
						n++;
					}
					r++;
				}
				Console.WriteLine(r);
			}
		}
	}
}

Measured memory_bytes: 5596
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long yokin = 100;
        long n = 0;

        while (true) {
            if (x <= yokin) {
                break;
            }
            yokin = (long) ((double) yokin * 1.01);
            n++;
        }

        System.out.print(n);
    }
}

Measured memory_bytes: 35724
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    int mx = 0;
    int cnt = 0;
    for( int i = 0; i < n; ++i ) {
        int a;
        cin >> a;
        if( a >= mx ) {
            ++cnt;

        }
        mx = max( a, mx );
    }
    cout << cnt << endl;
    return 0;
}



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

string solve() {
    string S;
    int K;
    cin >> S >> K;
    set<string> st;
    for ( int i = 0; i < S.size(); i++ ) {
        for ( int j = 1; i + j <= S.size(); j++ ) {
            if ( st.size() == K ) {
                if ( *prev(st.end()) <= S.substr(i, j) ) break;
            }
            st.insert(S.substr(i, j));
            if ( st.size() > K ) st.erase(prev(st.end()));
        }
    }
    return *prev(st.end());
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

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

long long a,b,c,d,cc,dd,cd,tot,ans,gc,divi;

int main(){
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	cc = b/c - (a-1)/c;
	dd = b/d - (a-1)/d;
	gc = (c*d)/__gcd(c,d);
	cd = b/gc - (a-1)/gc;
//	printf(">> %lld %lld %lld\n",cc,dd,cd);
	divi = cc+dd-cd;
	tot = b-a+1;
//	printf("%lld %lld\n",tot,divi);
	ans = tot-divi;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int n, k;
    cin >> n >> k;
    vint h(n);
    rep(i, n) cin >> h[i];
    sort(all(h));

    int ans = INF;
    rep(i, n) {
        int r = i+k-1;
        if (r >= n) break;
        ans = min(ans, h[r]-h[i]);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    int N;
    cin >>N;
    int t = N,c = 0;
    for(int i = 0;i < 1234567890;i++){
        if(t > 0){
            c += t % 10;
            t = t/ 10;
        }
        else break;
    }
    if(N%c == 0)cout  << "Yes" << endl;
    else cout << "No" << endl;
}
 

Measured memory_bytes: 256
#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;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=998244353 ;

vector<int> v[202020];
void dfs(int x, int p, vector<int>& d){
	for(auto to:v[x]){
		if(to==p)continue;
		d[to] = d[x] + 1;
		dfs(to,x,d);
	}
}


int main(){
    int n;
    cin>>n;
    rep(i,n-1){
		int x,y;
		cin>>x>>y;
		--x;--y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	vector<int> d1(n),d2(n),d3(n);
	dfs(0,-1,d1);
	int l = max_element(d1.begin(),d1.end())-d1.begin();
	dfs(l,-1,d2);
	int r = max_element(d2.begin(),d2.end())-d2.begin();
	dfs(r, -1, d3);
    int mi = 1;
    rep(i,n){
        if(d2[i]+d3[i]==d2[r])continue;
        if(d2[i]==d3[i]&&d3[i]==d2[r])continue;
        mi = max(max(d2[i],d3[i]),mi);
    }
    REP(i,1,n+1){
        if(i<=2)cout<<1;
        else if(i<=mi)cout<<0;
        else cout<<1;
    }
    cout<<endl;
    return 0;
}



Measured memory_bytes: 18200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (1e9)

int main(){
  int n, tl;
  int c, ts;
  cin >> n >> tl;

  int min_cost = INF;

  for(int i = 1; i <= n; i++){
    cin >> c >> ts;
    if(ts <= tl){
      min_cost = min(c, min_cost);
    }
  }

  if(min_cost == INF){
    cout << "TLE" << endl;
  } else {
    cout << min_cost << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define inf 1000000000000000000
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  
  ll h, w; cin >> h >> w;
  vector<vector<ll>> a(h, vector<ll>(w));
  vector<vector<ll>> b(h, vector<ll>(w));
  vector<vector<ll>> c(h, vector<ll>(w));
  rep(i, h) {
    rep(j, w) {
      cin >> a[i][j];
    }
  }
  rep(i, h) {
    rep(j, w) {
      cin >> b[i][j];
    }
  }
  rep(i, h) {
    rep(j, w) {
      c[i][j] = abs(a[i][j] - b[i][j]);
    }
  }

  vector<vector<vector<ll>>> dp(h, vector<vector<ll>>(w,vector<ll>(80 * (h + w) + 1)));
  dp[0][0][c[0][0]] = true;
  rep(i, h) {
    rep(j, w) {
      rep(k, 80 * (h + w) + 1) {
        if (0 <= i + 1 && i + 1 < h && dp[i][j][k]) {
          if (0 <= k + c[i + 1][j] && k + c[i + 1][j] <= 80 * (h + w)) dp[i + 1][j][k + c[i + 1][j]] = true;
          if (0 <= abs(k - c[i + 1][j]) && abs(k - c[i + 1][j]) <= 80 * (h + w)) dp[i + 1][j][abs(k - c[i + 1][j])] = true;
        }
        if (0 <= j + 1 && j + 1 < w && dp[i][j][k]) {
          if (0 <= k + c[i][j + 1] && k + c[i][j + 1] <= 80 * (h + w)) dp[i][j + 1][k + c[i][j + 1]] = true;
          if (0 <= abs(k - c[i][j + 1]) && abs(k - c[i][j + 1]) <= 80 * (h + w)) dp[i][j + 1][abs(k - c[i][j + 1])] = true;
        }
      }
    }
  }
  rep(k, 80 * (h + w) + 1) {
    if (dp[h - 1][w - 1][k]) {
      cout << k << endl;
      exit(0);
    }
  }
}


Measured memory_bytes: 652408
#include <stdio.h>
 
int main()
{
    int hotel[4][3][10],i,j,k,test,b,f,r,v;
    for(i=0;i<4;i++){
        for(j=0;j<3;j++){
            for(k=0;k<10;k++){
                hotel[i][j][k]=0;
            }
        }
    }
    scanf("%d",&test);
    for(i=0;i<test;i++){
        scanf("%d %d %d %d",&b,&f,&r,&v);
        hotel[b-1][f-1][r-1]+=v;
    }
    for(j=0;j<3;j++){
            for(k=0;k<10;k++){
                printf(" %d",hotel[0][j][k]);
            }
            printf("\n");
        }
    for(i=1;i<4;i++){
        printf("####################\n");
        for(j=0;j<3;j++){
            for(k=0;k<10;k++){
                printf(" %d",hotel[i][j][k]);
            }
            printf("\n");
        }
    }
    return 0;
}


Measured memory_bytes: 2112
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <fstream>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;
typedef map<int, int> mii;
typedef map<int, string> mis;
typedef map<string, int> msi;
typedef set<int> si;
typedef set<ll> sl;
typedef map<ll, ll> mll;
typedef queue<int> qi;
typedef queue<ii> qii;
typedef vector<string> vs;
typedef pair<ll, ll> iil;
typedef vector<iil> viil;

#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0 ; i < n ; i++)
#define INF 1000000000

void solve() {
    int m, n;
    cin >> m >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    int df = 0;
    int mx = 0;
    for (int i = 1 ; i < n ; i++) {
        df += a[i] - a[i - 1];
        mx = max(mx, a[i] - a[i - 1]);
    }
    df += a[0] + m - a[n - 1];
    mx = max(mx, a[0] + m - a[n - 1]);
    cout << df - mx << endl;
}

void querySolve() {
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    //querySolve();
    solve();
}


Measured memory_bytes: 1152
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
b=gets.chomp.split(" ").map(&:to_i)
c=gets.chomp.split(" ").map(&:to_i)
res=0
(a.size-1).times do|i|
	res+=b[a[i]-1]
	if(a[i]+1==a[i+1])	
		res+=c[a[i]-1]
	end
end
res+=b[a[n-1]-1]
puts res

Measured memory_bytes: 1788
package main

import (
	"fmt"
	"math"
)

func main() {
	var n, k int
	var h, dp []int
	fmt.Scanf("%d %d", &n, &k)
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Scanf("%d", &tmp)
		h = append(h, tmp)
	}
	for i := 0; i < n; i++ {
		dp = append(dp, math.MaxInt64)
	}
	dp[0] = 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n && j <= i+k; j++ {
			tmp := dp[i] + abs(h[j]-h[i])
			if tmp < dp[j] {
				dp[j] = tmp
			}
		}
	}
	fmt.Println(dp[n-1])
}
func abs(in int) int {
	if in >= 0 {
		return in
	} else {
		return -in
	}
}
func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}


Measured memory_bytes: 8844
//#define LOCAL

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <climits>
#include <set>

//#define int long long
//typedef long long ll;
using ll = long long;
using R = double;

//#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

#define MOD 1000000007

using namespace std;

typedef vector<int> V;
typedef vector<V> VV;

ll C[51][51];

void comb_table(int N)
{
    for (int i=0; i<=N; i++) {
        for (int j=0; j<=i; j++) {
            if (j == 0 or j == i) {
                C[i][j] = 1LL;
            } else {
                C[i][j] = C[i-1][j-1] + C[i-1][j];
            }
        }
    }
}

signed main()
{
#ifdef LOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif

    int N, A, B;
    const int NMAX = 50;
    ll v[NMAX];

    cin >> N >> A >> B;
    REP(i,N) cin >> v[i];

    comb_table(N);
    sort(v, v + N);
    reverse(v, v + N);

    R max_average = 0.0;
    REP(i,A) {
        max_average += v[i];
    }
    max_average /= A;

    int a_th_val_num = 0, a_th_val_pos = 0;
    for (int i=0; i<N; i++) {
        if (v[i] == v[A-1]) {
            a_th_val_num++;
            if (i < A) {
                a_th_val_pos++;
            }
        }
    }

    ll cnt = 0LL;
    if (a_th_val_pos == A) {
        for (a_th_val_pos=A; a_th_val_pos<=B; a_th_val_pos++) {
            cnt += C[a_th_val_num][a_th_val_pos];
        }
    } else {
        cnt += C[a_th_val_num][a_th_val_pos];
    }

    cout.precision(20);
    cout << fixed << max_average << endl;
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int  oth=0;
	long int W, H;
	double men,x, y;
	scanf("%ld %ld %lf %lf", &W, &H, &x, &y);
	men = (double)W * H / 2;
	if (x == (double)W / 2 && y == (double)H / 2)
	{
		oth = 1;
	}
	printf("%lf %d", men, oth);
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main()
{
	long long n,k;
	cin>>n>>k;
	if(n%k<(k-n%k)) cout<<n%k<<endl;
	else cout<<k-n%k<<endl;
	return 0;
}
/*
39-14=25
25-14=11
11-14=3
3-14=11

3-7=4
4-7=3

*/

Measured memory_bytes: 256
using System;
class Program
{
	static void Main(string[] args)
	{
		
		string[] input = Console.ReadLine().Split(' ');
		int a = int.Parse(input[0]);
		int b = int.Parse(input[1]);
        int aa=a;
        int bb=b;
        int Akekka=0;
        int Bkekka=0;
        
        //Console.WriteLine(Akekka);
		for(int i=0;i<b;++i){
          Akekka+=a;
          a=a*10;
        }
        a=aa;
        for(int i=0;i<a;++i){
          Bkekka+=b;
          b=b*10;
        }
        if(Akekka>Bkekka){
          Console.WriteLine(Akekka);
        }
        else{
          Console.WriteLine(Bkekka);
        }
	}
}

Measured memory_bytes: 11092