akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int_n():
    return list(map(int, input().split()))


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []
    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        if s != MA:
            m = min(MA, s+c)
            alt = d[u][s] + dd
            if d[u][m] > alt:
                d[u][m] = alt
                heapq.heappush(q, (d[u][m], (u, m)))
        for v in g[u]:
            a, b = g[u][v]
            alt = b + d[u][s]
            m = s - a
            if m >= 0 and d[v][m] > alt:
                d[v][m] = alt
                heapq.heappush(q, (d[v][m], (v, m)))

    for i in range(2, N+1):
        print(min(d[i]))


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()


Measured memory_bytes: 89116
#include <stdio.h>
long xor(long n){
  if (n%4==0){
    return n;
  }
  if (n%4==1){
    return 1;
  }
  if (n%4==2){
    return n^1;
  }
  if (n%4==3){
    return 0;
  }
}
int main(){
  long a,b;
  scanf("%ld%ld",&a,&b);
  if (a==0){
    printf("%ld\n",xor(b));
  }
  else{
    printf("%ld\n",xor(a-1)^xor(b));
  }
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int n, h;
const int N = 2000;
int fa[N], ok[N], cnt[N], vis[N];
int get_f(int t) {return fa[t] = (fa[t] == t? t: get_f(fa[t]));}
int main()
{
    cin >> n >> h;
    for (int i = 1; i <= h * 2; ++ i) fa[i] = i;
    for (int i = 1; i <= n; ++ i)
    {
        int a, b, c, d, l, r;
        cin >> a >> b >> c >> d;
        if (c == 0) l = a; else l = c + h;
        if (d == 0) r = b + h; else r = d;
        // cerr << l << " " << r << endl;
        cnt[l] ++; cnt[r] --;
        vis[l] = vis[r] = 1;
        if (get_f(l) != get_f(r)) fa[get_f(l)] = get_f(r);
    }
    for (int i = 1; i <= h; ++ i) if (cnt[i] < 0) return puts("NO"), 0;
    for (int i = 1; i <= h; ++ i) if (cnt[i + h] > 0) return puts("NO"), 0;
    for (int i = 1; i <= h * 2; ++ i) if (cnt[i] != 0) ok[get_f(i)] = 1;
    for (int i = 1; i <= h * 2; ++ i) if (vis[i]) if (!ok[get_f(i)]) return puts("NO"), 0;
    puts("YES");
}


Measured memory_bytes: 256
n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

count = {}

for i in range(n):
    if d[i] in count.keys():
        count[d[i]] += 1
    else:
        count[d[i]] = 1  

for i in range(m):
    if t[i] not in count.keys():
        print("NO")
        break
    if count[t[i]] == 0:
        print("NO")
        break
    else:
        if t[i] not in count.keys():
            print("NO")
            break
        else:
            count[t[i]] -=1
    if i == m-1:
        print("YES")

Measured memory_bytes: 41316
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int a,b;
int main(){
    scanf("%d%d",&a,&b);
    for(int i=1;i<=1e4+5;i++){
        if(i*2/25==a&&i/10==b){
            printf("%d",i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}


Measured memory_bytes: 128
fun main(arg: Array<String>) {
    var S = readLine()!!
    var L = S.length
    var M = mutableListOf<String>()
    var n = 0
    var m = -1
    while (n < L) {
        if (n == m) break
        m = n
        for (l in 1 .. L-n) {
            val s = S.substring(n, n+l)
            if (M.isEmpty() || M.last() != s) {
                M.add(s)
                n += l
                break
            }
        }
    }
    println(M.size)
}

Measured memory_bytes: 50152
#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
 
int N;
string s;
 
int main() {
  cin >> s;
  N = s.length();
  int p = 0;
  for (int i=0; i<N; i++) if (s[i] == 'p') p++;
  cout << (N / 2) - p << "\n";
  return 0;
}


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

int main(){
  int n; cin>>n;
  pair<pair<string,int>,int> rest[110];
  for(int i=0;i<n;i++){
    string s;
    int p;
    cin>>s >>p;
    rest[i]=make_pair(make_pair(s,-p),i);
  }
  sort(rest,rest+n);
  for(int i=0;i<n;i++)cout<<rest[i].second+1<<endl;
}

Measured memory_bytes: 256
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

X.sort(key=lambda x: x[1])
t = 0
ans = "No"
for a, b in X:
    if t + a > b:
        break
    t += a
else:
    ans = "Yes"
print(ans)



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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>0;(i)--)
#define rrep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define rrepr(i,n,m) for(int (i)=(n);(i)>(m);(i)--)
#define esort(s) sort((s).begin(),(s).end())

typedef long long ll;
typedef pair<int,int> ipair;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;

const int INF = 1000000000;
const ll LINF = 1000000000000000000;
const double PI = acos(-1.0);
const double EPS = 1e-10;

const ll MOD = 1000000007ll;
const int MAX=510000;

int N;
void solve(){
    cin>>N;
    double ans;
    if(N%2) ans=(N+1)/2.0/N;
    else ans=1.0/2;
    printf("%.10lf\n",ans);
    return;
}

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

    solve();
    return 0;
}

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

#define ll long long
#define MAX 100105

const ll INF = 1LL << 60;
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;
}

ll N, W;
ll w[MAX], v[MAX];
ll dp[105][MAX];

int main() {
    cin >> N >> W;
    for(int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= W; j++) {
            chmax(dp[i + 1][j], dp[i][j]);
            if(j >= w[i]) {
                chmax(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
            }
        }
    }

    printf("%lld\n", dp[N][W]);
}


Measured memory_bytes: 79360
n = int(input())
a1 = list(map(int,input().split()))
a2 = list(map(int,input().split()))
ame = 0
for i in range(n):
  get = sum(a1[0:i+1])+sum(a2[i:n])
  ame = max(ame,get)
print(ame)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<ll,ll> pa;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=5e2+5,mod=1e9+7;
int Q,stp;
ll X,Y,ans,f[maxn];
vector<pa>A[maxn];
void calc(vector<pa>A){
	rep2(i,0,SZ(A)){
		ll a=A[i].w1,b=A[i].w2;
		if(a<b)ans=(ans+(b<=X)*((Y-a)/b))%mod;
		else ans=(ans+(a<=Y)*((X-b)/a))%mod;
	}
}
int main(){
	f[0]=f[1]=1;
	rep(i,2,90)f[i]=f[i-1]+f[i-2];
	A[1].pb(mp(1,2));A[1].pb(mp(1,3));
	A[1].pb(mp(2,1));A[1].pb(mp(3,1));
	rep(i,1,86){
		rep2(j,0,SZ(A[i])){
			ll a=A[i][j].w1,b=A[i][j].w2;
			if(a<b){
				A[i+1].pb(mp(b,a+b));
				if(a+2*b<=f[i+3])A[i+1].pb(mp(b,a+2*b));
			}else{
				A[i+1].pb(mp(a+b,a));
				if(b+2*a<=f[i+3])A[i+1].pb(mp(b+2*a,a));
			}
		}
	}
	read(Q);
	while(Q--){
		read(X);read(Y);
		if(X==1&&Y==1){
			puts("1 1");
			continue;
		}
		if(X>Y)swap(X,Y);
		for(stp=2;;stp++)if(f[stp]>Y||f[stp-1]>X)break;
		stp-=2;
		if(stp==1){
			ans=0;
			rep(i,1,X)ans=(ans+Y/i)%mod;
			rep(i,1,X)rep(j,1,min(Y,ll(i-1)))if(i%j==0)ans=(ans+1)%mod;
			printf("%d %lld\n",stp,ans);
		}else{
			ans=0;
			calc(A[stp-1]);
			printf("%d %lld\n",stp,ans);
		}
	}
	return 0;
}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define _ ios::sync_with_stdio(false);cin.tie(0);
#define ll long long int
#define eb emplace_back
#define F first
#define S second

int main(){_
	string s;
	while(cin>>s)
	{
		int sum=0;
		for(int i=0;i<s.length();i++)
		{
			sum+=(s[i]-'0');
		}
		cout<<(sum%9?"No\n":"Yes\n");
	}

	return 0;
}

Measured memory_bytes: 3692
parseint(x) = parse(Int, x)
parseintmap(x::Array{SubString{String},1}) = map(parseint, x)

function solve(a::Int, p::Int)::Int
    (3a+p)÷2
end

function main()
    a, p = readline() |> split |> parseintmap
    println(solve(a, p))
end

main()

Measured memory_bytes: 166676
#include<bits/stdc++.h>
#include<string>
#include<cmath>

using namespace std;

#define ll long long int
#define ld long double 
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 1000000007

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

    ld a,v;
    ld b,w;
    ld t;
    cin>>a>>v>>b>>w>>t;
    if(b > a){
    if(v <= w){
        cout<<"NO\n";
    }else{
        if((b-a)/(v-w) <= t){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }
    }else if(a > b){
        if(v <= w){
            cout<<"NO\n";
        }else{
            if((a-b)/(v-w) <= t){
                cout<<"YES\n";
            }else{
                cout<<"NO\n";
            }
        } 
    }
}

Measured memory_bytes: 3728
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define FastIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define debug(x,y) cout<<x<<"-"<<y<<endl;
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long int lli;
lli minn(lli a,lli b)
{
	if(b < a)
	{
		return b;
	}
	else
	{
		 return a;
	}
	
}
lli poww(lli x,lli y)
{
	if(y==0 || x==1)return 1;
	lli ans=1;
		if(y%2==0)
		{
			lli t=poww(x,(y/2));
			return t*t;
		}
		else
		{
			return x*poww(x,y-1);
			
		}	
}
int main()
{
	FastIO
	int t=1;
	// cin>>t;
	while(t--)
	{
		lli n,k;
		cin>>n>>k;
		lli arr[200001];
		for(int i=0;i<n;i++)
		{
			lli k;
			cin>>k;
			k--;
			arr[i]=k;
		}
		lli vt[200001];
		memset(vt,-1,(n+1)*(sizeof(lli)));
		lli j=0;
		lli cur=0;
		vt[0]=0;
		lli ans;
		while(1)
		{
			// debug("cur",cur)
			if(j==k)
			{
				ans=cur;
				cout<<ans+1;
				return 0;
			}
			cur=arr[cur];
			if(vt[cur]==-1)
			{
				j++;
				vt[cur]=j;
			}
			else
			{
				j++;
				int l=j-vt[cur];
				// debug(l,j);
				k=(k-j)%l;
				break;
			}
			
		}
		memset(vt,-1,(n+1)*(sizeof(lli)));
		j=0;
		// debug(l,cur);
		while (1)
		{
			if(j==k)
			{
				ans=cur;
				break;
			}
			cur=arr[cur];
			j++;
		}
		
		cout<<ans+1;
		return 0;
	}
}


Measured memory_bytes: 6816
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <numeric>
#include <math.h>
#include <climits>

using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;

template <typename T>
T gcd(T a, T b) {
    if(a < b) gcd(b, a);
    if (b == 1) return 1;
    T r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}


int main() {
    ll N;
    cin >> N;
    
    ll sqrtN = sqrt(N)+1;
    ll sum = 0;
    for (ll k = 1; k <= sqrtN; k++) {
        ll lb = (N+k+1)/(k+1);
        ll ub = N/k;
        
        while (lb < ub) {
            ll x = (lb+ub)/2;
            ll lem = N%x;
            if (lem == k) {
                sum += x;
                break;
            }
            if (lem > k) lb = x+1;
            else ub = x;
        }
    }
    cout << sum << endl;
}


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

int main(void){
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> P(N), C(N);
    for(int i = 0; i < N; i++){
        cin >> P[i];
        P[i]--;
    }
    for(int i = 0; i < N; i++) cin >> C[i];

    vector<ll> cyclelen(N, 0);
    vector<vector<ll>> cycleC(N, vector<ll>(N + 1));
    for(int i = 0; i < N; i++){
        int x = i;
        do{
            cyclelen[i]++;
            x = P[x];
        }while(x != i);

        cycleC[i][0] = 0;
        for(int j = 1; j <= N; j++){
            x = P[x];
            cycleC[i][j] = cycleC[i][j - 1] + C[x];
        }
    }

    ll ans = -1111111111LL;
    for(int i = 0; i < N; i++){
        int L = cyclelen[i];
        for(int j = 1; j <= min(K, cyclelen[i]); j++){
            if(cycleC[i][L] < 0) ans = max(ans, cycleC[i][j]);
            else{
                ll D = cycleC[i][L];
                ll Q = (K - j) / L; 
                ans = max(ans, D * Q + cycleC[i][j]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 198840
/*
*	User: Isanchez_Aguilar
*	Problem: CodeForces 
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>

using namespace std;
using Long = long long;

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

	set<int> vals;

	for (int i = 0; i < 3; ++i)
	{
		int val;
		cin >> val;
		
		vals.insert(val);
	}

	if (vals.size() == 2)
		cout << "Yes\n";
	else
		cout << "No\n";


	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    
    //変数：使用水量「 useWater 」と水道料金の合計金額「 sumMoney 」置く
    int useWater, sumMoney;
    
    //入力：使用水量「 useWater 」を入力する
    cin >> useWater;
    
    while(1){
        //終了条件：使用水量「 useWater 」が[ -1 ]のとき終了   ♪♪♪♪♪♪♪わぁいヽ(ω・ヽ)(ノ・ω)ﾉ わぁい♪♪♪♪♪♪♪♪♪♪
        if(useWater == -1) break;
        
        //初期値：基本料金は1150円だから
        sumMoney = 1150;
    
        //条件：大きい値から水道料金の計算をする
        if(30 < useWater) sumMoney += (10 * 125) + (10 * 140) + ((useWater - 30) * 160); 
        
        //一応：上の条件を満たしてないことは30以下の数字だよ
        else if(20 < useWater) sumMoney += (10 * 125) + ((useWater - 20) * 140); 
        else if(10 < useWater) sumMoney += ((useWater - 10) * 125);
        
        //出力：先月の水道料金との差を出力する（計算：先月の水道料金[ 4280円 ]　－　今月の水道料金）
        cout << 4280 - sumMoney << endl;
        
        //再入力：使用水量「 useWater 」を入力する
        cin >> useWater;
    
    }
}




Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  FOR(i, v.size() - 1) { ret += to_string(v[i]) + ","; }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

#define MAX 300000
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

long long COM(int n, int k) {
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
  GI2(H, W);
  GI2(A, B);
  COMinit();
  ll ans = COM((H - 1) + (W - 1), (H - 1));
  A = H - A;
  B = B - 1;
  while (A < H && B >= 0) {
    ans = (ans + MOD -
           COM(A + B, A) * COM((H - A - 1) + (W - B - 1), H - A - 1) % MOD) %
          MOD;
    A++;
    B--;
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 7296
/*
 * ALDS1_7_B.cpp
 *
 *  Created on: Apr 30, 2018
 *      Author: 13743
 */

#include<iostream>
#include<algorithm>

using namespace std;

struct Node {
	int pa, lc, rc;
};

Node T[25];
int sib[25];
int D[25];
int H[25];

void setDepth(int u, int d) {
	if(u == -1) return;
	D[u] = d;
	setDepth(T[u].lc, d+1);
	setDepth(T[u].rc, d+1);
}

void setHeight(int u) {
	H[u] = 0;
	int lh=-1, rh=-1;
	if(T[u].lc != -1) {
		setHeight(T[u].lc);
		lh = H[T[u].lc];
	}
	if(T[u].rc != -1) {
		setHeight(T[u].rc);
		rh = H[T[u].rc];
	}
	H[u] = max(lh, rh) + 1;
}

int main() {
	int n;
	cin >> n;
	for(int i=0; i<n; i++) {
		T[i].pa = -1;
		sib[i] = -1;

	}
	for(int i=0; i<n; i++) {
		int id, l, r;
		cin >> id >> l >> r;
		T[id].lc = l;
		T[id].rc = r;
		if(l != -1) {
			T[l].pa = id;
			sib[l] = r;
		}
		if(r != -1) {
			T[r].pa = id;
			sib[r] = l;
		}
	}

	int root;
	for(int i=0; i<n; i++) {
		if(T[i].pa == -1) root = i;
	}
	setDepth(root, 0);
	setHeight(root);

	for(int i=0; i<n; i++) {
		cout << "node " << i << ": ";
		cout << "parent = " << T[i].pa << ", ";
		cout << "sibling = " << sib[i] << ", ";
		cout << "degree = " << (T[i].lc!=-1) + (T[i].rc!=-1) << ", ";
		cout << "depth = " << D[i] << ", ";
		cout << "height = " << H[i] << ", ";
		if(T[i].pa == -1) cout << "root" << endl;
		else if(T[i].lc + T[i].rc == -2) cout << "leaf" << endl;
		else cout << "internal node" << endl;
	}
}



Measured memory_bytes: 3100
#include<iostream>
#include<cstdlib>
#include<map>
#include<cstring>
#include<queue>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

const int w=10,h=10;
int ix,iy,i,j,k,n;
pair<int,int> splink[10];
int dx[12] = {-2,-2,-2,1,0,1,2,2,2,1,0,-1};
int dy[12] = {1,0,-1,-2,-2,-2,-1,0,1,2,2,2};


struct state{
  int x,y,t;
  state(int x,int y,int t) : x(x), y(y), t(t) {;}
  state() {;}
    };

bool ok(int x,int y,int t) {
  if(x < 0 || x >= 10 || y < 0 || y > 9) return false;
  if(abs(splink[t].first-x) <= 1 && abs(splink[t].second-y) <= 1) return true;
  return false;
}
bool bfs(int x,int y) {
  state now(x,y,0);
  queue<state> Q;
  Q.push(now);
  while(!Q.empty()) {
    now = Q.front(); Q.pop();
    if(now.t == n) return true;
    rep(j,12) {
      int ddx = now.x+dx[j],ddy = now.y+dy[j];
      if(ok(ddx,ddy,now.t)) {
	Q.push(state(ddx,ddy,now.t+1));
      }
    }
  }
  return false;
}

int main() {
  while(cin>>ix>>iy, ix|iy) {
    cin>>n;
    rep(i,n) {
      cin>>j>>k;
      splink[i] = make_pair(j,k);
    }
    if(bfs(ix,iy)) cout<<"OK"<<endl;
    else cout<<"NA"<<endl;
  }
}

Measured memory_bytes: 0
//
//  main.cpp
//  ABC172F
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main(int argc, const char * argv[]) {
    int n;
    cin>>n;
    ll a[303]={};
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll s=a[1]+a[2];
    ll c=0;
    for(int i=3;i<=n;i++){
        c^=a[i];
    }
    if(s<c||(s-c)%2==1){ // cが大きい時、不可能
        cout<<-1<<endl;
        return 0;
    }
    ll d=s-c;
    if(d<0||d%2==1){
        cout<<-1<<endl;
        return 0;
    }
    d/=2;
    if(d>a[1]||d&c){
        cout<<-1<<endl;
        return 0;
    }
    bitset<40> d40,ap40,c40;
    d40=bitset<40>(d);
    c40=bitset<40>(c);
    vector<ll>free;
    rep(i,40){
        if(c40[i]==0) {
            ap40.set(i,d40[i]);
        }else{
            free.push_back(i);
            if(d40[i]==1){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    sort(free.rbegin(),free.rend());
    ll r_ans=ap40.to_ullong();
    ll cand=0;
    for(auto& x:free){
        if(ap40.set(x,1).to_ullong()>a[1]){
            ap40.set(x,0);
        }
        cand=(ll)ap40.to_ullong();
        r_ans=max(r_ans,cand);
    }
    if(r_ans==0){ // 山１を全て移動させることはできない
        cout<<-1<<endl;
    }else{
        cout<<a[1]-r_ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3176
s = input()
for i in range((1<<3)):
    x = int(s[0])
    y = s[0]
    for j in range(3):
        if ((i>>j)&1) == 0:
            x += int(s[j+1])
            y += '+' + s[j+1]
        else:
            x -= int(s[j+1])
            y += '-' + s[j+1]
    if x == 7:
        print(y+"=7")
        break;


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;


void make_z(const string& str, vector<ll>& z); 

bool search(
    const string& text,
    const string& pattern
){
    string concat = pattern + "$" + text; 
    ll l = concat.size(); 
  
    vector<ll> z(l);
    make_z(concat, z);
 
    for (ll i = pattern.size() + 1; i < l; ++i){
        if (z.at(i) == pattern.size()){
            return true;
        }
    }
    return false;
} 

void make_z(const string& s, vector<ll>& z) { 
    const ll n = s.size(); 
    ll L = 0, R = 0; 
    for (int i = 1; i < n; ++i) {
        if (i > R) { 
            L = R = i; 
            while (R < n && s[R-L] == s[R]){
                R++;
            }
            z[i] = R-L; 
            R--; 
        }else{  // i <= R
            const ll k = i-L; 
            if (z[k] < R-i+1){
                z[i] = z[k]; 
            }else{
                L = i; 
                while (R<n && s[R-L] == s[R]){
                    R++;
                }
                z[i] = R-L; 
                R--; 
            }
        } 
    } 
} 


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

    int ans = 0;
    for(int pos = 0; pos < s.size() - 1; ++pos){
        int lo = 0;
        int hi = (s.size() - pos) / 2;
        while(lo < hi && hi > ans){
            int mid = (hi + lo + 1) / 2;

            bool res = search(
                s.substr(pos + mid, s.size() - (pos + mid)),
                s.substr(pos, mid)
            );
            if(res){
                lo = mid;
            }else{
                hi = mid - 1;
            }
        }
        ans = max(ans, lo);
    }
    cout << ans << endl;
    return 0;
}

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

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

   int pre = -999;

   for(int i = 0; i < n; i++){
       int h;
       cin >> h;

       if(pre < h){
           pre = h - 1;
       }
       else if(pre == h){
           pre = h;
       }
       else{
           cout << "No" << endl;
           return 0;
       }
   }
   cout << "Yes" << endl;
   return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define _abs(x)((x) < 0 ? (x) * -1 : (x))
#define _max(x, y)(max(0, max((x), (y))))
#define _min(x, y)(max(0, min((x), (y))))
template<typename T> inline bool __max__(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
template<typename T> inline bool __min__(T &x, const T &y) { return x > y ? x = y, 1 : 0; }

#define pb push_back
#define mp make_pair

static const ll MOD = 1e9 + 7;

int rec(const int &n, const int &k, const int &x, const int &depth) {
    if (n < depth) return x;

    int a = rec(n, k, x + k, depth + 1);
    int b = rec(n, k, x * 2, depth + 1);

    return min(a, b);
}

void solve(const int &n, const int &k) {
    int x = 1;

    int a = rec(n, k, x, 1);
    int b = rec(n, k, x, 1);

    cout << min(a, b) << '\n';
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //freopen("debug.txt", "w", stderr);

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

    int n, k;

    cin >> n;
    cin >> k;

    solve(n, k);

    return 0;
}


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

int main() {
    ll N;
    cin >> N;
    vector<ll> x(N), y(N), h(N);
    for (ll i = 0; i < N; i++) {
        cin >> x[i] >> y[i] >> h[i];
    }

    for (ll cx = 0; cx <= 100; cx++) {
        for (ll cy = 0; cy <= 100; cy++) {
            ll H = -1;
            for (ll i = 0; i < N; i++) {
                if (h[i] != 0) {
                    H = h[i] + abs(cx - x[i]) + abs(cy - y[i]);
                    break;
                }
            }
            assert(H != -1);
            bool ok = true;
            for (ll i = 0; i < N; i++) {
                if (h[i] != max(H - abs(cx - x[i]) - abs(cy - y[i]), (ll)0)) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }
    }
}

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

#define FOR(i,s,e) for(int i=(s);(i)<(int)(e);++(i))
#define REP(i,e) FOR(i,0,e)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define ppb(x) pop_back(x)
#define mp make_pair
#define mt make_tuple
#define t0(t) get<0>((t))
#define t1(t) get<1>((t))
#define t2(t) get<2>((t))

typedef long long ll;

class union_find_tree {
  private:
    vector<int> v;
    vector<int> connected_size;
    map<int, int> parent;
    map<int, int> rank;

  public:
    union_find_tree(int m) {
      v.resize(m);
      connected_size.resize(m);
      for (int i=0; i<m; i++) v[i]=i;
      for (int i=0; i<(int)v.size(); i++) {
        parent[v[i]] = v[i];
        rank[v[i]] = 1;
        connected_size[v[i]] = 1;
      }
    }

    union_find_tree(vector<int> _v) {
      v = _v;
      for (int i=0; i<(int)v.size(); i++) {
        parent[v[i]] = v[i];
        rank[v[i]] = 1;
        connected_size[v[i]] = 1;
      }
    }

    ~union_find_tree() {
      v.clear();
      parent.clear();
      rank.clear();
      connected_size.clear();
    }
    
    int root (int x) {
      return parent[x] == x ? x : parent[x] = root(parent[x]);
    }

    bool is_same(int x, int y) {
      return root(x) == root(y);
    }  

    void unite(int x, int y) {
      x = root(x);
      y = root(y);
      
      if (x == y) return;

      if (rank[x] < rank[y]) {
        parent[x] = y;
        connected_size[y] += connected_size[x];
      } else {
        parent[y] = x;
        connected_size[x] += connected_size[y];
        if (rank[x] == rank[y]) rank[x]++; 
      }
      return;
    }
};

int main() {
  vector<set<int>> s;
  int n, m;
  fscanf(stdin, "%d%d ", &n, &m);
  union_find_tree uft(n);
  REP(i,m) {
    int a, b;
    fscanf(stdin, "%d%d ", &a, &b);
    uft.unite(a-1,b-1);
  }
  vector<int> c(n);
  REP(i,n) c[uft.root(i)]++;
//REP(i,n) fprintf(stdout, "c[%d] = %d\n", i, c[i]);
  int res = 0;
  REP(i,n) res = max(res, c[i]);
  fprintf(stdout, "%d\n", res);
  return 0;
}


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

#define ll          long long
#define ull         unsigned long long
#define pb          push_back
#define pii         pair<int,int>
#define pll         pair<long,long>
#define vi          vector<int>
#define vll         vector<ll>
#define vii         vector<pii>
#define Mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)      (a).rbegin(),(a).rend()
#define ff           first
#define ss           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define mod        1000000007
//#define mod        998244353
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rem(i,a,b)  for(int i=a;i>b;i--)
#define mp(a,b)     make_pair(a,b)
#define INF         numeric_limits<ll>::max();
#define NINF        numeric_limits<ll>::min();
#define vvi(a,b,name)    vector<vector<int>> name(a,vector<int>(b,-1))
const long double pi=3.14159265359;

inline ll add(ll a,ll b,ll m){
    if((a+b)>=m)return (a+b)%m;
    return a+b;
}

inline ll mul(ll a,ll b,ll m){
    if((a*b)<m)return a*b;
    return (a*b)%m;
}

int n;
ll a[200005];
map<pair<int,int>,ll> dp;

ll go(int i,int j){
    if(j>(i+1)/2)return NINF+mod;

    if(i<1 || j<1 )return 0;

    if(dp.find({i,j})!=dp.end())return dp[{i,j}];

    return dp[{i,j}]=max(go(i-2,j-1)+a[i],go(i-1,j));

}

void solve(){
    int n;cin>>n;
    rep(i,1,n+1)cin>>a[i];
    cout<<go(n,n/2);
}

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


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

using namespace std;
const int MAXN = 110;

int n, a[MAXN];

int main() {
	scanf( "%d", &n );
	for( int i = 0; i < n; ++i ) {
		char ch; scanf( " %c", &ch );
		a[i] = ch == '(' ? 0 : 1;
	}
	int cnt = 0;
	for( int i = n-1; i >= 0; --i ) {
		cnt += a[i] == 1 ? 1 : -1;
		cnt = max(cnt, 0);
	}
	while( cnt-- ) putchar('(');
	for( int i = 0; i < n; ++i ) putchar( a[i] ? ')' : '(' );
	cnt = 0;
	for( int i = 0; i < n; ++i ) {
		cnt += a[i] == 0 ? 1 : -1;
		cnt = max(cnt, 0);
	}
	while( cnt-- ) putchar(')');
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 200002;
multiset<string> a,b;
vector<string> v;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    vector<int> v;
    int ans=0;
    cin>>n;
    FOR(i,0,n){
    	int k;cin>>k;
    	v.pb(k);
    }
    SORT(v);
    REV(v);
    FOR(i,0,n){
    	if(i%2==0)ans+=v[i];
    	else ans-=v[i];
    }
    pri(ans);
    return 0;
}


Measured memory_bytes: 256
def main():
    r, g, b, n = map(int, (input().split()))

    count = 0
    for rr in range(n//r + 1):
        for gg in range((n-rr*r)//g + 1):
            if (n-rr*r-gg*g) % b == 0:
                count += 1
    print(count)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
//コンパイラ最適化用
#pragma GCC optimize("Ofast")

//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//INT_MAXなど
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

// clang++ main.cc -std=c++11 -stdlib=libc++

/*
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    cin >> a[i];
*/

signed main(){
  ll N, K;
  cin >> N >> K;

  ll res = N;
  if (N > K)
    res = res % K;
  while (1)
    if (abs(res - K) < res)
      res = abs(res - K);
    else
      break;

  cout << res << endl;

  return 0;
}

Measured memory_bytes: 3564
n = int(input())
a = list(map(int, input().split()))
app = True

for i in a:
    if i % 2 == 0:
        if i % 3 == 0 or i % 5 == 0:
            continue
        else:
            print('DENIED')
            app = False
            break

if app == True:
    print('APPROVED')
    
    


Measured memory_bytes: 2940
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int main()
{
    long long x;
    cin >> x;
    long long s = 100;
    long long ans = 0;
    while (s < x) {
        s = static_cast<long long>(s * 1.01);
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3192
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var d1 = DateTime.Parse(Console.ReadLine());
            var d2 = new DateTime(2019,4,30);
            if (d1 > d2)
            {
                Console.WriteLine("TBD");
            }
            else
            {
                Console.WriteLine("Heisei");
            }
        }
    }
}


Measured memory_bytes: 11612
m,d = map(int,input().split())

ans = 0;

if(d >= 22):
  for i in range(1,m+1):
    for j in range(20,d+1):
      d1 = j%10
      d10 = int(j/10)
      if(d1 >= 2 and d10 >= 2 and i == d1*d10):
        ans += 1

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include <math.h>
#include <map>
#include <unordered_map>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define ci(x) cin >>x
#define co(x) cout<<x<<endl
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
long long fac(ll a) {
 long long ans=1;
 while(a>1){
 ans*=a;
 ans%=1000000007;
     a--;
    }
    return ans;
     }
int main() {
ll N;
  cin >>N;
  if(N%2==0) {
    cout<<N/2<<endl;
  }
  else {
cout<<N/2+1<<endl;
  }
}

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

using namespace std;
using ll = long long;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	map<int, int> cnt;
	ll sum = 0;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		sum += x;
		cnt[x]++;
	}
	int q;
	cin >> q;
	while (q--) {
		int b, c;
		cin >> b >> c;
		sum += (ll)(c - b) * cnt[b];
		cnt[c] += cnt[b];
		cnt[b] = 0;
		cout << sum << '\n';
	}
}

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

int main(){
  int a,b,c,x,y,money=1000000000;
  cin>>a>>b>>c>>x>>y;
  for(int i=0;i<=100000;i++){
    money=min(money,i*2*c+max(0,x-i)*a+max(0,y-i)*b);
  }
  cout<<money<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int i,j;
  char c;
  for(i=0;i<3;i++){
    for(j=0;j<3;j++){
      cin >> c;
      if(i==j)cout<<c;
    }
  }
  cout << endl;
  return 0;
}

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

struct Card{
  char suit;
  int value;
};

void selectionSort(Card A[], int N){ // N個の要素を含む0-オリジンの配列A
  int k;
  for(int i=0;i<N-1;i++){
    int minj = i;
     for(k=i+1;k<N;k++)
       if(A[k].value < A[minj].value)
         {minj = k;}
    if(i!=minj){swap(A[i],A[minj]);}
  }
}

void bubbleSort(Card A[],int N){
  for(int i=0;i<N-1;i++)
    for(int k=N-1;k>i;k--)
      if(A[k].value<A[k-1].value) swap(A[k],A[k-1]);
}

bool check(Card S[],Card B[],int N){
  for(int i=0;i<N;i++){
    if(S[i].suit!=B[i].suit) return false;
  }
  return true;
}

void print(Card A[],int N){
  cout <<A[0].suit<<A[0].value;
  for(int i=1;i<N;i++){
    cout<<" "<<A[i].suit<<A[i].value;
  }
  cout<<endl;
}
 
int main() {
  int n,temp;
  cin>>n;
  Card A[50],B[50];
  for(int i=0;i<n;i++){
    cin>>A[i].suit>>A[i].value;
    B[i]=A[i];
  }
  selectionSort(A,n);
  bubbleSort(B,n);
  print(B,n);
  cout <<"Stable"<<endl;
  print(A,n);
  if(check(A,B,n))cout<<"Stable"<<endl;
  else cout<<"Not stable"<<endl;
  return 0;
}



Measured memory_bytes: 3092
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	print(0, flush=True)
	s = input()
	if s != "Vacant":
		left = 0
		leftM = s
		print(N - 1, flush=True)
		s = input()
		if s != "Vacant":
			right = N - 1
			rightM = s
			while True:
				mid = (left + right) // 2
				print(mid, flush=True)
				s = input()
				if s == "Vacant":
					break
				elif (mid - left) % 2 == 0 and s != leftM or (mid - left) % 2 != 0 and s == leftM:
					right = mid
					rightM = s
				else:
					left = mid
					leftM = s

if __name__ == '__main__':
	main()

Measured memory_bytes: 3912
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
struct data{
	int n,p,q,r,c;
};
int main(){
	int n;
	while(cin >> n,n){
		data a[1001] = {};
		for(int i = 0; i < n; i++){
			int n,p,q,r;
			scanf("%d%d%d%d",&n,&p,&q,&r);
			data d = {n,p,q,r,(p*4+q*9+r*4)};
			a[i] = d;
		}
		int P,Q,R,C;
		scanf("%d%d%d%d",&P,&Q,&R,&C);
		bool flg = false;
		for(int i = 0; i < n; i++){
			if(P >= a[i].p && Q >= a[i].q && R >= a[i].r && C >= a[i].c){
				flg = true;
				printf("%d\n",a[i].n);
			}
		}
		if(!flg)puts("NA");
	}

	return 0;
}

Measured memory_bytes: 1260
#include <cstdio>
#include <cstring>
#define MAXN 200000

using namespace std;

int main(void){
  int n,m,f;
  
  int g[MAXN][2];
  scanf("%d%d",&n,&m);
  memset(g, 0, sizeof(g));
  for (int i=0; i<m; i++){
    int u,v;
    scanf("%d%d",&u,&v);
    if (u==1 || u==n) g[v-1][u==n]=1;
    if (v==1 || v==n) g[u-1][v==n] = 1;
  }
  f = 0;
  for (int i=1; i<n-1; i++){
    if (g[i][0] && g[i][1]) f = 1;
  }
  puts(f?"POSSIBLE":"IMPOSSIBLE");
  return 0;
}

Measured memory_bytes: 1664
import collections
S = input()
a = []
num = 0
for i,j in enumerate(S[::-1]):
    num += int(j)*(pow(10,i,2019))
    a.append(num%2019)

#print(a)
A = collections.Counter(a)
#print(A)

ans = 0
for i in A.values():
    if i>=2:
        ans += int(i*(i-1)/2)

ans += A[0]
print(ans)

Measured memory_bytes: 76128
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
	int a,b,c;
	cin >> a >> b >> c;
	if(a == b) cout << c << endl;
	else if(b == c) cout << a << endl;
	else if(c == a) cout << b << endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 60;

ll a,b;
ll c,d;

ll gcd(ll a,ll b){
  while(b != 0){
    a %= b;
    swap(a,b);
  }
  return a;
}

ll solve(ll x){
  return x-(x/c+x/d-x/(c*d/gcd(c,d)));
}

int main(){
  cin >> a >> b >> c >> d;
  cout << solve(b)-solve(a-1) << endl;

}


Measured memory_bytes: 256
// Problem : A - The Number of Even Pairs
// Contest : AtCoder - AtCoder Beginner Contest 159
// URL : https://atcoder.jp/contests/abc159/tasks/abc159_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize "trapv"//  WA to RE int!!
#include <bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORR(i,n) for(int i=n;i>=0;i--)
#define pb push_back
#define vlli vector<int>
#define slli set<int>
#define mlli map<int,int>
#define plii pair< int,int >
#define int long long int 
#define test int tt1234; cin>>tt1234;while(tt1234--)
#define endl "\n"
#define SI(a,n) int a[n];FOR(i,n) cin>>a[i];
#define input(a,n) int n;cin>>n; SI(a,n)
#define all(zz) zz.begin(),zz.end()
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define error(x) cerr << #x <<" is " << x << endl;
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define present(container, element) (container.find(element)!=container.end())
#define fint fast;test
#define set(a,x) memset(a,x,sizeof(a))
#define L(x)	((x)<<1)
#define R(x)	(((x)<<1)+1)
#define ft first
#define se second
#define MOD 1000000007
using namespace std;
template<typename... T> void rd(T&... args) { ((cin >> args), ...); }
template<typename... T> void pp(T... args) { ((cout << args << " "), ...); cout<<"\n"; }

void solve(){
	int a,b;
	rd(a,b);
	int ans=(a*(a-1))/2+(b*(b-1)/2)	;
	pp(ans);
	return;	
}


int32_t main() {
    // fint{
    	fast;
    	solve();
    // }
    return 0;
}


Measured memory_bytes: 3540
#include "algorithm"
#include "iostream"

using namespace std;

int main(){
  int m,n,A,B,B_sum,now,minas,year,FLAG;
  double rate;
  cin >> m;

  while(m--){
    int LAST_MAX=0;
      cin >> now >> year >> n;
      for(int i=0;i<n;++i){
      A=now;
      B=0;
      B_sum=0;
      cin >> FLAG >> rate >> minas;
      for(int j=0;j<year;++j){
        B=A*rate;
        if(FLAG&1)A+=B-minas;
        else{
          A-=minas;
          B_sum+=B;
        }
      }
      if(FLAG&1)LAST_MAX=max(A,LAST_MAX);
      else LAST_MAX=max(A+B_sum,LAST_MAX);
    }
    cout << LAST_MAX <<endl;
  }
  return 0;
}

Measured memory_bytes: 3136
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug" << x << endl;
using namespace std;

int main(){
    int n;
    while(cin >> n,n){
        double ave = 0, sum = 0;
        double input[1005];
        rep(i,n){
            cin >> input[i];
            ave+= input[i];
        }
        ave /= n;
        rep(i,n){
            sum += ((input[i] - ave) * (input[i] - ave));
        }
        printf("%.8lf\n", sqrt(sum / n));
    }
}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rem(i, m, n) for (int i = m; i < (n); i++)
#define eps (1e-7)
#define inf (1e9)
#define pi (acos(-1))
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];

    int j = 1;
    int count = 0;
    rep(i, n)
    {
        j = a[j - 1];
        count++;
        if (j == 2)
        {
            cout << count << "\n";
            return 0;
        }
    }

    cout << -1 << "\n";

    return 0;
}

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

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

int main() {
  int N,X,T;
  cin>>N>>X>>T;
  cout<<((N-1)/X+1)*T<<endl;
}

Measured memory_bytes: 3600
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<climits>
using namespace std;

int main() {
  int R,G,B,N;
  int r,g,b;
  int ansflg=0;
  int cnt=0;
  int tmp;

  cin >> R >> G >> B >> N;

  r = N/R;
  g = N/G;
  b = N/B;

  for(int i=0; i<=r; i++){
    for(int j=0; j<=g; j++){
      tmp = N-i*R-j*G;
      if(tmp%B==0 &&tmp >=0){
          cnt++;
          //          cout <<"i= " <<i <<"j= "<<j <<"k= " << tmp/B <<   " cnt = " << cnt <<endl; 
      }
    }
  }
  
    cout << cnt << endl;
}


Measured memory_bytes: 256
x, y  = map(int, input().split())
import itertools
mod = 10**9 + 7
def comb(a,b):
    x,y = 1,1
    for i in range(a):
        x *= (a+b-i)
        y *= (i+1)
        x %= mod 
        y %= mod
    gyakugen = pow(y,mod-2,mod)
    return x*gyakugen %mod
if (2*y-x) % 3 !=  0 or (2*x-y) % 3 != 0 or (2*y -x) < 0 or (2*x - y)<0:
    print(0)
else:
    a = int((2*y - x)/3)
    b = int((2*x - y)/3)
    print(int(comb(a,b)))


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

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PDD;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define dbl(k, x) fixed << setprecision(k) << (x)

template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}

#define _upgrade                \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)

// ********************** CODE ********************** //

const int N = 2e5 + 7;

vector<int> G[N];
vector<int> val;
vector<int> best_lis;

struct lis {
  vector<vector<int>> tab;

  void remove(int pos) {
    tab[pos].pop_back();
    if (sz(tab[pos]) == 0) {
      tab.pop_back();
    }
  }

  int bin_search(int x) {
    int L = -1;
    int R = sz(tab);
    while (L + 1 < R) {
      int M = (L + R) / 2;
      if (tab[M].back() < x) {
        L = M;
      } else {
        R = M;
      }
    }
    return R;
  }

  int add(int x) {
    int pos = bin_search(x);

    if (pos == sz(tab)) {
      tab.push_back(vector<int>());
    }

    tab[pos].push_back(x);
    return pos;
  }

  int get_lis_len() { return sz(tab); }
};

lis LIS;

void dfs(int v, int parent) {
  int pos = LIS.add(val[v]);
  // cerr << "-----\n";
  // for (auto &v : LIS.tab) {
  //   for (auto &e : v) {
  //     cerr << e << " ";
  //   }
  //   cerr << "\n";
  // }
  best_lis[v] = LIS.get_lis_len();
  for (auto &u : G[v]) {
    if (u != parent) {
      dfs(u, v);
    }
  }
  LIS.remove(pos);
}

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

  val.resize(n);
  for (auto &v : val) {
    cin >> v;
  }

  best_lis.resize(n);

  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  dfs(0, -1);

  for (auto &res : best_lis) {
    cout << res << "\n";
  }
  return 0;
}

Measured memory_bytes: 33872