akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const signed INF_=1001001001; const int INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":"\n");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
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(a>b){a=b;return 1;}return 0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct{template<class T> operator T(){T x;cin>>x;return x;}} IN;
struct before_main_function {
    before_main_function() {
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

const int MOD=1e9+7;
const int MAX_N=200005;
long long fact[MAX_N];
long long fact_inv[MAX_N];
long long bin_pow_mod(long long x,long long y) {
    if(x==0) return 0;
    long long prod=1;
    while(y>0) {
        if(y&1) {
            prod=(prod*x)%MOD;
        }
        x=(x*x)%MOD;
        y>>=1;
    }
    return prod%MOD;
}
struct init_fact {
    init_fact() {
        fact[0]=1, fact_inv[0]=1;
        for(int i=1;i<MAX_N;++i) {
            fact[i]=(fact[i-1]*i)%MOD;
            fact_inv[i]=bin_pow_mod(fact[i],MOD-2);
        }
    }
} init_fact;

int dp[1001][1001];
signed main() {
    int N=IN,A=IN,B=IN,C=IN,D=IN;
    dp[A-1][0]=1;
    REPF(i,A,B+1) {
        REP(j,N+1) {
            dp[i][j]+=dp[i-1][j];
            dp[i][j]%=MOD;
            REPF(k,C,D+1) {
                if(j<i*k) break;
                dp[i][j]+=dp[i-1][j-i*k]*fact[N-(j-i*k)]%MOD*fact_inv[N-j]%MOD*fact_inv[k]%MOD*bin_pow_mod(bin_pow_mod(fact[i],k),MOD-2)%MOD;
                dp[i][j]%=MOD;
            }
        }
    }
    cout<<dp[B][N]<<endl;
    return 0;
}


Measured memory_bytes: 11264
import java.io.*;
import java.util.Scanner;

public class Main {

   public static void main(String args[]) {

    Scanner scan = new Scanner(System.in);

     String l = scan.next();
	 String m =scan.next();     
	 String n = scan.next();     
    int a = Integer.parseInt(l);
    int b = Integer.parseInt(m);
    int c = Integer.parseInt(n);

    
          	if ((a == b && b == c)&&(b == c && a == c))  {
          		System.out.println("1");
          	   } else if ((a != b && b !=c)&&(b !=c && c != a)) {
          	   	 System.out.println("3");
          	   	} else {
          	   	 System.out.println("2");
   } 
   }
   }
   

Measured memory_bytes: 9680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;



int main(){
  ll H, W;
  cin>>H>>W;
  vector<vector<char>> A(H, vector<char>(W));
  vector<vector<ll>> dp(H, vector<ll>(W, 0));
  dp[0][0]=1;
  rep(i, H){
    rep(j, W){
      cin>>A[i][j];
      if(A[i][j]=='.'){
        if(i>0&&A[i-1][j]=='.'){
          dp[i][j]+=dp[i-1][j];
          dp[i][j]%=MOD;
        }
        if(j>0&&A[i][j-1]=='.'){
          dp[i][j]+=dp[i][j-1];
          dp[i][j]%=MOD;
        }
      }
    }
  }
  cout<<dp[H-1][W-1]<<endl;
  return 0;
} 

Measured memory_bytes: 12112
import java.util.Arrays;
import java.util.Scanner;

class Main{
	static final long MOD = 1000000007;

	static int H, W, K;
	static long[][] dp = new long[110][10];
	static int ans = 0;
	static long n = 0;




	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		int m  =sc.nextInt();
		int X  = sc.nextInt();
		int Y = sc.nextInt();
		int[] x = new int[n];
		int[] y = new int[m];
		for(int i = 0;i< n;i++){
			x[i] = sc.nextInt();
		}
		Arrays.sort(x);
		for(int i = 0;i < m;i++){
			y[i] = sc.nextInt();
		}
		Arrays.sort(y);

		for(int i = X+1;i < Y;i++){
			if(x[n-1] < i && i <= y[0]){
				System.out.println("No War");
				return;
			}
		}
		
		System.out.println("War");

	}
}







class Pair implements Comparable{
	int from;		//p
	int end;		//y
	int num;
	int bango;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}



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

int main(){
    int N; cin >> N;
    map<string, int> m;
    rep(i, N){
        string str;
        cin >> str;
        sort(all(str));
        m[str]++;
    }
    ll ans = 0;
    for(auto x:m){
        // cout << x.first << " " << x.second << endl;
        ans += x.second*(x.second - 1LL) / 2;
    }
    cout << ans << endl;
}


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

int main() {
	std::string str;
	int ans = 0;
	std::cin >> str;

	if (str[0] == '1') ans++;
	if (str[1] == '1') ans++;
	if (str[2] == '1') ans++;
	
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 256
import Foundation
let arr=readLine()!.split{$0==" "}.map{Int(String($0))!}
var a=arr[0]
var b=arr[1]
var c=arr[2]
var k=arr[3]
var max = 0

if k >= a {
    max += a
    k -= a
    if k > 0 {
        k -= b
        if  k > 0  {
           max -= k
        }
    }
}else{
    max = k
}
print(max)


Measured memory_bytes: 13244
#include<iostream>
#include<math.h>
using namespace std;

double log2(double x){
	return log(x)/log(2);
	
}

int out(int *A,int N){
	int i;
	for (i=0;i<=N-2;i++){
		cout << A[i] <<" ";
	}
	cout << A[N-1] <<endl;
	return 0;
}


int insertionSort(int *A,int n,int g){
	int cntnn=0,i,j,v;
	for (i=g;i<=n-1;i++){
		v=A[i];
		j=i-g;
		while (j>=0 && A[j]>v){
			A[j+g]=A[j];
			j=j-g;
			cntnn++;
		}
		A[j+g]=v;
	}
	return cntnn;
}

int shellSort(int *A,int n,int m, int *G){
	int cntn=0;
	int i,c;
	for (i=0;i<=m-1;i++){
		c=insertionSort(A,n,G[i]);
		cntn=cntn+c;
	}
	return cntn;
}

int main(){
	int n,cnt=0;
	cin >> n;
	int i;
	int A[n];
	for (i=0;i<=n-1;i++){
		cin >> A[i];
	}
	int m=floor(log2(n));
	if (n==1){
		m=1;
	}
	int G[m];
	for (i=m-1;i>=0;i--){
		G[i]=pow(2,m-i-1);
	}
	
	cnt=shellSort(A,n,m,G);
	
	cout << m <<endl;
	out(G,m);
	cout << cnt <<endl;
	for (i=0;i<=n-1;i++){
		cout << A[i] <<endl;
	}
	
	return 0;
}

Measured memory_bytes: 5128
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::io::Read;
use std::io::{stdout, BufWriter, Write};
 
fn main() {
    let mut buf = String::new();
    
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
 
    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();
 
    // 読み込んだStringを空白で分解する
    let mut iter = buf.split_whitespace();
 
    let n: usize = iter.next().unwrap().parse().unwrap();
    let mut p: Vec<usize> = (0..n).map(|_| {
        iter.next().unwrap().parse().unwrap()
    }).collect();
    
    for i in 0..n {
        if i + 1 == p[i] {continue;}
        else {
            let index = p[i] - 1;
            p.swap(i, index);
            break;
        }
    }
    
    let mut key = true;
    for i in 0..n {
        if i + 1 == p[i] {continue;}
        else {
            key = false;
            break;
        }
    }
    
    if key == true {
        println!("YES");
    }else{
        println!("NO");
    }
    
}

Measured memory_bytes: 4352
#include <iostream>
#include <bitset>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <numeric>
#include <array>
#include <queue>
#include <set>
#include <iomanip>
#include <limits>
#include <type_traits>
using namespace std;
using ll = long long int;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#define REP(i,n) for(int i=0;i<n;i++)

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

  priority_queue<pair<int, int>> queue;
  for (int i = 0; i < N; i++)
  {
    int temp;
    cin >> temp;
    queue.push(make_pair(temp, i));
  }
  
  pair<int, int> p = queue.top();
  int max_value = p.first;
  int max_index = p.second;
  queue.pop();

  pair<int, int> semi = queue.top();
  int semi_value = semi.first;

  for (int i = 0; i < N; i++)
  {
    if (i == max_index)
      cout << semi_value << endl;
    else
      cout << max_value << endl;  
      
  }
  
  

}

Measured memory_bytes: 3568
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cassert>
#include <numeric>
#include <queue>
#include <unordered_set>

using namespace std;

string solve(int64_t n) {
    int64_t sum = 0;

    int64_t nn = n;
    while (nn > 0) {
        sum += nn % 10;
        nn /= 10;
    }

    return n % sum == 0 ? "Yes" : "No";
}

int main() {
    int n;
    cin >> n;

    cout << solve(n) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,oo=0x3f3f3f3f;

int b[maxn],pre[maxn],n,m,ans;
namespace Seg{
	int a[maxn<<2];
	void clear(){
		memset(a,0x3f,sizeof a);
	}
	#define rt 1,1,n
	#define mid (l+r>>1)
	#define ls u<<1
	#define rs ls|1
	#define lc ls,l,mid
	#define rc rs,mid+1,r
	void update(int u,int l,int r,int ql,int qr,int v){
		if(ql<=l&&r<=qr){
			a[u]=min(a[u],v);
			return;
		}
		//cerr<<u<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
		//system("pause");
		if(ql<=mid)update(lc,ql,qr,v);
		if(qr>mid)update(rc,ql,qr,v);
	}
	int query(int u,int l,int r,int k) {
		if(l==r)return a[u];
		return min(a[u],k<=mid?query(lc,k):query(rc,k));
	}
}
struct data{
	int l,r;
	data(){};
	friend bool operator < (data a,data b){
		if(a.r!=b.r)return a.r<b.r;
		return a.l<b.l;
	}
}p[maxn];
void solve(){
	Seg::clear();
	cin>>n; 
	for(int i=1;i<=n;++i){
		cin>>b[i];
		//scanf("%d",b+i);
		b[i]=b[i]+b[i-1];
	}
	ans=b[n];
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		cin>>p[i].l>>p[i].r;
		//scanf("%d%d",&p[i].l,&p[i].r);
		//cerr<<p[i].l<<" "<<p[i].r<<endl;
	}
	sort(p+1,p+m+1);
	for(int i=1,l,r,cur=1,w;i<=m;++i){
		l=p[i].l,r=p[i].r;
		for(;cur<r;++cur)pre[cur+1]=pre[cur];
		w=(r-l+1)-(b[r]-b[l-1])+b[l-1]+pre[l-1];
		w=min(w,r-b[r]+Seg::query(1,1,n,l));
		pre[r]=min(pre[r],w-b[r]);
		//cerr<<l<<" "<<r<<endl;
		Seg::update(rt,l,r,w+b[r]-r);
	//cerr<<"wea"<<endl;
		ans=min(ans,w+b[n]-b[r]);
	}
	cout<<ans<<endl;
	//printf("%d\n",ans);
}
int main(){
	solve();
	return 0;
} 

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

int main() 
{
    vector<int> v(5);
    for (int i=0; i<5; i++)
        cin >> v[i];
    int k; cin >> k;
    string s = "Yay!";
    for (int i=0; i<4; i++)
        for (int j=i+1; j<5; j++)
            if (v[j]-v[i]>k)
                s = ":(";
    cout << s;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;i++)
#define fdr(i,a,b) for(int i=a;i>=b;i--)
#define xx 100001
#define ll long long
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
ll a[xx],cha[xx],ru[xx*2];
ll n;
inline void cot(ll k,ll x)
{
	while(k<xx*2)
	{
		ru[k]+=x;
		k+=(k&-k);
	}
}
inline ll get(ll k)
{
	ll ans=0;
	while(k>0)
	{
		ans+=ru[k];
		k-=(k&-k);
	}
	return ans;
}
inline bool check(ll k)
{
	memset(ru,0,sizeof(ru));
	cha[0]=0;
	fur(i,1,n) cha[i]=cha[i-1]+(a[i]>=k?1:-1);
	ll ans=0;
	fur(i,0,n)
	{
		ans+=get(cha[i]+xx);
		cot(cha[i]+xx,1ll);
	}
	return ans>=(n*(n+1)>>2);
}
int main()
{
	ll l=0,r=0;
	n=in;
	fur(i,1,n) a[i]=in,r=max(a[i],r);
	while(l<=r)
	{
		ll mid=l+r>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 3328
#include "bits/stdc++.h"
#define ll long long
#define N 100050
using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s; cin>>s;
    int n=s.length();
    int ans=1;
    int pr=1;
    for(int i=1;i<n;i++){
        if(s[i]==s[i-1]&&(pr==1)){
            pr=2;
            if(i<(n-1)){
                ans++; i++;
            }
            else break;
            continue;
        }
        ans++; pr=1;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 1356
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

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

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 3000+5;
const ll inf = 1e18;

int n;
int m;
int k;
int v[N][N];
ll memo[N][N][4];
bool vis[N][N][4];

ll DP(int x, int y, int left){
	if(x == n and y == m){
		return left? v[x][y] : 0;
	}
	if(vis[x][y][left]) return memo[x][y][left];
	ll ans = x + 1 <= n? DP(x + 1, y, 3) : -inf;
	if(left > 0){
		if(x + 1 <= n) ans = max(ans, v[x][y] + DP(x + 1, y, 3));
		if(y + 1 <= m) ans = max(ans, v[x][y] + DP(x, y + 1, left - 1));
	}
	if(y + 1 <= m) ans = max(ans, DP(x, y + 1, left));
	vis[x][y][left] = true;
	return memo[x][y][left] = ans;
}

int main(){
	ri3(n, m, k);
	for(int i = 1; i <= k; i++){
		int x, y, w;
		ri3(x, y, w);
		v[x][y] = w;
	}
	printf("%lld\n", DP(1, 1, 3));
	return 0;
}


Measured memory_bytes: 356440
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<numeric>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<functional>
#include<iterator>
#include<cmath>
#include<cctype>

using namespace std;

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

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = INF+7;

struct edge{int to,cost;};
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n,T;
	cin >> n >> T;

	vector<int> c;
	int t,cc;
	for(int i=0;i<n;i++){
		cin >> cc >> t;
		if(t<=T){
			c.push_back(cc);
		}
	}
	if(c.size() == 0){
		cout << "TLE\n";
		return 0;
	}
	sort(c.begin(),c.end());

	cout << c[0] << "\n";
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    ll n;
    cin >> n;
    vector<ll> a(5);
    REP(i,5) cin >> a[i];
    sort(a.begin(), a.end());
    ll x = (a[0]+n-1)/a[0];
    x += 4;
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
/*
ID: kiwio
LANG: C++14
TASK: 
*/
 
#include <bits/stdc++.h>
using namespace std;
 
int n, num, x[200005], yay, dist, nd, ans, ind;
 
int main () {
	ios_base::sync_with_stdio(0); cin.tie(NULL);/*
#ifndef turtle
	ofstream cout (".out");
	ifstream cin (".in");
#endif*/
	cin >> num;
	for (int i=1; i<=num; i++) {
		cin >> x[i];
		n=max(n, x[i]);
		if (x[i]==n) {
			ind=i;
		}
	}
	cout << n << " ";
	dist=1000000000;
	for (int i=1; i<=num; i++) {
		if (i!=ind) {
			if (abs(n/2-x[i])<dist and x[i]<=n) {
				dist=abs(n/2-x[i]);
				nd=x[i];
			}
		}
	}
	cout << nd;
 
 }

Measured memory_bytes: 640
def wd_fast(a)
  n=a.size-1
  0.upto(n){|k|0.upto(n){|i|0.upto(n){|j|
    x=a[i][k]+a[k][j]
    a[i][j]=(a[i][j]<x)? a[i][j] : x}}}
end
class UnionFind
  def initialize(size)
    @rank = Array.new(size, 0)
    @parent = Array.new(size, &:itself)
  end

  def unite(id_x, id_y)
    x_parent = get_parent(id_x)
    y_parent = get_parent(id_y)
    return if x_parent == y_parent

    if @rank[x_parent] > @rank[y_parent]
      @parent[y_parent] = x_parent
    else
      @parent[x_parent] = y_parent
      @rank[y_parent] += 1 if @rank[x_parent] == @rank[y_parent]
    end
  end

  def get_parent(id_x)
    @parent[id_x] == id_x ? id_x : (@parent[id_x] = get_parent(@parent[id_x]))
  end

  def same_parent?(id_x, id_y)
    get_parent(id_x) == get_parent(id_y)
  end
end

n=gets.to_i
a=n.times.map{gets.chomp.split("").map(&:to_i)}
u=UnionFind.new(a.size*2)
a.each_with_index{|x,i|
  x.each_with_index{|y,j|
    next if i>=j
    if y==1
      u.unite(i,j+n)
      u.unite(i+n,j)
    end
    }}
0.upto(n-1){|i| puts -1 or exit if u.same_parent?(i,i+n) }
a.map!{|x| x.map!{|y| y==0 ? 100000 : y}}
wd_fast(a)
0.upto(a.size-1){|i| a[i][i]=0}
d=a.map{|x| x.max}.max
puts d+1


Measured memory_bytes: 2684
#include<bits/stdc++.h>
#define INF 9223372036854775807LL
#define inf 1000000007
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define lol long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
lol a,b,c,d;
int i[100000];
int u[100000];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >>a>>b;
  if(a==b) cout <<"Yes\n";
  else cout <<"No\n";
  return (0);
}


Measured memory_bytes: 256
/*
	ex4_1
	ruuu0048
*/
#include <stdio.h>
#include <math.h>
 
int main(void){
 
    int tree_num,view_scope; //リンゴの木の本数Nと監視員の視野の広さDの変数を宣言
    int watchman_num; //必要な監視員の数の変数を宣言
    float view_capacity; //一人の監視員が見られる木の本数

    scanf("%d",&tree_num); //Nを入力
    scanf("%d",&view_scope); //Dを入力

    view_capacity = view_scope * 2 + 1; //Dから一人の監視員が見られる本数を計算

    watchman_num = ceil(tree_num / view_capacity); //float型で計算したものを繰り上げ
 
    printf("%d\n",watchman_num); //必要な監視員の数をを出力
 
    return 0; 
 
}


Measured memory_bytes: 128
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int max = 0;
		int total = 0;
		sc.nextInt();
		while (sc.hasNext()) {
			int a = sc.nextInt();
			if (a > max) max = a;
			total += a;
		}
		// 出力
		System.out.println(total - max/2);
	}
}


Measured memory_bytes: 22736
//------------------------------------------
// C++ templete 
//------------------------------------------
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long;

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//動的計画法で役に立つ関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//最大公約数と最小公倍数
ll gcd(ll a, ll b) {
    if(b==0)return a;
    return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
  ll g = gcd(a, b);
  return a/g*b;
}

vector<vector<long long> > comb(int n) {
  vector<vector<long long> > v(n + 1,vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    VI A(N);
    REP(i,N)
    {
        cin >> A[i];
    }
    
    cout << accumulate(ALL(A), -N) << endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front

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

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

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

	if(s==25)
		cout<<"Christmas"<<endl;
	else if(s==24)
		cout<<"Christmas Eve"<<endl;

	else if(s==23)
		cout<<"Christmas Eve Eve"<<endl;

	else if(s==22)
		cout<<"Christmas Eve Eve Eve"<<endl;


    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 300000
#define int long
int N, cnt = 0;
int A[MAX_N + 1], B[MAX_N];

int fanc(int i, int j){
    if(A[j] <= B[i]){
            cnt += A[j];
            B[i] -= A[j];
            A[j] = 0;    
        }
        else{
            A[j] -= B[i];
            cnt += B[i];
            B[i] = 0;
        }
}
signed main(){
    cin >> N;
    for(int i = 0; i < N + 1; i++){
        cin >> A[i];
    }
    for(int i = 0; i < N; i++){
        cin >> B[i];
    }
    for(int i = N - 1; i >= 0; i--){
        fanc(i, i + 1);
        if(B[i])
            fanc(i, i);
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3072
n = int(input())
n1 = n%10
if n1 == 2 or n1 == 4 or n1 == 5 or n1 == 7 or n1 == 9:
    print("hon")
elif n1 == 0 or n1 == 1 or n1 == 6 or n1 == 8:
    print("pon")
else:
    print("bon")

Measured memory_bytes: 9176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {  
  return b != 0 ? gcd(b, a % b) : a;
}//MAX
int lcm(int a, int b) { 
   return a * b / gcd(a, b);
   }
//MIN

 main() {
   int r;
   cin >> r;
   long long ans = pow(r,2);
   cout << ans << endl;
 }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

namespace std {
	#define u(x, a, b) for(ll x = a; x < b; x++)
	#define d(x, a, b) for(ll x = a; x > b; x--)
}

typedef long long ll;
typedef long double ld;

#define MAXI 100010
#define MOD 1000000007

int main(){
	ll h, w, k;
	cin >> h >> w >> k;
	
	ll arr[h][w] = {0};
	char c;
	u(one, 0, h){
		u(two, 0, w){
			cin >> c;
			if(c=='#'){arr[one][two]=1;}
			else{arr[one][two] = 0;}
		}
	}
	
	ll cnt = 0;
	u(i, 0, 1<<h){
		u(j, 0, 1<<w){
			ll one = i, two = j;
			ll rowcho[h] = {0};
			u(three, 0, h){
				rowcho[three] = one%2;
				one-=rowcho[three];
				one/=2;
			}
			
			ll colcho[w] = {0};
			u(three, 0, w){
				colcho[three] = two%2;
				two-=colcho[three];
				two/=2;
			}
			
			ll num = 0;
			u(three, 0, h){
				u(four, 0, w){
					if(rowcho[three]==0 && colcho[four]==0){num += arr[three][four];}
				}
			}
			if(num==k){cnt++;}
		}
		
		
	}
	cout << cnt;
}


Measured memory_bytes: 3616
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;

#include <complex>
#define CURR(P, i) (P[(i) % P.size()])
#define NEXT(P, i) (P[((i) + 1) % P.size()])

typedef complex<double> Point;
typedef vector<Point> Polygon;
struct Line : public vector<Point> {
  Line() {;}
  Line(Point a, Point b) { push_back(a); push_back(b); }
};
struct Circle {
  Point p;
  double r;
  Circle() {;}
  Circle(Point p, double r) : p(p), r(r) {;}
};


enum { OUT, ON, IN };
int contains(const Circle& C, Point p){
  p -= C.p;
  if(abs(C.r - abs(p)) < EPS) return ON;
  if(C.r > abs(p)) return IN;
  if(C.r < abs(p)) return OUT;
  assert(false);
}
//pをm中心にtだけ回転
Point rotate(Point p, Point m, double t){
  p -= m;
  p = Point(p.real() * cos(t) - p.imag() * sin(t),
            p.real() * sin(t) + p.imag() * cos(t));
  return p + m;
}
//Pをm中心にtだけ回転
Polygon rotate(Polygon P, Point m, double t){
  REP(i, P.size()){
    P[i] = rotate(P[i], m, t);
  }
  return P;
}
int main(){
  int N, R, Q;
  while(cin>>N>>R>>Q && N){
    Polygon object;
    REP(i, N){
      int x, y; cin>>x>>y;
      object.push_back(Point(x, y));
    }
    Circle sphere(Point(0, 0), (double)R);
    int touchindex = -1;
    REP(i, N){
      if(contains(sphere, object[i]) == ON) touchindex = i;
    }
    assert(touchindex != -1);
    REP(iter, Q){
      double lower = 0, upper = 2.0 * M_PI;
      REP(iter2, 40){
        double mid = (lower + upper) / 2.0;
        Polygon rotated = rotate(object, object[touchindex], mid);
        bool pointisout = false;
        REP(i, N){
          if(contains(sphere, rotated[i]) == OUT) pointisout = true;
        }
        if(pointisout){
          upper = mid;
        }else{
          lower = mid;
        }
      }
      int newtouchindex = -1;
      Polygon newobject = rotate(object, object[touchindex], lower);
      REP(i, N){
        if(i != touchindex && contains(sphere, newobject[i]) == ON){
          if(newtouchindex == -1 || 
              abs(newobject[newtouchindex] - object[touchindex]) < 
              abs(newobject[i] - object[touchindex]) ){
            newtouchindex = i;
          }
        }
      }
      assert(newtouchindex != -1);
      printf("%.12f %.12f\n", newobject[newtouchindex].real(), newobject[newtouchindex].imag());
      object = newobject;
      touchindex = newtouchindex;
    }
  }
  return 0;
}

Measured memory_bytes: 984
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e18;

signed main(){
  string s;
  cin>>s;
  int ans=INF;
  bool flag=true;
  rep(i,s.size())flag&=(s[i]==s[0]);
  if(flag){
    cout<<0<<endl;
    return 0;
  }
  for(char i='a';i<='z';i++){
    string t=s;
    int tmp=0;
    while(1){
      tmp++;
      string u="";
      rep(j,t.size()-1){
        if(t[j]==i||t[j+1]==i)u+=i;
        else u+=t[j];
      }

      bool f=true;
      rep(k,u.size())f&=(u[k]==u[0]);
      //cout<<"u="<<u<<' '<<"tmp="<<tmp<<endl;
      if(f)break;
      t=u;
    }
    ans=min(ans,tmp);
  }
  cout<<ans<<endl;

  return 0;
}


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

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

  int h, w;
  cin >> h >> w;
  vector<string> sv(h);
  for (int i = 0; i < h; i++) {
    cin >> sv.at(i);
  }

  vector<int> dx = {-1, 0, 0, 1};
  vector<int> dy = {0, -1, 1, 0};

  string ans = "Yes";
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      char c = sv.at(i).at(j);

      if (c != '#') continue;

      bool found = false;
      for (int k = 0; k < 4; k++) {
        int di = i + dx.at(k);
        int dj = j + dy.at(k);
        if (di < 0 || di >= h) continue;
        if (dj < 0 || dj >= w) continue;

        if (sv.at(di).at(dj) == '#') {
          found = true;
          break;
        }
      }

      if (!found) ans = "No";
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

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

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input! {
        n: usize, mut h: i64,
        mut ab: [(i64, i64); n],
    }
    ab.sort_by(|a, b| b.1.cmp(&a.1));
    let mut max_ = ab.iter().map(|&(a, _)| a).max().unwrap();

    let mut cnt = 0;
    for i in 0..n {
        if max_ <= ab[i].1 {
            h -= ab[i].1;
            cnt += 1;
        }
        if h <= 0 {
            break;
        }
    }
    if h > 0 {
        cnt += (h + max_ - 1) / max_;
    }
    println!("{}", cnt);
}


Measured memory_bytes: 6396
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef pair<int,int> P;
const int N=1010,M=200200;
int n,m,u,v,vi[N],bo[N],g[N][N],ans[M];
map<P,int>id;
vector<int>ve[N];
void dfs(int u,int*a){a[u]=1;for(int v:ve[u])if(!a[v]) dfs(v,a);}
void work(int u){
	FOR(i,1,n) vi[i]=i==u;
	for(int v:ve[u]) vi[v]?bo[v]=1:(dfs(v,vi),0);
}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	FOR(i,1,m) scanf("%d%d",&u,&v),ve[u].push_back(v),id[P(u,v)]=i;
	FOR(i,1,n) dfs(i,g[i]);
	FOR(i,1,n){
		for(int v:ve[i]) bo[v]=0;
		work(i);
		reverse(ve[i].begin(),ve[i].end());
		work(i);
		for(int v:ve[i]) ans[id[P(i,v)]]=g[v][i]^bo[v];
	}
	FOR(i,1,m) puts(ans[i]?"diff":"same");
}


Measured memory_bytes: 20864
// This amazing code is by Eric Sunli Chen.
#include<bits/stdc++.h>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int k,n;
int main()
{
	get1(k);
	if(k==1)
	{
		puts("1\n1");
		return 0;
	}
	n=(k+3)/4*2;
	printf("%d\n",n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			int v=(i+j)%n;
			if(i%2==1&&(v+n<k))v+=n;
			printf("%d ",v+1);
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n][d];
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<d;j++)
    {
      cin>>a[i][j];
    }
  }int count=0;
  for(int i=0;i<n-1;i++)
  {
    for(int j=i+1;j<n;j++)
    {
      int sum=0;
      for(int k=0;k<d;k++)
      {
      sum+=((a[i][k]-a[j][k])*(a[i][k]-a[j][k]));
      }
      int s=sqrt(sum);
      if(s*s==sum) {
         
	  
	  count+=1;
}
    }
  }
  cout<<count;
}

Measured memory_bytes: 256
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, r and f(k + 1) + p - r + c or m)
    memo[n] = m
  return m

t = int(input())
for _ in range(t):
  n, *b, d = map(int, input().split())
  memo = {0: 0, 1: d}
  print(f(n))


Measured memory_bytes: 10992
# your code goes here
#N=int(input())
#l = list(map(int,input().split()))
n,m,d = map(int,input().split())
k = abs(n-2*d-1)+1
if n > d + 1:
	x = n + k
else:
	x = 2
if d == 0:
	x = n
f = x/n/n
if n == 0 :
	print(0)
else:

		print((m-1)*x/n/n)
	# your code goes here

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

int main(){
  string s,t;
  cin>>s;
  int c=0;

  for(int i=0;i<s.size();i++){
    if(s[i]=='x')c++;
    else t+=s[i];
  }
  
  bool f=0;
  int n=t.size();
  for(int i=0;i<n/2;i++){
    if(t[i]!=t[n-1-i])f=1;
  }
  
  int cc=0,idx=-1,idxx=-1;
  for(int i=0;i<s.size();i++){
    if(s[i]!='x')cc++;
    if(idx!=-1&&s[i]!='x'){idxx=i;break;}
    if(idx==-1&&cc==(n+1)/2){idx=i;}
  }
  int ans=0;
  if(n%2)idxx=idx;
  int l=idx,r=idxx;

  while(l>=0&&r<s.size()){
    if(s[l]=='x'&&s[r]=='x')l--,r++;
    else if(s[l]=='x')l--,ans++;
    else if(s[r]=='x')r++,ans++;
    else l--,r++;
  }

  if(r<s.size())ans+=(int)s.size()-r;
  else ans+=l+1;

  if(f)ans=-1;
  if(n==0)ans=0;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <tuple>
#include <algorithm>
#include <numeric>

int main()
{
    size_t x, result=1;
    std::cin >> x;
    for(size_t i=2; i < 32; ++i)
        for(auto ex = i*i; ex <= x; ex*=i)
            result = std::max(result, ex);

    std::cout << result << std::endl;
        
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define db(a) cout << fixed << #a << " = " << a << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 5;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n, k;
	cin >> n >> k;
	vector<int> A(n);
	for (int i = 0; i < n; i++) {cin >> A[i]; A[i]--;} 
	vector<int> V(n);
	vector<int> D(n, -1);
	int counter = 0;
	int cn = 0;
	D[cn] = 0;
	counter++;
	int cycle_size = 0;
	
	while (true) {
		int nn = A[cn];
		//db(nn); db(counter);
		if (counter == k) {
			cout << nn + 1 << endl;
			return 0;
		}
		if (V[nn]) {
			k -= D[nn];
			cycle_size = D[cn] - D[nn] + 1;
			cn = nn;
			break;
		} else {
			V[nn] = true;
			D[nn] = D[cn] + 1;
			counter++;
			cn = nn;
		}
	}
	//db(k); db(cycle_size); db(cn);
	k %= cycle_size;
	counter = 0;
	//db(k);
	while (true) {
		//db(cn);
		if (counter == k) {
			cout << cn + 1 << endl;
			return 0;
		}
		counter++;
		cn = A[cn];
	}
	
}



Measured memory_bytes: 5572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"
template<class T> void chmax(T &a, const T b){ a = max(a, b); }
template<class T> void chmin(T &a, const T b){ a = min(a, b); }

struct LongestCommonSubsequence {
private:
    string s, t;
    vector<vector<int>> dp;
    
public:
    LongestCommonSubsequence(const string &_s, const string &_t) : s(_s), t(_t) {}
    
    int build() {
        int ls = s.length(), lt = t.length();
        dp.resize(ls + 1, vector<int>(lt + 1, 0));
        for(int i = 0; i < ls; i++) {
            for(int j = 0; j < lt; j++) {
                if (s[i] == t[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1]);
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j]);
            }
        }
        return dp[ls][lt];
    }
    
    string restore() {
        int x = s.length(), y = t.length();
        string ans = "";
        while((x > 0) && (y > 0)) {
            if (dp[x][y] == dp[x - 1][y]) {
                x--;
            }
            else if (dp[x][y] == dp[x][y - 1]) {
                y--;
            }
            else {
                x--;
                y--;
                ans += s[x];
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    string s, t;
    cin >> s >> t;
    LongestCommonSubsequence lcs(s, t);
    lcs.build();
    cout << lcs.restore() << endl;
    return 0;
}


Measured memory_bytes: 38520
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

void  base_num(ll data,ll base){
    if(data==0) return;
    ll next=abs(data)%abs(base);
    if(data<0) next=(abs(base)-next)%abs(base);
    base_num((data-next)/base,base);
    cout << next;
}



int main (){
    ll x;
    cin >> x;
    if ((x%100)>x/100*5){
        cout << 0 << endl;
    }else{
        cout << 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

ll dfs(ll x,ll n) {
  if(x<=1) return n;
  return dfs(x/2,n*2)+n;
}

void Main() {
  ll n;
  R n;
  pr(dfs(n,1));
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
function Main(input){
    input=input.split("\n");
    tmp = input[0].split(" ");
    
  var A = parseInt(tmp[0],10);
  var B =parseInt(tmp[1],10);
  var C = parseInt(tmp[2],10);
  var D = parseInt(tmp[3],10);

  if(A+B<C+D){console.log("Right");}
  if(A+B>C+D){console.log("Left");}
  if(A+B==C+D){console.log("Balanced");}
}      
Main(require("fs").readFileSync("/dev/stdin","utf8"));
          

Measured memory_bytes: 9420
from collections import deque


def run_process(processes, slot):
    """Simulate the round-robin scheduler.
    Returns a list of (process, elapsed_time).

    >>> ps = [('p1', 150), ('p2', 80), ('p3', 200), ('p4', 350), ('p5', 20)]
    >>> run_process(ps, 100)
    [('p2', 180), ('p5', 400), ('p1', 450), ('p3', 550), ('p4', 800)]
    """
    ps = deque(processes)
    tot = 0
    finish = []

    while len(ps) > 0:
        p, t = ps.popleft()
        dt = min(t, slot)
        if dt == t:
            finish.append((p, tot+dt))
        else:
            ps.append((p, t-dt))

        tot += dt

    return finish


def run():
    count, slot = [int(i) for i in input().split()]
    ps = []

    for _ in range(count):
        p, t = input().split()
        ps.append((p, int(t)))

    for p, t in run_process(ps, slot):
        print(p, t)


if __name__ == '__main__':
    run()



Measured memory_bytes: 18084
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF mugen
#define dump(x) cerr<<#x<<"="<<x<<endl
#define all(a) (a).begin(),(a).end()
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }

using ll = long long;
const ll mod = LLONG_MAX;

int N;
int t[110],v[110];
int maxV[40010];
//x,y方向に二倍
static double dp[310][4010];
int endTime=0;
int tempEndTime=0;
double ans;
int main(){
  cin>>N;

  rep(i,40010)rep(j,240)dp[j][i]=-1;
  rep(i,N){
    cin>>t[i];
    t[i]*=2;
    endTime+=t[i];
  }
  rep(i,N){
    cin>>v[i];
    v[i]*=2;
  }
  for (int i = 0; i < 40010; i++) maxV[i] = (1 << 28);
  int sum = 0;
  for (int i = 0; i < N; i++) {
    for (int j = sum; j <= sum + t[i]; j++) {
        maxV[j] = min(maxV[j], v[i]);
    }
    sum += t[i];
  }


  // //speedが増える時
  // (speed+(speed+1))*1/2
  // //speedが減る時
  // (speed+(speed-1)*1)/2
  // //speedが変わらないとき
  // (speed+speed)*1/2;
  dp[0][0]=0;
  for(int Time = 0; Time <sum;Time++){
    for(int speed=0;speed <=maxV[Time];speed++){
      if(dp[speed][Time]<0)continue;
      for(int k=-1;k<=1;k++){
        if(speed+k<0 || speed+k>maxV[Time+1])continue;
        dp[speed+k][Time+1]=max(dp[speed+k][Time+1],dp[speed][Time] + double(2 * speed + k) / 2.0);
      }

    }
  }


  cout<<fixed<<setprecision(20)<<dp[0][sum]/4.0<<endl;
}


Measured memory_bytes: 8448
N,K = (int(i) for i in input().split())

h = []
for i in range(N):
    h.append(int(input()))

h.sort()

difference = []

for i in range(N-K+1):
    #difference.append(h[N-1-i] - h[K-1-i])
    difference.append(h[K-1+i]-h[i])
    
print(min(difference))

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

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v) { bool first = true;string res = "{"; for (const auto &x : v) {if (!first) {res += ", ";} first = false; res += to_string(x);} res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = n/(a+b) * a;
    ans += min(n % (a+b), a);
    cout << ans;
}


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

using namespace std;

int main() {
	int A, B, C, D;
	string in;
	cin >> in;
	A = in[0] - '0', B = in[1] - '0', C = in[2] - '0', D = in[3] - '0';
	for (int i = 0; i < 8; i++) {
		int ans = A;
		string out;
		if (i & 1)ans += B, out += '+';
		else ans -= B, out += '-';
		if (i & 2)ans += C, out += '+';
		else ans -= C, out += '-';
		if (i & 4)ans += D, out += '+';
		else ans -= D, out += '-';
		if (ans == 7) {
			cout << A << out[0] << B << out[1] << C << out[2] << D << "=7" << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256