akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <complex>
#include <iostream>
#include <string>
//#include <math>
using namespace std;
typedef long long ll;
ll M = 500000000000;
ll power(ll x, ll n){
  ll res = 1;
  while(n>0){
    if(n&1) res *= x;
    x = x*x;
    n >>= 1;
  }
  return res;  
}

int main(){
  string S;
  ll K;
  cin >> S >> K;

  /*ll search=0;
  int i = 0;
  while(search < K){
    int x = S[i]-'0';
    search += power(x,M);
    i++;
  }
  cout << S[i-1] <<endl;*/

  int ans = 1;
  for(int i=0;i<K;i++){
    if(S[i]!='1'){
      ans = S[i] - '0';
      break;
    }
  }
  cout << ans <<endl;


  return 0;
}

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

typedef long long ll;

int a,b;

int main(){
	cin >> a >> b;
	char res = 'x';
	if(a*b == 15) {
		res = '*';
	} else if (a+b == 15){
		res = '+';
	}
	cout << res << endl;
}

Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] a = new int[n];
		Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
		for (int i = 0; i < n; i++) {
			int k = sc.nextInt();
			a[i] = k;
			map.put(k, i);
		}
		int[] b = new int[n];
		int id = 0;
		for (Integer value : map.keySet()) {
			b[map.get(value)] = id++;
		}

		int sum = 0;
		for (int i = 0; i < n; i += 2) {
			if (b[i] % 2 == 1) {
				sum++;
			}
		}
		System.out.println(sum);
	}

	public static void main(String[] args) {
		new Main().run();
	}
}


Measured memory_bytes: 29172
from collections import Counter

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

sushis = [[0 for _ in range(2)] for _ in range(n)]
cnt_sushi_type = {}
for i in range(n):
  t,p = map(int, input().split())
  sushis[i][0] = -p #ポイント、大きいものから取り出したいのでマイナスにして入れる
  sushis[i][1] = t #種類

cnt_types = Counter() #寿司の種類覚えておく用のdict

sushis.sort(key=lambda x:x[0])

sushi_set = []
ans = 0
for p, t in sushis[:k]:
  #大きいものからk個選んで得点を計算
  ans += -p
  cnt_types[t] += 1
  sushi_set.append([p,t]) #集合を保存
  
ans += len(cnt_types) ** 2 #ネタ数＊ネタ数を加点

##ここまで貪欲選択


max_types = []
max_types.append(ans)
#max_types[len(cnt_types)] = ans
for p, t in sushis[k:]: #これまで選んでないものを選択した場合についてみていく
  if t in cnt_types:
    continue #選んでない種類のネタを選びたいので、すでに選んでるネタであれば何もせず飛ばす
  else:
    #選んだ寿司集合にある一番得点の低い寿司を、現在見ている新ネタの寿司と入れ替える
    #実際に入れ替えるとめんどくさい（計算量的にappendとかしんどい）ので、ansとcnt_typesをいじることで調整する

    while sushi_set:
      ps, ts = sushi_set.pop() #小さい順で取り出す
      if cnt_types[ts] >= 2:
        #そのネタが2個以上あるなら一個減らして新セットを作る
        tmp =  max_types[-1]- (-ps) + (-p) + 2*len(cnt_types) + 1
        max_types.append(tmp)
        cnt_types[t] += 1
        cnt_types[ts] -= 1
        break #次のまだ見ぬネタを探しに行く
        
#各種類選んだ最大値から最大のものを選択で終了
print(max(max_types))
      

Measured memory_bytes: 35576
A = gets.to_i
B = gets.to_i
C = gets.to_i
X = gets.to_i

count = 0
0.upto(A).each do |i|
  0.upto(B).each do |j|
    0.upto(C).each do |k|
      count += 1 if 500 * i + 100 * j + 50 * k == X
    end
  end
end

puts count

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

const ll INF = 1LL << 60;

vector<int> G[(int)1e5 + 5];

int color[(int)1e5 + 5];
ll N, M;

bool dfs(int v, int c) {
    color[v] = c;
    for (int i = 0; i < G[v].size(); i++) {
        // 隣接している頂点が同じ色
        if (color[G[v][i]] == c) return false;

        // 隣接している頂点がまだ塗られていない
        if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
    }

    return true;
}

int main() {
    cin >> N >> M;
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 二部グラフかどうかの判定フラグ
    bool nibu = true;
    for (int i = 0; i < N; i++) {
        if (color[i] == 0) {
            if (!dfs(i, 1)) {
                nibu = false;
                break;
            }
        }
    }

    if (nibu) {
        // 二部グラフの場合、異なる色通しで辺ができる
        // b2: 黒色で塗る
        // w2: 白色で塗る

        // // 1. 通らないパターン
        // ll b2 = 0, w2 = 0;
        // b2 = N / 2;
        // w2 = N - b2;

        // 2. 通るパターン (1個ずつカウントアップ)
        ll b2 = 0, w2 = 0;
        rep(i, N) {
            if (color[i] == 1) {
                b2++;
            } else {
                w2++;
            }
        }
        b2 = N - w2;
        // w2 = N - b2; (置き換えても通る)

        ll ans = b2 * w2 - M;
        cout << ans << endl;
    } else {
        // 全部の辺 - M
        ll ans = N * (N - 1) / 2;
        ans -= M;

        cout << ans << endl;
    }
}

Measured memory_bytes: 9832
import math

def main():
  N, K = map(int, input().split())
  H = list(map(int, input().split()))
  
  if K >= N:
    print(0)
    return
  
  #ans = 0
  l = sorted(H, reverse=True)
  
  # del l[:K]
  # print(l)
  
  # ans += sum(l)
  
  print(sum(l[K:]))
  #print(ans)
  
  
main()

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

#define REP(i,n) for(int i=0;i<int(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define MSG(x) cout<<"#x"<<" "<<x<<endl;

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

int vx[]={0,0,-1,1};
int vy[]={1,-1,0,0};
int dx[]={1,0,-1,1,-1,1,0,-1};
int dy[]={1,1,1,0,0,-1,-1,-1};

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}	 

const ll mod=1e9+7;
const int INF=INT_MAX/2;

int N;

int main(){
    cin>>N;
    int res=INF;
    for(int i=1;i<N/2+1;i++){
        int a=i;
        int b=N-a;
        int sum=0;
        while(a>0){
            sum+=a%10;
            a/=10;
        }
        while(b>0){
            sum+=b%10;
            b/=10;
        }
        res=min(res,sum);
    }
    cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<int> l(n); REP(i, n) cin >> l[i];
  sort(ALL(l));
  int sum = 0;
  REP(i, n-1) sum += l[i];
  cout << (l[n-1] < sum ? "Yes" : "No") << '\n';
  return 0;
}


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

int n, m;

int main(){
    typedef pair<string, int> P;
    int n;
    cin >> n;
    vector<int> p(101, -1);
    string s;
    int t;
    vector<P> tmp(n);
    for (int i = 1; i <= n; i++){
        cin >> s >> t;
        tmp[i-1].first = s;
        tmp[i-1].second = -t;
        p[t] = i;
    }
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < n; i++){
        cout << p[-(tmp[i].second)] << endl;
    }
}








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

int p,q,r;

char perse(string x){
  string tmp;
  int n,c;
  char op,a,b;
  if(x[0] == '-'){
    x.erase(x.begin());
    return '0' + '2' - perse(x);
  }
  if(x[0] == '('){
    tmp.clear();
    n = 1;
    c = 0;
    while( c || (x[n] != '+' && x[n] != '*') ){
      if(x[n] == '(')c++;
      if(x[n] == ')')c--;
      tmp.push_back(x[n]);
      n++;
    }
    a = perse(tmp);
    op = x[n];

    tmp.clear();
    n++;
    while( c || x[n] != ')' ){
      if(x[n] == '(')c++;
      if(x[n] == ')')c--;
      tmp.push_back(x[n]);
      n++;
    }
    b = perse(tmp);

    if(op == '+'){
      if(a=='2' || b=='2')return '2';
      else if(a=='1' || b=='1')return '1';
      else return '0';
    }else if(op == '*'){
      if(a=='0' || b=='0')return '0';
      else if(a=='1' || b=='1')return '1';
      else return '2';
    }
  }

  if(x[0] == 'P')return '0' + p;
  if(x[0] == 'Q')return '0' + q;
  if(x[0] == 'R')return '0' + r;

  return x[0];
}
 
int main(){

  int c;
  string s;

  while(1){
    cin >> s;
    if(s==".")break;

    c = 0;
    for(p=0;p<3;p++){
      for(q=0;q<3;q++){
	for(r=0;r<3;r++){
	  if(perse(s) == '2')c++;
	}
      }
    }

    cout << c << endl;
  }
}

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

int n, d;
int x[100][100];

int main() {
    cin >> n >> d;
    for(int i = 0; i < n; i++) {
        for(int k = 0; k < d; k++) {
            cin >> x[i][k];
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j)
                continue;
            int sqsum = 0;
            for(int k = 0; k < d; k++) {
                sqsum += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
            }
            int sq = sqrt(sqsum);
            ans += (sq*sq == sqsum);
        }
    }

    cout << ans / 2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)
#define MAX_HW 2000

using namespace std;
typedef pair<int, int> ipair;

int mp[MAX_HW + 2][MAX_HW + 2], sp1[MAX_HW + 2][MAX_HW + 2];
int H, W;
int main(int argc, char **argv) {
    cin >> H >> W;
    for(int i = 0; i < H; ++i)
        for(int j = 0; j < W; ++j) {
            char ch;
            cin >> ch;
            mp[i][j] = (ch == '#' ? 1 : 0);
        }
    
    for(int i = 0; i < H; ++i) {
        int cur = 0;
        for(int j = 0; j < W; ++j) {
            if(mp[i][j] == 1) {
                cur = 0;
            } else {
                sp1[i][j] += cur;
                cur++;
            }
        }
    }

    for(int i = 0; i < H; ++i) {
        int cur = 0;
        for(int j = W - 1; j >= 0; --j) {
            if(mp[i][j] == 1) {
                cur = 0;
            } else {
                sp1[i][j] += cur;
                cur++;
            }
        }
    }

    for(int j = 0; j < W; ++j) {
        int cur = 0;
        for(int i = 0; i < H; ++i) {
            if(mp[i][j] == 1) {
                cur = 0;
            } else {
                sp1[i][j] += cur;
                cur++;
            }
        }
    }

    for(int j = 0; j < W; ++j) {
        int cur = 0;
        for(int i = H - 1; i >= 0; --i) {
            if(mp[i][j] == 1) {
                cur = 0;
            } else {
                sp1[i][j] += cur;
                cur++;
            }
        }
    }

    int res = -INF;
    
    for(int i = 0; i < H; ++i)
        for(int j = 0; j < W; ++j)
            res = max(res, sp1[i][j]);
    
    cout << (res + 1) << endl;
}

Measured memory_bytes: 31616
from itertools import product

h, w, k = map(int, input().split())
c = [input() for _ in range(h)]

ans = 0
for hl in product([0, 1], repeat=h):
    for wl in product([0, 1], repeat=w):
        cij = [list(c[i]) if hi == 0 else list('r' * w)
               for i, hi in enumerate(hl)]
        for j, wj in enumerate(wl):
            if wj == 1:
                for i in range(h):
                    cij[i][j] = 'r'
        cnt = 0
        for s in cij:
            cnt += sum(si == '#' for si in s)
        if cnt == k:
            ans += 1
print(ans)


Measured memory_bytes: 9036
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on

void main()
{
    long N = lread();
    writeln(N * 800 - N / 15 * 200);
}


Measured memory_bytes: 3592
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(), b = sc.nextInt();
		sc.close();
		int cnt = (b + a - 3) / (a - 1);
		System.out.println(cnt);
	}
}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef long double ld;
const ld pi = 4*atan((ld)1);
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll nax = 0;

ll n;

ll pangkat(ll x, ll y){
	if(y == 0){
		return 1;
	}
	ll temp = pangkat(x, y / 2);
	if(y & 1){
		return temp * temp % mod * x % mod;
	}
	else{
		return temp * temp % mod;
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	ll ans = pangkat(10, n);
	if(n == 1){
		cout << "0\n";
		return 0;
	}
	ans -= (pangkat(9, n) - pangkat(8, n) + mod)  % mod;
	ans -= (pangkat(9, n) - pangkat(8, n) + mod)  % mod;
	ans -= pangkat(8, n);
	ans = (((ans % mod) + mod) % mod);
	cout << ans << '\n';
}



Measured memory_bytes: 3648
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by shoya on 2017/04/12.
 */
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        PrintWriter pwout = new PrintWriter(System.out);
        for(Integer i : rabinKarp(str2, str1))
            pwout.println(i);
        pwout.flush();
        return;
    }

    static ArrayList<Integer> rabinKarp(String str1, String str2){
        ArrayList<Integer> list = new ArrayList<>();
        if (str1.length() > str2.length())
            return list;

        final long RADIX = Long.parseUnsignedLong("100000007");
        long t = 1, str1hash = 0, str2hash = 0;
        for (int i = 0; i < str1.length(); i++) {
            t *= RADIX;
            str1hash = str1hash * RADIX + str1.charAt(i);
            str2hash = str2hash * RADIX + str2.charAt(i);
        }
        for (int i = 0; i + str1.length() <= str2.length(); i++) {
            //System.out.println(Long.toUnsignedString(str1hash));
            //System.out.println(Long.toUnsignedString(str2hash));
            //System.out.println();
            if (str1hash == str2hash)
                list.add(i);
            if (i + str1.length() < str2.length()) {
                str2hash = str2hash * RADIX + str2.charAt(i + str1.length()) - str2.charAt(i) * t;
                //System.out.println(Long.toUnsignedString(str2hash));
            }
        }
        return list;
    }
}

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

using namespace std;

int main()
{
    long long int a, b, k, temp;      cin >> a >> b >> k;
    
    temp = k;
    k -= a;     a -= temp;
    
    if(a < 0)
        a = 0;
    
    if(k > 0)
    {
        temp = k;
        k -= b;     b -= temp;
    }

    if(b < 0)
        b = 0;
        
    cout << a << " " << b << endl;

    return 0;
}


Measured memory_bytes: 256
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
//チェックリストはマップを使う
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//またはかかつか
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//数が大きい時のせぐふぉはコードテストで試してみる
//スペルミスに注意
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
//関係性は隣接行列で記録
//過半数：N/2.0で判定
//ある量からある量を引く系の問題：端から定義してやる
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

//円周率
const double PI = 3.14159265358979323846;
//割るやつ
const ll M = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1)) % M;
}

//Nのd桁目の数
ll dignum(ll N, ll d) {
	ll x = pow(10, d);
	N %= x;
	ll y = pow(10, d - 1);
	N /= y;
	return N;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

int main() {
	ll N; cin >> N;
	int c = dignum(N,dig(N,10));
	int f = 0;
	for (int i = 1; i <= dig(N, 10) -1; i++) {
		if (dignum(N, i) != 9) f = 1;
	}

	if (f == 0) cout << c + 9 * (dig(N, 10) - 1) << endl;
	else cout << (c - 1) + 9 * (dig(N, 10) - 1) << endl;
}

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

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

int main(){
	
	int N,L[3000],i,ans=0,j,k;
	scanf("%d",&N);
	
	for(i=0;i<N;i++){
		scanf("%d",&L[i]);
	}
	
	qsort(L,N,sizeof(int),compare);
	
	
	for(i=0;i<N;i++){
		for(j=i+1;j<N;j++){
			for(k=j+1;k<N;k++){
			if((L[i]<L[j]+L[k])&&(L[j]<L[k]+L[i])&&(L[k]<L[i]+L[j])){
				ans++;
			}
			}
		}
	}
	
	
	printf("%d",ans);
	
	return 0;
}

Measured memory_bytes: 252
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int n,sum,m;
    cin>>n;
    sum=0;
    for (int i=1;i<sqrt(n);i++)
     { if (n%i==0)
        { m=(n/i)-1;
          if (m-i>0)sum+=m;
        }
         
     }
     cout<<sum;
    return 0;    
}

Measured memory_bytes: 256
from fractions import gcd

def mi():
    return map(int, input().split())

def main():
    N = int(input())
    b = list(mi())
    a = []
    for i in range(N):
        bl = False
        for j, v in enumerate(b):
            if v == j+1:
                t = j
                bl = True
        if bl:
            a.append(b.pop(t))
        else:
            print(-1)
            return
    
    for v in reversed(a):
        print(v)



if __name__ == '__main__':
    main()

Measured memory_bytes: 64364
//                        DushtuBunny
//                        Rahul Halder    
//    Indian Institute of Engineering Science & Technology,Shibpur


#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll int64_t
#define f first
#define se second
#define LB lower_bound
#define UB upper_bound
#define pb push_back
#define mp make_pair
#define vll vector<ll>
#define vi vector<int>
#define vc vector<char>
#define vpll vector<pair<ll,ll>>
#define pll pair<ll,ll>
const unsigned int MOD = 1000000007;

using namespace std;

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

    IOS;
    int T;
    // cin>>T;
    T=1;

    while(T--)
    {
        ll n,k;cin>>n>>k;
        ll a[n+1];
        for(int i=1;i<=n;i++)cin>>a[i];

        map<int,int>m;
        vll v,rotate;
        ll index = -1,i=a[1];
        m[1]=1;
        v.pb(1);
        while(m[i]!=1)
        {
            m[i]=1;
            v.pb(i);
            i = a[i];
        }

        rotate.pb(i);
        ll count = 0;
        i=a[i];

        while(i!=rotate[0])
        {
            rotate.pb(i);
            i=a[i];
            count++;
        }
        if(k<v.size())
            cout<<v[k];
        else
            cout<<rotate[(k-v.size())%(rotate.size())];
    }
  
    return 0;
}


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

vector< vector< vector<bool> > > V;
int n, m, p;
bool t;
int X[1000], Y[1000];

bool check(int x, int y, int z) {
  for (auto i=-1; i<=1; i++) {
    for (auto j=-1; j<=1; j++) {
      for (auto k=-1; k<=1; k++) {
	if (i==0 && j==0 && k==0) continue;
	for (auto l=1; l<m; l++) {
	  int tempx = x+l*i;
	  int tempy = y+l*j;
	  int tempz = z+l*k;
	  if (!(0<=tempx &&  tempx<n && 0<=tempy && tempy<n)
	      || !(0 <= tempz && tempz < V[tempx][tempy].size())
	      || (V[tempx][tempy][tempz] != t)) goto EXIT;
	}
	return true;
      EXIT:
	continue;
      }
    }
  }
  return false;
}

bool win() {
  for (auto i=0; i<n; i++) {
    for (auto j=0; j<n; j++) {
      for (auto k=0; k<V[i][j].size(); k++) {
	if (V[i][j][k] == t && check(i, j, k)) {
	  return true;
	}
      }
    }
  }
  return false;
}

void init() {
  V = vector< vector< vector<bool> > > 
    (n, vector< vector<bool> >(n, vector<bool>()));
  t = true;
  for (auto i=0; i<p; i++) {
    cin >> X[i] >> Y[i];
    X[i]--; Y[i]--;
  }  
}

void solve() {
  init();
  for (auto i=0; i<p; i++) {
    V[X[i]][Y[i]].push_back(t);
    if (win()) {
      cout << (t ? "Black" : "White") << " " << (i+1) << endl;
      return;
    }
    t = !t;
  }
  cout << "Draw" << endl;
}

int main() {
  while (cin >> n >> m >> p && n) {
    solve();
  }
}

Measured memory_bytes: 1220
import sys
sys.setrecursionlimit(10**6)

#a = int(input())
#b = list(map(int, input().split()))
d, t, s = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

if d/s <= t:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9156
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iomanip>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<numeric>

#define int long long

using namespace std;

int INF = 1e16 + 7;

void solve() {
    int x;
    cin >> x;
    cout << (x >= 30 ? "Yes" : "No");
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    solve();

    return 0;
}

Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char s[105],t[105];
int main()
{
	scanf("%d",&n);
	scanf("%s%s",s,t);
	for(int i=0;i<n;++i)
	{
		putchar(s[i]);
		putchar(t[i]);
	}
	puts("");
	return 0;
} 

Measured memory_bytes: 256
/*dismint|jjc*/
#include <bits/stdc++.h>
using namespace std;
#define forl(V, S, E) for(int V = S; V < E; V++)
#define ford(V, S, E) for(int V = S; V >= E; V--)
#define fore(E, X) for(auto &E:X)
#define println(X) cout << X << endl
#define printe(X) for(auto &E:X) cout << E << " "; cout << endl
typedef unordered_map<int, unordered_set<int>> graph;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int a, b, c; cin >> a >> b >> c;
	if(a+b+c > 21) println("bust");
	else println("win");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<l_l> vpl;
typedef vector<string> vs;
typedef pair<l_l,ll> lll;
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=1;i<=(n);i++)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=10100100100100100;
const ll dx[4]={1,-1,0,0};
const ll dy[4]={0,0,1,-1};
template<class T> inline bool chmin(T& a,T b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a,T b){
if(a<b){
a=b;
return true;
}
return false;
}
ll h,w;
ll vis[1010][1010];
int main(){
    cin>>h>>w;
    vs g(h);
    rep(i,h)cin>>g[i];
    queue<lll> q;
    rep(i,1010){
        rep(j,1010){
            vis[i][j]=-1;
        }
    }
    rep(i,h){
        rep(j,w){
            if(g[i][j]=='#'){
                q.push({{i,j},0});
                vis[i][j]=0;
            }
        }
    }
    while(q.size()){
        lll now=q.front();q.pop();
        ll nowx=now.fi.fi,nowy=now.fi.se,nowc=now.se;
        rep(i,4){
            if(nowx+dx[i]<0||nowx+dx[i]>=h||nowy+dy[i]<0||nowy+dy[i]>=w)continue;
            if(vis[nowx+dx[i]][nowy+dy[i]]>=0)continue;
            q.push({{nowx+dx[i],nowy+dy[i]},nowc+1});
            vis[nowx+dx[i]][nowy+dy[i]]=nowc+1;
        }
    }
    ll ans=0;
    rep(i,h){
        rep(j,w){
            chmax(ans,vis[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 37264
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

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

    long long x, y;
    cin >> x >> y;
    long long det = abs(x-y);
    if(det > 1) cout << "Alice";
    else cout << "Brown";

    return 0;
}


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

 using namespace std;

 int main() {
   int N, M, X, Y;

   cin >> N;

   if (N <= N / 100 * 111) cout << N / 100 * 111 << endl;
   else cout << (N / 100 + 1) * 111 << endl;

}


Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int i,j,k,num,A[1000],min,tmp,cnt=0;
  scanf("%d",&num);
  for(i=0;i<num;i++){
    scanf("%d",&A[i]);
  }
  

  for(j=0;j<num;j++){
 min=j;
    for(k=j;k<num;k++){
     

      if(A[min]>A[k]){
	min=k;
        
      }
    }

      if(A[j]!= A[min]){
	tmp=A[j];
	A[j]=A[min];
	A[min]=tmp;
	cnt++;
      }
    
  }
  for(i=0;i<num-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[i]);
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 604
import numpy as np
a,b,c,d = (int(i) for i in input().split())
if  np.abs(a - c)  <= d:
    print('Yes')
elif a <= b <= c and c-a < 2*d:
    print('Yes')
elif c <= b <= a and a-c < 2*d:
    print('Yes')
else :
    print('No')

Measured memory_bytes: 12500
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cpr = ((cpr * 2) + int(b)) % (C+1)

    for b  in X:
        if C-1 != 0:
            cmr = ((cmr * 2) + int(b)) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()


Measured memory_bytes: 95516
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[][] c = new int[3][3];
		for(int i=0;i<3;i++) {
			for(int j=0;j<3;j++) {
				c[i][j] = in.nextInt();
			}
		}
		int[] sum = new int[6];
		sum[0] = c[0][0] + c[1][1] + c[2][2];
		sum[1] = c[0][1] + c[1][2] + c[2][0];
		sum[2] = c[0][2] + c[1][0] + c[2][1];
		sum[3] = c[0][0] + c[1][2] + c[2][1];
		sum[4] = c[0][1] + c[1][0] + c[2][2];
		sum[5] = c[0][2] + c[1][1] + c[2][0];
		boolean takahashi = true;
		for(int i=1;i<6;i++) {
			if(sum[0]!=sum[i]) {
				takahashi = false;
				break;
			}
		}
		if(takahashi) System.out.println("Yes");
		else System.out.println("No");
		in.close();

	}

}


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

int main()
{

        long long N;
        cin >> N;

        long long cnt = sqrt(N)+1;

        long long min = 0;
        for (long long i = 1; i < cnt; ++i) {

                long long s = N / i;
                if (N%i == 0) {
                        string ss1 = to_string(s);
                        string ss2 = to_string(i);
//                      cout << "ss1,ss2= " << ss1 << "," << ss2 << endl;
                        int tmp = std::max(ss1.length(), ss2.length());
//                      cout << "tmp= " << tmp << endl;
                        if (min == 0) {
                                min = tmp;
                        }
                        else if (min > tmp) {
                                min = tmp;
                        }
                }


        }
        cout << min << endl;



}


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

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


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T & a, const T & b) {
	if (a < b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T & a, const T & b) {
	if (a > b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}


#define ARRAY_MAX 100005
const int INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };


/******************************************************************************************/


int dp[1000][10000];

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		cout << 'x';
	}
	cout << endl;




	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string>

using namespace std;

const int mod = 1000000007;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main()
{
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int x12 = x2 - x1;
    int y12 = y2 - y1;
    int x3 = x2 - y12;
    int y3 = y2 + x12;
    int x4 = x1 - y12;
    int y4 = y1 + x12;

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define pb push_back

typedef long long ll;
typedef pair<int,int> pi;
const int MAXN = (int)1e3+7;
const double INF = (double)1e18+7;

int N,M;
int deg[MAXN];
vector<int> in[MAXN],out[MAXN];
double dp[MAXN][2],prob[MAXN];
queue<int> qu;

int main()
{
    scanf("%d %d",&N,&M);
    rep(i,1,M) {
        int u,v;
        scanf("%d %d",&u, &v);
        out[u].pb(v);
        in[v].pb(u);
        deg[u] ++;
    }
    rep(i,0,N) rep(j,0,N) dp[i][j]=INF;
    dp[N][0] = dp[N][1] = 0;
    rep(i,1,N) if (deg[i] == 0) qu.push(i);

    while (!qu.empty()) {
        int k = qu.front();qu.pop();
        for(int v:in[k]) if(--deg[v]==0) qu.push(v);
        int num = 0;
        double pro = 0.0;
        for(int v:out[k]) num ++,pro += dp[v][0];
        if (num == 0) {
            continue ;
        }else if (num == 1) {
            for (int v:out[k]) dp[k][0] = dp[v][0]+1,dp[k][1] = dp[k][0];
        }else {
            dp[k][0] = pro/num+1;
            for (int v:out[k]) dp[k][1] = min(dp[k][1],(pro-dp[v][0])/(num-1)+1);
        }
    }
    prob[1] = 1.0;
    double ans = INF;
    rep(i,1,N-1) {
        double probb = prob[i]/out[i].size();
        for(int v:out[i]) prob[v]+=probb;
        //cout << dp[1][1] << " " << prob[i] << " " << dp[i][0] << " " << dp[i][1] << endl;
        ans = min(ans,dp[1][0]-prob[i]*(dp[i][0]-dp[i][1]));
    }


    printf("%.15f\n",ans);
}

/*
3.26333 1 3.26333 3.106
3.26333 0.166667 2.64 2.425
3.26333 0.166667 3.05 2.9
3.26333 0.166667 2.94 2.8
3.26333 0.275 2.45 2.1875
3.26333 0.163333 2.25 1.83333
3.26333 0.370833 2.5 2.5
3.26333 0.5 1.5 1
3.26333 0.454167 1 1
3.0133333333
*/


Measured memory_bytes: 2688
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <map>

#define INF 100100100
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

 
int main(){
    string s; cin >> s;
    string t = s;
    reverse(t.begin(), t.end());
    int n = s.size();
    int ans = 0;
   
        for(int i=0; i<=n/2-1; i++){
            if(s[i] != t[i]) ans++;
        }
        cout << ans << endl;
        return 0;
    
     
}


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


int main() {
	long N;
	cin >> N;
	vector<long> Np;
	for (long i = 1; i <= sqrt(N); i++)
	{
		if (N%i==0)
		{
			Np.push_back(i);
		}
	}
	if (Np.back()==1)
	{
		cout << N - 1;
	}
	else {
		//cout << Np.back() << endl;
		cout << Np.back() + N / Np.back()-2;
	}
}



Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <functional>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>

template <class Integer>
auto boost_irange(Integer last) { return boost::irange(static_cast<Integer>(0), last); }
template <class Integer>
auto boost_irange(Integer first, Integer last) { return boost::irange(first, last); }

class input
{
    std::istream& cin;

public:
    input() : cin(std::cin)
    {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }

    template <class T>
    inline input& operator>>(T& var)
    {
        cin >> var;
        return *this;
    }
    template <class T>
    inline input& operator,(T& var)
    {
        cin >> var;
        return *this;
    }

    template <class T>
    inline T read()
    {
        T var;
        cin >> var;
        return var;
    }

    template <class InputIterator>
    inline void read(InputIterator head, std::size_t n)
    {
        for (std::size_t i = 0; i < n; ++i) {
            cin >> *head;
            ++head;
        }
    }

    template <class T, class F>
    inline void online(std::size_t n, F&& f)
    {
        T var;
        for (std::size_t i = 0; i < n; ++i) {
            cin >> var;
            f(var);
        }
    }
};
template <class T, std::size_t n>
std::istream& operator>>(std::istream& in, std::array<T, n>& var)
{
    for (std::size_t i = 0; i < n; ++i) {
        in >> var[i];
    }
    return in;
}

class output
{
    std::ostream& cout;

public:
    class proxy
    {
        std::ostream& cout;

    public:
        proxy() : cout(std::cout) {}
        ~proxy() { cout << std::endl; }
        template <class T>
        proxy& operator,(T&& val)
        {
            cout << val << ' ';
            return *this;
        }
    };

public:
    output() : cout(std::cout) {}
    template <class T>
    proxy operator<<(T&& val)
    {
        cout << val << ' ';
        return {};
    }
};

template <class T, std::size_t n>
class StaticVector : public boost::container::static_vector<T, n>
{
    using Parent = boost::container::static_vector<T, n>;

public:
    // is_constructible_v >= C++17
    template <class... Args, std::enable_if_t<std::is_constructible<Parent, Args&&...>::value, std::nullptr_t> = nullptr>
    StaticVector(Args&&... args) : Parent(std::forward<Args>(args)...) {}
    StaticVector(input& in, std::size_t n_) : Parent(n_)
    {
        for (std::size_t i = 0; i < n_; ++i) in >> static_cast<Parent&>(*this)[i];
    }
};

int main()
{
    input in;
    output out;
    long N = in.read<int>();

    out << N * (N - 1) / 2;

    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.LongStream;

public class Main {

	public static final MyScanner in = new MyScanner();

	public static final Map<Integer, Integer> map = new HashMap<>();


	public static void main(String[] args) {

		int X = in.nextInt();
		int Y = in.nextInt();
		int A = in.nextInt();
		int B = in.nextInt();
		int C = in.nextInt();
		long[] p = new long[A];
		long[] q = new long[B];
		long[] r = new long[C];

		long sum = 0L;
		for(int i=0;i<A;i++) {
			p[i] = in.nextLong();
		}

		for(int i=0;i<B;i++) {
			q[i] = in.nextLong();
		}

		for(int i=0;i<C;i++) {
			r[i] = in.nextLong();
		}

		Arrays.sort(p);
		Arrays.sort(q);

		long[] apples = new long[X+Y+C];
		for(int i=0;i<X;i++) {
			apples[i] = p[A-1-i];
		}

		for(int i=X;i<X+Y;i++) {
			apples[i] = q[B-1-i+X];
		}

		for(int i=X+Y;i<X+Y+C;i++) {
			apples[i] = r[C-1-i+X+Y];
		}

		Arrays.sort(apples);
		for(int i=X+Y+C-1; i > C-1; i--) sum += apples[i];
		System.out.println(sum);
	}

	public static class MyScanner {
		Scanner sc = new Scanner(System.in);
		String next() { return sc.next();}
		int nextInt() { return Integer.valueOf(sc.next());}
		long nextLong() { return Long.valueOf(sc.next()); }
	}
}

Measured memory_bytes: 66356
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());

		int total = 0;
		for(int i=0; i<2; i++) {
			if(A >=B) {
				total += A;
				A--;
			} else {
				total += B;
				B--;
			}
		}
		System.out.println(total);

	}
}


Measured memory_bytes: 21844
<?php
error_reporting(0);
$stdin = file_get_contents('php://stdin');
$line = explode("\n",$stdin);
$fi = 0;
$cnt = 0;
$list = array();
$key = new stdclass();
foreach($line as $l) {
  if (empty($l)) continue;
  if ($fi == 0) {
    $a = explode(" ",$l);
    $key->S = $a[0];
    $fi++;
    continue;
  }
  if ($fi > 0) {
    $a = explode(" ",$l);
    $key->A=$a;
  }
}
$len=strlen($key->S);
$res = "";
for($i=0;$i<$len;$i++) {
  switch($key->S[$i]) {
  case '0':
    $res = $res . "0";
    break;
  case '1':
    $res = $res . "1";
    break;
  case 'B':
    if (strlen($res)>0) {
      $res = substr($res,0,strlen($res)-1);
    }
    break;
  }
}
printf("%s\n",$res);


Measured memory_bytes: 3832
#include<stdio.h>

#define N 500000
 
int L[(N/2)+2],R[(N/2)+2];
int a;
 
void merge(int b[],int l,int m,int r){
  int d,i,j,e=m-l,f=r-m;
  
  for(i=0;i<e;i++){
    
  L[i]=b[l+i];
  
  }
  
  for(i=0;i<f;i++){
    
  R[i]=b[m+i];
  
  }
  
  L[e]=1000000000;
  
  R[f]=1000000000;
  
  i=0;
  
  d=0;
  
  for(j=l;j<r;j++){

      a++;
      
      if(L[i]<=R[d]){
	
        b[j]=L[i];
	
	i+=1;
	
      }
      
      else {
	
      b[j]=R[d];
      
      d+=1;
      
      }
    }
}

void mergeSort(int b[],int l,int r){

  int m;
  
  if(l+1<r){
    
    m=(l+r)/2;
    
    mergeSort(b,l,m);
    
    mergeSort(b,m,r);
    
    merge(b,l,m,r);
    
  }
}
 
int main(){
  
  int b[N],c,i;
  
  a=0;
  
  scanf("%d",&c);
  
  for(i=0;i<c;i++){
    
  scanf("%d",&b[i]);
  
  }
  
  mergeSort(b,0,c);
  
  for(i=0;i<c-1;i++){
    
    printf("%d ",b[i]);
    
  }
  
   printf("%d\n",b[c-1]);
   
   printf("%d\n",a);
 
  return 0;
}



Measured memory_bytes: 5600
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int A = in.nextInt() - 1;
		int B = in.nextInt() - 1;
		int C = in.nextInt() - 1;
		int D = in.nextInt() - 1;
		String s = in.next();
		while ((A < N || B < N) && (A != C || B != D)) {
			if (D < C) {
				if (A + 2 < N && s.charAt(A + 2) != '#' && A + 2 != B && A + 2 <= C) {
					A += 2;
				} else if (A + 1 < N && s.charAt(A + 1) != '#' && A + 1 != B && A + 1 <= C) {
					A++;
				} else if (A + 2 == B || A + 1 == B || A == C) {
					if (B + 1 < N && s.charAt(B + 1) != '#' && B + 1 <= D) {
						B++;
					} else if (B + 2 < N && s.charAt(B + 2) != '#' && B + 2 <= D) {
						B += 2;
					} else {
						break;
					}
				} else {
					break;
				}
			} else if (C < D) {
				if (B + 2 < N && s.charAt(B + 2) != '#' && B + 2 != A && B + 2 <= D) {
					B += 2;
				} else if (B + 1 < N && s.charAt(B + 1) != '#' && B + 1 != A && B + 1 <= D) {
					B++;
				} else if (B + 2 == A || B + 1 == A || B == D) {
					if (A + 1 < N && s.charAt(A + 1) != '#' && A + 1 <= C) {
						A++;
					} else if (A + 2 < N && s.charAt(A + 2) != '#' && A + 2 <= C) {
						A += 2;
					} else {
						break;
					}
				} else {
					break;
				}
			}
		}
		System.out.println(A == C && B == D ? "Yes" : "No");
		in.close();
	}
}

Measured memory_bytes: 26776
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
      int N=int.Parse(Console.ReadLine());
      string[] str=Console.ReadLine().Split(' ');
      int[] shain=str.Select(int.Parse).ToArray();
 	 int[] count=new int[N];      
      foreach(var e in shain){
      count[e-1]++;        
        //Console.WriteLine(shain.Count(value=>value==j));
      }
      for(int i=0;i<N;i++){
        Console.WriteLine(count[i]);
      }
    }
    
  }

}



Measured memory_bytes: 43820
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let w = s.trim();

    let mut count =  [0; 26];
    let n: u8 = "a".as_bytes()[0];
    for i in 0..w.len() {
        count[{w.chars().nth(i).unwrap().to_string().as_bytes()[0] - n} as usize] += 1;
    }
    let mut btfl = true;
    for i in 0..count.len() {
        if count[i] % 2 == 1 {btfl = false}
    }
    println!("{}", if btfl {"Yes"} else {"No"});
}



Measured memory_bytes: 4352
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        var n = int.Parse(Console.ReadLine());
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var ans = 0;
        for (int i = 0; i < a.Length; i++)
        {
            if ((i + 1) % 2 == 1 && a[i] % 2 == 1) ans++;
        }


        // 出力
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 28164
#include <bits/stdc++.h>
using namespace std;
int main(){
  int x;
  string y;
  cin >> x;
  cin >> y;
  if(x%2 == 1){
    cout <<"No" << endl;
  }
  else{
    int z = x/2;
    int flag = 0;
    for(int i = 0; i < z; i++){
      if(y.at(i) != y.at(i+z)){
        flag = 1;
        break;
      }
      else{
      }
    }
    if(flag == 1){
      cout << "No" << endl;
    }
    else{
      cout << "Yes" << endl;
    }
  }
}
      
      
    
  

Measured memory_bytes: 256
def main():
  N = int(input())
  P = list(map(int, input().split()))

  ans = 1
  min_val = P[0]
  for i in range(1,N):
    if P[i] < min_val:
      ans += 1
      min_val = P[i]
    if min_val == 1:
      break

  print(ans)

if __name__ == "__main__":
	main()


Measured memory_bytes: 24872
#include "bits/stdc++.h"

using namespace std;

int main() {
    int N,H,M;
    cin >> N;
    int j = 0;
    M = 0;
    int ans = 0;
    while(j < N){
        cin >> H;
        j++;
        if(M <= H){
            ans = ans + 1;
            M = H;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 764
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <vector>
#define loop(n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
typedef long long int ll;
#define mxn 1e9


ll solve(ll* arr,ll n)
{
	ll dp[n][n];
	ll cost[n][n];

	for(ll i=0;i<n;i++)
	{
		dp[i][i] = arr[i];
		cost[i][i] = 0;	
	}

	for(ll l = 2;l <= n;l++)
	{
		for(ll i=0;i<= n-l;i++)
		{
			ll j = i + l - 1;
			dp[i][j] = LLONG_MAX;
			cost[i][j] = LLONG_MAX;
			for(ll k = i;k<j;k++)
			{
				//cout<<i<<" "<<k<<" "<<j<<endl;
				dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j]);
				cost[i][j] = min(cost[i][j],dp[i][k] + dp[k+1][j] + cost[i][k] + cost[k+1][j]);
				//cout<<dp[i][k]<<" "<<dp[k+1][j]<<endl;
			}
		}
	}
	
	/*
	for(ll i=0;i<n;i++)
	{
		for(ll j=0;j<n;j++)
		{
			if(i <= j)
				cout<<dp[i][j]<<" ";
			else
				cout<<-1<<" ";
		}
		cout<<endl;
	}
	*/ 
	
	return cost[0][n-1];
	
}



int main()
{
    fastio;
    ll n;
    cin>>n;
    ll arr[n];
    loop(n)
		cin>>arr[i];
	
	ll ans = solve(arr,n);
	cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6080
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  long int mod=1e9+7;
  long long int arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  long long int sum=0;
  for(int i=0;i<n;i++)
    sum=sum+arr[i];
  long long int res=0;
  for(int i=0;i<n-1;i++)
  {
    long long int a=sum-arr[i];
    sum=sum-arr[i];
    long long int p=((arr[i]%mod)*(a%mod))%mod;
    res=res+p;
  }
  long long int x=res%mod;
  cout<<x;
}
    

Measured memory_bytes: 5136
import collections
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
q=int(input())
x=collections.Counter(a)
for _ in range(q):
  b,c=map(int,input().split())
  s=s-x[b]*b+x[b]*c
  print(s)
  x[c]+=x[b]
  x[b]=0

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, A, B;
  cin >> N >> A >> B;
  cout << min(N*A, B) << endl;
}

Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int a[n],b[m];
    rep(i,n) cin>>a[i];
    rep(i,m) cin>>b[i];

    vector<ll> atot(n+1,0);
    rep(i,n) atot[i+1]=atot[i]+a[i];
    vector<ll> btot(m+1,0);
    rep(i,m) btot[i+1]=btot[i]+b[i];

    int ans=0;
    int ok=m;
    rep(i,n+1){
        while(0<=ok && k<atot[i]+btot[ok]) ok--;
        if(0<=ok) ans=max(ans,i+ok);
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 7992
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

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

    int tmp = 0;
    int ans = 1.0e8;
    for(int i = 0; i < n-1; i++) {
        tmp += v[i];
        ans = min(ans, abs((sum-tmp)-tmp));
    }
    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 256