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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
struct segtree{
private:
  vector<P> node;
  int siz;
public:
  segtree(int n){
    siz=1;
    while(siz<=n) siz*=2;
    node.resize(siz*2+1,P(0,0));
  }
  void upd(int pos,P x){
    pos+=siz-1;
    node[pos]=x;
    while(pos>0){
      pos=(pos-1)/2;
      node[pos]=max(node[pos*2+1],node[pos*2+2]);
    }
  }
  P get_max(int a,int b,int pos,int l,int r){
    if(a<=l&&r<=b) return node[pos];
    if(r<=a||b<=l) return P(0,0);
    int mid=(l+r)/2;
    P lb=get_max(a,b,pos*2+1,l,mid);
    P rb=get_max(a,b,pos*2+2,mid,r);
    return max(lb,rb);
  }
  P max_q(int a,int b){
    return get_max(a,b,0,0,siz);
  }
};
int main(){
  ll n,m;
  cin>>n>>m;
  string s;
  cin>>s;
  vector<ll> vec,ans;
  segtree seg=segtree(n+10);
  for(ll i=n;i>=0;i--) vec.push_back(s[i]=='0'?1:0);
  for(int i=0;i<=n;i++) seg.upd(i,P(vec[i],i));
  ll pos=0;
//  for(int i=0;i<=n;i++) cout<<vec[i]<<" ";
//  cout<<endl;
  while(pos<n){
    P p=seg.max_q(pos+1,min(pos+m+1,n+1));
  //  cout<<pos<<endl;
  //  cout<<p.first<<" "<<p.second<<endl;
    if(p.first==0) {
      cout<<-1<<endl;
      return 0;
    }
    ans.push_back(p.second-pos);
    pos=p.second;
  }
//  cout<<ans.size()<<endl;
  for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<(i==0?"\n":" ");
}


Measured memory_bytes: 6772
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

int c[3][3];
int main(){
  rep(i,3)rep(j,3)cin>>c[i][j];
  bool ok=1;
  rep(i,2)rep(j,2)
    if(c[i+1][j+1]-c[i+1][j]!=c[0][j+1]-c[0][j])ok=0;
  rep(i,2)rep(j,2)
    if(c[i+1][j+1]-c[i][j+1]!=c[i+1][0]-c[i][0])ok=0;
  cout<<(ok?"Yes":"No")<<endl;
}


Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXN = 200;

int mod;
int choose[MAXN + 1][MAXN + 1];
int fac[MAXN + 1];

void inc(int &a, int b) { if ((a += b) >= mod) a -= mod; }

int dp[MAXN + 1][MAXN + 1]; // dp[i][j] = ways to fill in x[i..na) with values j or greater, such that the constaint is satisfied for a[i..na) and b[j..nb) with the remaining values of x being j or less

int calccyc(int n, int lim) {
	int ret = 0;
	FORE(na, 1, min(n - 2, lim)) {
		int nb = n - na - 1;
		if (nb > lim) continue;
		for (int i = na; i >= 0; --i) for (int j = nb; j >= 0; --j) {
			if (i == na && j == nb) { dp[i][j] = 1; continue; }
			dp[i][j] = 0;
			if (i < na && i + nb - j <= lim && (j < nb || i>0)) inc(dp[i][j], dp[i + 1][j]);
			if (j < nb && j + na - (i - 1) <= lim) inc(dp[i][j], dp[i][j + 1]);
		}
		int mult = (ll)choose[n - 1][na] * fac[na] % mod*fac[nb] % mod;
		//printf("\t%d/%d -> %d*%d\n", na, nb, mult, dp[0][0]);
		ret = (ret + (ll)mult*dp[0][0]) % mod;
	}
	//printf("calccyc(%d,%d)=%d\n", n, lim, ret);
	return ret;
}

int n, lim;

int solve() {
	REPE(i, n) { choose[i][0] = choose[i][i] = 1; FOR(j, 1, i) choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % mod; }
	fac[0] = 1; FORE(i, 1, n) fac[i] = (ll)fac[i - 1] * i % mod;

	int ret = 0;
	REPE(nsingle, n) {
		int mult = (ll)choose[n][nsingle] * fac[nsingle] % mod;
		int rem = n - nsingle;
		if (rem == 1 || rem == 2) continue;
		int ways;
		if (rem == 0) {
			if (lim < nsingle - 1) continue;
			ways = 1;
		} else {
			int remlim = lim - nsingle;
			if (2 * remlim < rem - 1) continue;
			ways = calccyc(rem, remlim);
		}
		ret = (ret + (ll)mult*ways) % mod;
	}
	return ret;
}

void run() {
	scanf("%d%d%d", &n, &lim, &mod);
	printf("%d\n", solve());
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 4120
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] num = str.split(" ");
		int m = Integer.parseInt(num[0]);
		long n = Integer.parseInt(num[1]);
		long ans = 1;
		long m1000 = 1;
		long r = n % 1000;
		long k = (n - r) / 1000;
		if (r == 0) {
			r += 1000;
			k -= 1;
		}
		if (n > 10_000_000) {
			for (int i = 0; i < 1000; i++)
				m1000 = (m1000 * m) % 1_000_000_007;
			for (int i = 0; i < k; i++)
				ans = (ans * m1000) % 1_000_000_007;
			for (int i = 0; i < r; i++)
				ans = (ans * m) % 1_000_000_007;
			System.out.println(ans);
		}else{
			for (int i = 0; i < n; i++)
				ans = (ans * m) % 1_000_000_007;
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 25096
#include <stdio.h>
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define MOD 1000000007
typedef long long ll;
#include <string.h>

int main(){
	char s[101], t[201];
	scanf("%s%s", s, t);
	strcat(t, s);
	printf(t);
	return 0;
}

Measured memory_bytes: 128
import sys
def hit_blow(num):
   hits = 0
   blows = 0
   emp1 = [0,0,0,0]
   emp2 = [0,0,0,0]
   num.append(emp1)
   num.append(emp2)
   for i in range(0,4):
       i = i*2
       for j in range(0,4):
           j = j*2
           if num[0][i] == num[1][j] and num[2][int(i/2)] == 0 and num[3][int(j/2)] == 0:
               if i ==j :
                   hits += 1
               else:
                   blows += 1
               num[2][int(i/2)] = 1
               num[3][int(j/2)] = 1
   print(hits,blows)

flag = 0
num = []
for line in sys.stdin.readlines():
   if flag == 0:
       num.append(line)
       flag = 1
   elif flag == 1:
       num.append(line)
       flag = 2
   if flag == 2:
       flag = 0
       hit_blow(num)
       del num[:]

Measured memory_bytes: 7468
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double lb;
const ll MOD=1e9+7;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
void IOS(){	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);return ;}
ll n,k;
ll dp[100005],u[105];
int f(ll l){
	if(l==0)return 0;
	if(dp[l]!=-1)return dp[l];
	REP(i,n){
		if(l>=u[i]&&f(l-u[i])==0){
			return dp[l]=1;
		}
	}
	return dp[l]=0;
}

int main(){
	IOS();
	memset(dp,-1,sizeof(dp));
	cin>>n>>k;
	REP(i,n){
		cin>>u[i];
	}
	cout<<(f(k)==1?"First":"Second");
	return 0;
}

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

using namespace std;

int main() {
	char b;
	cin >> b;
	char c = 'C';
	if (b == 'A')c = 'T';
	if (b == 'T')c = 'A';
	if (b == 'C')c = 'G';

	cout << c << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <climits>
using namespace std;

#define MOD1097 1000000007

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mpair make_pair
#define pm(first, second) pb(mpair(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(X) (X).begin(), (X).end()
#define reall(X) (X).rbegin(), (X).rend()
#define divcel(a, b) (((a) + ((b) - 1)) / (b))

int main(){

	string S;
	cin >> S;
	char c = S[S.size()-1];
	switch(c){
		case '2':
		case '4':
		case '5':
		case '7':
		case '9':
			cout << "hon" << endl;
			break;
		case '0':
		case '1':
		case '6':
		case '8':
			cout << "pon" << endl;
			break;
		case '3':
			cout << "bon" << endl;
			break;
	}

	return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#define myfor(i,N) for(i=0;i<N;i++)
#define myforFL(i,f,l) for(i=f;i<l;i++)
#define myforInv(i,N) for(i=N;i>=0;i--)
#define myforFLInv(i,f,l) for(i=f;i>l;i--)
#define INF pow(10,14)
using namespace std;

int main(){
	int i,j,k,l;
	long N,M,X,C[12],A[12][12],B[12],cost,anscost = INF;
	cin >> N >> M >> X;
	myfor(i,N){
		cin >> C[i];
		myfor(j,M){
			cin >> A[i][j];
		} 
	}
	for(i=0;i<(1<<N);i++){
		myfor(l,M)B[l] = 0;
		cost = 0;
		for(j=0;j<N;j++){
			if(i & (1 << j)){
				myfor(k,M)B[k] += A[j][k];
				cost += C[j];
			}
		}
		myfor(l,M){
			if(B[l] < X)cost = INF;
		}
		anscost = min(anscost,cost);
	}
	if(anscost != INF)cout << anscost << endl;
	else cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 3220
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a


def lcm(a,b):
    return (a*b) // gcd(a,b)


N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

t = T[0]
for i in range(N - 1):
    t = lcm(t,T[i+1])
print(t)

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

main(){
  string L = "qwertasdfgzxcvb";
  string R = "yuiophjklnm";
  string str;
  char M[256];
  for ( int i = 0; i < L.size(); i++ ) M[L[i]] = 1;
  for ( int i = 0; i < R.size(); i++ ) M[R[i]] = 2;

  while(1){
    cin >> str;
    if ( str == "#" ) break;
    int pre = M[str[0]];
    int cnt = 0;
    for ( int i = 1; i < str.size(); i++ ){
      if ( M[str[i]] != pre ) cnt++;
      pre = M[str[i]];
    }
    cout << cnt << endl;
  }
  return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;


int main(){
  int n,x; 
  cin >> n >> x;
  vector<int> l(110,0);
  rep(i,n){ cin >> l[i];}
  int d=0,ans=0;
  while(x>=d && ans<n+1){
    d += l[ans];
    ans++;
  }
  cout << ans <<endl;
  return 0;
}


Measured memory_bytes: 256
N, W = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        if j - w[i][0] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i][0]] + w[i][1])

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[N][W])


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

using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define chmin(x,y) x = min(x,y)
using ll = long long;
using ld = long double;
using Pint = pair<int, int>;
const ll mod = 1e9+7;

const int INF = 1001001001;
int dp[1000001][2];

int main(int argc, char const* argv[])
{
  string s;
  cin>>s;
  reverse(ALL(s));
  s += '0';
  int n = s.size();
  REP(i,n+1)REP(j,2) dp[i][j] = INF;
  dp[0][0] = 0;

  REP(i,n)REP(j,2) {
    int x = s[i] - '0';
    x += j;
    if(x<10) chmin(dp[i+1][0], dp[i][j]+x);
    if(x>0) chmin(dp[i+1][1], dp[i][j]+(10-x));
  }
  int ans = dp[n][0];

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 9220
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    int[][] c = new int[3][3];

    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        c[i][j] = sc.nextInt();
      }
    }

    sc.close();

    int b0b1_1 = c[0][0] - c[0][1];
    int b1b2_1 = c[0][1] - c[0][2];

    int b0b1_2 = c[1][0] - c[1][1];
    int b1b2_2 = c[1][1] - c[1][2];
    
    int b0b1_3 = c[2][0] - c[2][1];
    int b1b2_3 = c[2][1] - c[2][2];
    
    int a0a1_1 = c[0][0] - c[1][0];
    int a1a2_1 = c[1][0] - c[2][0];
    
    int a0a1_2 = c[0][1] - c[1][1];
    int a1a2_2 = c[1][1] - c[2][1];
    
    int a0a1_3 = c[0][2] - c[1][2];
    int a1a2_3 = c[1][2] - c[2][2];

    String result = "No";

    if (b0b1_1 == b0b1_2 && b0b1_2 == b0b1_3) {
      if (b1b2_1 == b1b2_2 && b1b2_2 == b1b2_3) {
        if (a0a1_1 == a0a1_2 && a0a1_2 == a0a1_3) {
          if (a1a2_1 == a1a2_2 && a1a2_2 == a1a2_3) {
            result = "Yes";
          }
        }
      }
    }

    System.out.println(result);

  }

}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
void display()
{
    int a, b, c, d;
    cin>>a>>b>>c>>d;
    puts(a+b == c+d ? "Balanced" : a+b > c+d ? "Left" : "Right");
}
int main(void)
{
    display();
}


Measured memory_bytes: 3508
#include<bits/stdc++.h>
#define INFTY 10000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
const int MOD=1000000007;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int INF = 1e9;
int main(){
    string s,t;cin>>s>>t;
    int ans = t.length();
    int sz = s.length(),tz = t.length();
    int x = 0;
    while(x<sz-tz+1){
        int cnt = 0;
        rep(i,tz){
            if(s[x+i]==t[i])cnt++;
        }
        ans = min(ans,tz-cnt);
        //cout<<cnt<<endl;;
        x++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+1];
	for(int i=1;i<=n;++i)
		cin>>a[i];
	sort(a+1,a+n+1);
	int sum1=0,sum2=0;
	for(int i=1;i<=n;++i)
		if(i%2==1)
			sum1+=a[i];
		else
			sum2+=a[i];
	cout<<fabs(sum1-sum2);
	return 0;
 } 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVETSE(c) reverse((c).begin(),(c).end())
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define ALL(a)  (a).begin(),(a).end()
// int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> T maxt(T x,T y) {
    if (x>y) return x;
    else return y;
}
template<class T> T mint(T x,T y) {
    if (x>y) return y;
    else return x;
}
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

long long m = 1e9+7, mod = 1e9+7;
//逆元　a/b の modをとるとき -> a*modinv(b)%mod
long long modinv(long long a, long long m = 1e9+7) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

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



int main() {
  int N,K;
  ll a,ans=0,c;
  Vl A;
  cin >> N >> K;
  REP(i,N) {
    cin >> a;
    A.push_back(a);
  }
  SORT(A);
  FOR(i,K-1,N) {
    if (i==K-1) c = 1;
    else {
        c = c*(i)%mod*modinv(i-K+1)%mod;
    } 
    // cout << c << endl;
    ans = ( ans + (A[i] - A[N-1-i])*c%mod)%mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
typedef pair<int, int> Pii;
typedef vector<int> Vi;
const int INF = (1<<30);
const int dx[]={-1,0,1,1,1,0,-1,-1}, dy[]={-1,-1,-1,0,1,1,1,0};

int main()
{
  int h, w;
  int maps[1000][1000];
  int cnt[1000][1000] = {0};
  queue<Pii> q;

  cin >> h >> w;
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      char c;
      cin >> c;
      if( c == '.' ) {
	maps[i][j] = 0;
	for(int l=0; l<8; l++) {
	  int nx = j+dx[l], ny = i+dy[l];
	  if( 0 <= nx && nx < w && 0 <= ny && ny < h ) {
	    cnt[ny][nx]++;
	  }
	}
      }
      else {
	maps[i][j] = c - '0';
	q.push(Pii(i, j));
      }
    }
  }

  bool flag = true;
  int ans = 0;
  while( 1 ) {
    vector<Pii> v;
    flag = false;
    int tmp = q.size();
    for(int i=0; i<tmp; i++) {
      Pii p = q.front(); q.pop();
      int x = p.sc, y = p.fr;
      if( maps[y][x] && maps[y][x] <= cnt[y][x] ) {
	flag = true;
	maps[y][x] = 0;
	v.pb(Pii(y, x));
      }
    }
  

    if( !flag ) {
      break;
    }
    for(int i=0; i<v.size(); i++) {
      for(int l=0; l<8; l++) {
	int nx = v[i].sc+dx[l], ny = v[i].fr+dy[l];
	if( 0 <= nx && nx < w && 0 <= ny && ny < h ) {
	  cnt[ny][nx]++;
	  q.push(Pii(ny, nx));
	}
      }
    }
 
    ans++;
  }

  cout << ans << endl;
}

Measured memory_bytes: 16920
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	int n,m;
	int i,j,k;
	char s[100000];
	cin >> a >> b>> c;
	int t=b+c-a;
	if(t<0)t=0;
	cout << t;
}

Measured memory_bytes: 256
/*
AIZU ONLINE JUDGE ??????
???Reversing Numbers??????????????????
-----------------------------------------------------------------*/


#include<iostream>//???????????????<iostream>?????????????????????
using namespace std;

/*???????????¢??°*/
int main(){
	
	/*??°?????????????????°??£?¨?*/
	int size;
	cin>>size;//???????????°????????????????????????
	
	int array[size];
	int result[size];//???????????°??£?¨?
	
	
	/*??°?????????????????°"array"?????\???*/
	for(int i=0;i<size;i++){
		
		cin>>array[i];
		
	}
	
	
	/*?????????*/
	for(int j=0;j<size;j++){
	
		result[j]=array[size-j-1];
		
	}
	
	
	/*???????????????*/
	for(int k=0;k<size-1;k++){
	
		cout<<result[k]<<" ";
	}
	
	cout<<result[size-1]<<"\n";
	
	
	return 0;//??????
	
}

Measured memory_bytes: 1164
#[allow(unused_imports)]
use std::cmp::{min, max};

use io::*;

fn main() {
    let input = read_string();
    let mut sc = Scanner::new(&input);
    let s = sc.next_vec_char();
    let q: usize = sc.next();
    let mut flip = false;
    let mut head = vec![];
    let mut tail = vec![];
    for _ in 0..q {
        let t: usize = sc.next();
        if t == 1 {
            flip = !flip;
        } else {
            let f = sc.next::<usize>() == 2;
            let c = sc.next_vec_char()[0];
            if flip ^ f {
                tail.push(c);
            } else {
                head.push(c);
            }
        }
    }
    if flip {
        print!("{}", tail.iter().rev().cloned().collect::<String>());
        print!("{}", s.iter().rev().cloned().collect::<String>());
        println!("{}", head.iter().cloned().collect::<String>());
    } else {
        print!("{}", head.iter().rev().cloned().collect::<String>());
        print!("{}", s.iter().cloned().collect::<String>());
        println!("{}", tail.iter().cloned().collect::<String>());
    }
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }

        pub fn next_mat<T: FromStr>(&mut self, w: usize, h: usize) -> Vec<Vec<T>> {
            (0..h).map(|_| self.next_vec(w)).collect()
        }

        pub fn next_vec_char(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }

        pub fn next_mat_char(&mut self, n: usize) -> Vec<Vec<char>> {
            (0..n).map(|_| self.next_vec_char()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


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

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args) {
        int K = in.i();
        int T = in.i();
        int[] a = in.ii(T);
        int max = 1;
        for (int i = 0; i < T; i++) {
            max = Math.max(max, a[i]);
        }
        int ans = Math.max(0, 2 * max - K - 1);
        System.out.println(ans);
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = super.read(cbuf, 0, cbuf.length);
            } catch (IOException e) {
                e.printStackTrace();
            }
            head = 0;
        }
        return cbuf[head++];
    }

    int i() {
        int k = next() - '0';
        boolean minus = k == -3;
        int n = minus ? 0 : k;
        while (0 <= (k = next() - '0') && k <= 9) n = 10 * n + k;
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }

    long l() {
        int k = next() - '0';
        boolean minus = k == -3;
        long n = minus ? 0 : k;
        while (0 <= (k = next() - '0') && k <= 9) n = 10 * n + k;
        return minus ? -n : n;
    }

    char[] s(final int N) {
        char[] s = new char[N];
        for (int i = 0; i < N; i++) {
            s[i] = next();
        }
        next();
        return s;
    }

    public int read(char[] cbuf) {
        int i;
        char c;
        for (i = 0; (c = next()) != ' ' && c != '\n'; i++) cbuf[i] = c;
        return i;
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }
}


Measured memory_bytes: 32624
N = int(input())

def factorize(n):
    if n == 1: return []
    res = []
    x, y = n, 2
    while y * y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

from collections import Counter

F = factorize(N)
C = Counter(F)


res = 0

if N == 1:
    print(0)
else:
    for k, v in C.items():
        tmp = 0
        while True:
            if (tmp + 1) * (tmp + 2) // 2 > v:
                res += tmp
                break
            tmp += 1

    print(res)

Measured memory_bytes: 65828
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    int xi;
    vector<int> X(n);
    float S = 0.;
    for (int i=0; i<n; i++){
        cin >> X[i];
        S += X[i];
    }
    int mu = round(S / n);
    int distance = 0;
    for (int i=0; i<n; i++) {
        distance += pow(X[i] - mu, 2);
    }
    cout << distance << endl;

}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define lim 1000000000000000007
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(),v.end()
#define mod ((int)1e9+7)
using namespace std;
typedef long long int ll;
typedef pair<int,int> pi;
const int N = (int)1e5+5;

void solve() {
  int n,x,t;
  cin>>n>>x>>t;
  cout<<(n+x-1)/x*t;
}

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

  int T=1;
  //cin>>T;
  REP(TC,1,T) {
      //cout<<"Case #"<<TC<<": ";
      solve();
      cout<<"\n";
  }
}


Measured memory_bytes: 3652
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[m];
        int[] b = new int[m];
        int[] road = new int[n];
        Arrays.fill(road, 0);
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            road[a[i] - 1]++;
            road[b[i] - 1]++;
        }
        for (int i = 0; i < n; i++) {
            System.out.println(road[i]);
        }
    }
}


Measured memory_bytes: 22868
// C - /\/\/\/
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define allr(x) (x).rbegin(),(x).rend()
#define fst first
#define snd second

int main(){
	int N; cin>>N;
	vector<pair<int,int>> E(100000),O(100000);//[value]<count,value>
	rp(i, 0, N/2){
		int e,o; cin>>e>>o; e--;o--;
		E[e].fst++; E[e].snd = e+1;
		O[o].fst++; O[o].snd = o+1;
	}
	sort(allr(E)); sort(allr(O));
	int ans = N;
	ans -= E[0].snd != O[0].snd? E[0].fst + O[0].fst:
		max(E[0].fst + O[1].fst, E[1].fst + O[0].fst);
	cout<< ans <<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define vi vector<int>
#define ll long long
#define pb push_back
#define ii pair<int, int>
#define qi queue<int>
#define si stack<int>
#define mii map<int, int>
#define msi map<string, int>
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
using namespace std;

const int MAX = 1e3+5;
const int mod = 1e9+7;

bitset<MAX> bs;
vi primes;

void sieve() {
	bs.set();
	bs[0] = bs[1] = 0;

	for (int i = 2; i < MAX; i++) {
		if (bs[i])
			primes.pb(i);
		for (int p : primes) {
			if (i*p >= MAX)
				break;
			bs[i*p] = 0;

			if (i%p == 0)
				break;
		}
	}
}

mii ans;

void numDiv(int n) {

	for (int cur : primes) {
		if (cur*cur > n)
			break;

		int ctr = 0;

		while (n%cur == 0) {
			n/= cur;
			ctr++;
		}

		if (ctr > 0)
			ans[cur] += ctr;
	}


	if (n > 1)
		ans[n] += 1;

}


int main(int argc, char** argv) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	sieve();

	int n;
	cin >> n;

	for (int i = 2; i <= n; i++) 
		numDiv(i);

	ll c = 1;

	for (auto e : ans)
		c = (c * (e.sc+1))%mod;

	cout << c << '\n';

	//cin >> n;


	return 0;
}


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

#define NMAX 8

int n, m;
bool graph[NMAX + 1][NMAX + 1];
bool visited[NMAX + 1];

void initialize_graph() {
  int i, j;

  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      graph[i][j] = false;
    }
  }

  return;
}

bool all_visited() {
  int i;
  for (i = 0; i < n; i++) {
    if (visited[i] == false) {
      return false;
    }
  }
  return true;
}

int dfs(int u) {
  int v, ret = 0;

  visited[u] = true;

  if (all_visited()) {
    return 1;
  } else {
    for (v = 0; v < n; v++) {
      if (graph[u][v] == true && visited[v] == false) {
        visited[v] = true;
        ret += dfs(v);
        visited[v] = false;
      }
    }
  }
  return ret;
}

int main() {

  int i, a, b;

  cin >> n >> m;

  initialize_graph();

  for (i = 0; i < m; i++) {
    cin >> a >> b;
    graph[a - 1][b - 1] = true;
    graph[b - 1][a - 1] = true;
  }

  cout << dfs(0) << '\n';

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    char c[20];
    scanf("%s",&c);
    string s=c;
    reverse(s.begin(),s.end());
    printf("%s\n",s.c_str());
    return 0;
}

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

#define int long long
#define ld long double

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>b;i--)

#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second

#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";

const int logN = 20;
const int M = 1000000007;
const int INF = 1e12;
#define PI 3.14159265;
const int N = 200005;

#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>

void solve()
{
       int n,n1=0,n2=0,n3=0,n4=0;
       cin>>n;
       rep(c,0,n)
       {
              string s;
              cin>>s;
              if(s=="AC")
              {
                     n1++;
              }
              else if(s=="WA")
              {
                     n2++;
              }
              else if(s=="TLE")
              {
                     n3++;
              }
              else
              {
                     n4++;
              }
       }
       cout<<"AC x "<<n1<<"\n";
       cout<<"WA x "<<n2<<"\n";
       cout<<"TLE x "<<n3<<"\n";
       cout<<"RE x "<<n4<<"\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--)
    {
           solve();
    }
    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
int N,M;int D[100000]={0},parent[100000];
int calculate[100000]={0};
vector<vector<int>> family(100000,vector<int>());
int below;
void dfs(int node){
    if(calculate[node]==0){
        for(int i=0;i<family[node].size();i++){
            below=family[node][i];
            calculate[below]--;
            if(D[below]<D[node]+1){
                D[below]=D[node]+1;
                parent[below]=node;
            }if(calculate[below]==0){
                dfs(below);
            }
        }
    }return;
}
int main(){
    cin>>N>>M;
    int a,b;
    for(int i=0;i<N-1+M;i++){
        cin>>a>>b;
        family[a-1].push_back(b-1);
        calculate[b-1]++;
    }int root;
    for(int j=0;j<N;j++){
        if(calculate[j]==0){
            root=j;
            parent[j]=-1;
            break;
        }
    }dfs(root);
    for(int k=0;k<N;k++){        
        cout<<parent[k]+1<<endl;
    }
}

Measured memory_bytes: 12160
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;
#define Pi 3.1415926535897932384626
#define mod llint(1e9+7)

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

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

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//aCbを1000000007で割った余りを求める
llint convination(llint a, llint b) {
	llint ans = 1;
	for (llint i = 0; i < b; i++) {
		ans *= a - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= b; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

//aのb乗をmodで割った余りを求める
llint power(llint a, llint b) {
	if (b == 1)return a;
	if (b == 0)return 1;
	llint tmp = power(a, (llint)b / 2);
	tmp *= tmp;
	tmp %= mod;
	if (b % 2 == 1) {
		tmp *= a;
		tmp %= mod;
	}
	return tmp;
}

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	rep(i, s.size()) {
		if (s[i] + n > 'Z')cout << (char)(s[i] + n - 26);
		else cout << (char)(s[i] + n);
	}
	cout << endl;
	return 0;
}

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

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

    int cost_a = 0, cost_b = 0;

    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;

        if (a < x) {
            cost_a++;
        } else {
            cost_b++;
        }
    }

    cout << min(cost_a, cost_b) << endl;

    return 0;
}


Measured memory_bytes: 256
import numpy as np
n, k = list(map(lambda x: int(x), input().split(' ')))
su = list(range(1, n+1))
for i in range(int(k)):
  input()
  tmp = list(map(lambda x: int(x), input().split(' ')))
  for j in tmp:
    if j in su:
      su.remove(j)
  

print(len(su))

Measured memory_bytes: 27152
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

ll powmod(ll x, ll n) { // like pow(x, n)
  ll r = 1;
  while (n) {
    if (n & 1) {
      r = r * x % MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return r;
}

int main(int argc, char** argv) {
  int N;
  cin >> N;
  vector<ll> A(N);
  rep(i, N) {
    cin >> A[i];
  }
  vector<ll> B(N);
  rep(i, N) {
    cin >> B[i];
  }

  // If B[i] > B[i-1] + B[i+1], then we update B[i] -> B[i] % (B[i-1] + B[i+1])
  priority_queue<P> q; // The queue of pairs. The pair is [B[i], i].

  ll cnt = 0; // The count of operation.
  rep(i, N) {
    ll b = B[i];
    ll a = B[(i-1+N)%N];
    ll c = B[(i+1)%N];
    if ((b > a + c) && b != A[i]) {
      q.emplace(b, i);
    }
  }
  while (!q.empty()) {
    P p = q.top(); q.pop();
    int i = p.second;

    ll b = B[i];
    ll a = B[(i-1+N)%N];
    ll c = B[(i+1)%N];
    if ((b > a + c) && b > A[i]) {
      ll diff = (b - A[i]) / (a + c);
      B[i] -= diff * (a + c);
      cnt += diff; // cnt is the count of "B[i] = B[i] - (a + c)".
      q.emplace(a, (i-1+N)%N);
      q.emplace(c, (i+1)%N);
    }
  }
  // For Debug
  // cout << "after:" << endl;
  // rep(i, N) {
  //   cout << B[i] << " ";
  // }
  // cout << endl;

  bool ans = true;
  rep(i, N) {
    if (A[i] != B[i]) {
      ans = false;
      break;
    }
  }
  if (ans) {
    cout << cnt << endl;
  } else {
    cout << -1 << endl;
  }
}


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

int main(){
	char kata[19];
	scanf("%[^\n]", &kata);
	
	for(int i=0; i<19;i++){
		if(kata[i]== ','){
			printf(" ");
		}
		else {
		
		printf("%c", kata[i]);
	}
}
	return 0;
}

Measured memory_bytes: 1600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;
const ll MINF = LLONG_MIN;
const int INT_INF = INT_MAX;

int main()
{
    int n;
    cin >> n;
    vector<double> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    double res = 0.0;
    for (int i = 1; i < n; i++)
    {
        v[i] = (v[i - 1] + v[i]) / 2.0;
    }
    cout << v[n - 1] << endl;
}

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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n)　for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef string ss;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    y /= gcd(x,y);
    return (x*y);
}

int main()
{
    vs s(3);
    rep(i,3)cin >> s[i];
    cout << s[0][0] << s[1][1] << s[2][2] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0; i<n; ++i)
#define rep1(i,n) for(ll i=1; i<=n; ++i)
#define revrep(i,n) for(ll i=n-1; i>=0; --i)
inline constexpr ll Inf = (1ULL << 62) -1;
#define fastio cin.tie(nullptr); ios_base::sync_with_stdio(false);
#define endl '\n'
template <class T> bool updmax(T& a, T b) { if (b > a) { a = b; return true;} return false;}
template <class T> bool updmin(T& a, T b) { if (b < a) { a = b; return true;} return false;}

int main() {
    fastio;
    ll N;
    cin >> N;
    vector<vector<int>> g(N);
    map<pair<int,int>,int> weight;
    map<int,int> color;
    rep(i,N-1) {
        int u,v,w;
        cin >> u >> v >> w;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
        weight[{u,v}] = w;
    }
    queue<int> q;
    q.push(0);
    color[0] = 1;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int t : g[v]) {
            if (color[t] != 0)
                continue;
            int a = v, b = t;
            if (a > b) swap(a,b);
            if (weight[{a,b}] % 2)
                color[t] = 3-color[v];
            else
                color[t] = color[v];
            q.push(t);
        }
    }
    rep(i,N) {
        cout << (color[i]-1) << endl;
    }
}


Measured memory_bytes: 19876
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
import decimal
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N = INT()
    x = []
    y = []
    for _ in range(N):
        xx,yy = MAP()
        x.append(xx)
        y.append(yy)
    x = [(x[i],i) for i in range(N)]
    y = [(y[i],i) for i in range(N)]
    x.sort()
    y.sort()
    edges = []
    for i in range(N-1):
        edges.append((x[i][1],x[i+1][1],x[i+1][0]-x[i][0]))
        edges.append((y[i][1],y[i+1][1],y[i+1][0]-y[i][0]))
    edges.sort(key=lambda x:x[2])
    uf = UnionFind(N)
    answer = 0
    for i in range(len(edges)):
        s,t,w = edges[i]
        if not uf.same(s,t):
            uf.union(s,t)
            answer += w
    print(answer)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 58816
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
//long long mo = 1e9 + 7;

typedef struct Maze{
    int h;
    int w;
    int d;
} MAZE;

int main(){
    int H,W;
    int nwh=0, nbl=0;
    cin >> H >> W;
    vector<vector<char>> S(H, vector<char>(W, '0'));
    vector<vector<int>> Dist(H, vector<int>(W, -1));
    rep(i,H){
        rep(j,W){
            cin >> S[i][j];
            if(S[i][j] == '.'){
                nwh++;
            }else{
                nbl++;
            }
        }
    }
    queue<MAZE> que;
    MAZE tmp_m = {0,0,0};
    que.push(tmp_m);
    bool goal_f = false;
    while(!que.empty()){
        MAZE m = que.front();
        que.pop();
        if(!(0 <= m.h && m.h < H))continue;
        if(!(0 <= m.w && m.w < W))continue;
        if(S[m.h][m.w] == '#')continue;
        if(Dist[m.h][m.w] != -1)continue;
        Dist[m.h][m.w] = m.d;
        if(m.h == H - 1 && m.w == W - 1){
            goal_f = true;
            break;
        }
        que.push(MAZE{m.h-1, m.w, m.d +1});
        que.push(MAZE{m.h+1, m.w, m.d +1});
        que.push(MAZE{m.h, m.w-1, m.d +1});
        que.push(MAZE{m.h, m.w+1, m.d +1});
        //H-1, W-1
    }
    int ans = -1;
    if(goal_f){
        ans = (nwh - (Dist[H-1][W-1] + 1));
    }

    cout << ans << endl;
}



Measured memory_bytes: 256
s=input()
p=input()
no=True
for i in range(len(s)):
    ok=True
    for j in range(len(p)):
        if s[(i+j)%len(s)]!=p[j]:
            ok=False
            break
    if ok:
        print('Yes')
        no=False
        break
if no:
    print('No')


Measured memory_bytes: 5560
#include <bits/stdc++.h>
typedef long long ll;

const int N=5005,P=1e9+7;

int n,f[N][N],g[N],t[N],s[N];
std::vector<int> G[N];

void DFS(int x)
{
	f[x][s[x]=1]=1;
	for(int y:G[x])if(!s[y])
	{
		DFS(y);
		for(int i=1;i<=s[x]+s[y];++i)t[i]=0;
		for(int i=1;i<=s[x];++i)
			for(int j=0;j<=s[y];++j)
				t[i+j]=(t[i+j]+(ll)f[x][i]*f[y][j])%P;
		s[x]+=s[y];
		for(int i=1;i<=s[x];++i)f[x][i]=t[i];
	}
	for(int i=2;i<=s[x];i+=2)f[x][0]=(f[x][0]-(ll)f[x][i]*g[i]%P+P)%P;
}

int main()
{
	scanf("%d",&n),*g=1;
	for(int i=2;i<=n;i+=2)g[i]=g[i-2]*(i-1ll)%P;
	for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
	return DFS(1),printf("%d\n",P-f[1][0]),0;
}


Measured memory_bytes: 97408
import math
N,D = map(int,input().split())
lists = []
seisuu = []
cnt = 0
for i in range(N):
    X = list(map(int,input().split()))
    lists.append(X)
for i in range(N):
    for j in range(i+1,N):
        list_A = lists[i]
        list_B = lists[j]
        cnt = 0
        for k in range(D):
            cnt += abs(list_A[k] - list_B[k])**2
        m = float(math.sqrt(cnt))
        if m.is_integer():
         seisuu.append(m)
print(len(seisuu))

Measured memory_bytes: 3064
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<stack>
#include<queue>
#include<sstream>
#include<string>


#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i);

using namespace std;

const int INF=1<<28;

int main(){
	int h,w;

	while(1){

		cin >>h>>w;
		if(h==0 && w==0)break;

		int len=h*h+w*w;

		int min_h=151,min_w=151;

		for(int i=1;i<=150;i++){
			for(int j=1;j<i;j++){
				if((i*i+j*j>len) || (i*i+j*j==len&&j>h)){
					if(((i*i)+(j*j) < min_h*min_h+min_w*min_w) ||(i*i+j*j == min_h*min_h+min_w*min_w && j < min_h)){
						min_h=j;
						min_w=i;
					}
				}
			}
		}

		cout <<min_h<<" "<<min_w<<endl;

	}
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, k, p=-1000000;
    cin>>a>>b;
    p=max(p, a+b);
    p=max(p, a-b);
    p=max(p, a*b);
    cout<<p<<endl;
    return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
h = list(map(int,input().split()))
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(h[b])
    g[b].append(h[a])
ans = 0
for i in range(n):
    if len(g[i]) == 0:
        ans +=1
        continue
      
    if h[i] > max(g[i]):ans += 1
print(ans)
    

Measured memory_bytes: 23036
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <iomanip>
#include <vector>
#include <queue>
#include <numeric>
//#include <bits/stdc++.h>

using namespace std;
const int INF = 1 << 30;

int main()
{
    ios::sync_with_stdio(false);
    int n ,m;
    cin>>n>>m;
    cout<<n-m+1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll n,l,a[100000],key;
int main(void){
    cin>>n>>l;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        if(a[i-1]+a[i]>=l){
            key=i;
            break;
        }
    }
    if(key==0){
        cout<<"Impossible"<<endl;
        return 0;
    }
    cout<<"Possible"<<endl;
    for(int i=1;i<n;i++){
        if(i==key)break;
        cout<<i<<endl;
    }
    for(int i=n-1;i>=1;i--){
        if(i==key)break;
        cout<<i<<endl;
    }
    cout<<key<<endl;
}


Measured memory_bytes: 1664
# F - Playing Tag on Tree
# https://atcoder.jp/contests/abc148/tasks/abc148_f

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

n, u, v = map(int, input().split())
graph = [[] for _ in range(n)]

edge = [list(map(int, input().split())) for _ in range(n - 1)]

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))

from_u = dijkstra(n, graph, u - 1)
from_v = dijkstra(n, graph, v - 1)

# print(from_u)
# print(from_v)

fil = filter(lambda x : x[0] < x[1], [[fu, fv] for fu, fv in zip(from_u, from_v)])
sfil = sorted(list(fil), key=lambda x: [-x[1], -x[0]])  

# print(sfil)

print(sfil[0][1] - 1)


Measured memory_bytes: 85420