akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[]) {

        deque<int>que;
        int q, query, d, x, p;

        cin >> q;

        for(int i = 0; i < q; i++) {
                cin >> query;
                switch (query) {
                case 0:
                        cin >> d >> x;
                        if(d == 0) que.push_front(x);
                        else que.push_back(x);
                        break;
                case 1:
                        cin >> p;
                        cout << que[p] << endl;
                        break;
                case 2:
                        cin >> d;
                        if(d == 0) que.pop_front();
                        else que.pop_back();
                        break;

                }
        }
        return 0;
}



Measured memory_bytes: 4528
N,M=map(int,input().split())
li=[list(map(int,input().split())) for _ in range(M)]
zero=["0"]*N
flag=0
for i in range(M):
  order=li[i][0]-1
  if zero[order]=="0" or zero[order]==li[i][1]:
    zero[order]=li[i][1]
    if order==0 and li[i][1]==0 and N!=1:
      flag=1
  else:
    print(-1)
    exit()
a=[str(s) for s in zero]
if a[0]=="0" and flag==1:
  print(-1)
  exit()
if a[0]=="0" and N!=1:
  a[0]="1"
a2="".join(a)
a3=int(a2)
a4=str(a3)
if len(a2)!=len(a4):
  print(-1)
  exit()
print(a2)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAX 300005
const int maxk = 1e6+5;
bool a[maxk];
int main() {
    LL k;
    cin>>k;

    int x = 7;
    int ans = -1;
    int c = 1;
    while(!a[x % k]){
        if(x % k == 0){
            ans = c;
            break;
        }
        a[x % k] = 1;
        c++;
        x = x * 10 + 7;
        x %= k;
    }

    cout<<ans<<endl;

}

Measured memory_bytes: 4500
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
    }
    map<int,int> p;
    rep(i,n){
        if(p[a[i]]==0){
            p[a[i]]++;
        }
        else{
            p[a[i]]--;
        }
    }
    int ans=0;
    for(auto c:p){
        int count = c.second;
        if(count){
            ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
//#define   Y            imag()
//#define   X            real()
#define    clr(v,d)      memset( v, d ,sizeof(v))
#define   angle(n)      atan2((n.imag()),(n.real()))
#define   vec(a,b)       ((b)-(a))
#define   length(a)      hypot( (a.imag()),(a.real()) )
#define   normalize(a)      (a)/(length(a))
#define    dp(a,b)          (((conj(a))*(b)).real())
#define    cp(a,b)          (((conj(a))*(b)).imag())
#define    lengthsqrt(a)       dp(a,a)
#define    rotate0( a,ang)    ((a)*exp( point(0,ang) ))
#define    rotateA(about,p,ang)   (rotate0(vec(about,p),ang)+about)
#define    lcm(a,b)                ((a*b)/(__gcd(a,b)))
#define    reflection0(m,v)         (conj((v)/(m))*(m))
#define     reflectionA(m,v,p0)     (conj( (vec(p0,v))/(vec(p0,m)) ) * (vec(p0,m)) ) + p0
#define     same(p1,p2)               ( dp(  vec(p1,p2),vec(p1,p2)) < eps )
#define     point                    complex<double>
#define     PI                       acos(-1)
#define outfile freopen("out.out", "w", stdout);
#define infile  freopen("in.in", "r", stdin);
typedef  long long     ll ;
typedef  unsigned long long ull;
const double eps= (1e-9);
using namespace std;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
int getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1;}
int setBit1(int num, int idx) {return num | (1<<idx);}
ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}
void GO(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
int countNumBit1(int mask) {int ret=0; while (mask) 	{mask &= (mask-1);++ret;	}return ret;}
const int N=200000+9;
vector<ll> v;
ll k,n;
ll calc(int id){

   if(id<n-1){

    ll p1= v[n-1]-v[id]+(id==0?0:(k-v[n-1])+v[id-1]);
    return p1;
   }
   else{
    return (id==0?0:(k-v[n-1])+v[id-1]);
   }
}
int main(){
    GO();

    cin>>k>>n;

    for(int i=1;i<=n;i++){
        ll no;
        cin>>no;
        v.pb(no);
    }
    ll mi=1e13;
    for(int i=0;i<n;i++){

        mi=min(mi,calc(i));
    }
    cout<<mi<<endl;

}













































































































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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
  string s;
  getline(cin,s);
  vector<ll> v;
  ll l = s.size();
  for(int i = 0; i < l; i++){
    v.push_back((ll)(s[i]-'0'));
  }
  int K;
  cin>>K;
  ll ans = 0LL;
  if(K==1){
    ans+=9LL*(l-1LL)+v[0];
  }
  if(K==2&&l>=2){
    ans+=81LL*(l-1LL)*(l-2LL)/2LL+(v[0]-1LL)*(l-1LL)*9LL;
    int p = l-1LL;
    for(int i = 1; i < l; i++){
      if(v[i]!=0LL){
        p=i;
        break;
      }
    }
    ans+=9LL*(l-(p+1LL))+v[p];
  }
  if(K==3&&l>=3){
    ans+=9LL*9LL*9LL*(l-1LL)*(l-2LL)*(l-3LL)/6LL+(v[0]-1LL)*(l-1LL)*(l-2LL)*81LL/2LL;
    int p=l-1LL,q=l-1LL;
    for(int i = 1; i < l; i++){
      if(v[i]!=0LL){
        p=i;
        break;
      }
    }
    for(int i = p+1LL;i<l;i++){
      if(v[i]!=0LL) {
        q=i;
        break;
      }
    }
    ans+=81LL*(l-(p+1LL))*(l-(p+2LL))/2LL+(v[p]-1LL)*(l-(p+1LL))*9LL;
    ans+=9LL*(l-(q+1LL))+v[q];
  }
  cout<<ans<<endl;
}
  

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

int main() 
{
      int n;
      cin>>n;
      int arr[n+1];
      for(int i=1; i<=n;i++)
      cin>>arr[i];
      if(n==0 || n==1)
        cout<<0<<endl;
      else  
      {int dp[n+1];
      dp[0]=1,dp[1]=0,dp[2]=abs(arr[2]-arr[1]);
      
      for(int i=3; i<=n; i++)
        dp[i]=min(dp[i-2]+abs(arr[i]-arr[i-2]), dp[i-1]+abs(arr[i]-arr[i-1]));
        
        cout<<dp[n]<<endl;
        
      }  
        return 0;
}

Measured memory_bytes: 4388
def main():
    n, *a = map(int, open(0).read().split())
    p, q = min(a), max(a)

    if p == q:
        print(0)
        exit()

    x = []
    f, g = a.index(p) + 1, a.index(q) + 1
    if abs(p) > abs(q):
        for i in range(n):
            if a[i] > 0:
                x.append((f, i + 1))
        for i in range(n - 1):
            x.append((n - i, n - i - 1))

    else:
        for i in range(n):
            if a[i] < 0:
                x.append((g, i + 1))
        for i in range(n - 1):
            x.append((i + 1, i + 2))

    print(len(x))
    y = ['{} {}'.format(i[0], i[1]) for i in x]
    print('\n'.join(y))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9136
#include <iostream>
#define N 100005
using namespace std;

int main() {
	// your code goes here
	
	int n,num,f[N]={},i,ans=0;
	
	cin>>n;
	
	for(i=0;i<n;i++)  
	{
	    cin>>num;
	    f[num+1]++;
	}
	
	for(i=1;i<N-1;i++)
	{
	    ans=max(ans,f[i-1]+f[i]+f[i+1]);
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;
#define ll long long
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define PRINT(item) cout << (item) << endl;
#define PRINT_VEC(V) \
    for (auto v : (V)) cout << v << ' ';
const int MOD = 1000000007;
/* cout << fixed << setprecision(10) << decimal << endl; */

int main() {
    /* code */
    int N, M;
    cin >> N >> M;
    int ans = 0;
    if (N >= 2) {
        int Nbi = 1;
        FOR(i, 0, 2) { Nbi *= (N - i); }
        Nbi /= 2;
        ans += Nbi;
    }
    if (M >= 2) {
        int Mbi = 1;
        FOR(i, 0, 2) { Mbi *= (M - i); }
        Mbi /= 2;
        ans += Mbi;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
g = [i for i in range(n)]
for i in range(n):
    g[i] = a[i]-1
dist =[-1]*n
dist[0] = 0
q = deque([0])
hajimari = -1
loopnum = -1
while q:
    v = q.popleft()
    u = g[v]
    if dist[u] == -1:
        dist[u] = dist[v]+1
        q.append(u)
    else:
        hajimari = u
        loopnum = dist[v] + 1 - dist[u]
        break
    if hajimari != -1:
        break
if k <= dist[hajimari]:
    now = 0
    for _ in range(k):
        now = g[now]
    print(now+1)
else:
    now = hajimari
    for _ in range((k-dist[hajimari])%loopnum):
        now = g[now]
    print(now+1)

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

typedef pair<int,int> P;

const int MAX = 1000, INF = 100000000;
char map[MAX][MAX+1];
int H, W, N;
int sx, sy;
int gx, gy;
int steps;
int d[MAX][MAX];

const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

int bfs(){
	for(int i = 0; i < H; i++)
		for(int j = 0; j < W; j++) d[i][j] = INF;
	
	queue<P> que;
	que.push(P(sx,sy));
	d[sx][sy] = 0;
	
	while(que.size()){
		P p = que.front(); que.pop();
		
		if(p.first == gx && p.second == gy) break;
		
		for(int i = 0; i < 4; i++){
			int nx = p.first + dx[i], ny = p.second + dy[i];
			if(nx >= 0 && nx < H && ny >= 0 && ny < W && map[nx][ny] != 'X' 
			&& d[nx][ny] == INF){
				que.push(P(nx,ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
	}
		
	return d[gx][gy];
}

int main(){
	cin >> H >> W >> N;
	for(int i = 0; i < H; i++)
		cin >> map[i];
	
	steps = 0;
	int n = 0;
	while(n < N){
		for(int i = 0; i < H; i++)
			for(int j = 0; j < W; j++){
				if((map[i][j] == 'S' && n == 0) || map[i][j] == n + '0'){
					sx = i; sy = j;
				}
				if(map[i][j] == n + 1 + '0'){
					gx = i; gy = j;
				}
			}
		
		steps += bfs();
		n++;
	}
	cout << steps << endl;
	return 0;
}


Measured memory_bytes: 8008
/*
  第4回ユニリタプログラミングコンテスト～練習サイト～
  C言語用
  ファイル名 qA.c
  作成者 228 金子幸裕 2017/06/13 17:30
  ※long long 型 は 旧式のコンパイラでは対応していない
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

int main( void )
{
    long long int na, nb, nc;
    long long int ntmp;

    scanf( "%lld %lld %lld" , &na, &nb, &nc );

    if ( na > nb )
    {
        /* ab 入れ替え */
        ntmp = na;
        na   = nb;
        nb   = ntmp;
    }

    if ( nb > nc )
    {
        /* bc 入れ替え */
        ntmp = nb;
        nb   = nc;
        nc   = ntmp;
    }

    /* ここで nc に最大値が入っている */

    if ( na % 2 == 0 || nb % 2 == 0 || nc % 2 == 0 )
    {
        printf("%lld", 0);
    }
    else
    {
        ntmp = na * nb;
        printf("%lld", ntmp);
    }

    printf("\n");

    return ( 0 );

}


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

int main() {
  int N; cin>>N;
  int sum=0;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec.at(i);
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  int x=0;
  for(int i=1;i<N;i++){
    x+=vec.at(i);
  }
  if(x>vec.at(0)){
    cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;
}


 



Measured memory_bytes: 3640
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<bitset>
#define int long long
#define lowbit(x) ((x)&(-x))
#define hh putchar('\n')
#define kg putchar(' ')
using namespace std;
const int maxn=10005,mod=20101009;
int n,k,vis[maxn],ans;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
		if(ch=='-')
			f=-1;
		ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
    }
    return x*f;
}
inline void write(int a)
{
    if(a<0)
    {
		putchar('-');
		putchar('1');
    }
    else
    {
		if(a>=10)
			write(a/10);
		putchar(a%10+'0');
    }
}
signed main()
{
	n=read(),k=read();
	for(int i=1;i<=k;++i)
	{
		int x=read();
		while(x--)
		{
			int t=read();
			vis[t]=1;
		}
	}
	for(int i=1;i<=n;++i)
		ans+=(!vis[i]);
	write(ans);
	return 0;
}


Measured memory_bytes: 3600
#include <array>
#include <iostream>

int main() {
  std::array<std::array<int32_t, 3>, 3> C;
  std::cin >> C[0][0] >> C[0][1] >> C[0][2];
  int32_t b01 = C[0][1] - C[0][0], b12 = C[0][2] - C[0][1];
  for (size_t i = 1; i < C.size(); i++) {
    std::cin >> C[i][0] >> C[i][1] >> C[i][2];
    if (C[i][1] != C[i][0] + b01 || C[i][2] != C[i][1] + b12) {
      std::cout << "No" << std::endl;
      return 0;
    }
  }

  std::cout << "Yes" << std::endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define res register int
#define inf 0x3f3f3f3f
using namespace std;
int s, t; 
inline int read(){
    res w = 0, X = 0; register char ch = 0;
    while(!isdigit(ch)){w |= ch == '-'; ch = getchar();}
    while(isdigit(ch)){X = (X << 1) + (X << 3) + (ch ^ 48); ch = getchar();}
    return w ? -X : X;
}
int main(){
	cin >> t >> s;
	t--;
	s--; 
	printf("%d\n", s % t == 0 ? s / t : s / t + 1);
	return 0;
}

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

import sys

def parse_input(lines_as_string = None):

    lines = []
    if lines_as_string is None:
        lines.append(input())
        # 出力
        nm = lines[0].split(" ")
        n = int(nm[0])
        for i in range(n):
            lines.append(input())
    else:
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        nm = lines[0].split(" ")
        n = int(nm[0])

    rows = []
    for i in range(1, n+1):
        fields = lines[i].split(" ")
        rows.append((float(fields[0]), fields[1]))

    return (n, rows)

def solve(n, rows):

    result = 0.0
    for i in range(n):

        money = rows[i][0]
        unit = rows[i][1]
        k = 1
        if unit == 'BTC':
             k = 380000.0

        result += k * money


    return result

def main():

    print("%f" % solve(*parse_input()))

if __name__ == '__main__':

    main()


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

using namespace std;

#define run_forest_run ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define vi vector <int>
#define sz(a) (int)a.size()
#define fi first
#define se second
#define si set <int>
#define all(x) (x).begin(),(x).end()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
int gcd(int a,int b){if(b==0)return a;else return gcd(b,a%b);}
int lcm(int a,int b){return abs(a*b)/gcd(a,b);} 

const int inf = 1e9;	
const int mod = inf + 7;

const int N = 205000;
vector <int> g[N];
vector <bool> visited(N);
vector <int> color(N);


int n, m, q, x, y, k;
int dp[100001][3];
int ans;

int main()
{                   
	run_forest_run;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> dp[i][j];
		}
	}
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int maxi = -1;
			for (int k = 0; k < 3; k++)
			{
				if (k == j)
					continue;
				maxi = max(maxi, dp[i-1][k]);
			}
			dp[i][j] += maxi;
		}
	}
	int ans = 0;
	for (int i = 0; i < 3; i++)
	{
		ans = max(ans, dp[n-1][i]);
	}
	cout << ans;
}


Measured memory_bytes: 7040
#include<bits/stdc++.h>
#define ll long long
#define loop(n) for(ll i = 0; i<n; i++)
#define sort(a) sort(a.begin(), a.end())
using namespace std;
#define m 1000000007

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

    int rem = 0;
    string s; cin>>s;
    int n = s.size(), z = 0, o = 0;
    loop(n){
        if(s[i]=='0') z++;
        else o++;
    }

    cout<<2*min(o,z);
    return 0;
}

Measured memory_bytes: 512
package main

import (
	"bufio"
	"container/list"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()
	l := list.New()

	dir := true
	for i := 0; i < N; i++ {
		a := getInt()
		if dir == true {
			l.PushBack(a)
		} else {
			l.PushFront(a)
		}
		dir = !dir
	}

	if dir == true {
		for e := l.Front(); e != nil; e = e.Next() {
			fmt.Printf("%v ", e.Value)
		}
	} else {
		for e := l.Back(); e != nil; e = e.Prev() {
			fmt.Printf("%v ", e.Value)
		}
	}
	out()
}


Measured memory_bytes: 16916
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const double pi=acos(-1);
int main(){
  rep(k,MOD){
    int h,w;
    cin >> h >> w;
    if(h==0 && w==0) return 0;
    rep(i,w){
      cout<<'#';
    }
    cout << endl;
    
    rep(i,h-2){
      cout << '#';
      rep(j,w-2){
        cout << '.';
      }
      cout << '#';
      cout << endl;
    }
    rep(i,w){
      cout<<'#';
    }
    cout << endl;
    cout << endl;
  }
}



Measured memory_bytes: 3092
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;
long long power(int n) 
{
	int power = 1;
	for (int i = 0; i < n; i++) {
		power * 10;
	}
	return power;
}
int main()
{
	char A[10000], B[10000];
	scanf("%s%s", A, B);
	int i = 0, LA = 0, LB = 0;
	while (A[i] != '\0') {
		LA++;
		i++;
	}
	i = 0;
	while (B[i] != '\0') {
		LB++;
		i++;
	}
	i = 0;
	if (LA > LB) { printf("GREATER"); return 0; }
	else if (LA < LB) { printf("LESS"); return 0; }
	else {
		if (A[i] > B[i]) { printf("GREATER"); return 0; }
		else if (A[i] < B[i]) { printf("LESS"); return 0; }
		i++;
	}
	printf("EQUAL");
	return 0;
}

Measured memory_bytes: 128
using namespace std;
#include<iostream>
#include <string>
#include <set>
#include<algorithm>
#include<map>
#include <vector>
#include <iterator>
#include<stack>
int hans[100001];
int mod(int a, int b){
    if(a-b>0){
        return a-b;
    }
    else{
        return b-a;
    }
}
int func(int n,int hvalues[100001]){
    hans[n-2]=mod(hvalues[n-1],hvalues[n-2]);
    if(mod(hvalues[n-1],hvalues[n-3])>(mod(hvalues[n-1],hvalues[n-2])+mod(hvalues[n-3],hvalues[n-2]))){
        hans[n-3]=mod(hvalues[n-1],hvalues[n-2])+mod(hvalues[n-3],hvalues[n-2]);
    }
    else{
        hans[n-3]=mod(hvalues[n-1],hvalues[n-3]);
    }
    for(int i=n-4; i>=0;i--){
        int x=mod(hvalues[i],hvalues[i+2])+hans[i+2];
        int y=mod(hvalues[i],hvalues[i+1])+hans[i+1];
        hans[i]= x<y ? x:y;
    }
    return hans[0];
}
int main(){
    int n;
    cin>>n;
    int hvalues[n];
    for(int i=0; i<n; i++){
        cin>>hvalues[i];
    }
    cout<<func(n,hvalues);


}


Measured memory_bytes: 1024
#include <iostream>

int main() {
    int num, tmp, min, ans;
    std::cin >> num >> min;
    for(int i=1; i < num; i++){
        std::cin >> tmp;
        if(tmp - min >  ans || i  == 1){
                ans = tmp - min;
        }
        if( tmp < min ){
            min = tmp;
        }
    }
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 3100
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=500100;
inline int read(){
	int x=0,f=0,c=getchar();
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+c-'0';return f?-x:x;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);putchar(x%10+'0');
}
#include<bitset>
bitset<2000*2001>f;
int n,i,x,s;
int main(){
	//freopen("1.out","w",stdout);
	n=read();f[0]=1;
	for(i=1;i<=n;i++){
		x=read();f|=f<<x;s+=x;
	}for(i=(s+1)/2;!f[i];i++);printf("%d\n",i);
	return 0;
}

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

#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scanf("%c",&a)
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 1e5 + 10;

struct UF {
    int fa[N];

    inline void init(int n) {
        for (register int i = 1; i <= n; i++)fa[i] = i;
    }

    int get(int x) {
        return x == fa[x] ? x : (fa[x] = get(fa[x]));
    }

    inline void merge(int x, int y) {
        fa[get(x)] = get(y);
    }

    inline bool same(int x, int y) {
        return get(x) == get(y);
    }
} U;

int n, m;
bool v[N];

int main() {
    n = qr(), m = qr();
    U.init(n);
    while (m--) {
        int x = qr(), y = qr();
        U.merge(x, y);
    }
    int ans = 0;
    repi(i, 1, n) {
        int x = U.get(i);
        if (!v[x])ans++, v[x] = true;
    }
    pi(ans-1);
    return 0;
}

Measured memory_bytes: 4240
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
typedef vector<vector<int>> Mat;
const int inf = 1e9;
const int mod = 1e9 + 7;

int N, M, A, B, C, T;

Mat mulMatMat(const Mat& a, const Mat& b) {
    int n = a.size();
    int m = b[0].size();
    // assert(a[0].size() == b.size());
    Mat c(n, V(m, 0));
    rep(i, n) {
        rep(j, m) {
            rep(k, a[0].size()) {
                (c[i][j] += a[i][k] * b[k][j]) %= M;
            }
        }
    }
    return c;
}

V mulMatVec(const Mat& a, const V& v) {
    int n = a.size();
    // assert(a[0].size() == v.size());
    V c(n, 0);
    rep(i, n) {
        rep(j, a[0].size()) {
            (c[i] += a[i][j] * v[j]) %= M;
        }
    }
    return c;
}

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

    while (cin >> N >> M >> A >> B >> C >> T, N) {
        V s(N + 2);
        rep2(i, 1, N + 1) cin >> s[i];

        VV a(N + 2, V(N + 2));
        rep2(i, 1, N + 1) {
            a[i][i - 1] = A,    a[i][i] = B,    a[i][i + 1] = C;
        }

        for (; T > 0; T >>= 1) {
            if (T & 1) {
                s = mulMatVec(a, s);
            }
            a = mulMatMat(a, a);
        }

        rep2(i, 1, N + 1) {
            cout << (i != 1 ? " " : "") << s[i];
        }
        cout << endl;

    }
}

Measured memory_bytes: 3148
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
a,b,c = gets.chomp.split.map(&:to_i)

if (a==b && b!=c) || (a==c && c!=b) || (b==c && c!=a)
  puts 'Yes'
else
  puts 'No'
end


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

long long L, R;

int main(){
	cin >> L >> R;
	if(R-L > 5000){
		cout << 0 << endl;
	}else{
		long long mini = 2020;
		for(long long i = L; i <= R; i++){
			for(long long j = i+1; j <=R; j++){
				mini = min(mini, (i*j)%2019);
			}
		}
		cout << mini << endl;
	}
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdint.h>

uint64_t _gcd(int x, int y) {
        if (x == 0) {
                return y;
        }

        return _gcd(y % x, x);
}

uint64_t gcd(int x, int y) {
        if (x > y) {
                return _gcd(y, x);
        } else {
                return _gcd(x, y);
        }
}

uint64_t solve(int k) {
        int a, b, c;
        uint64_t ret = 0;
        uint64_t gcd_a_b;

        for (a = 1; a <= k; ++a) {
                for (b = 1; b <= k; ++b) {
                        gcd_a_b = gcd(a, b);
                        for (c = 1; c <= k; ++c) {
                                ret += gcd(gcd_a_b, c);
                        }
                }
        }

        return ret;
}

int main() {
        int k;
        int rc;

        rc = scanf("%d", &k);
        if (rc == 0) {
                perror("scanf");
                return 1;
        }

        printf("%lld\n", solve(k));

        return 0;
}


Measured memory_bytes: 1704
import collections

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
cnt1=collections.Counter(arr1)
cnt2=collections.Counter(arr2)
acum1=[0]*(n+1)
acum2=[0]*(n+1)
for i in range(1,n+1):
  acum1[i]=acum1[i-1]+cnt1[i]
  acum2[i]=acum2[i-1]+cnt2[i]
rotate=0
for i in range(1,n+1):
  rotate=max(rotate,acum1[i]-acum2[i-1])
ans=[0]*n
for i in range(n):
  ans[(i+rotate)%n]=arr2[i]
for i in range(n):
  if arr1[i]==ans[i]:
    print('No')
    break
else:
  print('Yes')
  print(*ans)

Measured memory_bytes: 68416
#include<bits/stdc++.h>
using namespace std;
int n,m,b[100][100];
char a[100][100];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++){
    		cin>>a[i][j];
    		if(a[i][j]=='#'){
    			b[i-1][j]++;
    			b[i+1][j]++;
    			b[i-1][j-1]++;
    			b[i-1][j+1]++;
    			b[i][j+1]++;
    			b[i][j-1]++;
    			b[i+1][j-1]++;
    			b[i+1][j+1]++;
    		}
    	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		if(a[i][j]=='#') cout<<'#';
    			else cout<<b[i][j];
    	}
    	cout<<"\n";
    }
    	
    return 0;
}


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

using namespace std;

#define ll long long
#define MOD (1000000007LL)

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

	vector<int> cnt = { 0,0,0 };
	ll ans = 1;
	for (int i = 0; i < n; ++i) {
		int c = 0;
		for (int j = 0; j < 3; ++j)
			if (cnt[j] == a[i])
				++c;
		ans *= c;
		ans %= MOD;
		for (int j = 0; j < 3; ++j) {
			if (cnt[j] == a[i]) {
				++cnt[j];
				break;
			}
		}
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

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

    string s;
    cin >> s;

    // <>>
    // keep track of net on either side
    int l = 0;
    int r = 0;
    vector<pii> rle;
    for (char c : s) {
        if (c == '<') {
            if (!rle.empty() and rle.back().first == 1) {
                rle.back().second++;
            } else {
                rle.emplace_back(1, 1);
            }
        } else {
            if (!rle.empty() and rle.back().first == -1) {
                rle.back().second++;
            } else {
                rle.emplace_back(-1, 1);
            }
        }
    }

    // {{1, 1}, {-1, 2}}
    ll ans = 0;
    int cur = 0;
    for (auto& p : rle) {
        // cout << p.first << ' ' << p.second << '\n';
        if (p.first == 1) {
            assert(cur == 0);
            // cout << 1LL * p.second * (p.second + 1) / 2 << '\n';
            ans += 1LL * p.second * (p.second + 1) / 2;
            cur = p.second;
        } else {
            if (cur < p.second) {
                ans -= cur;
                ans += p.second;
                // cout << -cur << '\n';
                // cout << p.second << '\n';
                cur = p.second;
            }

            /*
            if (cur > p.second) {
                cout << cur << '\n';
                cur = p.second--;
            }
            */

            ans += 1LL * p.second * (p.second - 1) / 2;
            // cout << 1LL * p.second * (p.second - 1) / 2 << '\n';
            cur = 0;
        }
    }

    cout << ans << '\n';

    return 0;

    // < > > > < < > < < < < < > > > <
    //0 3 2 1 0 1 2 0 1 2 3 4 5 2 1 0 1
    //
    // 1
    // -1
    // 3
    // 3
    // 3
    // 15
    // 2
    // 1
    // 1
}


Measured memory_bytes: 3352
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=1 +117;
const int MM=1 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}

const int mod=1e9+7;
int k,n;
LL fact[4*NN]={};
LL rev[4*NN]={};
char s[NN]={};
LL ksm(LL a,LL b){
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ret=a*ret%mod;
	return ret;
}
LL comp(int n,int m){
	return fact[n]*rev[m]%mod*rev[n-m]%mod;
}
void prefact(int n){
	fact[0]=1;
	for(int i=1;i<=n;++i)fact[i]=fact[i-1]*i%mod;
	rev[n]=ksm(fact[n],mod-2);
	for(int i=n;i>=1;--i){
		rev[i-1]=rev[i]*i%mod;
	}
}
int seq[NN][2]={},scnt=0;
LL ans=0;
int len[NN]={};
int pos[NN]={};
bool used[NN]={};
int rcnt=0;
int bcnt=0;
void calc(){
	int tp=0;
	for(int i=1;i<=k;++i)used[i]=0;
	for(int i=1;i<=scnt;++i){
		for(int j=1;j<=seq[i][1];++j){
			len[++tp]=seq[i][0];
			pos[tp]=0;
		}
	}
	int now=1;
	for(int i=1;i<=k;++i){
		if(!used[i]&&s[i]=='r'&&now<=tp&&pos[now]<i){
			--len[now],pos[now]=i,++now,used[i]=1;
		}
	}
	if(now!=tp+1)return ;
	now=1;
	while(now<=tp&&!len[now])++now;
	for(int i=1;i<=k;++i){
		if(!used[i]&&s[i]=='b'&&now<=tp&&pos[now]<i){
			--len[now],pos[now]=i,used[i]=1;
			++now;
			while(now<=tp&&!len[now])++now;
		}
	}
	if(now!=tp+1)return ;
	now=1;
	while(now<=tp&&!len[now])++now;
	for(int i=1;i<=k;++i){
		if(!used[i]&&now<=tp&&pos[now]<i){
			--len[now],pos[now]=i,used[i]=1;
			while(now<=tp&&!len[now])++now;
		}
	}
	if(now!=tp+1)return ;
	int les=tp-1;
	if(tp==0)les=1;
	int seg=tp+1;
	LL ad=fact[tp];
	for(int i=1;i<=scnt;++i){
		ad=ad*rev[seq[i][1]]%mod;
		int l=seq[i][0];
		for(int j=1;j<=seq[i][1];++j){
			if(l==1)les+=1;
			else les+=2*l-3;
			seg+=2*l-1;
		}
	}
	if(les>n)return ;
	//for(int i=1;i<=scnt;++i)cerr<<seq[i][0]<<":"<<seq[i][1]<<endl;
	//cerr<<endl;
	//cerr<<ad<<" "<<seg<<" "<<n-les<<endl;
	ad=ad*comp(n-les+seg-1,n-les)%mod;
	ans=(ans+ad)%mod;
}
int all=-1;
int TEST=0;
void dfs(int rem,int now){
	if(all>n)return ;
	if(now==0){
		calc();
		//for(int i=1;i<=scnt;++i)cerr<<seq[i][0]<<":"<<seq[i][1]<<endl;
		//cerr<<endl;
		return ;
	}
	for(int i=0;i*now<=rem;++i){
		if(i){
			++scnt;
			seq[scnt][0]=now;
			seq[scnt][1]=i;
			if(now==1)all+=i;
			else all+=i*(2*now-3);
			all+=i;
		}
		dfs(rem-i*now,now-1);
		if(i){
			--scnt;
			if(now==1)all-=i;
			else all-=i*(2*now-3);
			all-=i;
		}
	}
}
int main(){
	//open();
	n=read();
	k=read();
	prefact(4*k+n+10);
	scanf("%s",s+1);
	for(int i=1;i<=k;++i)
		if(s[i]=='r')rcnt++;
		else bcnt++;
	dfs(k,k);
	printf("%lld\n",ans);
	//cerr<<TEST<<endl;
	close();
	return 0;
}

Measured memory_bytes: 384
# coding UTF-8
# 
# problem D
# 
import itertools
import numpy as np
from scipy.spatial import distance

# 組み合わせ関数の定義
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

# データ入力
P = list(map(int, input().split()))

# X の値から, 2進む回数最大回数をX2に格納する
if P[0]%2 == 0:
    X2 = int(P[0]/2); X1 = 0
else:
    X2 = int(P[0]/2); X1 = 1

# Y の進み方として存在する, y軸に2進む回数をYに格納する
Y_check = []
Y = []
for y in range(X2+1):
    if 2*(P[0]-2*y)+y == P[1]:
        Y.append(y)
    Y_check.append(2*(P[0]-2*y)+y)

# 進み方を調べる
x = np.array(["1", "2"])
for i in range(len(Y)):
    #print(len(Y))
    #print(np.repeat(x, [Y[i], P[0]-2*Y[i]], axis=0))
    print(cmb(Y[i]+P[0]-2*Y[i], Y[i])%(10**9+7))

if not Y:
    print(0)



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

main()
{
    int A[10000], i = 0;
    while (cin >> A[i])
        {
            if (A[i] == 0)
                break;
            else
            cout << "Case " << i+1 << ": " << A[i] << endl;
            i++;
        }
    return 0;
}

Measured memory_bytes: 1196
import Foundation

func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}
func main() {
    let S = Array(readLine()!)
    let T = Array(readLine()!)
    var ans = 0
    for i in stride(from: 0, to: S.count, by: 1){
        if S[i] != T[i]{
            ans += 1
        }
    }
    print(ans)
}
main()

Measured memory_bytes: 18524
Sample, NumOfPaperA, NumOfPaperB = map(int, input().split())
MaximumNumberOfBothReader = min(NumOfPaperA, NumOfPaperB)
MinimumNumberOfBothReader = max(NumOfPaperA + NumOfPaperB - Sample, 0)
print(str(MaximumNumberOfBothReader) + ' ' + str(MinimumNumberOfBothReader))


Measured memory_bytes: 3060
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include "bits/stdc++.h"

using namespace std;

typedef unsigned long long ll;
typedef int                     integer;
#define int                     long long
#define ii                      pair<int,int>
#define vii                     vector<pair<int,int>>
#define vi                      vector<int>
#define vvi                     vector<vector<int>>
#define f(a,b,c)                for(int a=b;a<c;a++)
#define s(x)                    in>>x
#define s2(x,y)                 in>>x>>y
#define s3(x,y,z)               in>>x>>y>>z
#define s4(x,y,z,w)             in>>x>>y>>z>>w
#define p(x)                    out<<x<<endl
#define p2(x,y)                 out<<x<<" "<<y<<endl
#define pl(x)                   out<<x
#define p2l(x,y)                out<<x<<" "<<y
#define p1d(a,n)                for(int ix=0;ix<n;ix++) out<<a[ix]<<" "; out<<endl
#define p2d(a,n,m)              for(int ix=0;ix<n;ix++){ for(int jx=0;jx<m;jx++) out<<a[ix][jx]<<" "; out<<endl;}
#define range(v)                v.begin(),v.end()
#define w(x)                    while(x--)
#define rst(x)                  memset(x, -1, sizeof(x))
#define UNVISITED               -1
#define VISITED                 0
#define EXPLORED                2

void ssolve(std::istream& in, std::ostream& out){
 int x,y,a,b,c;
 s4(x,y,a,b);
 s(c);
 vi pp(a),q(b),r(c);
    vector<pair<int,char>> all;
 f(i,0,a){s(pp[i]);all.emplace_back(pp[i],'a');}
 f(i,0,b){s(q[i]);all.emplace_back(q[i], 'b');}
 f(i,0,c){s(r[i]);all.emplace_back(r[i], 'c');}

 sort(range(all));
 reverse(range(all));
    int aa = 0;
    int bb =0;
    int i =0;
    int tot = 0;
    tot = x+y;
    int k = 0;
    int sum = 0;
 while(k < tot && i<all.size()){
     if(all[i].second == 'a' && x>0){
         sum+=all[i].first;
         x--;
         k++;
     }
     else if(all[i].second == 'b' && y > 0){
         sum+=all[i].first;
         y--;
         k++;
     }
     else if(all[i].second == 'c'){
         sum+=all[i].first;
         k++;
     }
     i++;
 }
out<<sum<<endl;




}

class ERedAndGreenApples {
public:
	void solve(std::istream& in, std::ostream& out) {
        ios_base::sync_with_stdio(false);
        in.tie(0);out.tie(0);
        int t;
        int READ = 0;
        if(READ) s(t);
        else t = 1;
        while(t--){
            ssolve(in, out);
        }
	}
};


integer main() {
	ERedAndGreenApples solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
}


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,K;
vector<int> A;
bool dp [5001] [5001];

bool f(int m)
{
	memset(dp,false,sizeof(dp));
	dp [0] [0] = true;
	FOR(i,0,N) FOR(j,0,K + 1) if(dp [i] [j]){
		dp [i + 1] [j] = true;
		if(i != m && j + A [i] <= K) dp [i + 1] [j + A [i]] = true;
	}
	bool res = false;
	FOR(i,max(0,K - A [m]),K){
		res |= dp [N] [i];
	}
	return res;
}

int main()
{
	scanf("%d%d",&N,&K);
	A.assign(N,0);
	FOR(i,0,N){
		scanf("%d",&A [i]);
	}
	sort(ALL(A));

	int ok = N,ng = -1,mid;
	while(ok - ng > 1){
		mid = (ok + ng) / 2;
		if(f(mid)){
			ok = mid;
		}
		else{
			ng = mid;
		}
	}

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

	return 0;
}


Measured memory_bytes: 24704
#include<stdio.h>
int main(void){
	int W,H,x,y,r;
	
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
	
	if(x>=W || x<=0){
		printf("No\n");
	}else if(y>=H || y<=0){
		printf("No\n");
	}else if(x+r>W || x-r<0){
		printf("No\n");
	}else if(y+r>H || y-r<0){
		printf("No\n");
	}else
	printf("Yes\n");
	
	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> h(n+k);
  for (int i=0; i<n; i++) {
    cin >> h[i];
  }
  ll dp[n+k]; 
  for (int i=0; i<n+k; i++) {
    dp[i] = INT_MAX;
  }
  // dp initialization
  dp[0] = 0;
  for (int i=0; i<n; i++) {
    for (int j=1; j<=k; j++) {
      dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]));
      //cout << i+j << " " << dp[i+j] << endl;
    }
  }
  cout << dp[n-1] << endl;
  return 0;
}


Measured memory_bytes: 1408
from collections import deque

n = int(input())
graph = [[] for _ in range(n)]
edge = []

for _ in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    edge.append((a, b))

color = max([len(x) for x in graph])
print(color)

check = [False] * n
check[0] = True
DQ = deque()
DQ.append(0)

tree = [set() for i in range(n)]

while DQ:
    now = DQ.popleft()
    for node in graph[now]:
        if check[node] == False:
            check[node] = True
            tree[now].add(node)
            DQ.append(node)

memo = [False] * n
memo[0] = -1
DQ = deque()
DQ.append(0)

while DQ:
    now = DQ.popleft()
    if now == 0:
        c = 1
        for node in tree[now]:
            DQ.append(node)
            memo[node] = c
            c += 1
    else:
        c = 1
        for node in tree[now]:
            DQ.append(node)
            if c == memo[now]:
                c += 1
                memo[node] = c
                c += 1
            else:
                memo[node] = c
                c += 1

for a, b in edge:
    if a in tree[b]:
        print(memo[a])
    else:
        print(memo[b])

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

int V;
int INF = 1e8;
struct edge{ int to,cap,rev; };
vector<edge> G[500];
bool used[500];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  for(int i=0;i<(int)G[v].size();i++){
    edge &e=G[v][i];
    if(!used[e.to]&&e.cap>0){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}
int max_flow(int s,int t){
  int flow=0;
  while(1){
    memset(used,0,sizeof(used));
    int f=dfs(s,t,INF);
    if(f==0)break;
    flow+=f;
  }
  return flow;
}

int H,W;
char a[100][100];
int main(){
  V=205;
  cin>>H>>W;
  
  int si=V-2;
  int ti=V-1;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>a[i][j];
      if(a[i][j]=='o'){
        add_edge(i,100+j,1);
        add_edge(100+j,i,1);
      }else if(a[i][j]=='S'){
        add_edge(si,i,1e8);
        add_edge(si,100+j,1e8);
      }else if(a[i][j]=='T'){
        add_edge(i,ti,1e8);
        add_edge(100+j,ti,1e8);
      }
    }
  }
  int ans=max_flow(si,ti);
  if( ans > 200 ){
    ans=-1;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
constexpr double eps=1e-8;
const double pi=acos(-1);
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int Random(int mi,int ma){
    random_device rnd;
    mt19937 mt(rnd());//32bit
    //[mi,ma]
    uniform_int_distribution<int>engine(mi,ma);
    return engine(mt);
}
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
vector<int>kaijo,invkaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    invkaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
    rep(i,n+1)invkaijo[i]=modpow(kaijo[i],mod-2);
}
int comb(int a,int b){
    if(a<b)return 0;
    if(a<0||b<0)return 0;
    return kaijo[a]*invkaijo[a-b]%mod*invkaijo[b]%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
int pw26[2000010],pw25[2000010];
signed main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int k;
    string s;
    cin>>k>>s;
    int m=s.size(),n=m+k;
    pw25[0]=1,pw26[0]=1;
    for(int i=1;i<=2000000;i++){
        pw25[i]=pw25[i-1]*25%mod;
        pw26[i]=pw26[i-1]*26%mod;
    }
    init_fact(2000010);
    int ans=0;
    for(int q=0;q+m<=n;q++){
        int p=n-m-q;
        ans+=pw26[q]*comb(p+m-1,m-1)%mod*pw25[p]%mod;
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 66824
#include<iostream>
#include<string>
using namespace std;
string s;
int main() {
	getline(cin,s);
	for(int i=0;i<s.length();i++)
		if(s[i]>='A'&&s[i]<='Z')
			s[i]=s[i]+32;
		else if(s[i]>='a'&&s[i]<='z')
			s[i]=s[i]-32;
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 3176
import sys,os,io
input = sys.stdin.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
rem_max = N
cum_max = 0
cum_min = N+1
lis = []
for x,y in A:
  cum_max = max(cum_max, y)
  cum_min = min(cum_min, y)
  lis.append(y)
  if cum_max==rem_max and len(lis)==cum_max-cum_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    rem_max = cum_min-1
    lis = []
    cum_max = 0
    cum_min = N+1
print(*ans, sep='\n')


Measured memory_bytes: 117152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll M, DC = 0, S = 0;
	cin >> M;
	for(int i = 0; i < M; ++i){
		ll d, c; cin >> d >> c;
		S += d*c; DC += c;
	}
	ll r = DC-1 + (S-1)/9;
	cout << r << endl;
}

Measured memory_bytes: 256
n = int(input())
s = [int(input()) for  _ in range(n)]
ans = sum(s)
s.sort()
if ans%10 != 0:
    print(ans)
else:
    t = []
    for i in range(n):
        if s[i]%10 != 0:
            t.append(s[i])
    if len(t) == 0:
        print(0)
    else:
        print(ans-t[0])

Measured memory_bytes: 9052
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  rep(i, N) cin >> A[i];
  rep(i, N) cin >> B[i];
  priority_queue<pair<ll, int>> q;
  rep(i, N) q.push({B[i], i});
  ll ans = 0;
  while(!q.empty()) {
    auto ele = q.top(); q.pop();
    ll val = ele.first;
    int i = ele.second;
    if(val-A[i] < B[(i+N-1)%N]+B[(i+1)%N]) continue;
    ll rem = (val-A[i])%(B[(i+N-1)%N]+B[(i+1)%N]);
    ll cur = (val-A[i])/(B[(i+N-1)%N]+B[(i+1)%N]);
    ans += cur;
    B[i] = A[i]+rem;
    if(rem) q.push({B[i], i});
  }
  bool ok = true;
  rep(i, N) if(A[i] != B[i]) ok = false;
  cout << (ok ? ans : -1) << endl;
  return 0;
}


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

int main () {
  int N;
  cin >> N;
  
  if(N%10==3) {
    cout << "bon" << endl;
  }
  
  else if(N%10==0||N%10==1||N%10==6||N%10==8) {
    cout << "pon" << endl;
  }
  
  else {
    cout << "hon" << endl;
  }
}

Measured memory_bytes: 3636
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

X, Y, A, B, C = na()
P = na()
Q = na()
R = na()
ls = []
for lp in P:
    ls.append([lp, 0])
for lp in Q:
    ls.append([lp, 2])
for lp in R:
    ls.append([lp, 1])
ls.sort(reverse=True)

up = 0
down = 0
ans = 0
for item in ls:
    if item[1] == 0:
        if X > 0:
            X -= 1
            ans += item[0]
        elif X == 0 and Y > 0 and up > 0:
            up -= 1
            down += 1
            Y -= 1
            ans += item[0]
    elif item[1] == 2:
        if Y > 0:
            Y -= 1
            ans += item[0]
        elif Y == 0 and X > 0 and down > 0:
            down -= 1
            up += 1
            X -= 1
            ans += item[0]
    else:
        if X > 0:
            X -= 1
            ans += item[0]
            up += 1
        elif Y > 0:
            Y -= 1
            ans += item[0]
            down += 1
print(ans)


Measured memory_bytes: 127204
inp = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n')
N = inp.shift() * 1
X1 = Math.floor(N / 1.08)
X2 = Math.ceil(N / 1.08)
f = 0
for (i=X1;i<=X2;i++) {
    if (N == Math.floor(i * 1.08)) {
        X = i
        f = 1
        break;
    }
}
console.log(f ? X : ':(')


Measured memory_bytes: 21064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
using matrix = vector<vector<uint>>;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acos(-1);

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

    int N;
    cin >> N;
    vector<int> cnt(N);
    for (int i = 1; i < N; ++i) {
        int A;
        cin >> A;
        A--;
        cnt[A]++;
    }

    for (auto i : cnt)
        cout << i << '\n';
    return 0;
}


Measured memory_bytes: 3920