akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
using namespace std;
int main(){

// Seiranchan!
    int N,M,X,Y;
    cin >> N >> M >> X >> Y;

    vector <int> A(N);
    vector <int> B(M);

    REP(i,N) cin >> A[i];
    REP(i,M) cin >> B[i];

    SORT(A);
    SORT(B);

    int Max = max(A[A.size()-1],X);
    int Min = min(B[0],Y);

    if(Max<Min) cout << "No War" << endl;
    else cout << "War" << endl;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL
 
typedef struct node{
  struct node *l;
  struct node *r;
  struct node *p;
  int key;
}*Node;
 
Node root;
 
/*Node treeMinimum(Node x){
 
}
*/
Node treeSearch(Node u, int k){
  while(u!=NIL && k!=u->key){
    if(k < (u->key)){
      u = u->l;
    }
    else{
      u = u->r;
    }
  }
  return u;
}
/*
     
Node treeSuccessor(Node x){
 
 
}
 
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
 
 
 
}
*/
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  z = malloc(sizeof(struct node));
  z->key = k;
  z->l = NIL;
  z->r = NIL;
  while(x!=NIL){
    y = x;
    if(z->key<x->key){
      x = x->l;
    }
    else{
      x =x->r;
    }
  }
  z->p= y;
  if(y==NIL){
    root = z;
  }
  else if(z->key<y->key){
    y->l =z;
  }
  else{
    y->r =z;
  }
   
  }
 
void inorder(Node u){
  if(u != NIL){
    inorder(u->l);
    printf(" %d",u->key);
    inorder(u->r);
  }
}
 
void preorder(Node u){
  if(u!=NIL){
    printf(" %d",u->key);
    preorder(u->l);
    preorder(u->r);
  }
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
   
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
   
       
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }/* else if ( com[0] == 'd' ){
        scanf("%d", &x);
        treeDelete(treeSearch(root, x));
        }*/
  }
   
  return 0;
}

Measured memory_bytes: 19364
import java.io.*;
import java.util.*;

public class Main {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        long N;
        N = sc.nextLong();
        long M;
        M = sc.nextLong();
        long[] s = new long[(int)(M)];
        long[] c = new long[(int)(M)];
        for(int i = 0 ; i < M ; i++){
                s[i] = sc.nextLong();
                c[i] = sc.nextLong();
        }

        final Solver solver = new Solver();
        solver.solve(N, M, s, c);
    }
}

class Solver {
    public void solve(long N, long M, long[] s, long[] c) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append('a');
        }

        for (int i = 0; i < M; i++) {
            int index = (int) s[i] - 1;
            char num = (char) ('0' + c[i]);

            if (sb.charAt(index) == 'a' || sb.charAt(index) == num) {
                sb.setCharAt(index, num);
            }
            else {
                System.out.println(-1);
                return;
            }
        }

        if (N == 1 && (sb.charAt(0) == 'a' || sb.charAt(0) == '0')) {
            System.out.println(0);
            return;
        }

        if (sb.charAt(0) == 'a') {
            sb.setCharAt(0, '1');
        } else if (sb.charAt(0) == '0') {
            System.out.println(-1);
            return;
        }

        for (int i = 1; i < N; i++) {
            if (sb.charAt(i) == 'a') {
                sb.setCharAt(i, '0');
            }
        }

        System.out.println(sb.toString());
    }
}



Measured memory_bytes: 22996
package main
import(
  "fmt"
)
func main(){
  var a, b, c, x, y, z, l int
  ans:=0
  fmt.Scan(&a, &b, &c, &x, &y)
  if x<y{
    z=x
    l=y
  }else{
    z=y
    l=x
  }
  if a+b>=c*2{
    ans+=c*z*2
    if l==x && l-z!=0{
      if a<c*2{
        ans+=a*(l-z)
      }else{
        ans+=c*(l-z)*2
      }
    }else if l==y && l-z!=0{
      if b<c*2{
        ans+=b*(l-z)
      }else{
        ans+=c*(l-z)*2
      }
    }
  }else{
    ans=a*x+b*y
  }
  fmt.Println(ans)
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args) {
		Scanner scn=new Scanner(System.in);
		
		long A=scn.nextLong();
		long B=scn.nextLong();
			
		if((A+B)%2==0) {
			long s=(A+B)/2;
			
			System.out.println(s);
			
		}
		else {
			System.out.println("IMPOSSIBLE");
		}
			
		scn.close();	
	}
	
}

Measured memory_bytes: 21972
#include<stdio.h>

 int main(void){
    int a,b,c;
    scanf("%d %d %d", &a, &b, &c);
    
    int min=a+b;
       
       if(min>a+c) {
        min=a+c;
       }
        
       if(min>b+c) {
          min=b+c;
       }
    printf("%d\n",min);
        
   return 0;
 }

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;

public class Main{

	public static void main(String args[]){

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int x = sc.nextInt();
		Integer fee[] = new Integer[m];
		int costRight = 0;
		int costLeft =0;
		
		for(int i = 0; i < m; i ++) {
			fee[i] =sc.nextInt();
		}
		
		for(int i = x + 1; i <= n; i ++) {
			if(Arrays.asList(fee).contains(i)) {
				costRight ++;
			}
		}
		
		for(int i = x - 1; i >= 0; i --) {
			if(Arrays.asList(fee).contains(i)) {
				costLeft ++;
			}
		}
		
		if(costRight > costLeft) {
			System.out.println(costLeft);
		}else {
			System.out.println(costRight);
		}
	}
}

Measured memory_bytes: 23636
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u


n, k = map(int, input().split())
al = list(map(int, input().split()))
al_abs = []
al_p = []
al_m = []
zero_cnt = 0
MOD = 10**9+7

for a in al:
    if a == 0:
        zero_cnt+=1
    elif a > 0: 
        al_abs.append((abs(a),1))
        al_p.append(a)
    else: 
        al_abs.append((abs(a),-1))
al_abs.sort(reverse=True)


if n == k:
    ans = 1
    for a in al:
        ans *= a
        ans %= MOD
    print(ans)
    exit()


if len(al_abs) < k:
    print(0)
    exit()



if not al_p:
    if k%2 == 1 and zero_cnt > 0:
        print(0)
    else:
        if k%2 == 1:
            al_abs.sort()
        ans = 1
        for a,s in al_abs[:k]:
            ans *= (a*(-1))
            ans %= MOD
        print(ans)
    exit()


val = 1
m_cnt = 0
last_m = 0
last_p = 0
for i in range(k):
    v,sig = al_abs[i]
    val *= v
    val %= MOD
    if sig == -1:
        m_cnt += 1
        last_m = v
    else:
        last_p = v

if m_cnt %2 == 0:
    print(val)
    exit()


# minus -> plus 

## search next p
next_p = 0
for i in range(k,len(al_abs)):
    v,sig = al_abs[i]
    if sig == 1:
        next_p = v
        break

## search next m
next_m = 0
for i in range(k,len(al_abs)):
    v,sig = al_abs[i]
    if sig == -1:
        next_m = v
        break

if next_p == 0 and next_m == 0:
    print(0)
    exit()

# last_m -> next_p
if next_p*last_p >= next_m*last_m or last_p == 0:
    ans = val*modinv(last_m%MOD,MOD)*next_p
    ans %= MOD
    print(ans)

else:
    ans = val*modinv(last_p%MOD,MOD)*next_m
    ans %= MOD
    print(ans)

Measured memory_bytes: 125056
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> P;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
const ll INF = 1e+9+7;
ll n,m,l;
string s,t;
ull d[100000],dp[100][100];

int main(){
  cin >> n >> m >> l;
  if(m >= l)puts("delicious");
  else if(n < l-m)puts("dangerous");
  else puts("safe");
  return 0;
}

Measured memory_bytes: 256
n, m = map(int,input().split())

if n==1 or m==1:
    if n==1 and m==1:
        print(1)
    else:
        if n == 1:
            print(m-2)
        else:
            print(n-2)
else:
    if n == 2 or m == 2:
        print(0)
    else:
        print((n-2)*(m-2))

Measured memory_bytes: 3060
x=list(map(int,input().split()))

if x[0]>x[2]:
    print(str(x[0]-x[2])+" "+str(x[1]))
elif x[0]+x[1]>x[2]:
    print("0"+" "+str(x[0]+x[1]-x[2]))
else:
    print("0"+" "+"0")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define pa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
#define pb push_back
#define fi first
#define be begin()
#define en end()
#define se second

using ll = long long;
using namespace std;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
const int INFint = 1e9;
const ll INFll = 1e18;
ll MOD=1e9+7;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; } //最大公約数
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } //最大公倍数

// aのn乗をMODで割りながら計算する
ll modpow(ll a, ll n) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % MOD;
    a = a * a % MOD;
    n >>= 1; // right shift
  }
  return res;
}

// MODを法としたaの逆元を計算する
ll modinv(ll a) {
  return modpow(a, MOD - 2);
}

int main(){
  string a,b;
  cin>>a>>b;
  if (a>b) cout << '>' << endl;
  else if (a==b) cout << '=' << endl;
  else cout << '<' << endl;
  return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int a1,a2,a3;
    scanf("%d%d%d",&a1,&a2,&a3);
    int g,s;
    if(a1>=a2 && a1>=a3) g=a1;
    else if(a2>=a1 && a2>=a3) g=a2;
    else g=a3;
    if(a1<=a2 && a1<=a3) s=a1;
    else if(a2<=a1 && a2<=a3) s=a2;
    else s=a3;
    printf("%d\n",g-s);


    return 0;
}


Measured memory_bytes: 128
#0063
d = 0
while True:
    c = 0
    l = []
    try:
        text = str(input())
    except:
        break
    x = list(reversed(text))
    y = ''.join(x)
    if text == y:
        c += 1
    if c > 0:
        d += 1
print(d)


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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = euclid(b, a % b, y, x);
        return y -= a/b * x, d; }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1) ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1); return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this ^ (e / 2); r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    for (;;) {
        int w, d; cin >> w >> d; if (!w) break;
        vector<int> p(w), q(d);
        rep(i, 0, w) cin >> p[i];
        rep(j, 0, d) cin >> q[j];
        // guarantee w >= d
        if (w < d) swap(w, d), swap(p, q);
        sort(all(p)); sort(all(q));
        reverse(all(p)); reverse(all(q));
        int ans = 0;
        int j = 0;
        rep(i, 0, w) {
            while (j < q.size() && q[j] > p[i]) ans += q[j++];
            ans += p[i];
            if (q[j] == p[i]) j++;
        }
        while (j < q.size()) ans += q[j++];
        cout << ans << endl;
    }
}


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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int a[200000],b[200000];
int main(){
	int A,B,M;cin>>A>>B>>M;
	rep(i,A)scanf("%d",&a[i]);
	rep(i,B)scanf("%d",&b[i]);
	int Mina=*min_element(a,a+A),Minb=*min_element(b,b+B);
	int Min=INF;
	rep(i,M){
		int x,y,c;scanf("%d%d%d",&x,&y,&c);x--;y--;
		Min=min(Min,a[x]+b[y]-c);
	}
	cout<<min(Mina+Minb,Min)<<endl;
}

Measured memory_bytes: 1024
N = int(input())
a = list(map(int, input().split()))
M = sum(a)
S = a[0]
T = M - S
X = abs(T - S)
for i in range(1, N - 1):
    S += a[i]
    T = M - S
    X = min(X, abs(T - S))
print(X)

Measured memory_bytes: 30732
#include<bits/stdc++.h>
using namespace std;
int n,m,num=1,a[100010];
string s;
vector<int> v;
int main(){
	cin>>n>>m>>s;
	for (int i=0;i<n;i++)
		if (s[i+1]=='0')
			a[i]=1;
		else{
			int j=i+1;
			while (s[j]=='1') j++;
			a[i]=j-i;
			i=j-1;
		}
	for (int i=0;i<=n;i++)
		if (a[i]>m){
			cout<<-1<<endl;
			return 0;
		}
	for (int i=0;i<=n;i++) if (a[i]!=0) v.push_back(a[i]);
	for (int i=v.size()-1;i>=0;i--){
		for (int j=i-1;j>=0;j--)
			if (v[j]!=0){
				if (v[i]+v[j]<=m){
					v[i]+=v[j];i--;
					v.erase(v.begin()+j);
				}
				else
					break;
			}
		for (int j=i+1;j<v.size();j++)
			if (v[j]!=0){
				if (v[i]+v[j]<=m){
					v[i]+=v[j];
					v.erase(v.begin()+j);
				}
				else
					break;
			}
	}
	for (int i=0;i<v.size();i++) cout<<v[i]<<' ';
	return 0;
}

Measured memory_bytes: 1528
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
A.sort()

def shake_cnt(x):
    Y = np.searchsorted(A,x-A)
    return N*N - Y.sum()

right = 10 ** 6
left = 0 #握手するのがM人以上
while right > left + 1:
    mid = (left+right) // 2
    if shake_cnt(mid) >= M:
        left = mid
    else:
        right = mid

X = np.searchsorted(A, right-A) #握手しない人数
Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()

shake = N*N - X.sum()
happy = (Acum[-1] - Acum[X]).sum() + (A * (N-X)).sum()
happy += (M-shake) * left
print(happy)



Measured memory_bytes: 23452
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin >> N;
  vector<unsigned long long int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  sort(A.begin(),A.end());
  int state=1;
  unsigned long long int mult=A.at(0);
  for(int i=1;i<N;i++){
    if(A.at(i)==0||mult==0){
      mult=0;
      break;
    }else if(((1000000000000000000)/mult)<A.at(i)){
      state=(-1);
      break;
    }else{
      mult*=A.at(i);
    }
  }

  
  if(state!=-1){
   cout << mult << endl;
  }else{
    cout << state <<endl;
  }
}


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

from math import ceil
from fractions import gcd

def solve(A, B, C, D):
    if A < B or D < B: return False
    if A % B > C: return False
    if D % B == 0: return True

    g = gcd(B, D)
    r = A % g  # +D -B を繰り返すと x % g == r であるxを訪れる
    # x % g == r and C < x < B である x が存在するなら False を返す
    return not (C < B - g + r)

T = int(input())
for i in range(T):
    A, B, C, D = [int(t) for t in input().split()]
    print('Yes' if solve(A, B, C, D) else 'No')


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

n = int(input())

numbers = list(map(int, input().split(" ")))
a = int(numbers[0])
b = int(numbers[1])

cnt = 0

for i in range(n):
    if i + 1 != numbers[i]:
        cnt += 1

if cnt <= 2:
    print("YES")
else:
    print("NO")

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

using namespace std;

#define MOD 1000000007
typedef long long int ll;

int cnt[11][1001]={0};

int main(){


	ios_base::sync_with_stdio(false);
	cin.tie(0);
        
	int r,c,w;
	cin>>r>>c>>w;

	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			char temp;
			cin>>temp;
			cnt[i][j]+=temp-'0';
		}
	}

	int ans=INT_MAX;
	for(int num=0;num<(1LL<<r);num++){
		vector<int>cut;
		cut.push_back(0);
		for(int i=0;i<r-1;i++){
			if(num&(1LL<<i)){
				cut.push_back(i+1);
			}
		}
		cut.push_back(r);
		int pcnt[cut.size()]={0};
		bool ch=true;
		int sum=0;
		for(int j=1;j<=c;j++){
			int ccnt[cut.size()]={0};
			for(int ii=1;ii<cut.size();ii++){
				for(int i=cut[ii-1]+1;i<=cut[ii];i++){
					ccnt[ii]+=cnt[i][j];
				}
			}
			for(int i=1;i<cut.size();i++){
				if(ccnt[i]>w){
					ch=false;
				}
			}
			if(!ch){
				break;
			}
			bool cch=true;
			for(int i=1;i<cut.size();i++){
				if(ccnt[i]+pcnt[i]>w){
					cch=false;
				}
			}
			if(cch){
				for(int i=1;i<cut.size();i++){
					pcnt[i]+=ccnt[i];
				}
			}
			else{
				for(int i=1;i<cut.size();i++){
					pcnt[i]=ccnt[i];
				}
				sum++;
			}
		}
		if(ch){
			int temp=(int)cut.size()-2;
			//cout<<sum<<" "<<temp<<endl;
			ans=min(ans,sum+temp);
		}
	}
	cout<<ans<<endl;


	return 0;
}

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

int main() {
  long long n, a, b, c, d, e;
  cin >> n >> a >> b >> c >> d >> e;
  long long min_trans = min(a, min(b, min(c, min(d, e))));
  if (min_trans < n) cout << (n - 1) / min_trans + 5  << endl;
  else cout << 5 << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

typedef struct {
	int ID[100];
	int NUM;
} CANUM;

int main(void)
{
	CANUM canum[31] = {{0}, 0};
	int id, ca, i, j, ra = 1;
	int rank[100];
	
	while (1){
		scanf("%d,%d", &id, &ca);
		if (id == 0 && ca == 0){
			break;
		}
		
		canum[ca].ID[canum[ca].NUM++] = id;
	}
	
	for (i = 30; i >= 0; i--){
		if (canum[i].NUM != 0){
			for (j = 0; j < canum[i].NUM; j++){
				rank[canum[i].ID[j]] = ra;
			}
			ra++;
		}
	}
	
	while (scanf("%d", &id) != EOF){
		printf("%d\n", rank[id]);
	}
	
	return (0);
}

Measured memory_bytes: 620
//#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <cstring>
#include <climits>
#define INF INT_MAX / 2
using namespace std;

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

int main(void) {
  int n;

  while (cin >> n,n!=0) {
    int mi = INF, ma = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
      int p;
      cin >> p;
      sum += p;
      mi = min(mi, p);
      ma = max(ma, p);
    }
    sum -= (mi + ma);
    cout << sum / (n-2) << endl;
  }
}

// command ctrl 上下
// command D
// command caps G → '' ""

Measured memory_bytes: 1160
#include <stdio.h>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#define mod 1000000007
#define ll long long
#define pi acos(-1)
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	ll n;
	cin>>n;
	ll t = 100;
	ll p = 0;
	while(t<n){
		t=t*1.01;
		p++;
	}
	cout<<p;
	
    return 0; 
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int n,m,sum,tx[5]={0,0,1,-1},ty[5]={1,-1,0,0};
char a[1005][1005];
int vis[1005][1005];
struct S {
    int x,y,t;
};
bool check(int x,int y){
    if(x<1||x>n||y<1||y>m) return 0;
    if(vis[x][y]||a[x][y]=='#') return 0;
    return 1;
}
queue<S> q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]+1;
        for(int j=1;j<=m;j++){
            if(a[i][j]=='.'){
                sum++;
            }else{
                q.push(S{i,j,0});
                vis[i][j]=1;
            }
        }
    }
    int ans=0;
    while(!q.empty()){
        S p=q.front(); q.pop();
        //cout<<p.x<<" "<<p.y<<endl;
        for(int i=0;i<4;i++){
            int xx=p.x+tx[i];
            int yy=p.y+ty[i];
            if(check(xx,yy)==0) continue;
            ans=max(ans,p.t+1);
            q.push(S{xx,yy,p.t+1});
            vis[xx][yy]=1;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 17296
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;
    vector<int> P(A), Q(B), R(C);
    rep(i, A) cin >> P[i];
    rep(i, B) cin >> Q[i];
    rep(i, C) cin >> R[i];

    sort(all(P), greater<int>());
    sort(all(Q), greater<int>());
    sort(all(R), greater<int>());

    R.resize(C + X + Y);
    copy(P.begin(), P.begin() + X, R.begin() + C);
    copy(Q.begin(), Q.begin() + Y, R.begin() + C + X);
    sort(all(R), greater<int>());

    write(accumulate(R.begin(), R.begin() + X + Y, 0LL));
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

int main()
{
	int n, a;
	cin >> a >> n;
	int ans = 0;
	if(n != 1) {
		int cur = 1;
		while(1) {
			cur += a - 1;
			ans ++;
			if(cur >= n) break;
		}
	}
	cout << ans << endl;
	
}

Measured memory_bytes: 256
n = int(input())
v = [int(x) for x in input().split()]
odd = {}
even = {}
for i in range(n):
	x = v[i]
	if i&1==1:
		if x in odd:
			odd[x]+= 1
		else:
			odd[x] = 1
	else:
		if x in even:
			even[x]+= 1
		else:
			even[x] = 1
			
oddl = []
for p, q in odd.items():
	oddl.append((p, q))
evenl = []
for p, q in even.items():
	evenl.append((p, q))
	
oddl = sorted(oddl, key=lambda x: x[1], reverse=True)
evenl = sorted(evenl, key=lambda x: x[1], reverse=True)

oddn = (n+1)>>1
evenn = n-oddn
result = []
if oddl[0][0] == evenl[0][0]:
	if len(oddl) > 1:
		result.append((oddn-oddl[1][1])+(evenn-evenl[0][1]))
	if len(evenl) > 1:
		result.append((oddn-oddl[0][1])+(evenn-evenl[1][1]))
	if len(oddl) == len(evenl) == 1:
		result.append(evenn)
else:
	result.append((oddn-oddl[0][1])+(evenn-evenl[0][1]))
print(min(result))

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

int main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n,x,t;
	cin>>n>>x>>t;
	int d=ceil(n/floor(x));
	cout<<d*t<<"\n";
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
 
int main(){
 int n ;cin>> n ;
 vector<int> A(n) ; rep(i,n) cin>> A[i] ;
 ll ans=0 ;
 rep(i,n){
   if(A[A[i]-1]==i+1&&A[i]!=i+1)ans++ ;
 }

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

Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>

int main(void)
{
   int i,n,s;
   int a[100001];
   scanf("%d",&n);

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

   for(i=0;i<=n;i++)
   s+=abs(a[i+1]-a[i]);

   for(i=1;i<=n;i++)
      printf("%d\n",s-abs(a[i-1]-a[i])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]));
                    
   return 0;
}    


Measured memory_bytes: 1536
from collections import Counter
 
n, m = map(int, input().split())
A = list(map(int, input().split()))
 
B = [0] * (n + 1)
 
for i in range(n):
  B[i + 1] = B[i] + A[i] # BはAの累積和

li = [i % m for i in B] # それをMで割った余りがli

C = Counter(li) # 余りが同じものの個数が2つ以上ある際、その2つの組み合わせによって、割り切れる和の組み合わせ個数が求まる

ans = 0
for v in C.values():
  if v > 1:
    ans += v * (v - 1) // 2
 
print(ans)

Measured memory_bytes: 18844
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,c,x,sum=0,m;
  cin>>n>>c;
  for(int i=1;i<=c;++i){
    cin>>x;
    sum+=x;
  }
  m=sum/(n+1);
  if(sum%(n+1))++m;
  cout<<m<<endl;
  return 0;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
stack<int>st;
string s;
int n,ans;
int main()
{
	cin>>s;
	ans=n=s.size();
	for(int i=0;i<n;++i)
	{
		int tt=1;
		if(s[i]=='T')tt=0;
//		puts("nmsl");
		if(!st.empty()&&st.top()==1&&tt==0)	st.pop(),ans-=2;
		else								st.push(tt);
	}
//	while(!st.empty())cout<<"  "<<st.top()<<endl;
	cout<<ans;
	return 0;
}

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

#define crap ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace std;
using ll = long long;

void solve()
{
   ll n; cin>>n;
   cout<<n+n*n+n*n*n;
}
int main()
{
    crap;
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r", stdin) ;
        freopen("output.txt","w", stdout) ;
        freopen("error.txt","w", stderr) ;
    #endif
    int t;t=1;
  //  cin>>t;
    while(t--)
        {solve();}
    return 0;
}

Measured memory_bytes: 3648
n,k = map(int,input().split())
s = [int(input()) for i in range(n)]
s.sort()
c = s[k-1] - s[0]
for i in range(1,n-k+1):
    if s[i+k-1] - s[i] < c:
        c = s[i+k-1] - s[i]

print(c)

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

n,a,b = map(int,input().split())

def digit_list(num):
    num = str(num)
    num = list(num)
    num = list(map(int,num))
    return num

cnt = 0

for i in range(1,n+1):
    temp = sum(digit_list(i))
    if a <= temp <= b:
        cnt += i

print(cnt)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		sc.close();

		if(x < 1200)
			System.out.println("ABC");
		else
			System.out.println("ARC");
	}
}


Measured memory_bytes: 21844
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var N = Sarray()[0];
            var pi = Sarray();
            var cnt = 0L;
            for (var i = 0; i < N; ++i)
            {
                if (pi[i] == i + 1)
                {
                    ++cnt;
                    ++i;
                }
            }
            WriteLine(cnt);
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

Measured memory_bytes: 36220
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define mes(a, b)  memset(a, b, sizeof a)
#define pb push_back
typedef unsigned long long int ull;
typedef long long int ll;
const int    maxn = 1e5 + 20;
const int    maxm = 1e5 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;
const double pi   = acos(-1.0);
const double eps  = 1e-8;
using namespace std;
int main(){
	for(int i = 1;i <= 5;i++){
		int a;cin >> a;
		if(a == 0) printf("%d\n",i );
	}
}

Measured memory_bytes: 3748
#include<iostream>
#include<stack>
#include<sstream>
#include<iomanip>
#include<deque>
#include<cassert>
#include<string>
using namespace std;
double stod(string s){
  double ret;
  stringstream ss;
  ss << s;
  ss >> ret;
  return ret;
}

string dtos(double d){
  stringstream ss;
  ss << d;
  return ss.str();
}

int main(){
  string s;
  
  while(getline(cin,s)){
    //cout << s  << endl;
    deque<string> st1;
    stack<double> st2;
 
    stringstream ss;
    ss << s;

    int cnt = 0;
    while(cnt < (ss.str()).size()){
      string input;
      ss >> input;
      if(input == "")
	break;      
     
      st1.push_front(input),cnt++;
    }

    

    while(st1.size()){
      string pp = st1.back(); st1.pop_back();
      //cout << "pp = " << pp << endl;
      if(pp == "+"){
	double da,db;
	da = st2.top(); st2.pop();
	db = st2.top(); st2.pop();
      
	//cout << db << "+" << da << endl;
	st2.push(db+da);
	//cout << "push! " << st2.top() << endl;
      }
      else if(pp == "-"){
	double a,b;
	a = st2.top(); st2.pop();
	b = st2.top(); st2.pop();
       
	//cout << db << "-" << da << endl;
	st2.push(b-a);
	//cout << "push! " << st2.top() << endl;
      }
      else if(pp == "*"){
	double a,b;
	a = st2.top(); st2.pop();
	b = st2.top(); st2.pop();
       
	//cout << db << "*" << da << endl;
	st2.push(b*a);
	//cout << "push! " << st2.top() << endl;
      }
      else if(pp == "/"){
	double a,b;
	a = st2.top(); st2.pop();
	b = st2.top(); st2.pop();
	
	//cout << db << "/" << da << endl;
	st2.push(b/a);
	//cout << "push! " << st2.top() << endl;
      }
      else{
	st2.push(stod(pp));
      }
    }
    assert(st2.size() == 1);
    cout << setiosflags(ios::fixed) << setprecision(6) << st2.top() << endl;
  }
  return 0;
}

Measured memory_bytes: 1328
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        MyReader r = new MyReader();  
        long W, H, x, y;
        {long[] a = r.ll(); W = a[0]; H = a[1]; x = a[2]; y = a[3];}
        int two = 0;
        if(x*2 == W && y*2 == H)
            two++;
        println(W*H/2.0+" "+two);    
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}

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

int main(){
  int n,a,b;
  string str,ch,s;
  cin>>str;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>ch;
    if(ch=="replace"){
      cin>>a>>b>>s;
      str=str.replace(a,b-a+1,s);
    }
    else if(ch=="reverse"){
      cin>>a>>b;
      for(int j=a,k=b;j<k;j++,k--){
          swap(str[j],str[k]);
      }
      
    }
    else if(ch=="print"){
      cin>>a>>b;
      cout<<str.substr(a,b-a+1)<<endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3216
n = int(input())
train = []
for i in range(n-1):
    c,s,f = map(int,input().split())
    train.append((c,s,f))
for i in range(1,n+1):
    time = 0
    for j in range(i,n):
        if time <= train[j-1][1]:
            time = train[j-1][1]
        else:
            time = train[j-1][1] + (time - train[j-1][1] + train[j-1][2] - 1) // train[j-1][2] * train[j-1][2]

        time += train[j-1][0]
    print(time)





Measured memory_bytes: 41836
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	char S[200];
	long long int K ;
	long long int i = 0;
	//scanf("%s", S);
	//scanf("%d", &K);
	cin >> S >> K;
	for (i = 0; i < K; i++) {
		if (S[i] >= '2') {
			printf("%c\n", S[i]);
			return 0;
		}
	}
	printf("1\n");
	return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
int a[10][10];
void syou(int x,int y){
  int i,j;
  int nx,ny;
  int dx[4]={1,0,-1,0};
  int dy[4]={0,1,0,-1};
  for(i=0;i<4;i++){
    nx=x+dx[i];
    ny=y+dy[i];
    if(0<=nx && nx<10 && 0<=ny && ny<10)a[ny][nx]++;
  }
}
void tyu(int x,int y){
  int i,j;
  int nx,ny;
  int dx[8]={1,1,0,-1,-1,-1,0,1};
  int dy[8]={0,-1,-1,-1,0,1,1,1};
  for(i=0;i<8;i++){
    nx=x+dx[i];
    ny=y+dy[i];
    if(0<=nx && nx<10 && 0<=ny && ny<10)a[ny][nx]++;
  }
}
void dai(int x,int y){
  int i,j;
  int nx,ny;
  int dx[12]={1,1,0,-1,-1,-1,0,1,2,0,-2,0};
  int dy[12]={0,-1,-1,-1,0,1,1,1,0,2,0,-2};
  for(i=0;i<12;i++){
    nx=x+dx[i];
    ny=y+dy[i];
    if(0<=nx && nx<10 && 0<=ny && ny<10)a[ny][nx]++;
  }
}
int main(){
  int count=0,max=0;
  int x,y,size;
  int i,j;
  while(scanf("%d,%d,%d",&x,&y,&size)!=EOF){
    a[y][x]++;
    if(size==1)syou(x,y);
    if(size==2)tyu(x,y);
    if(size==3) dai(x,y);
  }
  for(i=0;i<10;i++){
    for(j=0;j<10;j++){
      if(a[i][j]==0)count++;
      if(a[i][j]>max)max=a[i][j];
    }
  }
  printf("%d\n%d\n",count,max);
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int N, d[202020]; 
ll c[202020];
 
int main()
{
  cin >> N;
	for (int i = 0; i < N; ++i){ 
    cin >> d[i];
    cin >> c[i];
  }
 
	ll ans = 0, cif = 0;
	for (int i = 0; i < N; ++i) {
		ans += c[i];
		cif += d[i] * c[i];
	}
 
	ans += (cif - 1) / 9;
	--ans;
  cout << ans << '\n';
	return 0;
}


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

using namespace std;

#define int long long
#define pb push_back
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)

signed main () {
  int n; cin >> n;
  vector<int> a(n+2);
  a[0] = 0;
  a[n+1] = 0;
  REP(i, n) cin >> a[i+1];
  int sum = 0;
  REP(i, n+1) {
    sum += abs(a[i+1] - a[i]);
  }
  vector<int> diff(n+1);
  vector<int> diff2(n);
  REP(i, n+1) {
    diff[i] = abs(a[i+1] - a[i]);
  }
  REP(i, n) {
    diff2[i] = abs(a[i+2] - a[i]);
  }

  REP(i, n) {
    cout << sum - diff[i+1] - diff[i] + diff2[i] << endl;
  }
}


Measured memory_bytes: 3584
#include <iostream>

void solve() {
    char c;
    std::cin >> c;

    std::cout << (std::isupper(c) ? 'A' : 'a') << "\n";
}

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

    solve();

    return 0;
}


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

#define NIL -1
using namespace std;

struct Node{
    int current_node,parent_node,left_child,right_child,sibling_node;
    int depth,height;
};

void setDepth(vector<Node> &Tree,const int current_node,const int depth){
    Tree[current_node].depth = depth;
    if(Tree[current_node].left_child != NIL) setDepth(Tree,Tree[current_node].left_child,depth+1);
    if(Tree[current_node].right_child!= NIL) setDepth(Tree,Tree[current_node].right_child,depth+1);  
}

void setHeight(vector<Node> &Tree, const int current_node){
    int h1 = 0, h2 = 0;
    if(Tree[current_node].right_child != NIL){
        setHeight(Tree,Tree[current_node].right_child);
        h1 = Tree[Tree[current_node].right_child].height + 1;
    }
    if(Tree[current_node].left_child !=NIL){
        setHeight(Tree,Tree[current_node].left_child);
        h2 = Tree[Tree[current_node].left_child].height + 1;
    }
    Tree[current_node].height = max(h1,h2); 
}


int main(){
    int num_node;
    int current_node,left_child,right_child,degree;
    int root;
    string node_type;
    scanf("%d",&num_node);
    vector<Node> Tree(num_node,Node{NIL,NIL,NIL,NIL,NIL,NIL,NIL});

    for(int i = 0;i < num_node;i++){
        scanf("%d %d %d",&current_node,&left_child,&right_child);
        Tree[current_node].left_child  = left_child;
        Tree[current_node].right_child = right_child;
        Tree[right_child].parent_node  = current_node;
        Tree[left_child].parent_node   = current_node;
        Tree[right_child].sibling_node = left_child;
        Tree[left_child].sibling_node  = right_child;
    }
    for(int i = 0;i < num_node;i++){
        if(Tree[i].parent_node == -1) root = i;
    }

    setDepth(Tree,root,0);
    setHeight(Tree,root);
    for(int i = 0;i < num_node;i++){
        degree =  (Tree[i].left_child == NIL && Tree[i].right_child==NIL) ? 0
                 :(Tree[i].left_child != NIL && Tree[i].right_child!=NIL) ? 2
                 :1;
        node_type = (Tree[i].parent_node  == NIL) ? "root"
                    : (Tree[i].left_child == NIL && Tree[i].right_child == NIL) ? "leaf"
                    : "internal node";
        printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n",
            i, Tree[i].parent_node, Tree[i].sibling_node, degree, Tree[i].depth, Tree[i].height, node_type.c_str());
    }

    return 0;   
}



Measured memory_bytes: 3316
import std;

ulong MAX = 100_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "cur", long, "prev");
alias PQueue(T, alias less = "a>b") = BinaryHeap!(Array!T, less);

void main()
{
    long n, m;
    scan(n, m);
    auto route = new long[][](n, 0);
    foreach (_; iota(m))
    {
        long a, b;
        scan(a, b);
        route[a - 1] ~= b - 1;
        route[b - 1] ~= a - 1;
    }

    auto bfs()
    {
        auto prevs = new long[](n);
        prevs[] = INF;
        auto reached = new bool[](n);
        reached[0] = true;

        auto q = DList!(Pair)(route[0].map!(x => Pair(x, 0)).array());
        while (!q.empty())
        {
            auto t = q.front();
            q.removeFront();
            if (!reached[t.cur])
            {
                reached[t.cur] = true;
                prevs[t.cur] = t.prev;
                foreach (next; route[t.cur])
                {
                    if (!reached[next])
                    {
                        q.insertBack(Pair(next, t.cur));
                    }
                }
            }
        }
        return prevs;
    }

    writeln("Yes");
    bfs[1 .. $].each!(x => writeln(x + 1));
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 27384
#include <cstdio>
#define MAX 10000
using namespace std;

int main(void) {
    int n, i, j, C[MAX + 1];
    scanf("%d", &n);
    unsigned short A[n+1], B[n+1];

    for (i = 0; i <= MAX; i++) C[i] = 0;

    for (i = 0; i < n; i++) {
        scanf("%hu", &A[i + 1]);
        C[A[i + 1]]++;
    }

    for (i = 1; i <= MAX; i++) C[i] = C[i] + C[i - 1];

    for (j = 1; j <= n; j++) {
        B[C[A[j]]] = A[j];
        C[A[j]]--;
    }

    for (i = 1; i <= n; i++) {
        if (i > 1) printf(" ");
        printf("%d", B[i]);
    }
    printf("\n");

    return 0;
}

Measured memory_bytes: 8888
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
int getsum(int val){
	int sumi=0;
	while(val>0){
		sumi+=val%10;
		val/=10;
	}
	return sumi;
}

int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int i;
    int mini=inf,a,b;
    f(i,1,n){
    	a=i;
    	b=n-i;
    	mini=min(mini,getsum(a)+getsum(b));
    }
    cout<<mini<<endl;


}

Measured memory_bytes: 768
--{-# LANGUAGE OverloadedStrings #-}
--{-# LANGUAGE OverloadedLists   #-}
{-# LANGUAGE BangPatterns      #-} --引数に!
{-# LANGUAGE MultiWayIf        #-}
{-# LANGUAGE TupleSections     #-}

import Data.Bits
import Data.Foldable
import Data.Maybe (fromJust)
import Data.List
import Data.Array  --変数衝突
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
import Data.Graph
--import Data.Vector as V　--変数衝突
import qualified Data.ByteString.Lazy.Char8 as B
import qualified Data.Vector.Unboxed as V
import Control.Monad
import Control.Monad.State
import Control.Monad.ST
import Debug.Trace

type DP s = STUArray s (Int,Int) Int

dp_i :: DP s -> Int -> [Char] -> Int -> ST s ()
dp_i dparr n [] _ = return ()
dp_i dparr n (c:s) k = do
  if c == '<'  --ここを工夫してO(N)　i-1の結果を残したい
    then foldlM (\a i -> readArray dparr (k,i) >>= \a' -> writeArray dparr (k+1,i) (mod' $ a+a') >> (return $ a+a')) 0 [1..n-1]
    else foldlM (\a i -> readArray dparr (k,i+1) >>= \a' -> writeArray dparr (k+1,i) (mod' $ a+a') >> (return $ a+a')) 0 [n-1,n-2..1]
  dp_i dparr (n-1) s (k+1)

solve :: Int -> String -> ST s Int
solve n s = do
  dparr <- newArray ((1,1),(n,n)) 0
  forM_ [1..n] $ \i -> writeArray dparr (1,i) 1
  dp_i dparr n s 1
  forM [1..n] (\i -> readArray dparr (n,i)) >>= return.mod'. sum

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

main0 :: B.ByteString -> Int
main0 cont =
   let remLines0 = map B.words (B.lines cont)
       [n']:remLines1 = remLines0
       n = readBInt n'
       [line2]:remLines2 = remLines1
       s = B.unpack line2
   in mod' $ runST $ solve n s

main :: IO ()
main = print . main0 =<< B.getContents

mod' :: Int -> Int
mod' n = if n < 1000000007 then n else mod n 1000000007


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

int main(){
  int N;
  cin >> N;
  bool check = true;
  rep(i, N){
    int a;
    cin >> a;
    if(a % 2 == 0){
      if(a % 3 != 0 && a % 5 != 0){
        check = false;
        break;
      }
    }
  }
  if(check)
    cout << "APPROVED" << endl;
  else
    cout << "DENIED" << endl;
}

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

int main(){
  int N;
  cin >> N;
  
  int cnt=0, max_c=0, tmp=1, num=1;
  for(int i=1; i<=N; i++){
    tmp=i;
    while(tmp>0){
      if(tmp%2==0){
        cnt++;
        tmp/=2;
      }else{
        break;
      }
    }
    if(cnt>max_c){
      max_c=cnt;
      num=i;
    }
    cnt=0;
  }
  
  cout << num << endl;
  return 0;
}

Measured memory_bytes: 256
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    i = int(input())

    print(A[i-1])

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3064
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        n: u64,
    }
    let mut ans = 1;
    let divisor = 10_u64.pow(9) + 7;
    for i in 1..n + 1 {
        ans = (ans * i) % divisor;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2120
#include <cstdio>
using namespace std;
char s[110][110];
int map[110][110];
int dir[8][2]={{0,1},{0,-1},{1,1},{1,0},{1,-1},{-1,1},{-1,0},{-1,-1}};
main()
{
	int a,b,c,n=1,m,flag=0;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	{
		if (s[i][j]=='.')
		{
			for (int k=0;k<8;k++)
			if (i+dir[k][0]>=1 && i+dir[k][0]<=n && j+dir[k][1]>=1 && j+dir[k][1]<=m)
			{
				if (s[i+dir[k][0]][j+dir[k][1]]=='#')
					map[i][j]++;
			}
		}
	}
	for (int i=1;i<=n;i++,puts(""))
	for (int j=1;j<=m;j++)
	if (s[i][j]=='.')
		printf("%d",map[i][j]);
	else
		printf("#");
	
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N, a[120];

int main(void) {

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

	int ans = 0;

	for (int i = 1; i <= N; i++) {
		if ((i % 2 == 1) && (a[i] % 2 == 1)) { ans++; }
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3592
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)

# n = 2
# a = [1,5]
# b = [2,4]
# c = [3,6]

# n = 6
# a = [2, 3, 6, 14, 53, 159]
# b = [6, 9, 58, 79, 84, 323]
# c = [2, 50, 79, 288, 383, 2643]

a.sort!
b.sort!
c.sort!

# p a
# p b
# p c

# 上2段
dp = [0] * n
n.times do |i|
  bsi = a.bsearch_index {|x| x >= b[i]}
  jmax = (bsi.nil? ? n - 1 : bsi - 1)
  dp[i] = jmax + 1 + (i == 0 ? 0 : dp[i-1])
end

# puts "dp"
# p dp

ans = 0
n.times do |i|
  bsi = b.bsearch_index {|x| x >= c[i]}
  jmax = (bsi.nil? ? n - 1 : bsi - 1)
  ans = ans + (jmax >= 0 ? dp[jmax] : 0)
end

puts ans


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


N, M, C = map(int, input().split(' '))
B = list(map(int, input().split(' ')))
ans = 0
for _ in range(N):
    a = list(map(int, input().split(' ')))
    if sum([x * y for x, y in zip(a, B)]) + C > 0:
        ans += 1
print(ans)

Measured memory_bytes: 3060