akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#include <vector>
#include <numeric>
#include <map>
#include <cmath>
#include <iomanip>
#include <queue>
using ll =long long;
#define PI 3.14159265358979
using P = pair<ll , ll>;
//using map = map<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;

int main(){
    vl x(5);
    rep(i,5) cin >> x.at(i);

    ll ans = 0;

    rep(i,5){
        if(x.at(i) == 0) ans = i+1;
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 3624
def main():
    L = int(input())
    r = 0
    while 2 ** (r+1) <= L:
        r += 1
    assert r < 20
    N = r + 1
    edges = list()
    for i in range(1, N):
        edges.append((i, i + 1, 0))
        edges.append((i, i + 1, 2**(i - 1)))
    for t in range(N - 1, 0, -1):
        if L - 2**(t - 1) >= 2**r:
            edges.append((t, N, L - 2**(t - 1)))
            L -= 2**(t - 1)
    print('{} {}'.format(N, len(edges)))
    for e in edges:
        print(' '.join(map(str, e)))


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl

int main() {
    int n; cin >> n;
    vector<int> a(n+2);
    a.at(0) = 0;
    rep(i, n) cin >> a.at(i+1);
    a.push_back(0);

    ll sum = 0;
    vector<int> b;
    rep(i, n+1){
        b.push_back(a.at(i+1)-a.at(i));
        sum += abs(a.at(i)-a.at(i+1));
    }

    rep(i, n){
        cout << sum - abs(b.at(i)) - abs(b.at(i+1)) + abs(b.at(i+1)+b.at(i)) << endl;
    }


}

Measured memory_bytes: 2552
#include <bits/stdc++.h>
using namespace std;
int main()
{
   vector<string>s;
   int n,l;
   cin>>n>>l;
   for(int i=0; i<n; i++){
       string c;
       cin>>c;
       s.push_back(c);
   }
   sort(s.begin(), s.end());
   for(int i=0; i<n; i++){
     cout<<s[i];
   }
   cout<<endl;
   return 0;
}


Measured memory_bytes: 256
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
using namespace std;

int main() {
    string s, t, c;
    int a, b;
    cin >> s >> t;
    cin >> a >> b >> c;
    if (s == c) {
        a--;
    } else if (t == c) {
        b--;
    }
    cout << a << " " << b << endl;
    return 0;
}

Measured memory_bytes: 256
//### In The Name Of GOD ###

//%% Remember; (((He))) is The (((Accepter))) %%

// GOD IS GREATER ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef long double ld ;

#define int ll
#define pb push_back
#define bp pop_back
#define pf push_front
#define fp pop_front
#define X first
#define Y second
#define sz(a) (int)(a.size())
#define sg(a, b) (a + b - 1) / b

const int MOD = 1000 * 1000 * 1000 + 7;
const ll INF = 1000 * 1000 * 1000 + 100;
const int MAXN = 200000 + 4;
const int MLOG = 22;
const int NMAX = 500 + 100; // ios_base :: sync_with_stdio(false);

int a[MAXN], pmark[MAXN], mark[MAXN];
vector <pair <int, int>> comp[MAXN];
vector <int> adj[MAXN];

void dfs(int v, int p, int cnt) {
	comp[cnt].pb({a[v], v});
	mark[v] = true;
	for(int i : adj[v]) 
		if(i != p)
			dfs(i, v, cnt);
}

signed main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	if(m == n - 1) {
		cout << 0;
		return 0;
	}
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(!mark[i])
			dfs(i, -1, cnt++);
	}
	int ans = 0;
	for(int i = 0; i < cnt; i++) {
		auto x = *min_element(comp[i].begin(), comp[i].end());
		pmark[x.Y] = true;
		ans += x.X;
	}
	vector <int> all;
	for(int i = 0; i < n; i++) {
		if(!pmark[i]) {
			all.pb(a[i]);
		}
	}
	if(sz(all) < cnt - 2) {
		cout << "Impossible";
		return 0;	
	}
	sort(all.begin(), all.end());
	for(int i = 0; i < cnt - 2; i++) {
		ans += all[i];
	}
	cout << ans;;
}

Measured memory_bytes: 20340
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()

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

    vector <bool> item(n,true);
    rep(i,k){
        int d;
        cin >> d;
        rep(j,d){
            int a;
            cin >> a;
            item[a-1] = false;
        }
    }

    int ans;
    for(auto x:item){
        if(x){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t n,a,b;
  cin >> n >> a >> b;
  if((b-a)%2==0)cout << (b-a)/2 << endl;
  else if((b-a)%2!=0){
    int64_t mind;
    mind=min(a-1,n-b);
    int64_t dis=(b-a-1)/2;
    cout << mind+dis+1 << endl;
  }
}


Measured memory_bytes: 3604
N, M = map(int, input().split())
Edge = [tuple(map(int, input().split())) for _ in range(M)]

import numpy as np
Graph = np.array([[0 if i == j else np.inf for i in range(N)] for j in range(N)])
for a,b,c in Edge:
    Graph[a-1,b-1] = c
from scipy.sparse.csgraph import dijkstra 
Graph = dijkstra(Graph,directed=False)
ans = 0
for a,b,c in Edge:
    if Graph[a-1,b-1] != c:
        ans += 1
print(ans)

Measured memory_bytes: 38836
#include<iostream>
using namespace std;
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b){
        cout << c << endl;
    }else if(b == c){
        cout << a << endl;
    }else if(a == c){
        cout << b << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int N;
    scanf("%d",&N);
    int a,b;
    a=N/10;
    b=N%10;
    if(a==9|b==9)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
list1 = []
cnt = 0
bit = 9
switch = 0
for i in range(5):
  list1.append(int(input()))
for i in range(5):
  amari = list1[i] % 10
  if amari == 0:
    cnt += 1
  else:
    switch = 1
    bit = min(bit,amari)
    list1[i] += 10-amari
if switch ==1:
  
  print(sum(list1)-10+bit)
else:
  print(sum(list1))

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

using std::sort;

const int N=2e5+10;

int R,C,n,top,que[N];

struct Node{
	int pos,id;
	Node(int x=0,int y=0,int id=0):id(id){
		if (y==0) pos=x;
		else if (x==R) pos=y+R;
		else if (y==C) pos=R+C+R-x;
		else pos=R+C+R+C-y;
	}
	bool operator < ( const Node &A ) const {
		return pos<A.pos;
	}
}p[N];

bool pd(int x,int y) { return (x==0 || x==R) || (y==0 || y==C); }

void Init() {
	int x1,y1,x2,y2;
	scanf("%d%d%d",&R,&C,&n); top=0;
	for (int i=1;i<=n;++i) {
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if (pd(x1,y1) && pd(x2,y2)) {
			p[++top]=Node(x1,y1,i);
			p[++top]=Node(x2,y2,i);
		}
	}
}

void Solve() {
	sort(p+1,p+top+1);
	int t=0;
	for (int i=1;i<=top;++i) {
		if (p[i].id==que[t]) --t;
		else que[++t]=p[i].id;
	}
	if (t) printf("NO\n");else printf("YES\n");
}

int main() {
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 2176
#include <stdio.h>
void swap (int *x, int *y) {
  int temp;
  temp = *x;
  *x = *y;
  *y = temp;
}
int partition (int array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;
  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);
  swap(&array[pivot], &array[j]);
  return j;
}
void quick_sort (int array[], int left, int right) {
  int pivot;
  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort(array, left, pivot-1);
    quick_sort(array, pivot+1, right);
  }
}
int main(void){
    int n, a[300000];
    int i,j;
    int flg = 0;
    scanf("%d", &n);
    for(i = 0;i < n;i ++){
        scanf("%d", &a[i]);
    }
    quick_sort(a, 0, n - 1);
    for(i = 0;i < n;i ++){
        if(a[i] == a[i + 1]){
            flg = 1;
            break;
        }
    }
    if(flg == 0){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int main (){
	int cont=1;
	bool band = false;
	string s;
	int pos;
	cin >> s;
	for (int i=1;i<4; i++){
		if (s[i] == s[0]) cont++;
		else if (!band){
			pos = i; band = true;
		}
	}
	if (cont == 2){
		for(int j=pos+1; j<4; j++){
			if (s[pos] == s[j]){
				cout << "Yes";
				return 0;
			}
		}
		cout << "No";
	}
	else{
		cout << "No";
	}
	
	return 0;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n; cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    cout << a[n-1] - a[0] << endl;
}

Measured memory_bytes: 256
N = int(input())
X = list(map(int, input().split()))

Xs = sorted(X)
med_d = Xs[N // 2 - 1]
med_u = Xs[N // 2]

for i in range(N):
    if X[i] <= med_d:
        print(med_u)
    elif X[i] >= med_u:
        print(med_d)


Measured memory_bytes: 26772
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <time.h>
#include <random>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define LONG_INF 10000000000000000
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
int main() {
	int a, b;
	cin >> a >> b;
	int ans = a + b;
	if (ans >= 24) {
		ans = ans - 24;
	}
	cout << ans << endl;
}

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

int main(){
  srand((unsigned int)time(NULL)); 
  int D,M=365*500;
  int c[30];
  int s[370][30];
  int t[370];
  int last[30];
  int ans_max=0,ans=0;
  int old_t,old_d;
  
  scanf("%d",&D);
  for(int i=1;i<=26;i++)
    scanf("%d",c+i);
  for(int i=1;i<=D;i++)
   for(int j=1;j<=26;j++)
     scanf("%d",&s[i][j]);
  
  for(int i=1;i<=D;i++)
    t[i]=rand()%26+1;
  
  ans_max=0;
  for(int k=1;k<=26;k++)
    last[k]=0;
  for(int d=1;d<=D;d++){
    ans_max+=s[d][t[d]];
    last[t[d]]=d;
    for(int j=1;j<=26;j++){
      ans_max-=c[j]*(d-last[j]);
    }
  }
  
  for(int i=1;i<=M;i++){
    ans=0;
    old_d=i%D+1;
    old_t=t[old_d];
    t[old_d]=rand()%26+1;
    for(int k=1;k<=26;k++)
      last[k]=0;
    for(int d=1;d<=D;d++){
      ans+=s[d][t[d]];
      last[t[d]]=d;
      for(int j=1;j<=26;j++){
        ans-=c[j]*(d-last[j]);
      }
    }
    if(ans<ans_max){
      t[old_d]=old_t;
    }else{
      ans_max=ans;
    }
  }
  
  for(int i=1;i<=D;i++)
    printf("%d\n",t[i]);
  return 0;
}

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

using namespace std;
using ll = long long int;

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

    ll n;
    cin >> n;
    vector<ll> a(n);
    for(auto &e: a) cin >> e;
    vector<vector<ll>> dp(n, vector<ll>(50, -1e18));
    dp[0][1 + 25] = a[0];
    dp[0][-1 + 25] = 0;
    dp[1][0 + 25] = a[1];
    dp[1][-2 + 25] = 0;
    for(ll i=1; i<n; i++) {
        for(ll j=-3; j<=3; j++) {
            if(i-2>=0) dp[i][j + 25] = max(dp[i][j+1 + 25], dp[i-2][j + 25] + a[i]);
            dp[i][j-1 + 25] = max(dp[i][j-1 + 25], dp[i-1][j + 25]);
        }
    }
    cout << dp[n-1][n/2 - (n+1)/2 + 25] << endl;

}


Measured memory_bytes: 90848
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, k = tin()
	#s = input()
	al = lin()
	cc = collections.Counter(al)
	cv = [cc[k] for k in cc]
	cv.sort()
	#print(cv)
	print(sum(cv[:-k]))
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 35236
def main():
    MOD=2019
    S=input()[::-1]
    count=[1]+[0]*MOD
    r,tmp=0,1
    for i in S:
        r += int(i)*tmp
        r %= MOD
        tmp *= 10
        tmp %= MOD
        count[r] += 1

    print(sum([i*(i-1)//2 for i in count]))

main()


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

int main() {
  int n; cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) cin >> a[i];
  int sub = 1;
  for(int i = 0; i < n; i++) {
    if(a[i] % 2 == 0) sub *= 2;
  }
  cout << pow(3, n) - sub << endl;
}


Measured memory_bytes: 4160
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int INF = numeric_limits<int>::max() / 2;
ll LINF = numeric_limits<ll>::max() / 2;
int MOD = 1e9 + 7;

int main()
{
    long double n,k;
    cin >> n >> k;
    long double ans = 0;
    long double ma = 1;
    int te = 1;
    while(te < k){
        te *= 2;
        ma *= 2;
    }
    for(int i = 1; i <= n; i++){
        int p = i;
        long double t = 1;
        while(p < k){
            p *= 2;
            t *= 2;
        }
        ans += ma / t;
    }
    cout << setprecision(12) << ans / n / ma << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    d = defaultdict(int)
    for _ in range(M):
        s, c = map(int, input().split())
        if d[s]:
            if d[s] != c:
                print(-1)
                exit()
        d[s] = c

    ans = [-1] * N
    for i, j in d.items():
        ans[i-1] = j

    if N != 1 and ans[0] == 0:
        print(-1)
        exit()
    
    if N == 1 and (ans[0] == -1 or ans[0] == 0):
        print(0)
        exit()
    str_ans = ''
    for i in range(N):
        if ans[i] == -1:
            if i == 0:
                str_ans += '1'
            else:
                str_ans += '0'
        else:
            str_ans += str(ans[i])



    print(str_ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 38384
#include <bits/stdc++.h>
 
using namespace std;
 
template< class t>
long long int gcd( t g,t h )
{
    return ( h==0 ? g : gcd(h,g%h) );
}
 

struct Comp {
  bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    if (a.first != b.first) {
      return a.first < b.first;
    }
    return a.second > b.second;
  }

}comp_functor;
 
int main() 
{
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    
    long long int i,j,ans=1,n,a[300005],c=0,b[300005],h[3000005]={0},temp,x,y;
    
    string s;
    
    cin>>s;
    
    n=s.length();
    
    for(i=0;i<n-8;i++)
    {
        cout<<s[i];
    }
    
    return 0;
}
 

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
      
        System.out.println(N * (N - 1) / 2 + M * (M - 1) / 2);
    }
}

Measured memory_bytes: 21844
#include<stdio.h>
int main()
{
  int i,j,n,p;
  int end;
  int remain;
  int num[50];
  while(1)
    {
      scanf("%d%d",&n,&p);
      if((n==0)&&(p==0)) break;
      for(i=0;i<n;i++) num[i]=0;
      i=0;
      remain=p;
      end=0;
      while(1)
	{
	  if(remain>0)
	    {
	      num[i]++;
	      remain--;
	    }
	  else
	    {
	      remain+=num[i];
	      num[i]=0;
	    }
	  for(j=0;j<n;j++)
	    {
	      if(num[j]==p)
		{
		  end=1;
		  break;
		}
	      else if((num[j]>0)&&(num[j]<p)) break;
	    }
	  if(end) break;
	  i++;
	  if(i==n) i=0;
	}
      printf("%d\n",j);
    }
  return 0;
}

Measured memory_bytes: 600
package main

import (
	"fmt"
	"strings"
)

func main() {
	var n, k int
	var s string
	fmt.Scan(&n, &k, &s)

	var result string
	for i := 1; i <= n; i++ {
		if i == k {
			str := s[i-1:i]
			result += strings.ToLower(str)
		} else {
			result += s[i-1:i]
		}
	}

	fmt.Println(result)
}


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

using namespace std;

int N, K;
int A[100010];

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

int main()
{
    cin >> N >> K;
    for (int i = 0; i < N; ++i) cin >> A[i];
    int GCD = 0, mx = 0;
    for (int i = 0; i < N; ++i) {
        GCD = gcd(GCD, A[i]);
        mx = max(mx, A[i]);
    }

    if (mx < K) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    if (K % GCD == 0) {
        cout << "POSSIBLE\n";
    } else {
        cout << "IMPOSSIBLE\n";
    }
}


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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	string w;
	cin >>w;
	vector<int> c(26, 0);
	for (int i=0; i<w.size(); i++)
		c.at(w.at(i)-'a')++;
	for (int i=0; i<26; i++)
		if (1==c.at(i)%2) {
			cout <<"No" <<endl;
			return 0;
		}
	cout <<"Yes" <<endl;
	return 0;
}



Measured memory_bytes: 256
import numpy as np
N,M,C = map(int,input().split(' '))
B = np.array(list(map(int,input().split(' '))))
As = [list(map(int,input().split(' '))) for i in [0]*N]

ans = 0
for A in As:
	if np.sum(A*B) + C > 0:
		ans += 1
print(ans)


Measured memory_bytes: 21544
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

#define REP(i,n) for(i=0;i<n;i++)
#define REVREP(i,n) for(i=n-1;i>=0;i--)

int iin() {
    int i;
    scanf("%d", &i);
    return i;
}

long long llin() {
    long long i;
    scanf("%lld", &i);
    return i; 
}

double din() {
    double i;
    scanf("%lf", &i);
    return i;
}

char cin() {
    char c;
    scanf("%c", &c);
    return c;
}

void stin(char *s) {
    scanf("%s", s);
}

void iout(int i) {
    printf("%d\n", i);
}

void llout(long long i) {
    printf("%lld\n", i);
}

void dout(double i) {
    printf("%lf\n", i);
}

void cout(char c) {
    printf("%c\n", c);
}

void stout(char *s) {
    printf("%s\n", s);
}

void check(char *S, int *C) {
    int i, j;
    REVREP(i,strlen(S)) {
        j = i + 1;
        if (j > strlen(S)) continue;
//        cout(S[i]);
        if (S[i] != 'A') {
            C[i] += C[j];
        } else {
            if (S[j] != 'C') {
                C[i] += C[j];
            } else {
                C[i] += (C[j] + 1);
            }
        }
    }
}

int main() {
    int N = iin(), Q = iin();
    char S[N];
    int C[N];
    int i;
    stin(S);
    memset(C, 0, sizeof C);
//    stout(S);
    check(S, C);
//    REP(i,N) { iout(C[i]); }
    REP(i,Q) {
        int l = iin(), r = iin();
        iout(C[l - 1] - C[r - 1]);
    }
    return 0;
}

Measured memory_bytes: 1280
N, Y = map(int, input().split())

f = False
for i in range(N+1):
  if f: break
  for j in range(N+1):
    if N - i - j < 0: break
    if i * 10000 + j * 5000 + (N - i -j) *1000 == Y:
      print (i,j,N-i-j)
      f = True
      break
if not f: print (-1, -1, -1)

Measured memory_bytes: 3060
N = int(input())
X = [list(map(int,input().split())) for i in range(N)]
for i in range(1,N):
    X[i][0]+=max(X[i-1][1],X[i-1][2])
    X[i][1]+=max(X[i-1][0],X[i-1][2])
    X[i][2]+=max(X[i-1][0],X[i-1][1])
print(max(X[N-1]))

Measured memory_bytes: 30580
#include <stdio.h>

int main()
{
    int s;
    int w;

    do{
        scanf("%d", &s);

    }while(s<0 || s>100);

    do{
        scanf("%d", &w);

    }while(w<0 || w>100);

    if(w>=s){
        printf("%s\n", "unsafe");
    } else {
    printf("%s\n", "safe");
    }

    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

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

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

typedef vector<ll> Edges;
typedef vector<Edges> Graph;

// トポロジカルソートで最長パスの長さを求めるやつ
// 返り値はトポロジカルソート不可能な場合（ループがある場合）-1
// それ以外は最長パスの長さ
// 配列tsには「頂点iを終点とする最長のパスの長さ」が入る

const ll V_MAX = 101010; // !! SHOULD BE EDITTED !!
vector<ll> ts(V_MAX, -1);

int topologicalSortLength(Graph &G){
	ll V = G.size();
	vector<ll> indeg(V, 0);
	queue<ll> qu;

	REP(i, V){
		REP(j, G[i].size()){
			indeg[G[i][j]]++;
		}
	}
	REP(i, V){
		if(!indeg[i]) qu.push(i);
	}

	ll depth = 0;
	while(!qu.empty()){
		ll s = qu.size();
		REP(i, s){
			ll now = qu.front();qu.pop();
			ts[now] = depth;
			REP(j, G[now].size()){
				ll next = G[now][j];
				indeg[next]--;
				if(!indeg[next]) qu.push(next);
			}
		}
		depth++;
	}

	REP(i, V){
		if(ts[i] == -1) return -1;
	}
	return depth;
}

// 普通のトポロジカルソート
// 返り値はトポロジカルソート不可能な場合（ループがある場合）false，それ以外 true
// tsには順番が入ります
// V_MAX と tsを上からコピーしてくるのを忘れない
bool topologicalSort(Graph &G){
	ll V = G.size();
	vector<ll> indeg(V, 0);
	queue<ll> qu;

	REP(i, V){
		REP(j, G[i].size()){
			indeg[G[i][j]]++;
		}
	}
	REP(i, V){
		if(!indeg[i]) qu.push(i);
	}

	ll idx = 0;
	while(!qu.empty()){
		ll s = qu.size();
		REP(i, s){
			ll now = qu.front();qu.pop();
			ts[now] = idx;
			idx++;
			REP(j, G[now].size()){
				ll next = G[now][j];
				indeg[next]--;
				if(!indeg[next]) qu.push(next);
			}
		}
	}

	return (idx == V);
}



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

    ll V, E;
    cin >> V >> E;
    Graph G(V);
    REP(i, E){
    	ll s, t;
    	cin >> s >> t;
    	G[s].push_back(t);
    }

    topologicalSort(G);
    vector<pll> P(V);
    REP(i, V) P[i].first = ts[i], P[i].second = i;
    sort(P.begin(), P.end());

    REP(i, V){
    	cout << P[i].second << endl;
    }
    return 0;
}


Measured memory_bytes: 4820
#include<vector>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a;
  for(int i=1;i<50;++i){
    for(int j=2;j<50;++j){
      a.push_back(pow(i,j));
    }
  }
  sort(a.begin(),a.end());
  for(int i=0;i<a.size();++i){
    if(a[i]>n){
      cout<<a[i-1]<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 4160
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))

data=[[0 for i in range(0,M)] for j in range(0,N)]
for i in range(0,N):
    if S[i]==T[0]:
        data[i][0]=1

dp=[[1 for i in range(0,M)] for j in range(0,N)]
for j in range(0,M):
    if j==0:
        if S[0]==T[0]:
            dp[0][0]=2
    else:
        if S[0]==T[j]:
            dp[0][j]=(dp[0][j-1]+1)%(10**9+7)
        else:
            dp[0][j]=dp[0][j-1]%(10**9+7)

for i in range(0,N):
    for j in range(0,M):
        if j!=0:
            if S[i]==T[j]:
                data[i][j]=(data[i][j-1]+dp[i-1][j-1])%(10**9+7)
            else:
                data[i][j]=data[i][j-1]
        if i!=0:
            dp[i][j]=(dp[i-1][j]+data[i][j])%(10**9+7)

print(dp[N-1][M-1]%(10**9+7))

Measured memory_bytes: 108380
def main():
    MOD = 10 ** 9 + 7

    N = int(input())
    *a, = map(int, input().split())

    b = [0] * 60
    for x in a:
        for j in range(60):
            b[j] += (x & 1) > 0
            x >>= 1

    t = 1
    ans = 0
    for j in range(60):
        ans = (ans + b[j] * (N - b[j]) * t) % MOD
        t <<= 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 122808
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long u64;

u64 binpow(u64 n, u64 x, u64 mod)
{
  u64 tgt = 1;
  u64 dig = n;
  while (x > 0) {
    if (x%2) {
      tgt = (tgt * dig) % mod;
    }
    dig = (dig * dig) % mod;
    x /= 2;
  }
  return tgt;
}

class Comb
{
public:
  u64 mod;
  vector< u64 > fact;
  vector< u64 > factf;
  void init(u64 size, u64 imod) {
    mod = imod;
    fact.resize(size+1);
    factf.resize(size+1);
    fact[0] = 1;
    factf[0] = 1;
    for (u64 i = 1; i <= size; ++i) {
      fact[i] = fact[i-1]*i%mod;
      factf[i] = binpow(fact[i], mod-2, mod);
    }
  }
  u64 comb(u64 n, u64 k) {
    if (n<k) return 0;
    if (k==0 || n==k) return 1;
    return ((fact[n] * factf[k]) % mod * factf[n-k]) % mod;
  }
};

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  Comb comb;
  comb.init(50, 1e9+7);
  int n, p;
  cin >> n >> p;
  int isodd = 0;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    if (a%2==1) isodd++;
  }
  u64 ret_odd = 0;
  for (int i = p; i <= isodd; i+=2) {
    ret_odd += comb.comb(isodd, i);
  }
  for (int i = 0; i < n-isodd; ++i) {
    ret_odd *= 2;
  }
  cout << ret_odd << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

int N, M, S, T;
int dyen[100100], dsnu[100100];
vector<pii> Gyen[100100];
vector<pii> Gsnu[100100];
int ans[100100];


signed main() {
    cin >> N >> M >> S >> T;
    --S;
    --T;
    rep(i, M) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        --u;
        --v;
        Gyen[u].push_back(pii(a, v));
        Gyen[v].push_back(pii(a, u));
        Gsnu[u].push_back(pii(b, v));
        Gsnu[v].push_back(pii(b, u));
    }
    rep(i, 100100)dyen[i] = dsnu[i] = INF;
    dyen[S] = 0;
    dsnu[T] = 0;
    {
        priority_queue<pii, vector<pii>, greater<pii>> que;
        que.push(pii(0, S));
        while (!que.empty()) {
            pii p = que.top();
            que.pop();
            int v = p.second;
            if (dyen[v] < p.first)continue;
            rep(i, Gyen[v].size()) {
                pii e = Gyen[v][i];
                if (e.first + dyen[v] < dyen[e.second]) {
                    dyen[e.second] = e.first + dyen[v];
                    que.push(pii(dyen[e.second], e.second));
                }
            }
        }
    }
    {
        priority_queue<pii, vector<pii>, greater<pii>> que;
        que.push(pii(0, T));
        while (!que.empty()) {
            pii p = que.top();
            que.pop();
            int v = p.second;
            if (dsnu[v] < p.first)continue;
            rep(i, Gsnu[v].size()) {
                pii e = Gsnu[v][i];
                if (e.first + dsnu[v] < dsnu[e.second]) {
                    dsnu[e.second] = e.first + dsnu[v];
                    que.push(pii(dsnu[e.second], e.second));
                }
            }
        }
    }

    int prev = -INF;
    for (int i = N - 1; i >= 0; --i) {
        ans[i] = max(prev, 1000000000000000 - dyen[i] - dsnu[i]);
        prev = ans[i];
    }
    rep(i, N) {
        cout << ans[i] << endl;
    }
    return 0;
}
//D


Measured memory_bytes: 19140
import java.util.Scanner;

public class Main {
    void run(String[] args){
        Scanner scan=new Scanner(System.in);
        String line=scan.nextLine();
        String print;
        String[] lines=line.split("");
        if(lines[lines.length-1].equals("s")){
            print=line+"es";
        }
        else{
            print=line+"s";
        }
        System.out.println(print);
    }
    public static void main(String args[]){
        Main printer = new Main();
        printer.run(args);
    }
}

Measured memory_bytes: 38736
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //
void solve(){
	int n = read.to!int;
	int a = read.to!int;
	int b = read.to!int;
	
	int ans = min(n * a, b); 
	ans.writeln;
	
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>


using namespace std;
using vll = vector<long long>;
using vvll = vector<vll>;
using vii = vector<pair<int, int>>;
constexpr long long mod = 1'000'000'007;

void process(int a, int b, int amin, int amax, int bmin, int bmax, long long x, vvll &ndp, vii &fs){
    if (amin <= a and a <= amax and bmin <= b and b <= bmax){
        if (ndp[a][b] == 0) fs.push_back(make_pair(a, b));
        ndp[a][b] += x;
        ndp[a][b] %= mod;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> Bmax(N + 1, N);
    vector<int> Bmin(N + 1, 0);
    vector<int> Amax(N + 1, N);
    vector<int> Amin(N + 1, 0);
    while (M--){
        int L, R, x;
        cin >> L >> R >> x;
        if (x == 1){
            Bmax[R] = min(Bmax[R], L - 1);
        }else if (x == 2){
            Bmin[R] = max(Bmin[R], L);
            Amax[R] = min(Amax[R], L - 1);
        }else{
            Amin[R] = max(Amin[R], L);
        }
    }
    vvll dp(N + 1, vll(N + 1, 0));
    vvll new_dp(N + 1, vll(N + 1, 0));
    dp[0][0] = 1;
    vii frontiers;
    vii new_frontiers;
    frontiers.push_back(make_pair(0, 0));
    for (int k = 0; k != N; ++k){
        new_frontiers.clear();
        int amin = Amin[k + 1];
        int amax = Amax[k + 1];
        int bmin = Bmin[k + 1];
        int bmax = Bmax[k + 1];
        for (const auto & p: frontiers){
            int a = p.first;
            int b = p.second;
            process(a, b, amin, amax, bmin, bmax, dp[a][b], new_dp, new_frontiers);
            process(a, k, amin, amax, bmin, bmax, dp[a][b], new_dp, new_frontiers);
            process(b, k, amin, amax, bmin, bmax, dp[a][b], new_dp, new_frontiers);
            dp[a][b] = 0;
        }
        swap(frontiers, new_frontiers);
        swap(dp, new_dp);
    }
    long long ret = 0;
    for (auto &p : frontiers) ret += dp[p.first][p.second];
    cout << ret % mod << endl;
    return 0;
}

Measured memory_bytes: 2628
#include<iostream>
using namespace std;
#define MAX 2000000

int H,A[MAX+1];

 void maxHeapify(int i){
    int l,r,largest;
    l  = 2*i;
    r = 2*i +1;

    if (l <=H && A[l] > A[i]) largest = l;
    else largest = i;
    if ( r<= H && A[r] > A[largest]) largest = r;

    if (largest != i){
        swap(A[i],A[largest]);
        maxHeapify(largest);
    }
}


int main(){
    cin >> H;
    for (int i = 1;i<=H;i++) cin >>A[i];
    for (int i = H/2; i >=1; i--) maxHeapify(i);

    for (int i = 1 ;i <=H ;i++) cout << " " << A[i];
    cout << endl;

    return 0;
    
}



Measured memory_bytes: 4952
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<double> x(N), y(N);
    for(int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }
    vector<vector<double>> d(N, vector<double>(N));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            d[i][j] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
        }
    }
    vector<int> S(N);
    for(int i = 0; i < N; i++) {
        S[i] = i;
    }
    vector<double> ans;
    do {
        double l = 0;
        for(int i = 0; i < N - 1; i++) {
            l += d[S[i]][S[i + 1]];
        }
        ans.push_back(l);
    } while(next_permutation(S.begin(), S.end()));
    double a = 0;
    for(int i = 0; i < ans.size(); i++) {
        a += ans[i];
    }
    cout << fixed << setprecision(10) << a / (double)ans.size() << endl;
    return 0;
}

Measured memory_bytes: 4000
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for (int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for (int (i) = (a) - 1; (i) >= (b); (i)--)
#define PI acos(-1.0)
#define DEBUG(C) cout<< C <<endl;
#define VI vector <int>
#define VII vector <VI>
#define VL vector <LL>
#define VLL vector <VL>
#define VD vector <double>
#define VDD vector <VD>
#define PII pair <int, int>
#define PDD pair <double, double>
#define PLL pair <LL, LL>
#define VPII vector <PII>
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define EB emplace_back
#define FORE(a, b) for (auto &&a:b)
#define FIND(s, n) (s.find(n) != s.end())

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9;
const int MOD = INF + 7;

int N, A, B;
string S;

int main(void) {
    cin >> N >> A >> B >> S;
    int a = 0, b = 0;
    int yosen = 0;
    REP(i, N) {
        if (S[i] == 'a') {
            a++;
            if (yosen < A + B) {
                printf("Yes\n");yosen++;
            } else {
                printf("No\n");a--;
            }
        } else if (S[i] == 'b') {
            b++;
            if (yosen < A + B && b <= B) {
                printf("Yes\n");yosen++;
            } else {
                printf("No\n");b--;
            }
        } else {
            printf("No\n");
        }
    }
}


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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, A[int(2e5+5)], now[int(2e5+5)];
vector <int> ans;

int main(){
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> A[i];

  for (int i = N; i >= 1; i--){
    if (now[i] % 2 == A[i]) continue;
    ans.push_back(i);
    for (int j = 1; j * j <= i; j++){
      if (i % j != 0) continue;
      now[j]++;
      if (j * j != i) now[i/j]++;
    }
  }

  int M = ans.size();
  cout << M << endl;
  for (int i = 0; i < M; i++){
    cout << ans[i];
    if (i == M - 1) cout << endl;
    else cout << " ";
  }
  return 0;
}


Measured memory_bytes: 5244
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string s = Console.ReadLine();
    int n = s.Length;
    int[] mewCount = new int[2];
    bool answer = true;

    for(int i = 0; i < n; i++)
    {
      if(s[i] == 'm')
      {
        mewCount[0]++;
      }
      else if(s[i] == 'e')
      {
        mewCount[1]++;
        if(mewCount[0] < mewCount[1])
        {
          answer = false;
          break;
        }
      }else
      {
        if(mewCount[0] == 0 || mewCount[1] == 0)
        {
          answer = false;
          break;
        }else if(mewCount[0] == 1 && i != n-1)
        {
          answer = false;
          break;
        }else
        {
          mewCount[0]--;
          mewCount[1]--;
        }
      }
      
      if(i == n-1)
      {
        if(mewCount[0] + mewCount[1] > 0) answer = false;
      }
    }

		Console.WriteLine(answer?"Cat":"Rabbit");
	}
}


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

int main(){
  int n,m,Q;
  cin >> n >> m >> Q;
  vector<int>l(m),r(m);
  for(int i=0; i<m; i++){
    cin >> l[i] >> r[i];
  }
  vector<int>p(Q),q(Q);
  for(int i=0; i<Q; i++){
    cin >> p[i] >> q[i];
  }
  
  vector<vector<int>>sum(n+1,vector<int>(n+1,0));
  for(int i=0; i<m; i++) sum[l[i]][r[i]]++;
  
  for(int i=1; i<=n; i++){
   for(int j=1; j<=n; j++){
     sum[i][j] += sum[i-1][j];
     sum[i][j] += sum[i][j-1];
     sum[i][j] -= sum[i-1][j-1];
   }
  }
  
  for(int i=0; i<Q; i++){ 
    int ans = sum[q[i]][q[i]]-sum[q[i]][p[i]-1]-sum[p[i]-1][q[i]]+sum[p[i]-1][p[i]-1];
    cout << ans << endl;
  }
  
  
}

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


void bfs(std::vector<std::vector<int>>& node, std::vector<int>& dist, int s) {
	std::queue<int> que;
	dist[s] = 0;
	que.push(s);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (auto p : node[v]) {
			if (dist[p] == -1) {
				dist[p] = dist[v] + 1;
				que.push(p);
			}
		}
	}
}

int main() {
	int N;
	std::cin >> N;
	std::vector<std::vector<int>> node(N + 1, std::vector<int>());
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		std::cin >> a >> b;
		node[a].push_back(b);
		node[b].push_back(a);
	}

	// 1 -> 
	std::vector<int> dist1(N + 1, -1);
	bfs(node, dist1, 1);

	// N ->
	std::vector<int> dist2(N + 1, -1);
	bfs(node, dist2, N);

	int check = 0;
	for (int i = 1; i <= N; i++) {
		if (dist1[i] <= dist2[i]) check++;
	}

	std::cout << (2 * check > N ? "Fennec" : "Snuke") << std::endl;


	return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>
#include <string>

using namespace std;

#define INF 1000000000000000005

int main()
{
    long long n,k;
    long long a[200005];
    
    
    
    cin >> n >> k;
    for (long long i = 1;i <= n;i++){
        cin >> a[i];
    }
    
    if (k <= n){
        long long dp1[200005];
        dp1[0] = 1;
        for (long long i = 1;i <= k;i++){
            dp1[i] = a[dp1[i-1]];
        }
        cout << dp1[k] << endl;
    }
    
    else {
        long long end = 0;
        long long sta;
        long long cycle;
        long long res;
        bool check[200005] = {0};
        long long dp2[200005];
        dp2[0] = 1;
        check[1] = true;
        for (long long i = 1;i <= n;i++){
            dp2[i] = a[dp2[i-1]];
            if (check[dp2[i]] == true){
                end = i;
                break;
            }
            check[dp2[i]] = true;
        }
        
        for (int i = 0;;i++){
            if (dp2[i] == dp2[end]){
                sta = i;
                break;
            }
        }
        
        cycle = end-sta;
        if (cycle == 0){
            cout << dp2[sta] << endl;
        }
        else {
            res = (k-sta)%cycle;
            cout << dp2[sta+res] << endl;
        }
    }
}


Measured memory_bytes: 6552
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
 
int main() {
  int a,b;
  string s,t,u;
  
  cin >> s >> t >> a >> b >> u;
  
  if(s==u)cout << a-1 << " "<<  b << endl;
  else cout << a <<" "<< b-1 << endl;
}



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

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)

const ll MOD = 1000000007;

using namespace std;

int A[100005];
int main()
{
	int N;
	cin >> N;
	REP(i, N)
	{
		cin >> A[i];
	}

	int ans = 1;
	ll pp = 0;
	FOR(i, N - 1, 1)
	{
		ll p = (ll)(A[i] - A[i - 1]);
		ll n = (ll)(A[i + 1] - A[i]);
		if (p == 0)p = pp;
		else pp = p;
		if (p*n < 0)
		{
			ans++;
			i++;
			pp = 0;
		}
	}
	cout << ans << endl;
	return 0;
}

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

typedef long long ll;
 
using tpl = tuple<int, int, int>;
typedef pair<int,int> pii;

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}

int K;

ll digsum(ll a){
    ll sum = 0;
    while(a){
        sum += (a % 10);
        a /= 10;
    }
    return sum;
}

int main(){

    cin >> K;
    set<ll> cand;
    for(int i = 1; i <= 9; i++) {
        cand.insert(i);
    }
    for(int i = 1; i <= 9; i++){
        cand.insert(i * 10 + 9);
    }

    for(int i = 2; i <= 14; i++){
        ll base = 1;
        for(int j = 0; j < i; j++) base *= 10;
        ll suf = 0;
        for(int j = 0; j < i; j++) suf = suf * 10 + 9;
        for(int j = 1; j <= 500; j++){
            cand.insert(base * j + suf);
        }
    }

    vector<ll> cand2(cand.begin(), cand.end());
    sort(cand2.begin(), cand2.end());
    set<ll> ans;
    for(int i = 0; i < (int)cand2.size(); i++){
        ll a = cand2[i];
        bool ok = true;
        for(int j = i + 1; j < (int)cand2.size(); j++){
            ll b = cand2[j];
            if(a * digsum(b) > b * digsum(a)){
                ok = false;
            }
        }
        if(ok){
            ans.insert(a);
        }
    }

    auto it = ans.begin();
    for(int i = 0; i < K; i++){
        cout << *it << endl;
        it++;
    }

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  int n,k;cin>>n>>k;
  cout<<n-k+1<<endl;
}

Measured memory_bytes: 3620
N,M = gets.split.map(&:to_i)
C = Array.new(M,0)
N.times do |i|
    a = gets.split.map(&:to_i)
    a[1..-1].each do |j|
        C[j-1] += 1
    end
end
puts C.count{|c|c==N}

Measured memory_bytes: 1788
import sys
input = sys.stdin.readline
enum = enumerate

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def main():
	n,a,b=linput()
	
	res = (b-a-1)%2
	
	sT = "Borys Alice".split()
	print(sT[res])
	#print(res)

if __name__ == "__main__":
	main()


Measured memory_bytes: 61964
N = int(input())

# Nを 1以上 9以下の 2つの整数の積として表すことができるなら Yes を、できないなら No を出力せよ。

for i in range(1, 9+1):
    for j in range(1, 9+1):
        if i * j == N:
            print("Yes")
            exit()
else:
    print("No")

Measured memory_bytes: 9076
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template <typename T=int>
struct BIT {
    const int n;
    vector<T> v;

    BIT(int n): n(n), v(n+1,0) {}

    void add(int i, int x) {
        i += 1;
        while (i <= n) {
            v[i] += x;
            i += i & -i;
        }
    }
    T sum(int i) {
        i += 1;
        T ret = 0;
        while (i > 0) {
            ret += v[i];
            i -= i & -i;
        }
        return ret;
    }
    T sum(int l, int r) {
        return sum(r) - sum(l-1);
    }
};

void solve() {
    int n;
    cin >> n;
    VI a(n);
    REP(i,0,n) cin >> a[i];

    VP ps(n);
    REP(i,0,n) ps[i] = MP(a[i],i);
    ps.pb(0,-1);
    sort(all(ps));
    reverse(all(ps));

    VLL ans(n);

    int mini = n;
    REP(i,0,n) {
        int idx = ps[i].second;
        chmin(mini, idx);
        ans[mini] += (1LL + i) * (ps[i].first - ps[i+1].first);
    }

    REP(i,0,n) cout << ans[i] << endl;
}

signed main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 5316
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import decimal


if __name__ == "__main__":
    s = input()
    d = ""
    c = ""
    ans = 0
    for i in s:
        d += i
        if d != c:
            c = d
            d = ""
            ans+=1
    print(ans)

Measured memory_bytes: 5572
import java.util.*;

public class Main {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    // int N = Integer.parseInt(scanner.nextLine());
    // int N = scanner.nextInt(), M = scanner.nextInt();
    // scanner.nextLine();
    // int[] n = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    // long[] n = Arrays.stream(scanner.nextLine().split(" ")).mapToLong(Long::parseLong).toArray();
    static void solve(Scanner scanner) {
        int N = scanner.nextInt(), T = scanner.nextInt();
        scanner.nextLine();
        int[][] q = new int[N][2];
        for (int i = 0; i < N; i++) {
            q[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(q, Comparator.comparing(x -> x[0]));

        int[][] dp = new int[N + 1][T + 1];
        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < T + 1; j++) {
                if (j >= q[i - 1][0]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - q[i - 1][0]] + q[i - 1][1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, q[i - 1][1] + dp[i - 1][T - 1]);
        }


        System.out.println(ans);
    }

}


Measured memory_bytes: 86988