akhauriyash/Code-Regression huggingface dataset:
# reduce

def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考1: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    # 参考2: https://atcoder.jp/contests/abc160/submissions/15255726
    from functools import reduce
    G = [[] for _ in range(n)]
    for a, b in edges:
        G[a].append(b)
        G[b].append(a)
    # step 1
    parents = [0] * n
    order = []  # 行きがけ順
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order.append(v)
        for u in G[v]:
            if p != u:
                stack.append(u)
                parents[u] = v
    # 下から登る
    dp_down = [0]*n  # 自身とその下
    for v in order[:0:-1]:
        p = parents[v]
        dp_down[v] = add_node(reduce(
            merge,
            (dp_down[u] for u in G[v] if u!=p),
            identity
        ), v)
    # step 2
    # 上から降りる
    dp_up = [identity] * n  # 親とその先
    for v in order:
        Gv = G[v]
        if len(Gv) == 1 and v != 0:
            continue
        p = parents[v]
        cum = identity
        right = [identity]
        for u in Gv[::-1]:
            if u != p:
                cum = merge(dp_down[u], cum)
                right.append(cum)
        cum = dp_up[v]
        idx_right = -2
        for u in Gv:
            if u != p:
                dp_up[u] = add_node(merge(cum, right[idx_right]), v)
                idx_right -= 1
                cum = merge(cum, dp_down[u])
    results = [add_node(
        merge(
            reduce(merge, (dp_down[u] for u in Gv if u != parents[v]), identity),
            dp_up[v]
        ), v
    ) for v, Gv in enumerate(G)]
    return results

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(input())
    AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    fac, facinv = comb.fac, comb.facinv
    def merge(a, b):
        a0, a1 = a
        b0, b1 = b
        return a0*b0*fac[a1+b1]*facinv[a1]*facinv[b1]%mod, a1+b1
    def add_node(a, idx):
        a0, a1 = a
        return a0, a1+1
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()


Measured memory_bytes: 183576
#include<stdio.h>
int main(void)
{
	int max,min,a,i,n;
	long long sum;
	max=10000000;
	min=-10000000;
	sum=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a);
		if(max>a){
			max=a;
		}
		if(min<a){
			min=a;
		}
		sum+=a;
	}
	printf("%d %d %lld\n",max,min,sum);
	
	return 0;
}



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

int main() {
    int64_t n, a, b;
    cin >> n;
    vector<int64_t> x(n), y(n);
    for (auto i = 0; i < n; i++) {
        cin >> a >> b;
        x[i] = a - b;
        y[i] = a + b;
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    cout << max(abs(x.back() - x.front()),
                abs(y.back() - y.front()))
         << endl;
    return 0;
}

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

constexpr ll INF = ll(1e+18) + 1;

ll dist(ll a, ll b, ll c, ll d) {
    return abs(a-c) + abs(b-d);
}

int main() {
    map<string, int> m;
    string buf;
    int N;

    cin >> N;

    rep (i, N) {
        cin >> buf;

        if (m.find(buf) == m.end()) {
            m.insert(make_pair(buf, 0));
        } else {
            m.erase(buf);
        }
    }

    cout << m.size() << endl;
}


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

template<class T>
inline bool rd(T &num) {
    char in;bool IsN = false;
    while(in = getchar(), in != '-' && (in < '0' || in > '9'))if(in == EOF)return false;
    in == '-' ? (IsN = true, num = 0) : num = in - '0';
    while(in = getchar(), in >= '0' && in <= '9')num = num * 10 + in - '0';
    return IsN ? num = -num : num, true;
}

#define __m int mid=(l+r)>>1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

#define rep(i,a,b) for(register int i = (a); i< (b); i++)
#define per(i,a,b) for(register int i = (a); i> (b); i--)
#define rd2(a,b) rd(a)&&rd(b)
#define rd3(a,b,c) rd(a)&&rd(b)&&rd(c)
#define clr(a) memset(a,0,sizeof(a))
#define inf(a) memset(a,0x3f,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

string nico;
#ifdef LOCAL
#define bug(x) cout<<#x<<" : "<<x<<endl
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#else
#define bug(x)
#define infile(x)
#define outfile(x)
#endif

const int maxn  = 3e3 + 7;
const int inf   = 0x3f3f3f3f;
const LL  Linf  = ((LL)inf<<32)|inf;
const int mod   = 1e9 + 7;

int num[maxn];
priority_queue<int,vector<int>,greater<int> >Div,ready;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k,q;
    int ans = inf;
    cin>>n>>k>>q;
    rep(i,0,n)
        cin>>num[i];
    num[n]=-inf;
    rep(i,0,n){
        while(ready.size())ready.pop();
        rep(j,0,n+1){
            if(num[j]>=num[i])
                Div.push(num[j]);
            else{
                while(Div.size()>=k){
                    ready.push(Div.top());
                    Div.pop();
                }
                while(Div.size())Div.pop();
            }
        }
        if(ready.size()<q)
            continue;
        int f = ready.top();
        int e = 0;
        rep(z,0,q){
            e = ready.top();
            ready.pop();
        }
        ans = min(e-f,ans);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "cmath"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	if (s < t) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;

signed main(){
  string s;
  cin>>s;
  int ans=0;

  int w=0;
  for(int i=0;i<s.size();i++)if(s[i]=='W')w++;

  int a=0;

  for(int i=0;i<s.size();i++){
    if(s[i]=='W'){
      ans+=i-a;
      a++;
    }
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,x;
    cin >> n >> x;
    int l[n];
    for(int i=0;i<n;i++)cin >> l[i];
    int d[n+1];
    d[0]=0;
    for(int i=1;i<=n;i++){
        d[i] = d[i-1]+l[i-1];
    }
    int ans=0;
    for(int i=0;i<n+1;i++){
        if(x>=d[i])ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define INF 2e18
#define mod 1000000007
#define y1 solai
#define fi first
#define se second
typedef long long ll;
void read(ll &x)
{
	scanf("%lld",&x);
}
void read(ll &x, ll &y)
{
	scanf("%lld%lld",&x,&y);
}
void read(ll &x, ll &y, ll &z)
{
	scanf("%lld%lld%lld",&x,&y,&z);
}
void print(ll x)
{
	printf("%lld ",x);
}
void println(ll x)
{
	printf("%lld\n",x);
}
const ll N=100000;
ll n,a[N+100],mn,mx,cnt,x,l,r,mid,ans1,ans2;
ll f(ll x)
{
	for(ll i=1;i<=n;i++)
		x=x/a[i]*a[i];
	return x;
}
int main()
{
	//freopen("c.cpp","r",stdin);
 
	cin>>n;
	for(ll i=1;i<=n;i++)
		read(a[i]);
	if(a[n]!=2)
	{
		cout<<-1;
		return 0;
	}
	l=1,r=INF;
	while(l<r)
	{
		mid=(l+r)/2;
		if(f(mid)>=2)
			r=mid;
		else
			l=mid+1;
	}
	if(f(l)!=2)
	{
		cout<<-1;
		return 0;
	}
	cout<<l<<" ";
	l=1,r=INF;
	while(l<r)
	{
		mid=(l+r+1)/2;
		if(f(mid)>2)
			r=mid-1;
		else
			l=mid;
	}
	cout<<l;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void){
  int t=0,h=0;
  int a,b,c;
  while((scanf("%d,%d,%d",&a,&b,&c))!=EOF){
    if(a*a+b*b==c*c){
      t++;
    }else if(a==b){
      h++;
    }
  }
  printf("%d\n",t);
  printf("%d\n",h);
  return 0;
}

Measured memory_bytes: 596
#!/usr/bin/env python3
import sys

def solve(s: str):
    """
    >>> solve("needed")
    (2, 3)
    >>> solve("ede")
    (1, 3)
    """
    for i, (c0, c1) in enumerate(zip(s, s[1:]), 1):
        if c0 == c1:
            return i, i+1
    for i, (c0, c2) in enumerate(zip(s, s[2:]), 1):
        if c0 == c2:
            return i, i+2
    return (-1, -1)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    print(*solve(s))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    # test()
    main()


Measured memory_bytes: 9172
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
using namespace std;
long long int cut(long long int h, long long int w) {
	if (h % 2 == 0 || w % 2 == 0) { return h * w / 2; }
	else {
		return max(h*(w / 2), w*(h / 2));
	}
}


int main() {
	long long int h, w,in=1000000000000000000;
	cin >> h>> w;
	if (h % 3 == 0 || w % 3 == 0) {
		cout << 0 << endl;
		return 0;
	}

	for (int i = 1; i < h; i++) {
		if (in > max(max(i*w,cut(h-i,w)),w*(h-i)-cut(h-i,w))-min(min(i*w, cut(h - i, w)), w*(h - i) - cut(h - i, w))) {
			in = max(max(i*w, cut(h - i, w)), w*(h - i) - cut(h - i, w)) - min(min(i*w, cut(h - i, w)), w*(h - i) - cut(h - i, w));
		}
	}

	for (int i = 1; i < w; i++) {
		if (in > max(max(i*h, cut(h, w-i)), (w-i)*(h) - cut(h, w-i)) - min(min(i*h, cut(h, w - i)), (w - i)*(h)-cut(h, w - i))) {
			in = max(max(i*h, cut(h, w - i)), (w - i)*(h)-cut(h, w - i)) - min(min(i*h, cut(h, w - i)), (w - i)*(h)-cut(h, w - i));
		}
	}
	cout << in << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<string>
#include<cstdlib>
#include<sstream>
#include<queue>
#include<deque>
#include<cmath>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<iomanip>
#define INF 2147483647
#define lli long long int
#define MOD 1000000007
#define pb push_back

using namespace std;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
int main() {
	int a,b,c; cin >> a >> b >> c;
	int ans = 0;
	bool awake = true;
	int interval = a;
	while(1){
		ans++;
		if (ans > 3600) {
			ans = -1;
			break;
		}
		if (awake and ans%60 == c){
			break;	
		}
		if (awake){
			interval--;
			if (interval == 0){
				awake = false;
				interval = b;
			}
		}else{
			interval--;
			if (interval == 0){
				awake = true;
				interval = a;
			}

		}
	}
	cout << ans << endl;
	return 0;

}

Measured memory_bytes: 3104
#include<iostream>
#include<string.h>
#include<cmath>
using namespace std;
int n;
int main()
{
	int m,sum=0;
	cin>>n>>m;
	if(n<=0&&m>=0)
	{
		cout<<"Zero"<<endl;
		return 0;
	}
	for(int i=n;i<=m;i++)
	{
		if(i<0)
		sum++;
	}
	if(sum%2!=0)
	{
		cout<<"Negative"<<endl;
	}
	else
	{
		cout<<"Positive"<<endl;
	} 
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define N 51
using namespace std;

int main(){
  while(1){
  string str[N];
  int p,a,b,c,d,e,f,s,m,n;
   double ans[N];
  cin>>n;
   if(n==0) break;
   for(int i=0;i<n;i++){
    cin>>str[i]>>p>>a>>b>>c>>d>>e>>f>>s>>m;
    ans[i]=((double)(f*m*s)-p)/((a+b+c)+(d*m)+(e*m));
  }
    for(int i=0;i<n-1;i++)
      for(int j=n-1;j>i;j--){
	if(ans[j]>ans[j-1]) swap(ans[j],ans[j-1]),swap(str[j],str[j-1]);
       else if(ans[j]==ans[j-1] && str[j]<str[j-1]) swap(str[j],str[j-1]);
      }
       for(int i=0;i<n;i++) cout<<str[i]<<endl;
    cout<<"#"<<endl;

  }
  return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
using namespace std;
    int main(void){
        // Your code here!
        int H, N;
        cin >> H >> N;
        int i;
        vector<int> A(N);
        int sum = 0;
            for(i = 0; i < N; i++){
                cin >> A.at(i);
                sum += A.at(i);
            }
                if(sum >= H){
                    cout << "Yes";
                }else{
                    cout << "No";
                }
    return 0;}


Measured memory_bytes: 640
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define fr(i, a, b) for(int i = a; i < b; i++)
#define frb(i, a, b) for(int i = a; i > b; i--)
#define sz(s) (int)s.size()
#define all(v) (v).begin(), (v).end()
#define srt(v) sort(all(v))
#define srtGreat(v) sort(all(v), greater<ll>())
#define iset tree < int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update >
#define oset tree < pair<int, int> ,  null_type ,  less<pair<int, int> > ,  rb_tree_tag ,  tree_order_statistics_node_update >
#define ll long long
using namespace std; 
using namespace __gnu_pbds; 

int  prg()
{
    int a,b;
    cin>>a>>b;
    cout<<a*b;
    return 0;
}
void multi()
{
    int t;
    cin>>t;
    for(int i=0;i<t;++i)
    {
       prg();
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    prg();
    return 0;
}

Measured memory_bytes: 3652
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;



int main() {
  int N;
  int ans = 0;

  cin >> N;

  if (10 > N) {
    cout << N << endl;
    return 0;
  }

  if (10 <= N)
    ans += min(9, N);
  if (100 <= N)
    ans += min(900, N - 100 + 1);
  if (1000 <= N) {}
  if (10000 <= N)
    ans += min(90000, N - 10000 + 1);

  cout << ans << endl;
}


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

int main(){
  int Asum = 0,Bsum = 0;
  int MaxN, Maxpos;

  int N;  //カード枚数
  cin >> N;

  vector <int> a(N,0);  //カードに書かれた数

  for (int i=0; i<N; i++){
    cin >> a.at(i);
  }

  int kaisu = N/2 + N%2;
  for (int loop=0; loop<kaisu; loop++){
  // Aliceの戦略
    Maxpos = 0;
    MaxN = 0;
    for (int i=0; i<N; i++){
      if (a.at(i) > MaxN){
        MaxN = a.at(i);
        Maxpos = i;
      }
    }
    Asum += MaxN;
    a.at(Maxpos) = 0;
  //Bobの戦略  
    Maxpos = 0;
    MaxN = 0;
    for (int i=0; i<N; i++){
      if (a.at(i) > MaxN){
        MaxN = a.at(i);
        Maxpos = i;
      }
    }
    Bsum += MaxN;
    a.at(Maxpos) = 0;
  }
  cout << Asum - Bsum << endl;
}     

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

long long N;
long long a[200000];

int main(){
    long long m;
    cin >> N;
    for(int i=0;i<N;i++) cin >> a[i];
    long long s = 0;
    for(int i=1;i<N;i++) s += a[i];
    long long t = a[0];
    m = abs(s-t);
    for(int i=1;i<N-1;i++){
        s -= a[i];
        t += a[i];
        m = min(m,abs(s-t));
    }
    cout << m << endl;
    return 0;
}

Measured memory_bytes: 1792
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("avx,avx2,fma,sse,sse2")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
int main()
{
    string s;
    cin>>s;
    int f=0,ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='R')f++;
        else f=0;
        ans=max(ans,f);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
int main()
{
  map<string, int> balls;
  string s1="";
  string s2="";
  cin>>s1;
  cin>>s2;
  int i,j;
  cin>>i;
  cin>>j;
  balls[s1]=i;
  balls[s2]=j;
  string s3="";
  cin>>s3;
  balls[s3]=balls[s3]-1;
  cout<<balls[s1]<<" "<<balls[s2];
}


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

using namespace std;
using ll       = long long;
const int NMAX = 3e3 + 11;

int  n, a[NMAX], li, ri;
ll   mem[NMAX][NMAX];
bool vis[NMAX][NMAX];

ll solve(bool maximizer)
{
    int l, r;
    ll  left_ans, right_ans;

    if (li > ri)
        return 0;

    ll &ans = mem[li][ri];
    if (vis[li][ri])
        return ans;
    vis[li][ri] = true;

    l        = a[li++];           // try
    left_ans = solve(!maximizer); // partial ans
    --li;                         // undo

    r         = a[ri--];           // try
    right_ans = solve(!maximizer); // partial ans
    ++ri;                          // undo

    if (maximizer)
        ans = max(l + left_ans, r + right_ans);
    else
        ans = min(left_ans - l, right_ans - r);
    return ans;
}

int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    li = 0, ri = n - 1;

    cout << solve(true) << endl;
    return 0;
}


Measured memory_bytes: 78592
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		
		final int s = sc.nextInt();
		
		int i = 1;
		final List<Integer> a = new ArrayList<>();
		a.add(s);
		int tail = s;
		while (true) {
			i++;
			final int an = f(tail);
			
			final boolean satisfy = a.stream().anyMatch(j -> j == an);
			
			if (satisfy) {
				break;
			}
			
			tail = an;
			a.add(an);
		}
		
		System.out.println(i);
	}
	
	private static int f(int n) {
		if (n % 2 == 0) {
			return n / 2;
		} else {
			return 3 * n + 1;
		}
	}

}

Measured memory_bytes: 27092
#include<iostream>
#include<algorithm>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define RREP(i, a, n) for(int i=n-1; i>=a; i--)

bool prime[1000001];
void create_prime() {
	prime[0] = prime[1] = false;
	REP(i, 2, 1000001) prime[i] = true;

	for (int i = 2; i*i <= 1000001; i++) {
		for (int j = 2 * i; j < 1000001; j += i) {
			prime[j] = false;
		}
	}
	return;
}
int main() {
	create_prime();
	
	int a, d, n;
	while (cin >> a >> d >> n, a || d || n) {
		int cnt = 0, idx = a;
		while (cnt < n) {
			if (prime[idx]) cnt++;
			idx += d;
		}

		cout << idx - d << endl;
	}

	return 0;
}

Measured memory_bytes: 4040
# 愚直解
#  from itertools import permutations

# # n = int(input())
# # kumiawase = list(permutations(range(1, 2 * n), 2 * n - 1))
# ans_set = set()
# kumiawase = [(3, 4, 5, 6, 1, 2, 7, 8, 9, 10, 11)]
# for kumi in kumiawase:
#     kouho = kumi
#     while kouho:
#         nex = []
#         for i in range(len(kouho) - 2):
#             temp = [kouho[i], kouho[i + 1], kouho[i + 2]]
#             temp.sort()
#             nex.append(temp[1])
#         if len(nex) == 1:
#             break
#         kouho = nex[::]
#         print(kouho)
#     ans_set.add(nex[0])
#     if nex[0] == 2:
#         print(kumi)
#         exit()

# print(ans_set)

n, x = map(int, input().split())

if x <= 1 or x >= 2 * n - 1:
    print("No")
    exit()
if n == 2:
    print("Yes")
    for i in range(3):
        print(i + 1)
    exit()

ans = [0] * (2 * n - 1)
used = [False] * (2 * n)

if x <= n:
    ans[n - 1] = x
    ans[n - 2] = x - 1
    ans[n] = x + 1
    ans[n - 3] = x + 2
    used[x] = True
    used[x - 1] = True
    used[x + 1] = True
    used[x + 2] = True
    num = 1
    for i in range(2 * n - 1):
        if ans[i] == 0:
            while used[num]:
                num += 1
            ans[i] = num
            num += 1
    print("Yes")
    print(*ans, sep="\n")
else:
    ans[n - 1] = x
    ans[n - 2] = x + 1
    ans[n] = x - 1
    ans[n - 3] = x - 2
    used[x] = True
    used[x + 1] = True
    used[x - 1] = True
    used[x - 2] = True
    num = 1
    for i in range(2 * n - 1):
        if ans[i] == 0:
            while used[num]:
                num += 1
            ans[i] = num
            num += 1
    print("Yes")
    print(*ans, sep="\n")



Measured memory_bytes: 21608
package main

import (
	"fmt"
)

func main() {
	//s := nextLine()
	var s string
	var res string
	fmt.Scan(&s)
	if s == "hi" || s == "hihi" || s == "hihihi" || s == "hihihihi" || s == "hihihihihi" {
		res = "Yes"
	} else {
		res = "No"
	}
	fmt.Println(res)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORe(i, k, n) for(int i = (k); i <= (n); i++)
#define FORr(i, k, n) for(int i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(int i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;

bool dp[(1<<10)+5][15];

int main(void){
  int n, m;
  cin >> n >> m;
  vector<int> s(m, 0);
  vector<int> p(m);
  REP(i, m){
    int k;
    cin >> k;
    REP(j, k){
      int t;
      cin >> t;
      t--;
      s[i] |= (1<<t);
    }
  }
  REP(i, m) cin >> p[i];

  FOR(i, 0, 1<<n){
    dp[i][0] = true;
    REP(j, m){
      int t = s[j] & i;
      if(__builtin_popcount(t) % 2 == p[j]) dp[i][j+1] = dp[i][j] & true;
    }
  }
  int ans = 0;
  FOR(i, 0, 1<<n) if(dp[i][m]) ans++;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0L;i--)
#define prep(i,n) for(int64_t i=1;i <= (int64_t)(n);i++)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  fspcnt = 0;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}

int64_t calcmodcomb(int64_t n,int64_t r){
  return (((modfact.at(n)*modinvfact.at(r))%univMod)*modinvfact.at(n-r))%univMod;
}

int64_t calcmodpositive(int64_t n){
  return (n + ((abs(n)+univMod-1)/univMod)*univMod)%univMod;
}
  
    */


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  string s,t,u;
  cin >> s >> t >> u;
  cout << s.at(0) << t.at(1) << u.at(2) << endl;
  
  
}

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

P p[600000];
ll sum[600000];
ll D[600000];
int main(){
	int n;scanf("%d",&n);
	rep(i,n){
		scanf("%lld%lld",&p[i].first,&p[i].second);
	}
	sort(p,p+n);
	rep(i,n){
		if(i)sum[i]+=sum[i-1];
		sum[i]+=p[i].second;
	}
	D[n-1]=LLONG_MIN/2;
	ll ans=0;
	for(int i=n-1;i>=0;i--){
		if(i!=n-1){
			D[i]=D[i+1];
		}
		D[i]=max(D[i],sum[i]-p[i].first);
		ll cnt=D[i];
		if(i)cnt-=sum[i-1];
		ans=max(ans,cnt+p[i].first);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 12032
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <sstream>
using namespace std;
int main(){
	string buf;
	
	while(getline( cin,buf )){
	
		for(int i=0;i<30;++i){
			string tmp = buf;
			for(int j=0;j<tmp.size();++j){
				if( tmp[j] >= 'a' && tmp[j] <= 'z' ){
					int aaa = (int)tmp[j] + i;
					if( aaa > 'z' ){
						int diff = aaa -1 - 'z' ;
						tmp[j] = 'a' + diff;
					}else{
						tmp[j] = aaa;
					}
				}
			}
			if( tmp.find("the")!=string::npos || tmp.find("this")!=string::npos ||tmp.find("that")!=string::npos ){
				cout << tmp << endl;
				break;
			}
			//cout << i << " " << tmp << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <climits>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> P;
static const ll INF=10000000000000;
struct ED{
	int s,t,d;
};

bool operator<(ED a,ED b){
	return a.d>b.d;
}

bool operator<(pair<ll,ED> a,pair<ll,ED> b){
	return a.F>b.F;
}


int main(){
	int V,E,r,s,t,d;
	vector<vector<ED> > v(100010);
	ll vmin[100010];
	int vis[100010];
	int exi[100010];
	priority_queue<pair<long long,ED> > pq;
	cin>>V>>E>>r;
	rep(i,100010){
		vmin[i]=INF;
		vis[i]=0;
		exi[i]=0;
	}
	rep(i,E){
		cin>>s>>t>>d;
		ED t1,t2;
		t1.s=s; t1.t=t; t1.d=d;
		t2.s=t; t2.t=s; t2.d=d;
		v[s].PB(t1);
		//v[t].PB(t2);
		exi[t]=exi[s]=1;
	}
	vmin[r]=0;
	vis[r]=1;
	rep(i,v[r].size()){
		pair<int,ED> tp;
		tp.F=v[r][i].d;
		tp.S=v[r][i];
		pq.push(tp);
	}
	
	while(!pq.empty()){
		pair<ll,ED> tmp=pq.top();
		pq.pop();
		if(vis[tmp.S.t]==1) continue;
		//cout<<"tmp "<<tmp.F<<" "<<tmp.S.s<<" "<<tmp.S.t<<" "<<tmp.S.d<<endl;
		vmin[tmp.S.t]=tmp.F;
		vis[tmp.S.t]=1;
		//cout<<tmp.t<<endl;
		rep(i,v[tmp.S.t].size()){
			//cout<<vis[v[tmp.t][i].t]<<endl;
			if(vis[v[tmp.S.t][i].t]==0){
				//cout<<"hoge\n";
				pair<ll,ED> tp;
				tp.F=tmp.F+v[tmp.S.t][i].d;
				tp.S=v[tmp.S.t][i];
				pq.push(tp);
				//cout<<"v "<<v[tmp.t][i].s<<" "<<v[tmp.t][i].t<<" "<<v[tmp.t][i].d<<endl;
			}
		}
	}
	rep(i,V){
		if(vis[i]==1){
			cout<<vmin[i]<<endl;
		}
		else if(vmin[i]==INF){
			cout<<"INF"<<endl;
		}
	}
	 return 0;
}

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

#define ll long long

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif

    int n;
    cin>>n;
    int A[n];
    for(int i=0;i<n;i++) cin>>A[i];
    int ans=0;
    sort(A,A+n);
    for(int i=0;i<n;i++){
        for(int j = i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                if(A[i]==A[j] || A[j]==A[k]) continue;
                if(A[i]+A[j]>A[k]) ans++;
            }
        }
    }
    cout<<ans;
}

Measured memory_bytes: 3700
N, K =map(int, input().split())
hs = [10**6]*K + list(map(int, input().split()))
dp = [0]*(N+K+1)
for i in range(K+1, N+K):
    ans = dp[i-1]+abs(hs[i]-hs[i-1])
    for k in range(2, K+1):
        ans = min(ans, dp[i-k]+abs(hs[i]-hs[i-k]))
    dp[i] = ans
print(dp[N+K-1])

Measured memory_bytes: 53856
#include <iostream>

int main(){
  
  int n,t,a,b,d,h,ans,num=1,anum=1;
  std::cin >> n >> t >> a >> ans;
  b = (t-a)*1000/6;
  d = abs(ans - b);

  while(std::cin >> h){
    num++;
    if(d > abs(b-h)){
      d = abs(b-h);
      anum = num;
    }
  }
  std::cout << anum << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int n,a,b,c;
int l[10];
int dfs(int i,int aa,int bb,int cc){

    if(i == n){
        if(min({aa,bb,cc}) == 0) return INF;
        else return abs(a-aa)+abs(b-bb)+abs(c-cc)-30;
    }
    int sub[4];   
    sub[0] = dfs(i+1,aa,bb,cc);
    sub[1] = dfs(i+1,aa+l[i],bb,cc)+10;
    sub[2] = dfs(i+1,aa,bb+l[i],cc)+10;
    sub[3] = dfs(i+1,aa,bb,cc+l[i])+10;
    return *min_element(sub,sub+4);
}

int main(){
    cin >> n >> a >> b >> c;
    for(int i = 0; i < n; i++) cin >> l[i];
    cout << dfs(0,0,0,0) << endl;
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) = abc155e()

fun abc155e() {
    val s = '0' + readLine()!!
    val n = s.length

    val dp = Array(n + 1) { LongArray(2) { Long.MAX_VALUE / 1000 } }
    dp[0][0] = 0

    for (i in 0 until n) {
        for (j in 0..1) {
            val d = s[n - i - 1] - '0' + j
            for (nd in 0..9) {
                val ni = i + 1
                val change = nd - d
                val nj = if (change < 0) 1 else 0
                val b = (change + 10) % 10

                dp[ni][nj] = Math.min(dp[ni][nj], dp[i][j] + nd + b)
            }
        }
    }

    val answer = dp[n][0]

    println(answer)
}


Measured memory_bytes: 102916
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <set>
#include <functional>
#include <map>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <climits>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define show(x) cout << #x << " = " << x << endl;
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    ll n,a,b;
    cin >> n >> a >> b;
    vector<int>x(n);
    ll ans = 0;
    rep(i,n){
        cin >> x[i];
    }
    rep(i,n-1){
        ans+=min((x[i+1]-x[i])*a,b);
    }
    cout << ans << endl;
}

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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second

Int INF = 1e18;
Int mod = 1e9+7;

int main() {
    Int n;
    cin >> n;
    Int cnt = 0;
    for (Int i = 1; i <= n; i++) {
        if (i < n - i) {
            cnt++;
        }
    }
    dump(cnt);
    return 0;

}

Measured memory_bytes: 256
while True:

    inputCount = int(input())

    if inputCount == 0:
        break

    timeList = []

    for lp in range(inputCount):
        timeList.append(int(input()))

    timeList.sort()

    totalTimeList = [0]

    for lp in range(inputCount - 1):
        waitTime = totalTimeList[-1] + timeList[lp]
        totalTimeList.append(waitTime)

    print(str(sum(totalTimeList)))



Measured memory_bytes: 6112
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 int mod=1000000007;
const int INF=1001001001;

int main() {
  int N;
  cin>>N;
  string s,t;
  cin>>s>>t;
  for(int i=N;i>=0;i--){
    string v=s;
    reverse(v.begin(),v.end());
    string r=v.substr(0,i);
    reverse(r.begin(),r.end());
    if(r==t.substr(0,i)){cout<<2*N-i<<endl;return 0;}
  }
  cout<<2*N<<endl;
  
  return 0;  
}

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

typedef long long ll;

int main() {
    int X;
    cin >> X;
    for (int i = 1; i <= 360; i++) {
        if ((X * i) % 360 == 0) {
            cout << i << "\n";
            return 0;
        }
    }
}

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

int main () {
  string S ;
  cin >> S ;
  
  string divide[4] = {"dream","dreamer","erase","eraser"} ;
  
  reverse(S.begin(),S.end()) ;
  
  bool can = true ;
  for(int i = 0 ; i < 4 ;i++) {
    reverse(divide[i].begin(),divide[i].end()) ;
  }
  for(int i = 0 ; i < S.size() ;) {
    bool can2 = false ;
    for(int j = 0 ; j < 4 ; j++ ){
      string d = divide[j] ;
      if(S.substr(i,d.size()) == d){can2 = true ;i += d.size() ;}
    }
      if(!can2) {can = false ;break ;}
  }
  if(can) cout << "YES" << endl ;
  else cout << "NO" << endl ;
}


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

int main(){
  int N;
  string S;
  cin >>N>>S;
  
  string ans;
  rep(i,S.length()){
    if(S.at(i)+N>'Z') ans += S.at(i) + N - 26;
    else ans += S.at(i) + N;
  }
  cout << ans<< endl;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;

int main(){
    string s, t;
    cin >> s >> t;
    bool flag = false;

    for (int i = s.size() - t.size(); i >= 0; --i) {
        int cnt = 0;
        for (int j = 0; j < t.size(); ++j) {
            if(s[i+j] == '?' || s[i+j] == t[j]) cnt++;
            else  break;
        }
        if(cnt == t.size()){
            for (int j = 0; j < t.size(); ++j) {
                s[i+j] = t[j];
            }
            for (int j = 0; j < s.size(); ++j) {
                if(s[j] == '?') s[j] = 'a';
            }
            flag = true;
            break;
        }
    }

    if(flag) cout << s << endl;
    else cout << "UNRESTORABLE" << endl;
}

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

using namespace std;
#define ll long long

const double pi = 3.141592653589793238;

int main()
{

    int n,m;
    cin>>n>>m;

    vector<vector<int>> graph(n+1);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> parent(n+1);
    vector<bool> isVisited(n+1, false);

    queue<int> dq;
    dq.push(1);
    
    int count = 0;

    while(dq.size() >0)
    {
        int val = dq.front();
        dq.pop();
        count++;
        isVisited[val] = true;

        for(int i=0;i<graph[val].size();i++)
        {
            int src = graph[val][i];
            if(!isVisited[src])
            {
                isVisited[src] = true;
                parent[src] = val;
                dq.push(src);
            }
        }
    }

    if(count < n)
    {
        cout<<"No"<<endl;
    }
    else
    {
        cout<<"Yes"<<endl;
        for(int i=2;i<parent.size();i++)
            cout<<parent[i]<<endl;
    }

    return 0;
}


Measured memory_bytes: 10116
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'
#define eb emplace_back
#define fst first
#define scd second
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

constexpr int mod = 1000000007;

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

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

// value
int N, K;
int a[100010], b[100010];
ll fact[100010], fact_inv[100010];
vii g;
bool err = false;

// 逆元を求める
long long mod_inv(long long value) {

	long long b = mod, u = 1, v = 0;

	while (b) {
		long long t = value / b;
		value -= t * b;
		swap(value, b);
		u -= t * v;
		swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;

	return u;
}

ll f(ll n){
  fact[0] = 1; fact_inv[0] = 1;
  if (fact[n] != 0) return fact[n];
  fact[n] = n * f(n - 1) % mod;
  return fact[n];
}

ll fi(ll n){
  if (fact_inv[n] != 0) return fact_inv[n];
  fact_inv[n] = mod_inv(f(n));
  return fact_inv[n];
}

ll nPr(int n, int r) {
	if (n < r) {
		cout << 0 << endl;
		exit(0);
	}
	return f(n) * fi(n - r) % mod;
}

ll ans;

void dfs(int n, int p, int rank) {
	if (err) return;
	if (g[n].size() == 1 && p != -1) return;
	ans *= nPr(K - min(2, rank + 1), g[n].size() + (p == -1 ? 0 : -1));
	ans %= mod;
	for (int i = 0; i < g[n].size(); i++) {
		if (g[n][i] == p) continue;
		dfs(g[n][i], n, rank + 1);
	}
	return;
}

void solve() {

	cin >> N >> K;
	g.resize(N);
	for (int i = 0; i < N - 1; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		g[a[i]].eb(b[i]);
		g[b[i]].eb(a[i]);
	}

	ans = K;
	dfs(0, -1, 0);
	if (err) {
		cout << 0 << endl;
	}cout << ans << endl;

	return;

}

int main() {

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

	solve();

	return 0;

}

Measured memory_bytes: 9984
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val tetra = Array(180, { 0 })
    var (_i, _n) = Pair(1, 1)
    while (_n < 1000000) {
        tetra[_i-1] = _n
        _n = ++_i*(_i+1)*(_i+2)/6
    }
    val tetra_odd = Array(45, { 0 })
    var (__i, __j, __n) = arrayOf(1, 0, 1)
    while (__n < 1000000) {
        if (__n.and(1) == 1) {
            tetra_odd[__j] = __n
            __j++
        }
        __n = ++__i*(__i+1)*(__i+2) / 6
    }
    val dp = IntArray(1000001)

    while (true) {
        val N = sc.nextInt()
        if (N == 0) break
        dp.fill(1000000, 1)
        dp[0] = 0
        for (n in tetra) {
            if (n > N) break
            for (i in n..N) {
                dp[i] = Math.min(dp[i], dp[i-n] + 1)
            }
        }
        val ans = dp[N]
        dp.fill( 1000000, 1)
        for (n in tetra_odd) {
            for (i in n..N) {
                dp[i] = Math.min(dp[i], dp[i-n]+1)
            }
        }
        println("${ans} ${dp[N]}")
    }
}


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

void solve(vector<string> &yard,char key,int x,int y){
    yard[y][x]='.';
    //cout<<y<<","<<x<<endl;
    if(yard[y+1][x]==key){
        solve(yard,key,x,y+1);
    }
    if(yard[y-1][x]==key){
        solve(yard,key,x,y-1);
    }
    if(yard[y][x+1]==key){
        solve(yard,key,x+1,y);
    }
    if(yard[y][x-1]==key){
        solve(yard,key,x-1,y);
    }
    return;
}

int main(void){
    // Your code here!
    int h,w;
    cin>>h>>w;
    while(1){
        int num=0;
        if(h==0&&w==0) break;
        vector<string> yard(h+2,string(w+2,'.'));
        for(int i=1;i<=h;i++){
            cin>>yard[i];
            yard[i]="."+yard[i]+".";
        }
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++){
                if(yard[i][j]!='.'){
                    char key=yard[i][j];
                    solve(yard,key,j,i);
                    num++;
                }
            }
        }
        cout<<num<<endl;
        cin>>h>>w;
    }
    
    
}

Measured memory_bytes: 3884
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;
 
// 32 mil = ~1 sec 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;

int main ()
{
  prep();
  long long h;
  cin >> h;
  long long many = 1;
  long long times = 0;
  while (h > 0){
      h /= 2;
      times += many;
      many *= 2;
  }
  cout << times;
  return 0; 
}


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

int main () {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x, y, ans = 0;
  cin >> x >> y;
  ans += (x<4?(4-x)*100000:0) + (y<4?(4-y)*100000:0);
  if (x == 1 && y == 1) ans += 400000;
  cout << ans << endl;
}

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

using namespace std;
const int maxn = 1e5+100;
const int INF = 0x3f3f3f3f;
vector<int> e[maxn];
int dp[maxn];
int DP(int i){
    if(dp[i]>0) return dp[i];
    dp[i]=0;
    for(int j=0;j<e[i].size();j++){
        dp[i]=max(dp[i],DP(e[i][j])+1);
    }
    return dp[i];
}
int main(){
    int n,m,u,v;
    cin>>n>>m;
    for(int i=1;i<=n;i++) dp[i]=-INF;
    for(int i=1;i<=m;i++){
        cin>>u>>v;e[u].push_back(v);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,DP(i));
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8192
import java.util.Scanner;

class Main{




	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		
		int h = sc.nextInt();
		int w = sc.nextInt();
		
		for(int i = 0;i < h;i++){
			String string = sc.next();
			System.out.println(string);
			System.out.println(string);
			
		}

	}
}

class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}




Measured memory_bytes: 23124
import java.util.Scanner
class ModInt {
	var v: Long
		private set
	constructor(v: Int){
		this.v = when {
			v>=0 -> v.toLong() % MOD
			v==Int.MIN_VALUE -> 852516373
			else -> MOD.toLong() - (-v%MOD)
		}
	}
	constructor(v: Long){
		this.v = when {
			v>=0 -> v % MOD
			v==Long.MIN_VALUE -> 708828003
			else -> MOD - (-v%MOD)
		}
	}

	override fun toString() = v.toString()
	fun toInt() = v.toInt()
	fun toLong() = v
	override fun equals(other: Any?): Boolean {
		return if (other is ModInt) v == other.v else false
	}
	override fun hashCode() = 31*17 + v.hashCode()

	operator fun unaryPlus() = this
	operator fun unaryMinus() = ModInt(MOD-this.v)

	private operator fun plus(o: Long) = ModInt(this.v + o)
	operator fun plus(o: ModInt) = this.plus(o.v)
	operator fun plus(o: Int) = this.plus(o.toLong())
	private operator fun minus(o: Long) = this.plus(-o)
	operator fun minus(o: ModInt) = this.minus(o.v)
	operator fun minus(o: Int) = this.minus(o.toLong())
	private operator fun times(o: Long) = ModInt(this.v*o)
	operator fun times(o: ModInt) = this.times(o.v)
	operator fun times(o: Int) = this.times(o.toLong())
	private operator fun div(o: Long) = this.times(pow(o, MOD-2))
	operator fun div(o: ModInt) = this.div(o.v)
	operator fun div(o: Int) = this.div(o.toLong())

	operator fun inc() = this.plus(1)
	operator fun dec() = this.minus(1)

	companion object{
		const val MOD = 1000000007

		private fun pow(b:Long, e: Int): ModInt{
			if (b==1L) return ModInt(1)
			var ans = 1L
			var b = b; var e = e
			while (e!=0){
				if (e%2==1) ans = (ans*b)%MOD
				b = (b*b)%MOD
				e /= 2
			}
			return ModInt(ans)
		}
		fun pow(b: Int, e: Int): ModInt = pow(b.toLong(), e)
		fun pow(b: ModInt, e: Int): ModInt = pow(b.v, e)
	}
}

fun main(args: Array<String>) {
	val scn = Scanner(System.`in`)
	val r1 = scn.nextInt()
	val c1 = scn.nextInt()
	val r2 = scn.nextInt()
	val c2 = scn.nextInt()

	val frac = mutableListOf(ModInt(1))
	repeat(r2+c2+2){frac.add(frac.last()*(it+1))}
	var ans = frac[r2+c2+2]/(frac[r2+1]*frac[c2+1])
	ans -= frac[r1+c2+1]/(frac[r1]*frac[c2+1])
	ans -= frac[r2+c1+1]/(frac[r2+1]*frac[c1])
	ans += frac[r1+c1]/(frac[r1]*frac[c1])
	print(ans)
}

Measured memory_bytes: 109344
#include<stdio.h>
#define L 2000

int main(){

  int n,i,j,k,pk,lk,rk,h,id;
 int A[250];
  scanf("%d",&h);

  for(i=1;i<h+1;i++){
    scanf("%d",&A[i]);

  }
  for(i=1;i<h+1;i++){
    id = i;
    pk = i/2;
    lk = 2*i;
    rk = 2*i+1;
    
    if(i==1){
      if(h>=3) printf("node %d: key = %d, left key = %d, right key = %d, \n",id,A[i],A[2],A[3]);
      if(h==2)  printf("node %d: key = %d, left key = %d, \n",id,A[i],A[2]);
      if(h==1) printf("node %d: key = %d, \n",id,A[i]);
    }
    if(i==1)continue;
    
    printf("node %d: key = %d, parent key = %d, ",id,A[i],A[pk]);
      
    if(lk<=h&&rk<=h){
      printf("left key = %d, right key = %d, ",A[lk],A[rk]);
    }
    else if(lk<=h&&rk>h) printf("left key = %d, ",A[lk]);

    if(i!=h+1)printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2056
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,Col,a[N][N];
int main()
{
	scanf("%d",&Col);
	if (Col==1){
		printf("1\n1\n");
		return 0;
	}
	if (Col%4==0) m=Col/4;else m=Col/4+1;
	n=2*m;
	for (int i=0;i<n;i++)
	  for (int j=0;j<n;j++)
	  {
	  	  a[i][j]=(i+j)%n;
	  	  if (i&1) a[i][j]+=n;
	  }
	for (int T=2*n-1;T>=Col;T--)
	{
		for (int i=0;i<n;i++)
		  for (int j=0;j<n;j++)
		    if (a[i][j]==T) a[i][j]-=n;
	}
	printf("%d\n",n);
	for (int i=0;i<n;i++)
	  for (int j=0;j<n;j++)
	    printf("%d%c",a[i][j]+1,j==n-1?10:32);
	return 0;
}

Measured memory_bytes: 2176
#include<stdio.h>

int main(void){

int a,b,d=0,r=0;

double f=0.0;

scanf("%d",&a);

scanf("%d",&b);

d=a/b;

r=a%b;

f=(double)a/(double)b;

printf("%d %d %.5lf",d,r,f);

return 0;

}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main() {
    ll N,W;
    cin>>N>>W;
    vector<ll>w(W);
    vector<ll>v(W);
    for(int i=0;i<N;i++){
        ll a,b;
        cin>>a>>b;
        w.at(i)=a;
        v.at(i)=b;
    }
    vector<vector<ll> >dp(N+1,vector<ll>(W+1));

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

    return 0;
}


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

struct node
{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;

Node root, NIL;

int maxh;

void insert(int k)
{
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  for(;x!=NIL;)
    {
      y=x;
      if(z->key < x->key)
	{
	  x=x->left;
	}
      else
	{
	  x=x->right;
	}
    }
  z->parent = y;
  if(y==NIL)
    {
      root=z;
    }
  else
    {
      if(z->key < y->key)
	{
	  y->left=z;
	}
      else
	{
	  y->right = z;
	}
    }
}

void inorder(Node u)
{
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node u)
{
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main()
{
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  maxh=0;
  i=0;
  while(i < n)
    {
      i++;
    scanf("%s", com);
    if (strcmp(com, "insert")==0)
      {
      scanf("%d", &x);
      insert(x);
    }
    else if(strcmp(com, "print")==0)
      {
	inorder(root);
        printf("\n");
	preorder(root);
	printf("\n");
    }
  }

  return 0;
}



Measured memory_bytes: 25296