akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
      	boolean b = true;
 
      for(int i = 0; i < num; i++){
        int a = sc.nextInt();
        if(a % 2 == 0){
          if(a % 3 != 0 && a % 5 != 0){
            b = false;
          }
        }
      }
      if(b == false){
        System.out.println("DENIED");
      }else{
        System.out.println("APPROVED");
      }
    }
}

Measured memory_bytes: 23636
import bisect

N, M = list(map(int, input().split()))
A = list(map(lambda x: int(x) * -1, input().split()))
A.sort()

cnt = 1
while cnt <= M:
    x = bisect.bisect(A, A[0]/2)
    for i in range(x):
        A[i] /= 2
        cnt += 1
        if cnt > M:
            break
    if x != 0 or x != len(A):
        A.sort()
print(sum(map(lambda x: int(-x), A)))

Measured memory_bytes: 64112
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
	ll d, t, s;
	cin >> d >> t >> s;
	if (d <= t * s)
		cout << "Yes";
	else
		cout << "No";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	for (; q > 0; q--) {
		solve();
		cout << endl;
	}
}

Measured memory_bytes: 3648
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


N, P = map(int, input().split())
res = prime_factorize(P)

cnt = {}
for r in res:
    if r not in cnt:
        cnt[r] = 1
    else:
        cnt[r] += 1

ans = 1
for k, v in cnt.items():
    ans *= k ** (v // N)
print(ans)


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

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int INF = 1e9;

#define NMAX 100005
bool v[NMAX];
vi adjList[NMAX];

using namespace std;

void dfs(int i){
    v[i] = true;
    queue<int> q; q.push(i);
    while(!q.empty()){
        int front = q.front(); q.pop();
        for(auto u: adjList[front]){
            if(!v[u]){
                v[u] = true;
                q.push(u);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
//    freopen("out.txt", "w", stdout);
    
    int N, M; cin >> N >> M;
    fill(v, v+NMAX, false);    
    for(int i = 0; i < M; i++){
        int x, y; cin >> x >> y;
        adjList[x].push_back(y);    
        adjList[y].push_back(x);    
    }

    int c = 0;
    for(int i = 1; i <= N; i++){
        if(!v[i]){
            c++;
            dfs(i);
        }
    }

    cout << c-1;

    return 0;

}


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

int main()
{
int a,b,k,c;



while(1){
    cin>>a>>b>>c;
    k=a+b;
    if(a==-1 && b==-1 && c==-1)
       break;

   if(a==-1 || b==-1)
    cout<<"F"<<endl;
   else if(k>=80)
    cout<<"A"<<endl;
   else if(65<=k)
    cout<<"B"<<endl;
   else if(50<=k)
    cout<<"C"<<endl;
    else if(30<=k)
    {
         if(c>=50)
               cout<<"C"<<endl;
         else
            cout<<"D"<<endl;
    }
    else
    cout<<"F"<<endl;


}

}








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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

ll n;

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

  cin>>n;

  if (n%2) out(0);

  ll f = 0;
  ll base = 2*5;
  while (base<=n) {
    f += n/base;
    base *= 5LL;
  }

  out(f);

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <string>

using namespace std;


int main() {
    string s; cin >> s;
    int ans = 1000000;
    for (int i = 0; i < s.length() - 2; i++) {
        int a = s[i] - '0';
        int b = s[i + 1] - '0';
        int c = s[i + 2] - '0';
        int x = 100 * a + 10 * b + c;
        ans = min(ans, abs(x - 753));
    }
    // int s; cin >> s;
    // int array[10];
    // int ans = 10000;
    // int nd = log10(s)+1;
    // cout << "nd: " << nd << endl;
    // for (int i = nd; i > 2; i--) {
    //     cout << "i: " << i << endl;
    //     // 3桁取り出す
    //     int target = 0;
    //     for (int j = 1; j <= 3; j++) {
    //     int y = pow(10, i - j);
    //     int x = s / y;
    //     cout << "x: " << x << endl;
    //     target += x * pow(10, 2 - j);
    //     }
    //     cout << "target: " << target << endl;
    //     int aa = target - 753;
    //     cout << "aa: " << aa << endl;

    // }
    cout << ans << endl;
    return 0;
}

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

int main(void) {
  int N,M = 0,d = 1;
  cin >> N;
  vector<int> vec(110);
  rep(i,N) {
    vec.at(i) = i;
    vector<int> count(110);
    while (vec.at(i) % 2 == 0) {
      count.at(i)++;
      vec.at(i) /= 2;
    }
    if(count.at(i) > M) {
      M = count.at(i);
      d = i;
    }
  }
  cout << d << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;
int main(){
    long long N;
    int K;
    int step;
    long long count = 0;
    long long temp = 0;
    cin>>N>>K;
    if(K==1){
        count = N*N*N;
        cout<<count<<endl;
        exit(0);
    } else if(K==2){
        if(N%2==0)
            count = N*N*N/4;
        else {
            auto a = N>>1;
            auto b = a+1;
            count = a*a*a+b*b*b;
        }
        cout<<count<<endl;
        exit(0);
    }else if(K==3){
        double base = (long long)floor(N/3);
        count = (long long)pow(base,3);
        cout<<count<<endl;
        exit(0);
    }
    else if(K%2==0){
        step = K/2;
    }else{
        step = K;
    }
    for(int i = 1;i*step<=N;i++){
        int j = K-i*step;
        for(;j<=N;j=j+K){
            if(j>0)temp++;
        }
        count+=temp*temp;
        temp = 0;
    }
    cout<<count<<endl;
    return 0;

};

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define max		  1000000
#define pb		  push_back
#define pairs	  pair<int, int>
#define vi		  vector<int>
#define vb		  vector<bool>
#define vii		  vector<pairs>
#define lb		  lower_bound
#define ub		  upper_bound
#define lli		  long long int
#define endl	  '\n'
#define FastInput ios_base::sync_with_stdio(false), cin.tie(NULL);
#define Cases	  cout << "Case " << ++Case << ": ";
#define __test    \
	int tt;       \
	int Case = 0; \
	cin >> tt;    \
	while (tt--)
#define read(x)	 freopen(x, "r", stdin)
#define write(x) freopen(x, "w", stdout)
#define InputArray(a, n)        \
	for (int i = 0; i < n; i++) \
		cin >> a[i];
#define CopyArray(a, temp, n)   \
	for (int i = 0; i < n; i++) \
		temp[i] = a[i];
#define PrintArray(a, n)        \
	for (int i = 0; i < n; i++) \
		cout << a[i] << " ";    \
	cout << endl;
using namespace std;

int main() {
#ifdef Niloy
	read("input.txt");
	write("output.txt");
#endif

	int n;
	cin >> n;
	long long arr[100010];

	for (int i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
	}

	long long int mul = 1;

	for (int i = 0; i < n; i++) {
		if (arr[i] == 0) {
			printf("0\n");
			return 0;
		}
	}

	for (int i = 0; i < n; i++) {
		if (arr[i] <= 1000000000000000000 / mul) {
			mul *= arr[i];
		} else {
			printf("-1\n");
			return 0;
		}
	}

	printf("%lld\n", mul);
	cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
	return 0;
}

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

int finddivsum(int n){
  int sum = 0;
  while(n >0){
    sum += n% 10;
    n /= 10;
  }
  return sum;
}


int main() {
  int n;
  cin >> n;
  int sum = finddivsum(n);
  if(n%sum==0) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

#define ll long long
#define mod 1000000007
#define mx 100005

int a[mx+10];
char ch[mx+10];
int n;

void solve(int ii)
{
    scanf("%d",&n);

    scanf("%s",ch);

    int re=0,par=0;

    for(int i=0;i<n;i++)
    {
        if(ch[i]=='A'&& i+2<n)
        {
            if(ch[i+1]=='B' && ch[i+2]=='C')re++,i+=2;
        }
    }

    printf("%d\n",re);

   return;
}

int main()
{
    int t=1;

    for(int i=1;i<=t;i++)solve(i);

    return 0;
}


Measured memory_bytes: 256
var s,r,g,b,n,t:Longint;
begin
read(r,g,b,n);
t:=n;
while True do begin
if t<0 then begin
dec(n,b);
t:=n;
if t<0 then begin
writeln(s);
exit;
end;
end;
if t mod r=0 then inc(s);
dec(t,g);
end;
end.

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <fstream>
#include <sstream>
#include <math.h>
#include <map>
using namespace std;

int main()
{
	int N,flug=0;
	vector<string> B;
	cin >> N;
	
	for(int i=0;i<N;i++)
	{
		string S;
		cin >> S;
		B.push_back(S);
		if(i==0)
		{
			continue;
		}
		else
		{
			string str1 = B[i].substr(0,1);
			string str2 = B[i-1].substr(B[i-1].size()-1,1);
			if(str1!=str2){flug++;}
		}
	}
	sort(B.begin(),B.end());
	for(int i=0;i<N-1;i++)
	{
		if(B[i]==B[i+1]){flug++;}
	}
	if(flug==0){cout << "Yes" << endl;}
	else{cout << "No" << endl;}
}

Measured memory_bytes: 256
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;
    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int n,i,j;
            cin>>n;
            ld dp[n][n+1];
            mem(dp,0);
            ld p;
            for(i=0;i<n;++i)
            {
                cin>>p;
                //cout<<p<<endl;
                if(i==0)
                {
                    dp[i][0]=1-p,dp[i][1]=p;
                    continue;
                }
                for(j=1;j<=n;++j)
                {
                    dp[i][j]=dp[i-1][j]*(1.0-p) + dp[i-1][j-1]*p;
                }
                dp[i][0]=(1-p)*dp[i-1][0];
            }
            ld ans=0.0;
            for(i=1;i<=n;++i)
            {
                if(i>=n-i)
                    ans=ans+dp[n-1][i];
            }
            printf("%.9Lf\n",ans);
        }
        return 0;
    }


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

int main() {
    int N;
    cin >> N;
    vector <int> takoyakis(N);

    for (int i = 0; i < N; i++) {
        cin >> takoyakis[i];
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            ans += takoyakis[i] * takoyakis[j]; 
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2

using namespace std;
int MOD = 1000000007;
int n,k;
signed main(){
    cin >> n >> k;
    int a[100010];
    int b[100010];
    rep(i,n) cin >> a[i] >> b[i];

    int ans = 0;
    rep(i,n){
        int c = 1;
        rep(j,30){
            if((!(k&(1LL<<j))) && (a[i]&(1LL<<j)))c = 0;
        }
        if(c == 1)ans += b[i];
    }
    for(int i = 30; i >= 0;i--){
        if(k&(1LL<<i)){
            int ans1 = 0;
            int x = k;
            x &= ~(1LL<<i);
            rep(ii,n){
                int c = 1;
                for(int j = i;j <= 30;j++){
                    if(!(x&(1LL<<j)) && (a[ii]&(1LL<<j)))c = 0;
                }
                if(c == 1)ans1 += b[ii];
            }
            ans = max(ans,ans1);
        }
    }
    
    cout << ans << endl;
    return 0;
}
// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl 

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main() {
  int n; ll ans=1;
  cin >> n;
  vector<int> cnt(n+1);
  cnt[0]=3;
  rep(i,n){
    int k; cin >> k;
    ans *= cnt[k];
    ans %= mod;
    cnt[k+1]++;
    cnt[k]--;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    int n,ans=0;
    cin>>n;
    int a[n];
    REP(i,n)cin>>a[i];
    REP(j,n){
        REP(k,n){
            if(abs(a[j]-a[k])>ans)ans=abs(a[j]-a[k]);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
# #!/usr/bin/env python3
# # -*- coding: utf-8 -*-


def main():
    N = int(input())
    V = list(map(int, input().split()))

    while len(V) != 1:
        V.sort()
        v1, v2 = V.pop(0), V.pop(0)
        V.append((v1 + v2) / 2)

    print(*V)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
N=gets.to_i
x = []
y = []
h = []

tmpx = 0
tmpy = 0
tmph = 0
N.times do
    xx,yy,hh = gets.chomp.split.map(&:to_i)
    x << xx
    y << yy
    h << hh
    if hh > 0
        tmpx = xx
        tmpy = yy
        tmph = hh
    end
end


0.upto(100) do |i|
    0.upto(100) do |j|
        hh = tmph + (tmpx - i).abs + (tmpy - j).abs

        flag = true;
        0.upto(N-1) do |k|
            if h[k] != [0, hh -  (x[k] - i).abs - (y[k] - j).abs].max
                flag = false
                break;
            end
        end      

        if flag == true
            printf("%d %d %d\n", i, j, hh)
            exit
        end
    end
end



Measured memory_bytes: 1788
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

void findPrime(int N, vector<bool>& isPrime)
{
    isPrime.assign(N+1, true);
    isPrime[0] = isPrime[1] = false;
    for(int i=2; i*i<=N; i++){
        if(isPrime[i]){
            for(int j=i; i*j<=N; j++){
                isPrime[i*j] = false;
            }
        }
    }
}

int main()
{
    vector<bool> isPrime;
    findPrime(200000, isPrime);

    int x;
    cin >> x;
    while(!isPrime[x])
        ++ x;
    cout << x << endl;

    return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main(int argc, char *argv[]) {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int n; cin >> n;
    int cnt1 = 0, cnt2 = 0;
    rep(i, n) {
        int a; cin >> a;
        if (a % 4 == 0) cnt1++;
        else if (a % 2 == 0) cnt2++;
    }
    cnt1 += cnt2 / 2;
    if (cnt1 >= n/2) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int H, W;
    cin >> H >> W;
    vector<vector<char>> G(H, vector<char> (W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> G[i][j];
        }
    }
    queue<iint> q;
    vector<vector<int>> A(H, vector<int> (W));
    vector<int> x(4);
    vector<int> y(4);
    x[0] = 1;
    x[1] = -1;
    x[2] = 0;
    x[3] = 0;
    y[0] = 0;
    y[1] = 0;
    y[2] = 1;
    y[3] = -1;
    int h, w, tmp, ans;
    ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if(G[i][j] == '#') continue;
            for (int k = 0; k < H; k++) {
                fill(ALL(A[k]), -1);
            }
            q.push(make_pair(i, j));
            A[i][j] = 0;
            while(!q.empty()){
                h = q.front().first;
                w = q.front().second;
                q.pop();
                for (int k = 0; k < 4; k++) {
                    if(h+x[k]<H&&h+x[k]>=0&&w+y[k]<W&&w+y[k]>=0){
                        if(A[h+x[k]][w+y[k]] != -1) continue;
                        if(G[h+x[k]][w+y[k]] == '.'){
                            A[h+x[k]][w+y[k]] = A[h][w] + 1;
                            q.push(make_pair(h+x[k], w+y[k]));
                        }
                    }
                }
            }

            tmp = 0;
            for (int k = 0; k < H; k++) {
                for (int l = 0; l < W; l++) {
                    tmp = max(tmp, A[k][l]);
                }
            }
            ans = max(ans, tmp);

        }
    }
    printf("%d\n", ans);


}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

ll f(int n){
    ll res = 1;
    while(n--){
        res = (res * 2)%MOD;
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    if(n%2){
        ll ans = 0;
        vi a((n+1)/2);
        rep(i,n){
            int b;
            cin >> b;
            b /= 2;
            a[b]++;
        }
        if(a[0]>=2){
            cout << 0 << endl;
            return 0;
        }
        for(int i=1;i<a.size();i++){
            if(a[i]!=2){
                cout << 0 << endl;
                return 0;
            }
        }
        cout << f((n+1)/2-1) << endl;
    }else{
        vi a(n/2);
        rep(i,n){
            int b;
            cin >> b;
            b /= 2;
            a[b]++;
        }
        for(int i=0;i<a.size();i++){
            if(a[i]!=2){
                cout << 0 << endl;
                return 0;
            }
        }
        cout << f(n/2) << endl;
    }
}

Measured memory_bytes: 384
#include <cstdio>
using namespace std;
int main(void){
	int A,B;
	char op;
	scanf("%d %c %d",&A,&op,&B);
	if(op == '+'){
		printf("%d\n",A+B);
	};
    if(op =='-'){
		printf("%d\n",A-B);
	};
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59



int main(){
  ll i,j;
  ll n,k;
  cin>>n>>k;
  if(k!=1) cout<<n-k<<endl;
  else cout<<0<<endl;
  return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
use std::str::FromStr;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input {(source=$s:expr,$($r:tt)*) => {let mut iter=$s.split_whitespace(); let mut next=||{iter.next().unwrap()}; input_inner! {next,$($r)*}};($($r:tt)*) => {let stdin=std::io::stdin();let mut bytes=std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next=move||->String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()}; input_inner! {next,$($r)*}};}
#[allow(unused_macros)]
macro_rules! input_inner {($next:expr) => {}; ($next:expr,) => {}; ($next:expr,$var:ident:$t:tt$($r:tt)*) => {let $var=read_value!($next,$t); input_inner! {$next$($r)*}};}
#[allow(unused_macros)]
macro_rules! read_value {($next:expr,($($t:tt),*)) => {($(read_value! ($next,$t)),*)}; ($next:expr, [$t:tt; $len:expr]) => {(0..$len).map(|_|read_value! ($next,$t)).collect::<Vec<_>>()}; ($next:expr,chars) => {read_value! ($next,String).chars().collect::<Vec<char>>()}; ($next:expr,usize1) => {read_value! ($next,usize)-1}; ($next:expr,$t:ty) => {$next().parse::<$t>().expect("Parse error")};}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

#[allow(dead_code)]
const MAX: usize = 100006;
#[allow(dead_code)]
const INF_U32: u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32: i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64: u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64: i64 = 1 << 62;
#[allow(dead_code)]
const MOD: i64 = 1e9 as i64 + 7;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(unused_imports)]
use std::f64;


fn main() {
    input!{n:usize, a:[(i64,i64);n]};
    let mut crt = 0i64;
    for i in (0..n).rev() {
        if (a[i].0 + crt) % a[i].1 == 0 {continue;}
        let d = ((a[i].0 + crt) / a[i].1 + 1) * a[i].1 - (a[i].0 + crt);
        crt += d;
        //debug!(i,a[i],d,crt);
    }
    println!("{}", crt);
}


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

const int MOD = 1000000007;
const int INF = 1e9;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n, i##_len=(n); i>=0; i--)
#define FOR(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
} 

int main(){
int N;
cin >> N;
vector<double> A(N);
REP(i, N) cin >> A[i];

double bo = 0;
REP(i, N){
bo += 1 / A[i];
}

double ans = 1 / bo;

cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(final String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] X = new int[N];
		int[] Y = new int[N];
		for(int i = 0; i < N; i++) {
			X[i] = sc.nextInt();
			Y[i] = sc.nextInt();
		}
		sc.close();

		// N個の町を訪れる経路の通りパターン数の取得
		Integer[] perm = new Integer[N];
		for(int i = 0; i < N; i++) {
			perm[i] = i + 1;
		}
		List<List<Integer>> permList = Permutation.get(perm);

		double sum = 0.0;
		int size = permList.size();

		// N個の町を訪れる経路の通りパターンから距離の計算
        for (List<Integer> comb : permList) {
			int x1 = Integer.MAX_VALUE;
			int y1 = Integer.MAX_VALUE;
			for(Integer c : comb) {
				if(x1 == Integer.MAX_VALUE && y1 == Integer.MAX_VALUE) {
					x1 = X[c - 1];
					y1 = Y[c - 1];
					continue;
				}
				int x2 = X[c - 1];
				int y2 = Y[c - 1];
				double xy = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
				sum += xy;
				// System.out.println("sum " + sum + " xy = " + xy + " : " + x1 + " " + x2 + " " + y1 + " " + y2);
				x2 = x1;
				y2 = y1;
			}
        }
		System.out.println(sum / size);
	}
}
/**
 * 順列生成
 */
class Permutation {

    /**
     * 順列のリストを返す
     * 
     * @param <T>
     * @param data 生成元配列
     * @return 順列リスト
     */
    public static <T> List<List<T>> get(final T[] data) {
		return permutation(data);
	}

    /**
     * 順列のリストを出力する
     * 
     * @param <T>
     * @param data 生成元配列
     */
    public static <T> void print(final T[] data) {
        int number = 0;
        for (final List<T> comb : permutation(data)) {
            System.out.println("#" + ++number + " " + Arrays.asList(comb));
        }
	}
    
    /**
     * 順列リストを作成する
     * @param <T>
     * @param data 生成元配列
     * @return 順列リスト
     */
    private static <T> List<List<T>> permutation(final T[] data) {
        final List<List<T>> result = new ArrayList<List<T>>();
		// 候補の配列
		final List<T> candidate = new ArrayList<>(Arrays.asList(data));
		// 順列の配列
		final List<T> perm = new ArrayList<>();
		permutation(candidate, perm, result);
        return result;
    }
	
    /**
     * 再帰呼び出し
     * @param <T>
     * @param candidate 候補の配列
     * @param perm 順列の配列
     * @param result 順列のリスト
     */    
    private static <T> void permutation(final List<T> candidate, final List<T> perm, final List<List<T>> result) {
		if(candidate.size() == 0) {
			result.add(perm);
		}
		for(int i = 0; i < candidate.size(); i++) {
			final List<T> p = new ArrayList<>(perm);
			final List<T> c = new ArrayList<>(candidate);
			p.add(c.get(i));
			c.remove(i);
			permutation(c, p, result);
		}
	}
}

Measured memory_bytes: 45544
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

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

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

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

	int a, b;
	cin >> a >> b;
	if (b * 2 >= a)
		cout << 0;
	else
		cout << a - b * 2;
}



Measured memory_bytes: 256
n = int(input())
comfort = 0
alist = list(map(int,input().split()))
alist.sort(reverse = True)
comfort += alist[0]
for i in range(1,int(n/2)):
	comfort += alist[i]*2
if n%2 ==1:
	comfort += alist[int((n-1)/2)]
print(comfort)


Measured memory_bytes: 31732
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import defaultdict
import sys
import math
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


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

# a/b の切り上げ


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    x = int(input())
    a = 100
    for i in range(4000):
        a = a * 1.01
        a = int(a)
        if a >= x:
            print(i+1)
            sys.exit()


if __name__ == '__main__':
    main()


Measured memory_bytes: 68132
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int n;
	cin>>n;
	string s;
	cin>>s;
     int arr[26];int brr[26];
     int m = 0;
	for(int  i = 1;i<n;i++)
	{
         memset(arr,0,sizeof arr);
         memset(brr,0,sizeof brr);

         for(int j = 0;j<i;j++)
         	arr[(s[j]-'a')] = 1;
         for(int j = i;j<n;j++)
         	brr[(s[j]-'a')] = 1;

         int tot = 0;

         for(int  i = 0;i<26;i++)
         	if(arr[i]==1 && brr[i]==1)
         		tot++;

          m  = max(m,tot);
	}
	cout<<m<<endl;
}

Measured memory_bytes: 3568
def z_algo(s):
    """https://www.youtube.com/watch?v=f6ct5PQHqM0
    """
    n = len(s)
    ret = [0] * n

    ref_frm, ref_tail = -1, -1  # 一番末尾まで探索したケースの起点と終点
    for frm in range(1, n):
        cont = max(0, min(ret[frm - ref_frm], ref_tail - frm)) if ~ref_frm else 0

        while (frm + cont < n) and (s[cont] == s[frm + cont]): cont += 1
        ret[frm] = cont
        if ref_tail < frm + cont:
            ref_tail = frm + cont
            ref_frm = frm
    ret[0] = n
    return ret


def main():
    N = int(input())
    S = input()

    ret = 0
    t = ''
    for c in reversed(S):
        # zalgoは[0,i]の比較で
        # 先頭が固定されているので
        # 末尾から文字を増やしていくことで
        # 先頭をSの各文字にしている
        t = c + t
        lcp = z_algo(t)
        for diff, len_ in enumerate(lcp):
            ret = max(ret, min(diff, len_))
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 55004
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
typedef pair<int, int> P;
const int mod = 1e9 + 7, inf = 1e16;

int modpow(int x, int n) {
	if (n == 0) return 1;
	if (n % 2) return (x * modpow(x * x % mod, n / 2) % mod + mod) % mod;
	return (modpow(x * x % mod, n / 2) + mod) % mod;
}

int fact(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= (i + 1);
		ans %= mod;
	}
	return (ans + mod) % mod;
}

int comb(int n, int r) {
	if (n < r) swap(n, r);
	if (n - r < r) r = n - r;
	return fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) % mod;
}

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

template <typename T>
void greater_sort(vector<T>& vec) {
	sort(all(vec), greater<T>());
	return;
}

int n;
int a[114514], l[114514], r[114514];
int ans = 0;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	l[0] = a[0];
	r[n - 1] = a[n - 1];
	rep(i, n - 1) {
		l[i + 1] = gcd(l[i], a[i + 1]);
	}
	Rep(i, n - 1) {
		r[i] = gcd(r[i + 1], a[i]);
	}
	rep(i, n) {
		if (i == 0) {
			ans = r[i + 1];
		}
		else if (i == n - 1) {
			ans = max(ans, l[i - 1]);
		}
		else {
			ans = max(ans, gcd(l[i - 1], r[i + 1]));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
def read():
    A, B, C = map(int, input().split(' '))
    K = int(input())
    return A, B, C, K


def fun(A, B, C, K):
    # A ... 赤
    # B ... 緑
    # C ... 青
    # A < B * 2^i
    # B < C * 2^j
    for i in range(K + 1):
        j = K - i
        if A < B * (2**i) and B * (2 ** i) < C * (2 ** j):
            return True
    return False


if __name__ == '__main__':
    A, B, C, K = read()
    print('Yes' if fun(A, B, C, K) else 'No')
        

Measured memory_bytes: 61848
# -*- coding: utf-8 -*-

s = input()

fl = True
for i in range(len(s)):
    if i % 2 == 0:
        if s[i] != 'h':
            fl = False
    else:
        if s[i] != 'i':
            fl = False
            
if len(s) % 2 == 1:
    fl = False

if fl:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 40236
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {
    ll n,l[10];
    std::cin >> n;
    ll sum = 0;
    ll m = 0;
    for (int i = 0; i < n;   i++) {
        std::cin >> l[i];
        sum+=l[i];
        m = max(m,l[i]);
    }
    if(m<sum-m){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
    
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double ldb;

int main(void)
{
	int l;
	scanf("%d",&l);
	ldb n = (ldb)l/3;
	printf("%.20lf",(double)(n*n*n));
	return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#include <queue>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int n,k,a[100005],minn=0x7f7f7f7f;
int main()
{
	fast;
	cin>>n>>k;
	for (int i=1;i<=n;i++)
	   cin>>a[i];
	sort(a+1,a+n+1);
	for (int i=1;i<=n-k+1;i++)
	   {
	   	   int j=i+k-1;
		   if (abs(a[j]-a[i])<minn)
	   	   {
	   	   	  minn=abs(a[i]-a[j]);
	   	   }
	   }
	cout<<minn<<endl;
    return 0;
}

Measured memory_bytes: 640
N,M,K=map(int,input().split())
m=998244353
max_n=4*10**5
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
a=0
for i in range(K+1):
    a=(a+M*pow(M-1,N-1-i,m)*comb(N-1,N-i-1))%m
print(a)

Measured memory_bytes: 56332
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<set>
 
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
#define PP(p) cout<<(p)<<" ";
#define INF 1e18

typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
//int dy[8]={1,1,1,0,-1,-1,-1,0};
//int dx[8]={-1,0,1,1,1,0,-1,-1};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    string S;
    cin>>K;
    cin>>S;
    if(S.size()<=K)cout<<S<<endl;
    else{
        rep(i,K)cout<<S[i];
        cout<<"..."<<endl;
    }
    return 0;
}


Measured memory_bytes: 3600
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] array = new boolean[(int) (1e9 + 1)];
		for (int i = 0; i < n; ++i) {
			array[sc.nextInt()] = true;
		}
		int m = sc.nextInt();
		for (int i = 0; i < m; ++i) {
			array[sc.nextInt()] = true;
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < array.length; i++) {
			if (array[i]) {
				sb.append(i);
				sb.append('\n');
			}
		}
		System.out.print(sb.toString());
	}
}



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

const string YES = "YES";
const string NO = "NO";

void solve(long long A, long long B, long long C){
    if (A * B * C == 5 * 5 * 7 && A + B + C == 5 + 5 + 7) cout << YES << endl; else cout << NO << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}


Measured memory_bytes: 3604
import java.util.*;

class Main{
    public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		long iix = sc.nextLong();
		long iiy = sc.nextLong();
        int retint = 0;
        for(long i=iix;i<=iiy;i*=2){
            retint++;
        }
		System.out.println(retint);
    }
}


Measured memory_bytes: 23892
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
using namespace std;
#define INF 1LL << 61
#define MAX 1LL << 30
#define MOD 1000000007
typedef long long ll;
//typedef pair<ll,ll> P;
//typedef pair<pair<int,int>,int> p;
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());
//#define int ll
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(true){
        int N,M;
        cin>>N>>M;
        if(N==0 && M==0){
            return 0;
        }
        int sumT=0,sumH=0;
        int T[310],H[310];

        for(int i=0;i<310;i++){
            T[i]=0;
            H[i]=0;
        }

        for(int i=0;i<N;i++){
            int t; cin>>t;
            T[t]++;
            sumT+=t;
        }
        for(int i=0;i<M;i++){
            int t; cin>>t;
            H[t]++;
            sumH+=t;
        }
        if(abs(sumT-sumH)%2==1 || abs(sumT-sumH)>200){
            cout<<-1<<endl;
            continue;
        }
        int ans=-1;
        if(sumT>=sumH){
            int x=sumT-sumH;
            x/=2;
            for(int i=100;i>=0;i--){
                if(T[i+x] && H[i]) ans=i;
            }
            if(ans==-1) cout<<-1<<endl;
            else cout<<ans+x<<" "<<ans<<endl;
        }else{
            int x=sumH-sumT;
            x/=2;
            for(int i=100;i>=0;i--){
                if(H[i+x] && T[i]) ans=i;
            }
            if(ans==-1) cout<<-1<<endl;
            else cout<<ans<<" "<<ans+x<<endl;
        }
    }
}



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

#include <algorithm>
#include <array>
#include <chrono>
#include <cstdio>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

#define ll long long
#define ld long double
#define P pair<ll, ll>
#define FOR(i, n, m) for (ll i = n; i < (ll)m; i++)
#define FORr(i, m, n) for (ll i = n; i >= (ll)m; i--)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define sortAl(v) sort(v.begin(), v.end())
#define sortAlr(v)          \
  sort(v.begin(), v.end()); \
  reverse(v.begin(), v.end())
#define cout(n) cout << fixed << setprecision(n)

int main() {
  ll N;
  ll s = 0;
  cin >> N;

  ll n = N;
  while (n) {
    s += n % 10;
    n /= 10;
  }

  if (N % s) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
from collections import deque

N = int(input())

L = [[] for i in range(N)]

for i in range(N-1) :
    u,v,w = map(int,input().split())
    
    u -= 1
    v -= 1
    
    L[u].append([v,w])
    L[v].append([u,w])

ans = [-1 for i in range(N)]
ans[0] = 0

q = deque()
q.append(0)

while q :
    a = q.popleft()
    
    for b,w in L[a] :
        if ans[b] == -1 :
            ans[b] = (ans[a] + w) % 2
            q.append(b)

print(*ans, sep="\n")


Measured memory_bytes: 46872
#include <stdio.h>

int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
		if(i*j+(n-i)*(m-j)==k){
			puts("Yes");
			return 0;
		}
	}
	puts("No");
}


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



int main() {
    string s,t;
    cin>>s>>t;
    vector<vector<int>> list(26,vector<int>(0));
    rep(i,s.size()){
        list.at(s.at(i)-'a').push_back(i+1);
    }
    int count=0,num=0;//何周目、何番目のsを考えているか
    rep(i,t.size()){
        int x=t.at(i)-'a';
        int y=list.at(x).size();
        if(y==0){cout<<-1<<endl;return 0;}
        if(list.at(x).at(y-1)<=num){count++;num=list.at(x).at(0);}
        else{
            num=lower_bound(list.at(x).begin(),list.at(x).end(),num+1)-list.at(x).begin();
            num=list.at(x).at(num);
        }
    }
    ll ans=s.size()*count+num;
    cout<<ans<<endl;
/*cout<<count<<" "<<num<<endl;
rep(i,26){
        rep(j,list.at(i).size()){
            cout<<list.at(i).at(j)<<" ";
        }
        cout<<endl;
}*/

    return 0;
}


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

using namespace std;
typedef long long ll;
//ループ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//コンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define D()
//定数
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    int n, buf;
    cin >> n;
    vector<int> a(n);
    REP(i,n-1) {cin >> buf; a.at(buf-1)++;}

    REP(i,n){
        cout << a.at(i) << endl;
    }
}

Measured memory_bytes: 4016
import sys

def solve1(s):
    n = len(s)
    i = 0
    while i <= n // 2:
        if s[n // 2] != s[n // 2 - i]:
            break
        if s[(n - 1) // 2] != s[(n - 1) // 2 + i]:
            break
        i += 1
    return (n - 1) // 2 + i


line = sys.stdin.readline().strip()
print(solve1(list(line)))


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

#define lint long long
#define P pair<int, int>

int main()
{
    int N;

    cin >> N;

    vector<P> R;
    vector<P> B;

    for(int i = 0; i < N; ++i){
        int a, b;
        cin >> a >> b;
        R.push_back(make_pair(a, b));
    }
    for(int i = 0; i < N; ++i){
        int a, b;
        cin >> a >> b;
        B.push_back(make_pair(a, b));
    }

    sort(R.begin(), R.end());
    sort(B.begin(), B.end());

    for(int i = 0; i < N; ++i){

    }

    vector<bool> used(N, false);

    int cnt = 0;

    for(auto e : B){
        int x, y;
        x = e.first; y = e.second;

        // cout << x << " " << y << " ";

        int pos = -1;
        int Y = -1;

        for(int i = 0; i < N; ++i){
            if(used[i] == true){
                continue;
            }
            if(R[i].first >= x){
                break;
            }
            
            if(R[i].second >= y){
                continue;
            }

            if(R[i].second >= Y){
                pos = i;
                Y = R[i].second;
                // cout << R[i].first << " " << R[i].second << " ";
            }
        }

        if(pos > -1){
            ++cnt;
            used[pos] = true;
        }

        // cout << endl;
    }

    cout << cnt << endl;




}

Measured memory_bytes: 256
n,x = map(int,input().split())
a = list(map(int,input().split()))
if a[0] > x:
  cost = a[0]-x
  a[0] = x
else:
  cost = 0
for i in range(1,n):
  if a[i]+a[i-1] > x:
    cost += (a[i]+a[i-1])-x
    a[i] = x-a[i-1]
print(cost)

Measured memory_bytes: 14252
def solve():
    from sys import stdin
    f_i = stdin
    
    ans = []
    while True:
        n = int(f_i.readline())
        if n == 0:
            break
        
        last_day = 1
        schedule = [set() for i in range(31)]
        
        for i in range(n):
            line = map(int, f_i.readline().split())
            f = next(line)
            
            for day in line:
                schedule[day].add(i)
                if day > last_day:
                    last_day = day
        
        groups = [set() for i in range(n)]
        for day in range(1, last_day + 1):
            member1 = schedule[day]
            member2 = member1.copy()
            for person in member1:
                member2 |= groups[person]
            
            if len(member2) == n:
                ans.append(day)
                break
            for person in member1:
                groups[person] |= member2
        else:
            ans.append(-1)
    
    print('\n'.join(map(str, ans)))

solve()


Measured memory_bytes: 5924
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

int main(){
  ll N; cin >> N;
  vector<ll> a(N); vector<ll> b(N);
  rep(i,N) cin >> a[i] >> b[i];

  SORT(a); SORT(b);
  ll ans = 0;
  // 奇数の時は簡単、それぞれの真ん中の点の時の間の数の個数
  if(N % 2 == 1){
    ll d = a[N / 2];
    ll u = b[N / 2];
    ans = u - d + 1;
    // if(ans < 0) ans = 0;
  }
  else{
    ll dd = a[N / 2 - 1];
    ll du = a[N / 2];
    ll ud = b[N / 2 - 1];
    ll uu = b[N / 2];
    ll nd = (dd + du);
    ll nu = (uu + ud);
    ans = nu - nd + 1;
    // if(ans < 0) ans = 0;
  }
  cout << ans << endl;
}


Measured memory_bytes: 6360
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};

int main () {
    int n; cin >> n;
    vector<ll> cnt(1e5+10);
    ll s = 0;
    rep(i, n) {
        int a; cin >> a;
        s += a;
        cnt[a] ++;
    }
    int q; cin >> q;
    rep(i, q) {
        ll b, c; cin >> b >> c;
        if (cnt[b] == 0) {
            cout << s << endl;
            continue;
        }
        s += (c - b) * cnt[b];
        cnt[c] += cnt[b];
        cnt[b] = 0;
        cout << s << endl;
    }
    return 0;
}

Measured memory_bytes: 4020