akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
  int n; cin >>n;
  vector<int> vec(n);
  vector<int> color(8,0);
  int low,high;
  int key=0;
  rep(i,n){
    cin >> vec[i];
    if(vec[i]>=1&&vec[i]<=399) color[0]++;
    if(vec[i]>=400&&vec[i]<=799) color[1]++;
    if(vec[i]>=800&&vec[i]<=1199) color[2]++;
    if(vec[i]>=1200&&vec[i]<=1599) color[3]++;
    if(vec[i]>=1600&&vec[i]<=1999) color[4]++;
    if(vec[i]>=2000&&vec[i]<=2399) color[5]++;
    if(vec[i]>=2400&&vec[i]<=2799) color[6]++;
    if(vec[i]>=2800&&vec[i]<=3199) color[7]++;
    if(vec[i]>=3200) key++;
  }
  int count=0;
  rep(i,8) if(color[i]>=1) count++;
  low=max(1,count);
  high=count+key;
  cout <<low<<" "<<high<<endl;
}    

Measured memory_bytes: 256
loop {
	n = gets.to_i
	break if n == 0

	unit_system = []
	ok = true
	n.times {
		gets.chomp =~ /^1 (\w+) = 10\^(-?\d+) (\w+)/
		next unless ok
		u1, x, u2 = $1, $2.to_i, $3
		us1 = unit_system.find{|us| us[u1]}
		us2 = unit_system.find{|us| us[u2]}
		if !us1 && !us2
			unit_system << {u1 => 0, u2 => x}
		elsif !us1
			us2[u1] = us2[u2] - x	
		elsif !us2
			us1[u2] = us1[u1] + x	
		elsif us1 == us2
			if us1[u1] + x != us2[u2]
				ok = false
			end
		else
			unit_system.delete(us2)
			us2.each{|u3, pos|
				y = pos - us2[u2]
				us1[u3] = us1[u1] + x + y
			}
		end
	}
	puts ok ? 'Yes' : 'No'
}

Measured memory_bytes: 6100
#include<bits/stdc++.h>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
int main(){
  int a[5];
  int k;
  for(int i=0;i<5;i++){
    cin>>a[i];
  }
  cin>>k;
  sort(a,a+5);
  if(a[4]-a[0]<=k)
  cout<<"Yay!"<<endl;
  else
  cout<<":("<<endl;
}


Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	int ki[100001]={0};
	int gu[100001]={0};
	int n,i;cin>>n;
	for(i=0;i<n/2;i++){
		int u,v;cin>>u>>v;
		ki[u]++;
		gu[v]++;
	}
	int Ka=0,Kb=0,Ga=0,Gb=0;
	for(i=0;i<=100000;i++){
		if(ki[Kb]<ki[i]){Kb=i;}
		if(ki[Ka]<ki[Kb]){swap(Ka,Kb);}
		if(gu[Gb]<gu[i]){Gb=i;}
		if(gu[Ga]<gu[Gb]){swap(Ga,Gb);}
	}
	//cerr<<Ka<<Ga<<endl;
	if(Ka!=Ga){cout<<n-(ki[Ka]+gu[Ga])<<endl;}
	else{cout<<n-max(ki[Ka]+gu[Gb],ki[Kb]+gu[Ga])<<endl;}
	return 0;
}

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

using namespace std;

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

    sort(v.begin(), v.end());

    double ans = v[0];
    for (int i=1; i<n; i++)
        ans = (ans + v[i]) / 2;

    cout << ans << endl;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while(1)
    {
        if(d == 0)
        {
            break;
        }
        if(a < b)
        {
            break;
        }
        b *= 2;
        d--;
    }
    while(1)
    {
        if(d == 0)
        {
            break;
        }
        if(b <c)
        {
            break;
        }
        c *= 2;
        d--;
    }
    if(a < b && b < c)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}
int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 3632
function Main(s) {
  var s = s.split("\n");
  var d = s[0].split(" ")[0]*1, g = s[0].split(" ")[1]*1;
  var p_c = s.map(e => e.split(" ").map(e => e*1));
  p_c = p_c.slice(1, d+1);
  var min = Infinity;
  for (var bit = 0; bit < (1<<d); bit++) {
    var arr = [];
    var sum = 0;
    var cnt = 0;
    for (var i = 0; i < d; i++) {
      if (bit & (1<<i)) {
        sum += p_c[i][0] * (i + 1)* 100 + p_c[i][1];
        cnt += p_c[i][0];
      } else {
        arr.push(i);
      }
    }
    if (sum < g) {
      var limit = Math.ceil((g - sum) / ((arr[arr.length-1]+1)*100));
      if (limit >= p_c[arr[arr.length-1]][0]) {
        continue;
      } else {
        cnt += limit;
      }
    }
    min = Math.min(min, cnt);
  }
  console.log(min);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 8012
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int x = 0;
		while(true){
			String line = br.readLine();
			char[] c = line.toCharArray();
			for(int i = 0; i < c.length; i++){
				x += Integer.parseInt("" + c[i]);
			}
			if( x == 0){
				break;
			}else{
				sb.append(x+"\n");
				x = 0;
			}
		}
		System.out.print(sb);
	}
}

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

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

    int start, end;
    bool sflag = true;
    for (size_t i = 0; i < s.size(); ++i){
        if (s[i] == 'A' && sflag == true){
            start = i;
            sflag = false;
        }
        else if (s[i] == 'Z') end = i;
    }

    cout << end - start + 1 << endl;
}

Measured memory_bytes: 640
#118_C
N=int(input())
A=list(map(int,input().split()))
while A.count(0)<N-1:
    A.sort()
    i=0
    while A[i]==0: i+=1
    min_A=A[i]
    A=[min_A if j==i else A[j]%min_A for j in range(N)]
print(max(A))

Measured memory_bytes: 14224
h,w,k = map(int,input().split())

sl = []
for _ in range(h):
    s = list(input())
    s = [int(i) for i in s]
    sl.append(s)
import itertools
sl_ac = []
for s in sl:
     ac = [0] + list(itertools.accumulate(s))
     sl_ac.append(ac)

anss = float("inf")


from itertools import product
for bits in product([0, 1], repeat=h-1):
    ans = 0
    ans += sum(bits)
    p = 0
    group = [0 for i in range(h)]
    for idx, bit in enumerate(bits):
        group[idx] = p
        p += bit
    group[-1] = p
    sum_group = [0 for i in range(sum(bits) + 1)]
    reset = 0
    flag = "OK"
    for i in range(w):
        for j in range(h):
            sum_group[group[j]] += sl[j][i]
        if max(sum_group) > k:
            if i == 0:
                flag = "NG"
            else:
                ans += 1
                reset = i
                sum_group = [0 for i in range(sum(bits) + 1)]
                for j in range(h):
                    sum_group[group[j]] += sl[j][i]
                if max(sum_group) > k:
                    flag = "NG"

    if flag == "OK":
        anss = min(ans, anss)
print(anss)






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

struct Point {
    int x, y;
};
bool operator<(const Point& x0, const Point& x1) { return x0.x < x1.x; }

int main() {
    int N, K;
    cin >> N >> K;
    int sB[4000][4000] = {}, sW[4000][4000] = {};
    int cB[4000][4000] = {}, cW[4000][4000] = {};

    for (int i = 0; i < N; i++) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        x %= 2 * K, y %= 2 * K;
        if (c == 'B') {
            cB[y][x]++;
            cB[y + 2 * K][x]++;
            cB[y][x + 2 * K]++;
            cB[y + 2 * K][x + 2 * K]++;
        } else {
            cW[y][x]++;
            cW[y + 2 * K][x]++;
            cW[y][x + 2 * K]++;
            cW[y + 2 * K][x + 2 * K]++;
        }
    }
    for (int i = 0; i < 4 * K; i++) {
        for (int j = 0; j < 4 * K; j++) {
            if (i && j) {
                sB[i][j] = sB[i - 1][j] + sB[i][j - 1] - sB[i - 1][j - 1] + cB[i][j];
                sW[i][j] = sW[i - 1][j] + sW[i][j - 1] - sW[i - 1][j - 1] + cW[i][j];
            } else if (i) {
                sB[i][j] = sB[i - 1][j] + cB[i][j];
                sW[i][j] = sW[i - 1][j] + cW[i][j];
            } else if (j) {
                sB[i][j] = sB[i][j - 1] + cB[i][j];
                sW[i][j] = sW[i][j - 1] + cW[i][j];
            } else {
                sB[0][0] = cB[0][0];
                sW[0][0] = cW[0][0];
            }
        }
    }
    auto cc = [&](int y, int x, int s[4000][4000]) {
        int res = s[y][x];
        if (y >= K) res -= s[y - K][x];
        if (x >= K) res -= s[y][x - K];
        if (y >= K && x >= K) res += s[y - K][x - K];
        return res;
    };
    int ans = 0;
    for (int i = 0; i < 2 * K; i++) {
        for (int j = 0; j < 2 * K; j++) {
            int cnt = 0;
            cnt += cc(i + K - 1, j + K - 1, sB) + cc(i + 2 * K - 1, j + 2 * K - 1, sB);
            cnt += cc(i + 2 * K - 1, j + K - 1, sW) + cc(i + K - 1, j + 2 * K - 1, sW);
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 250240
#include <bits/stdc++.h>
using namespace std;
#define int long long int

void test()
{
    int x, y;
    cin >> x >> y;
    for (int i = 0; i <= x; i++)
    {
        if (i * 2 + (x - i) * 4 == y)
        {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}
int32_t main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        test();
    }

    return 0;
}

Measured memory_bytes: 3612
for i in range(5):
    e  = int(input())
    if e == 0:
        break
    e500 = (1000 - e)//500
    e100 = (1000 - e)%500//100
    e50 = (1000 - e)%500%100//50
    e10 = (1000 - e)%500%100%50//10
    e5 = (1000 - e)%500%100%50%10//5
    e1 = (1000 - e)%500%100%50%10%5//1
    print(e500+e100+e50+e10+e5+e1)


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

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main(){
    int X,Y,Z;
    cin>>X>>Y>>Z;
    int temp =X;
    X=Y;
    Y=temp;
    temp=X;
    X=Z;
    Z=temp;
    cout <<X<<" "<<Y<<" "<<Z<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

//しっかり制約確認したか?
int main()
{
    int a; cin >> a;
    cout << a+(a*a)+(a*a*a) << endl;

    system("pause");
}


Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int N,K;
    cin>>N>>K;
    vector<int> bo(N,0);
    REP(i,N)cin>>bo[i];
    sort(bo.begin(),bo.end(),greater<int>());
    int ans=0;
    REP(i,K)ans+=bo[i];
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long int;
const int MOD = 1e9+7;

vector<vector<ll>> mat_mul(vector<vector<ll>> &mat1, vector<vector<ll>> &mat2){
    int n = int(mat1[0].size());
    vector<vector<ll>> mat3(n, vector<ll>(n, 0));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                mat3[i][j] = mat3[i][j] + mat1[i][k] * mat2[k][j];
                mat3[i][j] %= MOD;
            }
        }
    }
    return mat3;
}

vector<vector<ll>> mat_pow(vector<vector<ll>> &mat1, ll k){
    int n = int(mat1[0].size());
    vector<vector<ll>> mat2(n, vector<ll>(n, 0));
    for(int i=0; i<n; i++){mat2[i][i] = 1;}
    while(k > 0){
        if(k & 1){mat2 = mat_mul(mat1, mat2);}
        mat1 = mat_mul(mat1, mat1);
        k >>= 1LL;
    }
    return mat2;
}

void mat_print(vector<vector<ll>> &mat1){
    for(auto& line:mat1){
        for(auto& v:line){
            cout << v << " ";
        }
        cout << "\n";
    }
}

int main(){
    ll n, k; cin >> n >> k;
    vector<vector<ll>> mat(n, vector<ll>(n));
    for(auto& row:mat){
        for(auto& col:row){
            cin >> col;
        }
    }
    mat = mat_pow(mat, k);
    ll ans = 0;
    for(auto& row:mat){
        for(auto& col:row){
            ans += col;
            ans %= MOD;
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

/** AOJ_No.1159 ICPC_2009_A */
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int n = sc.nextInt();/* 候補者数 */
			int p = sc.nextInt();/* 小石の数 */
			if(n == 0) break;
			
			int[] hand = new int[n];/* 候補者の手元 */
			boolean _break = false;/* while(true)の終了条件を満たすか */
			while(true) {
				for(int i = 0; i < n; i++) {
					if(p == 0) {
						/* 椀が空なら、手札を椀に戻す */
						p = hand[i];
						hand[i] = 0;
					} else {
						/* 手札に一枚もってくる */
						hand[i]++;
						p--;
						
						/* (取り出し後に)椀が空なら */
						if(p == 0) {
							boolean isWin = true;/* 当選フラグ */
							for(int j = 0; j < n; j++) {
								/* 他の候補者に石があるならダメ */
								if(j != i && hand[j] != 0) isWin = false;
							}
							
							/* 当選者が居たなら */
							if(isWin) {
								System.out.println(i);
								_break = true;
								break;
							}
						}
					}
				}
				/* 当選者が出たなら */
				if(_break) break;
			}			
		}
	}
}



Measured memory_bytes: 27292
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int maxN = 100 * 1000 + 9;
const double EPS = 1e-9;

ll s[maxN], t[maxN], moment[2 * maxN], x[2 * maxN], c[maxN];
int n, C;

void read(){
  cin >> n >> C;
  for(int i = 0; i < n; i++)
    cin >> s[i] >> t[i] >> c[i];
}

void solv(){
  for(int i = 1; i <= C; i++){
    fill_n(x, 2 * maxN, 0);
    for(int j = 0; j < n; j++){
      if(c[j] == i){
        x[2 * s[j] - 1]++;
        x[2 * t[j]]--;
      }
    }
    for(int j = 1; j < 2 * maxN; j++)
      x[j] += x[j - 1];
    for(int j = 0; j < 2 * maxN; j++)
      moment[j] += (x[j] > 0);
  }

  cout << *max_element(moment, moment + 2 * maxN) << '\n';
}

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

  #ifdef DEBUG
    freopen("in.txt", "r", stdin);
  #endif

  read();
  solv();

  return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <string>

using namespace std;

int main(){
  	int n, k;
  	cin >> n >> k;
	string s;
  	cin >> s;

  	int max_len=0;
  	int line[n];
  	
  	for(int i=0; i<n; i++)
  		line[i] = 0;    
      
  	int itr = 0;
  
  	for(int i=0; i<n; i++){      
        if( i == 0 && s[i] == '0'){
          	itr++;
        }
      	else{
        	if(i != 0 && s[i] != s[i-1]){
	          	itr++; 
          		line[itr] = line[itr-1];
            }
        }
      	line[itr]++;
    }
  	if(s[n-1]=='0'){
    	itr++;
      	line[itr] = line[itr-1];
    }
     
/*
  	for(int i=0; i<=itr; i++)
      cout << line[i] << " ";
*/
  
  	int ans = 0;
  	if(itr < k*2) ans = line[itr];
    else{
      for(int i=k*2; i<=itr; i++){
        if(ans == 0) ans = line[i];
        else{
          if(i%2 == 0){
            if(i-(k*2+1) >= 0 && ans < line[i] - line[i-(k*2+1)]){
                ans = line[i] - line[i-(k*2+1)];
            }
          }
        }
      }
    }
  
	cout << ans << endl;  
  
	return 0;
}

Measured memory_bytes: 896
//IOI 2021

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

#define pb push_back
#define ff first
#define ss second

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

const int MAXN = 2 * 100 * 1000 + 17;

int n, m, par[MAXN], root, IN[MAXN], lev[MAXN];
bool mark[MAXN];
vector<int> adj[MAXN];

void dfs(int v, int le = 0) {
	mark[v] = true;
	for (auto u : adj[v])
		if (!mark[u] && IN[u] == 1) {
			if (le + 1 > lev[u])
				lev[u] = le + 1, par[u] = v;
			IN[u]--;
			dfs(u, lev[u]);
		}
		else if (!mark[u]) {
			if (le + 1 > lev[u])
				lev[u] = le + 1, par[u] = v;
			IN[u]--;
		}
		else
			;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i < n + m; i++) {
		int v, u;
		cin >> v >> u;
		adj[v].pb(u);
		IN[u]++;
	}
	for (int i = 1; i <= n; i++)
		if (!IN[i])
			root = i;
	dfs(root);
	for (int i = 1; i <= n; i++)
		cout << par[i] << endl;
	return 0;
}


Measured memory_bytes: 15232
N = int(input())
H = list(map(int, input().split()))
H[0] -= 1

def main():
    for i in range(1,N):
        if H[i]>H[i-1]:
            H[i] -= 1
        elif H[i]<H[i-1]:
            print('No')
            return
    print('Yes')


main()






Measured memory_bytes: 14396
MOD = 10 ** 9 + 7

H, W = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
	for w in range(W):
		if h + w == 0:
			dp[h][w] = 1
		elif a[h][w] == "#":
			continue
		elif h == 0:
			dp[h][w] = dp[h][w-1]
		elif w == 0:
			dp[h][w] = dp[h-1][w]
		else:
			dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % MOD

#print(dp)
print(dp[-1][-1])

Measured memory_bytes: 54236
s = input()

if s[0] == s[1] and s[1] == s[2] and s[0] == 'R':
    print(3)
elif (s[1] == s[2] and s[1] == 'R') or (s[1] == s[0] and s[0] == 'R'):
    print(2)
elif s[0] == 'R' or s[1] == 'R' or s[2] == 'R':
    print(1)
else:
    print(0)


Measured memory_bytes: 9056
import java.util.*;
class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = 1;
		int y = 1;
		while(true){
			x = sc.nextInt();
			y = sc.nextInt();
			if(x == 0 && y == 0) break;
			if(x < y){
				System.out.println(x + " " + y);
			}else{
				System.out.println(y + " " + x);
			}
		}
	}
}

Measured memory_bytes: 35536
m, d = map(int, input().split())
ans=0
for M in range(1,m+1):
    for D in range(1,d+1):
        d1=int(D%10)
        d10=int(D/10)
        if d1>=2 and d10>=2 and d1*d10==M:
            ans+=1
print(ans)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc166_b
{
  class Program
  {
    static void Main(string[] args)
    {
      var N = CIn.ReadInt();
      var K = CIn.ReadInt();

      var a = new int[N];

      for (int i = 0; i < K; i++)
      {
        var d = CIn.ReadInt();
        var A = CIn.ReadIntArray(d);

        foreach(var e in A)
        {
          a[e - 1]++;
        }
      }

      var ans = a.Count(e => e == 0);

      Console.WriteLine(ans);
    }
  }

  static class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(int n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(int n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(int n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(int n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }

    public static char[,] ReadCharMatrix(int h, int w)
    {
      var array = new char[h, w];
      for (var i = 0; i < h; i++)
      {
        var l = Console.ReadLine().ToCharArray();
        for (var j = 0; j < w; j++)
        {
          array[i, j] = l[j];
        }
      }
      return array;
    }
  }
}


Measured memory_bytes: 28328
DEBUG = False

import time

N, K = map(int, input().split())
A = [int(i)-1 for i in input().split()]

visited = [False] * N
next = A[0]
visited[0] = True
K -= 1
while not visited[next]:
    if DEBUG:
        print("K: {}, next: {}".format(K, next))
        print("visited: {}".format(visited))
        time.sleep(0.1)
    if K == 0:
        print(next+1)
        exit()
    visited[next] = True
    next = A[next]
    K -= 1

K -= 1
now = next
count = 1
next = A[next]
while now != next:
    next = A[next]
    count += 1
if DEBUG:
    print("count: {}".format(count))

K %= count

if DEBUG:
    print("now: {}, count: {}, K: {}".format(now, count, K))

while K > 0:
    if DEBUG:
        print("now: {}".format(now))
    now = A[now]
    K -= 1

print(A[now]+1)


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

bool dp[105];

int main()
{
  int n;
  cin >> n;
  dp[0] = 1;

  for(int i=0;i <= n;i+=4){
    int k=0;
    while(1){
      if(i+k > n) break;
      dp[i+k] =true;
      k += 7;
    }
  }
  
  if(dp[n]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
s=input()
T=input()
k=[]
for i in range(len(s)-len(T)+1):
    k.append(s[i:i+len(T)])
#print(k)

z=-1
for i in range(len(k)):
    f=1
    for j in range(len(T)):
        if k[i][j]!=T[j] and k[i][j]!='?':
            f=0
            break
    if f==1:
        z=i

if z==-1:
    print('UNRESTORABLE')
else:
    s+=' '*z
    S=s[:z]+T+s[len(T)+z:]
    S=list(S)
    for i in range(len(S)):
        if S[i]=='?':
            S[i]='a'
    print(''.join(S))

Measured memory_bytes: 3188
from collections import deque

def dfs(n,m,ls):
    stack = deque([1])
    visited = [0 for _ in range(n+1)]
    visited[0] = 1
    while stack:
        now = stack.pop()
        for i in range(1,n+1):
            if ls[now][i]==1 and visited[i]==0:
                stack.append(i)
        visited[now]=1
    if all(i==1 for i in visited):
        return True
    else:
        return False

if __name__ =="__main__":
    # n: 頂点, m: 辺
    n,m = map(int,input().split())
    ls = [[0 for _ in range(n+1)] for _ in range(n+1)]
    ls_inputs = [[int(x) for x in input().split()] for _ in range(m)]
    ans = 0
    for j in range(m):
        ls = [[0 for _ in range(n+1)] for _ in range(n+1)]
        for k,path in enumerate(ls_inputs):
            if j == k:
                pass
            else:
                ls[path[0]][path[1]]=1
                ls[path[1]][path[0]]=1
        if dfs(n,m,ls):
            pass
        else:
            ans +=1
    print(ans)
    
    
            
    

Measured memory_bytes: 41200
#include<iostream>

using namespace std;

#define XMAX 1000000
#define NMAX 30
#define NO -1
#define YES 1

int main(void){

	int erato[XMAX+1];

	for(int i=0;i<=XMAX;i++) erato[i]=YES;
	erato[0]=NO,erato[1]=NO;

	for(int i=2;i<=XMAX;i++){
		if(erato[i]==YES){
			for(int j=i+i;j<XMAX;j+=i){
				erato[j]=NO;
			}
		}
	}

	int n,x;
	int dp[XMAX+1];
	int price[NMAX];
	bool f;
	int ans;

	while(1){

		cin>>n>>x;
		if(n==0&&x==0) break;

		for(int i=0;i<n;i++){
			cin>>price[i];
		}

		for(int i=0;i<=x;i++) dp[i]=NO;
		dp[0]=YES;

		while(1){
			f=false;
			for(int i=0;i<x;i++){
				if(dp[i]==YES){
					for(int j=0;j<n;j++){
						if(i+price[j]<=x){
							if(dp[i+price[j]]==NO){
								f=true;
								dp[i+price[j]]=YES;
							}
						}
					}
				}
			}
			if(!f) break;
		}
		ans=-1;
		for(int i=x;i>=0;i--){
			if(dp[i]==YES&&erato[i]==YES){
				ans=i;
				break;
			}
		}

		if(ans==-1) cout<<"NA"<<endl;
		else cout<<ans<<endl;
	}

}

Measured memory_bytes: 8972
N, A, B = map(int, input().split())
S = str(input())

total = 0
kaigai = 0

for i in range(0, len(S)):
    if S[i] == 'a':
        if total < A+B:
            print('Yes')
            total += 1
        else:
            print('No')
    elif S[i] == 'b':
        if total < A+B and kaigai <B:
            print('Yes')
            total += 1
            kaigai += 1
        else:
            print('No')
    else:
        print('No')



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

using namespace std;

int main()
{
    int k,n;
    cin >> k>>n;
    int a[n];
    int b[n];
    cin >> a[0];
    for(int i=1;i<n;i++){
        cin >> a[i];
        b[i-1]=a[i]-a[i-1];
    }
    b[n-1]=a[0]+k-a[n-1];
    int sum =0,mx=0;
    for(int i=0;i<n;i++){
        sum+=b[i];
        mx=max(mx,b[i]);
    }
    cout << sum-mx<< endl;
    return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = Integer.parseInt(sc.next());

    if (N == 1) {
      System.out.println("Hello World");
    } else if (N == 2) {
      int A = Integer.parseInt(sc.next());
      int B = Integer.parseInt(sc.next());
      System.out.println(A + B);
    }
  }
}

Measured memory_bytes: 22228
#include "bits/stdc++.h"
using namespace std;
#define LL long long

void solve() {
   LL n,k;
   cin>>n>>k;
   
   LL ok=0LL;
   while(n!=0){
       n/=k;
       ok++;
   }
   cout<<ok<<"\n";
}
  
int main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();
 	return 0; 
}

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

using namespace std;
typedef long long Int;
#define MOD 1000000007
Int res = 1;
Int n, x;
char a[540][540];
Int cnti[540], cntj[540];
int main(){
  Int ans = 1080;
  Int minus = 0;
  Int total = 0;
  cin >> n;
  for(Int i = 0;i < n;i++){
    for(Int j = 0;j < n;j++){
      cin >> a[i][j];
      if(a[i][j] == '#'){
	total++;
	cntj[j]++;
	cnti[i]++;
	if(cntj[j] == n)minus--;
      }
    }
  }
  if(total == 0){
    cout << -1 << endl;
    return 0;
  }
  for(Int i = 0;i < n;i++){
    int hoge = cntj[i] == 0;
    ans = min(ans, n - cnti[i] + n + minus + hoge);
  }
  cout << ans << endl;
  return 0;
}
  


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
using namespace std;
typedef long long ll;
bool isvalid(bool valid[],int n)
{
    bool ok=true;
    while(n>0)
    {
        if(!valid[n%10]) ok=false;
        n/=10;
    }
    return ok;
}
int main(){
   #ifndef ONLINE_JUDGE 
      FILE_READ_IN 
      FILE_READ_OUT 
   #endif
   int n; cin>>n;
   int d; cin>>d;
   bool valid[10];
 
   fill(valid,valid+10,true);
   for(int i=0;i<d;i++)
   {
       int x; cin>>x;
       valid[x]=false;
   }
   int i=n;
   while (i<=10*n&&!isvalid(valid,i))
   {
       i++;
   }
   cout<<i<<"\n";
   
   return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) cin >> x.at(i) >> y.at(i);
  double d = 0.0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      double dx = x.at(i) - x.at(j), dy = y.at(i) - y.at(j);
      d += sqrt(dx * dx + dy * dy);
    }
  }
  cout << setprecision(17) << d / (0.5 * n) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include <numeric>
#include<cmath>
#include<string>
using namespace std;
#define ll long long

unsigned euclidean_gcd(unsigned a, unsigned b) {
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}

int main(void){
    ll int n;
    cin >> n;
    vector<ll>A(n);
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    vector<ll>l(n+1);
    l[0]=0,l[1]=A[0];
    vector<ll>r(n+1);
    r[n]=0,r[n-1]=A[n-1];
    for(int i=2;i<=n;i++){
        l[i] = euclidean_gcd(l[i-1],A[i-1]);
    }    
    for(int i=n-2;i>=0;i--){
        r[i] = euclidean_gcd(r[i+1],A[i]);
    }    
    ll ans =0;
    for(int i=0;i<n;i++){
        ll tmp;
        if(i==0){
            tmp = r[i+1];
        }else if(i==n-1){
            tmp = l[i];
        }else{
            tmp = euclidean_gcd(l[i],r[i+1]);
        }
        if(ans < tmp){
            ans = tmp;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
n = int(input())
odd = {}
eve = {}

nums = list(map(int,input().split()))

for i in range(n):
    
    new_v = nums[i]
    
    if (i % 2 == 0):

        if new_v in odd:
            odd[new_v] += 1

        else:
            odd[new_v] = 1

    else:

        if new_v in eve:
            eve[new_v] += 1

        else:
            eve[new_v] = 1



odd_m = max(odd , key=odd.get)
eve_m = max(eve , key=eve.get)

odd_c = odd.copy()
eve_c = eve.copy()

del odd_c[odd_m]
del eve_c[eve_m]

if len(odd_c) == 0:
    odd_mt = 0
else:
    odd_mt = max(odd_c , key=odd.get)

if len(eve_c) == 0:
    eve_mt = 0
else:
    eve_mt = max(eve_c , key=eve.get)

odd[0] = 0
eve[0] = 0


if odd_m != eve_m:
    print (n - odd[odd_m] - eve[eve_m])

elif odd[odd_m] + eve[eve_mt] > odd[odd_mt] + eve[eve_m] :
    print (n - odd[odd_m] - eve[eve_mt])

else:
    print (n - odd[odd_mt] - eve[eve_m])

    

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

typedef long long ll;
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define endl '\n'
const int N = 2e5 + 5;
using namespace std;

int main() {
    IO;
    int a[6];
    for (int i = 1; i <= 5; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= 5; ++i) {
        if (a[i] == 0) return cout << i, 0;
    }


}

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

int main() {
    double a, b, c, d, e, f;
    while (cin >> a >> b >> c >> d >> e >> f) {
        double x = (c * e - b * f) / (a * e - b * d);
        double y = (c * d - a * f) / (b * d - a * e);

        if (x == 0) x = 0;
        if (y == 0) y = 0;

        cout << fixed << setprecision(3) << x << " " << y << endl;
    }
    return 0;
}


Measured memory_bytes: 3272
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

const int mod = 998244353;
const int MX = 1000001;
ll inv[MX];
void calc(){
	inv[0] = inv[1] = 1;
	for (int i = 2; i < MX; i++) inv[i] = mod - mod / i * inv[mod % i] % mod;
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	calc();
	int n; cin >> n;
	vi sum(MX), sum2(MX);
	
	rep(i, n){
		int a; cin >> a;
		vi div;
		for(int j = 1; j * j <= a; j++) if(a % j == 0){
			div.pb(j);
			if(a != j * j) div.pb(a / j);
		}
		for(int d : div) (sum2[d] += a * (ll)sum[d] % mod) %= mod;
		for(int d : div) (sum[d] += a) %= mod;
	}
	
	ll ans = 0;
	for(int i = MX - 1; i > 0; i--){
		for(int j = i * 2; j < MX; j += i) (sum2[i] += mod - sum2[j]) %= mod;
		ans += sum2[i] * inv[i] % mod;
	}
	cout << ans % mod << endl;
	return 0;
}

Measured memory_bytes: 15872
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()

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

int main()
{
	int n;cin>>n;
	vector<int> a(n);
	rep(i,0,n-1)cin>>a[i];
	vector<int> L(n+1, 0), R(n+1, 0);
	rep(i,0,n-1){
		L[i+1] = gcd(L[i], a[i]);
	}
	for(int i=n-1; i>=0; --i){
		R[i] = gcd(R[i+1], a[i]);
	}
	int ans = 0;
	rep(i,0,n-1){
		ans = max(ans, gcd(L[i], R[i+1]));
	}
	cout<<ans<<endl;
}


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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int64_t root(vector<int64_t>& g, int64_t v) {
    if (g[v] != v) {
        g[v] = root(g, g[v]);
    }

    return g[v];
}

void merge(vector<int64_t>& g, int64_t v, int64_t u) {
    g[root(g, v)] = root(g, u);
}

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

    vector<int64_t> g(2 * n);
    iota(g.begin(), g.end(), 0L);

    for (auto i : irange(0L, n)) {
        int64_t p;
        cin >> p;
        --p;

        merge(g, i, n + p);
    }

    for (auto i : irange(0L, m)) {
        int64_t x, y;
        cin >> x >> y;
        --x;
        --y;

        merge(g, n + x, n + y);
    }

    int64_t ans = 0L;
    for (auto i : irange(0L, n)) {
        if (root(g, i) == root(g, n + i)) {
            ++ans;
        }
    }

    cout << ans << endl;
}

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

struct Node{
  int p, l, r;
};

Node T[100010];
int depth[100010];
int height[100010];

void rec( int s, int d = 0 ){
  depth[s] = d;
  if( T[s].r != -1 ) rec( T[s].r, d + 1 );
  if( T[s].l != -1 ) rec( T[s].l, d + 1 );
}

int rec2( int s ){
  int h1 = 0, h2 = 0;
  if( T[s].l != -1 ) h1 = rec2( T[s].l ) + 1;
  if( T[s].r != -1 ) h2 = rec2( T[s].r ) + 1;

  return height[s] = ( h1 > h2 ? h1 : h2 );
}

int degree( int v ){
  int res = 0;
  if( T[v].l != -1 ) res++;
  if( T[v].r != -1 ) res++;
  return res;
}

int sibling( int v ){
  if( T[v].p == -1 ) return -1;
  if( T[ T[v].p ].l != v ) return T[ T[v].p ].l;
  return T[ T[v].p ].r;
}

int main(){
  int N; cin >> N;
  for( int i = 0; i < 100010; i++ ) T[i].p = T[i].l = T[i].r = -1;

  for( int i = 0; i < N; i++ ){
    int id, left, right;
    cin >> id >> left >> right;

    T[id].l = left;
    T[id].r = right;
    T[left].p = id;
    T[right].p = id;
  }

  for( int i = 0; i < N; i++ ){
    if( T[i].p == -1 ){
      rec( i );
      rec2( i );
      break;
    }
  }
  
  for( int i = 0; i < N; i++ ){
    cout << "node " << i << ": " << "parent = " << T[i].p << ", "
	 << "sibling = " << sibling( i )
	 << ", degree = " << degree( i ) << ", "
	 << "depth = " << depth[i] << ", height = " << height[i] << ", ";
    
    if( T[i].p == -1 ) cout << "root";
    else if( T[i].l != -1 || T[i].r != -1 ) cout << "internal node";
    else cout << "leaf";
    cout << endl;
  }
  
}



Measured memory_bytes: 4276
dp = []
dist = []
INF = 1000000000

def tsp(s, v, dp, n):
    if dp[s][v] >= 0:
        return dp[s][v]
    if s == (1<<n)-1 and v == 0:
        dp[s][v] = 0
        return 0
    res = INF
    for u in range(n):
        if (s >> u & 1) == 0:
            res = min(res, tsp(s | (1 << u), u, dp, n) + dist[v][u])
    dp[s][v] = res
    return res
    
line = input()
v, e = list(map(int, line.split()))
dp = [ [-1] * v for _ in range(0, 1 << v)]
dist = [ [INF] * v for _ in range(0, v)]
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    dist[s][t] = d
ans = tsp(0, 0, dp, v)
print(ans if ans < INF else -1)


Measured memory_bytes: 15452
#include <iostream>
#include <math.h>
#include <cstdio>

using namespace std;

int main(){
	double x1, y1, x2, y2;
	double ans;
	
	cin >> x1 >> y1 >> x2 >> y2;
	ans = pow((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1), 0.5);
	
	printf("%.8f\n", ans);
	
	return 0;
} 

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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

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

void seica_add(ll &a,ll &b){
	a += b;
	if(a >= MOD)a -= MOD;
}

ll dp[3333][3333][2];

int main(){
	
	ll n,m;cin >> n >> m;
	
	REP(i,n+1){
		if(i == 0)dp[0][i][1] = 1;
		else dp[0][i][0] = 1;
	}
	
	REP(i,m){
		REP(j,n+1){
			REP(k,2){
				if(dp[i][j][k]){
					if(j > 0){
						if(j == 1){
							seica_add(dp[i+1][j-1][1],dp[i][j][k]);
							seica_add(dp[i+1][j][1],dp[i][j][k]);
						}
						else{
							seica_add(dp[i+1][j-1][k],dp[i][j][k]);
							seica_add(dp[i+1][j][k],dp[i][j][k]);
						}
					}
					
					if(j < n){
						seica_add(dp[i+1][j+1][k],dp[i][j][k]);
						seica_add(dp[i+1][j][k],dp[i][j][k]);
					}
				}
			}
		}
	}
	
	ll ans = 0;
	
	REP(i,n+1)seica_add(ans,dp[m][i][1]);
	
	cout << ans << endl;
						
	
	return 0;
}

Measured memory_bytes: 157952
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    rep(i,3){
        if(s[i]!=t[2-i])return NO,0;
    }
    YES;
}


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

struct node{
  int key;
  struct node *r,*l,*p;
};

typedef struct node Node;

Node *root,*nil;

void insert(int t){
  Node *x=root,*y=nil,*z;

  z=malloc(sizeof(Node));
  z->key = t;
  z->r=nil;
  z->l=nil;

  while(x!=nil){
    y=x;

    if(z->key < x->key){
      x = x->l;
    }
    else {
      x = x->r;
    }
  }

  z->p = y;
  if(y==nil)root = z;
  else {
    if(z->key < y->key){
      y->l = z;
    }
    else {
      y->r = z;
    }
  }
}

void inorder(Node *q){
  if(q==nil)return;

  inorder(q->l);
  printf(" %d",q->key);
  inorder(q->r);
}
void preorder(Node *q){
  if(q==nil)return;

  printf(" %d",q->key);
  preorder(q->l);
  preorder(q->r);
}

Node * find(int t){
  Node *aaa=root;

  while(1){
    if(aaa==nil){
      break;
    }
    else if(aaa->key == t){
      //printf("%d     %p p=%p l=%p r=%p\n",t,aaa,aaa->p,aaa->l,aaa->r);
      break;
    }
    else if(aaa->key < t){
      aaa = aaa -> r;
    }
    else {
      aaa = aaa-> l;
    }
  }

  return aaa;
}

void delete(int t){
  Node *aaa,*bbb,*ccc,*ddd,*eee;

  aaa = find(t);
  //printf("fff    key=%d nil=%p p=%p l=%p r=%p\n",aaa->key,nil,aaa->p,aaa->l,aaa->r);
  if(aaa->l == nil && aaa->r == nil){
    //printf("test0\n");
    if(aaa->p->l == aaa){
      aaa->p->l = nil;
    }
    else {
      aaa->p->r = nil;
    }
  }
  else if(aaa->l == nil || aaa->r == nil){
    if(aaa->p->l == aaa){
      if(aaa->l!=nil){
	aaa->p->l = aaa->l;
	aaa->l->p = aaa->p;
      }
      else {
	aaa->p->l = aaa->r;
	aaa->r->p = aaa->p;
      }
    }
    else {
      if(aaa->l!=nil){
	aaa->p->r = aaa->l;
	aaa->l->p = aaa->p;
      }
      else {
	aaa->p->r = aaa->r;
	aaa->r->p = aaa->p;
      }
    }
  }
  else {
    //printf("test1\n");
    bbb = aaa->r;
    while(1){
      if(bbb == nil)break;

      ccc = bbb;
      bbb = bbb->l;
    }
    //printf("test2\n");
    aaa->key = ccc->key;


    
    
    
    //printf("test3\n");
    if(ccc->r!=nil)
    ccc->r->p = ccc->p;



    
    //printf("test3.1\n");
    if(ccc->p == aaa){
      // printf("test3.2\n");
      ccc->p->r = ccc->r;
    }
    else{
      // printf("test3.3\n");
      ccc->p->l = ccc->r;
    }
    // printf("test4\n");
    aaa = ccc;
  }
  free(aaa);
}   

int main(){
  int n,i,j,t;
  char s[10];
  Node *k;

  root = nil;
  
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",s);
    if(s[0]=='i'){
      scanf("%d",&t);
      insert(t);
    }
    else if(s[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(s[0]=='f'){
      scanf("%d",&t);
      k = find(t);
      if(k==nil)printf("no\n");
      else printf("yes\n");
    }
    else if(s[0]=='d'){
      scanf("%d",&t);
      delete(t);
    }
  }
  return 0;
}



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

int N, A;
int X[55];
int64_t dp[55][2510][55];

int main()
{
	cin >> N >> A;
	for (int i = 0; i < N; ++i) {
		cin >> X[i];
	}
	dp[0][0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= A * N; ++j) {
			for (int k = 0; k <= N; ++k) {
				if (j >= X[i]) {
					dp[i + 1][j][k] = dp[i][j - X[i]][k - 1] + dp[i][j][k];
				}
				else {
					dp[i + 1][j][k] = dp[i][j][k];
				}
			}
		}
	}
	int64_t v = 0;
	for (int i = 1; i <= N; ++i) {
		v += dp[N][A * i][i];
	}
	cout << v << endl;
	return 0;
}

Measured memory_bytes: 54400
#include <stdio.h>
#define MAX_N 100000

int a[MAX_N] = {0};
bool lighten[MAX_N] = {false};

int dfs(void)
{
    int i = 0, cnt = 0;
    for (;;) {
        if (lighten[1]) return cnt;
        i = a[i] - 1;
        if (lighten[i]) return -1;
        lighten[i] = true;
        cnt++;
    }
}

int main(void)
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    lighten[0] = true;
    printf("%d\n", dfs());
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;


const long long  MAX = 200000;
int main() {
    

    long long R[MAX], n;

    cin >> n;
    for (long long i=0;i<n;i++){
        cin >> R[i];
    }
    long long maxv = -2000000000;
    long long minv = R[0];
    for (int i=1;i<n;i++){
        maxv = max(maxv,R[i]-minv);
        minv = min(minv,R[i]);
    }
    cout << maxv << endl;


}


Measured memory_bytes: 4680
#include<stdio.h>
#define SIZE 200002
int main(){
    int N,all=0;
    scanf("%d",&N);
    int a[SIZE],ans[SIZE];
    for(int i=0;i<N;i++)
        scanf("%d",a+i);
        for(int i=0;i<N;i++)
            all ^= a[i];
        for(int i=0;i<N;i++)
            ans[i] = all ^ a[i];
    for(int i=0;i<N;i++)
        printf("%d ",ans[i]);
}

Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

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

    ll num;
    cin >> num; 
    cout << (1000 - num % 1000) % 1000 << endl;

    return 0;
}

Measured memory_bytes: 3684
import sys
n = int(input())
l = input().split()
count = 0
l = [int(i) for i in l]
for i in range(n-2):
    tmp = l[i:i+3]
    c = tmp[1]
    changed = sorted(tmp)
    if c == changed[1]:
        count += 1
print(count)


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int>P;
#define INF 1000000000000000
int n, k;
vector<int>can[5005];
long long cost[5005][5005] = { 0 };
long long c[5005] = { 0 };
long long d[5005] = { 0 };
int r[5005] = { 0 };

void bfs(int s) {
	long long far[5005] = { 0 };
	int visited[5005] = { 0 };
	for (int j = 0; j < 5005; j++) far[j] = INF;
	far[s] = 0;
	visited[s] = 1;
	queue<int>que;
	que.push(s);
	while(!que.empty()) {
		int now = que.front();
		que.pop();
		for (int j = 0; j < can[now].size(); j++) {
			int next = can[now][j];
			if (!visited[next]) {
				far[next] = far[now] + 1;
				visited[next] = 1;
				que.push(next);
			}
		}
	}
	for (int j = 0; j < n; j++) {
		if (1 <= far[j] && far[j] <= r[s]) {
			cost[s][j] = c[s];
		}
	}
	return;
}

void dijkstra() {
	int used[5005] = { 0 };
	for (int i = 0; i < 5005; i++) d[i] = INF;
	d[0] = 0;
	while (true) {
		int v = -1;
		for (int u = 0; u < n; u++) {
			if (!used[u] && (v == -1 || d[v] > d[u])) v = u;
		}
		if (v == -1) break;
		used[v] = true;
		for (int i = 0; i < n; i++) {
			if (v != i) d[i] = min(d[i], d[v] + cost[v][i]);
		}
	}
	return;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> c[i] >> r[i];
		d[i] = INF;
	}
	for (int i = 0; i < 5005; i++) {
		for (int j = 0; j < 5005; j++) {
			if (i != j) cost[i][j] = INF;
		}
	}
	d[0] = 0;
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		can[a].push_back(b);
		can[b].push_back(a);
	}
	for (int i = 0; i < n; i++) {
		bfs(i);
	}
	/*for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	if (cost[i][j] != INF) cout << cost[i][j] << endl;
	}
	}*/
	dijkstra();
	cout << d[n - 1] << endl;
	return 0;
}



Measured memory_bytes: 199284