akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main () {
  int n,k;
  cin>>n>>k;
  string a;
  cin>>a;
  vector<int> b(n);
  vector<int> c(n);
  int j=0;
  if (a[0]=='0') {
    j+=1;
  }
  
  for (int i=0;i<n-1;++i) {
    if (a[i]=='0' && a[i+1]=='1') {
      b[j]=i+1;
    }
    if (a[i]=='1' && a[i+1]=='0') {
      c[j]=i;
      j+=1;
    }
  }
  
  if (a[n-1]=='1') {
    c[j]=n-1;
  } else {
    b[j]=n-1;
    c[j]=n-1;
  }
  
  int ans=0;
  for (int l=0;l<=j;++l) {
    for (int t=0;t<=k;++t) {
    	int p=c[l+t]-b[l]+1;
    	ans=max(ans,p);
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
            #include<ext/pb_ds/assoc_container.hpp>
            #include<ext/pb_ds/tree_policy.hpp>
            using namespace __gnu_pbds;
            using namespace std;
            # define ll long long
            # define int long long  //comment it out when MLE
           // # define endl "\n"
            template <typename T>
            using ordered_set = tree<T, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

            #define gok ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
            //# define m 163577857
            # define mo 1000000007
            # define pi acos(-1)
            # define fi first
            # define se second
            #define REP(i,n) for (int i = 1; i <= n; i++)
            const ll mod =  998244353;
            //const int K = 2;
            //typedef vector<vector<int> > matrix;

          int add(int a, int b,int mod) {
                a%=mod;
                b%=mod;
                a += b;
                if (a >= mod) a -= mod;
                if(a<0)
                {
                    a += mod;
                    a %= mod;
                }
                return a;
            }

            int mul(ll a, int b,int mod) {
                a%=mod;
                b%=mod;
                a *= b;
                a += mod;
                return a % mod;
            }
            int po(int a,int b,int mod)
            {
                if(b==0)
                    return 1;
                if(b%2==0)
                    return po(mul(a,a,mod),b/2,mod);
                return mul(a,po(mul(a,a,mod),(b-1)/2,mod),mod);
            }


            ll fact[2000003];
            ll inv[2000003];

            void fact0()
            {
                int i,j;
                fact[0]=1;
                for(i=1;i<=2000000;i++)
                {
                    fact[i]=i*fact[i-1]%mod;
                }
                inv[0]=1;
                inv[1]=1;
                ll p=mod;
                for (i=2; i<=2000000; i++)
                    inv[i] = (p - (p/i) * inv[p%i] % p) % p;

                for(i=2;i<=2000000;i++)
                {
                    inv[i]*=inv[i-1];
                    inv[i]%=mod;
                }
            }
            int help(int a,int b)
            {
               // cout<<a<<" "<<b<<endl;
                int an = fact[a];
                //cout<<an<<endl;
                an *= inv[b];
                an %= mod;
                an *= inv[a-b];
                an %= mod;
                return an;
            }
/*
          void random()
            {
              srand(time(0));
            for (int i = 0; i < n; i ++)
                perm[i] = i + 1;
            random_shuffle(perm, perm + n);
            }
int ncr(int a,int b)
{
    int tt = fact[a];
    tt %= mod;
    tt *= inv[a-b];
    tt %= mod;
    tt *= inv[b];
    tt %= mod;
    return tt;
}
*/

signed main() {
	gok

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

    int n;
    cin>>n;

    int d = n/1000;
    if(n%1000)
        d++;

    int nn = d*1000;
    cout<<nn-n;










 }























  return 0;
}


Measured memory_bytes: 3688
// inputに入力データ全体が入る
function Main(input) {
  // 1行目がinput[0], 2行目がinput[1], …に入る
  input = input.split("\n");
  const tmp = input[1].split(" ").map(n => parseInt(n,10));
  const sorted = tmp.sort((a, b) => b - a);
  var alice = 0, bob = 0;
  sorted.forEach((value, index) => {
    if (index % 2 === 0) alice += value;
    if (index % 2 !== 0) bob += value;
  });

  console.log(alice - bob);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
# coding: utf-8

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0 

ta = A[-1]

for a, b in list(zip(A[:-1], B))[::-1]:

    tb = b
    if ta >= b:
        ans += b
        ta = a
        continue
    else:
        ans += ta
        tb -= ta
        ta = 0
        

    if a >= tb:
        ans += tb
        ta = a - tb
    else:
        ans += a
        ta = 0

print(ans)

Measured memory_bytes: 19244
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
signed main()
{
	int n=read();
	cout<<(n-2)*180;
	return 0;
	//NOTICE LONG LONG!!!!!
}

Measured memory_bytes: 256
import sys
import math
from pprint import pprint
 
A, B, N = map(int, sys.stdin.readline().strip().split())
 
def func(x):
    return A*x//B - A*(x//B)
 
 
right = N
left = 0
while right - left > 5:
    mid_left = right//3+left*2//3
    mid_right = right*2//3+left//3
    # print("mid", mid_left, mid_right)
    if mid_left == mid_right:
        break
    # print("func", func(mid_left), func(mid_right))
    if func(mid_left) <= func(mid_right):
        left = mid_left
    else:
        right = mid_right
    # print("lr", left, right)
 
ans = -1 * float("inf")
for i in range(left, right+1):
    # print(i, func(i))
    ans = max(ans, func(i))
print(ans)

Measured memory_bytes: 9800
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    int N, K;
    
    cin >> N >> K;
    
    vector<int> A(N);
    map<int, int> m;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        m[A[i]]++;
    }
    
    vector<int> counts;
    for (auto item : m) {
        counts.push_back(item.second);
    }
    sort(counts.begin(), counts.end());
    
    int ans = 0;
    int idx = 0;
    if (counts.size() <= K) {
        ans = 0;
    } else if (counts.size() > K) {
        while ((counts.size() - idx) > K) {
            counts[idx]--;
            ans++;
            if (counts[idx] == 0) {
                idx++;
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 11516
n = int(input())
a = []
for x in range(n):
  b = [int(xx) for xx in input().split()]
  a.append(b)
a.sort(key = lambda x : x[1])
#print(a)

i = 0
k = 1
for x in a:
  if(i + x[0] > x[1]):
    k = 0
    break
  i = i + x[0]
if(k == 1):print("Yes")
else:print("No")


Measured memory_bytes: 41176
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

const int INF = 1001001001;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};

int main() {
  int h, w, ans=0;
  cin >> h >> w;
  vector<string> s(h);
  REP(i,h) cin >> s[i];

  // 始点 si, sj
  REP(si,h) {
    REP(sj,w) {
      if (s[si][sj] == '#') continue;
      vector<vector<int>> dist(h, vector<int>(w, INF));
      queue<pair<int, int>> q;
      // func
      auto update = [&](int i, int j, int x) {
        if (dist[i][j] != INF) return;
        dist[i][j] = x;
        q.push(make_pair(i,j));
      };
      update(si, sj, 0);
      while(!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        REP(dir,4) {
          int ni = i+di[dir];
          int nj = j+dj[dir];
          if (ni<0||ni>=h||nj<0||nj>=w) continue;
          if (s[ni][nj] == '#') continue;
          update(ni,nj,dist[i][j]+1);
        }
      }
      REP(i,h) {
        REP(j,w) {
          if (dist[i][j] == INF) continue;
          ans = max(ans, dist[i][j]);
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
import time
import math
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

S = input()
T = S[::-1]
ans = 0
for i in range(len(S)//2):
	if S[i] != T[i]:
		ans += 1
print(ans)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)


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

//セグ木ここから
//*
//↓ここを変える
typedef struct atai{ll a;}atai;
atai xx(atai x,atai y){
	atai r;
	r.a=max(x.a,y.a);
	return r;
}
atai aid={0};
//↑ここを変える

int segNUM;
atai *segN,*seg;
void seguse(int n){
	segN=(atai*)calloc(2*n,sizeof(atai));
	segNUM=n;
	seg=segN+segNUM;
	rep(i,1,2*segNUM)segN[i]=aid;
}
//seg[]に値を与えてから初期化
void seginit(){for(int node=segNUM-1;node;node--)segN[node]=xx(segN[node*2],segN[node*2+1]);}
void segupdate(int node,atai x){
	//seg[node]をxに更新
	node+=segNUM;
	segN[node]=x;
	while(node/=2)segN[node]=xx(segN[node*2],segN[node*2+1]);
}

atai segcalcsub(int l,int r,int k,int cl,int cr){
	if(l>=r)return aid;
	//完全に含むとき
	if(l<=cl&&cr<=r)return segN[k];

	int cm=(cl+cr)/2;
	//左側だけ
	if(r<=cm)return segcalcsub(l,r,2*k  ,cl,cm);
	//右側だけ
	if(cm<=l)return segcalcsub(l,r,2*k+1,cm,cr);
	//両方
	return xx(segcalcsub(l,r,2*k,cl,cm),segcalcsub(l,r,2*k+1,cm,cr));
}
atai segcalc(int l,int r){return segcalcsub(l,r,1,0,segNUM);}
//セグ木ここまで
//*/


int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	
	seguse(1<<19);
	rep(i,0,n){
		int a;
		scanf("%d",&a);
		atai x=segcalc(max(0,a-k),min(300010,a+k+1));
		x.a++;
		segupdate(a,x);
	}
	
	printf("%lld",segcalc(0,300010).a);
}



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

int main()
{
    int R, C, K;
    cin>>R>>C>>K;
    vector<vector<long long>> V(R, vector<long long>(C));
    for (int k=0; k<K; k++)
    {
        int r, c, v;
        cin>>r>>c>>v;
        V[r-1][c-1] = v;
    }

    vector<long long> T(C);
    long long T2[4] = {};
    for (int x=0; x<C; x++)
    {
        for (int i=2; i>=0; i--)
            T2[i+1] = max(T2[i+1], T2[i]+V[0][x]);
        for (int i=0; i<=3; i++)
            T[x] = max(T[x], T2[i]);
    }

    for (int y=1; y<R; y++)
    {
        vector<long long> P(C);
        P.swap(T);

        long long T2[4] = {};
        for (int x=0; x<C; x++)
        {
            T2[0] = max(T2[0], P[x]);
            for (int i=2; i>=0; i--)
                T2[i+1] = max(T2[i+1], T2[i]+V[y][x]);
            for (int i=0; i<=3; i++)
                T[x] = max(T[x], T2[i]);
        }
    }

    cout<<T[C-1]<<endl;
}


Measured memory_bytes: 73436
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],f[100010];
int main()
{
	memset(f,0x3f,sizeof(f));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	f[1]=0;
	f[2]=abs(a[1]-a[2]);
	for(int i=3;i<=n;i++)
	{
		f[i]=min(abs(a[i]-a[i-1])+f[i-1],abs(a[i]-a[i-2])+f[i-2]);
	}
	printf("%d",f[n]);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string s, t; cin >> s >> t;
  int min = t.size();
  
  for (int i=0; i<=s.size()-t.size(); i++){
    int cnt=0;
    for (int j=0; j<t.size(); j++){
      if(s.at(i+j)!=t.at(j)){
        cnt++;
      }
    }
    if (min > cnt){ min = cnt;}
  }
   cout << min << endl;     
}

Measured memory_bytes: 3580
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
	map<string, int> box;
	int N, M;
	int max = 0;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string tmp;
		cin >> tmp;
		box[tmp]++;
	}

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		string tmp;
		cin >> tmp;
		box[tmp]--;
	}
	
	for (auto it = box.begin();it != box.end();it++) {
		if (it->second > max)
			max = it->second;
	}

	cout << max << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main()
{
  int n,a,b,cnt=0;
  cin >> n;
  cin >> a;
  cin >> b;
  for(int i=1; i<n+1; i++){
    int sum = i/10000 + i/1000%10 + i/100%10 + i/10%10 + i%10;
    if(a<=sum && sum<=b){
      cnt+=i;
    }
  }
  cout<< cnt <<endl;
}

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

typedef long long ll;

int main(void) {

    int N; cin >> N;
    ll words[5];
    for (int i = 0; i < 5; i++) words[i] = 0;

    for (int i = 0; i < N; i++) {
        string S; cin >> S;
        char c = S[0];
        switch (c) {
            case 'M':
                words[0]++; break;
            case 'A':
                words[1]++; break;
            case 'R':
                words[2]++; break;
            case 'C':
                words[3]++; break;
            case 'H':
                words[4]++; break;
        }
    }

    ll ans = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = i+1; j < 5; j++) {
            for (int k = j+1; k < 5; k++) {
                ans += words[i]*words[j]*words[k];
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <list>

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

int main() {
    int r, g;
    cin >> r;
    cin >> g;
    int ans = g*2 - r;
    cout << ans << endl;

}

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

int main() {
  vector<char>A(4);
  for(int i=0;i<4;i++){
    cin >> A.at(i);
  }
  sort(A.begin(),A.end());
  if(A.at(0)==A.at(1)&&A.at(2)==A.at(3)&&A.at(0)!=A.at(2)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

int main(){
  string s, t;
  cin >> s >> t;
  int len = s.length();
  int ans = 0;
  for(int i = 0; i < len; ++i){
    if(s[i] != t[i]){
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3892
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define lu unsigned long long int
#define pi pair<ll, ll>
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mk make_pair
#define ve vector
#define lr(n) for (ll i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define be begin
#define sz(a) (ll)(a.size())
#define INF 1e18
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

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

// ll mod = 1e9+7;

// ll mult(ll x, ll y){
//     ll rem=1;
//     while(y){
//         if(y&1){
//             rem=(rem*x)%mod;
//         }
//         x=(x*x)%mod;
//         y>>=1;
//     }
//     return rem;
// }

ll dp[200005]={0};
ll t1[200005]={0};
ll t2[200005]={0};
void solve(ll T){
	ll n;
	cin>>n;
	string s;
	cin>>s;
	ll cnt=0;
	for(ll i=0;i<n;i++){
		if(s[i]=='1') cnt++;
	}
	if(cnt==0){
		for(ll i=0;i<n;i++){
			cout << "1\n";
		}
		return;
	}
	ll mod1=0, mod2=0;
	for(ll i=n-1,x1=1,x2=1%(cnt+1);i>=0;i--){
		if(cnt-1>=1){
			t1[n-i-1]=x1%(cnt-1);
		}
		t2[n-i-1]=x2;
		if(s[i]=='1'){
			if(cnt-1>=1){
				mod1=(mod1+x1)%(cnt-1);
			}
			mod2=(mod2+x2)%(cnt+1);
		}
		if(cnt-1>=1) x1=(x1*2)%(cnt-1);
		x2=(x2*2)%(cnt+1);
	}

	for(ll i=1;i<=200000;i++){
		ll p=__builtin_popcount(i);
		dp[i]=1+dp[i%p];
	}

	for(ll i=0;i<n;i++){
		if(s[i]=='1'){
			if(cnt==1){
				cout << "0\n";
				continue;
			}
			ll m=(mod1-t1[n-1-i]+cnt-1)%(cnt-1);
			// cout << m << " :\n";
			cout << dp[m]+1 << "\n";
		}
		else{
			ll m=(mod2+t2[n-1-i])%(cnt+1);
			// cout << m << " :\n";
			cout << dp[m]+1 << "\n";
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// std::cout << std::unitbuf;
	ll T=1;
	// cin>>T;
	for(ll t=1;t<=T;t++){
		solve(t);
	}
	return 0;
}

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

const string YES = "POSSIBLE";
const string NO = "IMPOSSIBLE";

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
void solve(long long N, long long K, std::vector<long long> A)
{
    long long gc = 0, ma = 0;
    for (int i = 0; i < N; i++)
        gc = gcd(A[i], gc), ma = max(ma, A[i]);
    if (K % gc)
    {
        cout << NO << endl;
        return;
    }
    if (K > ma)
    {
        cout << NO << endl;
        return;
    }
    cout << YES << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    long long K;
    scanf("%lld", &K);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &A[i]);
    }
    solve(N, K, std::move(A));
    return 0;
}


Measured memory_bytes: 4024
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long int ll;
template<typename T> T changeMax(T& a, T b){if(a < b)a = b;return 0;}
const ll MOD = 1000000007;

int main()
{
    int a, b, ans = 0;
    cin >> a >> b;
    if(a <= b){
        ans += a;
    }
    else{
        ans += a-1;
    }
    cout << ans << endl; 
    return 0;
}

Measured memory_bytes: 256
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 ) *} } ;}
macro_rules !read_value {($next :expr ,($($t :tt ) ,*) ) =>{($(read_value !($next ,$t ) ) ,*) } ;($next :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($next ,$t ) ) .collect ::<Vec <_ >>() } ;($next :expr ,chars ) =>{read_value !($next ,String ) .chars () .collect ::<Vec <char >>() } ;($next :expr ,usize1 ) =>{read_value !($next ,usize ) -1 } ;($next :expr ,$t :ty ) =>{$next () .parse ::<$t >() .expect ("Parse error" ) } ;}

const MOD: usize = 1000000007;

fn main() {
   input! {
      _k: String,
      d: usize,
   }

   let k: Vec<usize> = _k.as_bytes().iter().map(|&b| (b - b'0') as usize).collect();
   let n = k.len();

   let mut dp = vec![vec![0; d]; n];
   let mut s = k[0];
   for i in 0..k[0] {
      dp[0][i % d] += 1;
   }
   for i in 1..n {
      for j in 0..10 {
         for l in 0..d {
            dp[i][(l + j) % d] += dp[i - 1][l % d];
            dp[i][(l + j) % d] %= MOD;
         }
      }
      for j in s..s + k[i] {
         dp[i][j % d] += 1;
      }
      s += k[i];
      s %= d;
   }
   dp[n - 1][s % d] += 1;

   dp[n - 1][0] += MOD - 1;
   dp[n - 1][0] %= MOD;

   println!("{}", dp[n - 1][0]);
}


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

const int N = 1010;

int A[N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, a, b;
	cin >> n >> m >> a >> b;
	for (int j = 0; j < a; ++j) {
		for (int i = 0; i < b; ++i) {
			A[i][j] = 0;
		}
		for (int i = b; i < n; ++i) {
			A[i][j] = 1;
		}
	}
	for (int j = a; j < m; ++j) {
		for (int i = 0; i < b; ++i) {
			A[i][j] = 1;
		}
		for (int i = b; i < n; ++i) {
			A[i][j] = 0;
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << A[i][j];
		}
		cout << '\n';
	}
	return 0;
}


Measured memory_bytes: 5248
/*
[diverta2019-2] D - Squirrel Merchant
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int P = 2;
const int Q = 3;
const int MAX_N = 5000;
const int MAX_C = 5000;

int N;
int c[P][Q];
ll dp[MAX_N * MAX_C + 1][Q + 1];

ll solve() {
    ll W = N;
    for (int p = 0; p < P; p++) {
        int w[3], v[3];
        for (int q = 0; q < Q; q++) {
            w[q] = c[p][q];
            v[q] = c[p ^ 1][q] - c[p][q];
        }

        memset(dp, 0, sizeof(dp));
        for (int q = 1; q <= Q; q++) {
            for (int i = 0; i <= W; i++) {
                dp[i][q] = dp[i][q - 1];
                if (i >= w[q - 1]) {
                    dp[i][q] = max(dp[i][q], dp[i - w[q - 1]][q] + v[q - 1]);
                }
            }
        }
        W += dp[W][Q];
    }

    return W;
}

int main() {
    cin >> N;
    for (int p = 0; p < P; p++) {
        for (int q = 0; q < Q; q++) {
            cin >> c[p][q];
        }
    }

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 781568
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;

int main( void )
{
	ll x, y, a, b, c;

	cin >> x >> y >> a >> b >> c;

	ll p[a];
	for ( ll& _p : p ) {
		cin >> _p;
	}
	sort(p, p + a);

	ll q[b];
	for ( ll& _q : q ) {
		cin >> _q;
	}
	sort(q, q + b);

	ll r[c];
	for ( ll& _r : r ) {
		cin >> _r;
	}
	sort(r, r + c);

	ll ans[x + y];
	memcpy(ans, &p[a - x], sizeof(ll) * x);
	memcpy(&ans[x], &q[b - y], sizeof(ll) * y);
	sort(ans, ans + x + y);

	ll i = 0, j = c - 1;
	while ( (j >= 0) && (ans[i] < r[j])  ) {
		ans[i] = r[j];
		i++;
		j--;
	}

	ll out = 0;
	for ( ll& _ans : ans ) {
		out += _ans;
	}
	cout << out << endl;
}


Measured memory_bytes: 3968
import java.util.Scanner;

public class Main{

	private static int n;
	private static int m;

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

		for(int i = 0; i < n; i++) {
			a[i] =-1* sc.nextInt();
		}

		MyHeap heap = new MyHeap(a);

		for(int i = 0; i < m; i++) {
			int max = heap.pop()/2;
			heap.push(max);
		}

		long sum = 0;
		for(int i = 0; i < n; i++) {
			sum -= heap.heap[i];
		}
		System.out.println(sum);

		sc.close();
	}
	private static class MyHeap {

		int[] heap;
		int sz;//空の先頭

		MyHeap(int[] a){
			this.heap = new int[n+1];//最大容量
			this.sz = 0;
			for(int i = 0; i < a.length; i++) {
				this.push(a[i]);
			}
		}

		void push(int x) {
			int i = sz++;
			while(i > 0) {
				int p = (i-1)/2;
				if(heap[p] <= x) break;
				heap[i] = heap[p];
				i = p;
			}
			heap[i] = x;
		}

		 int pop() {
			int ret = heap[0];
			int x = heap[--sz];
			int i = 0;
			while(i*2+1<sz) {
				int a = i*2+1; int b = i*2+2;
				if(b < sz && heap[b] < heap[a]) a = b;
				if(heap[a] >= x) break;
				heap[i] = heap[a];
				i = a;
			}
			heap[i] = x;
			return ret;
		}
	}
}

Measured memory_bytes: 50012
#include<stdio.h>
int main(){
  int n,k,q,pe[100002],a,i;
  scanf("%d%d%d",&n,&k,&q);
  for(i=0;i<n;i++)
    pe[i]=k-q;
  for(i=0;i<q;i++){
    scanf("%d",&a);
    pe[a-1]+=1;
  }
  for(i=0;i<n;i++){
    if(pe[i]>0)
      printf("Yes\n");
    else
      printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 896
def colsum(n):
    ret = 0
    num = n
    while num >= 10:
        ret += num%10
        num //= 10
    ret += num
    return ret

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

n,a,b = iim()
cnt = 0
for i in range(1,n+1):
    if a <= colsum(i) <= b:
        cnt += i
print(cnt)

Measured memory_bytes: 3060
#include <stdio.h>

int main(void){
	char ch;
	int alpha[26]={0},i;
	while(scanf("%c",&ch)!=EOF){
		if('A'<=ch && ch<= 'Z'){
			alpha[ch-'A']++;
		}
		else if('a'<=ch && ch<= 'z'){
			alpha[ch-'a']++;
		}
	}
	for(i=0;i<26;i++){
		printf("%c : %d\n",'a'+i,alpha[i]);
	}
	return 0;
}

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

using namespace std;

#define ull unsigned long long
#define ll long long
#define int long long
#define ld long double

#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define MX LLONG_MAX
#define MN LLONG_MIN

const ll mod=1e9+7;
const ll N=1e5+5;

ll powermodm(ll x,ll n,ll M){ll result=1;while(n>0){if(n % 2 ==1)result=(result * x)%M;x=(x*x)%M;n=n/2;}return result;}
ll power(ll _a,ll _b){ll _r=1;while(_b){if(_b%2==1)_r=(_r*_a);_b/=2;_a=(_a*_a);}return _r;}
ll gcd(ll a,ll b){if(a==0)return b;return gcd(b%a,a);}          
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}

int32_t main()                  
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    set<char> ms; 
    for(ll i=0;i<4;i++)
        ms.insert(s[i]);
    if(ms.size()==2)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

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

using namespace std;

#define long long long

const long MAXA = 1e16 + 1000;

long k, c[50];

bool Try(long n)
{
    long lo = (k - n) / (n + 1) + 1;
    long excess = k - lo * n;
    for (int i = 0; i < n; ++i)
    {
        c[i] = lo;
        long add = min(excess, (MAXA + k - n + 1) / (n + 1) - c[i]);
        c[i] += add;
        excess -= add;
    }
    return excess == 0;
}

int main()
{
    scanf("%lld", &k);
    if (k == 0)
    {
        printf("2\n1 1");
        return 0;
    }
    for (long i = 2; i <= 50; ++i)
        if (Try(i))
        {
            printf("%lld\n", i);
            for (int j = 0; j < i; ++j) printf("%lld ", i - 1 + (i + 1) * c[j] - k);
            break;
        }
    return 0;
}


Measured memory_bytes: 128
fun main(args: Array<String>){

    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map(String::toInt)
    var count = 0

    for(i in 1..n-2){
        if(list[i-1]<list[i] && list[i]<list[i+1]){
            count++
        }
        else if(list[i+1]<list[i] && list[i]<list[i-1]){
            count++
        }
    }

    println(count)


}

Measured memory_bytes: 38032
from collections import defaultdict

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = defaultdict(int)
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

N = int(input())
MOD = 10**9 + 7
factors = defaultdict(int)
for i in range(2, N+1):
    fac = prime_factorization(i)
    for p, n in fac.items():
        factors[p] += n
ans = 1
for _, n in factors.items():
    ans = (ans * (n+1)) % MOD
print(ans)

Measured memory_bytes: 32876
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch AnOddProblem | diff AnOddProblem.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address AnOddProblem.cpp && ./a.out

/*

 7/11/2020

 5:02-

 */

const int MAX_N=1e6+1;
int A[MAX_N];
int N;

void solve() {
  int res=0;
  REP(i,N) if((i+1)%2&&A[i]%2) ++res;
  cout<<res<<endl;
}

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

  cin>>N;
  REP(i,N) cin>>A[i];
  solve();

  return 0;
}


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

using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back

const int mod = 998244353;
ll madd(ll a, ll b) { return a + b >= mod ? a + b - mod : a + b; }
ll mmult(ll a, ll b) { return a * b >= mod ? a * b % mod : a * b; }

const int N = 3000, S = 3000;
int n, s;
vector<int> v;
int dp[N][S + 1];

ll go(int at, int cs) {
    if(cs == s) return n - at + 1;
    if(at == n) return 0;
    if(dp[at][cs] != -1) return dp[at][cs];
    ll res = 0;
    if(cs + v[at] <= s)
        res = madd(res, go(at + 1, cs + v[at]));
    res = madd(res, go(at + 1, cs));
    dp[at][cs] = res;
    return res;
}


void solve() {
    cin >> n >> s;
    v.resize(n);
    for(int i = 0 ; i < n ; i++)
        cin >> v[i];
    for(int i = 0 ; i < N ; i++)
        fill(dp[i], dp[i] + (S + 1), -1);
    ll res = 0;
    for(int i = 0 ; i < n ; i++)
        if(v[i] <= s)
            res = madd(res, mmult(i + 1, go(i + 1, v[i])));
    cout << res << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
    cout.flush();
	return 0;
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int hp[2], at[2];
	cin >> hp[0] >> at[0] >> hp[1] >> at[1];
	for(int i = 0;; ++i){
		if(i % 2 == 0){
			hp[1] -= at[0];
			if(hp[1] <= 0){
				cout << "Yes" << endl;
				return 0;
			}
		}else{
			hp[0] -= at[1];
			if(hp[0] <= 0){
				cout << "No" << endl;
				return 0;
			}
		}
	}
}

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

int main(){
    int N;
    char s[300001];
    cin>>N;
    cin>>s;

    int e[300001];
    int w[300001];
    e[0] = 0;
    w[0] = 0;

    for(int i=0; i<N; i++){
        e[i+1] = e[i];
        w[i+1] = w[i];
        if(s[i] == 'E') e[i+1]++;
        if(s[i] == 'W') w[i+1]++;
    }
    int min = N;
    for(int i=0; i<N; i++){
        int sum = 0;
        sum += w[i];
        sum += e[N]-e[i+1];
  

        if(min>sum) min=sum;
    }
    cout<<min<<endl;
    return 0;
}

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


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

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

    double tmp = (v[0]+v[1])/2;
    for(int i=0;i<N-2;i++){
        tmp = (tmp+v[i+2])/2;
    }

    cout << tmp << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define inf 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
using namespace std;

int n,m;
bool used[200005];
vector<int>vec[200005];
void dfs(int x){
	used[x]=true;
	rep(i,vec[x].size()){
		if(!used[vec[x][i]]){
			dfs(vec[x][i]);
		}
	}
}
signed main(){
	cin>>n>>m;
	rep(i,n){
		int k;cin>>k;
		rep(j,k){
			int a;cin>>a;
			vec[i].push_back(a+n);
			vec[a+n].push_back(i);
		}
	}
	dfs(0);
	rep(i,n){
		if(!used[i]){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
}


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

int main(){
    static long long int N, a, b[100000], i, ret = 1, bi = 2;
    static char c;
    for(c = getchar(); c != 10; c = getchar()){
        N = ((N * 5) << 1) + c - 48;
    }
    ++(*b);
    for(i = 0; i < N; ++i){
        for(c = getchar(), a = 0; c != 32 && c != 10; c = getchar()){
            a = ((a * 5) << 1) + c - 48;
        }
        ++b[a];
    }
    for(i = ~N & 1; i < N; i += 2){
        if(b[i] != 2){
            puts("0");
            return 0;
        }
    }
    N >>= 1;
    while(N){
        if(N & 1){
            ret *= bi;
            ret %= 1000000007;
        }
        bi *= bi;
        bi %= 1000000007;
        N >>= 1;
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<algorithm>//everybody dies in their nightmares
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
#include<vector>
#include<sstream>
#include<cmath>
#include<unordered_set>
#include<unordered_map>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll phi(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n) { ll s = 1;while (n) { if (n & 1) { s = s * a % mod; }a = (a*a) % mod;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }

bool isPrime(long long x) { if (x <= 1)return false;if (x == 2)return true;if (x % 2 == 0)return false;long long i, m;m = sqrt(x);f(i, 2, m) { if (x % i == 0)return false; }return true; }

const int N = 1e5 + 5;
int t;
int main()
{
	ll n,a, b;
	while (cin >> n >> a >> b)
	{
		ll ans = quickmod(2, n) - 1;//p1
		ll a1 = 1, b1 = 1;
		f(i, 1, a)
		{
			a1 = a1 * (n - i + 1)%mod;//n-1+1
			a1 = a1 * inv(i, mod) % mod;
		}
		f(i, 1, b)
		{
			b1 = b1 * (n - i + 1) % mod;//n-1+1
			b1 = b1 * inv(i, mod) % mod;
		}
		
		ans += mod;
		ans += mod;
		//debug(ans);
		//debug(a1);
		//debug(b1);
		cout << (ans - b1 - a1)%mod << endl;
	}
	return 0;
}




Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>

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

int main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	ll ans=0;
	for(int k=0; k<(1<<n); k++){
		string t1, t2;
		for(int i=0; i<n; i++){
			if(((k>>i)&1)==1){
				t1+=s[i];
			}else{
              t2+=s[i];
            }
		}
        
      reverse(t1.begin(), t1.end());
      reverse(t2.begin(), t2.end());
		ll dp[19][19]={};
		int m=t1.length();
		dp[0][0]=1;
		for(int i=1; i<=n; i++){
			for(int j=0; j<=m; j++){
				if(j>=1 && s[n+i-1]==t1[j-1]){
					dp[i][j]+=dp[i-1][j-1];
				}
              if(i-j-1>=0 && s[n+i-1]==t2[i-j-1]){
                dp[i][j]+=dp[i-1][j];
              }
			}
		}
     
		ans+=dp[n][m];
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
object Main extends App {
  val sc = new java.util.Scanner(System.in)

  val n = sc.nextInt
  val list = List.fill(n)(sc.nextInt())

  val map = list.groupBy(identity).mapValues(_.size).toMap
  var delete_count = 0
  var checked = Map[Int, Boolean]()

  list.foreach({e =>
    if (checked.isDefinedAt(e)) {
    } else {
      if (map(e) > e) {
        delete_count += map(e) - e
      }

      if (map(e) < e) {
        delete_count += map(e)
      }

      checked += (e -> true)
    }
  })
  println(delete_count)
}


Measured memory_bytes: 121636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> s(m),c(m);
    rep(i,m){
        cin >> s[i] >> c[i];
        s[i]--;
    }
    for(int i = 0;i < 1000;i++){
        string str = to_string(i);
        int cnt = str.size();
        bool flag = true;
        rep(j, m)
        {
            if(str[s[j]]-'0' != c[j]){
                flag = false;
            }
        }
        if (cnt == n && flag)
        {
            cout << i << "\n";
            return 0;
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;

import java.util.*;

public class Main {
    long MOD = (long) 1e9 + 7;

    InputStream in;
    OutputStream out;

    public Main() {
        this(System.in, System.out);
    }

    public Main(InputStream in, OutputStream out) {
        this.in = in;
        this.out = out;
    }

    void run() {
        Scanner sc = new Scanner(this.in);
        PrintWriter out = new PrintWriter(this.out);

        // write your code
        int n = sc.nextInt();
        int[] a = new int[n];
        int all = 0;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            all ^= a[i];
        }
        out.print(a[0] ^ all);
        for (int i = 1; i < n; i++) {
            out.print(" " + (a[i] ^ all));
        }
        out.println();

        out.flush();
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

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

Measured memory_bytes: 61236
N, Y = map(int, input().split())
result = [-1, -1, -1]
for i in range(N+1):
    for j in range(N-i+1):
        k = N - (i+j)
        price = 10000 * i + 5000 * j + 1000 * k
        if price == Y:
            result = [i, j, k]
            break

print(*result)

Measured memory_bytes: 3060
N,K = map(int,input().split())

A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]
flag = [-1] * N

for i in range(N):
  town[i] = [i,A[i] - 1]

f = 0

while flag[f] == -1:
  t = town[f][1]
  flag[f] = t
  f = town[t][0]
  visited.append(t)
  
l = visited[-1]
lv = len(visited)

if K <= lv:
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:-1]
  lc = len(cycle)
  print(cycle[(K - lv + 1) % lc] + 1)
##i

Measured memory_bytes: 50452
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using ll = long long int;
using vec = vector<int>;
using P = pair<int,int>;
const int INF = 1e9+7;

int main() {
  int x, n;
  cin >> x >> n;
  vec p(n);
  bool f = true;
  rep(i,n) {
    cin >> p[i];
    if (p[i] == x) f = false;
  }

  if (f) {
    cout << x << endl;
    return 0;
  }

  sort(all(p));
  int idx = lower_bound(all(p), x) - p.begin();
  int i = 0;
  while (true) {
    if (idx-i < 0) {
      cout << x-i << endl;
      return 0;
    }
    if (p[idx-i] != x-i) {
      cout << x-i <<endl;
      return 0;
    }
    if (idx+i >= n) {
      cout << x+i << endl;
      return 0;
    }
    if (p[idx+i] != x+i) {
      cout << x+i << endl;
      return 0;
    }
    i++;
  }
}


Measured memory_bytes: 3628
from collections import Counter
N = int(input())
L = [input() for _ in range(N)]
#for n in range(N):
    #S = input()
    #L.append(S)
Dic = Counter(L)
max_value = max(Dic.values())
max_k_list = [i for i, j in Dic.items() if j == max_value]
max_k_list = sorted(max_k_list)
for t in max_k_list:
    print(t)

Measured memory_bytes: 35576
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if (b - a == c - b)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define LLINF (1LL<<60)
typedef unsigned long long ll;
 
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)
#define mod 1000000007
 
//C++14 (GCC 5.4.1)
 
ll powmod(ll x,int n){
    ll ans=1,y=x;
    int k=n;
    while(k){
        if(k&1) ans= (ans*y)%mod;
        y=(y*y)%mod;
        k/=2;
    }
    return ans;
}
#define inv(x) powmod(x,mod-2)
#define needF 2000
ll f[needF+1], rf[needF+1];//f[x]=x!
void initF() {
    f[0] = 1;
    repd(i,1,needF+1) f[i]=( f[i-1]*i ) % mod;
    rf[needF] = inv(f[needF]);
    rrepd(i, needF-1, 0) rf[i] = (rf[i+1] * (i+1)) % mod;
}
ll nCk(int n, int k) {
    if(n<k) return 0;
    ll bc = ( rf[n-k]*rf[k] ) % mod;
    return (f[n]*bc) % mod;
}
#define nHk(n,k) nCk((n)+(k)-1,k)
 
 
int main() {
    int N,K;
    cin >>N>>K;
    initF();
    repd(i,1,K+1){
        cout<< (nCk(N-K+1,i)*nCk(K-1,i-1))%mod<<endl;
    }
 
    return (0);
}

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

int main(){
    int n,x;
    cin>>n>>x;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    long long int sum=0;
    for(int i=0;i<n-1;i++){
        if(a[i]+a[i+1]>x){
            int dis=a[i]+a[i+1]-x;
            if(a[i+1]-dis>=0){
                a[i+1]-=dis;
                sum+=dis;
            }
            else{
                a[i+1]=0;
                sum+=dis;
            }

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



Measured memory_bytes: 640
from sys import stdin
import heapq


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    As = []
    for i in [int(x) for x in stdin.readline().rstrip().split()]:
        heapq.heappush(As, -i)
    for _ in range(M):
        x = heapq.heappop(As)
        heapq.heappush(As, -(-x // 2))
    print(sum([-1 * x for x in As]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 14180
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)


using namespace std;


int64_t dp[101][4];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	string s; cin >> s;
	int k; cin >> k;

	dp[0][0] = 1;
	dp[0][1] = (s[0] - '0') - 1;
	if (k == 1) dp[0][1]++;
	int c =	1;
	FOR_LT(i, 1, s.size()) {
		int v = s[i] - '0';

		if (c < k) {
			if (v != 0) {
				dp[i][c + 1] += v - 1;
				if (c + 1 == k) dp[i][c + 1]++;
				dp[i][c]++;
				c++;
			}
		}

		dp[i][0] = dp[i - 1][0];
		FOR_LE(j, 1, k) {
			dp[i][j] += dp[i - 1][j - 1] * 9 + dp[i - 1][j];
		}
	}

	cout << dp[s.size() - 1][k] << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod %
using namespace std;
using ll = long long;

int main(){
    string a,b; cin >> a >> b;

    if(a == b){
        cout << "EQUAL" << endl;
        return 0;
    }
    if(a.size() > b.size()){
        cout << "GREATER" << endl;
        return 0;
    }else if(a.size() < b.size()){
        cout << "LESS" << endl;
        return 0;
    }

    for(int i = 0; i < a.size(); i++){
        if(a[i] > b[i]){
            cout << "GREATER" << endl;
            return 0;
        }else if(a[i] < b[i]){
            cout << "LESS" << endl;
            return 0;
        }
    }

    cout << "EQUAL" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first setprecision

#if MYDEBUG
#include "lib/cp_debug.h"
#else
#define DBG(...) ;
#endif

using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL  MOD=1E9+7;

struct Problem{
    LL x,k,q;
    vector<LL> r,t,a;
    vector<vector<LL>> s;
    void solve(){
        cin >> x >> k;
        r.push_back(0);
        for(int i=0; i<k; ++i){
            int tmp;
            cin>> tmp;
            r.push_back(tmp);
        }
        cin >> q;
        for(int i=0; i<q; ++i){
            int tt,mm;
            cin>> tt >> mm;
            t.push_back(tt);
            a.push_back(mm);
        }
        s= vector<vector<LL>> (k+1,vector<LL>(4));
        s[0]={0,0,x,x};
        for(int i=1; i<=k; ++i){ //s[i]
            LL dr= r[i]-r[i-1];
            DBG(dr)
            if(i%2!=0){ //decreasing
                s[i]={max(s[i-1][0]-dr,0ll),max(s[i-1][1],dr-(s[i-1][0]-s[i-1][1])),
                    s[i-1][2],max(s[i-1][3]-dr,0ll)};
            }else{ //increasing
                s[i]={min(s[i-1][0]+dr,x),s[i-1][1],
                    min(s[i-1][2],x-dr-(s[i-1][3]-s[i-1][2])),min(s[i-1][3]+dr,x)};
            }
            if(s[i][2]<=s[i][1]){
                assert(s[i][0]==s[i][3]);
                s[i][2]=0;
                s[i][1]=x;
            }
        }
        DBG(s)
        for(int i=0; i<q; ++i){
            LL it = upper_bound(r.begin(),r.end(),t[i])-r.begin();
            it--;
            DBG(i,it)
            LL prev;
            if(a[i]<=s[it][1]) prev = s[it][0];
            else if(a[i]>=s[it][2])prev = s[it][3];
            else prev = s[it][0] + (a[i]-s[it][1]);
            DBG(prev)
            if(it%2==0){ //dec
                cout << max(0ll, prev-(t[i]-r[it])) <<"\n";
            }else{ //inc
                cout << min(x,prev+(t[i]-r[it]))<<"\n";
            }
        }
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    Problem p;
    p.solve();
    return 0;
}



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

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

 int sequence[n];
 int count=0;
 while( count<n ){
  cin >> sequence[count];
  count++;
 }

 for( int j=n-1; j>=0; j-- ){
  if( j!=0 ){
   cout << sequence[j] << " ";
  }else{
   cout << sequence[j];
  }
 }

 cout << endl;
}


Measured memory_bytes: 3100