akhauriyash/Code-Regression huggingface dataset:
import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    val n = readLine.toInt
    val _input = new Array[Int](n)
    1 to n foreach { i =>
      _input(i-1) = readLine.toInt
    }
    val input = _input.toList
    //println(input)
    val head1 :: head2 :: tail = input

    println(calMaxProf(tail, head2 - head1, math.min(head1, head2), math.max(head1, head2)))
  }

  @tailrec def calMaxProf(input: List[Int], maxProf: Int = Int.MinValue, min: Int = Int.MaxValue, max: Int = Int.MinValue): Int = input match {
    case head :: tail =>
      if (head < min) {
        calMaxProf(tail, maxProf, head, max)
      } else if (head - min > maxProf) {
        calMaxProf(tail, head - min, min, head)
      } else {
        calMaxProf(tail, maxProf, min, max)
      }
    case Nil =>
      maxProf
  }
}



Measured memory_bytes: 71148
#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<vector>
#include<climits>
#define ll long long int
using namespace std;
int main(void) {
  ll n;
  ll x;
  ll y=0;
  cin>>n;
  x=n;
  do {
    y+=x%10;
    x=x/10;
  } while (x!=0);
  if(n%y==0)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll H, W; cin >> H >> W;
  if(H == 1 || W == 1){
    cout << 1 << endl;
  }else if(H%2 == 0 && W%2 == 0){
    cout << (H * W) / 2 << endl;
  }else if(H%2 == 0 && W%2 == 1){
    cout << (H/2) * W << endl;
  }else if(H%2 == 1 && W%2 == 0){
    cout << H * (W/2) << endl;
  }else{
    cout << ((H+1)/2)*((W+1)/2) + (H/2)*(W/2) << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <string>
#include <sstream>
#include <cstring>
#include <cmath>

using namespace std;

#ifdef DEBUG
#define LOG(args) cout << args << "\n"
#define debug(x) x
#else
#define LOG(args)
#define debug(x)
#endif

#define vi vector<int>
#define ii pair<int, int>
#define vii vector< ii >
#define vvi vector< vi >
#define mp make_pair
#define pb push_back
#define ms(x, v) memset(x, v, sizeof(x))
#define all(x) x.begin(), x.end()
#define REP(x, n) for(int x = 0; x < n; x++)
#define REPV(x, v, n) for(int x = v; x < n; x++)
#define REVE(x, n) for(int x = n; x >= 0; x--)

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	string str;
	cin >> N >> str;
	vi W, R;
	for(int i = 0; i < N; i++)
	{
		if(str[i] == 'W')
			W.pb(i);
		else
			R.pb(i);
	}
	int l = 0, r = R.size() - 1, ans = 0;
	while(l < W.size() && r >= 0 && W[l] < R[r])
		ans++, l++, r--;
	cout << ans << "\n";
	return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  bool ok = true;
  rep(i,n) {
    if (a[i]%2 == 1) continue;
    if (a[i]%3 != 0 && a[i]%5 != 0) ok = false;
  }
  if (ok) cout << "APPROVED" << endl;
  else cout << "DENIED" << endl;
 
return 0;
}

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

string shuffle(string str, int len){
    string head = str.substr(0,len);
    string tail = str.substr(len,str.size()-len);
    return tail+ head;
}
int main(){
    string target;
    int time;
    int len;
    
    while(1){
        cin >> target >> time;
        if (target =="-") break;
        for (int i =0; i<time; i++){
            cin >> len;
            target = shuffle(target,len); 
        }
        cout << target << endl;
    }
    return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int main(void)
{
    int N; cin >> N;
    int a[100010]; rep(i ,N) cin >> a[i];
    int count[100010] = {};
    for (int i = 0; i < N; i++){
        count[a[i]-1]++;
        count[a[i]]++;
        count[a[i]+1]++;
    }
    int M = 0;
    for (int i = 0; i < 100001; i++){
        M = max(M,count[i]); 
    }
    cout << M << endl;
    return 0;
}


Measured memory_bytes: 1024
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()

for i in s.split(","):
	print(i,"", end="")
print()

Measured memory_bytes: 4212
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
 
typedef pair<int,int> P;
 
int main(){
    int N, Q;

    while( cin >> N >> Q, N || Q ){
        // m[name] := テ・ツ陳古ヲツ堋ヲnameテ」ツ?ォテ・ツッツセテ・ツソツ愿」ツ?凖」ツつ?テ・ツ陳古ヲツ堋ヲ,ティツ・ツソテヲツ堋ヲテ」ツ?ョテヲツ慊?・ツ、ツァ)テ」ツ?ョテァツオツ?」ツつ津ィツソツ氾」ツ??
        map<string, P> m;
        // v := テ・ツ陳古ヲツ堋ヲテ」ツ?ョテ・ツ青催・ツ可催」ツつ津、ツソツ敕ヲツ個?
        vector<string> v;
         
        for(int i = 0 ; i < N ; i++ ){
            // name := テ・ツ陳古ヲツ堋ヲテ」ツ?ョテ・ツ青催・ツ可? y1 := テ・ツ陳古ヲツ堋ヲ, y2 := ティツ・ツソテヲツ堋ヲ
            string name;
            int y1, y2;
             
            cin >> name >> y1 >> y2;
            if( m.count(name) ){
                if( m[name].second < y2 ){
                    m[name] = P(y1, y2);
                }
            }else{
                m[name] = P(y1, y2);
                v.push_back( name );
            }
        }
         
        for(int i = 0 ; i < Q ; i++ ){
            int q;
            cin >> q;
            
            // flag := ティツァツ」テ」ツ?古・ツュツ佚・ツ慊ィテ」ツ?凖」ツつ凝」ツ?凝」ツ?ゥテ」ツ??」ツ??
            bool flag = false; 
            for(int j = 0 ; j < v.size() ; j++ ){
                int y1 = m[v[j]].first;
                int y2 = m[v[j]].second;
                
                // テ・ツ陳古ヲツ堋ヲ[1,y1] <=> ティツ・ツソテヲツ堋ヲ[y2-y1+1, y2] テ」ツ?ィテ・ツッツセテ・ツソツ愿」ツ?療」ツ?ヲテ」ツ??」ツつ?
                // テ・ツッツセテ・ツソツ愿」ツ?古」ツ?づ」ツつ凝」ツ?ィテ」ツ??
                if( y2 - y1 + 1 <= q && q <= y2 ){ 
                    flag = true;
                    int ans = q - (y2 - y1);
                    // ティツァツ」テ」ツ?ョテ・ツ?コテ・ツ環?
                    cout << v[j] << " " << ans << endl;
                    break;
                }
            }
            
            // ティツァツ」テ」ツ?古・ツュツ佚・ツ慊ィテ」ツ?療」ツ?ェテ」ツ??」ツ?ィテ」ツ??
            if( !flag ){
                cout << "Unknown" << endl;
            }
        }
    }
}

Measured memory_bytes: 1344
modIntDivisor :: Int
modIntDivisor = floor 1e9 + 7

extGcd :: Integral a => Int -> Int -> (Int, Int)
extGcd a 0 = (1, 0)
extGcd a b = (x, y)
	where
		(x', y') = extGcd b (a `mod` b)
		x = y'
		y = x' - a `div` b * y';

newtype ModInt = ModInt { unModInt :: Int } deriving (Eq, Show)

modInt :: Int -> ModInt
modInt x = ModInt $ (x `mod` modIntDivisor + modIntDivisor) `mod` modIntDivisor

modIntMap2 :: (Int -> Int -> Int) -> ModInt -> ModInt -> ModInt
modIntMap2 f a b = modInt $ f (unModInt a) (unModInt b)

instance Num ModInt where
	(+) = modIntMap2 (+)
	(-) = modIntMap2 (-)
	(*) = modIntMap2 (*)
	abs = id
	signum _ = 1
	fromInteger = modInt . fromInteger

instance Enum ModInt where
	toEnum = modInt
	fromEnum = unModInt

minv :: ModInt -> ModInt
minv a = modInt y
	where (_, y) = extGcd modIntDivisor $ unModInt a

mdiv :: ModInt -> ModInt -> ModInt
mdiv x y = x * minv y

mperm :: ModInt -> ModInt -> ModInt
mperm _ 0 = 1
mperm n r = product [(n - r + 1)..n]

mcomb :: ModInt -> ModInt -> ModInt
mcomb n r = mperm n r `mdiv` product [1..r]

calc :: Int -> Int -> ModInt
calc x y
	| (x + y) `mod` 3 /= 0       = 0
	| (diff + dist) `mod` 2 /= 0 = 0
	| n < 0 || dist < n          = 0
	| otherwise = mcomb (modInt dist) (modInt n)
	where
		diff = x - y
		dist = (x + y) `div` 3
		n = (diff + dist) `div` 2

main :: IO ()
main = do
	[x, y] <- map read . words <$> getLine :: IO [Int]
	print $ unModInt $ calc x y


Measured memory_bytes: 508
#include<iostream>
#include<functional>
#include<utility>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int n, m;
string s;


int main() {
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i]=='x')
		{
			n++;
		}
	}
	if (n <= 7)
	{
		cout << "YES" << endl;
		return 0;
	}
	cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100000;
vector<int> g[N];
int sz[N], dp[N];

void dfs(int u, int prev) {
        vector<int> len;
        for (auto v : g[u]) if (prev != v) {
                dfs(v, u);
                len.push_back(sz[v]);
                dp[u] = max(dp[u], dp[v]);
                sz[u] = max(sz[u], sz[v] + (g[u].size() == 2));
        }
        sort(len.rbegin(), len.rend());
        if (len.size() >= 2) dp[u] = max(dp[u], len[0] + len[1] + (g[u].size() == 2));
}           

int main() {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        int leaf = 0;
        for (int i = 0; i < n; i ++) if (g[i].size() == 1) leaf ++;
        dfs(0, -1);
        printf("%d\n", dp[0] + leaf);
        return 0;
}


Measured memory_bytes: 6656
import java.io.*;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        out.println(sc.nextInt()+sc.nextInt()+sc.nextInt()>=22?"bust":"win");
        out.flush();
        out.close();
    }
    static class Scanner {

        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }


        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }


        public Integer[] nextIntegerArray(int n) throws IOException {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public double[] nextDoubleArray(int n) throws IOException {
            double[] ans = new double[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextDouble();
            return ans;
        }

        public short nextShort() throws IOException {
            return Short.parseShort(next());
        }

    }

}

Measured memory_bytes: 21332
nt=[int(x) for x in input().split()]
mini=1001
try:
    for y in range(nt[0]):
        temp=([int(z) for z in input().split()])
        if(temp[1]<=nt[1] and temp[0]<mini):
            mini=temp[0]
            ans=mini
    print(ans)
except:
    print("TLE")


Measured memory_bytes: 3060
n=int(input())
t=[int(input()) for i in range(n)]

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

	
if n==1:
	print(t[0])
	exit()

check=gcd(t[0],t[1])
ans=t[0]*t[1]//check
for i in range(2,n):
	check=gcd(ans,t[i])
	ans=ans*t[i]//check
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define INFINITY 100000
int cost[20][20];

int main(void){
  char s;
  int n,m,x1,x2,y1,y2;
  REP(i,20)
    REP(j,20)
      cost[i][j] = (i!=j)?INFINITY:0;
  cin>>n>>m;
  while(m--){
    int a,b,c,d;
    cin>>a>>s>>b>>s>>c>>s>>d;
    cost[a-1][b-1] = c;
    cost[b-1][a-1] = d;
  }
  cin>>x1>>s>>x2>>s>>y1>>s>>y2;
  REP(k,n)
    REP(i,n)
      REP(j,n)
       cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
  cout << y1 - y2 - cost[x1-1][x2-1] - cost[x2-1][x1-1] << endl;
  return 0;
}

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

void fnInput(vector<int>& rvnSort)
{
  int nMaxSiz;
  cin >> nMaxSiz;
  
  rvnSort.resize(nMaxSiz);
  for (int i = 0; i < nMaxSiz; i++)
    cin >> rvnSort[i];
}

void fnInsertionSort(vector<int>& rvnSort, int nGap, int& rnSortCnt)
{
  for (int nxing = nGap; nxing < rvnSort.size(); nxing++)
  {
    int nTrg = rvnSort[nxing];
    int nxed = nxing - nGap;

    while (nxed >= 0         &&
           nTrg < rvnSort[nxed])
    {
      rvnSort[nxed + nGap] = rvnSort[nxed];
      nxed -= nGap;

      rnSortCnt++;
    }
    rvnSort[nxed + nGap] = nTrg;
  }
}

void fnShellSort(vector<int>& rvnSort, vector<int>& rvnGap, int& rnSortCnt)
{
  for (int nGap = 1; nGap <= rvnSort.size(); nGap = 3 * nGap + 1)
    rvnGap.push_back(nGap);
  
  for (int i = rvnGap.size() - 1; i >= 0; i--)
    fnInsertionSort(rvnSort, rvnGap[i], rnSortCnt);
}

void fnOutput(const vector<int>& cnrvnSort, const vector<int>& cnrvnGap, int nSortCnt)
{
  cout << cnrvnGap.size() << endl;

  for (int i = cnrvnGap.size() - 1; i >= 0; i--)
  {
    if (i != cnrvnGap.size() - 1) cout << " ";
    cout << cnrvnGap[i];
  }
  cout << endl;

  cout << nSortCnt << endl;

  for (int i = 0; i < cnrvnSort.size(); i++)
    cout << cnrvnSort[i] << endl;
}

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

  vector<int> vnSort;
  vector<int> vnGap;
  int nSortCnt = 0;

  fnInput(vnSort);
  fnShellSort(vnSort, vnGap, nSortCnt);
  fnOutput(vnSort, vnGap, nSortCnt);

  return 0;
}



Measured memory_bytes: 6712
#include<iostream>
#include<unordered_map>
#include<bitset>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<ctype.h>
#include<unordered_set>
#include<string>
#include<iomanip>
#include<queue>
#include<limits>
#include<map>
#include<stack>
#include<iterator>
#include<cstring>
 
#include<deque>
#define pi 3.141592653589793238
#include<chrono>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    
    //cin >> T;
    while (T--) {
        ll n, a, b;
        cin >> n >> a >> b;
        vector<ll> v(n);
        for(i = 0; i < n; i++){
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        ll lo = 1, hi = 1e9, mid;
        ll ans = INF;
        while(lo <= hi){
            mid = (lo + hi) / 2;
            ll moves = mid;
            vector<ll> h;
            h = v;
            //cout << "##" << mid<< endl;
            for(i = n - 1; i >= 0; i--){
                h[i] = h[i] - (b * mid);
                h[i] = max(h[i], 0LL);
            }
            bool flag = true;
            for(i = n - 1; i >= 0; i--){
                ll req = (h[i] + a - b - 1) / (a - b);
                //cout << h[i] << " ";
                if(req > moves){
                    flag = false;
                }
                else{
                    moves -= req;
                }
            }
            //cout << endl;
            if(flag){
                ans = mid;
                hi = mid - 1;
            }
            else{
        
                lo = mid + 1;
            }
        }
        cout << ans;
    }
    return 0;
}

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


// string S = "1214";
// long long K = 4;

string S;
long long K;
long long days = 5000000000000000;

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

    // cout << days;
    // string a(3, 'A');
    // cout << a << endl;

    // 1が連続する
    int one = 0;
    string first_not_one = "";
    for (int i = 0; i < S.size(); i++) {
        if (S[i] != '1') {
            first_not_one = S[i];
            break;
        }
        one++;
    }

    if (one >= K) {
        cout << 1 << endl; 
    } else {
        cout << first_not_one << endl; 
    }


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  cin >>N>>M;
  int A[M+1];
  int answer[N+1];
  int B[M+1][N+1];
  for(int i=1;i<=N;i++)answer[i]=0;
  for(int i=1;i<=M;i++)cin >> A[i];
  for(int i=1;i<=M;i++){
    for(int j=1;j<=N;j++){
      cin >>B[i][j];
      if(A[i]==B[i][j]){
        answer[j]++;
      }else{
        answer[A[i]]++;
      }
    }
  }
  for(int i=1;i<=N;i++)cout<<answer[i]<<endl;
  return 0;
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
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() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int X, Y, Z;
  cin >> X >> Y >> Z;
  cout << Z << " " << X << " " << Y << endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--) 
#define Rep(i,a) for(int i = 0; i < a; i++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ab(x) ((x) < 0 ? -(x) : (x))
using namespace std;
typedef long long LL;
typedef map<int, int>::iterator mit;
typedef set<int>::iterator sit;
typedef pair<int, int> pii;
#define x first
#define y second
const int N = 1e5 + 10;

struct edge{ int to, pre, c; }e[N << 1]; int u[N], l = 0;
void ins(int a, int b, int c) { e[++l] = (edge){b, u[a], c}, u[a] = l; }
#define v e[i].to
#define ec e[i].c
#define reg(i,a) for(int i = u[a]; i; i = e[i].pre)

int n, m;
bool vis[N], ok;
LL cnt[3]; int d[N];
int T;
void dfs(int x, int l) {
	vis[x] = true; cnt[l]++; d[x] = l;
	reg(i,x) {
		T++;
		if (!vis[v]) dfs(v, (l + ec) % 3);
		else if ((l + ec) % 3 != d[v]) ok = false;
	}
}

int main() {
	scanf("%d%d",&n,&m);
	rep(i,1,m) {
		int a, b; scanf("%d%d",&a,&b);
		ins(a, b, 1), ins(b, a, 2);
	}
	LL ans = 0;
	rep(i,1,n) if (!vis[i]) {
		T = 0;
		rep(j,0,2) cnt[j] = 0; ok = true;
		dfs(i, 0); LL s = cnt[0] + cnt[1] + cnt[2];
		if (!ok) ans += s * s;
		else {
			if (cnt[0] && cnt[1] && cnt[2]) 
				ans += cnt[0] * cnt[1] + cnt[1] * cnt[2] + cnt[2] * cnt[0];
			else 
				ans += T / 2;
		}
	}
	cout <<ans<<endl;
}

Measured memory_bytes: 6528
#include<stdio.h>
int main(){
	int w,h,x,y,r;
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	if(w>=x+r&&x-r>=0&&h>=y+r&&y-r>=0){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
#define forn(i, s, t) for (int i = s ; i < (int)t ; i++)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pf2(x,y) printf("%d %d\n",x,y)
#define pf(x) printf("%d\n",x)
#define each(x) for(auto it:x)  cout<<it<<endl;
#define pi pair<int,int>
#define pb push_back
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define pf(x) printf("%d\n",x)
#define pf2(x,y) printf("%d %d\n",x,y)
#define mem(a,x) memset(a,x,sizeof(a))
#define copy(b,a) memcpy(a,b,sizeof(a))
#define SZ(x) (int)x.size()
#define VI vector<int>
#define VII vector<pair<int,int>>
#define PI pair<int,int>
using namespace std;
typedef long long ll;
const ll P=998244353;
ll Mod(ll x,ll p=P) {return x%p;}
ll qpow(ll x,ll y,ll p=P){ll ans=1;for(x%=p;y;y>>=1,x=x*x%p)if(y&1) ans=ans*x%p;return ans;}
ll inv(ll x,ll p=P){return x<=1?1:(p-p/x)*inv(p%x,p)%p;}
ll sqrt2(ll x){ll l=1,r=2e9;while(l<r){ll mid=(l+r+1)>>1;if(mid*mid<=x) l=mid;else r=mid-1;}return l;}
ll sqrt3(ll x){ll y=(ll)(powl((long double)x,1.0/3.0)+0.5);while(y*y*y<x) y++;while(y*y*y>x) y--;return y;}
ll comb(ll n,ll m,ll p=P){if(m>n||n<0) return 0;if(m>n-m) m=n-m;ll ans=1;for(int i=1;i<=m;i++)ans=ans*n%p,ans=ans*inv(i,p),n--;return ans;}
ll comb(ll n,ll m){if(m>n||n<0) return 0;if(m>n-m) m=n-m;ll ans=1;for(int i=1;i<=m;i++)ans=ans*n,ans/=i,n--;return ans;}
ll ceil(ll x,ll y){return (x+y-1)/y;}
int lowerbit(int x) {return x&-x;}
int HighBit(int x){for(int i=30;i>=0;i--)if(x>>i&1) return i;return -1;}
char inline nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
template <typename T>
bool rd(T& v){static char ch;while(ch!=EOF && !isdigit(ch)) ch=nc();if(ch==EOF) return false;for(v=0;isdigit(ch);ch=nc())v=v*10+ch-'0';return true;}
template <typename T>
void o(T p){static int stk[70],tp;if(p==0) {putchar('0');return ;}if(p<0) {p=-p;putchar('-');}while(p) stk[++tp]=p%10,p/=10;while(tp) putchar(stk[tp--]+'0');}
const int maxn=1e5+5;
ll solve(ll n){
    vector<PI> prime;
    for(ll i=2;i*i<=n;i++){
        if(n%i) continue;
        prime.pb({i,0});
        while(n%i==0){
            n/=i;
            prime.back().second++;
        }
    }
    ll ans=1;
    if(n!=1) ans=2;
    for(auto it:prime)
        ans*=it.se+1;
    return ans-1;
}
int main(){
    ll n;
    cin>>n;
    ll ans=0;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            ll t=n;
            while(t%i==0)
                t/=i;
            if(t%i==1) ans++;
            if(i*i==n) continue;
            t=n;
            while(t%(n/i)==0)
                t/=n/i;
            if(t%(n/i)==1) ans++;
        }
    }
    ans++;
   // pf(ans);
    cout<<ans+solve(n-1);
}


Measured memory_bytes: 256
/*
  coded by: mi_ni_
  "LIVE LONG AND PROSPER"
*/
 
#include <bits/stdc++.h>
using namespace std;

#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define newl '\n'
#define TEST_CASE(fun) int tc; cin>>tc; while(tc--){ fun(); }
#define TEST_CASE_2 int tc; cin>>tc; for(int i=1;i<=tc;i++)
#define TEST_CASE_3(fun) int tc; cin>>tc; for(int i=1;i<=tc;i++){ cout<<"Case #"<<i<<": "; fun(); }
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define forab(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define forabr(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define trav(i,x) for(auto& i:x)

using ll=long long int;
using ull=unsigned long long int;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vl=vector<ll>;
using vii=vector<pii>;
using vll=vector<pll>;

const ld pi=acosl(-1);
const int inf=(int)1e9+7;
const ll llinf=(ll)1e18+7;
const ld eps=1e-7;

//other
template<typename T> inline bool powerof2(T a){ return (a&&(!(a&(a-1)))); }
template<typename T> inline T log_2(T a){ T res=-1; while(a){ a/=2; res++; } return res; }

//make sure to choose TEST_CASE in main for multiple test cases
void solve(){
	int n;
	cin>>n;
	vi a(n),b(n);
	forn(i,n) cin>>a[i]>>b[i];
	sort(all(a));
	sort(all(b));
	if(n%2){
		int mid=(n-1)/2;
		cout<<b[mid]-a[mid]+1<<newl;
	}
	else{
		int mid=n/2;
		int l=(a[mid]+a[mid-1]);
		int r=(b[mid]+b[mid-1]);
		cout<<(r-l)+1<<newl; 
	}
}

int main(){
	FAST_IO
	cout<<fixed<<setprecision(15);
	cerr<<fixed<<setprecision(10);
	//init_fact();
	//TEST_CASE(solve)
	//TEST_CASE_2{}
	//TEST_CASE_3(solve)
	solve();
	return 0;
}

Measured memory_bytes: 4784
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

int H , W;
bool b[10][10];

int main(){
	scanf("%d%d" , &H , &W);
	repp(i,0,H){
		repp(j,0,W){
			char c;
			scanf(" %c" , &c);
			b[i][j] = c == '#';
		}
	}
	bool ans = b[0][0];
	int x = 0;
	int y = 0;
	b[0][0] = 0;
	while(x + 1 < H || y + 1 < W){
		if(b[x+1][y]){
			++x;
		} else if(b[x][y+1]){
			++y;
		} else {
			ans = 0;
			break;
		}
		b[x][y] = 0;
	}
	repp(i,0,H){
		repp(j,0,W){
			if(b[i][j]) ans = 0;
		}
	}
	printf("%s\n" , ans ? "Possible" : "Impossible");
	return 0;
}


Measured memory_bytes: 128
#pragma GCC optimze("Ofast")
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define pb push_back
#define vi vector<ll>
#define vs vector<string>
#define vp(x,y) vector< pair<x,y> >
#define mp make_pair
#define all(x) x.begin(),x.end()
#define Sort(x) sort(all(x));
#define DSort(x) sort(all(x), greater<>());
#define l_b lower_bound
#define u_b upper_bound
#define u_set unordered_set
#define u_map unordered_map
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0)

const ll M=1e9+7;
const ld PI=3.14159265;
using namespace std;

int main(){
    fast_io;
    ll n,d,x,y,i,c=0;
    ld dist=0.0;
    cin>>n>>d;
	for(i=0;i<n;i++){
		cin>>x>>y;
		dist=sqrt(x*x+y*y);
		if(dist<=d) c++;
	}
	cout<<c;
}



Measured memory_bytes: 3716
#include<stdio.h>
int main(void)
{
	int n,i,j,x,y,l[100];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&l[i]);
	}
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(l[i]<l[j]){
				x=l[i];
				l[i]=l[j];
				l[j]=x;
			}
		}
	}
	y=0;
	for(i=1;i<n;i++){
		y=y+l[i];
	}
	// printf("%d %d\n",l[0],y);
	if(l[0]<y){
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define M 1000000007
#define pb push_back
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define NAYAN freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);



int dp[100001];
int a[100001];
int n;

int solve(int i)
{
    if(i==n)
        return 0;
    if(i>n)
        return 9999999999;
    if(dp[i]!=-1)
        return dp[i];
    int x,y;
    x=abs(a[i]-a[i+1])+solve(i+1);
    y=abs(a[i]-a[i+2])+solve(i+2);
    dp[i]=min(x,y);
    return dp[i];
}
signed main()
{
    boost
   // #ifndef ONLINE_JUDGE 
   // NAYAN
   // #endif
   
    //int n;
    cin >> n;
   // int a[n];
    memset(dp,-1,sizeof(dp));
    int i;
    for(i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    int ans=solve(1);
    cout << ans << endl;

}






















Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		scan.close();
		
		int ans = 0;
		for (int i = 1 ; i <= N ; i++) {
			if ( i % 2 == 1) {
				int cnt = 0;
				for (int j = 1 ; j <= i ; j++) {
					if (i % j == 0) {
						cnt++;
					}
				}
				if (cnt == 8) {
					ans++;
				}
			}
		}
		
		System.out.print(ans); 
	}
}


Measured memory_bytes: 21972
def c():
    x = int(input())
    if x < 100:
        return 0
    # 下2桁
    tmp = int(str(x)[-2:])
    N = x // 100
    lower = 100*N
    upper = 105*N
    if lower <= x <= upper:
        return 1
    else:
        return 0


if __name__ == "__main__":
    ans = c()
    print(ans)


Measured memory_bytes: 38384
def count(s):
    res = {}
    for ch in s:
        if not ch in res:
            res[ch] = 0
        res[ch] += 1
    return res

def run():
    n = int(raw_input())
    S = [sorted(raw_input()) for i in range(n)]
    U = [count(s) for s in S]
    ans = ""
    for ch in set(S[0]):
        num = min([(u[ch] if ch in u else 0) for u in U])
        if num > 0:
            ans += ch * num
    return "".join(sorted(ans))
print run()

Measured memory_bytes: 2820
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll a,b;
  cin >> a >> b;
  ll d=abs(b-a);
  if(d%2) {
    pr("IMPOSSIBLE");
    return;
  }
  pr((a+b)/2);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<map>
#include<utility>
#include<stdlib.h>
#include<ctime>
using namespace std;



int main()
{
	string s;
	cin >> s;
	s.erase(3);
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 3624
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(N):
    q = deque(["3", "5", "7"])

    cnt = 0
    while q:
        s = q.popleft()

        if int(s) > N:
            continue

        if len(set(s)) == 3:
            cnt += 1

        for c in ["3", "5", "7"]:
            q.append(s + c)

    return cnt


def main():
    N = int(input())
    ans = bfs(N)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 7540
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10, mod = 1e9 + 7;
int fact[N], invfact[N];
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (((ll) x) * y) % mod;}
inline int powr(int a, ll b){
	int x = 1 % mod;
	while(b){
		if(b & 1) x = mul(x, a);
		a = mul(a, a);
		b >>= 1;
	}
	return x;
}
inline int inv(int a){ return powr(a, mod - 2);}
void pre(){
	fact[0] = invfact[0] = 1;
	for(int i = 1;i < N; i++) fact[i] = mul(i, fact[i - 1]);
	invfact[N - 1] = inv(fact[N - 1]);
	for(int i = N - 2; i >= 1; i--) invfact[i] = mul(invfact[i + 1], i + 1);
	assert(invfact[1] == 1);
}
inline int C(int n, int k){
	if(n < k || k < 0) return 0;
	return mul(fact[n], mul(invfact[k], invfact[n - k]));
}

int get(int n, int k){
	if(k == 1) return (n == 2 || n == 3);
}

int f(int n, int k){
	if(k == 0) return 0;
	if(k == 1) return n == 2;
	if(n == 2) return 1;
	return mul(C(k - 1, n - 1 - k), mul(fact[k], fact[n - 1 - k]));
}

int main(){
	int n;
	pre();
	cin >> n;
	int ans = 0;
	for(int k = 0; k <= n - 1; k++){
		ans = add(ans, mul(k, sub(f(n, k), f(n, k - 1))));
	}
	cout << ans;
}

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

int main()
{
        string A, B, C;
        cin >> A >> B >> C;
        if (A[A.length()-1] == B[0] && B[B.length()-1] == C[0]) {
                cout << "YES" << endl;
        }
        else {
                cout << "NO" << endl;
        }


}


Measured memory_bytes: 256
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	var A, B, C, D int
	nextInt(&A, &B, &C, &D)
	var step int
	for A > 0 && C > 0 {
		if step % 2 == 0 {
			C-=B
		} else {
			A-=D
		}
		step++
	}
	if A <= 0 {
		fmt.Printf("No")
	} else {
		fmt.Printf("Yes")
	}
}

const MAX_INT int = 1_000_000_000

var sc = bufio.NewScanner(os.Stdin)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)

func nextLine() string {
	buffer := make([]byte, 0)
	for true {
		line, isPrefix, err := reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func nextInt(A ...*int) {
	L := strings.Split(nextLine(), " ")
	for i, a := range A {
		*a, _ = strconv.Atoi(L[i])
	}
}
func nextInts(A *[]int) {
	L := strings.Split(nextLine(), " ")
	(*A) = make([]int, len(L))
	for i, l := range L {
		(*A)[i], _ = strconv.Atoi(l)
	}
}

func nextInt64(A ...*int64) {
	L := strings.Split(nextLine(), " ")
	for i, a := range A {
		*a, _ = strconv.ParseInt(L[i], 0, 64)
	}
}

func max(a int, b int) int {
	if a >= b {
		return a
	}
	return b
}



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

int main(){
  vector<int> a = {1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
  int x, y;
  cin >> x >> y;
  x--; y--;
  cout << (a[x] == a[y] ? "Yes" : "No") << endl;
}


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

// #define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define vin(v,n) copy_n(istream_iterator<int>(cin),n,back_inserter(v));
#define all(v) v.begin(),v.end()
#define INF 2000000000
#define MOD 1000000007
#define ll long long 
#define vi vector<int>
#define ii pair<int,int>
#define si set<int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define f1(i,a,b) for(int i = a;i<b;i++)
#define f2(i,a,b) for(int i = a;i<=b;i++)

using namespace std;
const int N = 1e5+5;
vi g[N];
stack<int> st;
vector<bool> vis(N, false);

void dfs(int x)
{
   vis[x] = true;
   for(int v:g[x])
      if(!vis[v]) 
         dfs(v);
   st.push(x);
}

int32_t main() 
{
	IOS;
   int n, m;
   cin >> n >> m;
   f1(i,0,m)
   {
      int x, y;
      cin >> x >> y;
      g[x].pb(y);
   }
   f2(i,1,n)
   {
      if(!vis[i])
         dfs(i);
   }

   vi dp(n+1, 0);
   int res = 0;
   while(!st.empty())
   {
      int u = st.top();
      st.pop();
      for(int v:g[u])
      {
         dp[v] = max(dp[v], dp[u]+1);
         res = max(res, dp[v]);
      }
   }

   cout << res;
	return 0;
	
}


Measured memory_bytes: 8576
x,y = map(int, input().split())

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



move = (x+y) / 3
if int(move) != move or x < move or y < move:
    print(0)
else:
    move = int(move)
    diff = max(x,y) - min(x,y)
    res = cmb(move, move//2 - diff//2, mod)
    print(res)

Measured memory_bytes: 122356
#include <stdio.h>
#include <iostream>

using namespace std;

#define PRIME_MAX 250000	//9,223,372,036,854,775,807までの値に対応

class PrimeNumber
{
private:
	bool ary[PRIME_MAX];	//ary[i]がtrueならiは素数
public:
	//コンストラクタ
	PrimeNumber(){
		for(long long i=0;i<PRIME_MAX;i++){
			ary[i]=1;
		}
		ary[0]=0;ary[1]=0;
		for(long long i=2;(i*i)<PRIME_MAX;i++)
			if(ary[i])
				for(long long j=(i<<1);j<PRIME_MAX;j+=i)
					if(ary[j])
						ary[j]=0;
	};
	//sからeまでの素数を数える
	long long count(long long s,long long e){
		long long count=0;
		for(long long i=s;i<=e;i++){
			if(ary[i])count++;
		}
		return count;
	};
	//iが素数なら1を返す
	bool get(long long i){
		return ary[i];
	};
};

int main(void){

	PrimeNumber prime;
	long long n;

	while(1){

		cin >>n;
		if(!n)
			break;

		cout<<prime.count(n+1,2*n)<<endl;
	}

	return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

const ll MXN=100005;
vector<edge> G[MXN];
vl c(MXN,-1);

void bfs(ll x,ll k){
  c[x]=k;
  ll z=G[x].size();
  rep(i,z){
    if(c[G[x][i].to]==-1){
      bfs(G[x][i].to,(k+G[x][i].cost)%2);
    }
  }
}

int main() {
  ll N;
  cin >> N;
  rep(i,N-1){
    ll a,b,w;
    cin >> a >> b >> w;
    a--;
    b--;
    w%=2;
    G[a].push_back({b,w});
    G[b].push_back({a,w});
  }
  bfs(0,0);
  rep(i,N){
    cout << c[i] << endl;
  }
}

Measured memory_bytes: 10240
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int m=n%10;
	if(m==3)
	cout<<"bon";
	else if(m==0||m==1||m==6||m==8)
	cout<<"pon";
	else
	cout<<"hon";
	return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




int main(){


	ll N;
	scanf("%lld",&N);

	ll T = 1,A = 1;

	ll t,a;
	ll num_t,num_a;

	for(int i = 0; i < N; i++){

		scanf("%lld %lld",&t,&a);

		if(T%t == 0){

			num_t = T/t;
		}else{

			num_t = T/t+1;
		}
		if(A%a == 0){

			num_a = A/a;
		}else{

			num_a = A/a+1;
		}

		ll mult = max(1LL,max(num_t,num_a));

		T = mult*t,A = mult*a;
	}

	printf("%lld\n",T+A);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
#define FOR(i, a, b) for(LL i=(LL)(a);i<(LL)(b);i++)
#define REP(i,x) for(LL i=0;i<(LL)(x);i++)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(10);

    int N;
    cin >> N;
    if(N % 2 == 1)
    {
        N += 1;
    }

    cout << N/2 << endl;
    return 0;
}

Measured memory_bytes: 256
/*
Author : Devil088
*/
#include<bits/stdc++.h>
using namespace std;
#define MOD 998244353
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int a,b;
	cin>>a>>b;
	
	if(a>b)cout<<"safe";
	else cout<<"unsafe";
	
}


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

int main()
{
    int N;
    int a, b;
    vector<string> mozi(a);
    int i, j;
    cin >> a >> b;
    for (i = 0; i < a; i++)
    {
        cin >> mozi.at(i);
    }
    for (i = 0; i < b + 2; i++)
    {
        cout << "#";
    }
    cout << endl;
    for (i = 0; i < a; i++)
    {
        cout << "#";
        cout << mozi.at(i);
        cout << "#" << endl;
    }
    for (i = 0; i < b + 2; i++)
    {
        cout << "#";
    }
    cout << endl;
}


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

using namespace std;

#define llong long long
#define ii pair<int, int>
#define xx first
#define yy second
#define len(s) ((int)s.size())
#define rep(i,n) for (int i = -1; ++i < n; )
#define rep1(i,n) for (int i = 0; ++i <= n; )

#define maxn 101010
int n;
vector<int> gr[maxn];

int cnt[2];
queue<int> qu;
int col[maxn];

void bfs() {
  memset(col, -1, sizeof(col));
  col[1] = 0;
  col[n] = 1;
  cnt[0] = cnt[1] = 1;
  for (qu.push(1), qu.push(n); len(qu); qu.pop()) {
    int u = qu.front();
    for (auto v: gr[u]) {
      if (col[v] != -1) continue;
      col[v] = col[u];
      cnt[col[v]] ++;
      qu.push(v);
    }
  }
}

int main() {
  cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  rep1(i, n - 1) {
    int u, v; cin >> u >> v;
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  bfs();
  if (cnt[0] > cnt[1]) cout << "Fennec";
  else cout << "Snuke";

  //rep1(i, n) clog << i << ' ' << col[i] << endl;

  return 0;
}


Measured memory_bytes: 6272
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 1<<28
using namespace std;

int p[22][22];
int n;
int memo[1<<18];

int solve(int bit){

  if(bit == (1<<n) -1) return 0;
  if(~memo[bit]) return memo[bit];
  
  int ret = INF;
  for(int i=0;i<n;i++){
    // if(1 & (bit>>i) == 0){
    if(bit & (1 << i)) continue;
      for(int j=0;j<n;j++){
	//if(1 & (bit>>j) == 1){
	if(bit & (1 << j)){
	  ret = min(solve(bit | (1<<i) )+p[i][j+1], ret);
	}
	ret = min(solve(bit | (1<<i) )+p[i][0], ret);
	// }
    }
  }

  return memo[bit] = ret;
}

int main(){

  for( ; ; ){

    cin >> n;
    if(!n) break;
   
    for(int i=0;i<n;i++) for(int j=0;j<=n;j++) cin >> p[i][j];

    memset(memo, -1, sizeof(memo));
    cout << solve(0) << endl;

  }

}

Measured memory_bytes: 2192
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class B { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long N = GetLong();
		var adj = Range(0, N).Select(_ => new List<long>()).ToArray();
		for(long i = 1; i < N; i++)
		{
			long a = GetLong() - 1;
			adj[a].Add(i);
		}
		WriteLine(dp(adj, 0));
	}

	private long dp(List<long>[] adj, long v)
	{
		var list = new List<long>();
		foreach(var c in adj[v])
			list.Add(dp(adj, c));
		
		list.Sort();
		list.Reverse();
		long res = 0;
		for(long i = 0; i < list.Count; i++)
			chmax(ref res, list[(int)i] + i + 1);

		return res;
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 62768
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int Amax = scan.nextInt();
        int Bmax = scan.nextInt();
        int Cmax = scan.nextInt();
        int kosu = scan.nextInt();
		int Akosu = 0;
        int Bkosu = 0;
        int Ckosu = 0;
        if (Amax < kosu) {
          Akosu = Amax;
          if ((Amax + Bmax) < kosu) {
            Bkosu = Bmax;
            Ckosu = kosu - Bmax - Amax;
          } else {
            Bkosu = kosu - Amax;
          }
        } else {
          Akosu = kosu;
        }
        System.out.println(Akosu - Ckosu);
    }
}

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

#define ll long long
#define ull unsigned long long 

int main(){
    string s;
    cin >> s;
    int n = s.length();

    ll ans=0;
    vector<int> b(n);
    if(s[0] == 'B'){
        b[0] = 1;
    }

    for(int i=1; i<n; ++i){
        if(s[i] == 'W'){
            b[i] = b[i-1];
            ans += b[i];
        }
        else
            b[i] = b[i-1]+1;
    }

    cout << ans;
}


Measured memory_bytes: 4364
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <string>

using namespace std;

int getret(int num){
	int sum = 0;

	if (num<0) return 0;

	while (num) {
		sum = sum + num % 10;
		num = num / 10;
	}

	return sum;
}

int main() {

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

	int sum = 0;

	for (int i = 0; i <= n; ++i) {
		if (a <= getret(i) && getret(i) <= b) {
			sum = sum + i;
		}
	}

	cout << sum << endl;


	return 0;
}

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

int main(){
        ll d, g;
        scanf("%lld %lld", &d, &g);
        vector<ll> p(d), c(d);
        for(int i=0; i<d; i++) scanf("%lld %lld", &p[i], &c[i]);
        for(int i=0; i<d; i++) c[i] += (i+1)*100 * p[i];

        ll mini = 10e9;
        for(int i=0; i<(1<<d); i++){
                ll summa = 0, cnt = 0, max_idx = 0;
                for(int j=0; j<d; j++){
                        if((i>>j)&1){
                                summa += c[j];
                                cnt += p[j];
                        }else max_idx = j;
                }
                ll some = (max((ll)0, g-summa)+((max_idx+1)*100-1))/((max_idx+1)*100);
                if(some <= p[max_idx]) mini = min(mini, cnt+some);
        }
        printf("%lld\n", mini);
        return 0;
}

Measured memory_bytes: 256