akhauriyash/Code-Regression huggingface dataset:
import sys

D = int(input())
C = [int(i) for i in input().split()]
L = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

S = []
for _ in range(D):
    s = [int(i) for i in input().split()]
    S.append(s)

for d in range(D):
    s = S[d]
    t = []
    for j in range(26):
        tmp = s[j]
        for k in range(26):
            if k != j:
                tmp -= C[k] * (d + 1 - L[k])
        t.append(tmp)
    ma = max(t)
    L[t.index(ma)] = d + 1
    print(t.index(ma) + 1) 


Measured memory_bytes: 69148
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

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


  vector<int> x(m);
  multiset<int> dist;
  int tmp;
  for (int i = 0; i < m; ++i) cin >> x[i];
  if (n >= m) {
    cout << "0" << endl;
    return 0;
  }
  sort(x.begin(), x.end());
  for (int i = 1; i < m; ++i) {
    tmp = x[i] - x[i -1];
    dist.insert(tmp);
  }

  int ans = 0;
  ans = x[m - 1] - x[0];
  auto itr = dist.end();
  for (int i = 0; i < n - 1; ++i) {
    --itr;
    ans -= *itr;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 5376
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>

#define ll long long
#define pll pair<ll, ll>

#define reps(i, f, n) for (int i = (f); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

const int INF = 1111111111;
const double EPS = 1e-9;

using namespace std;

void init()
{
}

void solve()
{
	int l, r, d;
	cin >> l >> r >> d;

	int ans = 0;
	reps(i, l, r + 1)
	{
		if (i % d == 0)
			ans++;
	}
	cout << ans << endl;
}

int main()
{
	init();
	solve();
}


Measured memory_bytes: 3156
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <string.h>
#include <stack>
#include <algorithm>
#include <stdio.h>
#include <functional>
using namespace std;

int main()
{
	int n, q;
	int s[10000];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}

	cin >> q;
	int cnt = 0;
	for (int i = 0; i < q; i++)
	{
		int t;
		cin >> t;
		for (int j = 0; j < n; j++)
		{
			if (t == s[j])
			{
				cnt++;
				break;
			}
		}
	}

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1196
def prime_fact(n: int) -> dict:
    ret = {}
    div = 2
    while n >= div:
        if n % div == 0:
            n //= div
            ret[div] = 1
        while n % div == 0:
            n //= div
            ret[div] += 1
        if div == 2:
            div += 1
        else:
            div += 2
    return ret


def fact(n: int) -> int:
    if n < 0:
        return -1
    if n == 0:
        return 1
    return n*fact(n-1)


def q756(N: int) -> int:
    f = fact(N)
    p = prime_fact(f)

    # それぞれ 74, 24, 14, 4, 2, 個以上の因数の数
    c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
    for v in p.values():
        if v >= 74:
            c74 += 1
        if v >= 24:
            c24 += 1
        if v >= 14:
            c14 += 1
        if v >= 4:
            c4 += 1
        if v >= 2:
            c2 += 1

    ret = c74
    if c2 > 1:
        ret += c24 * (c2-1)
    if c4 > 1:
        ret += c14 * (c4-1)
    if c2 > 2 and c4 > 1:
        ret += ((c4 * (c4-1)) // 2) * (c2-2)

    return ret


if __name__ == "__main__":
    N = int(input())
    ans = q756(N)
    print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#define f first
#define s second

using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;
typedef pair<int,int> P;

mat mul(mat &A,mat &B){
  mat C(A.size(),vec(B[0].size()));
  for(int i=0;i<A.size();i++){
    for(int k=0;k<B.size();k++){
      for(int j=0;j<B[0].size();j++){
	C[i][j]=(C[i][j]+A[i][k]*B[k][j]);
      }
    }
  }
  return C;
} 

mat pow(mat A,ll n){
  mat B(A.size(),vec(A.size()));
  for(int i=0;i<A.size();i++)B[i][i]=1;
  while(n>0){
    if(n&1)B=mul(B,A);
    A=mul(A,A);
    n>>=1;
  }
  return B;
}

int main(void){

  int n,m,z,s,d;
  vector<P>G;

  while(cin >> n >> m >> z,n|m|z){
    G.clear();
    G.push_back(P(1,1));
    for(int i=0;i<m;i++){
      cin >> s >> d;
      G.push_back(P(s,d));
      G.push_back(P(d,s));
    }

    mat A(G.size(),vec(G.size()));
 
    for(int i=0;i<G.size();i++)
      for(int j=1;j<G.size();j++)
	if(i!=j && G[i].f!=G[j].s && G[i].s==G[j].f)A[i][j]=1;

    A=pow(A,z);

    bool fg=false;
    for(int i=0;i<A.size();i++)
      if(G[i].s==n && A[0][i])fg=true;

    cout << (fg?"yes":"no") << endl;
  }
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    vi A(N);
    rep(i, N) {
        cin >> A[i];
    }

    int cnt1 = 0;
    int cnt2 = 0;
    int cnt4 = 0;
    rep(i, N) {
        if (A[i] % 4 == 0) {
            cnt4++;
        } else if (A[i] % 2 == 0) {
            cnt2++;
        } else {
            cnt1++;
        }
    }

    if (cnt2 != 0) cnt1++;

    if (cnt4 >= cnt1 - 1) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3728
n = int(input())
alst = list(map(int, input().split()))
alst.sort(reverse = True)
ans = 0
pos = 0
cnt = 0
while cnt < n - 1:
    cnt += 1
    ans += alst[pos]
    if cnt % 2 == 1:
        pos += 1
print(ans)

Measured memory_bytes: 31608
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=998244353;
inline int kpow(int a,int b)
{
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1)s=1ll*s*a%mod;
	return s;
}
int n,m,jc[500050],jcv[500050],ans;
inline int C(int a,int b)
{
	if(a<b)return 0;
	return 1ll*jc[a]*jcv[b]%mod*jcv[a-b]%mod;
}
int main()
{
	scanf("%d %d",&n,&m);
	jc[0]=1;
	for(int i=1;i<=500000;++i)jc[i]=1ll*jc[i-1]*i%mod;
	jcv[500000]=kpow(jc[500000],mod-2);
	for(int i=500000;i;--i)jcv[i-1]=1ll*jcv[i]*i%mod;
	for(int i=0;i<=n&&i<=m;++i)
		if(i&1)ans=(ans+1ll*(mod-C(n,i))*C(m,i)%mod*jc[i]%mod*kpow(n+1,m-i)%mod*kpow(m+1,n-i))%mod;
		else ans=(ans+1ll*C(n,i)*C(m,i)%mod*jc[i]%mod*kpow(n+1,m-i)%mod*kpow(m+1,n-i))%mod;
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 4096
//#pragma GCC optimize ("O3")
//#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int dp[10000];
int AB[10001];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int H = getint(), N = getint();
	rep1(i, 10000) dp[i] = 1e9;
	rep1(i, 10000) AB[i] = 2e9;

	rep(i, N) {
		int a = getint(), b = getint();
		chmin(AB[a], b);
	}
	rep1(i, 10000) {
		int k = AB[i];
		if (k < 1e9) {
			int ima = k;
			for (int j = i + i; j <= 10000; j += i) {
				ima += k;
				if (AB[j] >= ima) AB[j] = 2e9;
			}
		}
	}

	int kotae = 2e9;
	for (int i = 10000; i >= 1; i--) {
		int k = AB[i];
		if (k < 1e9) {
			auto dp2 = dp + i;
			int kazu = max(0, H - i);
			rep(j, kazu) if (dp2[j] > dp[j] + k) dp2[j] = dp[j] + k;
			for (int j = kazu; j <= H; j++) if (kotae > dp[j] + k) kotae = dp[j] + k;
		}
	}
	printf("%d", kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		// 整数の入力
		long n = sc.nextLong();
		//int x = sc.nextInt();
		//String s = sc.next();

		//String[] ss = s.split("");

		//int[] a = new int[n];

		long upper = n;
		long target =2;
		long lastHit = 1;

		while(target<=upper) {
			if(n%target==0) {
				lastHit = target;
			}else {

			}
			upper = n/target;
			target++;
		}


		System.out.println(lastHit+ n/lastHit -2);

		/*
		TreeMap<Integer,Integer> treeMap = new TreeMap<>();//sorted no duplication
		treeMap.put(b[n], n);
		*/

	}

}
/*
class City{
	int order;
	int prefecture;
	int year;
	int number;
	City(int order,int prefecture, int year){
		this.order = order;
		this.prefecture = prefecture;
		this.year = year;
	}
}
*/


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

using namespace std;
using namespace __gnu_cxx;

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

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

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

const int N = 200005;

int n;
int a[N];
int L[N], R[N];

void init() {
	for (int i = n - 1; i >= 0; i--) {
		R[i] = i + 1;
		while (R[i] < n && a[i] < a[R[i]])
			R[i] = R[R[i]];
	}
	for (int i = 0; i < n; i++) {
		L[i] = i - 1;
		while (L[i] >= 0 && a[i] < a[L[i]])
			L[i] = L[L[i]];
	}
}

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


Measured memory_bytes: 2560
H,W=map(int,input().split())
a=[]
for i in range(H):
    a.append(input())

tate=[[False]*W for i in range(H)]
yoko=[[False]*W for i in range(H)]

for i in range(H):
    if('#' in a[i]):
        for j in range(W):
            yoko[i][j]=True
for j in range(W):
    for i in range(H):
        if(a[i][j]=='#'):
            for k in range(H):
                tate[k][j]=True
            continue
for i in range(H):
    for j in range(W):
        if(tate[i][j] and yoko[i][j]):
            print(a[i][j],end='')
    if(yoko[i]!=[False]*W):
        print()

Measured memory_bytes: 4596
<?php
$input1 = trim(fgets(STDIN));
$input2 = trim(fgets(STDIN));
$array = explode(" ", $input2);

sort($array);
echo($array[0])." ";

rsort($array);
echo($array[0])." ";

$sum = 0;
for($i = 0; $i <= $input1 -1; $i++){
    $sum = $sum + $array[$i];
}
echo $sum;
?>

Measured memory_bytes: 16816
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;
using mapis = unordered_map<Int,string>;
using mapii = unordered_map<Int,Int>;
using pii = pair<Int,Int>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}
Int printX(Int r, Int D, Int X, int count){
    if(count == 10){
        return 0;
    }
    Int nextX = r*X - D;
    cout<< nextX <<endl;
    printX(r,D,nextX,count+1);

}

int myPow(int x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    return x * myPow(x, p-1);
}

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

    Int ans =0;
    rep(i,N-2){
        if(S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C'){
            ans++;
        }
    }

    cout << ans <<endl;





    return 0;
}


Measured memory_bytes: 256
//============================================================================
// Name        : hoba.cpp :)
// Author      : (O_O Diab) (Why_not) (el 3AQ)
// Version     :
// Copyright   : please, Don't touch me :(
// Description : problem in C++
// MAIN IDEA   : combinatorics NCR
//============================================================================
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define rw freopen("graphs_as_a_service.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define rep(i,a) lp(i,0,a-1)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace __gnu_pbds;
using namespace std;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int N = 3e2 + 3, mod = (int) 1e9 + 7, INF = 0x3f3f3f3f;
int ans[N * N] = { }, val[N][N] = { }, h, w, d, q, x, y;
pii po[N * N];
int main() {
#ifdef ONLINE_JUDGE
	FAST
#endif
	cin >> h >> w >> d;
	lp(i,1,h)
	{
		lp(j,1,w)
		{
			cin >> x;
			po[x]= {i,j};
		}
	}
	lp(i,1,h*w)
	{
		if (i <= d)
			ans[i] = 0;
		else
			ans[i] = ans[i - d] + abs(po[i].F - po[i - d].F)
					+ abs(po[i].S - po[i - d].S);
	}
	int q;
	cin >> q;
	while (q--) {
		cin >> x >> y;
		cout << ans[y] - ans[x] << "\n";
	}
	return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
int main()
{
  int N, M;
  cin >> N >> M;
  int L_max = 0, R_min = INT_MAX;
  rep(i, M)
  {
    int L, R;
    cin >> L >> R;
    L_max = max(L, L_max);
    R_min = min(R, R_min);
  }
  printf("%d\n", R_min>=L_max ? R_min - L_max+1 : 0);
  return 0;
}


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

int main() {
	long long N, ANS = 1000000000;
	cin >> N;
	vector<long long> X(N);
	for (int i = 0; i < N; i++) cin >> X[i];
	for (int i = 0; i <= 100; i++) {
		long long COUNT = 0;
		for (int j = 0; j < N; j++) COUNT += (X[j] - i) * (X[j] - i);
		ANS = min(ANS, COUNT);
	}
	cout << ANS << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ans=1<<30;
int main()
{
	string s;
	cin>>s;
	int l=s.length();
	for(int i=1;i<l;i++)
	{
		if(s[i]!=s[i-1])
		{
			ans=min(ans,max(i,l-i));
		}
	}
	printf("%d",min(ans,l));
	return 0;
}

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

int main() {
    int a, b;
    cin >> a >> b;
    b = 10 * b;
    int ans;
    for (int i = 0; i < 10; i++)
    {        
        if(floor((double)(b+i)*0.08) == a){
            ans = b + i;
            break;
        }
        ans = -1;
    }
    cout << ans << endl;   
    return 0;
}

Measured memory_bytes: 3592
n = list(map(int, input().split()))
num = 0

for i in range(1, n[0]+1):
  strn = str(i)
  total = 0
  for j in range(len(strn)):
    total += int(strn[j])
    
  if total <= n[2] and total >= n[1]:
    num += i

print(num)

Measured memory_bytes: 3060
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<vector>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)((x).size()))
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)j;i>=(int)k;i--)
using namespace std;
typedef long long LL;
typedef double DB;
const DB pi=acos(-1.0);
const int N=110000;
int go[N<<2][26];
int node=1;
int sz[N<<2];
int n,Q;
struct query{
	int id;
	char d[30];
}qq[N];
char str[1010000];
int tot=0;
int st[N];
int ed[N];
int ends[N<<2];
vector<int>que[N];
int ans[N];
int gtw[26][26];
int main(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%s",str+tot+1);
		st[i]=tot+1;
		ed[i]=st[i]+strlen(str+st[i])-1;
		tot=ed[i]+3;
		int now=1;
		rep(j,st[i],ed[i]){
			if(!go[now][str[j]-'a'])go[now][str[j]-'a']=++node;
			now=go[now][str[j]-'a'];
			sz[now]++;
		}
		ends[now]++;
	}
	scanf("%d",&Q);
	rep(i,1,Q){
		int k;scanf("%d",&k);
		scanf("%s",qq[i].d);
		que[k].pb(i);
	}
	rep(i,1,n){
		memset(gtw,0,sizeof gtw);
		
		int now=1;
		int rr=0;
		rep(j,st[i],ed[i]){
			int dd=str[j]-'a';
			rep(k,0,25)if(go[now][k])if(k^dd){
				gtw[dd][k]+=sz[go[now][k]];
			}
			rr+=ends[now];
			now=go[now][dd];
		}
		
		rep(j,0,que[i].size()-1){
			int xx=que[i][j];
			ans[xx]=1+rr;
			rep(d,0,25)rep(l,d+1,25)
			ans[xx]+=gtw[qq[xx].d[l]-'a'][qq[xx].d[d]-'a'];
		}
	}
	rep(i,1,Q)printf("%d\n",ans[i]);
	return 0;
}



Measured memory_bytes: 51712
pos = 0
def number(s):
	global pos
	x = pos
	if s[pos] == '-' or s[pos] == '+':
		pos += 1
	while s[pos].isdigit():
		pos += 1
	return int(s[x:pos])
expression = None
def factor(s):
	global pos
	if s[pos] == '(':
		pos += 1
		result = expression(s)
		pos += 1
		return result
	else:
		return number(s)
def term(s):
	global pos
	result = factor(s)
	while True:
		if s[pos] == '*':
			pos += 1
			result *= factor(s)
		elif s[pos] == '/':
			pos += 1
			x = factor(s)
			result = int(abs(result) / abs(x)) * cmp(x, 0) * cmp(result, 0)
		else:
			break
	return result
def _expression(s):
	global pos
	result = term(s)
	while True:
		if s[pos] == '+':
			pos += 1
			result += term(s)
		elif s[pos] == '-':
			pos += 1
			result -= term(s)
		else:
			break
	return result
expression = _expression

for i in xrange(input()):
	pos = 0
	print expression(raw_input())

Measured memory_bytes: 4272
#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
long long int heap[300];
int ukuran;
scanf("%d",&ukuran);
for(int i=1;i<=ukuran;i++) cin>>heap[i];
for(int i=1;i<=ukuran;i++){
printf("node %d: key = %d, ",i,heap[i]);
if(i/2>0)printf("parent key = %d, ",heap[i/2]);
if(i*2<=ukuran) printf("left key = %d, ",heap[i*2]);
if(i*2+1<=ukuran)printf("right key = %d, ",heap[i*2+1]);
printf("\n");
}

return 0;
}


Measured memory_bytes: 3220
a=int(input())
list1=list(map(int,input().split()))
list2=sorted(list1,reverse=True)
k=1
sum1=list2[0]
s=a-2
while(s>0) :

  if s==1 :
    sum1+=list2[k]
    break
  else :
    sum1+=list2[k]*2
    k+=1
    s-=2

print(sum1)

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

int main(){
  int N; cin>>N;
  map<int,int> mpe,mpo;
  for(int i=0;i<N;i++){
    int a; cin>>a;
    if(i&1) mpe[a]++;
    else mpo[a]++;
  }
  int e = 0, o = 0, ev, ov;
  for(auto &u:mpe){
    if(e < u.second){
      e = u.second;
      ev = u.first;
    }
  }
  for(auto &u:mpo){
    if(o < u.second){
      o = u.second;
      ov = u.first;
    }
  }
  int ans = N - e - o;
  if(ev == ov){
    mpe.erase(ev);
    mpo.erase(ov);
    int e2 = 0, o2 = 0;
    for(auto &u:mpe)
      if(e2 < u.second) e2 = u.second;
    for(auto &u:mpo)
      if(o2 < u.second) o2 = u.second;
    ans = min(N - e2 - o, N - e - o2);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
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;
}
const int INF = 2e9;
const int MOD = 1e9 + 7;

int main() {
   string s;
   cin >> s;
   int n = s.size() - 2;
   string t;
   t = s[0];
   t += to_string(n);
   t += s[s.size() - 1];
   cout << t << endl;
   return 0;
}

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

int main() {
  int a,c=0,d,f=0;
  cin>>a;
 vector<string> b(a+1);
  vector<string> e(a+1);
  map<string,int>score;
  map<string,bool> g;
for(int i=0;i<a;i++){
  cin>>b.at(i);
  score[b.at(i)]++;
}
for(int i=0;i<a;i++){
    if(score[b.at(i)]==c && g[b.at(i)]==false){
      e.at(f)=b.at(i);
      f++;
      g[b.at(i)]=true;
         c=max(score[b.at(i)],c);
      continue;
    }
     c=max(score[b.at(i)],c);
    if(c==score[b.at(i)] && g[b.at(i)]==false){
       e.at(f)=b.at(i);
      f++;
      g[b.at(i)]=true;
    }
  }
for(auto i:score ){
  if(i.second==c){
    cout<<i.first<<endl;
  }
}
}

Measured memory_bytes: 40832
#include <stdio.h>
#include <stdlib.h>

int main(void){
    int a, b, x1, x2, ii1;
    scanf("%d %d", &a, &b);
    for(ii1=0; ii1<5000; ii1++){
        if((int)(ii1*0.08)==a && (int)(ii1*0.1)==b){
            printf("%d\n", ii1);
            return 0;
        }
    }
    printf("%d\n", -1);
    return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll>PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll MOD = 1e4+7;
int main() {
    int n;
    cin >> n;
    map<string, int> mp;
    rep(i, n) {
        string tmp_s;
        cin >> tmp_s;
        ++mp[tmp_s];
    }
    int m;
    cin >> m;
    rep(i, m) {
        string tmp_t;
        cin >> tmp_t;
        --mp[tmp_t];
    }
    int ans = 0;
    for ( auto tmp_mp : mp ) ans = max(ans, tmp_mp.second);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

long unsigned euclidean_gcd(long unsigned a, long unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  long unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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

  ll a, b;
  cin >> a >> b;
  ll g =  euclidean_gcd(a, b);
  cerr << g << endl;

  ll ans = 1;
  for (ll i = 2; i*i < g; i++) {
    if (g%i == 0) {
      ans++;
      while (g%i == 0) {
        g /= i;
      }
    }
  }
  if (g != 1) ans++;

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
int main(){
	int a;
	int b=1;
	while(1){
		cin>>a;
		if(a==0){
			break;
		}else{
			cout<<"Case "<<b<<": "<<a<<endl;
			b++;
		}
	}
}
//Case i: x


Measured memory_bytes: 3040
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    
    int a = num/1000;
    int b = (num%1000)/100;
    int c = ((num%1000)%100)/10;
    int d = ((num%1000)%100)%10;
    
    if(a+b+c+d == 7){
      System.out.println(a + "+" + b + "+" + c + "+" + d + "=7");
    }else if(a-b+c+d == 7){
      System.out.println(a + "-" + b + "+" + c + "+" + d + "=7");
    }else if(a-b-c+d == 7){
      System.out.println(a + "-" + b + "-" + c + "+" + d + "=7");
    }else if(a-b-c-d == 7){
      System.out.println(a + "-" + b + "-" + c + "-" + d + "=7");
    }else if(a-b+c-d == 7){
      System.out.println(a + "-" + b + "+" + c + "-" + d + "=7");
    }else if(a+b-c+d == 7){
      System.out.println(a + "+" + b + "-" + c + "+" + d + "=7");
    }else if(a+b-c-d == 7){
      System.out.println(a + "+" + b + "-" + c + "-" + d + "=7");
    }else if(a+b+c-d == 7){
      System.out.println(a + "+" + b + "+" + c + "-" + d + "=7");
    }

  }
}


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

typedef long long ll;

const int MAX_N = 2e5 + 10;
ll A, B, C, ans = 10000;

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> A >> B >> C;
	for (int i = max({A, B, C}); i <= 100; i++) {
		ll a, b, c;
		ll res = (i - A) / 2 + (i - B) / 2 + (i - C) / 2;
		a = ((i - A) % 2);
		b = ((i - B) % 2);
		c = ((i - C) % 2);

		if (a + b + c != 0 && a + b + c != 2)
			continue;

		ans = min(ans, res + ((a + b + c) == 2));
	}

	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
/**
  * @file pa.cpp
  * @brief atcoder

  *

  * @author yao
  * @date 2018-10-06
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#define ft frist
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#endif //DBG

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

int main()
{
    int n,a,b;
    scanf("%d",&n);
    if(n==1)
        puts("Hello World");
    else //n==2
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",a+b);
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
string oddeven(long long x){
  long long a;
    a=x/2;
  if(a*2==x){
  return "even";
  }
  else{
  return "odd";
  }
}
int main(){
  long long H,W;
  cin>>H>>W;
  string a,b;
  a=oddeven(H);
  b=oddeven(W);
  if(H==1 || W==1){
  cout<<1<<endl;
  }
  else if(a=="odd" && b=="odd"){
    cout<<H*(W-1)/2+H/2+1<<endl;
  }
  else{
  cout<<(H*W)/2<<endl;
  }
}

Measured memory_bytes: 3604
#include <iostream>
#include <iso646.h>
using namespace std;

int main()
{
    int n,a;
    int k =0;
    cin >>n ;
    for(int i = 0; i<n;i++){
        cin >> a;
        while(a%2 ==0){
            a = a/2;
            k++;
        }
    }
   cout << k;
    return 0;
}

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

using namespace std;
#define PI 3.1415926535897932384626
#define ll long long
#define ull unsigned long long

#define all(x) x.begin(), x.end()
#define fo(i, n) for (i = 0; i < n; i++)
#define sortall(x) sort(all(x))

#define vi vector<int>
#define vs vector<string>
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, int> pii;
typedef vector<psi> vpsi;
typedef vector<psi> vpci;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
//=======================

const int MOD = 1'000'000'007;
const int N = 2e6 + 13;

//=======================
vi g[N];
int a[N];
int n, m, k;
//=======================
int AC = 0, WA = 0, TLE = 0, RE = 0;
void solve()
{
    string s;
    cin >> s;
    if (s == "AC")
        AC++;
    if (s == "WA")
        WA++;
    if (s == "TLE")
        TLE++;
    if (s == "RE")
        RE++;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    printf("AC x %d\n", AC);
    printf("WA x %d\n", WA);
    printf("TLE x %d\n", TLE);
    printf("RE x %d", RE);
}

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define REP(idx, N) for (u64 idx = 0; idx < N; idx++)

int main() {
  u32 N = 0;
  cin >> N;

  switch (N % 10) {
  case 2:
  case 4:
  case 5:
  case 7:
  case 9:
    cout << "hon" << endl;
    break;
  case 0:
  case 1:
  case 6:
  case 8:
    cout << "pon" << endl;
    break;
  default:
    cout << "bon" << endl;
    break;
  }

  return 0;
}


Measured memory_bytes: 3668
#include <stdio.h>
int main(void) {
int A,B,C,K;
scanf("%d%d%d%d",&A,&B,&C,&K);
if(K<=A){
printf("%d\n",K);
}else if(A<K&&K<=A+B){
printf("%d\n",A);
}else{
printf("%d\n",A-(K-(A+B)));
}
return 0;
}

Measured memory_bytes: 1708
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

int main(){
  fix20;
  int n;
  cin >> n;
  vector<double> p(n);
  rep(i,n) cin >> p[i];
  vector<vector<double>> dp(n+1, vector<double>(n+1, 0));
  dp[0][0] = 1.0;
  rep(i,n){
    rep(j,n+1){
      if(j == 0) dp[i+1][j] = dp[i][j] * (1.0 - p[i]);
      else dp[i+1][j] = dp[i][j] * (1.0 - p[i]) + dp[i][j-1] * p[i];
    }
  }
  double ans = 0;
  rep(i,n+1){
    if(i > n - i) ans += dp[n][i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 73804
#include <bits/stdc++.h>
using namespace std;
long long int power( long long int x, long long int y, long long int p) 
{long long int res = 1;
    x = x % p; 
    while (y > 0) { 
        if (y & 1) 
            res = (res * x) % p; 
  
        y = y >> 1;
        x = (x * x) % p; 
    } 
    return res; 
} 
long long int  modInverse(long long int n, long long int p) 
{ 
    return power(n, p - 2, p); 
}  
long long int  nCrModPFermat(long long int n, long long int r, long long int p) 
{  
    if (r == 0) 
        return 1; 
long long int fac[n + 1]; 
    fac[0] = 1; 
    for (int i = 1; i <= n; i++) 
        fac[i] = (fac[i - 1] * i) % p; 
  
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
} 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);
   long long int s; cin>>s;
   long long int m=1000000007;
   long long int ans=0;
   if(s<3){cout<<0;
   }
   else{
   for(long long int n=1;n<=s/3;n++){
   long long int q=s-3*n;
  ans=(ans+nCrModPFermat(q+n-1,q,m))%m;
   }
   cout<<ans;
}
	return 0;
}


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

template <typename Monoid>
struct SegmentTree {
  using F = function<Monoid(Monoid, Monoid)>;

  int sz;
  vector<Monoid> seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) { seg[k + sz] = x; }

  void build() {
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a++]);
      if (b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const { return seg[k + sz]; }
};

int N, K;
vector<int> P, Q;

int main() {
  cin >> N >> K;
  P.resize(N);
  rep(i, N) cin >> P[i];
  Q = vector<int>(P);

  SegmentTree<int> segMin(
      N, [](int a, int b) { return min(a, b); }, INT_MAX),
      segMax(
          N, [](int a, int b) { return max(a, b); }, INT_MIN);

  rep(i, N) {
    segMin.update(i, P[i]);
    segMax.update(i, P[i]);
  }

  int ans = N - K + 1;
  int nStable = 0;
  vector<int> S(N + 1, 0);
  rep(i, N - 1) S[i + 1] = S[i] + (P[i + 1] > P[i]);

  // [l, r]
  auto isStable = [&](int i) { return S[i + K - 1] - S[i] == K - 1; };

  for (int i = 0; i + K <= N; ++i) {
    if (isStable(i)) ++nStable;

    if (i + K == N || (isStable(i) && isStable(i + 1))) continue;
    if (segMin.query(i, i + K) == P[i] &&
        segMax.query(i + 1, i + 1 + K) == P[i + K])
      --ans;
  }
  if (nStable > 1) ans -= nStable - 1;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6656
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    string S;
    cin >> S;
    int A[4];
    for ( int i = 0; i < 4; i++ ) {
        A[i] = S[i] - '0';
    }
    
    string s_ans;
    for ( int i = 0; i < (1<<3); i++ ) {
        
        string s = to_string(A[0]);
        int ans = A[0];
        for ( int j = 0; j < 3; j++ ) {
            if ( ( 1 << j ) & i ) {
                ans += A[j+1];
                s += '+';
            }
            else {
                ans -= A[j+1];
                s += '-';
            }
            s += '0' + A[j+1];
        }
        if ( ans == 7 ) {
            s_ans  = s;
            break;
        }
        
    }
    
    cout << s_ans + "=7" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int ans=0,x=0,n;

    string s;
    cin>>n>>s;

    for(int i=0; i<s.size(); i++){

        if(s[i]=='I')
           x++;
        else x--;

        ans=max(ans,x);
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
	char a[3];
	for (int i = 0; i < 3; i++) {
		cin >> a[i];
		if (a[i] == '1')a[i] = '9';
		else a[i] = '1';
	}
	for (int i = 0; i < 3; i++) {
		cout << a[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
long long sq(long long x)
{
	long long r=sqrt(x)-2;
	cmax(r,0);
	while(r*r<=x)++r;
	return r-1;
}
long long work(long long a,long long b)
{
	if(a==b)return a-1<<1;
	if(a<b)std::swap(a,b);
	long long s=a*b-1;
	long long q=sq(s);
	long long ans=0;
	if(q&&q*(q+1)>s)++ans,--q;
	return ans+q+q-1;
	ans+=q;
	--q;
	int fl=0;
	while(q>0)
	{
		if(q==b)--q,fl=1;
		if(q==0)break;
		long long l=s/(q+1)+1,r=s/q;
		if(l!=r)break;
		if(l==a)if(fl)return ans+dmax(q-1,0);else return ans+dmax(q-2,0);
		--q;
	}
	return ans+dmax(q-1,0);
}
int main()
{
	int T=io::F();
	while(T--)printf("%lld\n",work(io::F(),io::F()));
	//for(register int i=1;i<=100;++i,puts(""))
	//	for(register int j=1;j<=100;++j)
	//		printf("%2lld ",work(i,j));
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

vector<int> arr[3];

vector<int> g[200010];
int cnt[3];
int color[200010];


#ifdef CLION

ifstream ifs("/home/kyuridenamida/atcoder-workspace/hitachi2020/C/in_1.txt");
#define cin ifs
#define scanf DONT_USE_SCANF
#endif

int placeholder;

void putColor(int x, vector<int> priority) {
    for (int col : priority) {
        if (cnt[col] > 0) {
            cnt[col]--;
            color[x] = col;
            return;
        }
    }
}


bool vis[200010];

vector<int> gr[2];

void dfs(int root, int col) {
    if (vis[root]) return;
    gr[col].push_back(root);
    vis[root] = true;
    for (auto i : g[root]) {
        dfs(i, col ^ 1);
    }
}

void solve(long long N, std::vector<long long> a, std::vector<long long> b) {
    memset(color, -1, sizeof(color));
    for (int i = 1; i <= N; i++) {
        cnt[i % 3]++;
        arr[i % 3].push_back(i);
    }

    for (int i = 0; i < N - 1; i++) {
        a[i]--;
        b[i]--;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0, 0);
    if (gr[0].size() < gr[1].size()) swap(gr[0], gr[1]);

    if (gr[0].size() <= cnt[0]) {
        placeholder = 2;
        for (auto i : gr[0]) {
            putColor(i, {0});
        }
        for (auto i : gr[1]) {
            putColor(i, {1, 2, 0});
        }
    } else if (gr[1].size() <= cnt[0]) {
        placeholder = 2;
        for (auto i : gr[1]) {
            putColor(i, {0});
        }
        for (auto i : gr[0]) {
            putColor(i, {1, 2, 0});
        }
    } else {
        placeholder = 0;
        for (auto i : gr[0]) {
            putColor(i, {1, 0});
        }
        for (auto i : gr[1]) {
            putColor(i, {2, 0});
        }
    }


    for (int i = 0; i < N; i++) {
        cout << arr[color[i]].back() << " ";
        arr[color[i]].pop_back();
    }


}

int main() {
    long long N;
    cin >> N;
    std::vector<long long> a(N - 1);
    std::vector<long long> b(N - 1);
    for (int i = 0; i < N - 1; i++) {
        cin >> a[i];
        cin >> b[i];
    }
    solve(N, std::move(a), std::move(b));
    return 0;
}


Measured memory_bytes: 22552
/*                        ______
 _______   /\     |``\   |        |  /
    |     /  \    |__/   |____    |/
    |    / _ _\   |  \   |        |\
    |   /      \  |   \  |______  |  \

            Dept. of CSE
        Comilla  University

*/
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Node struct node
#define spc " "
#define  E  2.71828182845904523536
#define pb push_back
#define pp pop_back
#define valid(nx,ny) nx>=0 && nx<n && ny>=0 && ny<m
#define ee endl
#define pii pair<int,int>
#define infinity 10000000000000000
#define mod 1000000007
int fx[]={0,0,+1,-1};
int fy[]={+1,-1,0,0};

using namespace std;
///check n=1;
///check corner case;
const int maX=1e5+1;
vector<ll>Graph[maX],cost[maX];
ll visit[maX];
ll x[10];
ll y[10];

int main()
{
    ll n,i,m,x,j,y;
    cin>>n>>m>>x>>y;
    ll ara[n];
    ll bra[m];
    for(i=0;i<n;i++)cin>>ara[i];
    for(j=0;j<m;j++)cin>>bra[j];
    sort(ara,ara+n);
    sort(bra,bra+m);
    ll z=ara[n-1]+1;
    if(z> x && z<=y && z<=bra[0])cout<<"No War"<<endl;
    else cout<<"War"<<endl;
return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n >= 3200)  cout << s << endl;
    else cout << "red" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
const long long MOD=2019;

int main(void){
    long long L,R;
    cin>>L>>R;

    if(L/MOD < R/MOD){
        cout<<"0\n";
        return 0;
    }

    L%=MOD;
    R%=MOD;

    int ans=MOD;
    int pro=0;
    for(int i=L; i<=R; i++){
        for(int j=i+1; j<=R; j++){
            pro=(i*j)%MOD;
            if(pro<ans){
                ans=pro;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
n,k,a[100000],s,S,i;
main(){
	for(;scanf("%d%d",&n,&k),n;){
		s=0;
		S=-1e9;
		for(i=0;i<n;i++){
			scanf("%d",a+i);
			s+=a[i];
			if(i>=k){
				s-=a[i-k];
				if(s>S)
					S=s;
			}
		}
		if(s>S)
			S=s;
		printf("%d\n",S);
	}
	exit(0);
}

Measured memory_bytes: 0
object Main extends App {
  val o = io.StdIn.readLine
  val e = io.StdIn.readLine

  val n = o.length

  if (o.length == e.length) {
    val result = for (index <- 0 until n) yield o(index).toString+e(index).toString
    println(result.mkString)
  } else {
    val pre_result = for (index <- 0 until n-1) yield o(index).toString+e(index).toString
    val result = pre_result:+o.last
    println(result.mkString)
  }
}

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

using namespace std;

int main(){
    int n;
    while(true){
        cin>>n;
        if(n==0)break;
        vector<int> k(n);
        for (int i = 0; i < n; ++i) {
            cin>>k[i];
        }
        string s;
        cin>>s;
        vector<char> ans;
        for (int i = 0; i < s.size(); ++i) {
            int key=k[i%n];
            bool lc=('a'<=s[i]&&s[i]<='z');
            if(lc){
                if(s[i]-key>='a'){
                    ans.push_back(s[i]-key);
                }
                else {
                    key-=s[i]-'a'+1;
                    if(key<=25)ans.push_back('Z'-key);
                    else {
                        key-=26;
                        ans.push_back('z'-key);
                    }
                }
            }
            else{
                if(s[i]-key>='A'){
                    ans.push_back(s[i]-key);
                }
                else {
                    key-=s[i]-'A'+1;
                    if(key<=25)ans.push_back('z'-key);
                    else {
                        key-=26;
                        ans.push_back('Z'-key);
                    }
                }
            }
        }
        for(auto i:ans)cout<<i;
        cout<<endl;
    }
    return 0;
}


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

int main()
{	
	string s;

	while (cin >> s) {
		string u;

		if (s.size() % 2 == 1)
			cout << "NA" << endl;
		else {
			for (int i = 0; i < (int)s.size(); i += 2) {

				int t = stoi(s.substr(i, 2));

				if (t / 10 < 1 || t / 10 > 6 || t % 10 > 5) {
					u = "NA";
					break;
				}

				t = t / 10 * 5 + t % 10 + 91;

				if (t == 123)
					t = 46;
				else if (t == 124)
					t = 63;
				else if (t == 125)
					t = 33;
				else if (t == 126)
					t = 32;

				u += (char)t;
			}
			cout << u << endl;
		}
	}

	return 0;
}



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

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

  int p[n];
  int min = n+1;
  int num = 0;
  for(int i = 0; i < n; i++){
    cin >> p[i];

    if(min > p[i]){
      min = p[i];
      num++;
    }
  }

  cout << num << endl;

  return 0;
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define fi first
#define se second
#define setpre(x) cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ cout << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 100005;

/* ...o(^-^)o... */

int main(){
    lint h, n; cin >> h >> n;
    rep(i, n){
        lint a; cin >> a; h -= a;
    }
    yn(h <= 0);
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
#define mk make_pair
#define fir first
#define sec second
#define il inline
#define rg register
#define pb push_back
using namespace std;
const int N = 100010; 
int n,m,a[N];
ll pre[N],suf[N];
void solve(int x){
	int p = lower_bound(a+1,a+n+1,x)-a;
	int l = (n - p + 2)>>1, r = min((n+1)>>1, n - p + 1);
//	int l = 1, r = n + 1;  
	while(l<r){
		int mid = (l+r)>>1;
		int p1 = max(n - mid * 2, 0) , p2 = n - mid;
		if( abs( a[p1] - x ) > abs( a[p2] - x) ) r = mid;
		else l = mid + 1;
	}
	ll ans=pre[n]-pre[n-r]+suf[1]-suf[max(1,n-r*2+1)];
	printf("%lld\n",ans);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+a[i]; 
		if(i&1)suf[n-i+1]=suf[n-i+2]+a[n-i+1];
		else suf[n-i+1]=suf[n-i+2];
	} 
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x);
		solve(x);
	}
	return 0;
}//by tkys_Austin;


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
int N, M;

int main() {
    cin >> N >> M;
    vector<char> S(N);
    vector<char> T(M);
    for(int i = 0; i < N; ++i) {
        cin >> S.at(i);
    }
    for(int j = 0; j < M; ++j) {
        cin >> T.at(j);
    }

    int G = std::__gcd(N, M);
    int n, m;
    n = N/G; m = M/G;
    for(int k = 1; k <= G; ++k) {
        if(S.at((k-1) * n) != T.at((k-1) * m)) {
            cout << "-1" << endl;
            return 0;
        }
    }

    printf("%lld\n", 1ll * N * M / G);
    return 0;
}

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

using namespace std;

typedef long long int64;

vector< int > tree[100000], g[100000];
int sg[100000];

int getSG(int v)
{
  if(sg[v] != -1) return sg[v];
  if(g[v].size() == 0) return sg[v] = 1;
  sg[v] = 0;
  for(int i = 0; i < g[v].size(); i++) {
    sg[v] ^= getSG(g[v][i]);
  }
  return sg[v] = sg[v] + 1;
}

int getSGSum()
{
  memset(sg, -1, sizeof(sg));
  return (getSG(0));
}

void dfs(int idx, int par = -1)
{
  for(auto &to : tree[idx]) {
    if(to == par) continue;
    dfs(to, idx);
    g[idx].push_back(to);
  }
}

int main()
{
  int N;
  cin >> N;
  for(int i = 1; i < N; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    tree[a].emplace_back(b);
    tree[b].emplace_back(a);
  }
  dfs(0);
  if(getSGSum() == 1) cout << "Bob" << endl;
  else cout << "Alice" << endl;
}

Measured memory_bytes: 16256
#include <bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    int minx=999999999;
    for(int i=1; i<=100; i++)
    {
        int ans=0;
        for(int j=0; j<n; j++)
            ans+=(a[j]-i)*(a[j]-i);
        minx=min(ans,minx);
    }
    printf("%d\n",minx);
    return 0;
}


Measured memory_bytes: 256