akhauriyash/Code-Regression huggingface dataset:
//abc162_e.cpp
//Sun Apr 12 20:58:02 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

using namespace std;
using ll=long long;
typedef pair<int,int> P;

ll mod_pow(ll x, ll n, ll mod){
	if (n==0){
		return 1;
	}
	ll res = mod_pow(x*x%mod,n/2,mod);
	if (n&1){
		res = res * x % mod; //nが奇数の場合はxを余分にかける。
	}
	return res;
}

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

	ll njou[100010];
	njou[0] = 0;
	for (int i=1;i<100010;i++){
		njou[i] = mod_pow(i,n,MOD);
	}

	ll ans = njou[k];
	ll counted = 0;
	ll counts[100010];
	fill(counts,counts+100010,0);
	for (int i=k;i>=2;i--){
		ll yakusu = k/i;
		ll tmp = njou[yakusu];
		if (yakusu>=2){
			for (int j=2;j<=yakusu;j++){
				tmp = ((tmp-counts[i*j])%MOD+MOD)%MOD;
			}
		}
		ll tmp2 = (tmp * (i-1)) % MOD;
		ans = (ans+tmp2)%MOD;
		counted = (counted+tmp)%MOD;
		counts[i]=tmp;
	}

	cout << ans << endl;
//	ll modify = ((njou[k]-counted)%MOD+MOD)%MOD;
//	ans = (ans + modify)%MOD;
//	cout << njou[k] << endl;
//	cout << modify << endl;
//	cout << ans << endl;
}

Measured memory_bytes: 5200
#include<bits/stdc++.h>
using namespace std;
 
#define NL '\n'
#define xx first
#define yy second
#define ll long long
#define mp make_pair
#define pb push_back
#define sz(x) x.size()
#define all(x) (x).begin(), (x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define async() ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 
#define FayeValentine 
void dz(){cerr<<NL;}template<typename H,typename... T> void dz(H h,T... t){cerr<<' '<<h;dz(t... );}
#ifdef  FayeValentine
#define debug(...) cerr<<"("<<#__VA_ARGS__<<"):",dz(__VA_ARGS__)
#else
#define debug(...) 
#endif

void absinthe() {
	int n, k; cin >> n >> k;
	ll sum = 0;
	for(ll i = k+1; i <= n; i++) {
		ll el = (i-k), d = n/i;
		ll cur_sum = el*d;
		if(n%i!=0) {
			ll ex = n-(d*i);
			if(ex >= k) cur_sum += (ex - k + 1);
			if(k == 0) cur_sum--;	
		}
		sum += cur_sum;
	}
	cout << sum << NL;

}
 
int main(){
  async();
  int __t = 1, __c; //cin >> __t;
  for(__c = 1; __c <=__t; __c++) {
    //cout << "Case " << __c << ": "; 
    absinthe();
  }
}  


Measured memory_bytes: 256
fun main(args: Array<String>) {
    tenka1_2017b()
}

fun tenka1_2017b() {
    val n = readLine()!!.toInt()
    val abList = (1..n).map { readLine()!!.split(' ').map { it.toLong() } }

    val last = abList.maxBy { it[0] }!!

    val answer = last[0] + last[1]

    println(answer)
}


Measured memory_bytes: 64252
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>

using namespace std;

#define int long long
#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}

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

signed main()
{
	int n; cin >> n;
	int ans = 0;
	rep(i, n) ans = gcd(read(), ans);

	cout << ans << endl;
}




Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define INF 1e6
using namespace std;

int main(){
	int n,hh[2],mm[2],ss[2];
	while(cin>>n,n){
		int time[86500];
		rep(i,86500)time[i]=0;
		rep(i,n){
			scanf("%d:%d:%d",&hh[0],&mm[0],&ss[0]);
			scanf("%d:%d:%d",&hh[1],&mm[1],&ss[1]);
			time[hh[0]*3600+mm[0]*60+ss[0]]++;
			time[hh[1]*3600+mm[1]*60+ss[1]]--;	
		}
		rep(i,86490){
			time[i+1]+=time[i];
		}
		int inf=0;
		rep(i,86500){
			if(time[i]==0)continue;
			else if(inf<time[i]){
				inf=time[i];
			}
		}
		cout<<inf<<endl;
	}
	return 0;
}

Measured memory_bytes: 3420
fun main(args: Array<String>) {
    val s = readLine()!!

    s.forEachIndexed { i, v ->
        if ((i % 2 == 0 && v == 'L') 
            || (i % 2 == 1 && v == 'R')) {
                println("No")
                return
        }
    }

    println("Yes")
}

Measured memory_bytes: 33740
import math
N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]

x = A-B

def func(cnt):
    dmg = B*cnt
    tmp = [max(0, val-dmg) for val in h]
    cnt2 = sum([math.ceil(val/x) for val in tmp])
    if cnt2 > cnt:
        return False
    else:
        return True

ok = 10**9 # exist
ng = 0 # not exist
while abs(ok-ng) > 1:
    cnt = (ok + ng) // 2
    if func(cnt):
        ok = cnt
    else:
        ng = cnt
print(ok)

Measured memory_bytes: 15048
import java.util.Scanner;
class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int M=sc.nextInt();
		int[] kosu=new int[100001];
		long[][] aa=new long[M][3];
		for(int i=0; i<=100000; i++) {
			kosu[i]=0;
		}
		for(int i=0; i<M; i++) {
			long a=sc.nextLong();
			long b=sc.nextLong();
			kosu[(int)a]++;
			aa[i][0]=a*10000000000L+b;
			aa[i][1]=i;
		}
		for(int i=1; i<=100000; i++) {
			kosu[i]=kosu[i-1]+kosu[i];
		}
		quick_sort(aa,0,M-1);
		for(int i=0; i<M; i++) {
			aa[i][2]=i+1;
		}
		long[][] ansss=new long[M+1][2];
		for(int i=0; i<M; i++) {
			ansss[(int)aa[i][1]][0]=aa[i][0];
			long ban=aa[i][0]/10000000000L;
			ansss[(int)aa[i][1]][1]=aa[i][2]-kosu[(int)ban-1];
		}
		String unti="";
		String buri="";
		for(int i=0; i<M; i++) {
			long aaaa=ansss[i][0]/10000000000L;
			unti=String.format("%06d", (int)(aaaa));
			buri=String.format("%06d", (int)(ansss[i][1]));
			System.out.println(unti+buri);
		}
	}
	static void quick_sort(long[][] d, int left, int right) {
		if (left>=right) {
			return;
		}
		long p = d[(left+right)/2][0];
		int l = left, r = right;
		long tmp,tmp1,tmp2;
		while(l<=r) {
			while(d[l][0] < p) { l++; }
			while(d[r][0] > p) { r--; }
			if (l<=r) {
				tmp = d[l][0]; d[l][0] = d[r][0]; d[r][0] = tmp;
				tmp1=d[l][1]; tmp2=d[r][1]; d[l][1]=tmp2; d[r][1]=tmp1;
				l++; r--;
			}
		}
		quick_sort(d, left, r);
		quick_sort(d, l, right);
	}
}


Measured memory_bytes: 169468
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define repi(i, x) for (auto i = (x).begin(), i##_fin = (x).end(); i != i##_fin; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a) ? "Yes" : "No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int, int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long, long long> P;
typedef vector<P> VP;
template <class T>
inline bool chmax(T &a, T b)
{
	if (a < b)
	{
		a = b;
		return 1;
	}
	return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
	if (a > b)
	{
		a = b;
		return 1;
	}
	return 0;
}
const long long INFLL = 1LL << 60;
const int INF = 1 << 30;
const double PI = acos(-1);
int main()
{
	int n, m;
	ll k;
	int ans = 0;
	cin >> n >> m >> k;
	V a(n);
	V b(m);
	V suma(n + 1, 0LL);
	V sumb(m + 1, 0LL);
	rep(i, n)
	{
		cin >> a[i];
		suma[i + 1] += a[i];
		suma[i + 1] += suma[i];
		//clog<<suma[i+1]<<" ";
	}
	//clog<<endl;
	rep(i, m)
	{
		cin >> b[i];
		sumb[i + 1] += b[i];
		sumb[i + 1] += sumb[i];
		//	clog<<sumb[i+1]<<" ";
	}
	auto ter=b.begin();
	int legth=0;
	//clog<<endl;
	rep(i, n + 1)
	{
		if (suma[i] > k)
			continue;
		ter = upper_bound(all(sumb), k - suma[i]);
		legth = (ter - sumb.begin());
			chmax(ans, legth+i - 1);

		//clog << ans << " " << *(upper_bound(all(sumb), k - suma[i])--) << endl;
	}
	cout << ans << endl;
}


Measured memory_bytes: 9588
#include<bits/stdc++.h>
using namespace std;
int n,m,a,x,y,maxx=-2147483640,miny=2147483647,ans;
int main()
{
	scanf("%d%d%d%d",&n,&m,&x,&y);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		maxx=max(a,maxx);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a);
		miny=min(a,miny);
	}
	for(int i=maxx+1;i<=miny;i++)
	{
		if(i>x&&i<=y)
		{
			puts("No War");
			return 0; 
		}
	}
	puts("War");
	return 0; 
}

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

long long n,ans;

int main()
{
	scanf("%lld",&n);
	if(n%2) {
		printf("0");
		return 0;
	}
	n/=2;
	while(n) {
		ans+=n/5;
		n/=5;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 256
from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

ctr = defaultdict(list)
for i, s in enumerate(S):
    ctr[s].append(i)

i = -1
cnt = 0
flag = False
for t in T:
    if t not in ctr:
        flag = True
        break

    j = bisect_right(ctr[t], i)
    if j == len(ctr[t]):
        idx = ctr[t][0]
    else:
        idx = ctr[t][j]

    if i >= idx:
        cnt += 1
    i = idx

if flag:
    print(-1)
else:
    print(cnt * len(S) + i + 1)


Measured memory_bytes: 80204
N=int(input())
*A,=map(int,input().split())
Q=int(input())
*M,=map(int,input().split())
mf=['no']*Q
t=[]
for i in range(0,2**N):
    ans=0
    for j in range(N):
        if (i>>j&1):
            ans+=A[j]
    t.append(ans)
tset=set(t)

for i in range(Q):
    if M[i] in tset:
        mf[i] = 'yes'

for i in mf:
    print(i)


Measured memory_bytes: 43076
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        bool[] b = new bool[100000];
        int N = int.Parse(Console.ReadLine());
        int n = N;
        List<int> p = new List<int>();
        for(int i=2;i<100000;i++){
            if(!b[i]){
                for(int j=i;j<100000;j+=i){
                    b[j] = true;
                }
                if(n % i == 0){
                    p.Add(i);
                }
                while(n % i == 0){
                    n /= i;
                }
            }
        }
        if(n != 1){
            p.Add(n);
        }
        int C = p.Count;
        long count = 0;
        for(int i=0;i<1<<C;i++){
            int c = 0;
            int num = 1;
            for(int j=0;j<C;j++){
                if((i & (1 << j)) != 0){
                    c++;
                    num *= p[j];
                }
            }
            if(c % 2 == 0){
                count += N/num; 
            }
            else{
                count -= N/num;
            }
        }
        sb.Append(count+"\n");
    }
}

Measured memory_bytes: 9312
*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+2) for i in range(LS+2)]
for i in range(LS-1, -1, -1):
    X = dp[i]; Y = dp[i+1]; si = S[i]
    r = X[LT]
    for j in range(LT-1, -1, -1):
        X[j] = r = max(Y[j+1] + 1, Y[j], r) if si == T[j] else max(Y[j], r)
i = j = 0
ans = []
X = dp[0]; Y = dp[1]
while i < LS and j < LT:
    if S[i] == T[j] and X[j] == Y[j+1] + 1:
        ans.append(S[i])
        i += 1; j += 1
        X = Y; Y = dp[i+1]
    elif X[j] == Y[j]:
        i += 1
        X = Y; Y = dp[i+1]
    else:
        j += 1
print(*map(chr, ans), sep='')

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

using namespace std;

typedef pair<int, int> p;
typedef long long ll;
const int inf = 1000000007;

ll gcd(ll x, ll y) {
  return (x % y) ? gcd(y, x % y) : y;
}

ll lcm(ll x, ll y) {
  return x / gcd(x, y) * y;
}

int main() {
  int n;
  cin >> n;
  ll pre;
  cin >> pre;
  for (int i = 1; i < n; i++) {
    ll tmp;
    cin >> tmp;
    pre = lcm(pre, tmp);
  }
  cout << pre << endl;
  return 0;
}

Measured memory_bytes: 3528
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",n*n);
}

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

#define rep(i, n) for(int i = 0; i < n; ++i)
#define abrep(i, a, b) for(int i = a; i < b; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define abrrep(i, a, b) for(int i = b-1; i >= a; --i)
typedef long long ll;


int main(){
  	string s1, s2;
  	cin>>s1>>s2;
  	int ls1,ls2;
  	ls1 = s1.length();
  	ls2 = s2.length();
  	int dp[ls1][ls2];
  	char p[ls1][ls2];
  	rep(i, ls1)
      rep(j, ls2){
      	dp[i][j] = 0;
  		p[i][j] = 'c';
      }
  	int idx;
  	idx = s1.find(s2.front(), 0);
  	if(idx != string::npos)
  		abrep(i, idx, ls1)
      		dp[i][0] = 1;
  	idx = s2.find(s1.front(), 0);
  	if(idx != string::npos)
  		abrep(i, idx, ls2)
      		dp[0][i] = 1;
  	abrep(i, 1, ls1)
      abrep(j, 1, ls2){
    	if(s1.at(i) == s2.at(j)){
          	dp[i][j] = dp[i-1][j-1] + 1;
      		p[i][j] = 'c';
        }
      	else{
          	dp[i][j] = dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
      		p[i][j] = dp[i-1][j]>dp[i][j-1]?'l':'u';
        }
    }
  	char s[dp[ls1-1][ls2-1]];
	int i = dp[ls1-1][ls2-1] - 1;
  	int ax = ls1 - 1, ay = ls2 - 1;
  	while(i>=0){
      	while(p[ax][ay] != 'c'){
        	if(p[ax][ay] == 'l'){
              ax -= 1;
            }
          	else{
              ay -= 1;
            }
        }
      	if(ax != 0)
      		s[i] = s2.at(ay);
      	else
      		s[i] = s1.at(0);
      	--i;--ax;--ay;
    }
	rep(i, dp[ls1-1][ls2-1])
      	cout<<s[i];
  	return 0;
}


Measured memory_bytes: 44160
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ph push
#define ptc putchar
#define enter putchar('\n')
#define mod 1000000007
using namespace std;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef long long lnt;
inline int read(){
	int x = 0;char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 1) + (x << 3) + c - '0' , c = getchar();
	return x;
}
inline void write(int x){
	if (!x){
       ptc('0');
       return;
	}
	int dg[20] , len = 0;
	while (x) dg[len++] = x % 10 , x /= 10;
	while (len--) ptc(dg[len]+'0');
}
inline void writeln(int x){
	write(x);
	ptc('\n');
}

const int N = 1e5 + 10;

char s[N];
int n , cnt[26];
int main(){
	scanf("%d",&n);
	scanf("%s",s + 1);
	for (int i = 1;i <= n;i++){
		cnt[s[i]-'a']++;
	}
	int answer = 1;
	for (int i = 0;i < 26;i++) answer = 1ll * answer * (cnt[i] + 1) % mod;
	answer--;if (answer == -1) answer += mod;
	cout<<answer<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define fastio   ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll        long long
#define yes       printf("YES\n")
#define no        printf("NO\n")
#define pb        push_back
#define srtd(x)   sort(x.begin(),x.end())
#define rvsd(x)   reverse(x.begin(),x.end())
#define scn(n)    scanf("%lld",&n)
#define scab(a,b) scanf("%lld %lld",&a,&b)
#define pn(n)     printf("%lld\n",n)
#define pab(a,b)  printf("%lld %lld",a,b)
#define nl        cout<<endl
#define MAX       1000011
#define PI        acos(-1.0)
#define mmst(a,b) memset(a,b,sizeof(a));
#define FOR(i,n)  for(ll i=1;i<=n;i++)
#define LOP(i,n)  for(ll i=0;i<n;i++)
//Emama_ Nahid//
using namespace std;
int main()
{
    fastio;
    ll n,m,i,j,k;
    ll a,b;
    cin>>n>>m>>k;
    i=k-n;
    if(i>0)
    {
        a=0;
        b=m-i;
        b= max(b,a);
    }
    else
    {
        a=-1*i;
        b=m;
    }
    cout<<a<<" "<<b<<endl;



    return 0;

}






Measured memory_bytes: 256
#include <bits/stdc++.h>
// const std::string ans[2] = {"No\n", "Yes\n"};

int main() {
    using namespace std;
    long long x;
    cin >> x;
    long long ans = (x / 500LL) * 1000;
    ans += ((x % 500LL) / 5LL) * 5;
    cout << ans << endl;
    return 0;
}

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

int n;
#define maxn 500011
char s[maxn];
int f[maxn][3],inf=0x3f3f3f3f;
int suml[maxn],sumr[maxn];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	f[1][1]=f[2][1]=-inf;
	f[1][0]=f[2][0]=0;
	int one=0,cnt=0;
	for (int i=1;i<=n;i++)
	{
		if (s[i]=='1') one++;
		else cnt++,suml[i]=one,one=0;
	}
	one=0;
	for (int i=n,tot=cnt;i>=1;i--)
	{
		if (s[i]=='1') one++;
		else sumr[i]=one,one=0,tot--;
	}
	f[0][0]=0;f[0][1]=f[0][2]=-inf;
	int last=0,ans=0;
	for (int i=1;i<=n;i++) if (s[i]=='0')
	{
		f[i][0]=max(f[last][0],max(f[last][1],f[last][2]));
		f[i][1]=suml[i] && sumr[i]?max(f[last][0]+suml[i],suml[i]>=1?f[last][1]+suml[i]-1:-inf):-inf;
		f[i][2]=suml[i] && sumr[i]?
		max(max(f[last][0]+sumr[i],suml[i]>=2?f[last][1]+sumr[i]:0),suml[i]>=1?f[last][2]+sumr[i]-1:-inf):-inf;
		ans=max(ans,max(f[i][0],max(f[i][1],f[i][2])));
		last=i;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 10496
#include <iostream>

const int get_area_triangle(const int& base, const int& height)
{
  return (base * height) / 2;
}

int main()
{
  int height, base;

  std::cin >> height >> base;
  std::cout << get_area_triangle(base, height) << std::endl;

  return 0;
}

Measured memory_bytes: 256
//By Vlgd
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x;
	node *l,*r,*p;
};
node* root=NULL;
void insert(int x){
	node *n=(node*)malloc(sizeof(node));
	n->x=x;
	n->r=n->l=NULL;
	node *tmp=root,*fa=NULL;
	while(tmp!=NULL){
		fa=tmp;
		if (x<tmp->x) tmp=tmp->l; 
		else tmp=tmp->r;
	}
	n->p=fa;
	if (fa==NULL){
		root=n;
	}
	else{
		if (x<fa->x) fa->l=n;
		else fa->r=n;
	}	
}
bool find(int k){
	node *T=root;
	while (T!=NULL){
		if (k<T->x) T=T->l;
		else if (k>T->x) T=T->r;
		else return true;
	}
	return false;
}
void ino(node *T){
	if (T!=NULL){
		ino(T->l);
		printf(" %d",T->x);
		ino(T->r);
	}
}
void pre(node *T){
	if (T!=NULL){
		printf(" %d",T->x);
		pre(T->l);
		pre(T->r);
	}
}
main(){
	int n,xx;
	string ins;
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		cin>>ins;
		if (ins=="insert"){
			scanf("%d",&xx);
			insert(xx);
		}
		else if (ins=="find"){
			scanf("%d",&xx);
			if (find(xx)) printf("yes\n");
			else printf("no\n");
		}
		else if (ins=="print"){
			ino(root);printf("\n");
			pre(root);printf("\n");
		}
	}
}


Measured memory_bytes: 22032
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        long k = scan.nextLong();

        int[] a = new int[n];
        Arrays.setAll(a, x -> scan.nextInt());

        Map<Integer, Integer> map = new HashMap<>();
        for (int turn = 1, teleport = 0; k >= 0; k--, turn++) {
            if (map.getOrDefault(teleport, 0) > 0) {
                k %= turn - map.get(teleport);
            }

            map.put(teleport, turn);

            if (k == 0) {
                System.out.println(teleport + 1);
                return;
            }

            teleport = a[teleport] - 1;
        }
    }
}


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


int main(){
  int x;
  cin >> x;
  if(x==0)cout<<1;
  else if(x==1)cout<<0;
}


Measured memory_bytes: 3672
import collections

n = int(input())
s = list(sorted(input()) for _ in range(n))

l = []
for li in s:
    st = ''
    for x in li:
        st += x
    l.append(st)

c = collections.Counter(l)

ans = 0
for x in c.values():
    ans += x * (x - 1) // 2

print(ans)


Measured memory_bytes: 45512
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int x;
  cin>>x;
  int ans=0;
  int k=x;
  while(true){
   ans++;
    k+=x;
    if(k%360==0) break;
    
    
  }
  cout<<ans+1<<endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	ll x;cin>>x;
	ll ans=x*2/11;
	if(x*2%11!=0) ans++;
	if(x%11==6) ans--;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 200010
#define pp pair<int,int>
#define P pair<pp,int>
using namespace std;
int a[N],b[N],s[N],tot;
int deg1[N],deg2[N];
int fa[N];
int ans;
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
void merge(int x,int y){
	if(fa[x]==-1)fa[x]=x;
	if(fa[y]==-1)fa[y]=y;
	int g1=Find(x),g2=Find(y);
	if(g1!=g2)fa[g1]=g2;
}
vector<int>q[N];
bool ok[N];
int main(){
	int n,sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum^=a[i],s[++tot]=a[i];
	for(int i=1;i<=n;i++)scanf("%d",&b[i]),s[++tot]=b[i];
	s[++tot]=sum;
	sort(s+1,s+tot+1);
	tot=unique(s+1,s+tot+1)-s-1;
	memset(fa,-1,sizeof fa);
	for(int i=1;i<=n;i++){
		if(a[i]!=b[i]){
			int g1=lower_bound(s+1,s+tot+1,a[i])-s;
			int g2=lower_bound(s+1,s+tot+1,b[i])-s;
			deg1[g2]++,deg2[g1]++;
			merge(g1,g2);
			ans++;
		}
	}
	int gg=lower_bound(s+1,s+tot+1,sum)-s;
	if(fa[gg]==-1)fa[gg]=gg;
	for(int i=1;i<=tot;i++){
//		cout<<"!!"<<i<<" "<<deg1[i]<<" "<<deg2[i]<<endl;
		if(deg1[i]>deg2[i]){
			int r=deg1[i]-deg2[i];
			if(r>=2)return 0*printf("-1\n");
			else {
				if(gg!=i)return 0*printf("-1\n");
			}
		}
	}
	int num=0;
	for(int i=1;i<=tot;i++)if(fa[i]==i&&Find(i)!=Find(gg))num++;
	printf("%d\n",num+ans);
	return 0;
}

Measured memory_bytes: 10368
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
priority_queue<double> pq;
long long n, m, p, ans;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> p; pq.push(p);
	}
	for (int i = 0; i < m; i++) {
		p = pq.top(); pq.pop(); pq.push(p / 2);
	}
	for (int i = 0; i < n; i++) {
		ans += pq.top(); pq.pop();
	}
	cout << ans << endl;
}

Measured memory_bytes: 1528
n=int(input())
arr1=[]
arr2=[]
for _ in range(n):
  s=input()
  cnt1=0
  cnt2=0
  for i in range(len(s)):
    if s[i]=='(':
      cnt1+=1
    else:
      if cnt1==0:
        cnt2+=1
      else:
        cnt1-=1
  if cnt1-cnt2>=0:
    arr1.append([cnt1,cnt2])
  else:
    arr2.append([cnt1,cnt2])
arr1=sorted(arr1,key=lambda x:x[1])
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
arr=arr1+arr2
cnt=0
for a,b in arr:
  if b>cnt:
    print('No')
    break
  else:
    cnt+=a-b
else:
  if cnt==0:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 220548
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}
void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}

int t[3000];

int main(){
	int n,m;
	int i,j,k;
	int a,b,c;
	int x,y;
	cin>>n>>x>>y;
	x--,y--;
	for(i=0;i<n;i++){
		for(j=i+1;j<n;j++){
			a=j-i;
			b=abs(x-i)+1+abs(y-j);
			a=min(a,b);
			t[a]++;
		}
	}
	for(i=1;i<n;i++){
		cout<<t[i]<<endl;
	}
}

Measured memory_bytes: 256
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

class UnionFind:
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rank = [0]*(n+1)

    # ノードxのrootノードを見つける
    def findRoot(self, x):
        if(self.root[x] < 0): # 根
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.findRoot(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.findRoot(x)
        y = self.findRoot(y)
        # すでに同じ木に属していた場合
        if x == y:
            return 
        # 違う木に属していた場合rankを見てくっつける方を決める
        if self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

    # ノードxが属する木のサイズを返す
    def count(self, x):
        return -self.root[self.findRoot(x)]

def main():
    n, m = i_map()

    uf = UnionFind(n)

    for _ in range(m):
        a, b = i_map()
        
        if uf.isSameGroup(a, b):
            continue
        else:
            uf.unite(a, b)

    max_count = 0
    for i in range(n):
        max_count = max(max_count, uf.count(i))

    print(max_count)

if __name__ == '__main__':
    main()


Measured memory_bytes: 84452
import numpy as np
N, K, Q = map(int, input().split())
p = np.array([K - Q] * N)
for i in range(Q):
  A = int(input())
  p[A-1] = p[A-1] + 1
for s in p:
  if s > 0:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 18484
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
using namespace std;
 
#define LOCAL  1
#define UPLOAD 2
 
#define ll long long
const long long INF = 1LL << 60;
 
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define REP(i,M) for(int i=0;i<M;i++)
 
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
 
int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
  
  ll K = input();
  ll A = input();
  ll B = input();

  float f = (float)A / (float)K;
  float f2 = (float)B / (float)K;
  ll answer = ceil(f);

  if(answer <= f2){
    output("OK");
  }
  else{
    output("NG");
  }
  
  return 0;
}

Measured memory_bytes: 3592
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
int dp[5005],maxi=1e18; 
P<int,int> a[5005];
bool cmp(P<int,int> x,P<int,int> y){
	RE x.F+x.S<y.F+y.S;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	FOR(i,1,n)cin>>a[i].F>>a[i].S,dp[i]=maxi;
	sort(a+1,a+n+1,cmp);
	FOR(i,1,n){
		for(int j=n;j>=1;j--){
			if(dp[j-1]<=a[i].F){
				gmin(dp[j],dp[j-1]+a[i].S);
			}
		}
	}
	for(int i=n;i>=0;i--){
		if(dp[i]!=maxi){
			cout<<i<<'\n';RE 0;
		}
	}
	RE 0;
}




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

int main()
{
	int n;
	cin >> n;
	int i = 1;
	CHECK_NUM:
	int x = i;
	if ( x % 3 == 0 ){
    cout << " " << i;
    goto END_CHECK_NUM;
	}
	INCLUDE3:
	if ( x % 10 == 3 ){
    cout << " " << i;
    goto END_CHECK_NUM;
	}
	x /= 10;
	if ( x ) goto INCLUDE3;
	END_CHECK_NUM:
	if ( ++i <= n ) goto CHECK_NUM;
	cout << endl;
}

Measured memory_bytes: 3072
import sys
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    ans_id = [None]*m
    p_count = [0]*(n+1)

    list_ipy = [None]*m
    for i in range(m):
        p, y = map(int, input().split())
        list_ipy[i] = (i, p, y)
    list_ipy.sort(key=lambda x: x[2])

    for ipy in list_ipy:
        i, p, _ = ipy
        p_count[p] += 1
        first = format(p, '06')
        second = format(p_count[p], '06')
        ans_id[i] = first + second

    for id in ans_id:
        print(id)


if __name__ == '__main__':
    main()


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

int main() {
  int n;
  int ans=0;
  cin>>n;
  vector<int>p(n);
  for(int i=0;i<n;i++) cin>>p[i];
  for(int i=1;i<n-1;i++){
    if(p[i-1]>p[i] && p[i]>p[i+1]) ans++;
    else if(p[i-1]<p[i] && p[i]<p[i+1]) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
    }
    if a == b {
        println!("Draw");
    } else if a == 1 {
        println!("Alice");
    } else if b == 1 {
        println!("Bob");
    } else if a > b {
        println!("Alice");
    } else {
        println!("Bob");
    }
} 


Measured memory_bytes: 4352
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
visited = []
tf_visited = [0] * n
pos = 0
count = 0
 
while tf_visited[pos] == 0:
	visited.append(pos)
	tf_visited[pos] = 1
	pos = a[pos]-1
	count += 1
	if count >= k:
		print(pos+1)
		exit()
 
loop_start = visited.index(pos)
loop_length = len(visited)-loop_start
pos_t = (k-loop_start) % loop_length + loop_start
print(visited[pos_t]+1)

Measured memory_bytes: 32356
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
			System.out.println("Possible");
		} else {
			System.out.println("Impossible");
		}

		sc.close();
	}
}

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

int main() {
  int N;
  cin >> N;
  
  if(N%2==0){
  cout << 0.5 << endl;
  }
  
  if(N%2==1){
  cout << double ((N+1)/2)/N << endl;
  }
}

Measured memory_bytes: 256
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	int n;
	
	cin >> n;

	double x[n];
	string u[n];

	double sum = 0.0;

	rep(i, n)
	{
		cin >> x[i] >> u[i];
		if (u[i] == "JPY")
		{
			sum += x[i];
		}
		else
		{
			sum += 380000.0 * x[i];
		}
	}

	cout << sum << endl;
	
	return 0;
}


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

int main() {
	int N,H; cin>>N>>H;
	vector<int> a(N), b(N);
	for(int i=0; i<N; i++)
		cin>>a[i]>>b[i];
	sort(a.rbegin(),a.rend());
	sort(b.rbegin(),b.rend());
	int mx=a[0], ret=0;
	for(int i=0; i<N; i++) 
		if(b[i]>mx&&H>0) H-=b[i], ret++;
	if(H>0) ret+=(H+mx-1)/mx;
	cout<<ret<<"\n";
	return 0;
}

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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int euclid(int a, int b){
  if(a < b){
    int tmp = a;a = b;b = tmp;
  }
  int r = a % b;
  if(r < 0) r += b;
  while(r != 0){
    a = b;b = r;r = a % b;
    if(r < 0) r += b;
  }
  return b;
}

int main(){
  int N,X,d;
  scanf("%d %d",&N,&X);
  int x[N];
  for(int i=0;i<N;i++) scanf("%d",&x[i]);
  d= abs(x[0]-X);
  for(int i=1;i<N;i++){
    d=euclid(d,abs(x[i]-X));
  }
  printf("%d\n",d );
  }


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

using namespace std;

typedef long int lint;
typedef long long int llint;

#define INF 1073741824
#define LINF 4611686018000000000
#define MOD 1000000007

int dfs(set<int> v[], bool vi[], int s) {
    if (v[s].size() == 0) return 1;
    vi[s] = true;
    int cnt = 1;
    for (int a: v[s]) {
        if (!vi[a]) cnt += dfs(v, vi, a);
    }
    return cnt;
}

int main() {
    int n, m;
    cin >> n >> m;
    int a, b;
    set<int> v[n];
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--;
        b--;
        v[a].insert(b);
        v[b].insert(a);
    }
    bool vi[n];
    for (int i = 0; i < n; i++) {
        vi[i] = false;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dfs(v, vi, i));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 41300
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1e6+5 ;
int n, m, a[maxn], dfn[maxn], fa[maxn] ;
int v[maxn], minn[maxn], rt, ch[maxn][2], tot, gn = 0 ;
#define L ch][0
#define R ch][1

void push_up ( int x ) {
	minn[x] = v[x] ;
	if (x[L]) minn[x] = min(minn[x], x[L][minn]) ;
	if (x[R]) minn[x] = min(minn[x], x[R][minn]) ;
}
void Rotate ( int x ) {
	int y = fa[x], z = fa[y], d = y[R]==x, son = ch[x][d^1] ;
	if ( y == rt ) rt = x ;
	else ch[z][z[R]==y] = x ;
	fa[x] = z ;
	fa[y] = x ;
	if (son) fa[son] = y ;
	ch[y][d] = son ;
	ch[x][d^1] = y ;
	push_up(y) ;
	push_up(x) ;
}
void splay ( int x, int tar = 0 ) {
	while ( fa[x] != tar ) {
		int y = fa[x], z = fa[y] ;
		bool dx = x==y[R], dy = y==z[R] ;
		if (z == tar) ;
		else Rotate(dx^dy? x:y) ;
		Rotate(x) ;
	}
	push_up(x) ;
}
int new_node ( int fat, int value ) {
	fa[++tot] = fat ;
	minn[tot] = v[tot] = value ;
	tot[L] = tot[R] = 0 ;
	return tot ;
}
void insert ( int value, int p ) {
	int x = rt ;
	if (!x) {
		rt = new_node(0, value) ;
		return ;
	}
	while (x) {
		if (!x[L]) {
			if ( !x[R]) {
				if ( p > x[v] ) {
					x[R] = new_node(x, value) ;
					splay(x) ;
					return ;
				} else {
					x[L] = new_node(x, value) ;
					splay(x) ;
					return ;
				}
			} else {
				if ( p > x[v] || p > x[R][minn] ) x = x[R] ;
				else {
					x[L] = new_node(x, value) ;
					splay(x) ;
					return ;
				}
			}
			continue ;	
		} else if (!x[R]) {
			if ( p > x[v] ) {
				x[R] = new_node(x, value) ;
				splay(x) ;
				return ;
			} else x = x[L] ;
			continue ;
		}
		if ( x[R][minn] < p || x[v] < p ) x = x[R] ;
		else x = x[L] ;
	}
}
void print ( int x ) {
	if (x[L]) print(x[L]) ;
	a[v[x]] = ++gn ;
	if (x[R]) print(x[R]) ;
}
int main() {
	int i ;
	Read(n) ; Read(m) ;
	for ( i = 1 ; i <= n ; i ++ ) Read(a[i]) ;
	for ( i = 1 ; i <= n ; i ++ ) dfn[a[i]] = i ;
	for ( i = 1 ; i <= n ; i ++ ) insert ( dfn[i], dfn[i]+m ) ;
	gn = 0 ;	
	print(rt) ;	
	for ( i = 1 ; i <= n ; i ++ ) printf ( "%d\n", a[i] ) ;	
	return 0 ;
}

Measured memory_bytes: 35968
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; ++i)
#define rep(i, n) repl(i, 0, n)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define chmax(x,y) x = max(x, y)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using G = vector<vector<int>>;
const int MOD = 1000000007;
const int INF = 1001001001;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, -1, 0, 1};

struct mint {
  ll x;
  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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    vector<int> s, t;
    rep(i, n) {
        cin >> a[i];
        if(a[i] < 0) t.pb(a[i]);
        else s.pb(a[i]);
    }

    int S = s.size();
    int T = t.size();
    bool ok = false;
    if(S > 0) {
        if(n == k) ok = (T%2 == 0);
        else ok = true;
    }
    else {
        ok = (k % 2 == 0);
    }

    mint ans = 1;
    if(!ok) {
        sort(all(a), [](int x, int y) {
            return abs(x) < abs(y);
        });
        rep(i, k) ans *= a[i];
    }
    else {
        sort(all(s));
        sort(rall(t));
        if(k % 2 == 1) {
            ans *= s.back();
            s.pop_back();
        }
        vector<ll> p;
        while(s.size() >= 2) {
            ll x = s.back(); s.pop_back();
            x *= s.back(); s.pop_back();
            p.pb(x);
        }
        while(t.size() >= 2) {
            ll x = t.back(); t.pop_back();
            x *= t.back(); t.pop_back();
            p.pb(x);
        }
        sort(rall(p));
        rep(i, k/2) {
            ans *= p[i];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6404
import java.util.*;

public class Main {

	public static void main(String[] args) {
    	//declare
    	int target,times,start,end;
    	String   ret;
    	
    	//input
    	Scanner sc = new Scanner(System.in);
    	
    	while(true){
    		ret = "";
    		target = sc.nextInt();
    		if(target == 0){break;}
    		times  = sc.nextInt();
    		while(times-- > 0){
    			start = sc.nextInt();
    			end   = sc.nextInt();
    			target -= (end - start);
    		}
    		if   (target <= 0){ret = "OK";}
    		else              {ret = String.valueOf(target);}
    		System.out.println(ret);
    	}
	}
}

Measured memory_bytes: 23584
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<stack>
#include<list>
#include<unordered_map>
#include<unordered_set>
#include<cctype>
#include<iomanip>
#include<limits>
#include<bitset>

using namespace std;
typedef long long int ll; typedef pair<int, int> P; typedef unsigned long long int ull;
const ll mod = 1000000007;
const int inf = 1e9 + 7;
const ll linf = 1LL << 60;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define REP(i,m,n) for(int i=(m);i<(int)n;i++)
#define all(a) (a).begin(),(a).end()
#define allg(a) (a).begin(),(a).end(),greater<>()
#define SUM(a) accumulate((a).begin(),(a).end(),0)
#define d10 std::setprecision(10)
#define d20 std::setprecision(20)
#define vec vector<int>
#define vecb vector<bool>
#define vecd vector<double>
using str = string;
const double PI = 3.14159265359;
template <typename T> 
int len(T tmp){
	int res = 0;
	while(tmp>0){
		res++;
		tmp /= 10;
	}
	return res;
}
template <typename T>
T gcd(T a, T b) {
	T t;
	while (b != 0) {
		t = a % b; a = b; b = t;
	}
	return a;
}
template <typename T>
T recfact(T start, T n) {
	T i;
	if (n <= 16) {
		T r = start;
		for (i = start + 1; i < start + n; i++) r = r * i % mod;
		return r % mod;
	}
	i = n / 2;
	return recfact(start, i) % mod * recfact(start + i, n - i) % mod;
}
template <typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}
template <typename T>
T fct(T n) {
	return recfact<T>(1, n);
}
template <typename T>
T ncm(T n, T m) {
	if (n < m)return 0;
	T x = (fct(n) % mod / (fct(m) * fct(n - m)) % mod) % mod;
	return x;
}
std::string sreverse(string str, int firstItr, int secondItr) {
	if (firstItr < 0 || secondItr>int(str.size() - 1))return str;
	while (firstItr < secondItr) {
		swap(str[firstItr], str[secondItr]);
		firstItr++; secondItr--;
	}
	return str;
}
std::string RunLengthEncoding(std::string str) {
	int itr = 0; std::string res;
	while (itr < int(str.size())) {
		char tmp = str[itr++];
		int length = 1;
		while (itr <int(str.size()) && str[itr] == tmp) { ++itr; ++length; }
		res.push_back(tmp);
		res += to_string(length);
	}
	return res;
}
std::string split(std::string str, size_t first_itr, size_t second_itr) {
	std::string tmp;
	for (size_t i = first_itr; i < second_itr + 1; i++) {
		tmp.push_back(str.at(i));
	}
	return tmp;
}


int main(void)
{
	int n;
	bool ans = true;
	cin >> n;
	vec h(n);
	for (int i = 0; i < n;i++){
		cin >> h[i];
	}
	rep(i,n-1){
		if(h[i]>h[i+1]){
			h[i + 1]++;
			if(h[i]>h[i+1]){
				ans = false;
				break;
			}
		}
	}
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

llong N, K;
vector<vector<llong> > memo;

llong dp(llong now, llong sep) {
	if (now == 0) return memo[now][sep] = sep == 0;
	if (sep == 0) return memo[now][sep] = 0;
	if (memo[now][sep] != -1) return memo[now][sep];

	return memo[now][sep] = (dp(now-1, sep) + dp(now-1, sep-1)) % mod;
}

int main() {
	cin >> N >> K;

	memo.resize(N+1, vector<llong>(K+2, -1));
	for (int i = 0; i <= K+1; ++i)
		dp(N, i);

	for (int i = 1; i <= K; ++i) {
		llong b = memo[K][i];
		llong r = (memo[N-K][i-1] + memo[N-K][i]*2 + memo[N-K][i+1]) % mod;

		cout << b*r%mod << endl;
	}

	return 0;
}


Measured memory_bytes: 31744
#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack> 
#include<vector>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
//const int MAX_V=105;
const long double pi = 3.14159265;
const long long mod =1e9+7;


int main(){
    
    int X,A,B;
    cin >> X >> A >> B;
    X-=A;
    cout << X%B << endl;

    return 0;
}
 

Measured memory_bytes: 256
class Dice
	def initialize(array)
		@data = array
	end
	
	def move(dir)
		case dir.downcase
		when "e"
			tmp=@data[0]
			@data[0]=@data[3]
			@data[3]=@data[5]
			@data[5]=@data[2]
			@data[2]=tmp
		when "n"
			tmp=@data[0]
			@data[0]=@data[1]
			@data[1]=@data[5]
			@data[5]=@data[4]
			@data[4]=tmp
		when "s"
			tmp=@data[0]
			@data[0]=@data[4]
			@data[4]=@data[5]
			@data[5]=@data[1]
			@data[1]=tmp
		when "w"
			tmp=@data[0]
			@data[0]=@data[2]
			@data[2]=@data[5]
			@data[5]=@data[3]
			@data[3]=tmp
		end
	end
	
	def get_top
		return @data[0]
	end
end

array = gets.chomp.split(" ").map(&:to_i)
dice = Dice.new(array)

r = gets.chomp

r.each_char{ |c|
	dice.move(c)
}

puts dice.get_top

Measured memory_bytes: 8672
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int main(){
	int N;
	cin>>N;
	int a=0,b=0,c=0;
	rep(i,N){
		int x;
		cin>>x;
		if(x%4==0) a++;
		else if(x%2==0) b++;
		else c++;
	}
	bool ok = 0;
	if(a>=c){
		ok = 1;
	}
	if(a==c-1 && b==0){
		ok = 1;
	}
	if(ok) puts("Yes");
	else puts("No");
}


Measured memory_bytes: 256