akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

int dp[200005][2];

class ADividingAString {
public:
    static constexpr int kStressIterations = 0;

    static void generateTest(std::ostream& test) {
    }

    void solve(std::istream& cin, std::ostream& cout) {
        CLR(dp, 0);

        string s;
        cin >> s;

        int N = s.size();

        dp[0][0] = 1;
        FOR(i, 1, N - 1) {
            if (s[i] != s[i - 1]) {
                dp[i][0] = dp[i - 1][0] + 1;
            }
            dp[i][0] = max(dp[i][0], dp[i - 1][1] + 1);
            if (i >= 2) {
                dp[i][1] = dp[i - 2][0] + 1;
            }
        }
        cout << max(dp[N - 1][0], dp[N - 1][1]) << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    ADividingAString solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 3920
#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
int main()
{
 ll a,v,b,w,t;
 cin>>a>>v>>b>>w>>t;
 if(a==b)
    cout<<"YES"<<endl;
 else{
 if(w>=v)
    cout<<"NO"<<endl;
 else
 {
     if(abs(a-b)<=(v-w)*t)
        cout<<"YES"<<endl;
     else
        cout<<"NO"<<endl;
 }}
}


Measured memory_bytes: 3652
sentinel = str(10**9+1)

def partition(A, p, r):
    x = int(A[r][1])
    i = p - 1
    for j in range(p, r):
        if int(A[j][1]) <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def merge(lst,left,middle,right):
    left_lst  =  lst[left:middle] + [['',sentinel]]
    right_lst = lst[middle:right] + [['',sentinel]]

    i,j = 0,0
    for k in range(left,right):
        if int(left_lst[i][1]) <= int(right_lst[j][1]):
            lst[k] = left_lst[i]
            i += 1
        else:
            lst[k] = right_lst[j]
            j += 1

def merge_sort(lst,left,right):
    if left+1 < right:
        middle = (left+right)//2
        merge_sort(lst,left,middle)
        merge_sort(lst,middle,right)
        merge(lst,left,middle,right)


n = int(input())
n_lst = [[i for i in input().split()] for _ in range(n)]
m_lst = list(n_lst)
quick_sort(n_lst,0,n-1)
merge_sort(m_lst,0,n)
print('Stable' if n_lst == m_lst else 'Not stable')
for ans in n_lst:
    print('{} {}'.format(ans[0],ans[1]))



Measured memory_bytes: 23292
#include<stdio.h>

int main(){
   int k, a, b;
   scanf("%d", &k);
   scanf("%d %d", &a, &b);

   int judge = 0;
   for(int i=a; i<=b; i++){
      if(i % k == 0){
         judge = 1;
      }
   }

   if(judge == 1){
      printf("OK\n");
   } else {
      printf("NG\n");
   }

   return 0;
}


Measured memory_bytes: 1640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for (int i=0; i<N; ++i) {
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  int a=1;
  for (int i=0; i<N-1; ++i) {
    if (vec.at(i) != vec.at(i+1)) {
      ++a;
    }
  }
  cout << a << endl;
}

Measured memory_bytes: 256
N = gets.to_i
S = gets[0,N]
open = close = 0
S.chars.each{|c|
  if c == ?(
    open += 1
  else
    if open > 0
      open -= 1
    else
      close += 1
    end
  end
}
# p [open, close]
puts ?( * close + S + ?) * open


Measured memory_bytes: 1788
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


K = ni()
S = ns()
if K >= len(S):
    print(S)
else:
    print(S[:K] + "...")


Measured memory_bytes: 61908
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

X,K,D=map(int, input().split())

X = abs(X)

if 0 <= X - K*D:
    print(X-K*D)
else:
    tmp = X%D
    tmp2 = tmp - D
    if (K - (X - tmp)//D)%2 == 0:
        print(abs(tmp))
    else:
        print(abs(tmp2))


Measured memory_bytes: 72900
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

    vector<int> A(N);
    int cntMinus=0;
    int min = 1e9;
    for(int i=0;i<N;i++){
        cin >> A[i];
        if( A[i] <= 0 )  cntMinus++;
        if( abs(A[i]) < abs(min) )  min = A[i];
    }

    long long ans=0;
    for(int i=0;i<N;i++){
        ans += abs(A[i]);
    }
    if( cntMinus % 2 == 1 ){
        ans -= abs(min) * 2;
    }

    cout << ans << endl;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

  int N;
  cin>>N;
  ll ans=0;
  vector<int>A(N+1),B(N);
  for(int i=0;i<=N;i++)cin>>A[i];
  for(int i=0;i<N;i++)cin>>B[i];
  for(int i=0;i<N;i++){
    if(A[i]>=B[i])A[i]-=B[i],ans+=B[i],B[i]=0;
    else B[i]-=A[i],ans+=A[i],A[i]=0,ans+=min(B[i],A[i+1]),A[i+1]-=min(B[i],A[i+1]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<string>
#include<cctype>
#include<cmath>
#include<queue> 
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
 
int main(){
  
  int A,B,C,D,i,ans=102,end=0;
  cin >> A >> B >> C >> D;
  if(D<=A || B<=C){
    cout << 0 << endl;
  }else if(C<=A && A<D && D<=B){
    cout << D-A << endl; 
  }else if(A<=C && C<B && B<=D){
    cout << B-C << endl;
  }else if(A<=C && D<=B){
    cout << D-C << endl;
  }else if(C<=A && B<=D){
    cout << B-A << endl;
  }
  
  return 0;
}
 

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;
const int INF = 1e9;

int main() {
  int n, ans = INF;
  string s;
  cin >> n >> s;
  vector<int> W(n), E(n);

  if (s[0] == 'W')
    W[0] = 1, E[0] = 0;
  else
    W[0] = 0, E[0] = 1;

  for (int i = 1; i < n; ++i) {
    if (s[i] == 'W') {
      W[i] = W[i - 1] + 1, E[i] = E[i - 1];
    } else {
      W[i] = W[i - 1], E[i] = E[i - 1] + 1;
    }
  }

  for (int i = 1; i < n - 1; ++i)
    ans = min(ans, W[i - 1] + E[n - 1] - E[i - 1]);

  ans = min({ans, E[n - 1] - E[0], W[n - 2]});

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


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

int main() {
    for(int i=1;i<10;i++){
    cout << i<<"x1="<<i*1<<endl;
    cout << i<<"x2="<<i*2<<endl;
    cout << i<<"x3="<<i*3<<endl;
    cout << i<<"x4="<<i*4<<endl;
    cout << i<<"x5="<<i*5<<endl;
    cout << i<<"x6="<<i*6<<endl;
    cout << i<<"x7="<<i*7<<endl;
    cout << i<<"x8="<<i*8<<endl;
    cout << i<<"x9="<<i*9<<endl;
    }
    return 0;
}




Measured memory_bytes: 2984
def make1d(n)
  a = Array.new(n)
  for i in 0..(n-1)
    a[i] = 0
  end
  a
end

def make2d(height,width)
  a = Array.new(height)
  for i in 0..(height-1)
    a[i] = make1d(width)
  end
  a
end
 def min(a, b)
   (a < b) ? a : b
 end

# version 1.4
# see http://lecture.ecc.u-tokyo.ac.jp/johzu/joho-kagaku/


n,k=gets.split.map(&:to_i)
s=make2d(n,2)
for i in 0..n-1
  a,b=gets.split.map(&:to_i)
  s[i][0]=a
  s[i][1]=b
end
s.sort!

sum=0
for i in 0..n-1
  sum=sum+s[i][1]
  if sum>=k
    puts s[i][0]
    break
  end
end


Measured memory_bytes: 10640
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define INF INT_MAX
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n;
ll b[101];
ll ans;
ll a[101];
int main(){
   cin.tie(0);  
   ios::sync_with_stdio(false);
   cin>>n;


   FOR(i,n-1){
     cin>>b[i];
   }

   ans+=b[n-2];
   a[n-1]=b[n-2];
   for(int i=n-2;i>=0;i--){
     if(i==0) ans+=b[0];
     else if(b[i-1]>b[i]){
       ans+=b[i];
       a[i]=b[i];
     }else{
       ans+=b[i-1];
       a[i]=b[i-1];
     }
   }
   
   cout<<ans<<endl;
   return 0;
}



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

using namespace std;
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;



int main () {
   SpeedForce;
	cin >> n;
	ll sum = 0, pref = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum += a[i];
	}
	ll ans = sum;

	for (int i = 1; i <= n; i ++) {
		pref += a[i];
		ll mx = max(pref, sum - pref);
		ll res = 0;
		if (mx > pref) res += mx - pref;
		if (mx > sum - pref) res += mx - sum + pref;
		ans = min(ans, res);
	}        

	cout << ans;

   return Accepted;
}

// B...a

Measured memory_bytes: 18688
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define per(i,s,n) for(int i=n-1;i>=s;i--)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=1000000007;

int main(){
  int n;
  int k;
  cin>>n>>k;
  k--;
  char c;
  rep(i,n){
    cin>>c;
    if(k==i){
      c=(c-'A')+'a';
    }
    cout<<c;
  }
  cout<<endl;
}



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

int main() {
  int A;
  int B;
  cin >> A >> B;
  
  int ans;
  if(A>B) ans = A+(A-1);
  else if(A<B) ans = B+(B-1);
  else ans = A+B;
  
  cout << ans << endl;
}

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

int main()
{
	int N,i,m4,m2,m1;
	cin >> N;
	m4 = 0;
	m2 = 0;
	m1 = 0;
	vector<int>A(N);
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (i = 0; i < N; i++) {
		if (A[i] % 4 == 0)
			m4++;
		else if (A[i] % 2 == 0)
			m2++;
		else if (A[i] % 2 == 1)
			m1++;
	}
	if (m2 == 0) {
		if(m4>=m1-1)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	else if (m4 >= m1)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 768
program main
  implicit none
  integer :: N
  character(len=4000) :: S
  integer(8) :: out
  integer :: i,j,k
  integer(8) :: iR(3)
  integer,parameter :: I_R = 1, I_G = 2, I_B = 3
  read(*,*) N
  read(*,*) S
  iR(:) = 0
  do i = 1,N
     if (S(i:i) == "R") then
        iR(I_R) = iR(I_R) + 1
     end if 
     if (S(i:i) == "G") then
        iR(I_G) = iR(I_G) + 1
     end if
     if (S(i:i) == "B")  then
        iR(I_B) = iR(I_B) + 1
     end if
  end do
  out = iR(1)*iR(2)*iR(3)
  do i = 1,N-2
     do j = i+1,N-1
        k = 2*j-i
        !if ( k>N) cycle
        if (k <= N ) then
           if ( (S(i:i) /= S(j:j)) .and. ( S(i:i) /= S(k:k) )&
                .and. (S(j:j) /= S(k:k)) ) then
              out = out - 1
           end if
        end if
     end do
  end do
  write(*,'(i0)') out
  stop
end program main


Measured memory_bytes: 2928
#include "vector"
#include "set"
#include "map"
#include "unordered_set"
#include "unordered_map"
#include "string"
#include "iostream"
#include "algorithm"
#include "queue"

using namespace std;

#define ll long long
#define INF 2e9
#define INF2 4611686018427387904
//#define MOD 1000000007
#define MOD 998244353
#define MAX_SIZE 1000000000

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { bool first = true; for (const auto& j: v) { if (!first) { os << " "; } first = false; os <<j; } os << "\n"; return os; }
template<typename T>
istream& operator>>(istream& is, vector<T>& v) { for (auto& elem : v) { is >> elem; } return is; }

vector<ll> f;
void set_f(int n) { f.resize(n+1); f[0] = 1; for (int i=1; i<= n; i++) { f[i] = (f[i-1] * i) % MOD;} }
ll nod(ll a, ll b) { if (b == 0) { return a; } else { return nod(b, a % b); } }
ll pw(ll x, ll n, ll m=MOD) { if (n == 0) { return 1;} if (n%2 == 0) { return pw((x*x) % m, n/2, m); } return (pw(x, n-1, m) * x) % m; }
ll dv(ll a, ll b) { return (a * pw(b, MOD - 2)) % MOD; }
ll c_n_k(int n, int k) { if (k > n) { return 0; } if (k < 0) { return 0; } return dv(dv(f[n], f[k]), f[n-k]); }


void solve() {
    int n, s;
    cin >> n >> s;

    vi a(n);
    cin >> a;

    vll dp1(s+1, 0);
    dp1[0] = 1;

    ll ans = 0;
    for (int i=0; i<n; i++) {
        if (a[i] < s) {
            ans = (ans + dp1[s - a[i]] * (n-i)) % MOD;
        }
        if (a[i] == s) {
            ans = (ans + (i+1) * (n-i)) % MOD;
        }

        vll dp2 = dp1;
        for (int j=a[i]; j<=s; j++) {
            if (j == a[i]) {
                dp2[j] += i+1;
            } else {
                dp2[j] += dp1[j - a[i]];
            }

            dp2[j] %= MOD;
        }

        dp1 = dp2;
    }

    cout << ans;
}


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

    if (0) {
        int tests;
        cin >> tests;
        for (int t = 1; t <= tests; t++) {
            //cout << "Case #" << t << ": ";
            solve();
            //cout << "\n";
        }
    } else {
        solve();
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
int main() {
	int N; cin >> N;
	vector<string>S(N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		cin >> S.at(i);
		if (S.at(i) == "E869120") ans++;
	}
	cout << ans << endl;
}



Measured memory_bytes: 3324
#include "bits/stdc++.h"
using namespace std;


int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int H, W;
int check(vector<vector<int>>&field, int y, int x) {
	vector<int>colors;
	vector<int>xs;
	vector<int>ys;
	for (int i = 0; i < 4; ++i) {
		int ny(y), nx(x);
		while (1) {
			ny += dy[i]; nx += dx[i];
			if (ny < 0 || ny >= H || nx < 0 || nx >= W)break;
			if (field[ny][nx]) {
				colors.push_back(field[ny][nx]);
				xs.push_back(nx);
				ys.push_back(ny);
				break;
			}
		}
	}
	int score = 0;
	for (int i = 0; i < colors.size(); ++i) {
		for (int j = i + 1; j < colors.size(); ++j) {
			if (colors[i] == colors[j]) {
				if (colors[i] != 0) {
					field[ys[i]][xs[i]] = 0;
					field[ys[j]][xs[j]] = 0;
					score += 2;
				}
			}
		}
	}
	return score;
}

int main() {
cin >> H >> W;
	vector<vector<int>>field(H,vector<int>(W));
	for (int i = 0; i < W; ++i) {
		
	}
	for (int i = 0; i < H; ++i) {
		string st; cin >> st;
		for (int j = 0; j < W; ++j) {
			if (st[j] != '.') {
				field[i][j] = st[j] - 'A' + 1;
			}
		}
	}
	bool flag = true;
	int score = 0;
	while (flag) {
		flag = false;
		int plusscore = 0;
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				if (!field[y][x]) {
					plusscore+=check(field, y, x);
				}
			}
		}
		if (plusscore) {
			flag = true;
			score += plusscore;
		}
	}
	cout << score << endl;
	return 0;
}

Measured memory_bytes: 3960
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
#define rep(i,n) for (int i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define MOD 998244353
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

/*
#include <math.h>
int standerd = int(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

ll cnt[2000000]={};
ll B;
ll C;
ll N;
ll M;
ll K;

vector<ll> inv,fact,invfact;
void Mod_build(ll n,ll mod){
	fact.resize(n+1);
	inv.resize(n+1);
	invfact.resize(n+1);
	fact[0]=inv[0]=invfact[0]=1;
	inv[1]=1;
	for(ll i=0;i<n;i++){
		fact[i+1]=fact[i]*(i+1)%mod;
		if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;
		invfact[i+1]=invfact[i]*inv[i+1]%mod;
	}
}

ll comb(ll n,ll k,ll mod){
	if(n<0||k<0||k>n)return 0;
	return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;
}
ll getPower(ll value,ll shisu){
    ll ans = 1;
    ll cnt = shisu;
    while(cnt>0){
        if(cnt%2==1){
            ans = ans * value % MOD;
        }
        value = value * value % MOD;
        cnt = cnt/2;
    }
    return ans;
}
int main(){
    cin >> N;
    cin >> M;
    cin >> K;
    Mod_build(201010,MOD);


    ll nCk;
    ll ans = 0;
    for( int ki = 0 ; ki <=K ; ki++ ){
        nCk = comb(N-1,ki,MOD);
        ans += ((nCk * M) % MOD) * getPower(M-1,N-ki-1);
        ans = ans % MOD;
    }
    if(ans<0) ans+=MOD;
    cout << ans << endl;

}

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

typedef long long ll;
#define REP(i, n, m) for(int i = n; i < m; i++)
#define REPR(i, n, m) for(int i = n; i >= m; i--)
#define LREP(i, n, m) for(ll i = n; i < m; i++)
#define LREPR(i, n, m) for(ll i = n; i >= m; i--)

#define P pair<int, int >


const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;



//---functions---//
int gcd(int a, int b){
    if(a < b) swap(a, b);
    return b?gcd(b, a%b):a;
}

int s2i(string num){stringstream ss; ss << num << flush; int n; ss >> n; return n;}
string i2s(int n){stringstream ss; ss << n << flush; return ss.str();}

bool firstCompare(const P& firstElof, const P& secondElof){
    return firstElof.first < secondElof.first;
}
bool secondCompare(const P& firstElof, const P& secondElof){
    return firstElof.second < secondElof.second;
}
//---------------//
//-----class-----//
class UnionFind{
    public:
        vector<ll> par; //parents
        vector<ll> siz; // sizes of set
        vector<ll> rank; // rank of each element 
    UnionFind(ll n): par(n), siz(n, 1LL), rank(n){
        LREP(i, 0, n) par[i] = i;
    }
    //initialization
    /*
    void init(ll n){
        par.assign(n);
        siz.assign(n, 1LL);
        rank.assign(n);
        LREP(i, 0, n) par[i] = i;
    }
    */

    // find the root of x
    ll find(ll x){
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }

    //Unite two set including x or y
    void unite(ll x, ll y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]){
            par[x] = y;
            siz[y] += siz[x];
        }else{
            par[y] = x;
            siz[x] += siz[y];
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    //Do x and y belong to the same set?
    bool issame(ll x, ll y){
        return find(x) == find(y);
    }

};

struct edge{ll u, v, cost; };
bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

ll V, E;
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin >> V >> E;
    edge e[E];
    UnionFind uf(V);
    LREP(i, 0, E){
        cin >> e[i].u >> e[i].v >> e[i].cost;
    } 
    
    sort(e, e + E, comp);
    ll ans = 0;
    LREP(i, 0, E){
        if(!uf.issame(e[i].u, e[i].v)){
            uf.unite(e[i].u, e[i].v);
            ans += e[i].cost;
        }
    }
    cout << ans << '\n';

}




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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;

int main()
{
  int X; scanf("%d", &X);
  int val = sqrt(X * 2);
  int ans = -1;
  if (val * (val + 1) == 2 * X) {
    ans = val;
  }
  else if (val * (val + 1) > 2 * X) {
    ans = val;
  }
  else {
    ans = val + 1;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
from collections import deque
N,Q = map(int, input().split())
a = [0] * (N-1)
b = [0] * (N-1)
g=[[] for i in range(N+1)]
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
p = [0] * Q
x = [0] * Q
ans=[0]*(N+1)
for i in range(Q):
    p[i], x[i] = map(int, input().split())
    ans[p[i]]+=x[i]
    
q = deque([1]) 
ch=[0]*(N+1)
while len(q) > 0:
    pp = q.popleft()     # キュー取りだし（先頭）
    if ch[pp]==0:
        ch[pp]=1
    for u in g[pp]:
        if ch[u]!=1:
           
            ans[u]+=ans[pp]
            q.append(u)
    #print(pp,l,q)

    
for i in range(1,N+1):
    print(ans[i],end=' ')

Measured memory_bytes: 126728
#include<iostream>
using namespace std;
int main() {
    char c;
    while (cin.get(c)){
        if      (c == 'a'){
            c = 'A';
        }
        else if (c == 'b') {
            c = 'B';
        }
        else if (c == 'c') {
            c = 'C';
        }
        else if (c == 'd') {
            c = 'D';
        }
        else if (c == 'e') {
            c = 'E';
        }
        else if (c == 'f') {
            c = 'F';
        }
        else if (c == 'g') {
            c = 'G';
        }
        else if (c == 'h') {
            c = 'H';
        }
        else if (c == 'i') {
            c = 'I';
        }
        else if (c == 'j') {
            c = 'J';
        }
        else if (c == 'k') {
            c = 'K';
        }
        else if (c == 'l') {
            c = 'L';
        }
        else if (c == 'm') {
            c = 'M';
        }
        else if (c == 'n') {
            c = 'N';
        }
        else if (c == 'o') {
            c = 'O';
        }
        else if (c == 'p') {
            c = 'P';
        }
        else if (c == 'q') {
            c = 'Q';
        }
        else if (c == 'r') {
            c = 'R';
        }
        else if (c == 's') {
            c = 'S';
        }
        else if (c == 't') {
            c = 'T';
        }
        else if (c == 'u') {
            c = 'U';
        }
        else if (c == 'v') {
            c = 'V';
        }
        else if (c == 'w') {
            c = 'W';
        }
        else if (c == 'x') {
            c = 'X';
        }
        else if (c == 'y') {
            c = 'Y';
        }
        else if (c == 'z') {
            c = 'Z';
        }
        cout.put(c);
    }
}

Measured memory_bytes: 2984
//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>
#include <cstdint>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef unsigned long long		SQWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int main()
{
	int N;
	cin >> N;

	for (int i = N; i < 1000; i++) {
		int keta1 = (i % 10);
		int keta2 = (i / 100);
		int keta3 = (i / 10) % 10;
		if ((keta1 == keta2) && (keta1 == keta3)) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<stack>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
#define MAX 510000
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
using namespace std;

int main(){
    stack<int> S;
    int a,b,x;
    string s;
    
    while(cin>>s){
        if(s[0]=='+'){
            a=S.top();S.pop();
            b=S.top();S.pop();
            S.push(a+b);
        }
        else if(s[0]=='-'){
            b=S.top();S.pop();
            a=S.top();S.pop();
            S.push(a-b);
        }
        else if(s[0]=='*'){
            a=S.top();S.pop();
            b=S.top();S.pop();
            S.push(a*b);
        }
        else{
            S.push(atoi(s.c_str()));
        }
    }
    
    cout<<S.top()<<endl;
    return 0;
}


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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

/*
cin.tie(0);
ios::sync_with_stdio(false);
*/
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int i;
	int ans = 0;
	for (i = 0; i < s.size(); i++) {
		if (s[i] == '1')
			ans++;
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
// ABC175-A
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define e_b emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ipair;
typedef pair<ll,ll> lpair;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る
void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int n,x,t;
    cin>>n>>x>>t;
    cout<<(n+(x-1))/x*t<<endl;
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
//**デバッグ準備**//
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//gcdlcm, isPrime, eratos, Npow, divisor, modinv, bitSearch, bitList, dfs, bfs//
//dijkstra, WarshallFloyd, BellmanFord, UnionFind, COM, digitDP ,RMQ//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z;
ll MOD = 1000000007; ll INF = 1LL << 60; ll ans = 0; ll z = 0, o = 1;
vl flag, color, D, Ans, inter; vll path;
int main() {
	cin >> N;
	cout << 0 << endl;
	cout << flush;
	string s;
	string f;
	cin >> s;
	if (s == "Vacant") { exit(0); }
	f = s;
	ll left = 0;
	ll right = N - 1;
	ll mid = (left + right) / 2;
	for (i = 0;; i++) {
		mid = (left + right) / 2;
		cout << mid << endl;
		cout << flush;
		string s;
		cin >> s;
		if (s == "Vacant") { exit(0); }
		if ((mid % 2 == 1 && s == f) || (mid % 2 == 0 && s != f)) right = mid-1;
		else left = mid + 1;
	}
}

Measured memory_bytes: 852
def f(n, m):
  return(abs(n[0]-m[0]) + abs(n[1]-m[1]))

n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]

f0 = [x - y for x, y in XY]
f1 = [x + y for x, y in XY]

ans = max(max(f0) - min(f0), max(f1) - min(f1))

print(ans)

Measured memory_bytes: 61436
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		StringBuilder output = new StringBuilder();
		int n = scan.nextInt();
		for (int i = 3; i <= n; i++) {
			if ((i % 3) == 0) {
				output.append(" ").append(i);
			} else  {
				int x = i;
				while (x != 0) {
					if ((x % 10) == 3) {
						output.append(" ").append(i);
						break;
					}
					x /= 10;
				}
			}
		}
		System.out.println(output);
	}
}

Measured memory_bytes: 20404
#include <stdio.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

const int MAXN = 1e5+1;
const int MOD = 1e9 + 7;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define FAILNO {printf("NO\n"); return 0;}
#define FAIL1 {printf("-1\n"); return 0;}

int N,K;
char S[MAXN];
char A[MAXN];
int B[MAXN];

int main() {
#ifdef OJ
	freopen("input.txt", "rt", stdin);
	//freopen("output.txt", "wt", stdout);
#endif

	scanf("%d %d", &N, &K);
	scanf("%s", S);

	int j = 0;
	A[0] = S[0];
	B[0] = 1;

	for (int i = 1; i < N; i++) {
		if (S[i] == A[j]) {
			B[j]++;
		} else {
			A[++j] = S[i];
			B[j] = B[j-1] + 1;
		}
	}

	//printf("j = %d\n", j);
	//for (int i = 0; i <= j; i++) printf("%c", A[i]);
	//printf("\n");
	//for (int i = 0; i <= j; i++) printf("%d", B[i]);
	//printf("\n");

	//for (int i = 1; i <= j; i++) B[i] += B[i-1];
	int i;
	if (A[0] == '0') {
		i = min(j, 2*K-1);
	} else {
		i = min(j, 2*K);
	}

	int ans = B[i];
	int k = 0;
	int t = K;
	while(k < j) {
		if (A[k] == '0') t--;
		k++;
		while(i < j) {
			if (A[i+1] == '0' && t == K) break;
			i++;
			if (A[i] == '0') t++;
		}

		ans = max(ans, B[i] - B[k-1]);
	}
	printf("%d\n", ans);

	return 0;
}



Measured memory_bytes: 768
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using int64 = int64_t;

constexpr int64 MOD = 1000000007;

template <int MAX_N>
class UnionFind {
public:
    int parent[MAX_N];
    int rank[MAX_N];

    UnionFind(int n) {
        for (int j = 0; j < n; ++j) {
            parent[j] = j; rank[j] = 0;
        }
    }

    int find(int x) {
        if (parent[x] == x) { return x; }
        return parent[x] = find(parent[x]);
    }

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) { return false; }

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

        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int N, K, L;

UnionFind<202020> uf_road(202020);
UnionFind<202020> uf_rail(202020);

using P = pair<int, int>;

map<P, int> ret;

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

    for (int j = 0; j < K; ++j) {
        int p, q; cin >> p >> q;
        --p; --q;
        uf_road.unite(p, q);
    }
    for (int j = 0; j < L; ++j) {
        int r, s; cin >> r >> s;
        uf_rail.unite(--r, --s);
    }

    for (int j = 0; j < N; ++j) {
        P key = make_pair(uf_road.find(j), uf_rail.find(j));
        if (ret.find(key) == end(ret)) {
            ret[key] = 1;
        } else {
            ++ret[key];
        }
    }

    for (int j = 0; j < N; ++j) {
        P key = make_pair(uf_road.find(j), uf_rail.find(j));
        if (j > 0) { cout <<' ' ; }
        cout << ret[key];
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 15232
n = gets.to_i
d,x = gets.chomp.split(" ").map(&:to_i)

eaten_choco = n
n.times do
  input = gets.to_i
  i = 1
  while (input*i)+1 <= d
    eaten_choco += 1
    i+=1
  end
end

puts eaten_choco + x


Measured memory_bytes: 1788
#include <stdio.h>
int olds[6] = {10, 20, 30, 40, 50, 60};
int mans[7];
int main() {
	int N, I, i, x;
	while(1) {
		scanf("%d", &N);
		if(N == 0) break;
		for(i = 0; i < 7; ++ i) mans[i] = 0;
		for(I = 0; I < N; ++ I) {
			scanf("%d", &x);
			for(i = 0; i < 6 && x >= olds[i]; ++ i);
			mans[i] ++;
		}
		for(i = 0; i < 7; ++ i) printf("%d\n", mans[i]);
	}
	return 0;
}

Measured memory_bytes: 600
/*
g++ -std=c++11 -o2 -Wall ABC100A.cpp -o ./out/ABC100A.out
./out/ABC100A.out
*/

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

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define tr(c, i) for (iter(c) != (c).begin(); i != (c).end(); ++i)
#define pb push_back
#define mp make_pair

typedef long long ll;

int main(){
//    freopen("./input/input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a;
    int b;
    cin >> a >> b;
    if (max(a,b) - min(a,b) <= 1) {
      cout << "Yay!\n";
    } else {
      cout << ":(\n";
    }
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

//#define DEBUG
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int main(){
#ifdef DEBUG
	
#endif
	char S[50], T[50];
	scanf("%s", S);
	scanf("%s", T);
	int lenS = strlen(S);
	int lenT = strlen(T);

	int i,j;
	int index=-1;
	for (i = 0; i < lenS; i++) {
		for (j = 0; j < lenT; j++) {
			if (!(S[i + j] == '?' || S[i + j] == T[j])) {
				break;
			}
			if (j == lenT - 1) {
				index = i;
			}
		}
	}
	//printf("index=%d\n", index);
	if (index != -1) {
		for (i = 0; i < lenS; i++) {
			if (i == index) {
				for (j = 0; j < lenT; j++) {
					//printf("S[%d]=%c T[%d]=%c\n", i, S[i], j, T[j]);
					S[i] = T[j];
					i++;
				}
			}
			if (S[i] == '?') {
				S[i] = 'a';
			}
		}
		printf("%s\n", S);
	}
	else {
		printf("UNRESTORABLE\n");
	}
}

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

int main(){
  long long int cnt=0,ans=0,N,M ;
  vector<int> A(100001),B(100001);
  vector<long long int> H(100001);
  
  cin>> N>>M;
  for(long long int i=0;i<N;i++ )cin>>H.at(i);
  for(long long int i=0;i<M;i++){
    cin>>A.at(i)>>B.at(i);
  }
  
  vector<int> An(100001);
  for(long long int i=0;i<N;i++)An.at(i)=1;
  for(long long int i=0;i<M;i++){
    if(H.at(A.at(i)-1)>H.at(B.at(i)-1))An.at(B.at(i)-1)=0;
    else if(H.at(A.at(i)-1)<H.at(B.at(i)-1))An.at(A.at(i)-1)=0;
    else{An.at(B.at(i)-1)=0; An.at(A.at(i)-1)=0;}
  }
  for(long long int i=0;i<N;i++){
    ans+=An.at(i);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 5112
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e18;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
signed main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int ans = 0;
  rep(i, n) ans = gcd(ans, a[i]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
def insert(r, n):
    if 0 == len(T):
        T[n] = [None, None, None]
    else:
        if n < r:
            left = T[r][0]
            if left == None:
                T[r][0] = n
                T[n] = [None, None, r]
            else:
                insert(left, n)
        if r < n:
            right = T[r][1]
            if right == None:
                T[r][1] = n
                T[n] = [None, None, r]
            else:
                insert(right, n)

def find(n):
    if n in T:
        return True
    else:
        return False

def dele(r, n):
    z = T[n]
    left = z[0]
    right = z[1]
    p = z[2]
    if left is None and right is None:
        i = T[p].index(n)
        T[p][i] = None
        del T[n]
    elif left is None and right is not None:
        x = T[p].index(n)
        T[p][x] = right
        T[right][2] = z[2]
        del T[n]
    elif left is not None and right is None:
        x = T[p].index(n)
        T[p][x] = left
        T[left][2] = z[2]
        del T[n]
    elif left is not None and right is not None:
        inorder = list(map(int, print_inorder(r).split()))
        next_n = inorder[inorder.index(n) + 1]
        if r == n:
            r = next_n
        dele(r, next_n)
        T[next_n] = T[n]
        del T[n]
        n_r = T[next_n][1]
        n_p = T[next_n][2]
        if n_r is not None:
            v = T[n_r]
            if v[0] == n:
                v[0] = next_n
            if v[1] == n:
                v[1] = next_n
            if v[2] == n:
                v[2] = next_n
        if n_p is not None:
            v = T[n_p]
            if v[0] == n:
                v[0] = next_n
            if v[1] == n:
                v[1] = next_n
            if v[2] == n:
                v[2] = next_n
    return r

def print_inorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = ""
    if left != None:
        ans += print_inorder(left)
    ans += " {}".format(r)
    if right != None:
        ans += print_inorder(right)
    return ans

def print_preorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = " {}".format(r)
    if left != None:
        ans += print_preorder(left)
    if right != None:
        ans += print_preorder(right)
    return ans

n = int(input())
T = {}

root = None
for i in range(n):
    inst = input()
    if inst[0] == 'i':
        num = int(inst[7:])
        if i == 0:
            root = num
        insert(root, num)
    elif inst[0] == 'f':
        num = int(inst[5:])
        if find(num):
            print("yes")
        else:
            print("no")
    elif inst[0] == 'd':
        num = int(inst[7:])
        root = dele(root, num)
    elif inst[0] == 'p':
        print(print_inorder(root))
        print(print_preorder(root))

Measured memory_bytes: 127764
#include<bits/stdc++.h>
#include<set>
#include<queue>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

#define pb push_back
#define PI acos(-1.0)
#define MAX 10000007 //1e7+7
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define __FastIO  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
struct P
{
  ll pos,val;
};


int main(){
  ll N,M,A,B,C,D,testCase,K,val;
  ll arr[1005],brr[100005];
  map<ll,ll>mp;
  vector<ll>v,v1;
  vector< pair<ll,ll> >Pair;
  string str;
  while(cin>>N)
  {
    cin>>str;
    for(int i=0;i<str.size();i++)
    {
      /*if(str[i]>='a' and str[i]<='z')
        {
          ll tmp1=int(str[i])-97;
        }
        */
      ll tmp=int(str[i])+N,Num=N;
      if(str[i]>='a' and str[i]<='z' and tmp<=122)
      {
        str[i]=str[i]+N;
      }
      else if(str[i]>='A'  and str[i]<='Z' and tmp<=90)
      {
        str[i]=str[i]+N;
      }
      else
      {
        if(str[i]>='a' and str[i]<='z')
        {
          val=int(str[i]);
          while(N>0)
          {
            if((val+1)<=122)
            {
              val++;
            }
            else
            {
              val=97;
            }
            N--;
          }
          str[i]=char(val);
        }
        else
        {
          val=int(str[i]);
          while(N>0)
          {
            if((val+1)<=90)
            {
              val++;
            }
            else
            {
              val=65;
            }
            N--;
          }
          str[i]=char(val);
          N=Num;
        }
      }
    }
    cout<<str<<endl;
  }
  return 0;
}


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

int main() {
  int m, f, b;
  cin >> m >> f >> b;

  if (m + f < b) {
    cout << "NA" << endl;
  } else {

    if (b <= m) {
      cout << 0 << endl;
    } else {
      cout << b - m << endl;
    }
  }
}

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

int main() {
  int width, height;
  int *out = NULL;
  
  cin >> height >> width;
  out = (int*)malloc(height * width * sizeof(int));
  if ( out == NULL ) {
    cout << "malloc error" << endl;
    exit(-1);
  }
  
  memset( out, 0, height * width * sizeof(int) );
  
  for ( int h = 0; h < height ; h++ ) {
    int *top, *center, *bottom;
    center = out + h * width;
    if ( 0 < h ) top = center - width;
    else top = NULL;
    if ( h < height - 1 ) bottom = center + width;
    else bottom = NULL;
    
    for ( int w = 0; w < width ; w++ ) {
      char inp;
      bool flag_left = 0 < w;
      bool flag_right = w < width - 1;
      cin >> inp;
      
      if ( inp == '#' ) {
        if ( top ) {
          if ( flag_left ) top[-1]++;
          top[0]++;
          if ( flag_right ) top[1]++;
        }
        if ( flag_left ) center[-1]++;
        center[0] += 9;
        if ( flag_right ) center[1]++;
        if ( bottom ) {
          if ( flag_left ) bottom[-1]++;
          bottom[0]++;
          if ( flag_right ) bottom[1]++;
        }
      }
      if ( top ) top++;
      center++;
      if ( bottom ) bottom++;
    }
  }
  
  for ( int h = 0 ; h < height ; h++ ) {
    int *p = out + h * width;
    
    for ( int w = 0 ; w < width ; w++, p++ ) {
      if ( *p < 9 ) cout << *p;
      else cout << '#';
    }
    cout << endl;
  }
}



Measured memory_bytes: 256
import std.algorithm;
import std.bigint;
import std.concurrency;
import std.container;
import std.conv;
import std.functional;
import std.format;
import std.math;
import std.meta;
import std.numeric;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;


auto solve(long N) {
    if (N % 2 == 0)
        return 0.5;
    else
        return cast(double)(N / 2 + 1) / N;
}


void main() {
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    static if (is(ReturnType!solve == void))
        solve(N);
    else
        solve(N).writeln;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007
using namespace std;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);

}
int main()
{
    ios_base:: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    ll n;
    cin>>n;
    string s;
    cin>>s;
    vector<ll>r(n),b(n),g(n);
    for(ll i = n-1; i >= 0; i--)
    {
        if(s[i] == 'R')
            r[i]++;
        if(s[i]=='B')
            b[i]++;
        if(s[i]=='G')
            g[i]++;
        if(i != n-1)
        {
            r[i] += r[i+1];
            g[i] += g[i+1];
            b[i] += b[i+1];
        }
    }
    ll ans = 0;
    for(ll i = 0; i < n; i++)
    {
        for(ll j = i+1; j < n; j++)
        {
            if(s[i] == 'R')
            {
                if(s[j] == 'G' && j+1 < n)
                {
                    ans += b[j+1];
                    if(2*j-i < n && s[2*j-i] == 'B')
                        ans--;
                }
                if(s[j] == 'B' && j+1 < n)
                {
                    ans += g[j+1];
                    if(2*j-i < n && s[2*j-i] == 'G')
                        ans--;
                }
                continue;
            }
            if(s[i] == 'G')
            {
                if(s[j] == 'R' && j+1 < n)
                {
                    ans += b[j+1];
                    if(2*j-i < n && s[2*j-i] == 'B')
                        ans--;
                }
                if(s[j] == 'B' && j+1 < n)
                {
                    ans += r[j+1];
                    if(2*j-i < n && s[2*j-i] == 'R')
                        ans--;
                }
                continue;
            }
            if(s[i] == 'B')
            {
                if(s[j] == 'G' && j+1 < n)
                {
                    ans += r[j+1];
                    if(2*j-i < n && s[2*j-i] == 'R')
                        ans--;
                }
                if(s[j] == 'R' && j+1 < n)
                {
                    ans += g[j+1];
                    if(2*j-i < n && s[2*j-i] == 'G')
                        ans--;
                }
                continue;
            }
        }
    }
    cout<<ans;
}


Measured memory_bytes: 3700