akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        DJSet ds = new DJSet(n);
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt()-1;
            int y = sc.nextInt()-1;
            int z = sc.nextInt();
            ds.union(x, y);
        }
        System.out.println(ds.countSet());
        sc.close();

    }

}

class DJSet {
    /**
     * 各要素の親を保持する配列。
     * 自信が根である要素は負の数を持つ。
     * （負の数の場合、絶対値がその集合の要素数）
     */
    public int[] upper;

    /**
     * コンストラクタ。
     * @param n 対象となる要素数
     */
    public DJSet(int n){
        upper = new int[n];
        Arrays.fill(upper, -1);
    }

    /**
     * 要素xが含まれる集合のrootを求める。
     * rootを求める過程で経路圧縮しrootが親になるようにする。
     * @param x 要素x
     * @return 要素xが含まれる集合のroot
     */
    public int root(int x){
        return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
    }

    /**
     * 要素xと要素yが同じ集合か判定する。
     * @param x 要素x
     * @param y 要素y
     * @return 要素xと要素yが同じ集合であればtrue、そうでなければfalseを返す。
     */
    public boolean same(int x, int y){
        return root(x) == root(y);
    }

    /**
     * 要素xと要素yを含むそれぞれの集合を合併する。
     * 要素数の多い集合のrootを残し、少ないほうのrootをその下に合併する。
     * @param x 要素x
     * @param y 要素y
     * @return 要素xと要素yを含むそれぞれの集合を合併できたらtrue、もともと同じ集合で合併しなかったらfalseを返す。
     */
    public boolean union(int x, int y){
        x = root(x);
        y = root(y);
        if(x != y){
            if(upper[y] < upper[x]){
                int t = x;
                x = y;
                y = t;
            }
            upper[x] += upper[y];
            upper[y] = x;
        }
        return x != y;
    }

    /**
     * 集合の数を数える。
     * @return 集合の数
     */
    public int countSet(){
        int c = 0;
        for(int u :upper){
            if(u < 0) c++;
        }
        return c;
    }

    /**
     * 要素ｘが含まれる集合の要素数を数える。
     * @param x 要素ｘ
     * @return 要素ｘが含まれる集合の要素数
     */
    public int countElement(int x){
        return upper[root(x)] * -1;
    }
}


Measured memory_bytes: 89576
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += gcd(a,b,c)
print(ans)

Measured memory_bytes: 69684
#include<stdio.h>
int main(void){
	int a,b,c,d,e,f;
	while(1){
		scanf("%d %d",&a,&b);
		c=a;
		d=b;
		
		if(a==0&b==0){
			goto hata;
		}
		else{
			for(e=1;e<=c;e++){
				for(f=1;f<=d;f++){
					if(e==1){
						putchar('#');
					}
					else if(f==1){
						putchar('#');
					}
					else if(e==c){
						putchar('#');
					}
					else if(f==d){
						putchar('#');
					}
					else{
						putchar('.');
					}
				}
				putchar('\n');
			}
			putchar('\n');
		}
	}
	hata:
	return 0;
}

Measured memory_bytes: 572
#include<stdio.h>

int main(void){
  int x,y;
  scanf("%d %d",&x,&y);
  
  if((4*x-y) % 2 == 0 && 2*x <= y && 4*x >= y){
    printf("Yes");
  }else{
    printf("No");
  }
  
  return 0;
}



Measured memory_bytes: 1732
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    ll a[200003] {0};
    a[0] = -1;
    for(int i = 1; i <= n; i++) cin >> a[i];
    ll ans = 0;
    for(int i = 0; i <= n; i++){
        if(a[i] + 1 < a[i + 1]){
            cout << -1 << endl;
            return 0;
        }
        while(a[i] + 1 == a[i + 1]) i++;
        ans += a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1920
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
string n;
int ns;
string t[500000];
int pos;
int use[30];

bool che(string x){
rep(i,26)use[i]=0;

rep(i,ns){
	int tmp=x[i]-'a';
	if(!use[tmp]&&tmp>0){
		x[i]--;
		use[tmp]=1;
	}
}
	return x==n;
}

void dfs(int now,string x){
	if(ns==now){

		if(che(x))t[pos++]=x;
		return;
	}

	dfs(now+1,x+n[now]);

	if(n[now]!='z'){
		char a=n[now];
		a++;
		dfs(now+1,x+a);
	}

}

int main(){
while(cin>>n,n!="#"){

ns=n.size();
dfs(0,"");
cout<<pos<<endl;
if(pos<=10){
	rep(i,pos)cout<<t[i]<<endl;
}

else{
	rep(i,5)cout<<t[i]<<endl;
	for(int i=pos-5;i<pos;i++)cout<<t[i]<<endl;
}
rep(i,pos)t[i]="";
pos=0;
}
	return 0;
}


Measured memory_bytes: 8244
#import numpy as np
N = int(input())
A = list(map(int, input().split()))
#A = np.array(A)
B = [0]*N
#indices = [*range(len(A))]
#sorted_indices = sorted(indices, key=lambda i: A[i])
#for i in range(1, N+1):
#    B.append(A.index(i)+1)
#print(B)
#sorted_indices = sorted_indices + B
for i in range(N):
    B[A[i]-1] = i + 1
print(*B)
#print(*sorted_indices)

Measured memory_bytes: 13812
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

  int red = 0;
  for(int i = 0;i < N;i++) {
    if(S.at(i) == 'R') red++;
  }

  if(red > N/2) cout << "Yes" << endl;
  else cout << "No" << endl;
}



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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(void){
    ll N,K; cin >> N >> K;
    vector<ll> A(N); REP(i,N) cin >> A[i];
    vector<ll> S1(N+1), S2(N+1); S1[0] = 0; S2[0] = 0;
    REP(i,N){
        S1[i+1] = S1[i] + A[i];
        S2[i+1] = (S1[i+1] - (i+1)) % K;
    }

    map<ll,ll> m;
    REP(i,min(N+1,K)){
        if(m.find(S2[i]) == m.end()) m[S2[i]] = 1;
        else m[S2[i]]++;
    }

    ll ans = 0;
    for(auto p : m){
        ans += p.second * (p.second-1) / 2;
    }

    FOR(i,K,N+1){
        if(m[S2[i-K]]) m[S2[i-K]]--;
        else m.erase(m[S2[i-K]]);
        if(m.find(S2[i]) != m.end()) ans += m[S2[i]]++;
        else m[S2[i]] = 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 17408
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int i = 1,x;
		try{
			while((x = scn.nextInt()) != 0) {
				System.out.println("Case " + i + ": " + x);
				i++;
			}
		}catch(Exception e) {

		}
		scn.close();
	}
}


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

int main() {
	int N;
	cin >> N;
	unordered_map<int, int>A;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		A[a]++;
	}
	if (A.size() == 1 && A[0] > 0) {
		cout << "Yes" << endl;
		return 0;
	}
	if (A.size() == 2) {
		int Zero=0, Other=0;
		for (const auto& a : A) (a.first == 0 ?  Zero : Other) = a.second;
		cout << (Other == Zero * 2 ? "Yes" : "No") << endl;
		return 0;
	}
	if (A.size() == 3) {
		int Val [3] , Num[3];
		int i = 0;
		for (const auto& a : A) {
			Val[i] = a.first;
			Num[i] = a.second;
			i++;
		}
		if ((Val[0] ^ Val[1]) == Val[2] && Num[0] == Num[1] && Num[1] == Num[2]) cout << "Yes" << endl;
		else cout << "No" << endl;
		return 0;
	}
	if (A.size() >= 4) {
		cout << "No" << endl;
		return 0;
	}
}


Measured memory_bytes: 3620
n = int(input())
s = [input() for _ in range(n)]

l = 0
r = 0
m = []


def fin():
    print("No")
    exit()


for word in s:
    stack = []
    for e in word:
        if stack and stack[-1] == "(" and e == ")":
            stack.pop()
        else:
            stack.append(e)

    if stack:
        if stack[0] == ")" and stack[-1] == "(":
            m.append(stack)
        elif stack[0] == ")":
            r += len(stack)
        else:
            l += len(stack)

ml = []
mm = 0
mr = []

for word in m:
    ll = word.index("(")
    rr = len(word) - ll
    if ll > rr:
        mr.append([ll, rr])
    elif ll < rr:
        ml.append([ll, rr])
    else:
        mm = max(mm, ll)

ml.sort()
for ll, rr in ml:
    l -= ll

    if l < 0:
        fin()

    l += rr

mr.sort(key=lambda x: x[1])
for ll, rr in mr:
    r -= rr

    if r < 0:
        fin()

    r += ll

if mm <= l or mm <= r:
    if l == r:
        print("Yes")
        exit()

fin()


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

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> str(H);
  for (int i = 0; i < H; i++) {
   	cin >> str.at(i); 
  }
  
  string tb(W, '#');
  
  //cout << tb << endl;
  
  for (int i = 0; i < H + 2; i++) {
   	if (i == 0 || i == H + 1)
	    cout << "#" + tb + "#" << endl;
    else
     	cout << "#" + str[i - 1] + "#" << endl; 
  }
 
	 
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int mi=0;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]<0) mi++;
		A[i]=abs(A[i]);
	}
	sort(A,A+N);
	ll ret=0;
	FOR(i,N) {
		if(mi%2&&i==0) ret+=-A[i];
		else ret+=A[i];
	}
	cout<<ret<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;
const static ll MOD = 1e9 + 7;

int main(int argc, char *argv[]) {
    string s, t;
    cin >> s >> t;
    ll a, b;
    cin >> a >> b;
    string u;
    cin >> u;

    u == s ? cout << (to_string(a - 1) + " " + to_string(b)) << endl : cout << (to_string(a) + " " + to_string(b - 1))
                                                                            << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  int A, B;
  cin >> A >> B;
  cout << max({A+B, A-B, A*B}) << endl;
  return 0;
}

Measured memory_bytes: 256
s = list(input())
#print(s)
if s[0]!='A':
    print('WA')
    exit()
else:
    del s[0]
    for i in range(len(s)-1):
        if s[i] =='C' and 0<i:
            del s[i]
            if not str.islower(str(s)):
                print('WA')
                exit()
            else:
                print('AC')
                exit()
        else:
            continue
    print('WA')
    exit()

Measured memory_bytes: 3064
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    d,g=parseMap(split(readline()))
    pc=[parseMap(split(readline())) for i in 1:d]
    ans=10^9
    for i in 0:(1<<d)-1
        point=0
        no_max=0    # 解かなかった中で最も大きい点数
        cnt=0
        for j in 1:d
            if i & (1<<(j-1)) == 0
                point+=pc[j][1]*100*j+pc[j][2]
                cnt+=pc[j][1]
            else
                no_max=max(no_max,j)
            end
        end
        if point>=g
            ans=min(ans,cnt)
        else
            # 点数が足りなかった場合、no_max点の問題を解いて足りるか試していく
            for j in 1:pc[no_max][1]
                point+=100*no_max
                cnt+=1
                if j==pc[no_max][1]
                    point+=pc[no_max][2]
                end
                if point>=g
                    ans=min(ans,cnt)
                end
            end
        end
    end
    println(ans)
end
main()

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

using namespace std;

typedef long long ll;
typedef long double ld;
#define gap ' '
#define L(i) ((i) - (&i))

const int MAXN = 1e7 + 5;
	
int main(){	
	string s; cin >> s;
	string t = s;
	reverse(t.begin(), t.end());
	if(s != t){
		cout << "No" << endl; return 0;
	}
	string k, j;
	int n = s.length();
	int first = (n+3)/2-1, second =  (n-1)/2;
	--second;
	for(int i = 0; i <= second; ++i){
		k.push_back(s[i]);
	}
	for(int i = first; i < n; ++i){
		j.push_back(s[i]);
	}
	string a = j, b = k;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	if(a != j or b != k){
		cout << "No" << endl;
	}
	else{
		cout << "Yes" << endl;
	}
	return 0;
}


Measured memory_bytes: 3584
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>

using namespace std;

int main(){
  int N;
  scanf("%d", &N);
  map<int, int> D;
  for (int i = 0; i < N; i++){
    int temp;
    scanf("%d", &temp);
    if (D.find(temp) == D.end()){
      D[temp] = 1;
    }else{
      D[temp]++;
    }
  }
  int M;
  scanf("%d", &M);
  for (int i = 0; i < M; i++){
    int temp;
    scanf("%d", &temp);
    if (D.find(temp) != D.end()){
      D[temp]--;
      if (D[temp] == 0){
        D.erase(temp);
      }
    }else{
      cout << "NO";
      return 0;
    }
  }
  cout << "YES";
  return 0;
}


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

#define ll long long int
 
int main() {
    ll t, n, sum = 0;
    cin >> t >> n;
    for(int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        sum += x;
    }
    if(sum > t) 
        cout << -1 << endl;
    else 
        cout << (t - sum) << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#define int long long
using namespace std;

#define fin(i,n) for (int i = 0; i < n; i++)
#define fin2(i,a,b) for (int i = a; i < b; i++)
#define ford(i,n) for (int i = n-1; i >= 0; i--)
#define ford2(i,a,b) for (int i = a-1; i >= b; i--)
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define mod 1000000007
#define PI 3.1415926535897932384626
#define EXP1 2.718281828459045
#define BIG 1000000000000000000

#define sl(n) scanf("%lld", &n)
#define sll(n,m) scanf("%lld %lld", &n, &m)
#define slll(n,m,k) scanf("%lld %lld %lld", &n, &m, &k)
#define sllll(n,m,k,o) scanf("%lld %lld %lld %lld", &n, &m, &k, &o)
#define sd(n) scanf("%lf", &n)
#define sdd(n,m) scanf("%lf %lf", &n, &m)
#define sddd(n,m,k) scanf("%lf %lf %lf", &n, &m, &k)
#define sc(c) scanf(" %c", &c)
#define ss(s) scanf("%s", s)
#define sal(t,n) fin(iz,n) { scanf("%lld", &t[iz]); }
#define sad(t,n) fin(iz,n) { scanf("%lf", &t[iz]); }
#define gl(t) scanf(" %[^\n]", t);

#define pc(n) printf("%c\n", n)
#define ps(s) printf("%s\n", s)
#define pss(s) printf("%s\n", s.c_str())
#define pl(n) printf("%lld\n", n)
#define pll(n,m) printf("%lld %lld\n", n, m)
#define plll(n,m,k) printf("%lld %lld %lld\n", n, m, k)
#define pd(n) printf("%lf\n", n)
#define pdd(n,m) printf("%lf %lf\n", n, m)
#define pal(t,n) fin(rz,n) { printf("%lld ", t[rz]); } printf("\n")
#define pad(t,n) fin(rz,n) { printf("%lf ", t[rz]); } printf("\n")

#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
 
#define OK ps("OK")
#define OK1 ps("OK1")
#define OK2 ps("OK2")

#define ll int
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>

#define dll pair<ll, ll>
#define vdll vector<dll>
#define vvdll vector<vdll>

#define vb vector<bool>
#define vvb vector<vb>
#define vd vector<double>
#define vvd vector<vd>
#define vc vector<char>
#define vvc vector<vc>

#define all(v) v.begin(), v.end()
#define vlen(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second

int n,m;
const int borne = (int)(1e5) + 5;
vl adj[borne];
vl dp;

int gdp(int i)
{
    if (dp[i] == -1) {
        dp[i] = 0;
        for (int vo : adj[i]) chmax(dp[i], gdp(vo) + 1);
    }
    return dp[i];
}

signed main()
{
    sll(n, m);
    fin(i, m) {
        int x, y;
        sll(x, y);
        adj[x].push_back(y);
    }
    dp.assign(borne, -1);

    int r = 0;
    fin2(i, 1, n+1) chmax(r, gdp(i));
    pl(r);
}

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

#define pb         push_back

const int INF = 100000000;

int main(void) {
	map<char, int> key;
	key['q'] = 0;
	key['w'] = 0;
	key['e'] = 0;
	key['r'] = 0;
	key['t'] = 0;
	key['a'] = 0;
	key['s'] = 0;
	key['d'] = 0;
	key['f'] = 0;
	key['g'] = 0;
	key['z'] = 0;
	key['x'] = 0;
	key['c'] = 0;
	key['v'] = 0;
	key['b'] = 0;
	key['y'] = 1;
	key['u'] = 1;
	key['i'] = 1;
	key['o'] = 1;
	key['p'] = 1;
	key['h'] = 1;
	key['j'] = 1;
	key['k'] = 1;
	key['l'] = 1;
	key['n'] = 1;
	key['m'] = 1;

	while(1){
		string s;
		int cnt = 0;

		cin >> s;
		if(s[0] == '#') break;
		
		int state = key[s[0]];
		for(int i=0; i<s.size(); i++){
			if(state != key[s[i]]) {
				cnt++;	
				state = key[s[i]];
			}
		}

		cout << cnt << endl;

	}
	
	return 0;
}

Measured memory_bytes: 1188
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1100;

struct node{
	ll x,y;
}r[maxn];

bool cmp(node a,node b){
	return atan2(a.x,a.y)<atan2(b.x,b.y);
}

int main(){
	ll n,x,y;
	cin>>n;
	for(ll i=0;i<n;i++) cin>>r[i].x>>r[i].y;
	sort(r,r+n,cmp);
	ll ans=0;
	for(ll i=0;i<n;i++){
		x=r[i].x;y=r[i].y;
		ans=max(ans,x*x+y*y);
		for(ll j=(i+1)%n;j!=i;j=(j+1)%n){
			x+=r[j].x;
			y+=r[j].y;
			ans=max(ans,x*x+y*y);
		}
	}
	double Ans=sqrt(ans);
	printf("%.13lf\n",Ans);
	
	return 0;
}

Measured memory_bytes: 384
import fractions
a,b,c,d=map(int,input().split())
allab=b-a+1

cc=b//c-a//c
dd=b//d-a//d
lcm=c*d//fractions.gcd(c,d)
#print(lcm)
ee=b//lcm-a//lcm
if a%c==0:
  cc+=1
if a%d==0:
  dd+=1
if a%lcm==0:
  ee+=1
print(allab-cc-dd+ee)

Measured memory_bytes: 5044
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") 
///#pragma GCC target("avx2")
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <iomanip>
#include <cassert>
#include <functional>
#include <ctime>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <climits>
#include <numeric>

using namespace std;
#define open_streams ifstream fin("olympiad.in");ofstream fout("olympiad.out")
#define close_streams fin.close();fout.close()
#define speed cout.tie(0);cin.tie(0);ios_base::sync_with_stdio(0)
#define ll long long
#define ull unsigned long long
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define UNIQ(a) a.resize(unique(all(a)) - a.begin())
#define eps 1e-6
//const double PI = M_PI;
const int INF = INT_MAX;
const ll limit = 1LL * 4e18;
const int MOD = 1e9 + 711;
const int MOD2 = 1e9 + 933;
//---------------------------------------------------------------------------
const int mod = 1e9 + 7;
const int maxn = 2e5 + 100;





signed main() {
	speed;	
	ll n, k;
	cin >> n >> k;
	cout << min(n%k, k - n % k);
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int n,max,i,m,j;
	max=0;
	m=0;
	scanf("%d",&n);
	int a[n];
	for(i=0;i<n;i++){
		scanf("%d\n",&a[i]);
		if(a[i]>max){
			if(a[i]>m){
				max=m;
				m=a[i];
			}else{
				max=a[i];
			}
		}
	}
	for(i=0;i<n;i++){
		if(a[i]==m){
			printf("%d\n",max);
		}else{
			printf("%d\n",m);
		}
	}
	// your code goes here
	return 0;
}


Measured memory_bytes: 2304
<?php
$input = explode(' ', trim(fgets(STDIN)));

$n = (int)$input[0];
$k = (int)$input[1];

$input = explode(' ', trim(fgets(STDIN)));
$h_list = [];
foreach ($input as $i => $v) {
	$h_list[$i+1] = (int)$v;
}

$dp = [];
for ($i=1; $i <= $n; $i++) { 
	$dp[$i] = INF;
}
$dp[1] = 0;
$dp[2] = abs($h_list[1] - $h_list[2]);

for ($i=3; $i <= $n; $i++) { 
	$from = max(1, $i - $k);
	for ($j=$from; $j < $i; $j++) { 
		$dp[$i] = min($dp[$j] + abs($h_list[$j] - $h_list[$i]), $dp[$i]);
	}
}
echo $dp[$n];

Measured memory_bytes: 23024
A,B,C=map(int,input().split())
saidai=max(A,B,C)
saishou=min(A,B,C)
count=0

if  saidai==saishou:
    print(0)
    exit()


if (saidai*3-(A+B+C))%2==0:
    count=int((saidai*3-(A+B+C))/2)
else:
    count=2+int((saidai*3-(A+B+C))/2)

print(count)

Measured memory_bytes: 3064
n,m = map(int,input().split())

ans = 1

for i in range(1,int(m**0.5)+1):
    if m % i == 0 and m /n >= i:
        ans = max(ans,i)
        if i != m // i and m/n >= (m//i):
            ans = max(ans,m // i)

print(ans)


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;
map<pint,int>table;
int cur;
vpint G[1000000];

int make(int a,int c){
    if(table.count({a,c}))return table[{a,c}];
    table[{a,c}]=cur;
    G[a].pb({cur,1});
    G[cur].pb({a,0});
    return cur++;
}
int dist[1000000];

signed main(){
    cin>>N>>M;
    cur=N;
    rep(i,M){
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        a=make(a,c);
        b=make(b,c);
        G[a].pb({b,0});
        G[b].pb({a,0});
    }

    fill_n(dist,cur,1001001001);
    dist[0]=0;
    priority_queue<pint>que;
    que.push({0,0});
    while(que.size()){
        int v,c;
        tie(c,v)=que.top();que.pop();
        c=-c;
        if(dist[v]<c)continue;
        for(auto e:G[v]){
            if(dist[e.fi]<=c+e.se)continue;
            dist[e.fi]=c+e.se;
            que.push({-dist[e.fi],e.fi});
        }
    }

    if(dist[N-1]==1001001001)cout<<-1<<endl;
    else cout<<dist[N-1]<<endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

    int N;
    cin >> N;
    vector<ll> x(N), y(N);
    for(int i = 0; i < N; i++){
        cin >> x[i] >> y[i];
    }

    map<pair<ll, ll>, int> mp;

    ll tmp_x, tmp_y;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i != j){
                tmp_x = x[j] - x[i];
                tmp_y = y[j] - y[i];
                if(mp.count(make_pair(tmp_x, tmp_y)) == 0){
                    mp.insert(make_pair(make_pair(tmp_x, tmp_y), 1));
                }else{
                    mp[make_pair(tmp_x, tmp_y)]++;
                }
            }
        }
    }

    // for(auto itr = mp.begin(); itr != mp.end(); itr++){
    //     cout << itr->first.first << " " << itr->first.second << " " << itr->second <<  endl;
    // }

    int ans;
    if(N == 1){
        ans = 1;
    }else{
        ans = 100;

        for(auto itr = mp.begin(); itr != mp.end(); itr++){
            chmin(ans, N - itr->second);
        }
    }

    cout << ans << endl;


    return 0;
}



Measured memory_bytes: 384
#include <cstdio>
#include <vector>
#define pb push_back
#define tl(x) ((int)x.size()-1)
#define rep(i,j,k) for (i=j;i<=k;i++)
using namespace std;
const int N=1e5+5;
int n,i,u,v,ans;
vector<int> b[N];
int dfs(int x,int fa) {
	int j,ret=0;
	rep(j,0,tl(b[x]))
	if (b[x][j]!=fa)
		ret^=dfs(b[x][j],x)+1;
	return ret;
}
int main()
{
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n-1)
	{
		scanf("%d%d",&u,&v);
		b[u].pb(v); b[v].pb(u);
	}
	ans=dfs(1,1);
	if (ans) printf("Alice\n");
	else printf("Bob\n");
	return 0;
}

Measured memory_bytes: 10368
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926525
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------
ll a[200005];

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int n;cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  bool flag=false;
  // int a_init=0;
  ll cnt=0;
  if(a[n]>=n)flag=true;
  for(int i=1;i<n;i++){
    if(a[i]>=i){
      flag=true;
      break;
    }
    if(a[i+1]>a[i]+1){
      flag=true;
      break;
    }
    // ここは正しいっぽい
    if(a[i]>=a[i+1]){
      cnt+=a[i];
    }
  }
  cnt+=a[n];
  if(flag){
    P(-1);
    return 0;
  }else{
    P(cnt);
  }
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
int main(void){
  int n,i,ans;
  scanf("%d",&n);
  ans=n;
  char t[n];
  scanf("%s",t);
  for(i=0;i<n-1;i++){
    if(t[i]==t[i+1]){
      ans--;
    }
  }
  printf("%d",ans);
}

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

int main(){
	int N, K;
	cin >> N >> K;
	int L[K], R[K];
	rep(i,K) cin >> L[i] >> R[i];
	
	vector<ll> dp(2*N+5);
	dp[0] = 1;
	dp[1] = -1;
	rep(i,N) {
		rep(j,K) {
			dp[i+L[j]] += dp[i];
			dp[i+L[j]] = (dp[i+L[j]]+mod)%mod;
			dp[i+R[j]+1] -= dp[i];
		}
		dp[i+1] += dp[i];
		dp[i+1] = (dp[i+1]+mod)%mod;
	}	
	cout << dp[N-1] << endl;

	return 0;
}


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

using namespace std;

int main(){
    int a, b, c; cin >> a >> b >> c;
    if(a>b) swap(a, b);
    if((a <= c) && (c <= b)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  
  for(int i=0;i<n;i++){
    if( a.at(i)%2 == 0 ){
      if( a.at(i)%3 != 0 && a.at(i)%5 != 0 ){
        cout << "DENIED" << endl;
        return 0;
      }
    }
  }
  cout << "APPROVED" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
#define DBG(X) cout << #X << "=" << (X) << '\n';
#define SAY(X) cout << (X) << '\n';
#else
#define DBG(X)
#define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

std::string pad(int num)
{
    char buffer[4];
    std::snprintf(buffer, sizeof(buffer), "%03d", num);
    return buffer;
}

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

ull solve()
{
    ull N;

    std::cin >> N;

    ull inc = 0;
    ull money = 100;
    ull counter = 0;
    while (N - money > inc) {
        money += inc;
        inc = money / 100;
        ++counter;
        //cout << money << '\n';
    }

    return counter;
}

int main()
{
    std::cout << solve() << std::endl;
//    solve();

    return 0;
}

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

int main(){
    long long n , tw;
    cin>>n>>tw;
    long long dp[n + 1][tw + 1] , w[n + 1] , v[n + 1];
    for(long long i = 0; i <= n; i++){
        dp[i][0] = 0;
    }
    for(int i = 0; i <= tw; i++){
        dp[0][i] = 0;
    }
    for(int i = 1; i <= n; i++){
        cin>>w[i]>>v[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= tw; j++){
            if(j < w[i]){
                dp[i][j] = dp[i - 1][j];
            }
            else{
                dp[i][j] = max(v[i] + dp[i - 1][j - w[i]] , dp[i - 1][j]);
            }
        }
    }
    cout<<dp[n][tw]<<endl;
}

Measured memory_bytes: 82344
/**
     *    author:  shashank_hire
    **/
#include <bits/stdc++.h>
using namespace std;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define ll long long
#define ld long double
#define MOD 1000000007

vector<int> find3Numbers(vector<int> arr, int N) {
    // Your code here
    vector<int> dp;
    dp.push_back(arr[0]);
    int i;
    for(i=1;i<N;i++)
        {
            if(lower_bound(dp.begin(), dp.end(), arr[i])!=dp.end())
                *lower_bound(dp.begin(), dp.end(), arr[i]) = arr[i];
            else
                dp.push_back(arr[i]);
            // if(dp.size()==3)
    for(int j=0;j<dp.size();j++)
        cout<<dp[j]<<" \n"[j==dp.size()-1];
            if(dp.size()==3)
                return dp;
        }
    for(i=0;i<dp.size();i++)
        cout<<dp[i]<<" \n"[i==dp.size()-1];
    return vector<int>(0);
}

// main function
int main()
{
    ll n, m;
    cin>>n>>m;
    cout<<(n*(n-1)/2) + (m*(m-1)/2)<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define INF 10000000000
using namespace std;
using ll = long long;
int main()
{
    int n,r;
    cin >> n >> r;
    if(n >= 10){
        cout << r << endl;
    }else{
        cout << r+100 * (10 - n) << endl;
    }
}

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

typedef long long ll;
#define int ll
#define pb push_back
const int INF = 1e18;

signed main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n,k;
	cin>>n>>k;
	int arr[n];
	for(int i=0;i<n;i++)
		cin>>arr[i];

	vector<int> dp(k+1,0);
	for(int i=0;i<k;i++){
		for(int j=0;j<n;j++){
			if (arr[j] + i > k or dp[arr[j]+i] == 1)
				continue;
			dp[arr[j]+i] = dp[i]^1;
		}
	}
	if (dp[k])
		cout<<"First";
	else 
		cout<<"Second";
	return 0;
}

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

using namespace std;
typedef long long ll;

vector<ll>a(5005);
vector<ll>b(5005);
vector<ll>track;
bool vis[5005];

void dfs(int u, long long total_cycle)
{
    if(vis[u])
        return ;
    vis[u]=true;
    total_cycle+=b[u];
    track.push_back(total_cycle);
    dfs(a[u],total_cycle);
}
void solve()
{
    int n,k;
    cin>>n>>k;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        a[i]--;
    }
    for(int i=0; i<n; i++)
        cin>>b[i];
    ll ans=-2e18;
    for(int i=0; i<n; i++)
    {
        memset(vis,false,sizeof(vis));
        dfs(i,0);

        ll m = (ll) track.size();
        if(track.back()>0 && k>=m)
        {
            ll cycles= k/m;
            ll left= k%m;
            ll maxi=-2e18;
            for(int x=0; x<(int)track.size(); x++)
                maxi=max(maxi,track[x]);
            ans=max(ans,(cycles-1)*(track.back())+maxi);
            maxi=-2e18;
            for(int x=0; x<left; x++)
                maxi=max(maxi,track[x]);
            ans=max(ans,(cycles*track.back()) + maxi);
        }
        else
        {
            for(int j=0; j<(min((int)track.size(),k)); j++)
            {
                ans=max(ans,track[j]);
            }
        }
        track.clear();
    }
    cout<<ans;
    return;
}

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

    solve();
}


Measured memory_bytes: 3972
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n, m, k = map(int, input().split())
ans = 0
c = 998244353

ans = m * pow(m-1, n-1, mod=c)
temp = 1
for i in range(1, k+1):
    temp = temp*(n-i) % c
    temp = temp*invmod(i, c) % c
    ans += temp * m * pow(m-1, n-1-i, mod=c)
    ans = ans % c
print(ans%c)

Measured memory_bytes: 9184
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;



int main() {
    int n;
    cin >> n;
    vector<ll> u(n), v(n+1, 0);
    for (auto &&i : u) scanf("%lld", &i);
    partial_sum(u.begin(), u.end(), v.begin()+1);
    ll ans = INF<ll>;
    int l = 1, r = 4;
    for (int i = 2; i < n-1; ++i) {
        l--, r--;
        if(r <= i) r = i+1;
        if(l >= i) l = i-1;
        while(l < i && v[i] > 2*v[l]) l++;
        while(r < n && v[n]+v[i] > 2*v[r]) r++;
        for (int j = 0; j < 2 && l > j; ++j) {
            for (int k = 0; k < 2 && r > i; ++k) {
                ans = min(ans, max({v[l-j], v[i]-v[l-j], v[r-k]-v[i], v[n]-v[r-k]})-
                               min({v[l-j], v[i]-v[l-j], v[r-k]-v[i], v[n]-v[r-k]}));
            }
        }

    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

#define INF (i64)1e18
#define MOD (i64)(1e9+7)
#define REP(i, n) for(i64 i = 0; i < n; i++)
#define RANGE(i, a, b) for(i64 i = a; i < b; i++)
#define EACH(v, e, p) for_each(v.begin(), v.end(), [](auto& e) p)

int main() {
  int n;
  cin >> n;
  int ans = n % 1000;
  if (ans != 0) ans = 1000 - ans;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3616
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4.2")
#include <bits/stdc++.h>

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = 1e9+7; typedef vector<ll> VL;

void dbg(){ cerr << "\n"; } template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
	
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, k;
	cin >>n >>k;
	vector<pii> td(n);
	rep(i, n) cin >>td[i].second >>td[i].first;
	sort(td.rbegin(), td.rend());
	ll sm = 0;
	map<int,int> mp;
	VI dls;
	rep(i, k){
		int df,ds; tie(df, ds) = td[i];
		sm += df;
		if(mp.count(ds)>0) dls.push_back(df);
		mp[ds]++;
	}
	sort(all(dls));
	ll ans = sm + (ll)sz(mp)*sz(mp);
	int ct=0;
	rep2(i, k, n){
		if(ct >= sz(dls)) break;
		int df,ds; tie(df, ds) = td[i];
		if(mp.count(ds)) continue;
		sm += df; sm -=dls[ct];
		ct++; mp[ds]++;
		ans  = max(ans, sm + (ll)sz(mp) * sz(mp));
		//dbg(ans, sm, sz(mp), sz(dls));
	}
	cout << ans <<"\n";
	return 0;
}
//49304328985977

Measured memory_bytes: 4224
n, m, x = map(int, input().split())
text = []
ans=10000000000000
for i in range(n):
    tmp = list(map(int, input().split()))
    text.append(tmp)
for i in range(2**n):
    total = [0] * (m + 1)
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m+1):
                total[k]+=text[j][k]
    cnt=0
    for k in range(1,m+1):
        if total[k]>=x:
            cnt+=1
    if cnt==m:
        ans=min(ans,total[0])
if ans==10000000000000:
    print(-1)
else:
    print(ans)



Measured memory_bytes: 68752
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>

using namespace std;

#define SWAP(type, a, b) do { type t = a; a = b; b = t; } while(0)

typedef struct {
    int* verIdx;
    int num;
} Heap;

int* d; 
int* weight;
int n;

void makeMinHeap(Heap *heap, int idx);
void insert(Heap *heap, int key);
int extract(Heap *heap);

static inline int getParent(int idx) { return idx / 2; }
static inline int getLeft(int idx) { return idx * 2; }
static inline int getRight(int idx) { return idx * 2 + 1; }
static inline bool isCorrectHeapIdx(int idx, int heapSize) { return idx <= heapSize && 1 <= idx; }
static inline bool isEmpty(Heap *heap) { return heap->num <= 0; }

static inline int getMinCost(int idx) {
    return d[idx];
}

void makeMinHeap(Heap *heap, int idx) {
    int left = getLeft(idx);
    int right = getRight(idx);

    int minIdx = idx;
    if(isCorrectHeapIdx(left, heap->num) && getMinCost(heap->verIdx[minIdx]) > getMinCost(heap->verIdx[left])) {
        minIdx = left;
    } if(isCorrectHeapIdx(right, heap->num) && getMinCost(heap->verIdx[minIdx]) > getMinCost(heap->verIdx[right])) {
        minIdx = right;
    }

    if(minIdx != idx) {
        SWAP(int, heap->verIdx[minIdx], heap->verIdx[idx]);
        makeMinHeap(heap, minIdx);
    }
}

void insert(Heap *heap, int* key) {
    heap->verIdx[++heap->num] = *key;
    for(int i = getParent(heap->num); i >= 1; i = getParent(i)) {
        makeMinHeap(heap, i);
    }
}

void extract(Heap *heap, int* key) {
    *key = heap->verIdx[1];
    heap->verIdx[1] = heap->verIdx[heap->num--];
    makeMinHeap(heap, 1);
}

static inline bool isConnected(int s, int t) {
    return weight[s * n + t] != INT_MAX;
}

static inline int getWeight(int s, int t) {
    return weight[s * n + t];
}

void solve(int s) {
    Heap que;
    bool* isAddS = new bool[n]();

    que.verIdx = new int[n * n];
    que.num = 0;

    d = new int[n];
    d[s] = 0;
    for(int i = 0; i < n; i++) {
        if(s != i) {
            d[i] = INT_MAX;
        }
    }
    
    insert(&que, &s);

    while(1) {
        int u;
        while(1) {
            if(isEmpty(&que)) {
                return;
            } 

            extract(&que, &u);
            if(!isAddS[u]) {
                break;
            }
        }

        isAddS[u] = true;

        for(int i = 0; i < n; i++) {
            if(isConnected(u, i) && !isAddS[i]) {
                if(d[u] + getWeight(u, i) < d[i]) {
                    d[i] = d[u] + getWeight(u, i);
                }
                insert(&que, &i);
            }
        }
    }

    return;
}

int main() {

    scanf("%d", &n);

    weight = new int[n * n];

    for(int i = 0; i < n * n; i++) {
        weight[i] = INT_MAX;
    }
    

    for(int i = 0; i < n; i++) {
        int s;
        int deg;

        scanf("%d %d", &s, &deg);
        for(int j = 0; j < deg; j++) {
            int t;
            int w;

            scanf("%d %d", &t, &w);

            weight[s * n + t] = w;
        }
    }

    solve(0);

    for(int i = 0; i < n; i++) {
        cout << i << " " << d[i] << endl;
        
    }
}


Measured memory_bytes: 3240
import java.util.*;
import java.io.*;




 
public class Main 
{
	
	public static void main(String[] args) throws IOException 
	{ 
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		long k=s.nextLong();
		
		int ar[]=new int[n];
		for(int i=0;i<n;i++) {
			int u=s.nextInt();
			u--;
			ar[i]=u;
		}
		if(k<n) {
			int count=0;
			int next=0;
			while(count<k) {
				int val=ar[next];
				count++;
				next=val;
			}
			System.out.println(next+1);
		}else {
			int pos=0;
			int next=0;
			int noofnode=-1;
			HashMap<Integer,Integer>hm=new HashMap<>();
			hm.put(next, pos);
			while(true ) {
				pos++;
				int val=ar[next];
				if(hm.containsKey(val)) {
					noofnode=hm.get(val);
					break;
				}
				hm.put(val, pos);
				next=val;
			}
//				System.out.println(hm.size());
//				System.out.println(noofnode);
				k-=noofnode;
				int nodeincycle=hm.size()-noofnode;
				k%=nodeincycle;
				if(k==0) 
					k=nodeincycle;
				k++;
				int count=0;
				while(count<k) {
					int val=ar[next];
					count++;
					next=val;
				}
				System.out.println(next+1);
			
			
			
		}
	}

	
}




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

int main(){
    int A,B;
    scanf("%d %d",&A,&B);
    if(A==B) printf("%d",2*A);
    else if(A>B) printf("%d",A+(A-1));
    else printf("%d",B+(B-1));
    return 0;
}

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

int main() {
    using vec_t = std::vector<int>;
    int n{}, m{};
    std::cin >> n >> m;
    std::vector<vec_t> matrix(n);
    for(auto i=0; i<n; i++) {
        matrix[i] = vec_t(m);
        for(auto j=0; j<m; j++) {
           std::cin >> matrix[i][j];
        }
    }
    vec_t colvec(m);
    for(auto i=0; i<m; i++) {
        std::cin >> colvec[i];
    }
    for(auto i=0; i<n; i++) {
        int result{};
        for(auto j=0; j<m; j++) {
            result += matrix[i][j] * colvec[j];
        }
        std::cout << result << std::endl;
    }
}



Measured memory_bytes: 3128
// 7

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1ll<<29;
const bool debug = 0;

int N, M, Q;
bool valid[212345];
int a[212345];

int main() {
	cin >> N >> M >> Q;
	REP(i, M) scanf("%d", a + i);
	
	fill(valid, valid + N, 1);
	
	list<int> lis;
	REP(i, N) lis.insert(lis.end(), i);
	
	list<int>::iterator it = lis.begin();
	
	REP(i, M) {
		REP(j, a[i]) {
			if (a[i] & 1) { // 反時計周り
				--it;
				if (it == lis.end()) --it;
			}
			else { // 時計回り
				++it;
				if (it == lis.end()) ++it;
			}
		}
		
		valid[*it] = false;
		it = lis.erase(it);
		if (it == lis.end()) ++it;
	}
	
	
	REP(i, Q) {
		int q;
		scanf("%d", &q);
		printf("%d\n", valid[q]);
	}
	
	return 0;
}

Measured memory_bytes: 10464
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

int main()
{
	int N; scanf("%d",&N);
	int t;
	for(int i = 1;i <= N;t = i,i <<= 1)
		if(N == i)
		{
			printf("No\n");
			return 0;
		}
	if(N == 3)
	{
		printf("Yes\n");
		for(int i = 1;i <= 5; ++ i)
			printf("%d %d\n",i,i + 1);
	}
	else
	{
		puts("Yes");
		for(int i=2; i<N; i+=2)
		{
			printf("%d %d\n", 1, i);
			printf("%d %d\n", i, i+1);
			printf("%d %d\n", 1, N+i+1);
			printf("%d %d\n", N+i+1, N+i);
		}
		printf("%d %d\n", N+1, 3);
		if(!(N&1))
		{
			printf("%d %d\n", N, N^t);
			printf("%d %d\n", N*2, N+(t^1));
		}
	}
}

Measured memory_bytes: 2304
n,y = map(int,input().split())
res = [-1,-1,-1]
for i in range(n+1):
    for j in range(n-i+1):
        if(10000*i + 5000*j + 1000*(n-i-j) == y):
            res = [i,j,n-i-j]
            break
                
print(*res)

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert>
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
#include <chrono>

using namespace std;

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << " ";
    return a;
}

#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << "\n";
    const int INF = 1e18;
//    const int mod = 2600000069;
//    const int p = 10;
//    const ld PI = 3.1415926535;
#else
    #define dbg(x)
    const int INF = 1e18;
//    const int mod = 2600000069;
//    const int p = 179;
//    const ld PI = 3.1415926535;
#endif

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

const int MAXN = 4001;

const int MASK = (1 << 3);

int dp[MAXN][MASK];

int bit(char k) {
    if (k == 'R') return 0;
    if (k == 'G') return 1;
    if (k == 'B') return 2;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    dp[0][0] = 1;
    dp[0][1 << bit(s[0])] = 1;
    int ans = 0;
    for (int i = 1; i < n; i++) {
        int cur = (1 << bit(s[i]));
        for (int m = 0; m < (1 << 3); m++) {
            dp[i][m] += dp[i - 1][m];
            if ((m & cur) != 0) continue;
            dp[i][m | cur] += dp[i - 1][m];
        }
    }
    ans = dp[n - 1][7];
    int m;
    for (int i = 1; i < n - 1; i++) {
        for (int d = 1; d <= min(i, n - i - 1); d++) {
            m = (1 << bit(s[i])) + (1 << (bit(s[i - d]))) + (1 << (bit(s[i + d])));
            if (m == 7) {
//                cout << i - d << " " << i << " " << i + d << "\n";
                ans--;
            }
        }
    }
//    dbg(dp[n - 1][7]);
    cout << ans;
    //----------------------------------------------------------------------
    #ifdef LOCAL
        cout << "\n";
        cerr << "Time elapsed: " << (double)clock()/CLOCKS_PER_SEC << "s.\n";
    #endif
}
/*

*/


Measured memory_bytes: 3448