akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

/**
 * ZAKIREN第5章 4-6.データ構造の応用
 * 
 * @author tdi5277
 *
 */
public class Main {
	/** 入力用 */
	private static Scanner scan = new Scanner(System.in);

	/** 出力用 */
	private static StringBuilder stringBuilder = new StringBuilder();

	/**
	 * 文字列から配列を生成します。
	 * @param size 配列のサイズ
	 * @param arrayStr 配列にしたい数字を空白繋ぎにした文字列
	 * @return 配列
	 */
	private static int[] generateArray(int size, String arrayStr) {
		int[] array = new int[size];
		Arrays.fill(array, 0);
		String[] temp = arrayStr.split(" ");
		for (int i = 0; i < size; i++) {
			array[i] = Integer.parseInt(temp[i]);
		}
		Arrays.sort(array);
		return array;
	}
	
	/**
	 * メイン。
	 * 
	 * @param args 未使用
	 */
	public static void main(String[] args) {
		// 読み込み
		int n       = Integer.parseInt(scan.nextLine());
		String strS = scan.nextLine();
		int q       = Integer.parseInt(scan.nextLine());
		String strT = scan.nextLine();
		
		// 読み込み終了
		scan.close();
		scan = null;

		// 配列を生成
		int[] arrayS = generateArray(n, strS);
		int[] arrayT = generateArray(q, strT);
		
		// 同じものを含む個数を計算
		int count = 0;
		for (int i = 0; i < arrayS.length; i++) {
			if (i > 0 && arrayS[i] == arrayS[i - 1]) {
				continue;
			}
			int left = 0;
			int right = q;
			while(left < right) {
				int mid = (left + right) / 2;
				int key = arrayS[i];
				int target = arrayT[mid];
				if (key == target) {
					count++;
					break;
				} else if (key < target) {
					right = mid;
				} else {
					left = mid + 1;
				}
			}
		}

		// 結果出力 合計
		stringBuilder.append(count);

		System.out.println(stringBuilder.toString());

	}

}



Measured memory_bytes: 69204
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  string s;
  cin>>n>>s;
  int ans=0,tmp=0;
  for(int i=0;i<n;i++){
    if(s[i]=='I') tmp++;
    if(s[i]=='D') tmp--;
    ans=max(ans,tmp);
  }
  cout<<ans<<endl;
  return 0;
}


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

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };
	static final int INF = Integer.MAX_VALUE / 3;
	static final long LINF = Long.MAX_VALUE / 3;

	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		String s = fs.next();
		int z = 0;
		int o = 0;
		for(int i=0;i<s.length();i++) {
			if(s.charAt(i)=='0')z++;
			else o++;
		}
		int min = Math.min(o, z);
		System.out.println(min * 2);
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

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

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

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

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

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

Measured memory_bytes: 23124
use std::io;

fn main() {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    let vec: Vec<i8> = line.split_whitespace().map(|s| s.parse::<i8>().unwrap()).collect();
    let (a, b, c) = (vec[0], vec[1], vec[2]);
    if a < b && b < c {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 5020
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int arr[555][555];
struct node
{
    int x1,y1,x2,y2;
    node(int x,int y,int xx,int yy):
        x1(x),y1(y),x2(xx),y2(yy){}
};
int main() {
	vector<node>ans;
	int h,w;
	cin>>h>>w;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			cin>>arr[i][j];
		}
		
	}
	 for(int i=1;i<=h;i++){
        for(int j=1;j<w;j++){
            if(arr[i][j]&1){
                ans.push_back(node(i,j,i,j+1));
                arr[i][j+1]++;
            }
        }
    }
    for(int i=1;i<h;i++){
        if(arr[i][w]&1)
        {
            ans.push_back(node(i,w,i+1,w));
            arr[i+1][w]++;
        }
    }
    cout<<ans.size()<<endl;
    
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].x1<<" "<<ans[i].y1<<" "<<ans[i].x2<<" "<<ans[i].y2<<endl;
    }
	return 0;
}

Measured memory_bytes: 5232
//K-OS WITH THE OCDE

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <climits>

using namespace std;

typedef long long int ll;
typedef long double db;


#define TEST ll t; cin>>t; while(t--)
#define vell vector<ll>
#define pl pair<ll,ll>
#define all(v) v.begin(),v.end()
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define dbg(x)  cerr << #x << ": "<< x <<endl
#define dbg2(x,y) cerr<< #x <<": "<< x <<" || "<< #y << ": " << y << endl

#define endl "\n"
#define MAX 1e18
#define MIN INT_MIN
#define mod 1000000007



void solve()
{
   ll r,g,b,k;
   cin >> r >> g >> b >> k;

   while(g <= r && k) {
   	g*=2;
   	k--;
   }

    while(b <= g && k) {
   	b*=2;
   	k--;
   } 

   if(b > g && g > r)
   cout << "Yes";
   else
   cout << "No";       
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);cin.tie(0);   
    //TEST
     solve();
}



Measured memory_bytes: 3608
#include<stdio.h>
#include<limits.h>
#define min(a,b)(((a)<(b)?(a):(b)))
int main(){
  int n,y,i,j,k,q,g,f[102],u[102][102];
  scanf("%d%d%d",&n,&f[0],&f[1]);
  for(i=2;i<=n;i++){
    scanf("%d%d",&g,&f[i]);
  }
  for(i=1;i<n;i++){
    u[i][i]=0;
  }
  for(y=2; y<=n; y++){
    for(i=1; i<=n-y+1; i++){
      j=i+y-1;
      u[i][j]=INT_MAX;
      for(k=i; k<j; k++){
        q = u[i][k] + u[k+1][j] + f[i-1]*f[k]*f[j];
        u[i][j] = min(u[i][j], q);
      }
    }
  }

  printf("%d\n",u[1][n]);

  return 0;

}




Measured memory_bytes: 2108
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))

ans = 0
diff = 10**9
for i in range(n):
    if abs(a - (t-h[i]*0.006)) < diff:
        ans = i+1
        diff = abs(a - (t-h[i]*0.006))
print(ans)


Measured memory_bytes: 3060
import java.util.Scanner;
public class Main {
    public static void main(String[] args) throws Exception {
         
        Scanner sc = new Scanner(System.in);
        
        while( true ){
        
            String T = sc.next();
            int sum=0;
            
            if( T.equals("0") )
                break;

            for(int i=0;i<T.length();i++){
                sum += Character.getNumericValue(T.charAt(i)) ;
              }
            
                   System.out.print(sum);
            sum=0;
             System.out.println();
            }
        sc.close();
    }
}


Measured memory_bytes: 26176
#include<stdio.h>

#define N 100000
#define NIL -1

struct Node{int p,l,r;};

struct Node T[N];
int D[N]; //store each Depth

void print(int);
int rec(int,int);

int main(void){
  int n,k,v,d,b,r,l;
  int i,j;

  scanf(" %d",&n);
  for(i = 0; i < n; i++){
    T[i].p = T[i].l = T[i].r = NIL;
  }

  for(i = 0; i < n; i++){
    scanf(" %d",&v);
    scanf(" %d",&d);
    for(j = 0; j < d; j++){
      scanf(" %d",&b);
      if(j == 0) T[v].l = b;
      else T[l].r = b;
      l = b;
      T[b].p = v;
    }
  }

  for(i = 0; i < n; i++){
    if(T[i].p == NIL) r = i;
  }

  rec(r,0);


  for(i = 0; i < n; i++) print(i);
  
  return 0;
}

void print(int u){
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if(T[u].p == NIL) printf("root, ");
  else if(T[u].l == NIL) printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for(i = 0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if(i) printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}

int rec(int u, int p){
  D[u] = p;
  if(T[u].r != NIL) rec(T[u].r,p);
  if(T[u].l != NIL) rec(T[u].l,p+1);
}



Measured memory_bytes: 6388
import math

a, b, x = map(int, input().split())
if x == 0:
    print(0)

elif x == (a * a * b) / 2:
    print(45)

elif x > (a * a * b) / 2:
    y = 2 * (a * a * b - x) / (a * a)
    print(math.degrees(math.atan(y / a)))

else:
    y = (2 * x) / (a * b)
    print(math.degrees(math.atan(b / y)))


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int n;
vector<int> a;
int b[]={5,7,5,7,7,0};

int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    a.clear();
    rep(i,n){
      string s;
      cin>>s;
      a.push_back(s.size());
    }
    rep(i,n){
      int j=0,rest=b[0];
      repl(k,i,n){
        if(rest<a[k])break;
        rest-=a[k];
        if(rest==0){
          j++; rest=b[j];
          if(j==5)break;
        }
      }
      if(j==5){
        cout<<i+1<<endl;
        break;
      }
    }
  }
  return 0;
}



Measured memory_bytes: 3156
#include<iostream>
#include <string.h>
#include<stdio.h>
#include <math.h>
using namespace std;

int main() {
	
	string S;
	char C;

	cin >> C;

	S = "abcdefghijklmnopqrstuvwxyz";

	for (int i = 0; i < 26; i++) {
		if (S[i] == C) {
			cout << S[i + 1] << endl;;
		}
	}



	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<char> S(N);
  for(int i=0;i<N;i++){
    cin >> S.at(i);
  }
  int ans = 1;
  if( N == 1){
    cout << 1 << endl;
  }else{
    for(int i=1;i<N;i++){
      if(S.at(i-1)!=S.at(i)){
        ans++;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
typedef long long ll;
using namespace std;
vector<ll> factors;
ll n;
void seive()
{
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j+=i)
    factors[j]++;
}
int main()
{
   cin>>n;
   factors.resize(n+1);
   seive();
   ll ans=0;
   for(ll i=1;i<=n;i++)
   ans+= i*factors[i];
   
   cout<<ans<<endl;
    
}

Measured memory_bytes: 81032
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/

#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
#include <iomanip>
#include <set>
#include <stack>
#include <bitset>

////多倍長整数, cpp_intで宣言
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;

//#pragma gcc target ("avx2")
//#pragma gcc optimization ("o3")
//#pragma gcc optimization ("unroll-loops")
#define repeat(i, n, m) for(int i = n; i < (m); ++i)
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printim(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a) //少数出力
#define printLdb(a) printf("%.50Lf\n", a) //少数出力
#define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str()) //string出力
#define all(x) (x).begin(), (x).end()
#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)
#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)
#define Please return
#define AC 0
#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */
#define inf numeric_limits<double>::infinity();
#define linf numeric_limits<long double>::infinity()

using ll = long long;
using ull = unsigned long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1e9 + 7;
constexpr ll mod = 998244353;
constexpr long double eps = 1e-6;
const long double PI = acosl(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);
	while (c != '\n' && c != -1 && c != ' ') {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}


double acot(double x) {
	return PI / 2 - atan(x);
}

ll LSB(ll n) { return (n & (-n)); }

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

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

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	string s;
	scans(s);
	if (s[0] == s[1] and s[1] == s[2] and s[0] == 'R')puts("3");
	else if ((s[0] == s[1] and s[0] == 'R') or (s[1] == s[2] and s[1] == 'R'))puts("2");
	else if (s[0] == 'R' or s[1] == 'R' or s[2] == 'R')puts("1");
	else puts("0");

	Please AC;
}


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

int main(){
  int N, a, cnt = 0;
  cin >> N;
  int d[100] = {};

  for (int i = 0; i < N; i++) {
    cin >> a;
    d[a - 1]++;
  }
  for (int i = 0; i < 100; i++) if (d[i] > 0) cnt++;
  cout << cnt << endl;
}


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

#define JUDGE(x) (strstr(change,x))

int main(){
    
    int i,j;
    char str[100],change[100];
    while (gets(str) != NULL) {
        for (i=0; i<26; i++) {
            for (j=0; j<strlen(str); j++) {
                if(str[j]>='a' && str[j]<='z')
                    change[j] = str[j]+i >'z'? str[j]+i-26: str[j]+i;
                else
                    change[j] = str[j];
            }
            if (JUDGE("this") || JUDGE("that") || JUDGE("the")) {
                puts(change);
                break;
            }
        }
        memset(str, '\0', sizeof(str));
        memset(change,'\0', sizeof(change));
    }
    
    
    return 0;
    
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

const int N = 1e5+7;
int a[3][N];
int col[N * 3];

struct Fen {
int f[N];
void clear() {
    for (int i = 0; i < N; ++i) f[i] = 0;
}   
void add(int i, int x) {
    for (; i < N; i |= i + 1) 
        f[i] += x;
}   
int get(int i) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i) ans += f[i];
    return ans;
}   
int get(int l, int r) {
    //check r < l!
    return get(r) - get(l - 1);
}   
} f;

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(20); 
    #endif

    auto get = [&] (vector <int> a) {
        reverse(all(a));

        f.clear();

        int ans = 0;
        for (auto e : a) {
            ans += f.get(e);
            f.add(e, 1);
        }   
        return ans & 1;
    };  

    int n;
    cin >> n;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
            col[a[i][j]] = j;
        }

    int x = 1; 
    vector <int> inv(2);
    vector <int> p[2];
    for (int i = 0; i < n; ++i) {

        int c = col[x];

        vector <int> t;
        for (int j = 0; j < 3; ++j)
            t.app(a[j][c]);        

        auto t1 = t;
        sort(all(t1));
        vector <int> w = {x, x + 1, x + 2};
        if (t1 != w) {
            cout << "No" << endl;
            exit(0);
        }   
        if (t[1] != x + 1) {
            cout << "No" << endl;
            exit(0);
        }   

        p[i&1].app(c);

        int was = (x - 1) / 3;
        if ((was & 1) != (c & 1)) {
            cout << "No" << endl;
            exit(0);
        }   

        inv[i&1] ^= t[0] != x;        
        x += 3;
    }

    int p_inv = get(p[0]) + get(p[1]);

    vector <int> ar(n), did(n);
    for (int i = 0; i < n; ++i) {
        ar.app(a[0][i] > a[2][i]);
    }       
    for (int i = 0; i + 2 < n; ++i) {
        did[i] = ar[i];
        for (int j = 1; j <= 2 && j <= i; ++j) {
            did[i] ^= did[i - j];
        }   
    }   
    for (int i = n - 2; i < n; ++i) {
        int have = 0;
        for (int j = 1; j <= 2 && j <= i; ++j) {
            have ^= did[i - j];
        }   
        if (have != ar[i]) {
            cout << "No" << endl;
            exit(0);
        }   
    }   

    if (get(p[0]) == inv[1] && get(p[1]) == inv[0]) {
        cout << "Yes" << endl;
    }   
    else {
        cout << "No" << endl;
    }   
}


Measured memory_bytes: 12724
A,B,K = list(map(int,input().split()))
s = set()
for i in range(0,K):
    s.add(A+i)
for i in range(0,K):
    s.add(B-i)
l = sorted(filter(lambda x: A <= x <=B,list(s)))
for i in l:
    print(i)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
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;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

long long dp[200000];
long long stepup(long long step) {
    // step段数登る
    if(step < 0)
        return 0;
    if(dp[step] != 0)
        return dp[step];
    if(step == 0) {
        dp[step] = 1;
        return 1;
    }
    if(step == 1) {
        dp[step] = 1;
        return 1;
    } else if(step == 2) {
        dp[step] = 2;
        return 2;
    } else {
        long long s = stepup(step - 1) % MOD;
        s += stepup(step - 2) % MOD;
        s % MOD;
        dp[step] = s;
        return s;
    }
}

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> broken(M);
    REP(i, M) { cin >> broken[i]; }
    broken.push_back(N + 1);
    vector<long long> diff(M + 1);
    diff[0] = broken[0] - 1;
    REP(i, M) { diff[i + 1] = broken[i + 1] - broken[i] - 2; }
    long long ans = 1;
    REP(i, M + 1) {
        ans *= stepup(diff[i]);
        ans %= MOD;
        // cout << tmp << endl;
    }
    ans %= MOD;
    cout << ans << endl;
}

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

#define ipair pair<int,int>
#define rep(i,n) for(i=0;i<n;i++)
#define repj(i,j,n) for(i=j;i<n;i++)

#define PB(a,i) (a).push_back(i)
#define ALL(a) (a).begin(),(a).end()
#define SIZE(a,n) (a).resize(n)
#define SORT(a) sort(ALL(a))
#define VSORT(a, type) sort(ALL(a),greater<type>())
#define MAPIN(a,i,j) (a).insert(make_pair(i,j))

#define OK(i) cout<<"OK "<<i<<endl
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl

using namespace std;

typedef unsigned long long lli;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > Matrix;

int main() {
    ll n,i,j,k;
    vi d;

    cin>>n;
    SIZE(d,n);
    rep(i,n){
        cin>>d[i];
    }
    k=0;
    rep(i,n-1){
        repj(j,i+1,n){
            k+=d[i]*d[j];
        }
    }
    cout<<k;
	
	return 0;
}


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

vector<ll> to[11];

int main(){
    ll N,A,B;cin>>N>>A>>B;
    ll x[100010];cin>>x[0];
    ll ans=0;
    rep(i,1,N){
        cin>>x[i];
        ans+=min(A*(x[i]-x[i-1]),B);
    }
    cout<<ans<<endl;

}







Measured memory_bytes: 1024
#include <cstdio>

int main() {
    int D;
    scanf("%d",&D);
    switch(D) {
        case 25:
            printf("Christmas\n");
            break;
        case 24:
            printf("Christmas Eve\n");
            break;
        case 23:
            printf("Christmas Eve Eve\n");
            break;
        case 22:
            printf("Christmas Eve Eve Eve\n");
            break;
    }
    return 0;
}

Measured memory_bytes: 128
P = [1 for _ in range(100)]
P[0]=0
P[1]=0
for i in range(2,10):
    for j in range(i*i,100,i):
        P[j] = 0
Q = []
for i in range(100):
    if P[i]==1:
        Q.append(i)
C = {i:0 for i in Q}
N = int(input())
for i in range(2,N+1):
    x = i
    for p in C:
        while x%p==0:
            x = x//p
            C[p] += 1
#2 4 4
c2 = 0
c4 = 0
for p in C:
    if 2<=C[p]<4:
        c2 += 1
    elif C[p]>=4:
        c4 += 1
cnt = c2*((c4*(c4-1))//2)+c4*(((c4-1)*(c4-2))//2)
#2 24
c2 = 0
c24 = 0
for p in C:
    if 2<=C[p]<24:
        c2 += 1
    elif C[p]>=24:
        c24 += 1
cnt += c2*c24+c24*(c24-1)
#4 14
c4 = 0
c14 = 0
for p in C:
    if 4<=C[p]<14:
        c4 += 1
    elif C[p]>=14:
        c14 += 1
cnt += c4*c14+c14*(c14-1)
#75
c74 = 0
for p in C:
    if C[p]>=74:
        c74 += 1
cnt += c74
print(cnt)

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


using namespace std;



int main() {
    int p, q, r;
    scanf("%d %d %d", &p, &q, &r);
    int ans = p+q;
    ans = min(ans, r+p);
    ans = min(ans, q+r);
    printf("%d\n", ans);
    return 0;
}








Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<long long> scorelist;

int main() {
	int r,g,b;
	cin >> r >> g >> b;

	if ((r * 100 + g * 10 + b * 1) % 4 == 0) cout << "YES" << endl;
	else cout << "NO" << endl;
	

	return 0;
}


Measured memory_bytes: 256
#include<iostream>

int main(){
    int n;
    std::cin >> n;
    int maxVal = 0;
    int minTerm, maxTerm;
    std::cin >> minTerm;
    maxTerm = minTerm;
    for(int i = 0; i < n - 1; i++){
        int tmp;
        std::cin >> tmp;
        minTerm = std::min(minTerm, tmp);
        maxTerm = std::max(maxTerm, tmp);
        maxVal = std::max(maxVal, maxTerm - minTerm);
    }
    std::cout << maxVal << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
	os << '{';
	for(int i=0;i<sz(a);i++)
	{
		if(i>0&&i<sz(a)-1)
			os << ", ";
		os << a[i];
	}
	os << '}';
    return os;
}

int main()
{
    int n;
    scanf("%i",&n);
    int val[n][3];
    for(int i=0;i<n;i++)
        cin >> val[i][0] >> val[i][1] >> val[i][2];
    int dp[n+1][3];
    memset(dp,INT_MIN,sizeof(dp));
    for(int i=0;i<3;i++)
        dp[0][i]=val[0][i];
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            {
                if(j==k)
                    continue;
                dp[i][j]=max(dp[i][j],dp[i-1][k]+val[i][j]);
            }
        }
    }
    printf("%i\n",max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2])));
    return 0;
}


Measured memory_bytes: 2560
#include <cstdio>
using namespace std;

int main() {
	int a,b;
	while(scanf("%d %d",&a,&b)!=EOF) {
		int total=a+b,ans=1;
		while((total/1)>=10) {
			total/=10;
			++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1028
#include<stdio.h>
#include<string.h>
int main(){
  int n,m,i,j,sum,d[5000],p[5010]={0};
  char s[5000][1000],a[1000],b[1000];
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%s %d",s[i],&d[i]);
  scanf("%d",&m);
  while(m--){
    scanf("%s %s",a,b);
    for(i=0;strcmp(s[i],a);i++);
    for(j=0;strcmp(s[j],b);j++);
    for(i++;p[i];i=p[i]);
    for(j++;p[j];j=p[j]);
    if(i-j){
      if(d[i-1]<d[j-1])p[j]=i;
      else             p[i]=j;
    }
  }
  for(i=sum=0;i<n;i++){
    for(j=i+1;p[j];j=p[j]);
    sum+=d[j-1];
  }
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 5544
#include<stdio.h>

void trace(int A[], int N) {
  int i;
  for ( i = 0; i < N; i++ ) {
    if ( i > 0 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

void insertionSort(int A[], int N) {
  int i, v, j;
  for ( i = 1; i < N; i++) {
    v = A[i];
    j = i - 1;
    while ( j >= 0 && A[j] > v ) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    trace(A, N);
  }
}

int main() {
  int N, i, j;
  int A[100];

  scanf("%d", &N);
  for ( i = 0; i < N; i++ ) scanf("%d", &A[i]);

  trace(A, N);
  insertionSort(A, N);

  return 0;
}


Measured memory_bytes: 2756
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m;
  cin >> n >> m;
  vector<vector<int>> G(n);
  REP(i,m){
    int a,b; cin >> a >> b;
    a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  vector<int> ans(n, -1);
  queue<pair<int, int>> que;
  que.emplace(0, -1);
  while(!que.empty()){
    pair<int, int> p = que.front();
    que.pop();
    for(auto nv: G[p.first]){
      if(ans[nv]!=-1) continue;
      ans[nv] = p.first+1;
      que.emplace(nv, p.first);
    }
  }

  cout << "Yes\n";
  FOR(i,1,n) cout << ans[i] << '\n';
  return 0;
}


Measured memory_bytes: 10596
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;
int main(void){
  int n,k,i,j;
  string s;
  vector<string> vs;
  set<string> se;
  cin >> s >> k;
  n=s.size();
  for (i=0;i<n;i++){
    string t;
    for (j=0;i+j<n && j<5;j++){
      t.push_back(s[i+j]);
      if (se.find(t)==se.end()){
        vs.push_back(t);
        se.insert(t);
      }
    }
  }
  sort(vs.begin(),vs.end());
  cout << vs[k-1] << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
int main(){

  int a,b;
  char op;
  
  while (op != '?'){

    scanf("%d %c %d",&a,&op,&b);

    if (op == '+'){

      printf("%d\n",a+b);

	}

    if (op == '-'){

      printf("%d\n",a-b);

	}

    if (op == '*'){

      printf("%d\n",a*b);

	}

     if (op == '/'){

       printf("%d\n",a/b);

	}
     
     if (op == '?'){

       break;

	}

  }

  return 0;

}

Measured memory_bytes: 600
#include<iostream>
using namespace std;
#define N 100001
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

int table[10][N];
int dp(int n,int m,int *coin,int lim){
  rep(i,m+1){
    if ( i%coin[0]==0)table[0][i]=i/coin[0];
    else table[0][i]=lim+1;
  }
  
  REP(i,1,n){
    rep(j,coin[i]){
      if ( table[i-1][j]>lim){
	table[i][j]=lim+1;
      }else table[i][j]=0;
    }
    
    REP(j,coin[i],m+1){
      if ( table[i-1][j]>lim){
	if ( table[i][j-coin[i]]>lim)table[i][j]=lim+1;
	else table[i][j]=table[i][j-coin[i]]+1;
      }
      else table[i][j]=0;
    }    
  }
  
  return table[n-1][m]<=lim?true:false;
}

int solve(int n,int m,int *coin){
  int l=1,r=m,ret=m,mid;
  while(l<=r){
    mid =(l+r)/2;
    if ( dp(n,m,coin,mid)==false)l=mid+1;
    else {
      ret=mid;
      r=mid-1;
    }

  }

  return ret;
}

main(){
  int n,m;
  while(cin>>n>>m&&n){
    int coin[n];
    rep(i,n)cin>>coin[i];
    cout << solve(n,m,coin) << endl;
  }
}

Measured memory_bytes: 4768
def saiki(s, n, m):
  if n == 0:
    print(s)
    return
  
  a = ord('a')
  c = ord(m) + 2
  
  
  for i in range(a, c):
    saiki(s+chr(i), n-1, chr(max(i, ord(m))))
    
n = int(input())

saiki('a',n-1, 'a')

Measured memory_bytes: 4404
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
//#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod = 998244353;
const int N = 200005;
const int K = 10;
bitset < 200005 > b[2][30000];
vector < int > g[2][N];
int a[N], c[N], used[2][2][N], n, k, l;
vector < int > q[2][N];
void dfs(int f, int j, int v){
    used[f][j][v] = c[j];
    if (f == 0) q[j][c[j]].pb(v);
    if (f != 0) b[j][c[j]][v] = 1;
    for (auto u: g[j][v]){
        if (!used[f][j][u]) dfs(f, j, u);
    }
}
void naive(int c, int u){
    int res = 0;
    int comp = used[0][c][u];
   // cout << comp << endl;
    for (auto v: q[c][comp]){
       // cout << v << " " << endl;
        if (used[0][c ^ 1][u] == used[0][c ^ 1][v]) res++;
    }
    cout << res << endl;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("input.txt", "r", stdin);
    cin >> n >> a[0] >> a[1];
    for (int j = 0; j < 2; j++){
        for (int i = 1; i <= a[j]; i++){
            int u, v;
            cin >> u >> v;
            g[j][u].pb(v);
            g[j][v].pb(u);
        }
    }
    for (int j = 0; j < 2; j++){
        for (int i = 1; i <= n; i++){
            if (!used[0][j][i]){
                c[j]++;
                dfs(0, j, i);
            }
        }
    }
    c[0] = c[1] = 0;
    for (int j = 0; j < 2; j++){
        for (int i = 1; i <= n; i++){
            if (!used[1][j][i]){
                int c1 = q[j][used[0][j][i]].size();
                int c2 = q[j][used[0][j][i]].size();
                if (c1 >= K && c2 >= K){
                    c[j]++;
                    dfs(1, j, i);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if (q[1][used[0][1][i]].size() < K) naive(1, i); else
        if (q[0][used[0][0][i]].size() < K) naive(0, i); else
        cout << (b[0][used[1][0][i]] & b[1][used[1][1][i]]).count() << endl;
    }
}


Measured memory_bytes: 237696
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()
 
#define cMOD 1000000007ULL
#define cINF ((1ull<<62)-1)
#define cINFINT ((1<<30)-1)
 
int main()
{
	ll n,m; cin >> n >> m;
	map<ll,ll> mp;
	REP(i,n)
	{
		ll a; cin>>a;
		mp[a]++;
	}
	REP(i,m)
	{
		ll b,c;cin>>b>>c;
		mp[c]+=b;
	}
	ll sum = 0;
	ll idx = n;
	for( auto it = mp.rbegin(); idx > 0; ++it )
	{
		sum += (*it).first * min( idx, (*it).second );
		idx -= (*it).second;
	}
	
	cout << sum;
 
	return 0;
}

Measured memory_bytes: 12800
#include <iostream>
#include <fstream>
#include <bits/stdc++.h> 
#include <string>

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi; 
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef priority_queue<int> pqi;
typedef priority_queue<int, vi, greater<int>> mpqi;

#define IOS std::ios::sync_with_stdio(false); cin.tie(0);
#define F0R(i,a) for(int i = 0; i < a; i++)
#define R0F(i,a) for(int i = a - 1; i >= 0; i--)
#define S0RT(a,n) sort(a, a + n)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define trav(a,x) for(auto& a : x)

const int MOD = 1000000007;
const ll INF = 1000000000000000000;
const ld PI = 4*atan((ld)1);

/* NOTES TO SELF:
    Int overflow? Use all ll if in doubt.
    Edge cases? (n = 1, n = 0)
*/

int a, b, c;

int main(){
    IOS;
    cin >> a >> b >> c;
    if(a == c){
        if(a != b){
            cout << "Yes";
            return 0;
        }
        cout << "No";
        return 0;
    }
    if(a == b){
        if(a != c){
            cout << "Yes";
            return 0;
        }
        cout << "No";
        return 0;
    }
    if(b == c){
        if(a != b){
            cout << "Yes";
            return 0;
        }
        cout << "No";
        return 0;
    }
    cout << "No";
    return 0;
    // You should actually read the notes to self.
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
#define fo(i,n) for(i=0;i<n;++i)
#define forr(i,n) for(i=n-1;i>=0;--i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

ll gcd(ll a,ll b){while(a&&b)a>b?a%=b:b%=a;return a+b;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    ios_base::sync_with_stdio(false);cout.tie(NULL);
    ll x, y, a, z;
    cin>>x>>y>>a;
    ll ans = y/a;
    ans -= x/a;
    if(x%a==0)
      ans++;
      cout<<ans<<endl;
    return 0;
}


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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    float N;
    float x;
    cin>> N;
    if (N==0)
        (cout<< 0);
    else if ((int)N % 2==0)
    {
    x=0.5;
    (cout<<x);
    }
    else
    {
     x=(N+1)/(2*N);
    ( cout<< x);
    }
    return 0;
}


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

int main(){
    int r;
    int kai;

    if(scanf("%d", &r) == 1);
    kai = (r * r * (int)M_PI) / (int)M_PI;
    printf("%d",kai);
    return(0);
}

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

using namespace std;

typedef long long ll;

const char* sol3[3]={"aab","c.b","cdd"};
const char* sol4[4]={"aacd","bbcd","efgg","efhh"};
const char* sol5[5]={"aabbc","dee.c","d..fg","h..fg","hiijj"};
const char* sol6[6]={"aabbc.","ddeec.",".f.g.h",".f.g.h","i.j.kk","i.j.ll"};
const char* sol7[7]={"aa.bb.c",".dd..ec","f.gg.e.","f...h.i",".j..h.i","kj..ll.","k.mm.nn"};

char ans[1005][1005];

int main() {
  int n;
  scanf("%d",&n);
  if (n<=2) {
  	puts("-1");
  	return 0;
  }
  if (n==3) {
  	for(int i=0;i<3;i++) puts(sol3[i]);
  	return 0;
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++) ans[i][j]='.';
  int d=0;
  while (n-d>=8) {
  	for(int i=0;i<4;i++)
  	  for(int j=0;j<4;j++) ans[d+i][d+j]=sol4[i][j];
  	d+=4;
  }
  if (n-d==4) {
  	for(int i=0;i<4;i++)
  	  for(int j=0;j<4;j++) ans[d+i][d+j]=sol4[i][j];
  }
  else if (n-d==5) {
  	for(int i=0;i<5;i++)
  	  for(int j=0;j<5;j++) ans[d+i][d+j]=sol5[i][j];
  }
  else if (n-d==6) {
  	for(int i=0;i<6;i++)
  	  for(int j=0;j<6;j++) ans[d+i][d+j]=sol6[i][j];
  }
  else {
  	for(int i=0;i<7;i++)
  	  for(int j=0;j<7;j++) ans[d+i][d+j]=sol7[i][j];
  }
  for(int i=0;i<n;i++) puts(ans[i]);
  return 0;
} 

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-10;
const unsigned long long mod = 19999999999999997;
const int II = 3.1415926535;
typedef long long ll;
typedef unsigned long long ull;
ull HASH[N];
char str[N];
int num = 279;
ull Hash(char str[])
{
    ull ans = 0;
    int len = strlen(str);
    for(int i = 0;i < len;i++)
        ans = (ans*num+(ull)str[i])%mod;
    return ans%mod;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",str);
        HASH[i] = Hash(str);
    }
    int sum = n;
    sort(HASH+1,HASH+n+1);
    for(int i = 1;i < n;i++)
        if(HASH[i] == HASH[i+1])
            sum--;
    cout << sum << endl;
}

Measured memory_bytes: 5264
#include <iostream>/*{{{*/
#include <bits/stdc++.h>
#define rep(i, x) for(int i = 0; i < (int)(x); i++)
#define REPS(i,x) for(int i = 1; i <= (int)(x); i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i >= n;i--)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define FILL(x,y) memset(x,y,sizeof(x))
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define PB(a) push_back(a)
#define debug(x) cerr << __LINE__ << ": " << #x << " -> " << x << '\n'
#define INF 999999999
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};/*}}}*/

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

  map<string, int> c={};
  int n;cin>>n;
  rep(i,n){
    string s;
    cin >> s;
    c[s] += 1;
  }

  int m;cin>>m;
  rep(i,m){
    string s;
    cin >> s;
    c[s] -= 1;
  }

  int M = 0;
  for(auto x: c){
    M = max(x.second, M);
  }

  cout << M << endl;


  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <limits>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <cmath>

using namespace std;
int n;
long long cnt;

int main() {
    scanf("%d", &n);
    vector<long long> factors(n, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            factors[j]++;
        }
        cnt += factors[i];
    }
    cnt -= factors[n];
    printf("%lld\n", cnt);
    return 0;
}


Measured memory_bytes: 11064
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
using pqueg = priority_queue<int, vector<int>, greater<int>>;
using pquel = priority_queue<int, vector<int>, less<int>>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
int lcm(int a, int b){
  return a / __gcd(a, b) * b;
}
int r_int(int a, int b){
  return rand() % b + a;
}
const lint mod=1e9+7;

lint n;
vector<vector<plint>> cnct;
vector<int> seen;

void dfs(lint node, int color){
  seen[node] = color;
  for(plint next : cnct[node]){
    // 隣接していて，かつ未探索ノードを探す
    if(next.second != 0 && seen[next.first] == -1){
      // 辺の長さが偶数なら同じ色で塗る
      if(next.second%2 == 0) dfs(next.first, color);
      else dfs(next.first, (color+1)%2);
    }
  }
}

int main()
{
  cin >> n;
  cnct.assign(n, vector<plint>(0));
  REP(i,n-1){
    lint x, y, edge;
    cin >> x >> y >> edge;
    x--;
    y--;
    cnct[x].push_back({y, edge});
    cnct[y].push_back({x, edge});
  }

  seen.assign(n, -1);
  dfs(0, 0);

  REP(i,n) cout << seen[i] << "\n";
  return 0;
}


Measured memory_bytes: 9600
#include <iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<limits.h>

#define MOD 1000000007
#define DEBUG 0


using namespace std;

long long int modpow(long long int a, int n) {

	if (n == 0)return 1;
	if (n == 1) return a;

	long long int wk = modpow(a, n / 2);

	long long int ret = 0;
	if (n % 2 == 0) {
		ret = 1;
	}
	else {
		ret = a;
	}

	return (((ret * wk) % MOD) * wk) % MOD;

}

long long int gcd(long long int a, long long int b) {
	long long int tmp;
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	long long int r = a % b;

	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

long long int lcm(long long int a, long long int b) {

	long long int wk_int;

	wk_int = (a * b) % MOD;
	
	long long int ret;

	ret = (wk_int * modpow(gcd(a, b), MOD - 2)) % MOD;

	return ret;

}

bool isPrime(int n) {
	if (n == 1)return false;
	if (n == 2)return true;

	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}

	return true;
}








int main()
{
	int n;
	string str;
	cin >> n;
	cin >> str;


	int wk_left = 0;
	int wk_right = 0;

	int addition_left = 0;
	int addition_right = 0;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			wk_left++;
		}
		else {
			wk_right++;
			if (wk_right > wk_left) {
				wk_left++;
				addition_left++;
			}
		}
	}

	wk_left = 0;
	wk_right = 0;

	for (int i = str.length() - 1; i >= 0; i--) {
		if (str[i] == ')') {
			wk_right++;
		}
		else {
			wk_left++;
			if (wk_left > wk_right) {
				wk_right++;
				addition_right++;
			}
		}
	}

	string ans = string(addition_left, '(') + str + string(addition_right, ')');

	cout << ans << endl;

	return 0;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n,m,c;
    cin>>n>>m>>c;
    ll b[m];
    rep(0,i,m){
        cin>>b[i];
    }
    ll ans=0;
    rep(0,i,n){
        ll sum=0;
        rep(0,j,m){
            ll a;
            cin>>a;
            sum+=b[j]*a;
        }
        sum+=c;
        if(sum>0){
            ++ans;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;
typedef long long LL;

const int MOD = 1e9+7;
void solve(){
    int n,k,s;
    cin>>n>>k>>s;
    vector<int> re(n,s+1);
    for(int i=0;i<k;i++){
        re[i] = s;
    }
    for(int i=0;i<n;i++){
        if(re[i]==(1e9+1)) re[i] = 1e9-1;
    }
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<re[i];
    }
    cout<<endl;
}

int main(){
    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}

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

using namespace std;

struct Primal_Dual
{
  const int INF = 1 << 30;
  typedef pair< int, int > Pi;

  struct edge
  {
    int to, cap, cost, rev;
  };
  vector< vector< edge > > graph;
  vector< int > potential, min_cost, prevv, preve;

  Primal_Dual(int V) : graph(V) {}

  void add_edge(int from, int to, int cap, int cost)
  {
    graph[from].push_back((edge) {to, cap, cost, (int) graph[to].size()});
    graph[to].push_back((edge) {from, 0, -cost, (int) graph[from].size() - 1});
  }

  int min_cost_flow(int s, int t, int f)
  {
    int V = graph.size(), ret = 0;
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    potential.assign(V, 0);
    preve.assign(V, -1);
    prevv.assign(V, -1);

    while(f > 0) {
      min_cost.assign(V, INF);
      que.push(Pi(0, s));
      min_cost[s] = 0;

      while(!que.empty()) {
        Pi p = que.top();
        que.pop();
        if(min_cost[p.second] < p.first) continue;
        for(int i = 0; i < graph[p.second].size(); i++) {
          edge &e = graph[p.second][i];
          int nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];
          if(e.cap > 0 && min_cost[e.to] > nextCost) {
            min_cost[e.to] = nextCost;
            prevv[e.to] = p.second, preve[e.to] = i;
            que.push(Pi(min_cost[e.to], e.to));
          }
        }
      }
      if(min_cost[t] == INF) return -1;
      for(int v = 0; v < V; v++) potential[v] += min_cost[v];
      int addflow = f;
      for(int v = t; v != s; v = prevv[v]) {
        addflow = min(addflow, graph[prevv[v]][preve[v]].cap);
      }
      f -= addflow;
      ret += addflow * potential[t];
      for(int v = t; v != s; v = prevv[v]) {
        edge &e = graph[prevv[v]][preve[v]];
        e.cap -= addflow;
        graph[v][e.rev].cap += addflow;
      }
    }
    return ret;
  }
};

void solve()
{
  int V, E, F;
  cin >> V >> E >> F;
  Primal_Dual graph(V);
  for(int i = 0; i < E; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    graph.add_edge(a, b, c, d);
  }
  cout << graph.min_cost_flow(0, V - 1, F) << endl;
}

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

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

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

    vector<int> a(n + 1);
    rep(i, n) cin >> a[i + 1];

    vector<int> b(n + 1);
    for (ll i = n; i > 0; i--)
    {
        ll j = 2;
        ll sum = 0;
        while (i * j <= n)
        {
            sum ^= b[i * j];
            j++;
        }
        b[i] = sum ^ a[i];
    }
    vector<ll> ans;
    for (ll i = 1; i <= n; i++)
    {
        if (b[i])
            ans.push_back(i);
    }

    cout << ans.size() << endl;
    rep(i, ans.size()) cout << ans[i] << " ";

    return 0;
}

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

int main() {
  
  int N=0;
  
  cin >> N;
  
  string S;
  
  for(int i=0; i<N; i++) {
    
    cin >> S;
    
    if(S=="Y") {
    
      cout << "Four" << endl;
      
      return 0;
      
    }
    
  }
    
    cout << "Three" << endl;
  
  return 0;
  
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int n;
double dp[305][305][305];
double solve(int n1,int n2,int n3){
	if((n1+n2+n3) == 0){
		return 0;
	}
	if(dp[n1][n2][n3]==-1){
		double a=0,b=0,c=0;
		if(n3>0){
			c=solve(n1,n2+1,n3-1);
		}
		if(n2>0){
			b=solve(n1+1,n2-1,n3);
		}
		if(n1>0){
			a=solve(n1-1,n2,n3);
		}
		a*=n1;
		b*=n2;
		c*=n3;
		dp[n1][n2][n3]=(a+b+c)/(double)(n1+n2+n3)+(n/(double)(n1+n2+n3));
	}
	return dp[n1][n2][n3];
}
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	cin>>n;
	int n1=0,n2=0,n3=0,temp;
	for(int i=0;i<n;i++){
		cin>>temp;
		if(temp==1){
			n1++;
		}
		else if(temp==2){
			n2++;
		}
		else{
			n3++;
		}
	}
	for(int i=0;i<305;i++){
		for(int j=0;j<305;j++){
			for(int k=0;k<305;k++){
				dp[i][j][k]=-1;
			}
		}
	}
	printf("%.16lf\n",solve(n1,n2,n3));
	return 0;
}

Measured memory_bytes: 222080
#include<stdio.h>
 
int pos[][3]={
    {1,2,3},{1,3,5},{1,4,2},{1,5,4},
    {2,1,4},{2,3,1},{2,4,6},{2,6,3},
    {3,1,2},{3,2,6},{3,5,1},{3,6,5},
    {4,1,5},{4,2,1},{4,5,6},{4,6,2},
    {5,1,3},{5,3,6},{5,4,1},{5,6,4},
    {6,2,4},{6,3,2},{6,4,5},{6,5,3},
};
 
int f(int*d1,int*d2){
    for(int i=1;i<=6;i++)scanf("%d",d1+i);
    for(int i=1;i<=6;i++)scanf("%d",d2+i);
    for(int i=0;i<24;i++){
        int flag=1;
        for(int j=0;j<3;j++)flag&=d1[j+1]==d2[pos[i][j]];
        for(int j=3;j<6;j++)flag&=d1[j+1]==d2[7-pos[i][5-j]];
        if(flag)return 1;
    }
    return 0;
}
 
int a[110][7];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)for(int j=1;j<=6;j++)scanf("%d",&a[i][j]);
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
        if(f(a[i],a[j])){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
}


Measured memory_bytes: 2112