akhauriyash/Code-Regression huggingface dataset:
#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;}

const int INF=1001001001001001001ll;

struct segtree{
    static const int SEG=1<<12;
    vpint dat;
    segtree():dat(SEG*2,pint(-INF,-1)){}
    void init(){
        fill(all(dat),pint(-INF,-1));
    }
    void update(int k,pint x){
        k+=SEG-1;
        chmax(dat[k],x);
        while(k){
            k=(k-1)/2;
            dat[k]=max(dat[k*2+1],dat[k*2+2]);
        }
    }
    pint query(int a,int b,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return pint(-INF,-1);
        if(a<=l&&r<=b)return dat[k];
        return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
    }
};

int N;
int A[4010];
int sum[4010];
int dp[4010][4010];
short pre[4010][4010];
int idx[4010];
signed main(){
    cin>>N;
    rep(i,N)cin>>A[i];
    rep(i,N)sum[i+1]=sum[i]+A[i];

    fill_n(*dp,4010*4010,INF);
    dp[0][0]=-INF;
    segtree seg;
    for(int i=0;i<N;i++){
        seg.init();
        vpint vec;
        for(int j=0;j<N;j++)vec.pb(pint(dp[i][j]+sum[j],j));
        sort(all(vec));
        for(int j=0;j<N;j++)idx[vec[j].se]=j;

        for(int j=1;j<=N;j++){
            seg.update(idx[j-1],pint(sum[j-1],j-1));
            int lb=-1,ub=vec.size();
            while(ub-lb>1){
                int mid=(ub+lb)/2;
                if(vec[mid].fi<sum[j])lb=mid;
                else ub=mid;
            }
            if(ub==0)continue;
            pint p=seg.query(0,ub);
            if(p.fi==-INF)continue;
            dp[i+1][j]=sum[j]-p.fi;
            pre[i+1][j]=p.se;
        }

    }

    int x;
    for(x=N;;x--)if(dp[x][N]!=INF)break;
    int y=N;
    vint ans;
    for(int i=x;i>1;i--){
        y=pre[i][y];
        ans.pb(y);
    }
    reverse(all(ans));
    cout<<ans.size()+1<<endl;
    for(int i=0;i<ans.size();i++){
        if(i)cout<<" ";
        cout<<ans[i];
    }cout<<endl;

    return 0;
}

Measured memory_bytes: 140836
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

struct Node {
	Node *c[26]; int num;
	int las;
	Node() {
		rep(i, 26)c[i] = NULL;
		num = 0; las = 0;
	}
};
void add(Node* node, const string &s) {
	rep(i, s.length()) {
		int t = s[i] - 'a';
		if (node->c[t] == NULL)node->c[t] = new Node();
		node = node->c[t];
		node->num++;
	}
	node->las++;
}
int dfs(Node* node, const string &s, const string &r) {
	int ret = 0;
	rep(i, s.length()) {
		ret += node->las;
		rep(j, 26) {
			if (s[i] == r[j])break;
			if (node->c[r[j] - 'a'] != NULL)ret += node->c[r[j] - 'a']->num;
		}
		node = node->c[s[i] - 'a'];
	}
	return ret;
}

int n; vector<string> s;
vector<int> v;
int num[100000][26][26];
int b[100000];
void solve() {
	cin >> n; s.resize(n);
	Node* nd=new Node();
	rep(i, n) {
		cin >> s[i];
		if (s[i].length() > 600) {
			v.push_back(i);
		}
		else {
			add(nd, s[i]);
		}
	}
	rep(id, v.size()) {
		int i = v[id];
		rep(j, n) {
			if (s[i].length()>600&&s[j].length()>600&&i <= j)continue;
			bool f = false;
			rep(k, min(s[i].length(), s[j].length())) {
				if (s[i][k] != s[j][k]) {
					f = true;
					num[i][s[i][k] - 'a'][s[j][k] - 'a']++;
					num[j][s[j][k] - 'a'][s[i][k] - 'a']++;
					break;
				}
			}
			if (!f) {
				if (s[i].length() > s[j].length()) {
					b[i]++;
				}
				else {
					b[j]++;
				}
			}
		}
	}
	int q; cin >> q;
	rep(i, q) {
		int k; string p; cin >> k >> p; k--;
		int ans = 1 + b[k];
		vector<int> inv(26);
		rep(j, 26) {
			inv[p[j] - 'a'] = j;
		}
		rep(j, 26) {
			rep(l, 26) {
				if (inv[l] < inv[j]) {
					ans += num[k][j][l];
				}
			}
		}
		if (s[k].length() <= 600) {
			ans += dfs(nd, s[k], p);
		}
		cout << ans << endl;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}

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

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;

template<class _T> static void getint(_T& a) {
	std::cin >> a;
}
template<class _T> static void getint(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}
template <class _T> static _T tp_abs(_T a) {
	if (a < (_T)0) {
		a *= (_T)-1;
	}
	return a;
}

static void exec();

int main()
{
	exec();
	fflush(stdout);
	return 0;
}

static void exec()
{
	int N;
	getint(N);
	
	std::vector<LLONG> ai(N);
	for (int i = 0; i < N; i++) {
		getint(ai[i]);
	}

	LLONG ans[2] = { 0 };
	for (int k = 0; k < 2; k++) {
		LLONG sum = ai[0];
		if (k == 0) {
			if (sum <= 0) {
				ans[k] += (tp_abs(sum) + 1);
				sum = 1;
			}
		}
		else {
			if (sum >= 0) {
				ans[k] += (tp_abs(sum) + 1);
				sum = -1;
			}
		}

		for (int i = 1; i < N; i++) {
			int bfrSign = (sum > 0) ? 1 : -1;

			sum += ai[i];
			if ((bfrSign > 0) && (sum >= 0)) {
				ans[k] += (tp_abs(sum) + 1);
				sum = -1;
			}
			else if ((bfrSign < 0) && (sum <= 0)) {
				ans[k] += (tp_abs(sum) + 1);
				sum = 1;
			}
		}
	}
	printf("%lld\n", std::min(ans[0], ans[1]));
}


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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    ll N, K, C; cin >> N >> K >> C;
    string S; cin >> S;
    int ans[K];
    ll cnt = 0;
    REP(i, N){
        if (cnt == K) break;
        if (S[i] == 'o') {
            ans[cnt] = i; cnt++;
            i += C;
        }
    }
    cnt = 0;
    vector<int> res;
    REP(i, N){
        if (cnt == K) break;
        if (S[N-1-i] == 'o') {
            cnt++;
            if (ans[K - cnt] == N-1-i) {
                res.push_back(N-i);
            }
            i += C;
        }
    }
    for (auto idx = res.rbegin(); idx != res.rend(); idx++){
        cout << *idx << endl;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3340
#include<iostream>
#include<string>
#include<algorithm>

using namespace std ;
int main () {
  int R;
  cin >> R;
  if(R<1200) cout << "ABC" << endl;
  else if(R<2800) cout << "ARC" << endl;
  else cout << "AGC" << endl;
  return(0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp(a,b) make_pair(a,b)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
const int MOD=1000000007;
const double pi = 3.141592653589793;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
    }
    all(a);
    int sum=0;
    rep(i,k){
        sum += a[i];
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int sum=0;
    int tmp;
    rep(i,3){
        cin>>tmp;
        sum+=tmp;
    }
    if(sum>=22){
        cout<<"bust"<<endl;
    }else{
        cout<<"win"<<endl;
    }
}

Measured memory_bytes: 3508
#include <iostream>

int main()
{
    long long A, B;
    scanf("%lld %lld", &A, &B);
    
    if(B - A == 0){
        std::cout << A << std::endl;
        return 0;
    }
    if(B - A == 1){
        std::cout << (A ^ B) << std::endl;
        return 0;
    }

    long long a = (A % 2 == 0) ? A : A+1;
    long long b = (B % 2 == 1) ? B : B-1;
    long long ans = ((b - a + 1) % 4 == 0) ? 0 : 1;
    if(A % 2 == 1) ans ^= A;
    if(B % 2 == 0) ans ^= B;
    std::cout << ans << std::endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int x[9<<14];
    int i=0;
    int j=0;
    int min=9<<25;
    
    for(;~scanf("%d",x+i);i++);
    for(j=2;j<x[0]-x[1]+3;j++)min=fmin(x[j+x[1]-1]-x[j]+fmin(abs(x[j]),abs(x[j+x[1]-1])),min);
    printf("%d",min);
}

Measured memory_bytes: 2548
import math

def main():
    A = int(input())
    
    ans = 0
    for i in range(1,A+1):
        for j in range(1,A+1):
            _gcd = math.gcd(i,j)
            for k in range(1,A+1):
                gcd = math.gcd(_gcd,k)
                ans += gcd
    
    print(ans)
    
    
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 9188
#include <iostream>
#include <vector>
#include <map>

using namespace std;

//#define int long long

signed main() {
    int N, C;
    cin >> N >> C;
    
    int D[C][C], c[N][N];
    
    for(int i = 0; i < C; ++i){
        for(int j = 0; j < C; ++j){
            cin >> D[i][j];
        }
    }
    
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            cin >> c[i][j];
        }
    }
    
    map<int, int> x, y, z; //斜め列の色の頻度分布
    
    int sx = 0, sy = 0, sz = 0;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if((i + j) % 3 == 0){
                ++x[c[i][j] - 1];
                ++sx;
            }
            if((i + j) % 3 == 1){
                ++y[c[i][j] - 1];
                ++sy;
            }
            if((i + j) % 3 == 2){
                ++z[c[i][j] - 1];
                ++sz;
            }
        }
    }
    
    int ans = 1000 * N * N;
    for(int color = 0; color < C * C * C; ++color){
        int s = color % C, t = (color / C) % C, u = (color / (C * C)) % C;
        
        if(s == t | s == u | t == u){
            continue;
        }
        int cost = 0;
        
        for(int ic = 0; ic < C; ++ic){
            cost += x[ic] * D[ic][s] + y[ic] * D[ic][t] + z[ic] * D[ic][u];
        }
        if(ans > cost){
            ans = cost;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

const long long INFLL = 1LL << 60;
const int INFI = 1000000000;


int main(){
    int N; cin >> N;
    int ans = 0;
    int min = N+1;
    for(int i=0;i<N;i++){
        int n; cin >> n;
        if(min >= n) ans++;
        if(min > n) min = n;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
using System;
 
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {

    string[] input =Console.ReadLine().Split(' ');
	int a=int.Parse(input[0]);
    int b=int.Parse(input[1]);
	
      if (b%a ==0)
      {
      Console.WriteLine(a+b);
      }else{
      Console.WriteLine(b-a);
      }
      
    }
    
  }

}

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

#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)

#define LL long long
#define Ldouble long double
#define PI 3.1415926535897932384626

#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second

using namespace std;

int n, s[100005];
LL sum, cnt, c[100005];

int main(){
	scanf("%d", &n);
	FI(i, 1, n){
		scanf("%d", &s[i]);
		sum += s[i];
	}
	s[n + 1] = s[1];
	
	if(sum % (1LL * n * (n + 1) / 2) != 0){
		printf("NO\n");
		return 0;
	}
	
	cnt = sum / (1LL * n * (n + 1) / 2);
	
	FI(i, 1, n){
		LL d = s[i] + cnt - s[i + 1];
		if(d % n != 0 || d < 0){
			printf("NO\n");
			return 0;
		}
		c[i] = d / n;
	}
	FI(i, 1, n) cnt -= c[i];
	if(cnt == 0) printf("YES\n");
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int N,index=0,ans=0;cin>>N;
    vector<int> map(N,0);
    REP(i,N)cin>>map[i];
    REP(i,N){
        if(index==1){
            cout<<ans<<endl;
            return 0;
        } else {
            index=map[index]-1;
        }
        ans++;
    }
    cout<<-1<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE

template<typename T1,typename T2> void chmin(T1 &a,T2 b){if(a>b) a=b;};
template<typename T1,typename T2> void chmax(T1 &a,T2 b){if(a<b) a=b;};

signed main(){
  Int c,n,m;
  cin>>c>>n>>m;
  vector<Int> s(n),p(n);
  for(Int i=0;i<n;i++) cin>>s[i]>>p[i];

  const Int INF = 1e15;
  vector<Int> dp(c+1,-INF);
  dp[0]=0;
  for(Int i=0;i<n;i++){
    for(Int j=c;j>=0;j--){
      if(j+s[i]>c) continue;
      chmax(dp[j+s[i]],dp[j]+p[i]);
    }
  }
  for(Int i=0;i<c;i++) chmax(dp[i+1],dp[i]);
  for(Int k=1;k<=m;k++)
    cout<<dp[c/k]*k<<endl;
  return 0;
}



Measured memory_bytes: 3232
import std.stdio : write, writeln;
import std.array;
import std.range;
import std.typecons;
import std.bigint;
import std.algorithm;

void main(){
	while(true){
		int n = readln.chomp.to!int;
		if( !n )return;
		int[string] map;
		foreach(i; n.iota){
			foreach( str; readln.chomp.split){
				if( str in map ){
					++map[str];
				}else{
					map[str] = 1;
				}
			}
		}
		auto k = readln.front;
		bool[string] set;
		foreach( str; map.keys ){
			if( k == str.front ){
				set[ str ] = true;
			}
		}
		
		string[] ans;
		while( set.length > 0 ){
			int max_ = 0;
			string[] max_str;
			foreach( str; set.keys ){
				if( max_ < map[str] ){
					max_ = map[str];
					max_str = [str];
				}else if( max_ == map[str] ){
					max_str ~= str;
				}
			}
			
			max_str.sort;
			
			ans ~= max_str;
			foreach( str; max_str ){
				set.remove(str);
			}
			
			if( ans.length >= 5 ){
				ans = ans[ 0..5 ];
				break;
			}
		}
		
		bool flag = true;
		for( int i = 0; i < ans.length ; ++i ){
			if( i ){
				write = " ";
			}
			write = ans[ i ];
			flag &= false;
		}
		if( flag ) write = "NA";
		write = '\n';
	}
}

import std.stdio : readln;
import std.conv : to;
import std.string : split, chomp;
import std.traits;
string[] input;
string delim = " ";
T next(T)()
in
{
	assert(hasNext());
}
out
{
	input.popFront;
}
body
{
	return input.front.to!T;
}

T next( T : char )()
in
{
	assert(hasNext());
}
out
{
	input.front.popFront;
}
body
{
	return input.front.front.to!T;
}



bool hasNext(){
	if(input.length > 0){
		if(input.front.length == 0){
			input.popFront;
			return hasNext;
		}
		return true;
	}
	
	string str = readln;
	if(str.length > 0){
		input ~= str.chomp.split(delim);
		return hasNext;
	}else{
		return false;
	}
}


void dbg(T...)(T vs)
{
	import std.stdio : stderr;
	foreach(v; vs)
		stderr.write(v.to!string ~ " ");
	stderr.write("\n");
}

T clone(T)(T v){
	T v_;
	static if(isInputRange!(T)){
		foreach(ite; v){
			v_ ~= ite.clone;
		}
	}else{
		v_ = v;
	}
	
	return v_;
}

Measured memory_bytes: 2056
#include<bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323846264338327950L

int main(){
	cout << setprecision(12) << fixed;
	long double a , b;
	cin >> a >> b;

	long double hour , minute;
	cin >> hour >> minute;

	long double temp= 2 * PI * ((hour/12) + ((minute/12)/60) - (minute/60));
	long double ans = (a*a) + (b*b) - (2*a*b*cos(temp));
	
	printf("%20.20Lf\n",sqrt(ans));
	return 0;
}



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

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0)

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }

    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

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

int main() {
    int n = ri();
	string s; cin >> s;
	map<char, int> ma;
	for (auto c : s) ma[c]++;
	s64 res = 1;
	for (auto i : ma) res *= (i.se + 1), res %= 1000000007;

	cout << res-1 << endl;
    return 0;
}


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

#define swap(i,j) { int tmp = i; i = j; j = tmp; }

int n;
vector<int> tree[100010];
int par[100010] = {};
int num[100010] = {};
int vid[100010];
int head[100010];
int team[100010];
int b = 0;


int setnum(int i){
  if(tree[i].size() == 0) return num[i] = 1;

  int ret = 0;
  for(int j = 0;j < tree[i].size();j++){
    ret += setnum(tree[i][j]);
  }

  return num[i] = ret;
}

void dis(int n){
  memset(team,-1,sizeof(team));
  int gnum = 0;
  int next;
  int pos = 0;
  for(int i = 0;i < n;i++){
    if(team[i] != -1) continue;
    team[i] = gnum;
    head[i] = i;
    vid[i] = pos;
    pos++;
    next = i;
    while(tree[next].size() != 0){
      int maxi = 0;
      for(int j = 1;j < tree[next].size();j++){
        if(num[tree[next][maxi]] < num[tree[next][j]]){
          maxi = j;
        }
      }
      team[tree[next][maxi]] = gnum;
      head[tree[next][maxi]] = i;
      vid[tree[next][maxi]] = pos;
      pos++;
      next = tree[next][maxi];
    }
    gnum++;
  }
  return;
}

void build(int n){
  setnum(0);
  dis(n);
  return;
}

int lca(int i, int j){
  while(1){
    if(vid[i] > vid[j]) swap(i, j);
    if(head[i] == head[j]) return i;
    j = par[head[j]];
  }
}

int main(){
  cin >> n;

  int k;
  int c;
  for(int i = 0;i < n;i++){
    cin >> k;
    for(int j = 0;j < k;j++){
      cin >> c;
      par[c] = i;
      tree[i].push_back(c);
    }
  }

  build(n);

  int q;
  cin >> q;
  int a, b;
  for(int i = 0;i < q;i++){
    cin >> a >> b;
    cout << lca(a, b) << endl;
  }

  return 0;
}



Measured memory_bytes: 15128
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s1 = input()
    s2 = input()

    if s1[0] == s2[2] and s1[1] == s2[1] and s1[2] == s2[0]:
        print('YES')
        return
    else:
        print('NO')
        return

solve()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pi pair<ll, ll>
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pd pair<double, double>
#define vp vector<pi>
#define f(i, n) for(int i = 0; i < n; i++)
#define fo(i, a, n) for(int i = a; i < n; i++)
#define mod (1000*1000*1000+7)
#define sz(x) int((x).size())
#define all(x) x.begin(),x.end()
#define DBG(v) cerr << #v << " = " << (v) << endl;
ll INF = (1ll<<61);

using namespace std;

ll grid[10][10];

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >>  n;
    ll ans = 0;
    fo(i, 1, n+1){
      string s = to_string(i);
      grid[s[0]-'0'][s.back()-'0']++;
    }
    f(i, 10){
      f(j, 10){
        ans += grid[i][j] * grid[j][i];
      }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
//written by NewbieChd
#include <cstdio>
using namespace std;

const int maxN = 100003, delta = 'a' - 'A';
char s[maxN];

int main() {
    int n, k;
    scanf("%d%d%s", &n, &k, s + 1);
    s[k] += delta, printf("%s", s + 1);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#include<deque>
#include <regex>
#include <list> 
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define _GLIBCXX_DEBUG
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef long long ll;
const ll MOD = 1000000007;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll getDigit(ll n) {
	ll cnt = 0;
	while (n != 0) {
		n /= 10;
		cnt++;
	}
	return cnt;
}
int main() {
	ll n;
	cin >> n;
	string s, t;
	cin >> s >> t;
	bool f = true;
	for (ll k = 0; k < n; k++) {
		f = true;
		for (ll i = 0; i < n-k; i++) {
			if (s[i+k] != t[i]) {
				f = false;
			}
		}
		if (f == true) {
			return cout << n + k << endl,0;
		}
	}
	cout << 2 * n << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define inRange(x,a,b) (a <= x && x < b)
int di[8] = {0,0,1,-1,1,1,-1,-1};
int dj[8] = {1,-1,0,0,1,-1,1,-1};

int main(){
    char mat[3][3];
    for(int i = 0; i < 3; i++)  for(int j = 0; j < 3; j++)  mat[i][j] = (char)('A'+i*3+j);
    string s;
    while(cin >> s){
        int ni, nj;
        for(int i = 0; i < 3; i++)  for(int j = 0; j < 3; j++) if(mat[i][j]==s[0])  ni = i, nj = j;
        bool valid = true;
        for(int i = 1; i < s.length(); i++){
            for(int k = 0; k < 4; k++){
                int nni = ni+di[k], nnj = nj+dj[k];
                if(inRange(nni, 0, 3) && inRange(nnj, 0, 3) && mat[nni][nnj]==s[i]){
                    ni = nni, nj = nnj;
                    break;
                }
                if(k == 3)  valid = false;
            }
        }
        if(valid)   cout << s << endl;
    }
    return 0;
}


Measured memory_bytes: 3152
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

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

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

int main()
{
    int n;
    cin >> n;
    
    pii ans(-1, -1);
    rep(i, n){
        pii t;
        cin >> t.second >> t.first;
        t.second *= -1;
        ans = max(ans, t);
    }
    
    cout << -ans.second << ' ' << ans.first << endl;
}

Measured memory_bytes: 1160
def is_palindromic(N):
    N_reversed=list(str(N))
    N_reversed.reverse()
    N_reversed=int(''.join(N_reversed))
    if N_reversed==N:
        return True
    else:
        return False
A,B=map(int,input().split())
count=0
for i in range(A,B+1):
    if is_palindromic(i):
        count+=1
print(count)

Measured memory_bytes: 9020
#include <bits/stdc++.h>
#define rep(mayo,nc) for(int (mayo)=0; (mayo)<(nc); i++)
using namespace std;

int main(){
    int n;
    double ans = 0.0, A;
    cin >> n;
    for(int i = 1; i<=n; ++i) {
        cin >> A;
        ans += 1.0/A;
    }
    ans = 1.0/ans;
    cout << setprecision(16) << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
int const MOD = 1000000007;
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
int madd(int a, int b) {return (a + b) % MOD;}
int msub(int a, int b) {return (a - b + MOD) % MOD;}
int mmul(int a, int b) {return (a * b) % MOD;}
int minv(int a) {return mod_pow(a, MOD-2);}
int mdiv(int a, int b) {return mmul(a, minv(b));}

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

int a[100010], sum[100010];
signed main() {
    int n; cin >> n;
    rep(i,0,n) {
        cin >> a[i];
        if(i != 0) sum[i] = sum[i-1] + a[i];
        else sum[i] = a[i];
    }

    // plus
    int diff = 0, cnt = 0;
    rep(i,0,n) {
        if(i % 2 == 0) {
            if(sum[i] + diff <= 0) {
                int t = 1 - (sum[i] + diff);
                cnt += t;
                diff += t;
            }
        }
        else if(i % 2 == 1) {
            if(sum[i] + diff >= 0) {
                int t = 1 + sum[i] + diff;
                cnt += t;
                diff -= t;
            }
        }
    }

    diff = 0; int cnt2 = 0;
    rep(i,0,n) {
        if(i % 2 == 0) {
            if(sum[i] + diff >= 0) {
                int t = 1 + sum[i] + diff;
                cnt2 += t;
                diff -= t;
            }
        }
        else if(i % 2 == 1) {
            if(sum[i] + diff <= 0) {
                int t = 1 - (sum[i] + diff);
                cnt2 += t;
                diff += t;
            }
        }
    }
    // printf("cnt = %lld, cnt2 = %lld\n", cnt, cnt2);
    cout << min(cnt, cnt2) << endl;
    return 0;
}

Measured memory_bytes: 1792
/*
  The Island Was Silent before.
  .....
  And One day again it became Silent.
*/
#include<bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ll  long long
#define modd(a,b) ((a+2*b)%b)
#define debug(a) cout << #a << ": " << (a) << "\n"
#define ioso ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rtt cerr << "Time: " << clock()*1.0 / CLOCKS_PER_SEC << endl;
#define ffe freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
 
int main() {
  ioso
  #ifndef ONLINE_JUDGE
  ffe
  #endif
  ll a; //long double a;
  
  cin >> a;
  //ll k = (b*100);
  string b; cin >> b;
  //cout << b << endl;
  ll k = ((b[0]-'0')*100 + (b[2]-'0')*10 + b[3]-'0');
  //cout << k << endl;
  ll ans = ((a)*k)/100;
  cout << ans << endl;
}

Measured memory_bytes: 3660
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import itertools

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
matrix = [[0] * N for _ in range(N)]

for i in range(M):
    a, b = i_l()
    matrix[a-1][b-1] = 1
    matrix[b-1][a-1] = 1

cnt = 0
for x in itertools.permutations(range(N)):
    if x[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= matrix[x[i]][x[i+1]]
    cnt += factor

print(cnt)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int   //used int to avoid mle
#define ulli unsigned long long int 
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(lli i=a;i<b;i++)
#define initialize(array,size,value) for(lli i=0;i<size;i++) array[i]=value
#define couta(array,size) for(lli i=0;i<size;i++) cout<<array[i]<<" "
#define vl vector<lli>
#define vp vector< pair <lli,lli> >
#define sl set<lli>
#define spl set<pll>
#define msl multiset <lli>
#define msp multiset <pll>
#define pll pair<lli, lli>
#define mll map<lli, lli>              //for( map<lli, lli>::iterator i=temp.begin();i!=temp.end();i++)cout<<i->fi<<" "<<i->se<<endl;
#define mvl map<lli, vl>
#define umll unordered_map<lli, lli>
#define vt vector<pair<lli, pll >  >
#define vf vector<pair<pll,pll > >
#define qu queue<lli>
#define pq priority_queue<lli>
#define dq deque <lli>
#define ptr vector<lli>::iterator
#define bs(array,x) binary_search(array.begin(),array.end(),x)
#define lb(array,x) lower_bound(array.begin(),array.end(),x)
#define ub(array,x) upper_bound(array.begin(),array.end(),x)
#define nobw(array,i,j) upper_bound(array.begin(), array.end(), j)-lower_bound(array.begin(), array.end(), i) //number of numbers between i & j
#define vc clear()
#define endl '\n'
#define sp system("pause");
#define INF 9223372036854775807
#define MINF -9223372036854775808
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
lli mod=1000000007;
//string s=bitset<32>(n).to_string();
vp inp[16];
lli n;
lli rec(lli i,vl tt){
	if(i==n+1){
		lli c=0;
		for(lli i=1;i<=n;i++)if(tt[i]==1)c++;
			return c;
	}

	if(tt[i]==0){
		return rec(i+1,tt);
	}
	if(tt[i]==1){
		for(auto cc:inp[i]){
			//if(i==cc.fi && cc.se==0)return INT_MIN;
			if(tt[cc.fi]==-1){
			if(cc.se==0)tt[cc.fi]=0;
			if(cc.se==1)tt[cc.fi]=1;
			}
			else{
				if(tt[cc.fi]==cc.se)continue;
				else return INT_MIN;
			}

		}
		return rec(i+1,tt);

	}
	vl ttt=tt;
	tt[i]=1;
	ttt[i]=0;
	for(auto cc:inp[i]){
			//if(i==cc.fi && cc.se==0)return INT_MIN;
			if(tt[cc.fi]==-1){
			if(cc.se==0)tt[cc.fi]=0;
			if(cc.se==1)tt[cc.fi]=1;
			}
			else{
				if(tt[cc.fi]==cc.se)continue;
				else return rec(i+1,ttt);
			}
		}
	return max(rec(i+1,ttt),rec(i+1,tt));
}
int main()
{
 	ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(lli i=1;i<=n;i++){
    	lli ai;
    	cin>>ai;
    	while(ai--){
    		lli x,y;
    		cin>>x>>y;
    		inp[i].pb(mp(x,y));
    	}
    }
    vl tt;
    for(lli i=0;i<=n;i++)tt.pb(-1);
    cout<<rec(1,tt);
	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 A = sc.nextInt();
    int B = sc.nextInt();

    for(int i = 1;;i++){
      int j = A*i;
      if(j == B){
        System.out.println(A+B);
        break;
      } 
      if(j>B) {
        System.out.println(B-A);
        break;
      }      
    }
  }
}


Measured memory_bytes: 23252
#include<iostream>
using namespace std;
int main()
{
    int x,y,z,temp;
    cin>>x>>y>>z;

    temp=x;
    x=y;
    y=temp;
    temp=x;
    x=z;
    z=temp;
    cout<<x<<" "<<y<<" "<<z<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
 
int main() {
    cout << fixed << setprecision(10);
    double a,b,h,m;
    cin >> a >> b >> h >> m;
    double kakudo=min(abs(h*30+m*0.5-6*m),360-abs(h*30+m*0.5-6*m));
    double ans_2=a*a+b*b-2*a*b*cos(3.14159265358979/180*kakudo);
    cout << sqrt(ans_2) << endl;

}


Measured memory_bytes: 4160
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
class Program
{
  static void Main(string[] args)
        {
           
            string sa = Console.ReadLine();
            string sb = Console.ReadLine();
            string sc = Console.ReadLine();
 
            int countA = 0;
            int countB = 0;
            int countC = 0;
 
            char answer = 'a';
            bool endFlg = false;
            string endAns = "A";
 
            while (!endFlg)
            {
                if (answer == 'a')
                {
                    if (countA >= sa.Count())
                    {
                        endFlg = true;
                        endAns = "A";
                      break;
                    }
                    answer = sa[countA];
                    countA++;
                }
                else if (answer == 'b')
                {
                    
                    
                    if (countB >= sb.Count())
                    {
                        endFlg = true;
                        endAns = "B";
                      break;
                    }
                    answer = sb[countB];
                    countB++;
                }
                else if (answer == 'c')
                {
                    if (countC >= sc.Count())
                    {
                        endFlg = true;
                        endAns = "C";
                      break;
                    }
                  
                    answer = sc[countC];
                    
                    countC++;
                }
            }
 
            Console.Write(endAns);
  }
}

Measured memory_bytes: 11220
import java.util.*

fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val P = readLine()!!.split(" ").map(String::toInt)

    var tree : TreeSet<Int> = TreeSet()
    var answer = 0

    for(i in 0..N-1){
        tree.add(P[i])
        if(P[i] <= tree.first())answer++
    }

    println(answer)
}

Measured memory_bytes: 82836
import math

# one = 1000000000000001
dict={1:"a",2:"b",3:"c",4:"d",5:"e",6:"f",7:"g",8:"h",9:"i",10:"j",
        11:"k",12:"l",13:"m",14:"n",15:"o",16:"p",17:"q",18:"r",19:"s",20:"t",
        21:"u",22:"v",23:"w",24:"x",25:"y",26:"z"}

n=int(input())
ans = ""

while n:
    ans = str(dict[(n-1)%26+1]) + ans
    n=(n-1)//26

print(ans)


Measured memory_bytes: 9068
# D
from bisect import bisect_right
A,B,Q = map(int, input().split())
INF = float('inf')
s = [-INF] + [int(input()) for _ in range(A)] + [INF]
t = [-INF] + [int(input()) for _ in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b,d = bisect_right(s, x), bisect_right(t, x)
    ans = INF
    for s_visit in [s[b-1], s[b]]:
        for t_visit in [t[d-1], t[d]]:
            dist1 = abs(s_visit - x) + abs(t_visit - s_visit)
            dist2 = abs(t_visit - x) + abs(s_visit - t_visit)
            ans = min(ans, dist1, dist2)
    print(ans)

Measured memory_bytes: 14204
#include<cstdio>
#include<iostream>
#include<queue>
#define endl '\n'
using namespace std;
struct read
{
    inline int get()
    {
        register int x=0,t=1;
        register char ch=getchar();
        while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
        if (ch=='-') {t=-1;ch=getchar();}
        while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
        return x*t;
    }
    inline char getch()
    {
        register char ch=getchar();
        while (!(('a'<=ch&&ch<='z')||('A'<=ch&&ch<='Z'))) ch=getchar();
        return ch;
    }
    inline operator int()
    {
        return get();
    }
    inline operator char()
    {
        return getch();
    }
    inline read operator>>(int &a)
    {
        a=get();
        return *this;
    }
    inline read operator>>(char &a)
    {
        a=getch();
        return *this;
    }
    inline read operator<<(int t)
    {
        printf("%d",t);
    }
    inline read operator<<(char t)
    {
        printf("%c",t);
    }
};
const int N=1e5+100;
int n,k;
deque<int> a,b;
int main()
{
    read cin,cout;
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        int x=cin;
        if(x<0)
            a.push_front(x);
        if(x>0)
            b.push_back(x);
        if(x==0) k--;
    }
    int ans=0x3fffffff;
    if(k<=0)
    {
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=k-1;++i)
    {
        if(i>a.size()||k-i>b.size()) continue;
        ans=min(ans,-2*a[i-1]+b[k-i-1]);
        ans=min(ans,-a[i-1]+2*b[k-i-1]);
    }
    if(k<=a.size()) ans=min(ans,-a[k-1]);
    if(k<=b.size()) ans=min(ans,b[k-1]);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
n, m, x = map(int, input().split())
a = list(map(int, input().split()))

c1 = 0
for i in a:
    if i < x:
        c1 += 1

c2 = 0
for i in a:
    if i > x:
        c2 += 1

print(min(c1, c2))

Measured memory_bytes: 3060
n, x = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
sum = 0
a.each_with_index do |m, i|
  sum += m
  if x < sum
    puts i
    break
  elsif x == sum
    puts i + 1
	break
  end
  if i == n - 1
    puts n - 1
  end
end

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

int main()
{
    int n;
    cin >> n;
    int h[n] = {};
    for(int i=0; i<n; i++) cin >> h[i];
    bool end = false;
    int ans = 0;
    while(!end){
        end = true;
        bool seq = false;
        for(int i=0; i<n; i++){
            if(h[i] != 0){
                seq = true;
                h[i] = h[i] -1;
                end = false;
            }else{
                if(seq) ans++;
                seq = false;
            }
        }
        if(seq) ans++;
        // cout << ans << endl;
    }
    
    cout << ans << endl;    
    return 0;
}

Measured memory_bytes: 256
// C.

#include <iostream>
#include <sstream>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <set>
#include <vector>

#ifdef __GNUC__
#define int128_t __int128
#else
typedef long long int128_t;
#endif

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
	LL n, c = 0, p;
	cin >> n;
	n -= 1;
	int128_t mx = n, r = n, z, next;
	p = 1;
	for (z = 1; ; z *= 26) {
		++c;
		next = z * 26;
		if (r < next) {
			break;
		}
		r -= next;
		p = z;
	}
	string ans;
	for (int i = 0; i < c; ++i) {
		char x = 'a';
		while (r >= z) {
			x += 1;
			r -= z;
		}
		ans += x;
		z /= 26;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3592
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdint>

template <typename IntType>
constexpr IntType ExtendedGCD(IntType a, IntType b, IntType& x, IntType& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  const auto c = ExtendedGCD(b, a % b, y, x);
  y -= a / b * x;
  return c;
}

int main() {
  std::int64_t N;
  std::cin >> N;
  std::vector<std::int64_t> factors;
  N *= 2;
  auto n = N;
  for (std::int64_t p = 2; p * p <= n; ++p) {
    if (n % p == 0) {
      factors.push_back(p);
      n /= p;
      while (n % p == 0) {
        n /= p;
        factors.back() *= p;
      }
    }
  }
  if (n > 1) {
    factors.push_back(n);
  }
  std::int64_t best_k = std::max<std::int64_t>(1, N / 2 - 1);
  const auto search = [&](auto f, std::size_t index, std::int64_t a) -> void {
    if (index == factors.size()) {
      const auto b = N / a;
      std::int64_t x, y;
      ExtendedGCD(a, b, x, y);
      y = -y;
      if ((a == 1 || x > 0) && (b == 1 || y > 0)) {
        best_k = std::min(best_k, b * y);
      }
    } else {
      f(f, index + 1, a);
      f(f, index + 1, a * factors[index]);
    }
  };
  search(search, 0, 1);
  std::cout << best_k << std::endl;
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define int ll


int n;

vector<pair<int,P> > v;

pair<int,P> p;

signed main(){

  cin>>n;
  rep(i,n){
    int x,y,h;
    cin>>x>>y>>h;
    if(h!=0){
      p=make_pair(h,P(x,y));
    }
    v.PB(make_pair(h,P(x,y)));
    
  }

  for(int i=0;i<101;i++){
    for(int j=0;j<101;j++){
      int h = p.F+abs(p.S.F-i)+abs(p.S.S-j);
      bool flag = true;
      rep(k,n){
        if(v[k].F!=max((int)0,h-abs(v[k].S.F-i)-abs(v[k].S.S-j)))
          flag=false;
      }
      if(flag){
        cout<<i<<' '<<j<<' '<<h<<endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 256
/// Geometry INT

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int sign(const LL x) {
	if (x < 0) {
		return -1;
	}
	if (x > 0) {
		return 1;
	}
	return 0;
}

struct point {
	LL x, y;
	point() {}
	point(LL _x, LL _y) : x(_x), y(_y) {}
};

void normalize(point &P) {
	assert(P.x != 0 || P.y != 0);
	LL g = __gcd(P.x, P.y);
	P.x /= g;
	P.y /= g;
}

point operator + (const point &P, const point &Q) {
	return point(P.x + Q.x, P.y + Q.y);
}

point operator - (const point &P, const point &Q) {
	return point (P.x - Q.x, P.y - Q.y);
}

point operator * (const point &P, const LL k) {
	return point(P.x * k, P.y * k);
}

point operator / (const point &P, const LL k) {
	assert(k != 0 && P.x % k == 0 && P.y % k == 0);
	return point(P.x / k, P.y / k);
}

inline LL dot(const point &P, const point &Q) {
	return P.x * Q.x + P.y * Q.y;
}

inline LL cross(const point &P, const point &Q) {
	return P.x * Q.y - P.y * Q.x;
}

inline bool is_in(LL x, LL a, LL b) {
	if (a > b) {
		swap(a, b);
	}
	return (a <= x && x <= b);
}

inline bool is_in(const point &P, const point &A, const point &B) {
	if (cross(B - A, P - A) != 0) {
		return false;
	}
	return (is_in(P.x, A.x, B.x) && is_in(P.y, A.y, B.y));
}

inline bool segment_segment_intersect(const point &A, const point &B, const point &C, const point &D) {
	if (cross(B - A, D - C) == 0) { // lines are parallel
		return (is_in(A, C, D) || is_in(B, C, D) || is_in(C, A, B) || is_in(D, A, B));
	}
	if (sign(cross(C - A, B - A)) * sign(cross(D - A, B - A)) > 0) {
		return false;
	}
	if (sign(cross(A - C, D - C)) * sign(cross(B - C, D - C)) > 0) {
		return false;
	}
	return true;
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B
void test_segment_segment_intersection() {
	int q;
	cin >> q;
	while (q--) {
		point A, B, C, D;
		cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;
		cout << (segment_segment_intersect(A, B, C, D) ? "1" : "0") << "\n";
	}
}

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

	test_segment_segment_intersection();
}

Measured memory_bytes: 3164
#include <stdio.h>
#include <math.h>

int main(void)
{

	int D;
	int N;

	scanf("%d %d\n",&D,&N);

	float P;
	
	if (N != 100) P = pow(100,D) * N;
	else P = pow(100,D) * (N+1);
	
	printf("%.0f\n",P);

	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include<string>
#include<cmath>
#include<ciso646>
#include<cstring>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;


int main()
{
	int n, m;
	cin >> n >> m;
	vector<ll> h(n);
	rep(i, n) cin >> h[i];
	vector<bool> aa(n);
	rep(i, n) aa[i] = true;
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		if (h[a - 1] < h[b - 1])
			aa[a - 1] = false;
		else if(h[a-1]>h[b-1])
			aa[b-1] = false;
		else {
			aa[a - 1] = false;
			aa[b - 1] = false;
		}
	}
	int ans = 0;
	rep(i, n) {
		if (aa[i]) ans++;
	}
	cout << ans;

}

Measured memory_bytes: 4028
#include<stdio.h>
#include<stdlib.h>
#define BUFSIZE 10000000
int N,M,rem1;
int rem[BUFSIZE]={0};
int rem2[BUFSIZE]={0};
int main(void){
	scanf("%d",&N);

	for(int i=0;i < N-1 ;i++){
		scanf("%d",&rem[i]);
		rem2[rem[i]]++;
	}
	for(int i=1;i<=N;i++){
		printf("%d\n",rem2[i]);
		
	}


}

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

int main() {
	int N, M;
	int K[30];
	int A[30][30];
	int like[30];
	int ans = 0;

	for (int i = 0; i < 30; i++) {
		like[i] =0;
		for (int j = 0; j < 30; j++) {
			//A[i][j] = false;
		}
	}
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >>K[i];
		for (int j = 0; j < K[i]; j++) {
			cin >> A[i][j];
			A[i][j]--;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K[i]; j++) {
			like[A[i][j]]++;
		}
	}
	
	for (int i = 0; i < M; i++) {
		//printf("like[%d]=%d\n",i, like[i]);
		if (like[i] == N) {
			ans++;
		}
	}

	printf("%d", ans);
}

Measured memory_bytes: 256
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    n, m = map(int, input().split())

    a = [int(x) for x in input().split()]

    q = [tuple(map(int, input().split())) for _ in range(m)]
    q.sort(key=lambda x: x[1], reverse=True)

    r = [0] * n
    i, j = 0, 0
    while i < n and j < m:
        b, c = q[j]
        for _ in range(b):
            r[i] = c
            i += 1
            if i == n:
                break
        j += 1

    a += r
    a.sort(reverse=True)
    del a[n:]
    print(sum(a))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


Measured memory_bytes: 58876