akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<cmath>
#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
//#include<set>
#include<map>
//#include<list>
//#include<bitset>
#include<iomanip>

using namespace std;
using LLI = long long int;
LLI N;

//array<int, 8>dir_x = { 0,0,1,1,1,-1,-1,-1 };
//array<int, 8>dir_y = { 1,-1,1,0,-1,1,0,-1 };
//array<int, 4>dir_x2 = { 0,0,1,-1 };
//array<int, 4>dir_y2 = { 1,-1,0,0 };
//char alp[] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

class UnionFind {
public:
	vector<int>data;
	UnionFind(int size) :data(size, -1) {};
	bool unionset(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x]) {
				swap(x, y);
			}
			data[x] += data[y];
			data[y] = x;
		}
		return x != y;
	}
	bool findset(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

//LLI gcd(LLI x, LLI y) {
//	LLI  r;
//	if (x < y) {
//		swap(x, y);
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}
//LLI lcm(LLI x, LLI y) {
//	return x / gcd(x, y) * y;
//}

//long nCr(int n, int r) {
//	long ans = 1;
//	for (int i = n; i > n - r; i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1; i++) {
//		ans = ans / i;
//	}
//	return ans;
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

//#define debug(x) cerr << #x << " : " << x << endl
//#define debugv(x) cerr << #x << " : "; for(auto i:x) cerr << i << ", "; cerr<<endl

int main(void) {
	LLI M;
	cin >> N >> M;
	vector<LLI>P(N);
	UnionFind uf(N);
	for (int i = 0; i < N;i++) {
		cin >> P[i];
	}
	for (int i = 0; i < M;i++) {
		LLI x, y;
		cin >> x >> y;
		uf.unionset(x - 1,y - 1);
	}
	LLI cnt = 0;
	for (int i = 0; i < N;i++) {
		if (uf.findset(i,P[i] - 1)) {
			cnt++;
		}
	}
	cout << cnt << endl;
}


Measured memory_bytes: 1408
#include<cstdio>
using ull = unsigned long long;
const static int MOD = 1000000007;
const static int MAX_H = 100;
const static int MAX_W = 8;
ull dp[MAX_H+1][MAX_W], fibonacci[8] = {1, 1, 2, 3, 5, 8, 13, 21};

int main(){
    unsigned H, W, K;
    scanf("%u %u %u", &H, &W, &K);
    if(W == 1){
        printf("1\n");
        return 0;
    }
    K--;
    dp[0][0] = 1;
    for (size_t i = 1; i <= H; i++){
        dp[i][0] = (dp[i-1][0]*fibonacci[W-1] + dp[i-1][1]*fibonacci[W-2]) %MOD;
        for (size_t j = 1; j < W-1; j++){
            dp[i][j] = (dp[i-1][j-1]*fibonacci[j-1]*fibonacci[W - j - 1] + dp[i-1][j]*fibonacci[j]*fibonacci[W - j - 1] + dp[i-1][j+1]*fibonacci[j]*fibonacci[W - j - 2]) %MOD;
        }
        dp[i][W-1] = (dp[i-1][W-1]*fibonacci[W-1] + dp[i-1][W-2]*fibonacci[W-2]) %MOD;        
    }
    printf("%llu\n", dp[H][K]);
	return 0;
}

Measured memory_bytes: 1708
#include <stdio.h>
#include <math.h>	//10000番目の素数が104729
#define Max 104730
int main(void)
{

	int i,j,prime[Max]={0},n;
	prime[0]=1;
	prime[1]=1;
	for(i=2;i<sqrt(Max);i++){	//i<=j && i*j<Max⇒i<=sart(Max)
		for(j=2;i*j<Max;j++){
			prime[i*j]=1;		//xが素数⇒prime[x]=0,素数以外⇒prime[x]=1を代入
		}
	}
	while(scanf("%d",&n)){
		if(n==0) break;
		long long sum=0;
		int count=1;
		for(i=0;count<=n;i++){
			if(prime[i]==0){
				sum+=i;
				count++;
			}
		}
		printf("%lld\n",sum);
	}
	return 0;
}

Measured memory_bytes: 1012
#-*- coding: utf-8 -*-
import numpy as np

N, D = map(int, input().split())
X=[]
Y=[]
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

x=np.array(X)
y=np.array(Y)
distance_calc=(x**2+y**2)**0.5
cnt=0
for i in range(len(distance_calc)):
    if distance_calc[i]<=D:
        cnt+=1
print(cnt)

Measured memory_bytes: 49440
# coding: utf-8
# Your code here!
e1,e2,e3,e4=map(int,input().split())

if e1==e2 and e3==e4:
    print('yes')
elif e1==e3 and e2==e4:
    print('yes')
elif e1==e4 and e2==e3:
    print('yes')
else:
    print('no')


Measured memory_bytes: 5600
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

//arc044_b
int main(){
  string S;
  cin >> S;

  ll a[26] = {};

  REP(i,S.size())
  {
    ll tmp = S[i] - 'a';
    a[tmp]++;
  }

  string res = "Yes";

  REP(i,26)
  {
    if(a[i] % 2 != 0)
    {
      res = "No";
      break;
    }
  }

  cout << res << endl;

  return 0;
}

Measured memory_bytes: 256
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
n = gets.chomp.to_i
x = gets.chomp.split.map(&:to_i)

ans = INF
1.upto(100) do |i|
  cost = 0
  n.times do |j|
    cost += (i-x[j])**2
  end
  ans = cost if ans > cost
end

puts ans




Measured memory_bytes: 2300
#include <iostream>
using namespace std;
int main()
{
    int x,y;
    cin>>x>>y;
    if(y>4*x || y<2*x)
    {
        cout<<"No";
        return 0;
    }
    if (y%2 !=0)
    {
        cout<<"No";
        return 0;
    }
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 3636
rooms = [
        [[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, 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, 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, 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, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
        ]

num = int(input())
for _ in range(num):
    aRoom = input().split()
    rooms[int(aRoom[0])-1][int(aRoom[1])-1][int(aRoom[2])-1] = int(aRoom[3]) + rooms[int(aRoom[0])-1][int(aRoom[1])-1][int(aRoom[2])-1]

for b in range(4):
    for f in range(3):
        for r in range(10):
            print(' ',end="")
            print(int(rooms[b][f][r]),end="")
        print()
    if b <= 2:
        print("####################")



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

int H;

void maxHeapify(vector<int>& A, int i) {
	int l=2*i;
	int r=2*i+1;
	int largest;

	if(l<=H && (A[l]>A[i])) {
		largest = l;
	} else {
		largest = i;
	}

	if(r<=H && (A[r]>A[largest])) {
		largest = r;
	}

	if(largest!=i) {
		swap(A[i],A[largest]);
		maxHeapify(A,largest);
	}
	return;
}

void buildMaxHeap(vector<int>& A) {
	for(int i=H/2; i>=1; --i) {
		maxHeapify(A,i);
	}
	return;
}

int main() {
	int i;
	vector<int> A;
	scanf("%d",&H);
	A.resize(H+1);
	for(i=1; i<=H; ++i) {
		scanf("%d",&A[i]);
	}
	buildMaxHeap(A);
	for(i=1; i<=H; ++i) {
		printf(" %d",A[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 4192
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;

vector<vector<int>> graph;
vector<bool> visit;
int ans = 0;
int n;

void dfs(int v){
    visit[v] = true;
    int flag = true;
    rep(i, n){
        if(!visit[i]){
            flag = false;
            break;
        }
    }
    if(flag){
        ans++;
    }
    
    for(auto u : graph[v]){
        if(visit[u]){
            continue;
        }
        dfs(u);
    }
    visit[v] = false;
}


int main() {

    int m;
    cin >> n >> m;
    graph.resize(n);
    visit.resize(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        --a; --b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(0);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace contest8
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                //文字列読み込み
                var line_origin = Console.ReadLine();

                //空なら終わり
                if (string.IsNullOrEmpty(line_origin))
                {
                    break;
                }
                int ans = int.Parse(line_origin);

                int count = 0;
/*
 *              var choice = from a in Enumerable.Range(0, 10)
                             from b in Enumerable.Range(0, 10)
                             from c in Enumerable.Range(0, 10)
                             from d in Enumerable.Range(0, 10)
                             where a + b + c + d == ans
                             select Tuple.Create(a,b,c,d);

                foreach (Tuple<int,int,int,int> i in choice)
                {
                    count++;
                }
*/
                for (int a = 0; a < 10; a++)
                {
                    for (int b = 0; b < 10; b++)
                    {
                        for (int c = 0; c < 10; c++)
                        {
                            for (int d = 0; d < 10; d++)
                            {
                                if (a + b + c + d == ans)
                                {
                                    count++;
                                }
                            }
                        }
                    }
                }

                Console.WriteLine(count.ToString());
            }
        }
    }
}

Measured memory_bytes: 5600
#include<bits/stdc++.h>
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000001
#define MAXN        400005
#define mod         1000000007
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,d,i,j,k,sum,x,count=0;
    cin>>n>>d;
    ll a[n][d];
    for(i=0;i<n;i++){
        for(j=0;j<d;j++){
            cin>>a[i][j];
        }
    }
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            sum=0;
            for(k=0;k<d;k++){
                sum+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
            }
            x=sqrt(sum);
            if(x*x==sum){
                count++;
            }
        }
    }
    cout<<count;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

int N, K; 
long long h[100010];
long long dp[100010];
int main(){
    int N, K; cin >> N >> K;
    for (int i = 0; i < N; ++i) cin >> h[i] ;
    for (int i = 0; i < N; ++i) dp[i] = INF;
    dp[0] = 0;
    for (int i = 0; i < N; ++i){
        for( int j = 1; j <= K; ++j){
            chmin(dp[i + j], dp[i] + abs(h[i + j] - h[i]));
        }
    }
cout << dp[N - 1] << endl;    
    
    
    
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>

using namespace std;

int N, T, t[200000];
long long ans = 0;

int main(){
	cin >> N >> T;
	for (int i = 0; i < N; i++){
		cin >> t[i];
	}
	for (int i = 1; i < N; i++){
		if (t[i] - t[i - 1] < T){
			ans += t[i] - t[i - 1];
		}
		else{
			ans += T;
		}
	}
	ans += T;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

std::string solve(const std::string& s)
{
  return s.back() == 's' ? s + "es" : s + "s";
}

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

  std::cout << std::setprecision(20);
  std::cout << solve(s) << std::endl;
}


Measured memory_bytes: 3624
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args)throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = new String(in.readLine());
		Integer n = Integer.parseInt(s);
		System.out.println(n*n*n);

	}

}



Measured memory_bytes: 24172
from collections import Counter
import math


def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n //=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n //=f
        else:f +=2
    if n!=1:a.append(n)
    return a


mod=10**9+7
n=int(input())
A=Counter(prime_factorize(math.factorial(n)))
cnt=1
for i in A.values():
    cnt *=i+1
    cnt %=mod
print(cnt)

Measured memory_bytes: 39952
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main()
{
    FASTINOUT;
    ll x;
    cin>>x;
    cout<<(x-1)*(x)/2<<endl;
    return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;

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

	ll m, n;
	cin >> m >> n;
	string a[m];
	ll dp[m][n];
	memset(dp, 0, sizeof dp);
	for(ll i=0; i<m; i++)
	{
		cin >>  a[i];
	}
	bool fuck = 0;
	for(ll i=0; i<m; i++)
	{
		if(a[i][0] == '.' and !fuck)
			dp[i][0] = 1;
		else
		{
			dp[i][0] = -1;
			fuck = 1;
		}
	}
	fuck = 0;
	for(ll i=1; i<n; i++)
	{
		if(a[0][i] == '.' and !fuck)
			dp[0][i] = 1;
		else
		{
			dp[0][i] = -1;
			fuck = 1;
		}
	}
	for(ll i=1; i<m; i++)
	{
		for(ll j=1; j<n; j++)
		{
			if(a[i][j] == '#')
			{
				dp[i][j] = -1;
				continue;
			}
			if(dp[i-1][j] > 0)
				dp[i][j] = (dp[i][j] + dp[i-1][j] + mod)%mod;
			if(dp[i][j-1] > 0)
				dp[i][j] = (dp[i][j] + dp[i][j-1] + mod)%mod;
		}
	}
	cout << dp[m-1][n-1] << "\n";

	return 0;
}

Measured memory_bytes: 9088
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int M = Integer.parseInt(in.next());
            int D = Integer.parseInt(in.next());
            int ans = 0;

            if (D <= 21 || M <= 3) {
                out.println(0);
                return;
            }
            for (int i = 4; i <= M; i++) {
                for (int j = 22; j <= D; j++) {
                    int d1 = j % 10;
                    int d10 = j / 10;
                    if (d1 >= 2 && d10 >= 2 && d1 * d10 == i) ans++;
                }
            }

            // 出力
            out.println(ans);

        }

    }
}



Measured memory_bytes: 24276
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	for (a=0; a<10000; a++ ){
		cin >> b;
		if ( b == 0 ) break;
		else {
		cout<< "Case " << a+1 << ": " << b << endl;} 
	}
	return 0;
}



Measured memory_bytes: 3004
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
	string s;
	cin >> s;
	if (s == "SUN") {
		cout << 7 << endl;
	}
	else {
		if (s == "MON") {
			cout << 6 << endl;
		}
		if (s == "TUE") {
			cout << 5 << endl;
		}
		if (s == "WED") {
			cout << 4 << endl;
		}
		if (s == "THU") {
			cout << 3 << endl;
		}
		if (s == "FRI") {
			cout << 2 << endl;
		}
		if (s == "SAT") {
			cout << 1 << endl;
		}	
	}
}

Measured memory_bytes: 256
def B():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    ans = 1
    limit = 10**18
    for a in A:
        ans *= a
        if ans > limit:
            print(-1)
            return
    print(ans)
B()

Measured memory_bytes: 21784
#include <iostream>
using namespace std;
int a[105],b[105];
int main()
{
    int n,sum=0;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>b[i];
    }
    
    a[0]=b[0];
    a[n-1]=b[n-2];
    for(int i=1;i<n-1;i++)
    {
        a[i]=min(b[i-1], b[i]);
    }

    for(int i=0;i<n;i++)
    {
        sum+=a[i];
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    from builtins import int, map, list, print
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = (lambda: (sys.stdin.readline()).rstrip())
    input_list = (lambda: input().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N = input()
    print('YNeos'[not '7' in N::2])

if __name__ == '__main__':
    main()


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

using namespace std;

#define INF 0x3f3f3f3f
#define endl "\n"
#define MAXN 200010
#define F first
#define S second
#define abs(a, b) ((a > b) ? a-b : b-a)
#define rep(i, a, b) for(int i = (a); i <= (b); i++)

typedef long long int ll;

ll a[MAXN];
ll ct[MAXN];
bool us[MAXN];

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

	int n, x; cin >> n;
 
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		ct[a[i]]++;
	}
	
	ll cc = 0;
	for (int i = 0; i < n; i++) {
		if (!us[a[i]]) {
			cc += (ct[a[i]])*(ct[a[i]]-1)/2;
			us[a[i]] = true;
		}
	}

	for (int i = 0; i < n; i++) {
		cout << cc - (ct[a[i]]-1)  << endl;
	}

	return 0;
}


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

int main()
{
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    bool inc = true;
    int ans =0;
    if( a[0] > a[1])
        inc = false;
    bool br = false;
    for(int i=0;i<n-1;i++)
    {
        if( a[i]== a[i+1])
            continue;
        if( br )
        {
            if( a[i] > a[i+1])
                inc = false;
            else inc = true;
            br = false;
        }
        if( a[i] > a[i+1] && inc == true )
        {
            ans ++;
            br = true;
        }
        if( a[i] < a[i+1] && inc == false)
        {
            ans++;
            br = true;
        }
    }
    cout<<ans+1;
}

Measured memory_bytes: 4412
#include <stdio.h>
#include <stdlib.h>
 
int inputdata(){
	int num;
	if (scanf("%d", &num) == 1);
  	else { 
  		printf("Failed to read integer.\n"); 
  	}
  	
  	return num;
}
 
int main(void){
  int a,p; 
  a = inputdata();
  p = inputdata();

  printf("%d\n", (p+a*3)/2);
 
}

Measured memory_bytes: 128
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

const int MAXN = 140111;

int N;
int P[MAXN], X[MAXN];
pair<int, int> C[MAXN];
vector<pair<LL, LL> > V[MAXN];

LL mid;

vector<pair<LL, LL> > line(int a, int b) {
    vector<pair<LL, LL> > ret;
    int j = 0;
    REP (i, V[a].size()) {
	LL a_cst = V[a][i].second + X[a];
	while (j+1 < (int)V[b].size() && a_cst + V[b][j+1].first + X[b] <= mid) j++;
	if (j < (int)V[b].size() && a_cst + V[b][j].first + X[b] <= mid) {
	    a_cst = V[a][i].first + X[a];
	    LL b_cst = V[b][j].second + X[b];

	    if (ret.empty() || ret.back().second > b_cst)
		ret.emplace_back(a_cst, b_cst);
	}
    }
    return ret;
}

bool ok() {
    for (int v=N; v--;) {
	if (C[v].first == -1) {
	    if (V[v].empty()) V[v].emplace_back(0, 0);
	} else {
	    V[v].clear();
	    int l = C[v].first, r = C[v].second;
	    vector<pair<LL, LL> > lv = line(l, r);
	    vector<pair<LL, LL> > rv = line(r, l);
	    int i = 0, j = 0;
	    while (i < (int)lv.size() || j < (int)rv.size()) {
		pair<LL, LL> key;
		if (j == (int)rv.size()) {
		    key = lv[i++];
		} else if (i == (int)lv.size()) {
		    key = rv[j++];
		} else if (lv[i].first < rv[j].first || (lv[i].first == rv[j].first && lv[i].second < rv[j].second)) {
		    key = lv[i++];
		} else {
		    key = rv[j++];
		}

		if (V[v].empty() ||
			(V[v].back().first < key.first && V[v].back().second > key.second)) {
		    V[v].push_back(key);
		}
	    }
	    if (V[v].empty()) return false;
	}
    }
    return true;
}

void MAIN() {
    scanf("%d", &N);
    REP (i, N) C[i].first = C[i].second = -1;
    REP (i, N-1) {
	int a, x;
	scanf("%d%d", &a, &x);
	a--;
	P[i+1] = a;
	X[i+1] = x;

	if (C[a].first == -1) C[a].first = i+1;
	else C[a].second = i+1;
    }

    LL lo = -1, hi = (1LL<<40)-1;
    while (hi - lo > 1) {
	mid = (lo + hi) / 2;
	(ok()? hi: lo) = mid;
    }
    printf("%lld\n", hi);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 29584
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>

using namespace std;

inline int getArea(int x1, int y1, int x2, int y2, int x3, int y3) {
    return abs((x1-x2)*(y3-y2)-(x3-x2)*(y1-y2));
}
inline int H(int x, int y) {
    return x + y * 10000;
}
inline int X(int v) {
    return v % 10000;
}
inline int Y(int v) {
    return v / 10000;
}

int main() {
    int n;
    while (cin >> n, n) {
        vector<int> co(n);
        int x, y;
        for (int i=0; i<n; ++i) {
            cin >> x >> y;
            co[i] = H(x, y);
        }
        sort(co.begin(), co.end());

        int area = 0;
        for (int i=0; i<(int)co.size(); ++i) {
            for (int j=i+1; j<(int)co.size(); ++j) {
                int dx, dy, x3, y3, x4, y4;
                dx = X(co[j]) - X(co[i]);
                dy = Y(co[j]) - Y(co[i]);
                x3 = X(co[j]) - dy;
                y3 = Y(co[j]) + dx;
                x4 = X(co[i]) - dy;
                y4 = Y(co[i]) + dx;
                if (binary_search(co.begin(), co.end(), H(x3, y3)) && binary_search(co.begin(), co.end(), H(x4, y4))) {
                    area = max(area, getArea(X(co[i]), Y(co[i]), X(co[j]), Y(co[j]), x3, y3));
                }
            }
        }
        cout << area << endl;
    }
    return 0;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
int n,i,a[100002];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=gcd(a[i],a[i-1]);
	printf("%d",a[n]);
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0) return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1;  // 分母
  ll numerator = 1;    // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

class UnionFind {
 private:
  vector<ll> parents;

 public:
  UnionFind(ll n) : parents(n, -1) {}

  bool issame(ll x, ll y) { return root(x) == root(y); }

  bool merge(ll x, ll y) {
    if (issame(x, y)) return false;

    ll rx = root(x);
    ll ry = root(y);
    if (parents[rx] > parents[ry]) swap(rx, ry);
    // サイズ情報を更新
    parents[rx] += parents[ry];
    // yの親を更新
    parents[ry] = rx;

    return true;
  }

  ll size(ll x) { return -parents[root(x)]; }

 private:
  ll root(ll x) {
    if (parents[x] < 0) return x;
    // 根の親の値に木の(-)サイズの情報を入れる
    return parents[x] = root(parents[x]);
  }
};

ll gcd(ll a, ll b) {
  if (a % b == 0) {
    return (b);
  } else {
    return (gcd(b, a % b));
  }
}

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

  return true;
}

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);

  ll N;
  cin >> N;
  vector<ll> T(N);
  vector<ll> A(N);

  for (ll i = 0; i < N; i++) {
    cin >> T[i];
    cin >> A[i];
  }

  ll x = 1;
  ll y = 1;

  for (ll i = 0; i < N; i++) {
    ll t = T[i];
    ll a = A[i];

    ll n = max((x + (t - 1)) / t, (y + (a - 1)) / a);
    x = n * t;
    y = n * a;
  }

  cout << x + y << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
        // 自分の得意な言語で
        // Let's チャレンジ！！

        Scanner sc = new Scanner(System.in);
        int a=sc.nextInt();
        System.out.println(a+(a*a)+(a*a*a));
    }
}

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

int main() {
	int ans1,ans2;
	ans1=0;ans2=0;
	double noudo,ansnoudo;
	ansnoudo=0;
	int a,b,c,d,e,f;
	int mizu1,mizu2,satou1,satou2;
	scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f);
	for(int i=0;i*100*a<=f;i++){
		mizu1=i*100*a;
		for(int j=0;mizu1+j*100*b<=f;j++){
			mizu2=j*100*b;
			for(int k=0;(k*c)<=e*(mizu1+mizu2)/100;k++){
				satou1=k*c;
				for(int l=0;satou1+l*d<=e*(mizu1+mizu2)/100;l++){
					satou2=l*d;
					if(mizu1+mizu2+satou1+satou2<=f){
						noudo = 100.0*(satou1+satou2)/(mizu1+mizu2+satou1+satou2);
						if(noudo>=ansnoudo){
							ansnoudo=noudo;
							ans1=mizu1+mizu2+satou1+satou2;
							ans2=satou1+satou2;
						}
					}
				}
			}
		}
	}
	printf("%d %d\n",ans1,ans2);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rrep(i,n) for(int i=(int)n-1;i>=0;--i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

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

    int a, b, c;
    cin >> a >> b >> c;
    int x;
    cin >> x;
    int ans = 0;
    for (int i = 0; i <= a; ++i) {
        for (int j = 0; j <= b; ++j) {
            for (int k = 0; k <= c; ++k) {
                int now = 500 * i + 100 * j + 50 * k;
                if (now == x) ans++;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3604
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define ARR(array) for(int i=0;i<array.size();i++)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K
#define INF 1e18
#define MOD 100000007
#define SIZE 10005
#define PI 	3.14159265358979323846

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    ll ans = 0;
    REP(i,s.size()-1){
        if(s[i]==s[i+1]){
            s[i+1]=((s[i+1]=='0')?'1':'0');
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
S = str(input())

words = ['dream', 'dreamer', 'erase', 'eraser']

S = S[::-1]
for i in range(len(words)):
    words[i] = words[i][::-1]

fin = True
com1 = False
cont = 0

for i in range(len(S)):
    if cont > 0:
        cont -= 1
        continue
    for j in range(len(words)):
        if words[j] == S[i:i+len(words[j])]:
            com1 = True
            cont = len(words[j]) - 1
            break
    if com1 == False:
        fin = False
        break
    com1 = False

if fin == True:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 3188
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll a, b, c, d, s;
string str;

int main(){
	cin >> s;
	
	a = 0;
	d = 0;
	b = 1;
	for(ll i = 1; i <= 1e9; i++){
		a++;
		if(0 <= a*d-s && a*d-s <= 1e9){
			c = a*d-s;
			break;
		}
		d++;
		if(0 <= a*d-s && a*d-s <= 1e9){
			c = a*d-s;
			break;
		}
	}
	
	cout << 0 << " " << 0 << " " << a << " " << b << " " << c << " " << d << endl; 
	return 0;
}

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

int sum(int i,int j){
  if(i + j >= 1000000007){return i+j-1000000007;}
  return i+j;
}


int A[100001][13];
int main(){
  int len,res = 1;
  char s[100000];
  scanf("%s",s);
  len = strlen(s);
  A[0][0] = 1;
  for(int i = 0;i < len;i++){
    if(s[len-i-1] == '?'){
      for(int j = 0;j < 10;j++){
        for(int k = 0;k < 13;k++){
        	A[i+1][(j*res+k)%13] = sum(A[i+1][(j*res+k)%13],A[i][k]);
        }
      }
    }
    else{
      int j = s[len-i-1]-'0';
      for(int k = 0;k < 13;k++){
        A[i+1][(j*res+k)%13] = A[i][k];
      }
    }
    res = (res * 10)%13;
  }
  printf("%d\n",A[len][5]);
  return 0;
}

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

using namespace std;

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

int main(){
    int n, m;
    cin >> n >> m;
    ll a[100005];
    for(int i = 0; i < n; i++)cin >> a[i];
    sort(a, a+n);
    ll bc[100005][2];
    for(int i = 0; i < m; i++)cin >> bc[i][1] >> bc[i][0];
    using item = pair<ll,ll>;
    sort((item*)bc[0], (item*)bc[m], []( item x, item y ) { return x.first < y.first; });
    int d = m-1;
    for(int i = 0; i < n; i++){
        if(d < 0){
            break;
        }
        if(bc[d][0] > a[i]){
            if(bc[d][1]){
                a[i] = bc[d][0];
                bc[d][1]--;
            }
            if(bc[d][1] == 0)d--;
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i++)ans += a[i];
    cout << ans << endl;
    return 0;
}

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

using namespace std;

void uru(int c, int d) {
	int counter = 0;

	for (int i = c; i <= d; i++) {
		if (i % 4 == 0) {
			if (i % 100 == 0) {
				if (i % 400 == 0) {
					cout << i << endl;
					counter++;
				} 
			} else {
				cout << i << endl;
				counter++;
			}
		}
	}
	if (counter == 0) {
		cout << "NA" << endl;
	}
	return;
}

int main() {
	int a,b;
	int cou = 0;

	while (1) {
		scanf("%d%d", &a, &b);
		if (a == 0 && b == 0) {
			break;
		} else {
			if (cou != 0) {
				cout << endl;
			}
			uru(a,b);
			cou = 1;
		}
	}
	return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#define INF 9223372036854775807LL

ll C(ll x, const vector<ll>& v){
  rep(i,v.size()){
    x = x - x%v[i];
  }
  return x;
}


int main(){
  int K;
  cin >> K;
  vector<ll> v;
  rep(i,K){
    ll a;
    cin >> a;
    v.push_back(a);
  }
  ll mn = -1, mx = -1;
  {
    ll lb = 0, ub = INF;
    while(ub-lb>1){
      ll m = lb + (ub-lb)/2;
      if(C(m, v)<2) lb = m;
      else ub = m;
    }
    if(C(lb+1, v) == 2) mn = lb+1;
  }
  {
    ll lb = 0, ub = INF;
    while(ub-lb>1){
      ll m = lb + (ub-lb)/2;
      if(C(m, v)<=2) lb = m;
      else ub = m;
    }
    if(C(lb, v) == 2) mx = lb;
  }

  if(mn == -1) cout << -1 << endl;
  else cout << mn << " " << mx << endl;
  
  return 0;
}



Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;

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

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int i,j;
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	ll ans=0;
	if(a>=k) {
		cout<<k<<endl;
		return 0;
	}
	ans+=a;
	k-=a;
	if(b>=k) {
		cout<<ans<<endl;
		return 0;
	}
	k-=b;
	cout<<ans-k<<endl;
	return 0;

}

Measured memory_bytes: 3592
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};


ll g[16][16];
ll sum[1 << 15];
ll dp[1 << 15][16];

void solve(ll N, ll M, vector<ll> a, vector<ll> b, vector<ll> c) {
  REP(i,N) REP(j,N) g[i][j] = int(-1e9);
  REP(i,N) g[i][i] = 0;
  REP(i,M) g[a[i] - 1][b[i] - 1] = c[i];
  REP(i,M) g[b[i] - 1][a[i] - 1] = c[i];

  REP(bit,1<<N) REP(i,N) REP(j,i) {
    if ((bit >> i) & (bit >> j) & 1)
      if (g[i][j] != int(-1e9)) sum[bit] += g[i][j];
  }

  REP(bit,1<<N) REP(i,N) dp[bit][i] = -1e9;
  REP(bit,1<<N) if (bit & 1) dp[bit][0] = sum[bit];
  REP(bit,1<<N) REP(i,N) REP(j,N) {
    if ((bit >> j) & 1) continue;
    int rest = (1 << N) - 1 - bit - (1 << j);
    for (int bit2 = rest;; bit2 = (((bit2) - 1) & rest)) {
      chmax(dp[bit | (bit2 + (1 << j))][j], dp[bit][i] + sum[bit2 + (1 << j)] + g[i][j]);
      if (bit2 == 0) break;
    }
  }
  cout << accumulate(ALL(c), 0LL) - dp[(1 << N) - 1][N-1] << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll N;
	ll M;
	scanf("%lld", &N);
	scanf("%lld", &M);
	vector<ll> c(M-1+1);
	vector<ll> b(M-1+1);
	vector<ll> a(M-1+1);
	for (int i = 0 ; i <= M-1 ; i++) {
	  scanf("%lld", &a[i]);
	  scanf("%lld", &b[i]);
	  scanf("%lld", &c[i]);
	}
	solve(N, M, a, b, c);
	return 0;
}


Measured memory_bytes: 4608
#include <iostream>
using namespace std;
 
int main() {
	int S[4];
	int x;
	cin>>x;
	for(int i=3;i>=0;i--)
	{ 
		S[i]=x%10;
		x=int(x/10);
		
	}
	int a=10*S[0]+S[1];
	int b=10*S[2]+S[3];
	if(((12<a && a<99)||a==0) && 0<b && b<=12)
	cout<<"YYMM";
	else if(0<a && a<=12 && ((12<b && b<=99)||b==0))
	cout<<"MMYY";
	else if(0<a && a<=12 && 0<b && b<=12)
	cout<<"AMBIGUOUS";
	else
	cout<<"NA";
	
	return 0;
}


Measured memory_bytes: 888
str = int(input())

if ((int) (str / 1000) == (int) (str % 1000 / 100)) or ((int) (str % 1000 / 100) == (int) (str % 100 / 10)) or ((int) (str % 100 / 10) == (int) (str % 10)):
  print("Bad")
else:
  print("Good")
  

Measured memory_bytes: 2940
import math

A,B,H,M=map(int,input().split())

deg=abs(2*math.pi*(H/12+M/12/60)-(2*math.pi*M/60))

deg=deg if deg<=math.pi else (2*math.pi-deg)

l=math.sqrt(A**2+B**2-2*A*B*math.cos(deg))

if deg==0:
    print(abs(A-B))
elif deg==math.pi:
    print(abs(A+B))
else:
    print(l)

Measured memory_bytes: 9528
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll int a,b,c,d,ans;
	cin>>a>>b>>c>>d;
	{
		ans=max(max(a*c,a*d),max(b*c,b*d));
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3648
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define all(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
const int MAX = (int)2e5 + 5;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(all(a));
	ll res = 1;
	int now;
	int start;
	if (n % 2 == 0) {
		now = 1;
		start = 2;
		if (a[0] == now && a[1] == now) res *= 2;
		else res *= 0;
	}
	else {
		now = 0;
		start = 1;
		if (a[0] == now);
		else res *= 0;
	}
	for (int i = start; i < n; i += 2) {
		now += 2;
		res = res * 2 % mod;
		if (a[i] == now && a[i + 1] == now);
		else res *= 0;
	}
	cout << res << endl;
}

signed main() {
	cout << fixed << setprecision(20);
	rep(i, 1) solve();
	return 0;
}

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

typedef struct{
  int root,child,sibling;
}Node;

int getParent(Node *T,int id){
  return T[id].root;
}

int getDepth(Node *T,int id){
  int i=id,count=0;
  while(T[i].root!=-1){
    i=T[i].root;
    count++;
  }
  return count;
}

int getType(Node *T,int id){
  if (T[id].root==-1)return 0;
  if (T[id].child==-1)return 2;
  return 1;
}

int getChild(Node *T,int id,int *childs){
  int i=0;
  int child=T[id].child;
  if (child==-1)return 0;
  childs[i++]=child;
  while (T[child].sibling!=-1){
    child=T[child].sibling;
    childs[i++]=child;
  }
  return i;
}

int main(){
  Node T[100000];
  int chl[100000];
  int n,id,cn,cid,pcid;
  char *types[]={(char*)"root",(char*)"internal node",(char*)"leaf"};

  for (int i=0;i<100000;i++){
    T[i].root=-1;
    T[i].child=-1;
    T[i].sibling=-1;
  }
  cin >> n;
  for (int i=0;i<n;i++){
    cin >> id >> cn;
    pcid=-1;
    for (int j=0;j<cn;j++){
      cin >> cid;
      if (T[id].child==-1) T[id].child=cid;
      T[cid].root=id;
      if (pcid!=-1)T[pcid].sibling=cid;
      pcid=cid;
    }
  }
  for (int i=0;i<n;i++){
    //    printf("node 0: parent = -1, depth = 0, root, [1, 4, 10]");
    cout <<"node "<< i << ": ";
    cout <<"parent = "<<getParent(T,i)<<", ";
    cout <<"depth = "<<getDepth(T,i)<<", ";
    cout <<types[getType(T,i)] <<", [";
    cn=getChild(T,i,chl);
    for(int j=0;j<cn;j++){
      cout <<chl[j];
      if (j<cn-1)cout <<", ";
    }
    cout <<"]" << endl;
  }

  return 0;
}

Measured memory_bytes: 4616
using System;
class Program
 {
        static void Main(string[] args)
        {
    　　    int N = int.Parse(Console.ReadLine()); //標準入力
            string[] inputStr = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
            int[] input = new int[N];
            for(int i = 0; i < N; i++){
                input[i] = int.Parse(inputStr[i]);
            }
            int APoint = 0;
            int BPoint = 0;
            bool takeFlag = true;
            for(int i = 0; i < N; i++){
                int max = 0;
                int maxNum = -1;
                for(int j = 0; j < N; j++){
                    if(input[j] > max){
                        max = input[j];
                        maxNum = j;
                    }
                }
                input[maxNum] = 0;
                if(takeFlag){
                    APoint += max;
                    takeFlag = false;
                } else {
                    BPoint += max;
                    takeFlag = true;
                }
            }
            // Console.Write("改行なし a = {0} b = {1} c = {2}", a, b, c)//改行なし出力
            // Console.WriteLine("改行あり a = {0} b = {1} c = {2}", a, b, c);//改行付き出力
            Console.WriteLine((APoint - BPoint).ToString());
        }
 }

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

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

    int sum = 0;
    for (int i = 0; i < m; i++){
        int tmp;
        cin >> tmp;
        sum += tmp;
    }

    cout << (n < sum ? -1 : n - sum) << endl;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
using edge = pair<int, ll>;
using Graph = vector<vector<int>>; 
using WeightedGraph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main(){
  int a,b; cin >> a >> b;
  if(a==1) a= 14;
  if(b==1) b= 14;
  string ans = "Draw";
  if(a>b)ans = "Alice";
  if(b>a)ans = "Bob";
  cout << ans << endl;
}


Measured memory_bytes: 256
#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;
        
#define print(a) {for(auto xxxxx : (a)) cout << xxxxx << ' '; cout << '\n';}
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
        
ll next(){ll x; cin >> x; return x;}
const int maxn = 1e3 + 5, intf = 2e9;
const ll inf = 1e18, mod = 998244353;
const ld eps = 1e-6;

void solve(){
	string s , t; cin >> s >> t;
	if (s.size() + 1 == t.size()){
		t.pop_back();
		if (s == t){
			cout << "Yes\n";
			return;
		}
	}
	cout << "No\n";
}
    
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
            
    for (int t = 1; t--;) {
        solve();
    }
        
    return 0;
}
/*
        
        
*/

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

LL N;
LL a[55];
LL K;

int main(){
	scanf("%lld" , &N);
	repp(i,0,N){
		scanf("%lld" , a + i);
		K += a[i];
	}
	repm(i,N*(N-1),-1){
		LL z = K-i;
		if(z < 0) continue;
		LL b = 0;
		LL c = 0;
		repp(j,0,N){
			LL p = (a[j]+z)/(N+1);
			LL q = a[j]+z-(N+1)*p;
			if(q == N) b = -1234567;
			b += q;
			c += p;
		}
		if(b == i && c == z){
			printf("%lld\n" , z);
			break;
		}
	}
	return 0;
}


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

using namespace std;

string S;
int main() {
	int ret = 700;
	cin >> S;

	for (int i = 0; i < 3; i++) {
		if (S[i] == 'o') ret += 100;
	}

	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int n, i, a[45];
	scanf("%d", &n);
	for (i = 0; i <= n; i++)
	{
		a[i] = 0;
		if (i == 0 || i == 1)
		{
			a[i] = 1;
		}
	}
	if (n >= 2)
	{
		for (i = 2; i <= n; i++)
		{
			a[i] = a[i - 1] + a[i - 2];
			if (i == n)
			{
				printf("%d\n", a[i]);
			}
		}
	}
	else
	{
		printf("1\n");
	}
	return 0;
}

Measured memory_bytes: 1844
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  map<char,int>s;
  int num=10;
  char mo[]={"ABCDEF"};
  for(int i=0;i<6;i++){
    s[mo[i]]=num;
    num++;
  }
  char a[2],b[2];
  cin >> a[0] >> b[0];
  if(s[a[0]]>s[b[0]]){
    cout << '>' << endl;
  }else if(s[a[0]]<s[b[0]]){
    cout << '<' <<endl;
  }else{
    cout << '=' << endl;
  }
  return 0;
}
 

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()

    // 全探索で完了

    var cnt = 0

    for ( i in 1..n) {
        val len = i.toString().length
        if( len == 1 || len == 3 || len == 5) {
            cnt+=1
        }
    }

    println(cnt)
}

Measured memory_bytes: 38308
#https://atcoder.jp/contests/abc126/tasks/abc126_c
import math
N,K = map(int,input().split())
Current_Per = 0
for i in range(1,N+1):
    if i >= K:
        Current_Per += (1/N)
    else:
        Current_Per += ((0.5)**math.ceil(math.log((K/i),2)))*(1/N)

    
print(Current_Per)

Measured memory_bytes: 9356
package main

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

func main() {
	n := getInt()
	xs := getIntSlice(n)

	a, b := func() (int, int) {
		tmp := make([]int, n)
		copy(tmp, xs)
		sort.Ints(tmp)
		return tmp[n/2-1], tmp[n/2]
	}()

	for _, x := range xs {
		if x <= a {
			fmt.Println(b)
		} else {
			fmt.Println(a)
		}
	}
}

// -----------------------------------------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
}

func getInt() int {
	i, err := strconv.Atoi(getString())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 8192