akhauriyash/Code-Regression huggingface dataset:
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include<regex>
#include <unordered_map>  

using namespace std;

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x*x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)


//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

const int N = 200001;

int par[N];
int n, m, k, x;

//簡易的なunionfind木。rankによる縮約がなくても間に合うみたい。
int getp(int x) {
	return par[x] == x ? x : par[x] = getp(par[x]);
}

void unite(int x, int y) {
	x = getp(x); y = getp(y);
	if (x != y)par[x] = y;
}

void init() {
	for (int i = 1; i < n + m + 1;i++) par[i] = i;
}

int main() {

	cin >> n >> m;
	init();

	//人と言語を連結させる。
	//人がiで1,…,nが人
	//n+1からが言語の領域
	for (int i = 1; i < n+1; i++) {
		cin >> k;
		while (k--) {
			int buf; cin >> buf;
			unite(i, buf + n);
		}
	}

	//各人の頂点から1にいければ、全員がつながっていることになる。
	for (int i = 2; i < n + 1; i++) {
		if (getp(i) != getp(1)) {
			cout << "NO" << endl;
			return 0;
		}
	}

	cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 1408
N = int(input())
X = list(map(int,input().split()))
Y = sorted([(x-1,i+1) for i,x in enumerate(X)])

ans = [None] * (N*N)
must = []
for i,n in Y:
    ans[i] = n
    must += [n]*(n-1)
must.reverse()

used = [0] * (N+1)
free = [1]
for i in range(N*N):
    if ans[i]:
        a = ans[i]
        if used[a] != a-1:
            print('No')
            exit()
        free += [a]*(N-a)
    elif must:
        a = must.pop()
        ans[i] = a
    else:
        if free:
            a = free.pop()
            ans[i] = a
        else:
            print('No')
            exit()
    used[ans[i]] += 1

for i in range(1,N+1):
    if used[i] != N:
        print('No')
        exit()

print('Yes')
print(*ans)

Measured memory_bytes: 11048
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m,v,p;
    cin >> n >> m >> v >> p;
    vll a(n);
    REP(i,n) cin >> a[i];
    sort(ALL(a));
    if(p>=v){
        ll ok = n-p;
        ll ng = -1;
        while(abs(ok-ng)>1){
            ll mid = (ok+ng)/2;
            if(a[mid]+m>=a[n-p]){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        ll ans = n-ok;
        cout << ans << endl;
    }else{
        ll ok = n-p;
        ll ng = -1;
        while(abs(ok-ng)>1){
            ll mid = (ok+ng)/2;
            bool f = true;
            if(a[mid]+m<a[n-p]){
                f = false;
            }else{
                if(mid+1>=v-p+1){
                    f=true;
                }else{
                    ll sum = m*(mid+1);
                    ll vote = m*(v-p+1);
                    for(ll i= mid+1;i<=n-p;i++){
                        sum+=a[mid]+m-a[i];
                    }
                    if(sum>=vote){
                        f = true;
                    }else{
                        f= false;
                    }
                }
            }
            if(f){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        ll ans = n-ok;
        cout << ans << endl;
    }



    return 0;
}

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    char c;
    cin >> c;
    if (c == 'A') c = 'T';
    else if (c == 'T') c = 'A';
    else if (c == 'C') c = 'G';
    else c = 'C';
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 256
###草

import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1###int(N**(1/2))+1以上についてカウント
###あらかじめK=Nはカウント

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        ###
        #print(i,(N-1)//i)
        ###

if  (N-1)**(1/2) - int((N-1)**(1/2)) < 1e-10 or 1 + int((N-1)**(1/2)) - ((N-1)**(1/2)) < 1e-10:
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and (N**(1/m) - int(N**(1/m)) < 1e-10 or 1+int(N**(1/m))-N**(1/m) < 1e-10):###m=1のときはK=Nの話なのでpass
        Klist[round(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1
###
#print("count",count)
#print(Klist[:100])
###
print(sum(Klist)+count-Klist[1])


Measured memory_bytes: 10868
N = int(input())
H=list(map(int,input().split()))
INF=1000000000
dp=[INF]*(N+1)
dp[0]=0
for i in range(1,N):
  if i==1:
    dp[i]=dp[i-1]+abs(H[i]-H[i-1])
  else:
    dp[i]=min(dp[i-2]+abs(H[i-2]-H[i]),dp[i-1]+abs(H[i-1]-H[i]))
print(dp[N-1])

Measured memory_bytes: 13924
#include<stdio.h>
int main()
{
  int room[4][3][10] = {0}, i, j, k, n, b, f, r, v;

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%d%d%d%d" ,&b, &f, &r, &v);
    room[b-1][f-1][r-1] += v;
  }

  for(i = 0; i < 4; i++){
    for(j = 0; j < 3; j++){
      for(k = 0; k < 10; k++){

	printf(" %d", room[i][j][k]);
	
      }
      
      printf("\n");
      
    }
    
    if(i < 3) printf("####################\n");

  }
  
  return 0;
  
}

Measured memory_bytes: 612
n = int(input())

def comeon():
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

ab = list(comeon())

ans = 0
for a, b in ab[::-1]:
    a += ans
    diff = b - a % b if a % b > 0 else 0
    ans += diff

print(ans)

Measured memory_bytes: 17376
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
n = len(s)

if s != s[::-1]:
    print('No')
    quit()
if s[:n//2] != s[:n//2][::-1]:
    print('No')
    quit()
if s[n//2+1:] != s[n//2+1:][::-1]:
    print('No')
    quit()
print('Yes')

Measured memory_bytes: 38384
import java.util.*;
public class Main{
  public static void main(String[]args){
      Scanner sc = new Scanner(System.in);

      int d = sc.nextInt();

      if(d==25){
        System.out.println("Christmas");
      }
      if(d==24){
        System.out.println("Christmas Eve");
      }
      if(d==23){
        System.out.println("Christmas Eve Eve");
      }
      if(d==22){
        System.out.println("Christmas Eve Eve Eve");
      }
      
  }
}

Measured memory_bytes: 23124
using System;
using System.Collections.Generic;
using System.Linq;

namespace AIZU
{
	class Program
	{
		#region Reserve
		static int cin() { return cin(-1); }
		static int cin(int D)
		{
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static int[] cins(char spliter)
		{
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new int[] { };
			string[] ss = s.Split(spliter);
			int[] Res = new int[ss.Length];
			int g;
			for (int i = 0; i < ss.Length; i++) { 
				if(int.TryParse(ss[i],out g))
					Res[i] = g;
			}
			return Res;
		}
		static int[] cins() { return cins(' '); }
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }
		#endregion
		static void Main(string[] args)
		{
			int[] I = cins();
			if (I[1] > I[2]) { print(0);return; }
			if (I[1] == I[2]) { print(1);return; }
			if (I[0] == 1 && I[1] != I[2]) { print(0);return; }
			long Res =(long)(I[2] -I[1]) * (I[0] - 2) + 1;
			print(Res);
		}
	}
}

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

int main() {
  ll n; cin >> n;
  ll asum=0,bsum=0;
  vector<ll> a(n),b(n);
  rep(i,n){
    cin >> a[i]; asum+=a[i];
  }
  rep(i,n){
    cin >> b[i]; bsum+=b[i];
  }
  if(asum<bsum){
    cout << -1 << endl;
    return 0;
  }
  vector<ll> dif(n);
  ll fsum=0, cnt=0;
  rep(i,n){
    dif[i]=a[i]-b[i];
     if(dif[i]<0){
       fsum+=dif[i]*(-1); cnt++;
     }
  }
  if(fsum==0){
    cout << 0 << endl;
    return 0;
  }

  sort(dif.begin(),dif.end());
   ll psum=0;
   for(ll i=n-1;n>=0;i--){
    psum+=dif[i];cnt++;
    if(psum>=fsum){
      break;
    }
  }
  cout << cnt << endl;

}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

//#define DEBUG


int main(void)
{
  ll N;
  cin >> N;
  vector<ll> P(N);
  for(int i=0;i<N;i++)
  {
    cin >> P[i];
//    cout << P[i];
  }
  ll most_min;
  most_min = *min_element(P.begin(),P.end());
//  cout << min;
  ll count = 0;
  ll min = P[0]; // 最小値 最初は与えておく
  for(int i=0;i<N;i++)
  {
    // 今までの最小より小さいかのチェックで良い。
    if( P[i] > min )
    {
      continue;
    }
    min = P[i];
//    cout << "beg:" << *(P.begin()+i) << endl;
//      min =  *min_element(P.begin(),P.begin() + i + 1) ;
//    cout << min << endl;

    
    count++;
    // 最小値がでた時点でおわり　←とは限らない。
//    if(P[i]==most_min)      break;
  }
  cout << count;
  
  return 0;
} 

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



void swap (int *x, int *y) {
  int temp;

  temp = *x;
  *x = *y;
  *y = temp;

  return;
}

int gcd(int a,int b){
  if(a<b){
    swap(&a,&b);
  }

  if(b==0){
    return a;
  }

  int r=a%b;
  while(r!=0){
    a = b;
    b = r;
    r = (a%b);
  }

  return b;
}

/* クイックソート */
int dn(const void*a,const void*b){return*(int*)b-*(int*)a;}


long int modpow(long int a,long int n,long int mod){
  long int ans=1;
  while(n>0){
    if(n & 1){
      ans=ans*a%mod;
    }
    a=a*a%mod;
    n/=2;
  }
  return ans;
}

long int modinv(long int a,long int mod){
  return modpow(a,mod-2,mod);
}

int max(int a,int b){
  if(a<b){
    return b;
  }
  else{
    return a;
  }
}

int min(int a,int b){
  if(a<b){
    return a;
  }
  else{
    return b;
  }
}

void chmax(int *a,int b){
  if(*a < b){
    *a = b;
  }

  return;
}

void chmin(int *a,int b){
  if(*a > b){
    *a =b;
  }

  return;
}

/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/

int main(void){
  /*
  解法2
  (答え)=((総和の2乗)-(2乗の総和))/2
  ということがわかるので，それを実装

  2で割る部分は解法1と同じ

  */
  long int n;
  scanf("%ld",&n);

  long int A[n];
  
  //総和
  long int all=0;
  
  //2乗の総和
  long int sq_all=0;

  long int MOD=1e9+7;

  for(int i=0;i<n;i++){
    scanf("%ld",&A[i]);
    all+=A[i];

    //常にMODを取る！
    all%=MOD;

    sq_all+=modpow(A[i],2,MOD);
    
    //常にMODを取る！
    sq_all%=MOD;
  }


  //MOD上の2の逆元
  long int v=modinv(2,MOD);

  long int ans=modpow(all,2,MOD);
  ans-=sq_all;
  ans+=10*MOD;
  ans%=MOD;

  //常にMODを取る！
  printf("%ld\n",ans*v%MOD);

  return 0;
}

Measured memory_bytes: 3264
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    int times=0;
    int pos=-1;
    for(int i=0;i<3;i++)
    {

        if(str.at(i)=='R'&&pos==-1)
        {
            times++;
            pos=i;
           // cout<<"hello";

        }
        if(i>0)
        if(str.at(i)=='R'&&pos==i-1)
            {
                //cout<<"hello";
                times++;pos=i;
            }
    }
    cout<<times;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
// atoi : atoi(str.c_str())
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)

int main(){
  int k,s;
  cin >> k >> s;
  int answer = 0;
  rep(x,k+1){
    rep(y,k+1){
      int z = s - x - y;
      if(0 <= z && z <= k){
        answer++;
      }
    }
  }
  cout << answer << endl;
}


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

ll X, Y;

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

	cin >> X >> Y;
	ll ans = 0;
	do {
		X *= 2;
		ans++;
	} while (X <= Y);

	cout << ans << "\n";

}

Measured memory_bytes: 256
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

def lcm(x, y):
    return (x * y) // gcd(x, y)

n, m = map(int, input().split())
S = input()
T = input()

if S[:: n // gcd(n, m)] != T[:: m  // gcd(n, m)]:
    print(-1)
else:
    print(lcm(n, m))

Measured memory_bytes: 3316
#include<iostream>
#include<math.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt=0;
    if(n==0) { }
    else if(n==1) { cnt=1; }
    for(int i=1; i<=n; i*=2) {
        for(int j=1; j<=n; j++) {
            //cout << i << " " << j <<endl;
            if(j==i) {cnt=j;}
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a[] = new int[3];
        for(int i=0; i<3; i++){
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        if((a[2]-a[0]+a[2]-a[1])%2 == 0){
            System.out.println((a[2]-a[0]+a[2]-a[1])/2);
        }else{
            System.out.println((a[2]+1-a[0]+a[2]+1-a[1]-1)/2 + 1); 
        }
    }
}


Measured memory_bytes: 22996
require 'prime'
loop do
  n, p = gets.split.map(&:to_i)
  break if n == -1
  p Prime.each.lazy.drop_while{ |e| e <= n }
         .take(p).to_a
         .repeated_combination(2)
         .map{ |a, b| a + b }.sort[p - 1]
end

Measured memory_bytes: 10060
// Caracal vs Monster
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll=long long;

int main(){
    ll h;
    cin >> h;
    int x=0;
    ll sum=0;
    while(h>=1){
        if(h==1){
            sum+=pow(2, x);
            break;
        }
        else{
            sum+=pow(2, x);
            x++;
            h=h/2;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
//manip
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power(T a, T b)
{return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0
//bfs, not x, y, i, j
//not !(i % 2), i % 2 == 0
//check sample again


bool zero(string a) {
    if (a[0] == '0' && SZ(a) >= 2) return 0;
    return 1;
}

int main() {
    //cast caution
    //look constraints always
    cin.tie(0); ios::sync_with_stdio(false);
    
    
    
    int N, Q; cin >> N >> Q;
    int a[N]; rep(i, N) {cin >> a[i]; a[i]--;}
    if (N == 1) {
        cout << a[0] + 1 << endl;
        return 0;
    }
    vector<pii> v(N);
    v[a[0]].F = -1;
    v[a[0]].S = a[1];
    v[a[N - 1]].S = -1;
    v[a[N - 1]].F = a[N - 2];
    rep3(i, 1, N - 1) {
        v[a[i]].F = a[i - 1];
        v[a[i]].S = a[i + 1];
    }
    
    //rep(i, N) cout << v[i].F << " " << v[i].S << endl;
    
    
    int lead = a[0], last = a[N - 1];
    
    rep(i, Q) {
        int q; cin >> q; q--;
        //a ... b c d ... e
        int a = lead; //af = v[a].F, as = v[a].S;
        int b = v[q].F; //bf = v[b].F, bs = v[b].S;
        int c = q; //cf = v[c].F, cs = v[c].S;
        int d = v[q].S; //df = v[d].F, ds = v[d].S;
        int e = last; //ef = v[e].F, es = v[e].S;
        
        //qが最後尾なら
        if (v[c].S == -1) {
            v[a].F = c;
            v[b].S = -1;
            v[c].S = a; v[c].F = -1;
            lead = c; last = b;
        } else if (v[c].F == -1) {
            v[c].F = e; v[c].S = -1;
            v[d].F = -1;
            v[e].S = c;
            lead = d; last = c;
        } else {
            v[a].F = c;
            v[b].S = -1;
            v[c].F = e; v[c].S = a;
            v[d].F = -1;
            v[e].S = c;
            lead = d; last = b;
        }
        
    }
    
    //rep(i, N) cout << v[i].F << " " << v[i].S << endl;
    
    //return 0;
    
    int now = lead;
    
    while (v[now].S != -1) {
        cout << now + 1 << " ";
        now = v[now].S;
        
    }
    cout << last + 1 << endl;
    
}

/*
 10^5個のqueryに答える
 毎回10^5個並び替えるわけにはいかない
 
 最小限何を変えたらいいか
 ある数で、手前と直後
 これは一部だけ変わる
 
 
 
 
 */



Measured memory_bytes: 4020
#include <stdio.h>
int main()
{
    int n,m,k,i,j;
    scanf("%d %d %d",&n,&m,&k);
    
    if(k%n == 0 || k%m == 0)
    {
        printf("Yes\n");
        return 0;
    }
    else
    {
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=m;j++)
            {
                if(k == (n*j+m*i)-2*i*j)
                {
                    printf("Yes\n");
                    return 0;
                }
            }
        }
        
    }
    
    printf("No\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int RLEN=1<<18|1;
inline char nc() {
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
    char ch=nc(); int i=0,f=1;
    while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
    while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
    return i*f;
}

const int N=1e5+50;
int n;
multiset <int> S;
inline bool check(int v) {
    if(S.find(v)==S.end()) return false;
    S.erase(S.find(v)); return true;
}
int main() {
    n=rd(); for(int i=1;i<=n;i++) S.insert(rd());
    int mx=*S.rbegin();
    for(int i=1;i<=mx+1;i++) 
        if(!check(max(mx-i+1,i-1))) {puts("Impossible"); return 0;}
    for(multiset <int> ::iterator it=S.begin();it!=S.end();++it) {
        if(*it-1<(mx+1)/2) {puts("Impossible"); return 0;}
    } puts("Possible");
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

int V, E;
int dist[100000];
vector<int> a[100000];
map<pair<int, int>, int> mp;
const int INF = 1000000000;

int main() {
  int s;
  cin >> V >> E >> s;
  rep(i, E) {
    int x, y, temp;
    cin >> x >> y >> temp;
    a[x].push_back(y);
    mp[make_pair(x, y)] = temp;
  }
  priority_queue<P, vector<P>, greater<P>> que;
  que.push(P(0, s));

  rep(i, V) {
    dist[i] = INF;
  }
  dist[s] = 0;
  
  while(que.size()) {
    int p = que.top().second;
    que.pop();
    for(int i = 0; i < a[p].size(); i++) {
      if(dist[a[p][i]] > dist[p] + mp[make_pair(p, a[p][i])]) {
        dist[a[p][i]] = dist[p] + mp[make_pair(p, a[p][i])];
        que.push(P(dist[a[p][i]], a[p][i]));
      }
    }
  }

  rep(i, V) {
    if(dist[i] != INF) cout << dist[i] << endl;
    else cout << "INF" << endl;
  }
  return 0;
}


Measured memory_bytes: 41240
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

s = input().strip()
t = 0
for i in s:
    t += int(i)
if t%9:
    print('No')
else:
    print('Yes')




Measured memory_bytes: 68032
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long n, d;
	cin>>n>>d;
	long long x, y;
	long long ans=0;
	for (int i=1; i<=n; i++) {
		cin>>x>>y;
		if ((x*x+y*y)<=d*d) {
			ans++;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3628
/* by Natsu Kinmoe */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x)               ((int)(x).size())
#define all(x)              (x).begin(), (x).end()
#define loop(i, n)          for(int i = 0; i < (n); i++)
#define cont(i, n)          for(int i = 1; i <= (n); i++)
#define circ(i, a, b)       for(int i = (a); i <= (b); i++)
#define range(i, a, b, c)   for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v)      for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define y0          y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1          y1II11II11III11I1III11II111IIII1II1I1
#define pub         push_back
#define pob         pop_back
#define mak         make_pair
typedef long long   ll;
typedef long double lf;
const int   Inf = 0x3f3f3f3f;
const ll    INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

int n;
int d[105][2];

int main() {
	cin >> n;
	cont(i, n) cin >> d[i][0] >> d[i][1];
	cont(i, n - 2) if(d[i][0] == d[i][1] && d[i + 1][0] == d[i + 1][1] && d[i + 2][0] == d[i + 2][1]) {
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i,n) cin >> a[i];
	vector<ll> ans(n);
	rep(i,n) {
		if (i % 2 == 0) ans[0] += a[i];
		else ans[0] -= a[i];
	}
	rep(i,n-1) {
		ans[i + 1] = 2 * a[i] - ans[i]; 
	}
	rep(i,n) {
		if (i != 0) cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

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

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



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

int a[n]={0};

for(int i=0;i<n;i++)
cin>>a[i];

sort(a,a+n);

int res=0;

for(int i=0;i<k;i++)
res+=a[i];

cout<<res<<"\n";


return 0;
}



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

typedef long long ll;
const int N = 2000006;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int n,l;
	cin>>n>>l;
	
	int sm = 0;
	for(int i=1;i<=n;i++){
		int x = i+l-1;
		sm += x;
	}
	
	int ans = -1,mn = 1000000;
	for(int i=1;i<=n;i++){
		int x = i+l-1;
		if( abs(sm - (sm-x)) < mn ){
			mn = abs(sm-(sm-x));
			ans = sm-x;
		}
	}
	
	cout<<ans;
	
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 100005;

bool check(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return t == s;
}
int main() {
    string s;
    cin >> s;
    int n = s.size();
    string s1 = s.substr(0, (n - 1) / 2);
    string s2 = s.substr((n + 3) / 2 - 1);
    puts(check(s) && check(s1) && check(s2) ? "Yes" : "No");

    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;
using P = pair<int,int>;
const int MOD = 1000000007;

int main() {
    int a;
    cin>>a;
    int l=a/100;
    int r=a%100;
    if (1<=l&&l<=12) {
        if (1<=r&&r<=12) cout<<"AMBIGUOUS"<<endl;
        else cout<<"MMYY"<<endl;
    } else {
        if (1<=r&&r<=12) cout<<"YYMM"<<endl;
        else cout<<"NA"<<endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int low = 0;
	int n,k;
	//int a;
	cin >> n >> k;
//	for (int i = 1; i < n + 1; i++) {
	//	cin >> a;
		//if (a == 1)low = i;
	//}
	int ans;
	if( (n-1) % (k - 1)==0)ans=(n-1)/(k-1);
	else ans = (n - 1) / (k - 1) + 1;
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

#define rep(i,x,y) for(int i=(x); i<(y); ++i)

template <typename T>
void vec_print(vector<T> VEC){
  rep(i, 0, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  rep(i, 0, MAT.size()){
    rep(j, 0, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

template <typename CLASS1, typename CLASS2>
class HOGE{
  public:
    CLASS1 key;
    CLASS2 value;
    HOGE(ll key, ll value){
      this->key = index;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "key : " << key << ", value : " << value << "\n";
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;

void calc_dp(const int start, const vector<double>& p, vector<double>& dp){
  if(start==p.size()-1){
    dp[0] = 1.0-p[start];
    dp[1] = p[start];
    return;
  }
  calc_dp(start+1, p, dp);
  dp[p.size()-start] = dp[p.size()-start-1]*p[start];
  for(int i=p.size()-start-1; i>0; --i){
    dp[i] = dp[i]*(1.0-p[start]) + dp[i-1]*p[start];
  }
  dp[0] = dp[0]*(1.0-p[start]);
  return;
}

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N;
  cin >> N;
  // ans 1
  /* 
  vector<double> p(N);
  rep(i, 0, N){
    cin >> p[i];
  }
  vector<double> dp(N+1, 0.0);
  calc_dp(0, p, dp);
  */

  //ans 2
  vector<double> dp(N+1, 0.0);
  double tmp;
  cin >> tmp;
  dp[1] = tmp;
  dp[0] = 1.0-tmp;
  rep(i, 1, N){
    cin >> tmp;
    dp[i+1] = dp[i]*tmp;
    for(int j=i; j>0; --j){
      dp[j] = dp[j]*(1.0-tmp) + dp[j-1]*tmp;
    }
    dp[0] = dp[0]*(1.0-tmp);
  }

  double ans=0.0;
  rep(i, N/2+1, N+1){
    ans += dp[i];
  }

  printf("%.10lf\n", ans);

  return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = [0]*n

#n ... 番目の箱　b[n-1]　のボールの数
blist = []
for j in range(n-1,-1,-1):
    k=j+1
    count= 0
    while k<=n:
        count = count + b[k-1]
        k = k+j+1
    if a[j] == 1:
        if (count)%2 == 0:
            b[j] = 1
            blist.append(j+1)
    else:
        if (count)%2 == 1:
            b[j] = 1
            blist.append(j+1)

sb = sum(b)
print(sb)
strb = " ".join(map(str,blist))
print(strb)


Measured memory_bytes: 20592
def main():
    S = input()
    N = len(S)
    K = int(input())
    dp = [[[0]*(4) for j in range(2)] for i in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            for k in range(4):
                lim = (9 if j else int(S[i]))
                for d in range(lim + 1):
                    if k + (d != 0) > 3:
                        continue
                    dp[i+1][j or d < lim][k + (d != 0)] += dp[i][j][k]
    ans = 0
    for j in range(2):
        ans += dp[N][j][K]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 40944
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		String[] n = saori.nextHayami().split("");
		for(int i =0;i < n.length;i++){
			if(n[i].equals("1")){
				n[i] = "9";
			} else {
				n[i] = "1";
			}
			System.out.print(n[i]);
		}
		System.out.println("");
		
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 23124
#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
    int a,b,i,j;
    while(1){
        cin >> a >> b;
        if(a == 0 && b == 0) break;
        for(i = 0;i < a;i++){
            if(i == 0 || i == (a-1)){
                for(j = 0;j < b;j++){
                    cout << "#";
                }
                cout << endl;
            }else{
                cout << "#";
                for(j = 1;j < b-1;j++){
                    cout << ".";
                }
                cout << "#" << endl;
            }
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3092
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>
#include<cmath>
#include<assert.h>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<complex>
#include<bitset>

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

int N;
int X[100100];
int L, Q;
int d[20][100100];

signed main() {
    cin >> N;
    rep(i, N) {
        cin >> X[i];
    }
    X[N] = X[N - 1] + 1;
    N++;
    cin >> L >> Q;
    rep(i, N) {
        d[0][i] = l_b(X, X + N, X[i] + L + 1) - X - 1;
    }
    rep(i, 19) {
        rep(j, N) {
            d[i + 1][j] = d[i][d[i][j]];
        }
    }
    rep(i, Q) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if (a > b)swap(a, b);
        int x = a;
        int ans = 0;
        for (int j = 19; j >= 0; --j) {
            if (d[j][x] == b) {
                x = b;
                ans += 1ll << j;
                break;
            } else if (d[j][x] < b) {
                x = d[j][x];
                ans += 1ll << j;
            }
        }
        if (x < b)ans += 1;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 17280
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



s = S()
k = I()

index = -1
for i in range(len(s)):
    if s[i] != '1':
        ans = s[i]
        index = i
        break


if  k > index >= 0:
    print(ans)
else:
    print(1)

Measured memory_bytes: 39152
#include <bits/stdc++.h>
using namespace std;
 
int n,t; 
int f[200010];
long long ans;
 
int main() 
{
    cin>>n>>t;
    for (int i=1;i<=n;i++) scanf("%d",&f[i]);
    for (int i=1;i<n;i++) ans+=min(f[i+1]-f[i],t);
    cout<<ans+t<<endl;
}

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

bool atgc(string str){
  int n = str.size();
  rep(i,n){
     if(str[i] != 'A' && str[i] != 'T' && str[i] != 'C' && str[i] != 'G') return false;
  }
  return true;
}

void solve(){
  string s;
  cin >> s;
  int maximum = 0;
  int siz = s.length();
  for(int i=0; i<siz; i++){
    for(int j=i+1; j<=siz; j++){
      string substring = s.substr(i, j-i); 
      //cout << substring << endl;
      int leng = substring.length();
      if(atgc(substring)) maximum = max(maximum, leng);
    }
  }
  cout << maximum << endl;
}

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


Measured memory_bytes: 256
import Control.Applicative
import Data.Char

judge :: String -> String -> String
judge [] [] = "EQUAL"
judge (x:xs) (y:ys) 
          | ord x > ord y     = "GREATER"
          | ord x < ord y     = "LESS"
          | otherwise         = judge xs ys

main :: IO ()
main = do
  num1 <- getLine
  num2 <- getLine
  putStrLn $ case length num1 == length num2 of
               True -> judge num1 num2
               False -> if length num1 > length num2 then "GREATER"
                                                     else "LESS"

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()      //昇順
#define RALL(obj) (obj).rbegin(), (obj).rend()   //降順
#define print(obj) cout << obj << endl
#define scan(obj) cin >> obj

typedef long long ll;

using namespace std;

int main(void){
    ll n, sum = 0;
    cin >> n;
    vector<pair<ll, ll>> pairs(n);
    rep(i, n){
        ll tempa, tempb;
        cin >> tempa >> tempb;
        pairs[i].first = tempb;
        pairs[i].second = tempa;
    }
    sort(pairs.begin(), pairs.end());
    rep(i, n){
        sum += pairs[i].second;
        // cout << pairs[i].first << ' ' << pairs[i].second << ' ' << sum << endl;
        if(sum > pairs[i].first){
            print("No");
            return 0;
        }
    }
    print("Yes");
}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdio>
#include <queue>
#include <map>

#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define all(v) (v).begin(), (v).end()
#define MP make_pair
#define f first
#define s second

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> P;

void pp(vi v){
	rep(i, v.size()){
		cout << v[i] << ' ';
	}
	cout << endl;
}

void pp(vector<string> v){
	rep(i, v.size()){
		cout << v[i] << endl;
	}
}

void pp(int (*f)[21]){
	rep(i, 21){
		rep(j, 21){
			cout << f[i][j];
		}
		cout << endl;
	}
}

int main(){
	int n, m, a;
	while(cin >> n >> m >> a){
		if(!n && !m && !a) break;

		int bars[1001];
		rep(i, 1001) bars[i] = i;

		vector<pair<int, P> > hbar;
		rep(i, m){
			int h, p, q;
			cin >> h >> p >> q;
			hbar.push_back(MP(h, MP(p,q)));		
		}

		sort(all(hbar));

		rep(i, m){
			P p = hbar[i].second;
			swap(bars[p.first], bars[p.second]);
		}

		cout << bars[a] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1228
import itertools
L = input()
L = [int(x) for x in list(str(L))]
P = [0]*3
sum = L[0]
A = (1,-1)
for a in itertools.product(A,repeat=3):
	for i in range(3): 
		sum += a[i]*L[i+1]
		if a[i] == 1:
			P[i] = '+'
		else:
			P[i] = '-'
	if sum == 7:
		print(L[0],P[0],L[1],P[1],L[2],P[2],L[3],'=7',sep = '')
		break
	sum = L[0]

Measured memory_bytes: 9124
import java.util.Scanner;

public class Main {

    public static void main( String[] args ){

        Scanner in = new Scanner(System.in);

        String param = in.nextLine();
        String[] params = param.split( " ");

        int n = Integer.parseInt( params[0]);
        int k = Integer.parseInt( params[1]);
        String s = in.nextLine();

        String[] chars = s.split("");
        String ans = "";
        for( int i = 0 ; i < chars.length ; i++ ){
            if( i == k - 1 ){
                ans += chars[i].toLowerCase();
            }
            else {
                ans += chars[i];
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
import math
import time

n,k = map(int,input().split())

ans = 0
for i in range(1,n+1):
    if k<=i:
        ans +=1
    else:
        for j in range(1,1000):
            if i*(2**j)>=k :
                ans += 1/(2**j)
                break
print( ans/n )


Measured memory_bytes: 9160
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long unsigned int ll;
using namespace std;
ll gcd(ll a, ll b){
  if(b == 0){return a;}
  if(a < b){
    return gcd(b, a);
  }
  return gcd(b, a%b);
}
ll lcm(ll a, ll b){
  return (a/gcd(a, b))*b;
}
int main()
{
  ll n, m;
  cin >> n >> m;
  ll tmp =0;
  ll LCM = 0;
  ll num2 = 0;
  cin >> tmp;
  LCM = tmp/2;
  while(tmp%2==0){
    tmp /= 2;
    num2++;
  }
  ll num3 = pow(2,num2);
  for(ll i = 1;i < n; i ++){
    cin >> tmp;
    if(tmp %num3 != 0 || tmp%(num3*2)==0){
      cout << 0 << endl;
      return 0;
    }
    tmp /= 2;
    LCM = lcm(LCM,tmp);
    if(LCM > m){
      cout << 0 << endl;
      return 0;
    }
  }
  // cout << LCM << endl;
  ll k = m/LCM;
  if(k%2 == 0){
    cout << k/2 << endl;
  }else{
    cout << k/2 + 1 << endl;
  }
}


Measured memory_bytes: 256
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
use proconio::input;
//use proconio::marker::Usize1;
//use proconio::marker::Chars;
//use std::collections::HashSet;
use std::cmp::*;
fn main() {
    input! {
        a:i32,b:i32, mut k:i32
    }
    for i in (1..(min(a, b) + 1)).rev() {
        if a % i == 0 && b % i == 0 {
            k -= 1;
            if k == 0 {
                println!("{}", i);
            }
        }
    }
}


Measured memory_bytes: 2132
A = [1,3,5,7,8,10,12]
B = [4,6,9,11]
C = [2]

x,y = [int(x) for x in input().split()]
if x in C or y in C:
    print("No")
else:
    if (x in A and y in A) or (x in B and y in B):
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#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()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(20);

    int n;
    cin>>n;
    vi v(n);
    
    rep(i,n){
        cin>>v[i];   
    }
    int ans=INF;

    rep(x,101){
        int sum=0;
        rep(i,n){
            sum+=(x-v[i])*(x-v[i]);
        }
        ans=min(ans,sum);
    }

    cout<<ans<<endl;
    
}

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

using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define rep(i, N) for (ll i = 0; i < (N); i++)
#define For(i, a, b) for (ll i = (a); i < (b); i++)
#define all(A) (A).begin(), (A).end()

int main(){
    int N, X, Y;
    cin >> N >> X >> Y;
    ll A[N][N];
    rep(i, N)rep(j, N) A[i][j] = abs(i - j);
    X--;
    Y--;
    A[X][Y] = 1;
    A[Y][X] = 1;
    rep(i, N)rep(j, N) A[i][j] = min(min(A[i][j], A[i][X] + A[Y][j] + 1), A[i][Y] + A[X][j] + 1);

    int ans[N];
    rep(i, N) ans[i] = 0;
    rep(i, N)rep(j, N) ans[A[i][j]]++;

    rep(i, N - 1) cout << ans[i + 1] / 2 << endl;

    return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
  int N;
  cin >> N;
  cout << (1000 - N % 1000) % 1000 << endl;
}

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

using namespace std;

#define ll			long long
#define ALL(s)			(s).begin(),(s).end()
#define ALLn(s,n)		s,s+n
#define F			first
#define S			second
#define pb			push_back
#define tc(t)			int t; cin >> t; while(t--)
#define _			ios_base::sync_with_stdio(false); cin.tie(NULL);
#define PI 3.141592653589793238
const ll MOD = 1e9 + 7;
const ll INF = INT_MAX;
const ll MAX_N = 1e6 + 7;


void solve() {
    int n;
    cin >> n;

    map<int,int> m;

	for(int i = 1; i <= n; ++i) m[i] = 0;
    for(int i = 1; i < n; ++i) {
		int x;
		cin >> x;
		m[x]++;
	}

	for(int i = 1; i <= n; ++i) {
		cout << m[i] << "\n";
	}
}

int32_t main() {_
    //tc(t) 
	solve();
}


Measured memory_bytes: 13044
N,K = map(int,input().split())
A = list(map(int,input().split()))

if N==1:
    print(A[0] if K%2 else '')
    exit()

AA = A+A
last_i = {}
nx = [-1]*N
for i,a in enumerate(reversed(AA)):
    i = 2*N-i-1
    if i < N:
        nx[i] = (last_i[a] - i) % N + 1
    last_i[a] = i

visited = [-1]*N
visited[0] = 0
j = i = 0
while 1:
    p = nx[i]+N if nx[i]==1 else nx[i]
    j += p
    if visited[j%N] < 0:
        visited[j%N] = j
    else:
        break
    i = j%N
cycle = (j - visited[j%N]) // N
K %= cycle
j = i = 0
while 1:
    p = nx[i]+N if nx[i]==1 else nx[i]
    if j+p > N*K:
        break
    j += p
    i = j%N

if j%N == 0:
    if K==1:
        print(*A)
    else:
        print()
else:
    ans = []
    anss = set()
    for a in A[j%N:]:
        if a in anss:
            while ans[-1] != a:
                anss.remove(ans[-1])
                ans.pop()
            anss.remove(a)
            ans.pop()
        else:
            anss.add(a)
            ans.append(a)
    print(*ans)

Measured memory_bytes: 54596
#include <bits/stdc++.h>
#define maxn 100005
#define inf 1000000007
using namespace std;

int arr[maxn], dp[maxn];

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

    //freopen("d.in", "r", stdin);

    int n;cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> arr[i];
        dp[i] = inf;
    }

    dp[1] = 0;
    for (int i = 1; i <= n; i ++){
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(arr[i + 1] - arr[i]));
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(arr[i + 2] - arr[i]));
    }

    cout << dp[n];

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int n, k, soukyori;
  cin >> n >> k;
  
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    
    if (x < k - x) {
      soukyori += x * 2;
    }
    else {
      soukyori += (k - x) * 2;
    }
  }
 
  cout << soukyori << endl;
}

Measured memory_bytes: 384
#include<stdio.h>

int main(void) {
	unsigned int N, K, X, Y;
	unsigned int cost;

	scanf("%d", &N);		//全宿泊日数
	scanf("%d", &K);		//宿泊料金が安くなる前日までの日数
	scanf("%d", &X);		//通常の宿泊料金
	scanf("%d", &Y);		//安くなった後の宿泊料金

	
	if (N > K) {			//宿泊料金が安くなる日数よりも長く宿泊した場合
		cost = K * X + (N - K) * Y;			//通常の料金＋安くなった後の料金の合計を求める
	}
	//宿泊料金が安くなる日数より短く宿泊した場合
	else if (N <= K) {
		cost = N * X;						//通常の料金＊全宿泊日数で料金の合計を求める
	}
		
	printf("\n%d\n",cost);					

	return 0;
}

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

#define ll long long
#define pb push_back
#define mp make_pair
int main() 
{
	 ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     
		int n;
		cin>>n;
		ll a[n],b[n];
		for(int i=0;i<n;i++)
		cin>>a[i]>>b[i];
	ll	int ans=0;
		for(int i=n-1;i>=0;i--)
		{
			if((a[i]+ans)%b[i]==0)
			continue;
			
			ans+=b[i]-(a[i]+ans)%b[i];
		}
		cout<<ans<<endl;
			
				 
	
}


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

int main(void){
    int n;
    int p[100],max=0,total=0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> p[i];
        if(p[i]>max) max=p[i];
        total+=p[i];
    }
    cout << total-(max/2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int a,sum,b9,i;
  scanf("%d",&sum);
  while(sum){
    b9=0;
    for(i=0;i<9;i++){
      scanf("%d",&a);
      b9+=a;
    }
    printf("%d\n",sum-b9);
    scanf("%d",&sum);
  }
  return 0;
}

Measured memory_bytes: 600