akhauriyash/Code-Regression huggingface dataset:
#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 , M ;
  ll ans = 0 ;
  cin >> N >> M ;
  vector<ll> A(N) ;
  map<ll,ll> mp ;
  rep(i,N) cin >> A.at(i) ;
  vector<ll> S(N+1) ;
  S.at(0) = 0 ;
  mp[S.at(0)]++ ;
  rep(i,N){
    S.at(i+1) = S.at(i) + A.at(i) ;
    S.at(i+1) %= M ;
    mp[S.at(i+1)]++ ;
  }
  for(auto p : mp ){
    ans += (p.second - 1 )*p.second / 2 ;
  }
  cout << ans << endl ;
}


Measured memory_bytes: 5760
#include<iostream>
using namespace std;
using ll = long long;

int main() {
  	int n;
    ll k;
	cin >> n >> k;
	ll num[100001] = {};
	for (int i = 0;i < n;i++) {
		int a, b;
		cin >> a >> b;
		num[a] += b;
	}
	for (int i = 1;i < 100001;i++) {
		if (num[i] >= k) {
			cout << i;
			break;
		}
		else k -= num[i];
	}
}


Measured memory_bytes: 1024
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    if W % 3 == 0:
        print(0)
    elif H % 3 == 0:
        print(0)
    else:
        ret = MAX
        for h in range(1, H):
            # 横, 横, 横 分割パターン
            hh = (H - h) // 2
            hmin = min(hh * W, (H - h - hh) * W, h * W)
            hmax = max(hh * W, (H - h - hh) * W, h * W)

            # 横, 縦, 縦 分割パターン
            ww = W // 2
            wmin = min((H - h) * (W - ww), (H - h) * ww, h * W)
            wmax = max((H - h) * (W - ww), (H - h) * ww, h * W)

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        for w in range(1, W):
            # 縦, 縦, 縦 分割パターン
            ww = (W - w) // 2
            wmin = min(w * H, (W - w - ww) * H, ww * H)
            wmax = max(w * H, (W - w - ww) * H, ww * H)

            # 縦, 横, 横 分割パターン
            hh = H // 2
            hmin = min(w * H, hh * (W - w), (H - hh) * (W - w))
            hmax = max(w * H, hh * (W - w), (H - hh) * (W - w))

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10124
#include <bits/stdc++.h>
#include <ext/hash_map>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define REP(i,n) for( (i)=0 ; (i)<(n) ; (i)++ )
#define rep(i,x,n) for( (i)=(x) ; (i)<(n) ; (i)++ )
#define REV(i,n) for( (i)=(n) ; (i)>=0 ; (i)-- )
#define FORIT(it,x) for( (it)=(x).begin() ; (it)!=(x).end() ; (it)++ )
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define rforeach(it,c) for(__typeof((c).rbegin()) it=(c).rbegin();it!=(c).rend();++it)
#define foreach2d(i, j, v) foreach(i,v) foreach(j,*i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SZ(x) ((int)(x).size())
#define MMS(x,n) memset(x,n,sizeof(x))
#define mms(x,n,s) memset(x,n,sizeof(x)*s)
#define pb push_back
#define mp make_pair
#define NX next_permutation
#define UN(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define CV(x,n) count(all(x),(n))
#define FIND(x,n) find(all(x),(n))-(x).begin()
#define ACC(x) accumulate(all(x),0)
#define PPC(x) __builtin_popcountll(x)
#define LZ(x) __builtin_clz(x)
#define TZ(x) __builtin_ctz(x)
#define mxe(x) *max_element(all(x))
#define mne(x) *min_element(all(x))
#define low(x,i) lower_bound(all(x),i)
#define upp(x,i) upper_bound(all(x),i)
#define NXPOW2(x) (1ll << ((int)log2(x)+1))
#define PR(x) cout << #x << " = " << (x) << endl ;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;

const int OO = (int) 2e9;
const double eps = 1e-9;

const int N = 100005;

int n;
ll a[N], b[N];

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
//	freopen("in.txt", "rt", stdin);
//	freopen("out.txt", "wt", stdout);
#endif
	ll res = 0, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i] >> b[i];
	for (int i = n - 1; i >= 0; i--) {
		a[i] += sum;
		ll cur = (b[i] - a[i] % b[i]) % b[i];
		res += cur;
		sum += cur;
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 1792
import math
from statistics import mean

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
xs = [x for x, y in xy]
ys = [y for x, y in xy]


def get_circle_center_and_radius(x1, y1, x2, y2, x3, y3):
    """
    3点を通る円の中心と半径を取得
    """
    d = 2 * ((y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3))
    if d == 0:
        x, y, r2 = -1, -1, -1
    else:
        x = ((y1 - y3) * (y1 ** 2 - y2 ** 2 + x1 ** 2 - x2 ** 2) -
             (y1 - y2) * (y1 ** 2 - y3 ** 2 + x1 ** 2 - x3 ** 2)) / d
        y = ((x1 - x3) * (x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2) -
             (x1 - x2) * (x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2)) / -d
        r2 = (x - x1) * (x - x1) + (y - y1) * (y - y1)
    return (x, y), r2


def get_circle_center_and_radius_2p(x1, y1, x2, y2):
    x = (x1 + x2) / 2
    y = (y1 + y2) / 2
    r2 = (x - x1) * (x - x1) + (y - y1) * (y - y1)
    return (x, y), r2


def solve_naive(N, xy):
    if N < 2:
        return 0
    ret = math.inf
    for i in range(N):
        for j in range(N):
            (cx, cy), r2 = get_circle_center_and_radius_2p(
                xy[i][0], xy[i][1], xy[j][0], xy[j][1])
            for x, y in xy:
                if (x - cx) * (x - cx) + (y - cy) * (y - cy) > r2:
                    r2 = math.inf
                    break
            ret = min(ret, r2)
            for k in range(N):
                if i == j or j == k or k == i:
                    continue
                (cx, cy), r2 = get_circle_center_and_radius(
                    xy[i][0], xy[i][1], xy[j][0], xy[j][1], xy[k][0], xy[k][1])
                for x, y in xy:
                    if (x - cx) * (x - cx) + (y - cy) * (y - cy) > r2:
                        r2 = math.inf
                        break
                ret = min(ret, r2)
    return math.sqrt(ret)


ans = solve_naive(N, xy)
print(ans)


Measured memory_bytes: 80312
import java.io.*;
import java.util.Scanner;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int d = sc.nextInt();

		String[] c = {"Christmas Eve Eve Eve", "Christmas Eve Eve", "Christmas Eve", "Christmas"};

		pr.println(c[d - 22]);
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 21204
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    int N,T,A,ans = 1;
    cin >> N >> T >> A;
    int h[N];
    for(int i = 0;i < N;i++){
        cin >> h[i];
    }
    double cnt = abs(A-(T-h[0]*0.006));
    for(int i = 0;i < N;i++){
        double tmp;
        tmp = abs(A-(T-h[i]*0.006));
        if(cnt > tmp){
            ans = (i+1);
            cnt = tmp;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll N;
	ll t[5] = {0LL};
	cin >> N;
	rep (i, 5) cin >> t[i];

	ll X = *min_element(t, t+5);
	ll res = ceil((double)N / (double)X) + 4LL;
	
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define pb push_back

typedef long long int ll;
const ll INF=1LL<<50;
struct Edge {
  ll to, cost;
  Edge(ll a, ll b){to=a;cost=b;}
};
vector<vector<Edge> > graph;
vector<ll> dist;

/* num of vertex is 'n', start at 's' */
bool bellman_ford(ll n, ll s) {
  //dist.resize(n, INF);
  //dist[s] = 0;

  for (ll i = 0; i <= n; i++) {
    for (ll v = 0; v < n; v++) {
      for (ll k = 0; k < graph[v].size(); k++) {
        Edge e = graph[v][k];
	if(dist[v]==INF) continue;
        if (dist[e.to] > dist[v] + e.cost) {
          dist[e.to] = dist[v] + e.cost;
          if (i == n) return true; /* detect cycle */
        }
      }
    }
  }
  return false;
}


int main(void){
  ll n,m,i,a,b,c;

  cin>>n>>m;
  graph.resize(n);
  for(i=0;i<m;i++){
    cin>>a>>b>>c;
    graph[a-1].pb(Edge(b-1,-c));
  }
  ll res1,res2;
  dist.resize(n, INF);
  dist[0]=0;
  bellman_ford(n,0);
  res1=-dist[n-1];
  bellman_ford(n,0);
  res2=-dist[n-1];
  if(res2>res1) cout<<"inf"<<endl;
  else cout<<res1<<endl;
  /*
    if(bellman_ford(n,0)) cout<<"inf"<<endl;
    else cout<<-dist[n-1]<<endl;
  */
  return 0;
}


Measured memory_bytes: 384
# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を2と3以上の奇数で順次割っていくする（下から計算したら、素数判定は不要）
# 3. 2.の結果に含まれる数の種類の数＋１が答え

def main():
  a, b = map(int, input().split())
  while b != 0: a, b = b, a % b #最大公約数を求める
  print(num_facto(a) + 1)  
  
def num_facto(n):
  ans = 0
  if n == 1: return ans
  cursor = 2
  while cursor ** 2 <= n:
    if n == 1: break
    if n % cursor == 0: ans += 1
    while n % cursor == 0: n = n // cursor
    cursor = 3 if cursor == 2 else (cursor + 2)
  if n != 1: ans += 1
  return ans

if __name__ == "__main__":
  main()


Measured memory_bytes: 39888
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
using lint = long long;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	string S;
	cin >> S;

	if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) cout << "Bad" << "\n";
	else cout << "Good" << "\n";

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#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 mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
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};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n;cin >>n;
    ll ans=0;
    rep(i,n){
        ll d=i+1;
        if(d%3==0||d%5==0)continue;
        ans+=d;
    }
    cout << ans <<endl;
}

Measured memory_bytes: 3636
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#############
# Main Code #
#############

a,b,c = inputIL()

print(a+b+c-max(a,b,c))

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

char a[21][21];

int main()
{
  int n,x,y,m,s;
  int i;
  char d[3];

  while(1){
    scanf("%d", &n);
    if(n==0)
      break;

    memset(a,0,sizeof(a));

    for(i=0;i<n;i++){
      scanf("%d%d", &x, &y);
      a[x][y]=1;
    }

    scanf("%d", &m);
    x=10,y=10;
    while(m-- > 0){
      scanf("%s%d", d, &s);
      while(s-- > 0){
	if(d[0] == 'E')x++;
	else if(d[0] == 'S')y--;
	else if(d[0] == 'W')x--;
	else if(d[0] == 'N')y++;
	
	if(a[x][y]){
          n--;
          a[x][y]=0;
        }
      }
    }

    if(n==0)
      printf("Yes\n");
    else printf("No\n");
  }
  return 0;
}



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

typedef long long ll;

template<class T> inline void chmin(T &a, T b) {if(a > b) a = b;}

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

    ll N,W;
    cin >> N >> W;
    ll w[110],v[110];
    for(int i=0;i<N;i++) cin >> w[i] >> v[i];
    ll dp[110][100050];
    const ll INF = 1LL<<60;
    for(int i=0;i<110;i++) for(int j=0;j<100050;j++) dp[i][j] = INF;
    dp[0][0] = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<100050;j++){
            chmin(dp[i+1][j],dp[i][j]);
            if(j-v[i]>=0) chmin(dp[i+1][j],dp[i][j-v[i]]+w[i]);
        }
    }
    ll ans = 0;
    for(int j=0;j<100050;j++){
        if(dp[N][j]<=W) ans = j;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 86272
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if(a < b && b < c) {
			System.out.printf("Yes\n");
		}
		else {
			System.out.printf("No\n");
		}
	}
}



Measured memory_bytes: 26148
// 22
/****************************************************
https://searleser97.gitlab.io/algorithms/template.cpp
****************************************************/

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fors(_, x, n, s) for (int _ = x; _ < n; _ += s)
#define forn(_, x, n) fors(_, x, n, 1)
#define rep(_, n) forn(_, 0, n)
#define forrs(_, x, n, s) for (int _ = x; _ > n; _ -= s)
#define forrn(_, x, n) forrs(_, x, n, 1)
#define rrep(_, n) forrn(_, n - 1, -1)
#define fi first
#define se second
#define pb push_back
#define pairii pair<int, int>
#define all(x) x.begin(), x.end()
#define cerr(s) cerr << "\033[48;5;196m\033[38;5;15m" << s << "\033[0m"
// typedef __int128_t lli;
typedef long long int li;
typedef long double ld;
// 12
void _main(int tc) {
  li n, W;
  cin >> n >> W;
  vector<int> w(n), v(n);
  rep(i, n) { cin >> w[i] >> v[i]; }
  vector<vector<li>> mem(n, vector<li>(W + 1, -1));
  // function<li(int, int)> knapsack = [&](int i, int k) -> li {
  //   assert(k <= W);
  //   if (i == n - 1)
  //     if (k + w[i] <= W)
  //       return v[i];
  //     else
  //       return 0;
  //   if (mem[i][k] != -1) return mem[i][k];
  //   mem[i][k] = 0;
  //   if (k + w[i] <= W) mem[i][k] = v[i] + knapsack(i + 1, k + w[i]);
  //   if (k <= W) mem[i][k] = max(mem[i][k], knapsack(i + 1, k));
  //   return mem[i][k];
  // };
  // cout << knapsack(0, 0) << endl;
  rrep(i, n) {
    rrep(k, W) {
      if (i == n - 1) {
        if (k + w[i] <= W) mem[i][k] = v[i];
        else mem[i][k] = 0;
        continue;
      }
      mem[i][k] = 0;
      if (k + w[i] <= W) mem[i][k] = v[i] + mem[i + 1][k + w[i]];
      mem[i][k] = max(mem[i][k], mem[i + 1][k]);
    }
  }
  cout << mem[0][0] << endl;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  _main(0);
  return 0;
  int tc;
  cin >> tc;
  rep(i, tc) _main(i + 1);
}

Measured memory_bytes: 79488
S =input()
if(S[0]==S[1] and S[2]==S[3] and S[0]!=S[2] and S[0]!=S[3]):
    print('Yes')
elif(S[0]==S[2] and S[1]==S[3] and S[0]!=S[1] and S[0]!=S[3]):
    print('Yes')
elif(S[0]==S[3] and S[1]==S[2] and S[0]!=S[1] and S[0]!=S[2]):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());

        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());

        int diff = 4 * X - Y;

        if(diff < 0 || diff % 2 != 0) {
            pw.println("No");
        } else if(diff / 2 <= X) {
            pw.println("Yes");
        } else {
            pw.println("No");
        }

        br.close();
        pw.close();
    }
}

Measured memory_bytes: 32696
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 2005
#define INF 0x3f3f3f3f
#define p 1000000007
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, k, f[MAXN][MAXN], inv[MAXN*MAXN], fac[MAXN*MAXN];

void init()
{
    inv[0]=inv[1]=fac[0]=fac[1]=1;
    for(rint i=2; i<=n*k; ++i) inv[i]=1LL*inv[p%i]*(p-p/i)%p;
    for(rint i=2; i<=n*k; ++i)
    {
        inv[i]=1LL*inv[i]*inv[i-1]%p;
        fac[i]=1LL*fac[i-1]*i%p;
    }
}

int comb(int x, int y)
{
    return 1LL*fac[x]*inv[y]%p*inv[x-y]%p;
}

int main()
{
    scanf("%d%d", &n, &k);
    init();
    f[0][0]=1;
    if(k==1) {printf("1\n"); return 0;}
    for(rint i=1; i<=n; ++i)
        for(rint j=0; j<=i; ++j)
        {
            f[i][j]=(f[i][j]+f[i-1][j])%p;
            if(j)
            {
                int temp=n-i+(n-j+1)*(k-1)-1;
                f[i][j]=(f[i][j]+1LL*f[i][j-1]*(n-j+1)%p*comb(temp, k-2)%p)%p;
            }
        }
    printf("%d\n", f[n][n]);
    return 0;
}


Measured memory_bytes: 47232
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
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(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

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

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

	if (s == "abc") {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

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

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    char s;
    cin>>s;
    if(s-'a'>=0&&s-'a'<=25){
        cout<<'a'<<endl;
    }else{
        cout<<'A'<<endl;
    }
}

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

using namespace std;

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

	int a, b, c;
	cin >> a >> b >> c;
	set<int> s;
	int now = a;
	while(s.count(now%b) == 0)
	{
		if(now%b == c)
		{
			cout << "YES" << endl;
			return 0;
		}
		s.insert(now%b);
		now += a;
	}
	cout << "NO" << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

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

  private static Scanner sc = new Scanner(System.in);

  private void run() {
    String s = sc.next();
    System.out.println(s.charAt(0) + String.valueOf(s.length() - 2) + s.charAt(s.length() - 1));
  }
}


Measured memory_bytes: 39076
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <assert.h>
     
using namespace std;
     
typedef long long ll;
     
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
     
#define MOD 1000000007

int main(){
  ll n,d;
  cin>>n>>d;
  ll ans = 0;
  rep(i,0,n){
    ll a,b;
    cin>>a>>b;
    if(a*a+b*b<=d*d)ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String []args) throws IOException {
    	FastScanner in  = new FastScanner(System.in);
    	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false); 
    	solve(in, out);
    	in.close();
    	out.close();
    }
    static long gcd(long a, long b){ return (b==0) ? a : gcd(b, a%b); }
    static int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }
    static class FastScanner{
	BufferedReader reader;
	StringTokenizer st;
	FastScanner(InputStream stream){reader=new BufferedReader(new InputStreamReader(stream));st=null;}	
	String next(){while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}		    
	     st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
	String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}	    	  	
	int    nextInt()   {return Integer.parseInt(next());}
	long   nextLong()  {return Long.parseLong(next());}		
	double nextDouble(){return Double.parseDouble(next());}
	char   nextChar()  {return next().charAt(0);}
	int[]  nextIntArray(int n)         {int[] arr= new int[n];   int i=0;while(i<n){arr[i++]=nextInt();}  return arr;}
	long[] nextLongArray(int n)        {long[]arr= new long[n];  int i=0;while(i<n){arr[i++]=nextLong();} return arr;}	
	int[]  nextIntArrayOneBased(int n) {int[] arr= new int[n+1]; int i=1;while(i<=n){arr[i++]=nextInt();} return arr;}	    	
	long[] nextLongArrayOneBased(int n){long[]arr= new long[n+1];int i=1;while(i<=n){arr[i++]=nextLong();}return arr;}	    	
	void   close(){try{reader.close();}catch(IOException e){e.printStackTrace();}}				
    }
    
    /********* SOLUTION STARTS HERE ************/
    
    private static void solve(FastScanner in, PrintWriter out){
        int n = in.nextInt();
        out.write((n*n)+"\n");
    }
    
    /************* SOLUTION ENDS HERE **********/
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
	ll k; cin >> k;
	ll ans = 0;
	for (ll a = 1; a <=k ; a++) {
		for (ll b = 1; b <= k; b++)  {
			for (ll c = 1; c <=k; c++) {
				ans += __gcd(__gcd(a,b),c);
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 3636
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_BALL_MAX		100000									// 最大ボール数

// 内部変数
static FILE *szpFpI;											// 入力
static int si1Ball[D_BALL_MAX];									// ボール
static int siBCnt;												// ボール数
static int siK;													// K

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// ソート関数 - int昇順
int
fSortFncIU(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	int *lipVal1 = (int *)pzpVal1;
	int *lipVal2 = (int *)pzpVal2;

	// int昇順
	if (*lipVal1 > *lipVal2) {
		return 1;
	}
	else if (*lipVal1 < *lipVal2) {
		return -1;
	}

	return 0;
}

// 最大公約数 - 取得
int
fGetGcd(
	int piVal1					// <I> 値１
	, int piVal2				// <I> 値２
)
{
	int liWork;

	// ユークリッドの互除法
	if (piVal1 < piVal2) {
		liWork = piVal1;
		piVal1 = piVal2;
		piVal2 = liWork;
	}
	while (piVal2 > 0) {
		liWork = piVal1 % piVal2;
		piVal1 = piVal2;
		piVal2 = liWork;
	}

	return piVal1;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// ボール数・K - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siBCnt, &siK);

	// ボール - 取得
	for (i = 0; i < siBCnt; i++) {
		fscanf(szpFpI, "%d", &si1Ball[i]);
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	qsort(si1Ball, siBCnt, sizeof(int), fSortFncIU);

	// 最大値
	if (siK > si1Ball[siBCnt - 1]) {
		return -1;
	}

	// 最大公約数 - 取得
	int liGcd = 0;
	for (i = 0; i < siBCnt - 1; i++) {
		int liDF = si1Ball[i + 1] - si1Ball[i];
		if (liDF > 0) {
			if (liGcd == 0) {
				liGcd = liDF;
			}
			else {
				liGcd = fGetGcd(liGcd, liDF);
			}
		}
	}

	// 最大公約数 - なし
	if (liGcd == 0) {
		if (siK == si1Ball[0]) {
			return 0;
		}
		else {
			return -1;
		}
	}

	// 剰余
	if (siK % liGcd == si1Ball[0] % liGcd) {
		return 0;
	}
	else {
		return -1;
	}
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// １行出力
	if (liRet == 0) {
		sprintf(lc1Buf, "POSSIBLE\n");
	}
	else {
		sprintf(lc1Buf, "IMPOSSIBLE\n");
	}
	fOutLine(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <algorithm>

#define rep(i, s, e) for (int i = (s); i <= (e); i++)

using namespace std;

typedef long long i64;

int n;
i64 x;
vector<i64> a;

i64 mi[2010][2010];

int main()
{
    cin >> n;
    cin >> x;
    a.assign(n + 1, 0);
    rep(i, 0, n - 1) cin >> a[i];

    i64 result = (1LL << 60);
    rep(i,0,n - 1)
    {
        mi[0][i] = a[i];
        rep(k,1,n-1)
        {
            mi[k][i] = min(mi[k - 1][i],a[(n + i - k) % n]);
        }
    }
    rep(i,0,n - 1)
    {
        i64 sum = i * x;
        rep(j,0,n - 1)
        {
            sum += mi[i][j];
        }
        result = min(sum , result);
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 31616
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
a.sort(reverse = True)

N = n+2
P = mod
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

base = 1
for item in range(n-k+1, n):
    base = (base * item) % mod
for i in range(1, k):
    base = (base * inv_t[i]) % mod
base2 = base

ans = 0
ans2  = 0
top = n - 1
for ai in a:
    if top < k-1:
        break
    if ai > 0:
        ans += base * ai
        ans %= mod
    else:
        ans2 += abs(base * ai)
        ans2 %= mod

    base = base * inv_t[top] * (top - k + 1)  % mod
    top -= 1

top = n-1
for ai in reversed(a):
    if top < k-1:
        break
    if ai > 0:
        ans2 += base2 * ai
        ans2 %= mod
    else:
        ans += abs(base2 * ai)
        ans %= mod
    base2 = base2 * inv_t[top] * (top - k + 1)  % mod
    top -= 1
print((ans - ans2) % mod)


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

#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define F first
#define S second
int n,ans=0;
int d[100];
signed main(){
    cin>>n;
    rep(i,n){
        cin>>d[i];
    }
    rep(i,n){
        for(int j=i+1;j<n;j++){
            ans+=d[i]*d[j];
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

const int INF = 0x3f3f3f3f;
const ll  LINF = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 45+10;
const int mod = 1e9+7;

using namespace std;

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

	int n,ans=0;
	string s;

	cin >> n >> s;

	set<int> r,w;

	for(int i=0;i<n;++i){
		if(s[i]=='R') r.insert(i);
		else w.insert(i);
	}

	ans = min(w.size(),r.size());

	int moves = 0;

	while(!r.empty() && !w.empty() && *(w.begin()) < *(r.rbegin()) ) {
		++moves;
		int x = *(w.begin()); w.erase(x); r.insert(x);
		x = *(r.rbegin()); r.erase(x); w.insert(x);
	}

	ans = min(ans,moves);

	cout << ans << endl;

    return 0;
}



Measured memory_bytes: 12988
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <numeric>
#include <set>
#include <list>
#include <bitset>
#include <cstdlib>
#include <map>
using ll = long long int;
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> ans(N);
    for (int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        vector<int> tmp(26, 0);
        for (char c : str)
        {
            tmp[c - 'a']++;
        }
        ans[i] = tmp;
    }
    for (char c = 'a'; c <= 'z'; c++)
    {
        int tmp = ans[0][c - 'a'];
        for (int j = 1; j < N; j++)
        {
            tmp = min(tmp, ans[j][c - 'a']);
        }
        for (int j = 0; j < tmp; j++)
        {
            cout << c;
        }
    }
    cout << endl;

    return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	long long int x;
	string y;
	int a,b,c;
	cin>>x;
	cin>>y;
	int bb=(y[0]-'0')*100+(y[2]-'0')*10+(y[3]-'0');
	long long int ans=x*bb;
	cout<<ans/100<<endl;
	return 0;
}



Measured memory_bytes: 3676
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

#define read(x) scanf("%d",&x)
#define readl(x) scanf("%lld",&x)
#define ll long long 
#define ull unsigned long long

int n,l;
int b[200005]={0};

int main()
{
	read(n);
	for(int i=2;i<=n;i++) read(l),b[l]++;
	for(int i=1;i<=n;i++) printf("%d\n",b[i]);
	return 0;
} 

Measured memory_bytes: 4500
a, b, c, d, e, f = [ int(v) for v in input().split() ]

water_list =  [ a*100*i + b*100*j for i in range(30) for j in range(30) if  0 < a*100*i + b*100*j < f ]
water_list = sorted(list(set(water_list)))
sugar_water_list = []

def dencity(w,s):
    return (100*s) / (w+s)

for i in water_list:
    limit_sugar = min(int(e * i / 100),f-i)    
    max_sugar = 0
    for j in range(0,limit_sugar//d+1):
        limit_sugar_2 = limit_sugar - j*d
        k = limit_sugar_2 // c
        max_sugar = max(j*d+k*c,max_sugar)
    sugar_water_list.append((dencity(i,max_sugar),i+max_sugar,max_sugar))

print(sorted(sugar_water_list)[-1][1],sorted(sugar_water_list)[-1][2])


Measured memory_bytes: 38768
//mridul1809
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define s(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define sd(x) scanf("%lf",&x)
#define p(x) printf("%d ",x)
#define pl(x) printf("%lld\n",x)
#define pd(x) printf("%lf\n",x)
#define pend printf("\n")
#define nm 5005
#define debug(x) printf("point %d\n",x)
#define int ll
vector < pair<int,int> > v;

bool comp(pair<int,int> a , pair<int,int> b)
{
    return (a.fi + a.se < b.fi + b.se);
}
int dp[nm];
signed main()
{
    int i,j,a,b,n;
    sl(n);
    for(i=0;i<n;i++)
    {
        sl(a); sl(b);
        v.pb(mp(a,b));
    }

    sort(v.begin(), v.end(),comp);

    int ans = 0;

    for(i=0;i<nm;i++)
        dp[i] = (1LL<<58);

    dp[0] = 0LL;

    for(i=0;i<v.size();i++)
    {
        // cout << i << endl;
        for(j=nm-1;j>=1;j--)
        {
            if(dp[j-1] <= v[i].fi)
            {
                // cout << i << " " << j << endl;
                dp[j] = min(dp[j] , dp[j-1] + v[i].se);
                ans = max(ans , j);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

int main(void)
{
    int A, B;
    cin >> A >> B;
    if (A <= 5)
    {
        cout << 0 << endl;
    }
    else if (A > 12)
    {
        cout << B << endl;
    }
    else
    {
        cout << B / 2 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
/** Problem0133 : Rotation of a Pattern **/
int main()
{
	char ptn[8][8];
	for (int y=0; y<8; y++)
		for (int x=0; x<8; x++)
			cin >> ptn[x][y];

	cout << "90" << endl;
	for (int y=0; y<8; y++) {
		for (int x=7; x>=0; x--) {
			cout << ptn[y][x];
		}
		cout << endl;
	}
	
	cout << "180" << endl;
	for (int y=7; y>=0; y--) {
		for (int x=7; x>=0; x--) {
			cout << ptn[x][y];
		}
		cout << endl;
	}
	
	cout << "270" << endl;
	for (int y=7; y>=0; y--) {
		for (int x=0; x<8; x++) {
			cout << ptn[y][x];
		}
		cout << endl;
	}
	
	return 0;
}

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

bitset<10000> maze[10];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int r, c;
    while(cin >> r >> c, (r && c)){
        for(int i = 0; i < r; ++i)
            for(int j = 0; j < c; ++j){
                bool tmp;
                cin >> tmp;
                maze[i][j] = tmp;
            }
        int time = 1 << r;
        int ans = 0;
        for(int i = 0; i < time; ++i){
            for(int j = 0; j < r; ++j)
                if(i & (1 << j))
                    maze[j].flip();
            int result = 0;
            for(int C = 0; C < c; ++C){
                int cntpercol = 0;
                for(int R = 0; R < r; ++R)
                    if(maze[R][C])
                        ++cntpercol;
                result += max(cntpercol, r - cntpercol);
            }
            ans = max(ans, result);
            for(int j = 0; j < r; ++j)
                if(i & (1 << j))
                    maze[j].flip();
        }
        cout << ans << endl;
    }
    return 0;
}

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

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf = 1.01e9;
const i64 inf64 = 4.01e18;
const double eps = 1e-9;

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

template <typename T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T, size_t size> void fill(T (&ary)[size], const T& val){
    fill_n((T*)ary, size, val);
}

void solve() {
    //const i64 mod = 1'000'000'007;
    i64 N;
    cin >> N;
    vector<vector<pair<i64,i64>>> tree(N);
    rep(i,0,N-1){
        i64 u,v,w;
        cin >> u >> v >> w;
        --u;
        --v;
        w%=2;
        tree[u].emplace_back(make_pair(v,w));
        tree[v].emplace_back(make_pair(u,w));
    }

    vector<i64> ans(N);
    function<void(i64,i64,i64)> rec=[&](i64 u,i64 p,i64 req){
        ans[u]=req;
        for(auto e:tree[u]){
            i64 v=e.first,w=e.second;
            if(v==p) continue;
            if((req+w)%2==0) rec(v,u,0);
            else rec(v,u,1);
        }
    };
    rec(0,-1,0);

    rep(i,0,N){
        cout << ans[i] << endl;
    }
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 15120
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  string s;
  cin >> s;
  for (char c : s) {
    if (c == '1')
      cout << 9;
    else
      cout << 1;
  }
  cout << endl;
  return 0;
}

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  ll n, a, b;
  cin >> n >> a >> b;
  if(n == 1 && a != b || b < a) {
    cout << 0 << endl;
    return 0;
  }
  if(a == b) {
    cout << 1 << endl;
    return 0;
  }
  cout << (n - 2) * (b - a) + 1 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	string s;
	map<string,int> ans;
	for(int i=1;i<=n;i++) {
		cin>>s;
		ans[s]++;
	}
	cout<<ans.size()<<endl;
	return 0;
}

Measured memory_bytes: 19108
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
s = rs()
if len(s) % 2 == 1:
    print('No')
else:
    if s[:n // 2] == s[n // 2:]:
        print('Yes')
    else:
        print('No')

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

#define y1 aklsdja
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define pb push_back
#define t top()
#define fr front()

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , x) for(int i = 0 ; i < x ; ++i)
#define FORD(i , x , n) for(int i = x ; i >= n ; --i)

#define oo 1e17 + 5
#define ll long long
#define int long long
#define pow poww

const int N = 22;
const int MASK = (1 << 21) + 5;
int n , mod = 1e9 + 7;
int a[N][N] , dp[N][MASK];
vector < int > g[N];

int add(int a , int b)
{
    return (a + b) % mod;
}

main()
{
    //freopen("O.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i , 1 , n)
        FOR(j , 1 , n)
            cin >> a[i][j];
    REP(i , (1 << n))
    {
        int cnt = 0;
        FORD(j , n , 0)
            if((i >> j) & 1)
                cnt++;
        g[cnt].pb(i);
    }
    dp[0][0] = 1;
    FOR(i , 1 , n)
    {
        REP(s , g[i].size())
        {
            int mask = g[i][s];
            FORD(j , n , 0)
                if((mask >> j) & 1 && a[i][j + 1] == 1)
                    dp[i][mask] = add(dp[i][mask] , dp[i - 1][mask ^ (1 << j)]);
        }
    }
    cout << dp[n][(1 << n) - 1];
}


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

int main(){
  int n, m;
  std::cin >> n;
  string s[n];
  int a[n], par[n];
  for (int i = 0; i < n; i++) {
    std::cin >> s[i] >> a[i];
    par[i] = i;
  }
  std::cin >> m;
  string tmpa, tmpb;
  for (int i = 0; i < m; i++) {
    std::cin >> tmpa >> tmpb;
    int anum, bnum;
    for (int j = 0; j < n; j++) {
      if(s[j] == tmpa){
        anum = j;
      }else if(s[j] == tmpb){
        bnum = j;
      }
    }
    int cost = min(a[anum], a[bnum]);
    int apar = par[anum], bpar = par[bnum];
    for (int j = 0; j < n; j++) {
      if(par[j] == apar or par[j] == bpar){
        par[j] = par[anum];
        a[j] = cost;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans += a[i];
  }
  std::cout << ans << std::endl;
  return 0;
}

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

#define endl "\n"
#define int long long int
#define mod 1000000007
#define vi vector<int>
#define pint pair<int,int>
#define vint vector<vector<int>>
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 1e6+5;
int A[N], B[N], P[N];

int mat[1005][1005];
pint edges[N];
unordered_map<int, set<int>> m;

bool compare(vi a, vi b)
{
    return a[0] < b[0];
}

int lcm(int a, int b)
{
    return (a*b)/(__gcd(a,b));
}

int mypow(int a, int x)
{
    if(a<=1 || x==1) return a;
    if(x==0) return 1;

    int temp = mypow(a,x/2);
    if(x%2==0) return ((temp%mod) * (temp%mod))%mod;
    else return (a%mod * ((temp%mod) * (temp%mod))%mod)%mod;
}

int count_bits(int n)
{
    int cnt = 0;
    while(n)
    {
        n = n & (n-1);
        cnt++;
    }return cnt;
}

void bfs(int src, int n)
{
    unordered_map<int, bool> visited;
    for(int i=0;i<n;i++) visited[i] = false;
    queue<int> q;
    q.push(src);
    visited[src] = true;

    while(!q.empty())
    {
        int curr = q.front();
        q.pop();
        B[curr] -= min(B[curr], A[src]);
        //cout<<curr<<" "<<endl;

        for(auto neigh: m[curr])
        {
            if(visited[neigh] == false)
            {
                //cout<<neigh<<endl;
                q.push(neigh);
                visited[neigh] = true;
                m[src].erase(neigh);
                m[neigh].erase(src);
            }
        }
    }
}

void void_solve(int n)
{

}

int int_solve(int n)
{

}

string string_solve(string s, int x)
{

}

bool bool_solve(int n)
{

}

int32_t main()
{
    //code
	IOS;

    int t,n,m,a,b,x,y,i,j,z;
    //cin>>t;
    t = 1;
    while(t--)
    {
        //cin>>n;
        //for(i=0;i<n;i++) cin>>A[i];
        //cout<<int_solve(n)<<endl;

        //if(bool_solve(n)) cout<<"YES"<<endl;
        //else cout<<"NO"<<endl;
        //void_solve(n);

        string s;
        cin>>s;
        n = s.length();
        if(s[n-1] == 's') s+= "es";
        else s += "s";
        cout<<s<<endl;
    }

	return 0;
}


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

int main(){
	int n, m, sum=0,count=0;
  cin >> n >> m;
  vector<int> a(n);
  for(int i=0; i<n ; i++){
    cin >> a.at(i);
  sum += a.at(i);
  }
  for(int k = 0;k<n ; k++){
    if(sum <= 4*m*a.at(k))
      count++;
  }
  
  if(count >= m)
    cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3560