akhauriyash/Code-Regression huggingface dataset:
import java.io.ByteArrayInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

	static boolean honban = true;

    public static void main(String[] args) throws Exception {
    	if (honban) {
            Scanner sc = new Scanner(System.in);
            mainInternal(sc);

    	} else {
    		String[] testInputs = {
    				"contest\r\n" +
    				"son",

    				"contest\r\n" +
    				"programming",

    				"contest\r\n" +
    				"sentence"
    		};

    		for (String testInput : testInputs) {
    			Scanner sc = new Scanner(new ByteArrayInputStream(testInput.getBytes()));
    			mainInternal(sc);
    		}
    	}
    }

    public static void mainInternal(Scanner sc) {

    	char[] argS = sc.next().toCharArray();
    	char[] argT = sc.next().toCharArray();

    	// argSの各文字が、配列のどの位置に出てくるかを保存しておく
    	Map<Character, TreeSet<Integer>> charIndexMap = new HashMap<Character, TreeSet<Integer>>();

    	for (int i = 0; i < argS.length; i++) {
    		char c = argS[i];
    		TreeSet<Integer> t = charIndexMap.get(c);

    		if (t == null) {
    			t = new TreeSet<Integer>();
    			charIndexMap.put(c, t);
    		}

    		t.add(i);
    	}

    	// 文字列連結したS'全体において、どのインデックスにいるか
    	long fullGlobalIndex = 1;

    	// 直前のS内のインデックス（S'じゃなくて、S）
    	int prevLocalIndex = -1;

    	for (char c : argT) {

    		// 文字がどの位置に出てくるか？（同じ文字でも複数の個所に出てくる可能性がある）
    		TreeSet<Integer> charIndex = charIndexMap.get(c);

    		if (charIndex == null) {
    			System.out.println("-1");
    			return;
    		}

    		Integer nextLocalIndex = charIndex.higher(prevLocalIndex);

    		if (nextLocalIndex == null) {
    			nextLocalIndex = charIndex.first();

    			fullGlobalIndex += argS.length - prevLocalIndex + nextLocalIndex;
    			prevLocalIndex = nextLocalIndex;

    		} else {
    			if (prevLocalIndex < 0) {
    				prevLocalIndex = 0;
    			}
    			fullGlobalIndex += nextLocalIndex - prevLocalIndex;
    			prevLocalIndex = nextLocalIndex;
    		}
    	}

    	System.out.println(fullGlobalIndex);
    }
}

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

#define MorsheD ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
	// ===================
	MorsheD;
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ===================

	int n;
	cin >> n;

	ll ara[n], pre[n] = {};
	for (int i = 0; i < n; ++i) {
		cin >> ara[i];

		if (i) {
			pre[i] = ara[i] + pre[i - 1];
		} else {
			pre[i] = ara[i];
		}
	}

	ll sum = 0;
	for (int i = 0; i < n - 1; ++i) {
		sum += (((pre[n - 1] - pre[i]) % MOD) * (ara[i] % MOD)) % MOD;
		sum %= MOD;
	}

	cout << sum % MOD << '\n';

	return 0;
}

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

const int mod = 1e9 + 7;
ll dp[100005][2];
vector<int> e[100005];

void dfs(int v, int pre) {
  dp[v][0] = dp[v][1] = 1;
  for (int u : e[v]) {
    if (u == pre) continue;
    dfs(u, v);
    dp[v][0] = (dp[v][0] * dp[u][1]) % mod;
    dp[v][1] = (dp[v][1] * (dp[u][0] + dp[u][1])) % mod;
  }
}

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

  int n;
  cin >> n;
  for (int i =1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1, 0);
  cout << (dp[1][0] + dp[1][1]) % mod << '\n';

  return 0;
}

Measured memory_bytes: 14208
#include <stdio.h>
int main(){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    int e,f;
    e = c/b;
    f = a/d;
    if(c%b != 0){
        e=e+1;
    }
    if(a%d != 0){
        f=f+1;
    }
    if(f<e){
        printf("No");
    }else{
        printf("Yes");
    }

    return 0;
}


Measured memory_bytes: 1728
#include <iostream>
#include <array>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <climits>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using namespace std;

const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res /= a;
	}
};

struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
} comb(2000005);

mint g(int r, int c) {
	return comb(r + c + 2, r + 1) - 1;
}

bool comp(int i, int j) {
	return i > j;
}

int main()
{
	int a;
	cin >> a;
	string s;
	cin >> s;
	cout << ((a >= 3200) ? s : "red");
}


Measured memory_bytes: 31488
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    string t;
    cin >> s >> t;

    int res = 0;
    for (int i = 0; i < s.length(); ++i) {
        res += s[i] == t[i];
    }
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <unordered_map>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;
using LL = long long;

int main() {
	int h, w;
	cin >> h >> w;
	int n;
	cin >> n;
	vector<int> map;
	int a;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		for (int j = 0; j < a; j++) {
			map.emplace_back(i);
		}
	}
	int count = 0;
	for (int i = 0; i < h; i++) {
		if (i % 2 == 0) {
			for (int i = 0; i < w; i++) {
				cout << map[count];
				if (i != w - 1) {
					cout << " ";
					count++;
				}
			}
			cout << endl;
		}
		else {
			for (int i = 0; i < w; i++) {
				cout << map[count];
				if (i != w - 1) {
					cout << " ";
					count--;
				}
			}
			cout << endl;
		}
		count += w;
	}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define int long long
#define double long double
const int INF = 1e18, MOD = 1e9 + 7;

signed main() {
    deque<char> s;
    char c;
    while (cin>>c) {
        s.push_back(c);
    }
    int ans = 0;
    while (s.size() > 1) {
        if (s[0] == s[s.size() - 1]) {
            s.pop_back();
            s.pop_front();
        } else if (s[0] == 'x') {
            s.pop_front();
            ans++;
        } else if (s[s.size() - 1] == 'x') {
            s.pop_back();
            ans++;
        } else {
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
value = list(map(int,input().split()))
l = int(input())
l *= 100
rittoru = [25, 50, 100, 200]
m = value[0] * 2
total = 0

for i in range(1, 4):
    if m < value[i]:
        value[i] = m
        m *= 2
    else :
        m = value[i] * 2

for i in range(4)[::-1]:
    hon = l // rittoru[i]
    l %= rittoru[i]
    total += hon * value[i]

print (total)



Measured memory_bytes: 3064
#include <iostream>
#include<string>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef pair<double,double>P_D;
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define reprev(i, n) for (int i = (int)n - 1; i >= 0; i--)
#define ALL(a)  (a).begin(),(a).end()
#define MAX 100100
#define MAX_N 200100
#define SENTINEL 2000000000
#define MAX_B 1001001
#define NIL -1
#define MOD 1000000007
#define INF 1 << 29
#define INFTY 1000000000000000000LL

int main(){
    string s;
    cin>>s;
    int n=s.size();
    ll sum=0;
    for(int bit=0;bit<(1<<(n-1));bit++){
        ll t=s[0]-'0';
        for(int i=0;i<n-1;i++){
            if(bit & (1<<i)){
                sum+=t;
                t=s[i+1]-'0';
            }
            else{
                t*=10;
                t+=s[i+1]-'0';
            }
        }
        sum+=t;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  vl s(n);
  rep(i, n) cin >> s[i];
  ll sum = accumulate(all(s), 0LL);
  sort(all(s));
  rep(i, n) {
    if(sum % 10 > 0) break;
    if(s[i] % 10 > 0) sum -= s[i];
  }
  cout << (sum % 10 > 0 ? sum : 0) << endl;
}

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

using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;

#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define BIGINT 0x7FFFFFFF
#define E107 1000000007

#define TIME chrono::system_clock::now
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())

template<typename T1,typename T2>
ostream& operator <<(ostream &o,const pair<T1,T2> p){o<<"("<<p.first<<":"<<p.second<<")";return o;}

int m,n;

int data[101];

int main(){
    int i,j,k;
    
    cin>>n;
    
    for (i=0;i<n;i++){
        scanf("%d",data+i);
    }
    int t,cost=BIGINT,c;
    for (t=-100;t<=100;t++){
        c=0;
        for (i=0;i<n;i++){
            c+=(data[i]-t)*(data[i]-t);
        }
        cost=min(cost,c);
    }
    
    cout<<cost<<endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [0]*N
for i in range(N):
  A[i] = int(input())

A_sorted = sorted(A, reverse=True)
max1 = A_sorted[0]
max2 = A_sorted[1]

if max1 == max2:
  for _ in range(N):
    print(max1)
else:
  for i in range(N):
    if A[i] == max1:
      print(max2)
    else:
      print(max1)


Measured memory_bytes: 14076
import numpy as np

data = input().split(" ")
num = int(data[0])
D = int(data[1])

dist = [0]*num
for i in range(num):
  cord = input().split(" ")
  a = int(cord[0])
  b = int(cord[1])
  x = np.sqrt(a*a + b*b)
  if x <= D:
    dist[i] = int(1)
  else:
    dist[i] = int(0)
  
print(sum(dist))

Measured memory_bytes: 28132
#include <iostream>
#include <vector>

const int MAX_N = 1000000;
const int MOD = 1000000007;

int c[MAX_N];
inline void mul_mod(int& x, int y) { x = (long long)x * y % MOD; }

int main() {
  int n, a, res = 1;
  std::cin >> n;
  c[0] = 3;
  for (int i = 0; i < n; ++i) {
    std::cin >> a;
    mul_mod(res, c[a] - c[a + 1]);
    c[a + 1]++;
  }
  std::cout << res << std::endl;

  return 0;
}


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

int main(){
    int n,k;
    cin >> n >> k;
    vector <int> h(n);
    int ans;
    ans=0;
    rep(i,n){
        cin >> h[i];
        if(h[i]>=k){
            ++ans;
        }
    }

    cout << ans << endl;
    

    return 0;
}

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


using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 998244353;





int n;


VS v;

void f(string s, int i,bool b) {

	//cout << s << ' ' << i << endl;
	if (s.size() == n) {
		v.push_back(s);
		return;
	}
	
	if (b&&i == 1) {
		f(s + 'a', 1, true);
		if(s.size()!=0)	f(s + 'b', 2, false);
	}
	else {
		FOR(j, 1, i + 2) {
			string t = s;
			t += 'a' + j - 1;
			f(t, max(i, j), false);
		}
	}
}



int main() {

	
	cin >> n;
	
	f("", 1, true);


	sort(ALL(v));
	REP(i, v.size()) {
		cout << v[i] << endl;
	}


}




Measured memory_bytes: 7796
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if((abs(b-a)<=d && abs(c-b)<=d)||abs(c-a)<=d) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <math.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int iINF = 100100100;
const ll llINF = 1LL << 60;
string s = "";
int Size;
ll chmin(ll a, ll b)
{
	return a > b ? b : a;
}
ll getComb(int a, int b)
{
	cout << "(" << a << "," << b << ") = ";
	ll ret = 1;
	rep(i, b) {
		ret *= a - i;
	}
	rep(i, b) {
		ret /= b - i;
	}
	return ret;
}
int main()
{
	ll n;
	cin >> n;
	vector<ll> v(n), v_mod(n);
	rep(i, n)	cin >> v[i];
	sort(v.begin(), v.end());
	ll m = v.back();
	ll half = m / 2;
	ll ans = 0;
	rep(i, n - 1) {
		if (half < v[i])	v_mod[i] = m - v[i];
		else v_mod[i] = v[i];
		ans = max(ans, v_mod[i]);
	}
	rep(i, n - 1) {
		if (ans == v[i])	break;
		if (m - ans == v[i]) {
			ans = m - ans;
			break;
		}
	}
	cout << m << " " << ans << endl;
	return 0;
}


Measured memory_bytes: 4848
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define ll long long
#define M 100000007
#define fr first
#define sc second
#define endl "\n"
#define vc vector
#define pb push_back
#define pii pair<ll, ll>
#define psi pair<string, ll>
#define fast                                                                   \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(0);                                                                  \
  cout.tie(0);
#define PI 3.14159265
#define r0 return 0
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define tr(c, i) for (typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c), x) != (c).end())
#define what_is(x) cerr << #x << " is " << x << endl;
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
const char char_max = (char)(((unsigned char) char(-1)) / 2);

int main() {
  fast
  string a,b,c;
  ll x,y;
  cin>>a>>b>>x>>y>>c;
  if(c==a && x>0) x--;
  if(c==b  && y>0) y--;
  cout<<x<<" "<<y<<endl;
}



Measured memory_bytes: 256
import bisect
from itertools import accumulate
from operator import add

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort()
b.sort()
c.sort()

AonB=[]
BonC=[]
ans=0
for i in range(n):
    AonB.append(bisect.bisect_left(a,b[i]))

AonB=list(accumulate(AonB,add))

ans=0
for g in range(n):
    search=bisect.bisect_left(b,c[g])-1
    if search>=0:
        ans+=AonB[search]

print(ans)

Measured memory_bytes: 24060
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
using namespace std;
int main() {
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(min(a+b,a+c),b+c)<<endl;
}   




Measured memory_bytes: 256
# coding: UTF-8
import numpy as np

MOD = int(1e+9+7)
H, W, A, B = map(int, input().split())

fact = [1]
for i in range(1, W+H-1):
    fact.append((fact[-1]*i) % MOD)

ifact = [pow(fact[-1], MOD-2, MOD)]
for i in reversed(range(1, W+H-1)):
    ifact.append((ifact[-1]*i) % MOD)
ifact.reverse()


def comb(n, r):
    return fact[n]*ifact[n-r]*ifact[r]


r = H-A-1
s = 0
for c in range(B, W):
    s += comb(c+r, r) * comb(W-c+A-2, A-1)
    s %= MOD

print(int(s))


Measured memory_bytes: 28136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<ll>>;
using P = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef vector<ll> vi;
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
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; }

int main(){
  ll n, l;
  cin >> n >> l;
  ll ans = 0;
  for(ll i=1;i<=n;i++){
    ans += i + l - 1;
  }
  if(l>=0){
    ans -= l;
  }
  else if(n+l-1>0){
  }
  else{
    ans -= n + l - 1;
  }
  print(ans);
}

Measured memory_bytes: 256
// 1からスタンプを押していくBFS
// golangでpriority queueもってないから愚直FIFOで間に合うかどうかは正直わからん
// ちょっとだけIOを高速化したバージョン
package main

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

type Pos struct {
	cur, pre int
}

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()
	N, M := nextInt(), nextInt()

	T := make([][]int, N+1)
	for i := 1; i <= N; i++ {
		T[i] = []int{}
	}
	for i := 0; i < M; i++ {
		A, B := nextInt(), nextInt()
		T[A] = append(T[A], B)
		T[B] = append(T[B], A)
	}
	passed := make([]int, N+1)
	passed[1] = -1
	queue := []Pos{Pos{cur: 1, pre: 0}}
	for len(queue) > 0 {
		nex_queue := []Pos{}
		for i := 0; i < len(queue); i++ {
			now := queue[i]
			for _, nex := range T[now.cur] {
				if passed[nex] == 0 {
					nexPos := Pos{cur: nex, pre: now.cur}
					passed[nex] = now.cur
					nex_queue = append(nex_queue, nexPos)
				}
			}
		}
		queue = nex_queue
	}
	fmt.Fprintln(out, "Yes")
	for _, ans := range passed[2:] {
		fmt.Fprintln(out, ans)
	}

}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}


Measured memory_bytes: 24092
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    N = inputs[0]
    K = inputs[1]

    current = 1
    for i in range(N):
        if current < K:
            current += current
        else:
            current += K
    return current


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(int_inputs(2))
    print(ret)


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 510000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

int main() {
  int N;
  cin >> N;
  vector<int> x(N), y(N), h(N);
  for (int i=0; i<N; i++) cin >> x[i] >> y[i] >> h[i];
  bool exist = false; // 高さが0でないものが存在するか
  for (int i=0; i<N; i++) {
    if (h[i]!=0) {
      exist = true;
      break;
    }
  }
  if (exist) {
    // 中心座標を全探索
    for (int Cx=0; Cx<=100; Cx++) {
      for (int Cy=0; Cy<=100; Cy++) {
        int H = 0;
        for (int i=0; i<N; i++) {
          if (h[i]!=0) {
            H = abs(x[i]-Cx)+abs(y[i]-Cy)+h[i];
            break;
          }
        }
        bool pos = true;
        for (int i=0; i<N; i++) {
          if (max(H-abs(x[i]-Cx)-abs(y[i]-Cy), 0)!=h[i]) {
            pos = false;
            break;
          }
        }
        if (pos) {
          cout << Cx << " " << Cy << " " << H << endl;
          return 0;
        }
      }
    }
  }
  else {
    int H = 1;
    for (int Cx=0; Cx<=100; Cx++) {
      for (int Cy=0; Cy<=100; Cy++) {
        bool pos = true;
        for (int i=0; i<N; i++) {
          if (max(H-abs(x[i]-Cx)-abs(y[i]-Cy), 0)!=h[i]) {
            pos = false;
            break;
          }
        }
        if (pos) {
          cout << Cx << " " << Cy << " " << H << endl;
          return 0;
        }
      }
    }
  }
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<vector>
#include<climits>
#define ll long long int
using namespace std;
int main(void) {
  int a, b;
  cin>>a>>b;
  if(a<=b) cout<<a<<endl;
  else cout<<a-1<<endl;
  return 0;
}


Measured memory_bytes: 256
s = gets.strip.split('')
t = gets.strip.split('')

(s.length - t.length).downto(0) do |i|
  cs = s.dup
  cs[i..i+t.length-1] = t
  if s.zip(cs).all? {|l, r| l==?? || l==r  }
    puts cs.join('').gsub(??, ?a); exit
  end
end

puts 'UNRESTORABLE'

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define int       long long
#define nn        100005
 
struct act{
    int a,b,c;
};
act obj[nn];
int n;
 
int solve(){
    int dp[n+1][3] = {0};
    dp[1][0] = obj[1].a;
    dp[1][1] = obj[1].b;
    dp[1][2] = obj[1].c;
 
    for(int i=2;i<=n;i++){
        dp[i][0] = obj[i].a + max(dp[i-1][1],dp[i-1][2]);
        dp[i][1] = obj[i].b + max(dp[i-1][0],dp[i-1][2]);
        dp[i][2] = obj[i].c + max(dp[i-1][0],dp[i-1][1]);
    }
 
    return max(dp[n][0], max(dp[n][1], dp[n][2]));
}
 
int32_t main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>obj[i].a>>obj[i].b>>obj[i].c;
    }
    cout<<solve();
}

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

typedef struct{
  int x;
  int y;
  int z;
}Node;

void Pr(int);
void Ir(int);
void Or(int);

Node *node;

int main(void){

  int i,n,s,t;

  scanf("%d",&n);

  node=(Node*)malloc(n*sizeof(Node));

  for(i=0;i<=n-1;i++){
    node[i].x=-1;
    node[i].y=-1;
    node[i].z=-1;
  }
  for(i=0;i<=n-1;i++){
    scanf("%d",&s);
    scanf("%d",&node[s].y);
    if(node[s].y!=-1)
      node[node[s].y].x=s;
    scanf("%d",&node[s].z);
     if(node[s].z!=-1)
      node[node[s].z].x=s;
  }
  for(i=0;i<=n-1;i++){
    if(node[i].x==-1)
      t=i;
  }
  printf("Preorder\n");
  Pr(t);
  printf("\n");
  
  printf("Inorder\n");
  Ir(t);
  printf("\n");
  
  printf("Postorder\n");
  Or(t);
  printf("\n");
  
  free(node);

  return 0;
}


void Pr(int s){
  printf(" %d",s);
  if(node[s].y!=-1)
    Pr(node[s].y);
  if(node[s].z!=-1)
    Pr(node[s].z);
}

void Ir(int s){
  if(node[s].y!=-1)
    Ir(node[s].y);
  printf(" %d",s);
  if(node[s].z!=-1)
    Ir(node[s].z);
}

void Or(int s){
  if(node[s].y!=-1)
    Or(node[s].y);
  if(node[s].z!=-1)
    Or(node[s].z);
   printf(" %d",s);
}



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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair

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

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

int main(){
    int n;
    while(cin >> n, n){
        vi v(n);
        int sum = 0, ans = inf;
        rep(i, n){ cin >> v[i]; sum += v[i]; }
        rep(i, 1<<n){
            int suma = 0, sumb = 0;
            rep(j, n){
                if((i>>j)%2) suma += v[j];
                else sumb += v[j];
            }
            ans = min(ans, abs(suma-sumb));
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1192
#include <iostream>
#include <string>
#include <string.h>

using namespace std;
int table[90000];

void solve()
{
	int n;
	while(cin >> n, n)
	{
		memset(table, 0, sizeof(table));
		while(n--)
		{
			string str1, str2;
			cin >> str1 >> str2;
			int start, end;
			start = (str1[0] - '0') * 36000 + (str1[1] - '0') * 3600 + (str1[3] - '0') * 600 + (str1[4] - '0') * 60 + (str1[6] - '0') * 10 + (str1[7] - '0');
			end = (str2[0] - '0') * 36000 + (str2[1] - '0') * 3600 + (str2[3] - '0') * 600 + (str2[4] - '0') * 60 + (str2[6] - '0') * 10 + (str2[7] - '0');
			for(int i = start; i < end; ++i)
			{
				table[i]++;
			}
		}
		int max = 0;
		for(int i = 0; i < 90000; ++i)
		{
			if(max < table[i])
			{
				max = table[i];
			}
		}
		cout << max << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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

int main() {
    int n;
    cin >> n;
    
    vector<int64_t> b(n - 1);
    for(int i = 0; i < n - 1; i++) cin >> b[i];

    vector<int64_t> a(n);
    a[0] = b[0];
    for(int i = 1; i < n - 1 ; i++) {
        a[i] = min(b[i - 1], b[i]);
    }
    a[n - 1] = b[n - 2];
/*
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
*/
    int64_t ans = 0;
    for(int i = 0; i < n; i++) ans += a[i];
    cout << ans << endl;

    return 0;
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  string ans;
  if (A+B<C+D) ans = "Right";
  else if (A+B>C+D) ans = "Left";
  else ans = "Balanced";
  cout << ans << endl;
}

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

#define ED return 0;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) long(pow(x,y))
const long long int mod = 1000000007;
unsigned long long int gcd(unsigned long long int a, unsigned long long int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

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

    int N, K;
    cin >> N >> K;
    vector<int> vec (K);
    for(int i = 0;i < K;i++){
        cin >> vec.at(i);
    }
    int answer = N;
    while(true){
        bool test = true;
        for(int i = 0;i < K;i++){
            if(answer > 9999 && answer / 10000 == vec.at(i)){
                test = false;
                break;
            }
            if(answer > 999 && answer / 1000 % 10 == vec.at(i)){
                test = false;
                break;
            }
            if(answer > 99 && answer / 100 % 10 == vec.at(i)){
                test = false;
                break;
            }
            if(answer > 9 && answer / 10 % 10 == vec.at(i)){
                test = false;
                break;
            }
            if(answer % 10 == vec.at(i)){
                test = false;
                break;
            }
        }
        if(test){
            cout << answer << endl;
            ED
        }
        answer++;
    }
}


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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N) {
        cin >> a[i];
    }
    auto iter = find(ALL(a), 1);
    if(iter == a.end()) {
        cout << -1 << endl;
        return 0;
    }
    int p = 0;
    for(auto i = iter;i != a.end();i++) {
        if(*i == p + 1) {
            p++;
        }
    }
    cout << N - p << endl;
    return 0;
}



Measured memory_bytes: 1024
#include<stdio.h>
int main(void)
{
	int n=0,m=0,x=0,w=0,n2=0,m2=0,x2=0,w2=0,s=0,t=0;
	scanf("%d %d %d %d",&n,&m,&x,&w);	
	scanf("%d %d %d %d",&n2,&m2,&x2,&w2);
	s=n+m+x+w;
	t=m2+n2+x2+w2;
	if(s>t||s==t){
		printf("%d\n",s);
	}	
	else{
		printf("%d\n",t);
	}
}

Measured memory_bytes: 2664
N,A,B,C = map(int, input().split())
l = [int(input()) for _ in range(N)]

INF = 10**9

def mag(i, a, b, c):
    if i == N:
        if min(a,b,c) > 0:
            return abs(A-a) + abs(B-b) + abs(C-c) - 30
        else:
            return INF

    r0 = mag(i+1, a     , b     , c     )
    r1 = mag(i+1, a+l[i], b     , c     ) + 10
    r2 = mag(i+1, a     , b+l[i], c     ) + 10
    r3 = mag(i+1, a     , b     , c+l[i]) + 10

    return min(r0, r1, r2, r3)

print(mag(0,0,0,0))


Measured memory_bytes: 3064
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
static int n = int.Parse(Console.ReadLine());
static long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
static long answer = 0;
static int leftNum = 0;
static int[] oneCount = new int[21];

	static void Main()
	{

    for(int i = 0; i < n; i++)
    {
      for(int j = 0; j < 21; j++)
      {
        if(((nums[i] >> j)&1) == 1)
        {
          oneCount[j]++;
        }      
      }
      while(!AllOne())
      {
        for(int j = 0; j < 21; j++)
        {
          if(((nums[leftNum] >> j)&1) == 1)
          {
            oneCount[j]--;
          }      
        }
        leftNum++;
      }
      answer += i-leftNum+1;
    }

		Console.WriteLine(answer);
	}

  static bool AllOne()
  {
    for(int i = 0; i < 21; i++)
    {
      if(oneCount[i] > 1) return false;
    }
    return true;
  }
  
}

Measured memory_bytes: 32732
X,K,D = map(int,input().split())

X = abs(X)

if X <= D:
    if K %2 == 1:
        ans = abs(X-D)
    else:
        ans =X
else:
    
    if X - K*D >= 0:
        ans = X - K*D
    else:
        remain = K - (X//D)*D
        if remain % 2 == 0:
            ans = abs(X - (X//D)*D)
        else:
            ans = abs(X-(((X//D)+1))*D)
print(ans)

Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i, n) for (ll i = 0; i < (n); i++)
#define fori(i, b, e) for (ll i = (b); i < (e); i++)
#define forr(i, b, e) for (ll i = (b); i >= (e); i--)
#define allele(v) v.begin(), v.end()
#define fi first
#define se second
#define Mat vector<vector<ll>>
#define Arr vector<ll>

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    const ll mod = 1e9 + 7;
    int n, m;
    cin >> n >> m;
    Arr s(n), t(m);
    forn(i, n) cin >> s[i];
    forn(i, m) cin >> t[i];

    Mat dp(n + 1, Arr(m + 1));
    forn(i, n + 1)
    {
        forn(j, m + 1)
        {
            if (i == 0 || j == 0)
                dp[i][j] = 1;
            else
            {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
                if (s[i - 1] != t[j - 1])
                    dp[i][j] = (dp[i][j] + mod - dp[i - 1][j - 1]) % mod;
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

Measured memory_bytes: 31616
import sys
n = int(sys.stdin.readline())
h = list(map(int,sys.stdin.readline().split()))

for i in range(n):
    print('node {0}: key = {1}, '.format(i+1, h[i]), end='')
    if (i+1)//2-1>=0:
        print('parent key = {0}, '.format(h[(i+1)//2-1]), end='')

    if (i+1)*2<n+1:
        print('left key = {0}, '.format(h[(i+1)*2-1]), end='')

    if (i+1)*2<n:
        print('right key = {0}, '.format(h[(i+1)*2]), end='')

    print()


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

const int MOD = (int)1e9+7;

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++)  cin >> A.at(i);

  int ans=A.at(0);
  for(int i=1;i<N;i++){
    ans=gcd(ans,A.at(i));
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
n,k = map(int, input().split())
dp = [0]+ [float("INF")]*(n)

h = list(map(int, input().split()))
for i in range(n):
    for j in range(1,min(k+1,n-i)):
        dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
        #print(1,dp[i+j],dp[i]+abs(h[i]-h[i+j]))
        #print(dp)
print(dp[n-1])

Measured memory_bytes: 55488
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<assert.h>
//#include<unordered_map>
//#include<unordered_set>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <iomanip>
#include<bits/stdc++.h>

using namespace std;
#define lead_zero(x)    __builtin_clzll(x)
#define trail_zero(x)   __builtin_ctz(x)
#define total_1s(x)     __builtin_popcount(x)
#define ll long long int
#define pi 3.14159265358979323846
#define filein freopen("input.txt", "r", stdin)
#define forn(i,n) for(int i=0;i<n;i++)
#define maxx 1000000005
#define nullptr NULL


int main()
{
   int n;
   cin>>n;
   ll a[n+5];
   ll x=-1,ans=0,mm,mn,t=0;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];

   }
   ans=0,mm=a[0],mn=a[0];
   for(int i=1;i<n;i++)
   {
       if(a[i]<a[i-1]&&t==0)
       {
           // cout<<mn<<" "<<mm<<" "<<i<<" 1 ";
           ans+=mm;
        // cout<<ans<<endl;
           mm=0;
           mn=105;
           t=1;
       }

      else if(a[i]<a[i-1]&&t)
       {
          // cout<<mn<<" "<<mm<<" "<<i<<" 2 ";
           ans+=mm;
           ans-=mn;
           mm=0;
           mn=105;

         //  cout<<ans<<endl;


       }
       mm=max(mm,a[i]);
       mn=min(mn,a[i]);
   }
  // cout<<mn<<" "<<mm<<endl;
   if(mm!=0&&mn!=105&&t)
  {ans+=mm;
   ans-=mn;}
   else if(mm!=0&&mn!=105&&t==0)
   {
       ans+=mm;
   }
   cout<<ans<<endl;


}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 100100100100
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vii;
typedef vector<ll> vll;
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; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int a, b;
string s; 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    int n;
    cin >> n;
    if (n == 1) cout << "Hello World" << endl;
    else {
      cin >> a >> b;
      cout << a + b << endl;
    }
    return 0;
}




Measured memory_bytes: 892
/**
 * @Author: harshkhajuria
 * @Date:   03-Jun-2019 09:13:25 am
 * @Email:  khajuriaharsh729@gmail.com
 * @Filename: A - AtCoder Beginner Contest 999.cpp
 * @Last modified by:   harshkhajuria
 * @Last modified time: 03-Jun-2019 09:14:39 am
 */

#include <bits/stdc++.h>
#define ll long long
#define mp(a, b) make_pair(a, b)
#define newline cout << endl;
#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(),v.end()
using namespace std;

template <typename S, typename T> ostream& operator<<(ostream& out, pair<S, T> const& p)
{
	out << '(' << p.ff << ", " << p.ss << ')';
	return out;
}

template <typename T> ostream& operator<<(ostream& out, vector<T> const& v)
{
	int l = v.size();
	for (int i = 0; i < l - 1; i++)
		out << v[i] << ' ';
	if (l > 0)
		out << v[l - 1];
	return out;
}

template <typename T> void trace(const char* name, T&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename T, typename... Args> void trace(const char* names, T&& arg1, Args&&... args)
{
	const char* comma = strchr(names + 1, ',');
	cout.write(names, comma - names) << " : " << arg1 << " | ";
	trace(comma + 1, args...);
}

/*Input*/
/*Input*/

int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
	clock_t tStart = clock();
	int test;
	test = 1;
	// cin >> test;
	while (test--) {
    string s;
    cin >> s;
    int n = s.length();
    for(int i=0;i<n;i++){
      if(s[i]=='9') cout << '1';
      else cout << '9';
    }
    cout << endl;
	}
#ifdef LOCAL_DEFINE
	printf("Time taken: %.2fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);
#endif
	return 0;
}


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

struct edge { int to; int num; };
int col[100100];
vector<edge> tree[100100];
bool visited[100100];

void tansaku(int cur, int cl){
    int k = (cl == 1) ? 2 : 1;
    REP(i, 0, tree[cur].size()){ 
        int to = tree[cur][i].to;
        int num = tree[cur][i].num;
        if(visited[to]) continue;
        col[num] = k;
        visited[to] = true;
        tansaku(to, k);
        k++;
        if(k == cl) ++k;
    }
}

int main()
{
    int N;
    scanf("%d", &N);
    REP(i, 1, N){
        int a, b;
        scanf("%d %d", &a, &b);
        tree[a].push_back((edge){b,i});
        tree[b].push_back((edge){a,i});
    }
    visited[1] = true;
    tansaku(1, -1);
    int res = 1;
    REP(i, 0, N) res = max(res, col[i]);
    printf("%d\n", res);
    REP(i, 1, N) printf("%d\n", col[i]);
    return 0;
}

Measured memory_bytes: 7552
class BinaryTree:
    class Node:
        def __init__(self, nid, left, right):
            self.id = nid
            self.left = left
            self.right = right

        def has_left(self):
            return self.left is not None

        def has_right(self):
            return self.right is not None

        def __str__(self):
            return str(self.id)

    @classmethod
    def create(cls, ids):
        nodes = [None] * len(ids)

        def _create(nid):
            if nid in nodes:
                return nodes[nid]
            if nid == -1:
                return None

            lid, rid = ids[nid]
            if lid == -1 and rid == -1:
                right = None
                left = None
            elif lid == -1:
                right = _create(rid)
                left = None
            elif lid == -1:
                right = None
                left = _create(lid)
            else:
                right = _create(rid)
                left = _create(lid)
            nodes[nid] = cls.Node(nid, left, right)
            return nodes[nid]

        def _root(nodeids):
            for nid in range(len(nodeids)):
                if all([lid != nid and rid != nid for lid, rid in nodeids]):
                    return nid

        root = _create(_root(ids))
        return cls(root)

    def __init__(self, root):
        self.root = root

    def preorder(self):
        def _preorder(node):
            yield node
            if node.has_left():
                yield from _preorder(node.left)
            if node.has_right():
                yield from _preorder(node.right)
        yield from _preorder(self.root)

    def inorder(self):
        def _inorder(node):
            if node.has_left():
                yield from _inorder(node.left)
            yield node
            if node.has_right():
                yield from _inorder(node.right)
        yield from _inorder(self.root)

    def postorder(self):
        def _postorder(node):
            if node.has_left():
                yield from _postorder(node.left)
            if node.has_right():
                yield from _postorder(node.right)
            yield node
        yield from _postorder(self.root)


def run():
    n = int(input())

    nodeids = [None] * n
    for i in range(n):
        nid, lid, rid = [int(x) for x in input().split()]
        nodeids[nid] = [lid, rid]

    tree = BinaryTree.create(nodeids)

    print('Preorder')
    for node in tree.preorder():
        print(" {}".format(node), end="")
    print()
    print('Inorder')
    for node in tree.inorder():
        print(" {}".format(node), end="")
    print()
    print('Postorder')
    for node in tree.postorder():
        print(" {}".format(node), end="")
    print()


if __name__ == '__main__':
    run()



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

int main() {
	int n;
	cin >> n;
	vector<pair<double, double>> x(n);
	rep(i, n) cin >> x[i].first >> x[i].second;
	double ans = 0;
	double cnt = 0;
	vector<int> v(n);
	rep(i, n) v[i] = i;
	do {
		rep(i, n - 1) ans += sqrt((x[v[i + 1]].first - x[v[i]].first) * (x[v[i + 1]].first - x[v[i]].first) + (x[v[i + 1]].second - x[v[i]].second) * (x[v[i + 1]].second - x[v[i]].second));
		cnt++;
	} while (next_permutation(v.begin(), v.end()));
	printf("%.12f\n", ans / cnt);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;

int main() {
  Real a, b;
  cin >> a >> b;
  Bint t = static_cast<Bint>(a * b);
  cout << t << endl;
}

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

static const char* names[15]={
	"Rock" ,"Fire"  ,"Scissors","Snake"    ,"Human",
	"Tree" ,"Wolf"  ,"Sponge"  ,"Paper"    ,"Air"  ,
	"Water","Dragon","Devil"   ,"Lightning","Gun"
};

int get_id(const char* name) {
	int i;
	for(i=0;i<15;i++) {
		if(strcmp(name,names[i])==0)return i;
	}
	return -1;
}

const char* getnamefromid(int id) {
	static const char* err="Draw";
	if(id<0 || id>14)return err;
	return names[id];
}

int main(void) {
	int n;
	int i,j;
	char hand[100];
	int hands_id[1000];
	int winner;
	int ok,ng;
	while(1) {
		scanf("%d",&n);
		if(n==0)break;
		for(i=0;i<n;i++) {
			scanf("%s",hand);
			hands_id[i]=get_id(hand);
		}
		winner=-1;
		for(i=0;i<n;i++) {
			ok=ng=0;
			for(j=0;j<n;j++) {
				if(hands_id[i]!=hands_id[j]) {
					if((hands_id[i]-hands_id[j]+15)%15>7) {
						ok=1;
					} else {
						ng=1;
					}
				}
			}
			if(ok && !ng){winner=hands_id[i];break;}
		}
		puts(getnamefromid(winner));
	}
	return 0;
}

Measured memory_bytes: 0
//package AtCoder;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		
		
			
		int[] a=new int[n];
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		sc.close();
		
		if(n==1)
		{
			System.out.println(0);
			return;
		}
		int[] cost=new int[n];
		//cost[0]
		cost[0]=0;
		cost[1]=Math.abs(a[1]-a[0]);
		for(int i=2;i<n;i++)
		{
			cost[i]=Math.min(Math.abs(a[i]-a[i-1])+cost[i-1], Math.abs(a[i]-a[i-2])+cost[i-2]);
			
		}
		System.out.println(cost[n-1]);

	}

}


Measured memory_bytes: 51416
#include<iostream>
#include<numeric>

using namespace std;


int main() {
	// 各月の日数を定数として定義しておく
	// 最初に0があるのは
	// 1.配列のインデックスと月が異なるとややこしくなる
	// 2.1月の場合に例外的な処理をしなくていいようにするため
	const int offset_days[]{
		0,31,29,31,30,31,30,31,31,30,31,30,31
	};
	const char* day_str[]{
		"Monday",
		"Tuesday",
		"Wednesday",
		"Thursday",
		"Friday",
		"Saturday",
		"Sunday"
	};
	// 処理を簡単にするため、前年の大晦日を起点に考える
	const int day_12_31 = 2;

	int m, d;
	while (cin >> m >> d, m != 0) {
		// 各月の日数の和を求める。
		// オフセットとして前年の大晦日に対応する値を設定する。
		int sum = std::accumulate(&offset_days[0], &offset_days[m], day_12_31);
		// 該当する日の曜日を求めるため、日数を加算して7で割ったあまりを求める。
		int day = (sum + d) % 7;
		cout << day_str[day] << endl;
	}

	return 0;
}

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

int main()
{
    int r, D, x;
    cin >> r >> D >> x;
    
    int ans = r * x - D;
    cout << ans << endl;
    for (int i = 0; i < 9; i++) {
        int ch = r * ans - D;
        ans = ch;
        cout << ans << endl;
    }
}

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

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

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9 + 7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(a) begin(a), end(a)

int main(void) {
    int N = 8;
    vector<vector<int>> G(8, vector<int>(8, 0));
    int k;
    cin >> k;
    vector<pair<int, int>> queens;
    REP(i, k) {
        int r, c;
        cin >> r >> c;
        G[r][c] = 1;
        queens.pb(make_pair(r, c));
    }

    vector<int> perm(N);
    REP(i, N) perm[i] = i;

    do {
        bool ok = true;
        for (auto i : queens) {
            if (perm[i.fi] != i.se) ok = false;
        }
        if (!ok) continue;

        // REP(i, N) cout << perm[i] << " \n"[i == N - 1];
        REP(i, N) {
            bool okok = true;
            for (int j = 0; j < i; j++) {
                if (abs(i - j) == abs(perm[i] - perm[j])) okok = false;
            }
            if (!okok) ok = false;
        }

        if (ok) {
            REP(i, N) G[i][perm[i]] = 1;
            break;
        }
    } while (next_permutation(ALL(perm)));

    REP(i, 8) {
        REP(j, 8) {
            if (G[i][j])
                cout << 'Q';
            else
                cout << '.';
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3172
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF 1e12

ll dp[100][200000];

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

    vector<ll> a;
    a.pb(1);

    ll b = 6;

    while(b <= n) {
        a.pb(b);
        b*=6;
    }
    b  = 9;
    while(b <= n){
        a.pb(b);
        b*=9;
    }

    REP(i,a.size() + 1)
        REP(j,n+1)
            dp[i][j] = INF;

    dp[0][0] = 0;

    FOR(i,1,a.size()+1) {
        REP(j,n+1) {
            dp[i][j] = min(dp[i][j],dp[i - 1][j]);

            if(j - a[i - 1] >= 0) {
                dp[i][j] = min(dp[i][j],dp[i][j - a[i - 1]]+1);
            }
        }
    }

    cout << dp[a.size()][n] << endl;
}



Measured memory_bytes: 19968