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

int main() {
  string A="1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51";
  int K=0;
  cin >> K;
  int count =0;
  if (K ==1){
    cout << "1" << endl;
  }else{
  for(int i=0; i<A.size()-1; i++){
    if(count==K-1){
      cout << A.at(i+1);
      if(A.at(i+2)!=','){
        cout << A.at(i+2);
      }
      cout << "" << endl;
      break;
    }
    if(A.at(i)==','){
      count++;
    }
  }
  }
  
  
}


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

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10, MOD = 1e9 + 7;
ll pos[maxn],fac[maxn],facm[maxn];

ll quick_pow(ll a,ll n,ll p)
{
    ll x = a;
    ll res = 1;
    while(n)
    {
        if(n & 1)
        {
            res = ((ll)res * (ll)x) % p;
        }
        n >>= 1;
        x = ((ll)x*(ll)x) % p;
    }
    return res;
}

ll C(ll n,ll k){
    if(k > n) return 0ll;
    ll ans = fac[k]*fac[n-k]%MOD;
    ans = (fac[n]*quick_pow(ans,MOD-2ll,MOD))%MOD;
    return ans;
}

int main()
{
    fac[0] = 1;
    for(int i = 1;i < maxn;i++)
        fac[i] = (fac[i-1]*i)%MOD;
	ll n;
	scanf("%lld", &n);
	n++;
	ll m, x;
	for(int i = 1;i <= n;i++)
	{
		scanf("%lld", &x);
		if (pos[x])
		{
			m = n - (i - pos[x] + 1);
			break;
		}
		pos[x] = i;
	}
	for(int i = 1;i <= n;i++)
		printf("%lld\n", (C(n, i) - C(m, i-1)+MOD) % MOD);
	return 0;
}


Measured memory_bytes: 2816
#include <stdio.h>
#include <string.h>

int main(void)
{
  char str[8];
  
  scanf("%s\n",str);
  
  if(strcmp(str,"AAA")== 0){
    printf("No");
  }else if(strcmp(str,"BBB")==0){
    printf("No");
  }else{
    printf("Yes");
  }
}

Measured memory_bytes: 128
// Problem : 
// 			B - Trained?
// 			Editorial
// 		
// Contest : AtCoder - AtCoder Beginner Contest 065
// URL : https://atcoder.jp/contests/abc065/tasks/abc065_b
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(i,n)         for(int i=0;i<n;i++)
#define Fo(i,k,n)       for(int i=k;i<n;i++) 
#define endl            "\n"
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define vec(x)          vector<x>
#define matrix(x)       vector<vector<x>>
#define sz(x)             (int)x.size()
#define mem(a,b)        memset(a, b, sizeof a)
#define vii             vector<pair<int,int>>
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define gcd(a,b)        __gcd(a,b)
#define lcm(a,b)        (a*(b/gcd(a,b)))
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define MOD             998244353
#define deb(x)          cerr <<#x<<" = "<<x<<"\n"
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(v)          v.begin(),v.end()
#define rep(i,a,b)      for (int i = a; i<b; ++i)
#define len(s)          s.length()
#define watch(x)         cout << #x << " = " << x << endl
#define trace(x)         cerr << #x << " = " << x << endl
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
int power(int a,int b,int m=mod)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}

void angshuGod()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

const int N = 1e5+1;
const double pi = acos(-1);

void solve(){
    
	int n; cin>>n;
	vi v(n+1); 
	rep(i,1,n+1) cin>>v[i];
	bool visited[n+1] = {false};
	int curr = 1;
	bool flag = false;
	int cnt = 0;
	while(true){
		cnt++;
		visited[curr] = true;
		int val = v[curr];
		if(val == 2){
			flag = true;
			break;
		}
		if(visited[val]){
			flag = false;
			break;
		}
		curr = val;
	}
	if(flag) cout<<cnt;
	else cout<<-1;
}

 
int32_t main()
{
    angshuGod();

    int t;

    t = 1;
    //cin>>t;

    while(t--){
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 4300
#include<iostream>
#include<string>
#include<cmath>
#include<iomanip>
using namespace std;

int main(){
    double shi, fen,s,f,js,jf,c;
    while(cin>>shi>>fen>>s>>f){
        jf = 360 * f / 60;
        js = 30 * s + 30 * f / 60;
        c = abs(jf - js);
        if(c>180)
            c = 360 - c;
        cout <<fixed<<setprecision(20)<< sqrt(shi * shi + fen * fen - 2 * shi * fen * cos(c / 180 *3.141592653589793238462643383279)) << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
n = int(input())
A = [int(input()) for i in range(n)]

ng = 0
if A[0] != 0:
    ng = 1
ans = 0
for i in range(1, n):
    if A[i] > A[i-1] and A[i] - A[i-1] > 1:
        ng = 1
        break
    elif A[i] <= A[i-1]:
        ans += A[i]
    else:
        ans += 1

if ng == 0:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 61656
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rrep(i, n) for(ll i = n - 1; i > -1; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
const ll INF = 1LL << 62;
const ll MOD = 1000000007 /*988244353*/;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, h, x, y, z, p, q, m, n, t, r, k, w, l, ans, i, j;
string S, T;
vl A1, B1, C1, A2, B2, C2;
vector<PP> VP;
void solve() {
    while(q--) {
        map<ll, ll> M;
        cin >> n >> a >> b >> c >> d;
        ans = INF;
if(n==1){
cout<<d<<endl;
continue;
}
        t = n + 1;
        M[n] = 0;
        while(t > 0) {
            auto ite = M.lower_bound(t);
            ite--;
            t = (*ite).fi;
            // cout << t << endl;
            if(M[t / 2] > 0)
                M[t / 2] = min(M[t / 2], M[t] + a + (t % 2) * d);
            else
                M[t / 2] = M[t] + a + (t % 2) * d;
            if(M[(t + 1) / 2] > 0)
                M[(t + 1) / 2] = min(M[(t + 1) / 2], M[t] + a + (1 - ((t + 1) % 2)) * d);
            else
                M[(t + 1) / 2] = M[t] + a + (1 - ((t + 1) % 2)) * d;
            if(M[t / 3] > 0)
                M[t / 3] = min(M[t / 3], M[t] + b + (t % 3) * d);
            else
                M[t / 3] = M[t] + b + (t % 3) * d;
            if(M[(t + 2) / 3] > 0)
                M[(t + 2) / 3] = min(M[(t + 2) / 3], M[t] + b + (2 - ((t + 2) % 3)) * d);
            else
                M[(t + 2) / 3] = M[t] + b + (2 - ((t + 2) % 3)) * d;
            if(M[t / 5] > 0)
                M[t / 5] = min(M[t / 5], M[t] + c + (t % 5) * d);
            else
                M[t / 5] = M[t] + c + (t % 5) * d;
            if(M[(t + 4) / 5] > 0)
                M[(t + 4) / 5] = min(M[(t + 4) / 5], M[t] + c + (4 - ((t + 4) % 5)) * d);
            else
                M[(t + 4) / 5] = M[t] + c + (4 - ((t + 4) % 5)) * d;
            // cout << t << " " << M[t] << endl;
            if(t < (INF - M[t]) / d)
                ans = min(ans, M[t] + t * d);
        }

        cout << ans << endl;
    }
}
int main() {
    // cout<<fixed<<setprecision(15);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> q;
    solve();
}


Measured memory_bytes: 4332
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int x,a,b,c,bestby;
    cin>>x>>a>>b;
    if (b<=a){cout<<"delicious";return 0;}
    if (b>a){
        c = b - a;
        if(c > x){
            cout<<"dangerous";return 0;
        }
        else {
            cout<<"safe";
            return 0;
        }
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi
#define int long long

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline LL gl()
{
	LL f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int N=2e5+5;
const int mod=998244353;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};

int n,k,a[N];
int f(int mid)
{
	int ret=0;
	for (int i=0;i<n;i++)
  	{
		if (a[i]==0)
    	{
			if (mid>=0)
          ret+=n-1;
			continue;
		}
		if (a[i]<0)
    	{
			int target=mid/a[i];
			if (target*a[i]>mid)
          target++;
			int idx=lower_bound(a,a+n,target)-a;
			ret+=n-idx;
			if (idx<=i)
          ret-=1;
		}
		else
      	{
			int target=mid/a[i];
			if (target*a[i]>mid)
          target--;
			int idx=upper_bound(a,a+n,target)-a-1;
			if (idx<0)
          continue;
			ret+=idx+1;
			if (idx>=i)
          ret-=1;
		}
	}
	return ret/2;
}

signed main()
{
	cin>>n>>k;
	for (int i=0;i<n;i++)
      cin>>a[i];
	sort(a,a+n);
	int lo=-1e18,hi=1e18;
	while (lo<hi)
  	{
		int mid=lo+(hi-lo)/2;
		if (f(mid)>=k)
        hi=mid;
		else
        lo=mid+1;
	}
	cout<<lo<<endl;
	return 0;
}


Measured memory_bytes: 1792
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n = int(input())
    s = set()
    for _ in range(n):
        x = input()
        s.add(x)
    print(len(s))
if __name__ == '__main__':
    main()


Measured memory_bytes: 31064
#include<bits/stdc++.h>
#define pi 3.1415926535897932384626
using namespace std;
      
struct P{
  int x, y;
  bool operator < (const P &a )const{
    //if(x!=a.x)
    return y<a.y;
  };
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
int o[3101];
int l[441];
int j[441];

long long x,y,z,mod=1000000007;
//string r;
char r[3111];

P u[1];
priority_queue<int> q;
stack<int> s;
//set<P> s;
map<int,int> p;

vector<int> v;

bool as(P a,P b)
{
  //if(a.x!=b.x)
  //return a.x<b.x;
  return a.x<b.x;
}

int main()
{
  scanf("%d",&a);
  for(int t=1;t<=a;t++)
  scanf("%d",&o[t]);
  k=mod;
  for(int i=-100;i<=100;i++)
  {
    n=0;
    for(int t=1;t<=a;t++)
      n+=(o[t]-i)*(o[t]-i);
    k=min(k,n);
  }
  printf("%d",k);
}
//0
//16



Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = 2;
        int c = 2;
        if(a == 1){
            c = 1;
        }
        while(b<a){
            b *= 2;
            if(b<=a){
                c = b;
            }
        }
        System.out.println(c);
    }
}

Measured memory_bytes: 22736
def root(x,d):
    if d[x]!=x:
        d[x]=root(d[x],d)
    return d[x]
def unite(x,y,h):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        h[x]=min(x,y)
        h[y]=h[x]
from collections import defaultdict
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b)
d=defaultdict(int)
l=""
for i in range(1,n+1):
    d[(root(a[i],a),root(b[i],b))]+=1
for i in range(1,n+1):
    l+=str(d[(root(a[i],a),root(b[i],b))])+" "
print(l[:-1])

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

int main() {
  int n;
  cin >> n;
  long long lucas[n + 1];
  lucas[0] = 2;
  lucas[1] = 1;
  int i;
  for (i = 2; i < n + 1; i++) {
    lucas[i] = lucas[i - 1] + lucas[i - 2];
  }
  cout << lucas[n] << endl;
  return 0;
}


Measured memory_bytes: 256
# 初期入力　　２０２０－０７２７　21：50
import math
import sys
input = sys.stdin.readline  #文字列では使わない
N = int(input())
ans =":("
for i in range(1,50001):
    a =int( i *1.08 )
    if a==N:
        ans =i
        break
print(ans)

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n,m;
vector<P> res;
vector<ll> g[100010];
bool vis[100010];

ll dfs(ll v,ll pre){
  vis[v]=true;
  ll crtsgn=0;
  for(ll nv : g[v]){ // back
    if(nv==pre)continue;
    if(vis[nv]){
      crtsgn=1-crtsgn;
      res.push_back(P(v,nv));
    }
  }
  for(ll nv : g[v]){
    if(vis[nv])continue;
    ll sgn=dfs(nv,v);
    if(sgn==0){
      crtsgn=1-crtsgn;
      res.push_back(P(v,nv));
    }else{
      res.push_back(P(nv,v));
    }
  }
  return crtsgn;
}

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

  cin>>n>>m;
  rep(i,m){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  if(m%2==1){
    cout<<-1<<endl;
    return 0;
  }

  dfs(0,-1);

  rep(i,m){
    cout<<res[i].fi+1<<" "<<res[i].se+1<<endl;
  }

  return 0;
}


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

ll f(ll h){
  if(h==1)return 1;
  return f(h/2)*2+1;
}

int main() {
  ll h;cin>>h;
  cout<<f(h)<<endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int a,b,c,d,g,k,m,n,j,ans;
	cin >> a >> b >> c >> d;
	g = (c*d)/__gcd(c,d);
	k = b/g-(a-1)/g;
	m = b/c-(a-1)/c;
	n = b/d-(a-1)/d;
	j=m+n-k;
	ans = b-a+1-j;
	cout << ans;
	return 0;
}

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

string s;
int a, z;

int main(void){
  cin >> s;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == 'A'){
      a = i;
      break;
    }
  }
  for(int i = s.size() - 1; i >= 0; i--){
    if(s[i] == 'Z'){
      z = i;
      break;
    }
  }

  cout << z- a + 1 << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repr(i, s, e) for(int i=s; i>=e; i--)
#define reps(i, s, e) for(int i=s; i<=e; i++)
#define inf 1e18
#define all(v) v.begin(),v.end()
#define vsort(v) sort(v.begin(), v.end())
#define vsortr(v) sort(v.begin(), v.end(), greater<ll>())
#define sz(x) x.size()
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
#define enl << endl
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T &a, T b){ if(a<b){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a){ a=b; return true; } return false; }
template<typename T> T gcd(T a, T b){ if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b){ return a*b/gcd(a, b); }
template<typename T> void vdebug(vector<T> v){ for(auto vv : v){ cout << vv << " "; } cout << endl; }
template<typename T> void adebug(T arr[], int n){ rep(i, n){ cout << arr[i] << " "; } cout << endl; }
void ans(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; }
void ans2(bool b){ if(b) cout << "YES" << endl; else cout << "NO" << endl; }
int keta(ll num){ int k=0; while(num>0){ num/=10; k++; } return k; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};


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

    ll a, b, c;
    cin >> a >> b >> c;

    if(a + b + 1 >= c){
        cout << c + b << endl;
    }else{
        cout << b + (a+b+1) << endl;
    }

    return 0;
}


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

const int MAX = 1 << 17;

struct seg_node {
	int cnt;
	seg_node *lch, *rch;
	seg_node(int c, seg_node *l, seg_node *r) : cnt(c), lch(l), rch(r) {}
};

seg_node* fix(seg_node *x) {
	return x ? new seg_node(x->cnt + 1, x->lch, x->rch) : new seg_node(1, nullptr, nullptr);
}

seg_node* insert(seg_node *x, int p, int lb = 0, int ub = MAX) {
	x = fix(x);
	if (ub - lb == 1) return x;
	int c = (lb + ub) / 2;
	if (p < c) {
		x->lch = insert(x->lch, p, lb, c);
	}
	else {
		x->rch = insert(x->rch, p, c, ub);
	}
	return x;
}

int get_lca(int u, int v, const vector<vector<int>>& par, const vector<int>& d) {
	if (d[u] < d[v]) swap(u, v);
	int x = 0, dis = d[u] - d[v];
	while (dis) {
		if (dis & 1) {
			u = par[x][u];
		}
		dis >>= 1;
		x++;
	}
	assert(d[u] == d[v]);
	if (u == v) return u;
	for (int i = 16; i >= 0; i--) {
		if (par[i][u] != par[i][v]) {
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][u];
}

void dfs(int v, int prev, const graph& G, vector<int>& p, vector<int>& d, vector<seg_node*>& rts, const vector<int>& x) {
	p[v] = prev;
	d[v] = (prev != -1 ? d[prev] + 1 : 0);
	rts[v] = insert(prev != -1 ? rts[prev] : nullptr, x[v]);
	for (auto to : G[v]) if (to != prev) {
		dfs(to, v, G, p, d, rts, x);
	}
}

vector<int> compress(vector<int>& v) {
	auto res = v;
	sort(res.begin(), res.end());
	res.erase(unique(res.begin(), res.end()), res.end());
	for (auto& val : v) {
		val = lower_bound(res.begin(), res.end(), val) - res.begin();
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	vector<int> x(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i];
	}
	auto xs = compress(x);
	graph G(N);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b; a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<vector<int>> par(17, vector<int>(N));
	vector<int> d(N);
	vector<seg_node*> rts(N);
	dfs(0, -1, G, par[0], d, rts, x);
	for (int i = 1; i < 17; i++) {
		for (int j = 0; j < N; j++) {
			par[i][j] = par[i - 1][j] != -1 ? par[i - 1][par[i - 1][j]] : -1;
		}
	}
	while (Q--) {
		int v, w, l;
		cin >> v >> w >> l; v--, w--, l--;
		int lca = get_lca(v, w, par, d), plca = par[0][lca];
		vector<seg_node*> ss = { rts[v], rts[w], rts[lca], (plca != -1 ? rts[plca] : nullptr) };
		int res = 0;
		for (int i = 0; i < 17; i++) {
			int cnt = 0;
			for (int j = 0; j < 4; j++) {
				if (j < 2) {
					cnt += (ss[j] && ss[j]->lch ? ss[j]->lch->cnt : 0);
				}
				else {
					cnt -= (ss[j] && ss[j]->lch ? ss[j]->lch->cnt : 0);
				}
			}
			if (l < cnt) {
				for (int j = 0; j < 4; j++) {
					if (ss[j]) ss[j] = ss[j]->lch;
				}
			}
			else {
				l -= cnt;
				res += 1 << (16 - i);
				for (int j = 0; j < 4; j++) {
					if (ss[j]) ss[j] = ss[j]->rch;
				}
			}
		}
		printf("%d\n", xs[res]);
	}
	return 0;
}



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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	int h,w;
	vector<string> a;

	cin >> h >> w;
	a.resize(h+1);
	for(int i = 0; i < h; i++)
		cin >> a[i];

	bool check = true;
	for(int i = 0; i < h; i++){
		bool go = false;
		for(int j = 0; j < w; j++){
			if(!go && a[i][j] == '.' && a[i+1][j] == '#')
				check = false;
			if(go && a[i][j] == '#' && a[i+1][j] == '.')
				check = false;
			if(a[i][j] == '#' && a[i+1][j] == '#')
				if(go)
					check = false;
				else
					go = true;
		}
	}

	if(check)
		cout << "Possible" << endl;
	else
		cout << "Impossible" << endl;

	return 0;
}

Measured memory_bytes: 256
#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 n; cin >> n;
    vector<vector<pair<int,ll>>> g(n+1);
    for(int i=0; i<n-1; i++){
        int x, y;
        ll z; cin >> x >> y >> z;
        g.at(x).push_back(make_pair(y, z));
        g.at(y).push_back(make_pair(x, z));
    }

    vector<int> dist(n+1, -1);
    queue<int> q;
    dist.at(1)=1;
    q.push(1);

    while(!q.empty()){
        int v=q.front();
        q.pop();

        for(auto i:g.at(v)){
            if(dist.at(i.first)!=-1) continue;

            if(i.second%2==0){
                dist.at(i.first) = dist.at(v);
                q.push(i.first);
            }
            else{
                dist.at(i.first) = (dist.at(v)+1)%2;
                q.push(i.first);
            }
        }
    }

    rep(i, n) cout << dist.at(i+1) << endl;

}

Measured memory_bytes: 8320
k,n = gets.split(/ /).map(&:to_i)
a = gets.split(/ /).map(&:to_i)

longest = k - a.last + a.first

1.upto(a.length - 1) do |i|
  tmp = a[i] - a[i - 1]
  longest = tmp if tmp > longest
end

puts k - longest


Measured memory_bytes: 15364
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,n;
int main()
{
    cin>>a>>b>>c;
    if(b>=a)
    {
        cout<<1<<endl;
        return 0;
    }
    if(c>=b)
    {
        cout<<-1<<endl;
        return 0;
        
    }
    if((a-b)%(b-c)>=1) 
        n=1;
    cout<<((a-b)/(b-c)+n)*2+1<<endl;
    return 0;
}

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

const int m=200000001;
int main(){
  int n;
  cin >> n;
  vector<P> a;
  rep(i,n){
    int x,y;
    cin >> x >> y;
    a.push_back(make_pair(x-y,x+y));
  }
  sort(a.begin(),a.end());
  //rep(i,n) cout << a[i].first << ' ' << a[i].second << "\n";
  int l=0,ans=n;
  while(l<n){
    int jump=1;
    for(int r=l+1;r<n;r++){
      //cout << l << ' ' << r << "\n";
      if(a[l].second>a[r].first){
        ans--;
        if(a[l].second<=a[r].second){
          jump++;
          continue;
        }else{
          break;
        }
      }else{break;}
    }
    l+=jump;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 4320
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K;
  cin >> N >> K;
  
  int x = 1;
  
  for (int i = 0; i < N; i++) { // iのスコープはforの終わりまで

    if( x * 2 <= x + K ){
      x *= 2;
      
    }
    
    else {
      x += K;
      
    }
  }
  
  cout << x <<endl;
}

Measured memory_bytes: 3672
import java.util.*;

public class Main {

    static int ans = 0;

    private static void rec(int[] a) {

        boolean eNumExist = false;
        int index = -1;
        int max = 0;

        for (int i = 0; i < a.length; i++) {

            if (a[i] % 2 == 0) {
                eNumExist = true;
                a[i] = a[i]/2;
                break;
            }
        }

        if (eNumExist)
        {
            ans++;
            rec(a);

        }else{

            return;
        }
    }


    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int N = Integer.parseInt(scan.next());
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(scan.next());
        }

        rec(a);

        System.out.println(ans);
    }
}

Measured memory_bytes: 40280
#include<cstdio>
using namespace std;
int a[10000001],b[10000000],c[10000000];
int main()
{
	int n,i,j;
	scanf("%d",&n);
	for(i=0;i<10000;i++)
	{
		c[i]=0;
	}
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i+1]);
		c[a[i+1]]++;
	}
	for(i=1;i<=10000;i++)
	{
		c[i]=c[i]+c[i-1];
	}
	for(j=1;j<=n;j++)
	{
		b[c[a[j]]]=a[j];
		c[a[j]]--;
	}
	for(i=1;i<=n;i++)
	{
		if(i>1) printf(" ");
		printf("%d",b[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 18388
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
long double const pi = std::acos(-1.0L);
typedef pair<int,int> P;
const int INF = 1001001001;


int main() {
  string s;
  cin >> s;
  if(s[s.size()-1] == 's') cout << s << "es" << endl;
  else cout << s << "s" << endl;
  return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main()
{
	int i,j,c,s,n;
	while(scanf("%d",&n),n)
	{
		for(s=0,i=2;i<=n;++i)
		{
			for(c=0,j=1;j<=i;++j)c+=j;
			for(;;)
			{
				if(c>=n)
				{
					if(c==n)++s;
					break;
				}
				c+=i;
			}
		}
		printf("%d\n",s);
	}
	return 0;
}

Measured memory_bytes: 0
nums = [int(_) for _ in input().split()]
nums.sort()
ans = 0

dif = nums[2] - nums[1]
ans += dif
nums[0] += dif
nums[1] += dif
dif = nums[2] - nums[0]
if dif % 2 == 0:
    ans += dif // 2
    print(ans)
else:
    ans += dif // 2 + 2
    print(ans)

Measured memory_bytes: 3064
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int64_t, int64_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  string X;
  cin >> X;
  const int64_t L = static_cast<int64_t>(X.length());
  stack<char> st;
  for (int64_t i = 0; i < L; ++i) {
    const char ch = X.c_str()[i];
    if (ch == 'S') {
      st.emplace(ch);
    } else {
      if (st.empty()) {
        st.emplace(ch);
      } else if (st.top() == 'S') {
        st.pop();
      } else {
        st.emplace(ch);
      }
    }
  }
  cout << st.size() << endl;
  return 0;
}


Measured memory_bytes: 3712
# ABC 124: B – Great Ocean View
n = int(input())
h = [int(s) for s in input().split()]

number_inns_can_see_ocean = 0
highest = h[0]

for height_of_inn in h:
    if height_of_inn >= highest:
        number_inns_can_see_ocean += 1
        highest = height_of_inn

print(number_inns_can_see_ocean)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

ll mod_pow(ll x,ll n,ll MD){
  x%=MD;
  ll res=1;
  while(n>0){
    if(n&1) res=res*x%MD;
    x=x*x%MD;
    n>>=1;
  }
  return res;
}

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

  int N;
  cin>>N;
  string S;
  cin>>S;

  vector<int> dp(N+1,0);
  for(int i=1;i<=N;i++){
    int p=__builtin_popcount(i);
    dp[i]=dp[i%p]+1;
  }

  int one=0;
  rep(i,N) if(S[i]=='1') one++;
  int up=0,dw=0;
  if(one!=N){
    rep(i,N){
      if(S[i]=='0') continue;
      up+=mod_pow(2,N-1-i,one+1);
      up%=(one+1);
    }
  }
  if(one!=0&&one-1!=0){
    rep(i,N){
      if(S[i]=='0') continue;
      dw+=mod_pow(2,N-1-i,one-1);
      dw%=(one-1);
    }
  }

  for(int i=0;i<N;i++){
    if(S[i]=='1'){
      if(one-1==0){
        cout<<0<<"\n";
        continue;
      }
      ll res=mod_pow(2,N-i-1,one-1);
      ll ans=dp[(dw-res+(one-1))%(one-1)]+1;
      cout<<ans<<"\n";
    }else{
      ll res=mod_pow(2,N-i-1,one+1);
      ll ans=dp[(up+res+(one+1))%(one+1)]+1;
      cout<<ans<<"\n";
    }
  }

  return 0;
}


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

int partition(pair<int, char> a[], int p, int r)
{
    int x = a[r].first;
    int i = p - 1;

    for(int j = p; j < r; j++) {
        if (a[j].first <= x) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r]);

    return i + 1;
}

void quicksort(pair<int, char> a[], int p, int r)
{
    if (p < r){
        int q = partition(a, p, r);
        quicksort(a, p, q - 1);
        quicksort(a, q + 1, r);
    }
}

bool comp(pair<int, char> a, pair<int, char> b)
{
    return a.first < b.first;
}

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

    pair<int, char> a[n], b[n];
    for(int i = 0; i < n; i++) cin >> a[i].second >> a[i].first, b[i] = a[i];

    quicksort(a, 0, n - 1);

    stable_sort(b, b + n, comp);

    bool f = true;
    for(int i = 0; i < n; i++) {
        // cerr << b[i].second << " " << b[i].first << " " << a[i].second << " " << a[i].first << endl;
        if(b[i] != a[i]) f = false;
    }
    cout << (f ? "Stable" : "Not stable") << endl;
    for(int i = 0; i < n; i++) {
        cout << a[i].second << " " << a[i].first << endl;
    }

    return 0;
}



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

int min_of_common(int a0, int a1, int b0, int b1) {
  if (a0 > a1 || b0 > b1) return -1;
  if (a0 >= b0 && a0 <= b1) return a0;
  if (b0 >= a0 && b0 <= a1) return b0;
  return -1;
}

int modify(int current, int target, double tax) {
  while ((int)(current * tax) < target) current++;
  while ((int)(current * tax) > target) current--;
  return current;
}

int main() {
  int A, B;
  const double tax_a = 0.08, tax_b = 0.1;
  scanf("%d %d", &A, &B);
  const double 
    A0 = (double)A / tax_a,
    A1 = (double)(A + 1) / tax_a,
    B0 = (double)B / tax_b,
    B1 = (double)(B + 1) / tax_b;
  const int
    iA0 = modify(ceil(A0), A, tax_a),
    iA1 = modify(ceil(A1), A, tax_a),
    iB0 = modify(ceil(B0), B, tax_b),
    iB1 = modify(ceil(B1), B, tax_b);
  printf("%d\n", min_of_common(iA0, iA1, iB0, iB1));
  return 0;
}


Measured memory_bytes: 128
//
// Created by tac on 2016/10/16.
//

#include <algorithm>
#include <cstdlib>
#include <string>
#include <iostream>

namespace {

void print(const std::string &str,
           std::string::size_type a,
           std::string::size_type b) {
    std::cout << str.substr(a, b - a + 1) << std::endl;
    return;
}

const std::string reverse(const std::string &str,
                          std::string::size_type a,
                          std::string::size_type b) {
    std::string ret = str;
    std::reverse(ret.begin() + a, ret.begin() + b + 1);
    return ret;
}

const std::string replace(const std::string &str,
                          std::string::size_type a,
                          std::string::size_type b,
                          const std::string &rep) {
    std::string ret = str;
    ret.replace(ret.begin() + a, ret.begin() + (b + 1), rep);
    return ret;
}

}

int main() {
    std::string str;
    int n;
    std::string op, rep;
    int a, b;
    std::cin >> str;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> op;
        std::cin >> a >> b;
        if (op == "print") {
            print(str, a, b);
        } else if (op == "reverse") {
            str = reverse(str, a, b);
        } else if (op == "replace") {
            std::cin >> rep;
            str = replace(str, a, b, rep);
        } else {
            throw std::runtime_error("");
        }
    }
    return EXIT_SUCCESS;
}

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

int main(){
    int N;
    cin >> N;
    int l, r;
    int sum = 0;

    for(int i = 0; i < N; i++){
        cin >> l >> r;
        sum += 1+r-l;

    }

    cout << sum << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  cin >> a;
  vector<int> pre = a;
  ll ans = numeric_limits<ll>::max();
  for (int t = 0; t < n; ++t) {
    ll cur = t * (ll)x;
    for (int i = 0; i < n; ++i) {
      cur += pre[i];
      pre[i] = min(pre[i], a[(i + t + 1) % n]);
    }
    ans = min(ans, cur);
  }
  cout << ans;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 256
A,B,N=map(int,input().split())
if N>=B:
	x=(N//B)*B-1
	t=B-1
	ans=max((A*x)//B-A*(x//B),(A*t)//B-A*(t//B))
	print(ans)
else:
	print((A*N)//B-A*(N//B))
 

Measured memory_bytes: 9184
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repf(i,a,n) for(int i = (int)(a); i < (int)(n); i++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

int main(){
    int n,m,k;
    string ans = "No";
    cin >> n >> m >> k;
    int nm = n*m;
    rep(i,n){
        rep(j,m){
            int t = (i+1)*(j+1)+(n-i-1)*(m-j-1);
            if(t == k || nm - t == k){
                ans = "Yes";
            }
        }
    }
    cout << ans << endl;
}

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;


int main(){

    int n;
    cin >> n;
    if(n < 1000) cout << "ABC" << endl;
    else cout << "ABD" << endl;

    return 0;
}

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

using namespace std;

bool comp(pair<int, long long> a, pair<int, long long> b) {
  return a.first < b.first;
}

void solve(vector<long long>& a, int cur, set<int> comb, vector<long long>& rets, int K) {
  if (comb.size() == K) {
    vector<pair<int, long long> > p;
    for (set<int>::iterator i = comb.begin(); i != comb.end(); ++i) {
      p.push_back(make_pair(*i, a[*i]));
    }

    sort(p.begin(), p.end(), comp);

    // find the larger building than the first one
    int cursor = 0;
    long long largest = 0;
    long long ret = 0;
    for (int i = 0; i < a.size(); ++i) {
      if (i == p[cursor].first) {
        if (p[cursor].second <= largest) {
          ret += largest + 1 - p[cursor].second;
          largest = largest + 1;
        } else {
          largest = p[cursor].second;
        }
        ++cursor;
        if (cursor == p.size())
          break;
      } else {
        largest = max(a[i], largest);
      }
    }

    rets.push_back(ret);

  } else {
    for (int i = cur + 1; i < a.size(); ++i) {
      set<int> tmp = comb;
      tmp.insert(i);
      solve(a, i, tmp, rets, K);
    }
  }
}

int main(int argc, char* argv[]) {
  int N, K;
  cin >> N >> K;

  vector<long long> a(N);
  for (int i = 0; i < N; ++i)
    cin >> a[i];

  set<int> comb;
  vector<long long> rets;
  solve(a, -1, comb, rets, K);

  long long ret = 1000000000000000LL;
  for (int i = 0; i < rets.size(); ++i)
    ret = min(rets[i], ret);

  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#define inf 0x3f3f3f3f
#define esp 1e-7
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n,k;
int num[100050];

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

int main(){
	n=read();
	k=read();
	int maxx=1;
	for (int i=1;i<=n;i++){
		num[i]=read();
		maxx=max(maxx,num[i]);
	}
	for (int i=2;i<=n;i++){
		num[1]=gcd(num[i],num[1]);
	}
	if (k%num[1]==0&&maxx>=k)	printf("POSSIBLE\n");
	else if (maxx==k)	printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;


signed main(){
  int n,a,b;
  string s;
  cin>>n>>a>>b>>s;
  int pass=0,fpass=0;

  rep(i,n){
    if(s[i]=='a'&&pass<a+b){
        cout<<"Yes"<<endl;
        pass++;
    }else if(s[i]=='b'&&pass<a+b&&fpass<b){
      cout<<"Yes"<<endl;
      pass++;fpass++;
    }else{
      cout<<"No"<<endl;
    }
  }
  return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    // odd + odd = even
    // even + even = even
    long long ret = 0;
    
    for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        ret++;
    
    for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++)
        ret++;
    
    cout << ret << endl;
    return 0;
}


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

int main()
{
  string S, T;
  cin >> S >> T;
  
  int count = 0;
  
  for(int i = 0; i < S.size(); i++)
  {
    if(S.at(i) != T.at(i)){count++;}
  }
  cout << count << endl;
}

Measured memory_bytes: 3824
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
#define fs first
#define sc second
// 多倍長
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using boost::rational;
using boost::multiprecision::cpp_int;

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;



int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll n;
    cin >> n;
    
    REP(i, 1, n + 1){
      ll ans = 0;
      REP(j, 1, 101){
        if(j * j > i) break;
        REP(k, 1, 101){
          if(j * j + k * k + j * k > i) break;
          REP(l, 1, 101){
            if(j * j + k * k + l * l + j * k + k * l + l * j > i) break;
            if(j * j + k * k + l * l + j * k + k * l + l * j == i) ans++;
          }
        }
      }
      print(ans);
    }
    

}



Measured memory_bytes: 3628
#include <iostream>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  if (A >= B) {
    swap (A, B);
  }
  if (C >= D) {
    swap (C, D); 
  }
  
  cout << A + C << endl;
  
  return 0;
}

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

vector<vector<int>>v,dp;

void solve(){
	int n;cin>>n;
	v.resize(n,vector<int>(3));
	dp.resize(n,vector<int>(3,-1));
	for(int i=0;i<n;i++){
        cin>>v[i][0]>>v[i][1]>>v[i][2];
	}
	dp[0][0]=v[0][0];
	dp[0][1]=v[0][1];
	dp[0][2]=v[0][2];
	for(int i=1;i<n;i++){
        //cout<<i<<"\n";
        dp[i][0] = max(dp[i-1][1],dp[i-1][2])+v[i][0];
        dp[i][1] = max(dp[i-1][0],dp[i-1][2])+v[i][1];
        dp[i][2] = max(dp[i-1][1],dp[i-1][0])+v[i][2];
        //cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<"\n";
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<"\n";

}
int main(){
	int t=1;//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}


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

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<double,double> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int n,m;
ll pos[MX], mn = INF, mx = -INF;
vpi adj[MX];

void dfs(int a, ll b) {
    if (pos[a] != INF) {
        if (pos[a] != b) {
            cout << "No";
            exit(0);
        }
        return;
    }
    pos[a] = b;
    mn = min(mn,b), mx = max(mx,b);
    for (auto z: adj[a]) dfs(z.f,b+z.s);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    FOR(i,1,n+1) pos[i] = INF;
    F0R(i,m) {
        int l,r,d; cin >> l >> r >> d;
        adj[l].pb({r,d}), adj[r].pb({l,-d});
    }
    FOR(i,1,n+1) if (pos[i] == INF) {
        dfs(i,0);
        if (mx-mn > 1000000000) {
            cout << "No";
            exit(0);
        }
    }
    cout << "Yes";
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

Measured memory_bytes: 11520
#include<stdio.h>

int main(){
    int n, a, max = 0, min = 0, i;
    long sum = 0;
    scanf("%d",&n);
    
    if(n==0){
        printf("no\n");
    }else{
        for(i=0;i<n;i++){
            scanf("%d",&a);
            if(i==0){
                min = a;
                max = a;
                sum = a;
            }else{
                if(max < a) max=a;
                if(a < min) min=a;
                sum += a;
            }
        }
        printf("%d %d %ld\n",min,max,sum);
    }
    return 0;
}

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

int main(){
	int N,A,res=1;
	map<int,int> mp;
	cin>>N;
	rep(i,N){
		cin>>A;
		mp[A]++;
		if(mp[A]>2 || A>=N || mp[0]>1){
			cout<<0<<endl;
			return 0;
		}
	}
	rep(i,N/2)res=(res*2)%1000000007;
	cout<<res<<endl;
}


Measured memory_bytes: 2560
#include <iostream>

int main()
{
  int A, B, C, K, ans;
  std::cin >> A >> B >> C >> K;

  if (A >= K)
  {
    ans = K;
  }
  else
  { // A < K
    if (A + B >= K)
    {
      ans = A;
    }
    else // A+B < K, K-(A+B) cards from C
    {
      ans = A - (K - (A + B));
    }
  }
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int n) {
	if (n == 2)return true;
	if (n % 2 == 0)return false;
	for (int i = 3; i <= sqrt(n); i += 2) if (n%i == 0)return false;
	return true;
}
int main() {
	int n;
	while (cin >> n) {
		if (!n)return 0;
		int sum = 0;
		for (int i = n + 1; i <= 2 * n; i++) {
			if (isprime(i))sum++;
		}
		cout << sum << endl;
	}
}

Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
long long c[100010];
int main()
{
  long long n,i;
  scanf("%lld",&n);
  long long sum=0;
  long long x;
  for(i=0;i<n;i++)
  {
    scanf("%lld",&x);
    c[x]++;
    sum+=x;
  }
  long long q;
  scanf("%lld",&q);
  while(q--)
  {
    long long b,p;
    scanf("%lld%lld",&b,&p);
    sum-=b*c[b];
    c[p]+=c[b];
    sum+=p*c[b];
    c[b]=0;
    printf("%lld\n",sum);
  }
}

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

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

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

ll lcm(int a, int b) {
    return (ll)a * b / __gcd(a, b);
}

int main(){
    int A, B;
    cin >> A >> B;
    cout << lcm(A, B) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#define pb push_back 
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<30)
#define MOD 1000000007
using ll = long long;
using namespace std;

int main() {
    int n, ma=0,mi=INF;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        ma = max(ma, t);
        mi = min(mi, t);
    }
    cout << ma - mi << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int SIX[]  = {6*6*6*6*6*6, 6*6*6*6*6, 6*6*6*6, 6*6*6, 6*6, 6};
int NINE[] = {9*9*9*9*9, 9*9*9*9, 9*9*9, 9*9, 9};
static int memo[100000];
	     
int search(int n) {
  if(n == 0) return 0;
  if(memo[n] != 0) return memo[n];

  int ret0 = n;
  for(int i = 0; i < 6; i++) {
    if(n >= SIX[i]) {
      ret0 = search(n - SIX[i]) + 1;
      break;
    }
  }
  int ret1 = n;
  for(int i = 0; i < 5; i++) {
    if(n >= NINE[i]) {
      ret1 = search(n - NINE[i]) + 1;
      break;
    }
  }
  int ret = (ret0 < ret1) ? ret0 : ret1;
  memo[n] = ret;
  return ret;
}

int main(void) {
  int N;
  scanf("%d", &N);

  int Ans = search(N);
  printf("%d\n", Ans);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}



int main(){

  char x;
  cin >> x;

  if(x>='A' && x<='Z'){
    cout << "A" << endl;
  }else{
    cout << "a" << endl;
  }

}



Measured memory_bytes: 3628
#include <stdio.h>

int main(void)
{
        int n,i,c;

        scanf("%d",&n);

        int p[n];

        for(i=0;i<n;i++)
                scanf("%d",&p[i]);

        c=0;
        for(i=0;i<n;i++)
                if(p[i]!=i+1) c++;

        if(c<=2) printf("YES\n");
        else     printf("NO\n");

        return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n, p[101], a[101], cnt = 0;
int main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cout.tie (nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        p[a[i]] = i;
    }
    for (int i = 1; i <= n; ++ i) {
        if (p[i] != i) {
            swap (p[i], p[a[i]]);
            ++ cnt;
        }
    }
    if (cnt > 1) {
        cout << "NO";
    }
    else {
        cout << "YES";
    }
}


Measured memory_bytes: 256