akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
long long int kaizyou[200005] = { 1 };
//aからbまでの積を求める(mod)
long long int kai(long long int a, long long int b, long long int mod) {
	long long int tmp = 1;
	for (long long int i = a; i <= b; i++) {
		tmp *= i;
		tmp %= mod;
		kaizyou[i] = tmp;
	}

}

//累乗(繰り返し2乗法)　aのb乗(mod)を求める。
long long int rui(long long int a, long long int b, long long mod) {
	int memo[65] = {};
	long long int A[65] = {};
	long long int tmp = 1;
	for (int i = 0; i < 65; i++) {
		memo[i] = b % 2;
		b /= 2;
	}

	A[0] = a;
	A[0] %= mod;

	for (int i = 1; i < 65; i++) {
		A[i] = A[i - 1] * A[i - 1];
		A[i] %= mod;
	}
	for (int i = 0; i < 65; i++) {
		if (memo[i] == 1) {
			tmp *= A[i];
			tmp %= mod;
		}
	}
	tmp %= mod;
	return tmp;
}

//コンビネーション計算
long long int comb(long long int n, long long int r, long long int mod) {
	long long int tmp;

	tmp = (kaizyou[n] * rui(kaizyou[r], mod - 2, mod)) % mod;
	tmp *= rui(kaizyou[n - r], mod - 2, mod);
	tmp %= mod;
  	if(tmp<0){tmp=(mod+tmp)%mod;}
	return tmp;
}

int main() {
	long long int n, max = 0, s[100005] = {}, num[100005] = {}, right, left = 0, sum = 0,mod=1000000007;

	
	cin >> n;
	for (int i = 1; i <= n + 1; i++) {
		cin >> s[i];
		num[s[i]]++;
	}
	kai(1, 2*n, mod);
	for (int i = 1; i <= n + 1; i++) {
		if (num[s[i]] == 2 && left == 0) { left = i; }
		else if (num[s[i]] == 2) { right = i; }
	}

	for (int i = 1; i <= n + left - right + 1; i++) {
		if ((comb(n + 1, i, mod) - comb(n + left - right, i - 1, mod)) % mod < 0) {
			cout << mod +(comb(n + 1, i, 1000000007) - comb(n + left - right, i - 1, mod)) % mod << endl;
		}
		else {
			cout << (comb(n + 1, i, mod) - comb(n + left - right, i - 1, mod)) % mod << endl;
		}
	}
	for (int i = n + left - right + 2; i <= n + 1; i++) {
		cout << (comb(n + 1, i, mod)) % mod << endl;

	}

	return 0;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int L,R,d;
  cin>>L>>R>>d;
  
  
  int ans=0;
  
  for(int i=L;i<=R;i++){
    if(i%d==0){
      ans++;
    }
  }
  
  
  cout<<ans<<endl;
}

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

const int INF = 1e9;

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

    vector<int> h(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
    }

    vector<int> dp(n);
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for(int i=2; i<n; i++){
        int minimum = INF;
        for(int j=1; j<=min(i,k); j++){
            minimum = min(minimum, dp[i-j] + abs(h[i] - h[i-j]));
        }
        dp[i] = minimum;
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);        
        Long a = stdIn.nextLong();
        Long b = stdIn.nextLong();
        int c = stdIn.nextInt();
        int d = stdIn.nextInt();
        long lcm = LCM(c,d);
        System.out.println((b - a + 1) - ((b/c - (a - 1)/c) +( b/d - (a - 1)/d) - b/lcm + (a - 1)/lcm)); 
    }
    static long LCM(long x, long y){
        if( x < y){
            long t = x;
            x = y;
            y = t;
        }
        return x*y / gcd(x, y);
    }

    private static long gcd(long m, long n){
        if(n == 0) return m;
        else return gcd(n, m % n);
    } 
}

Measured memory_bytes: 22100
#include <stdio.h>

int main(){
  char c,t[6]={'a','i','u','e','o'};
  int ans=0;
  scanf("%c",&c);
  for(int i=0;i<5;i++){
    if(t[i]==c) ans=1;
  }
  printf("%s\n",ans==1?"vowel":"consonant");
  return 0;
}

Measured memory_bytes: 1588
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,s,n) for(int i = (s);i<(n);i++)
#define repe(i,s,n) for(int i = (s);i<=(n);i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
const ll MOD=1000000007,INF=1e18;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};



signed main(){
    string s;
    cin>>s;
    int x=s.size();
    if(x%2==0){
        if(s[0]!=s[x-1])cout<<"Second"<<endl;
        else cout<<"First"<<endl;
    }
    else{
        if(s[0]!=s[x-1])cout<<"First"<<endl;
        else cout<<"Second"<<endl;
    }
    return 0;
}

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

int main() {
	int a, b, c;
	scanf("%d/%d/%d", &a, &b, &c);

	a = a * 40 * 20 + b * 40 + c;

	printf("%s", a <= 2019 * 40 * 20 + 4 * 40 + 30 ? "Heisei" : "TBD");

	return 0;
}

Measured memory_bytes: 256
"use strict";

const Main = args => {
  const input = args.trim().split("\n");
  const S = input[1].split("");
  let current = 0;
  let max = 0;

  S.forEach(e => {
    if (e === 'I') {
      current++;
    } else {
      current--;
    }
    max = current > max ? current : max
  });
  console.log(max);
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<vector<int> > adj(n);
    for(int i=0; i<n-1; i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    queue<pair<int,int> > wait;
    wait.push(make_pair(0, 0));
    wait.push(make_pair(n-1, 1));
    vector<int> used(n, -1);
    used[0] = 0;
    used[n-1] = 1;
    while(!wait.empty()){
        int pos = wait.front().first;
        int color = wait.front().second;
        wait.pop();
        for(int i=0; i<(int)adj[pos].size(); i++){
            if(used[adj[pos][i]] == -1){
                used[adj[pos][i]] = color;
                wait.push(make_pair(adj[pos][i], color));
            }
        }
    }

    int count = 0;
    for(int i=0; i<n; i++){
        if(used[i]==0) count++;
    }
    if(count*2 > n){
        cout << "Fennec" << endl;
    }else{
        cout << "Snuke" << endl;
    }
    return 0;
}


Measured memory_bytes: 6272
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
using namespace std;
#define lol long long


int main()
{
	vector<int> A(2);
	cin >> A[0] >> A[1];
	sort(A.begin(), A.end());
	if (A[0] == A[1]) {
		cout << A[0] * 2 << endl;
	}
	else {
		cout << A[1] + A[1] - 1 << endl;
	}
}

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

int main(){
  int N;cin >> N;
  ll sum = 0;
  for(ll i=1;i<=N;i++){
    if(i%3!=0&&i%5!=0){
      sum += i;
    }
  }
  cout << sum << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> A(n);
    string S;
    cin >> S;
    for (int i = 0; i < n; i++)
        A[i] =  S[i] - '1';

    auto f = [&](){
        int b = 0;
        for (int i = 0; i < n; i++){
            b ^= (A[i] & 1) & (((n - 1) & i) == i);
        }
        return b;
    };

    if (f() == 1){
        puts("1");
        return 0;
    }

    if (any_of(A.begin(), A.end(), [](const auto &a){return a == 1;})){
        puts("0");
        return 0;
    }

    for (auto &a: A)
        a >>= 1;

    puts(f() == 1 ? "2" : "0");
}

Measured memory_bytes: 5380
#include<cstdio>
int main(){
    for(int i=0;i<3;i++){
        int h,m,s,h2,m2,s2;
        scanf("%d%d%d%d%d%d",&h,&m,&s,&h2,&m2,&s2);
        s2-=s;
        if(s2<0){
            s2+=60;
            m2--;
        }
        m2-=m;
        if(m2<0){
            m2+=60;
            h2--;
        }
        h2-=h;
        printf("%d %d %d\n",h2,m2,s2);
    }
}

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

int main() {
  string s;
  cin >> s;
  if (s.at(2) == s.at(3) && s.at(4) == s.at(5))
    cout << "Yes" << endl;
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        v[a-1]++;
    }

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    int cnt = 0;
    for(int i = n-1; i >= 0; i--){
        if(v[i] != 0){cnt = i+1; break;}
        else{v.pop_back();}
    }

    if(cnt <= k){cout << 0 << endl;}
    else{
        long long ans = 0;
        for(int i = v.size() - 1; i >= 0; i--){
            ans += v[i];
            cnt--;
            if(cnt == k){break;}
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int N,r,b;
    string s;
    cin>>N>>s;
    r=b=0;
    REP(i,N){
        if(s[i]=='R'){
            r++;
        } else {
            b++;
        }
    }
    cout<<(r>b?"Yes":"No")<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
struct P{
long long A;
long long B;
};
bool operator< (const P&a, const P&b){
return a.A < b.A;
}
int main(){
    const long long N = 100100;
     P p[N];
     long long n;
     long long m;
     std::cin >> n >> m;
     long long i = 0;
     for( ;i < n; i++ ){
        std::cin >> p[i].A;
        std::cin >> p[i].B;
     }
     std::sort (&p[0],&p[n]);
     long long cost = 0;
     for(i = 0; i < n; i++){
        if(m >= p[i].B){
            cost += p[i].A * p[i].B;
            m -= p[i].B;
        }
        else{
            cost += m * p[i].A;
            break;
        }

     }
     std::cout << cost;
}


Measured memory_bytes: 1792
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int digit(int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += x % 10;
		x /= 10;
	}
	return cnt;
}
int read() {
	int tmp;
	cin >> tmp;
	return tmp;
}
int xor128() {
	static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	int t = (x xor (x << 11));
	x = y; y = z; z = w;
	return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}

signed main() {
	string s;
	cin >> s;
	int a = 0, b = 0, c = 0;
	rep(i, s.size()) {
		if (s[i] == 'a') a++;
		else if (s[i] == 'b') b++;
		else c++;
	}
	if (max({ a,b,c }) - min({ a,b,c }) <= 1) {
		cout << "YES" << endl;
	}
	else cout << "NO" << endl;

	return 0;
}


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

int main(){
  string str;
  int i;

  cin >> str;
  for(i=0;i<str.size();i++){
    if(str[i] - 3 < 'A')str[i] += 23;
    else str[i] -= 3;
  }

  cout << str << endl;
}

Measured memory_bytes: 0
h,w,k=map(int,input().split())
hoge=[[0 for i in range(w)] for j in range(h)]
itigo=1
for i in range(h):
  moge=input()
  for j in range(w):
    if(moge[j]=='#'):
      hoge[i][j]=itigo
      itigo+=1
      
now=0
for i in range(h):
    for j in range(w):
      if(hoge[i][j]!=0):
        now=hoge[i][j]
      else:
        hoge[i][j]=now
    now=0

for i in range(h):
    for j in range(w):
      j=w-j-1
      if(hoge[i][j]!=0):
        now=hoge[i][j]
      else:
        hoge[i][j]=now
    now=0
      
for i in range(w):
    for j in range(h):
      if(hoge[j][i]!=0):
        now=hoge[j][i]
      else:
        hoge[j][i]=now
    now=0
    
for i in range(w):
    for j in range(h):
      j=h-j-1
      if(hoge[j][i]!=0):
        now=hoge[j][i]
      else:
        hoge[j][i]=now
    now=0

for i in range(h):
    for j in range(w):
      print(hoge[i][j],end=" ")
    print("")

Measured memory_bytes: 7504
# coding: utf-8

N = int(input())
Word = []
flag = True
for i in range(N):
    a = list(input())
    if a in Word:
        flag = False
        break
    Word.append(a)
if flag:
    for i in range(N-1):
        if Word[i][len(Word[i])-1] != Word[i+1][0]:
            flag = False
if flag:
    print("Yes")
else:
    print("No")

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

string animal = "SW";

void output(vector<int> &v){
    for(auto e : v)cout << animal[e];
    cout << endl;
    return;
}

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

    bool ok = false;
    for(int i=0;i<4;++i){
        vector<int> v;
        v.push_back(i>>1);
        v.push_back(i&1);
        for(int i=2;i<n;++i){
            if(v.back() == 0){
                if(s[i-1] == 'o')v.push_back(v[i-2]);
                else v.push_back(1^v[i-2]);
            }else{
                if(s[i-1] == 'o')v.push_back(1^v[i-2]);
                else v.push_back(v[i-2]);
            }
        }

        bool zero_flag = false;
        if(v[0] == 0 && s[0] == 'o' || v[0] == 1 && s[0] == 'x'){
            if(v.back() != v[1])continue;
            zero_flag = true;
        }else{
            if(v.back() == v[1])continue;
            zero_flag = true;
        }

        if(!zero_flag)continue;
        if(v.back() == 0 && s.back() == 'o' || v.back() == 1 && s.back() == 'x'){
            if(v[n-2] != v[0])continue;
            ok = true;
            output(v);
            break;
        }else{
            if(v[n-2] == v[0])continue;
            ok = true;
            output(v);
            break;
        }
    }

    if(!ok)cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 1444
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define LEN 201

int main(void) {
    int length, i, flag;
    char str[LEN]; 
    int mes = 0;
    while(scanf("%s",str) != EOF) {
        flag = 0;
        length = strlen(str);
        if(length % 2) {
            puts("NA");
            continue;
        } 
        for(i = 0; i < length; i++ ) {
            if( '1' > str[i] || str[i] >'6') {
                puts("NA");
                flag = 1;
                break;
            }
            i++; 
            if('1' > str[i] || str[i] > '5') {
                puts("NA");
                flag = 1;
                break;
            }
        }
        if(flag) {
            continue;
        }
        for(i = 0; i < length; i++ ) {
            mes = 91;
            mes += (str[i] - 48) * 5;
            mes += (str[++i] - 48);
            if(mes == 123) {
                mes = '.';
            } else if(mes == 124) {
                mes = '?';
            } else if(mes == 125) {
                mes = '!';
            } else if(mes == 126) {
                mes = 32;
            }
            printf("%c",mes);
        }
        puts("");
    }
    return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<int>> ans(H, vector<int>(W, 0));
    
    rep(i, H) {
        rep(j, W) {
            char c;
            cin >> c;
            if (c == '#') {
                for (int h = -1; h <= 1; h++) {
                    for (int w = -1; w <= 1; w++) {
                        if (h == 0 && w == 0) {
                            ans[i][j] = -1;
                            continue;  
                        }
                        if (i + h < 0 || i + h >= H || j + w < 0 || j + w >= W || ans[i + h][j + w] == -1) continue;
                        ans[i + h][j + w]++;
                    }
                }
            }
        }
    }

    rep(i, H) {
        rep(j, W) {
            if (ans[i][j] == -1) cout << "#";
            else cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}

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

int main(){
  string S,piece;
  cin >> S >> piece;

  string ans= S;
  int lenS= S.size();
  int lenp= piece.size();
  bool restorable= false;
  for(int offset= lenS- lenp; offset>= 0; offset--){
    bool match= true;
    for(int j=0; j<lenp; j++){
      if(S.at(offset+ j)=='?' || S.at(offset+ j)==piece.at(j)){
        continue;
      }
      else{
        match= false;
        break;
      }
    }

    if(match){
      restorable= true;
      for(int j=0; j<lenp; j++){
        ans.at(offset+ j)= piece.at(j);
      }
      for(int i=0; i<offset; i++){
        if(S.at(i)=='?'){ ans.at(i)= 'a'; }
      }

      break;
    }
    else{
      if(S.at(offset+ lenp- 1)=='?'){ ans.at(offset+ lenp- 1)= 'a'; }
    }
  }

  if(!restorable){ ans= "UNRESTORABLE"; }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=100005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

int n;
vi a;

int main(){
	cin>>n;
	a=vi(n);
	for(auto &i:a) cin>>i;
	ll res=0,t=0;
	for(int i=0;i<n-1;i++){
		(t+=Div(1,i+1))%=mod;
		(res+=(a[i+1]-a[i])*t)%=mod;
	}
	for(int i=1;i<n;i++) (res*=i)%=mod;
	cout<<res<<endl;
}

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

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int INF = int (1e9) + int (1e5);
const ll INFL = ll(2e18) + ll(1e10);
const ui MOD = 1E9 + 7;
const double EPS = 1e-9;
#define FOR(i,n) for (int i=0;i<(n);++i)
#define ROF(i,x) for(int i = (x) ; i >= 0 ; --i)
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ODD(x) (((x)&1)==0?(0):(1))
#define sign(x) ((x > 0) - (x < 0))
std::mt19937_64  generator(std::chrono::system_clock::now().time_since_epoch().count());

inline ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a, ll b) { return a ? gcd(b%a, a): b; }
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }


void READ(bool _local){
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _DEBUG
    if (_local)
        freopen ("in.txt", "r", stdin);
#endif
}

int main() {
    READ(1);
    ll n,m,v,p;cin>>n>>m>>v>>p;
    vector<ll> a(n);
    vi cnt(n);
    FOR(i,n) cin>>a[i];
    sort(a.begin(),a.end());
    cnt[n-1]=1;
    for(int i=n-2;i>=0;--i){
        if (a[i]==a[i+1]){
            cnt[i] = cnt[i+1]+1;
        }else cnt[i]=1;
    }


    int lo=0;
    int hi=n-p;
    while(hi>0 && a[hi-1]==a[hi])--hi;

    auto va=[&] (int x){
        if (a[x]+m<a[n-p]) return false;
        ll rest=(ll)m*(v-x-cnt[x]-p+1);
        int j=x+cnt[x];
        int last=n-p+1;
        int limit=(p>1?a[last]:a[n-1]+1);
        while(j<last && rest>0){
            ll y=a[x]+m-a[j];
            if (y<=0) return false;
            rest -= (ll)y*((a[j]<limit)?cnt[j]:last-j);
            j += cnt[j];
        }
        return rest<=0;
    };
    while(lo<hi){
        int mid=lo+(hi-lo)/2;
        if (va(mid))
            hi=mid;
        else {
            lo = mid + cnt[mid];
        }
    }
    cout << n-lo;
    return 0;
}



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

int main() {
	int A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;
	vector<int> vec (3);
	vec.at(0) = A * X + B * Y;
	vec.at(1) = max(X,Y) * C * 2;
	if(X > Y){
		vec.at(2) = min(X,Y) * C * 2 + (X - Y) * A;
	}
	else{
		vec.at(2) = min(X,Y) * C * 2 + (Y - X) * B;
	}
	sort(vec.begin(),vec.end());
	cout << vec.at(0) << endl;
}

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

const int MAX_N = 100;

void trace(int (&A)[MAX_N], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;
}

void insertionSort(int (&A)[MAX_N], int N) {
    for (int i = 1; i < N; ++i) {
        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
        trace(A, N);
    }
}

int main() {
    int N;
    int A[MAX_N];

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

    trace(A, N);
    insertionSort(A, N);

    return 0;
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define x first
#define y second
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //assert(freopen("input.txt","r",stdin));
    //assert(freopen("output.txt","w",stdout));
    int n;
    cin>>n;
    if(n>=30)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

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

typedef long long ll;
typedef complex<double> Vec;

ll N;
map<string, ll> S;
ll R;

int main() {
  cin >> N;
  for (ll i = 0; i < N; ++i) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    ++S[s];
  }
  for (auto scnt : S) {
    ll cnt = scnt.second;
    R += cnt * (cnt - 1) / 2;
  }
  cout << R << endl;
  return 0;
}


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

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

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
  long H,W,A,B;
  cin>>H>>W>>A>>B;
  long ans=0;
  COMinit();
  for(int i=B;i<=W-1;i++){
    ans+=COM(H-A-1+i,H-A-1)*COM(A-1+W-1-i,A-1);
    ans%=MOD;
  }
cout<<ans<<endl;
}


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

int main(){
  int n,a[27]; cin >>n;
  for(int i = 1; i<=26; i++) a[i]=99999;
  for(int i = 1; i<=n; i++){
    string s; cin >>s;
    int b[27] = {0};
    rep(j,s.size()) b[(s[j]-'a')+1]++;
    for(int j = 1;j<=26;j++) a[j]=min(a[j],b[j]);
  }
  for(int i = 1; i<=26; i++){
    for(int j = 1;j<=a[i]; j++) cout << char(i+'a'-1);
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

ll P = 1000000007;
vvi G = vv(100001, 0, 0, int);
ll dp[100001][2];
void dfs(int from, int now){
  if(G[now].size()==0) {
    dp[now][0] = dp[now][1] = 1;
    return;
  }
  dp[now][0] = dp[now][1] = 1;
  for(int i=0;i<G[now].size();i++){
    if(G[now][i]==from) continue;
    dfs(now, G[now][i]);
    dp[now][0] = (dp[now][0]*((dp[G[now][i]][0]+dp[G[now][i]][1])%P))%P;
    dp[now][1] = (dp[now][1]*dp[G[now][i]][0])%P;
  }
}
int main(int argc, char const *argv[]) {
  int N, a, b;
  std::cin >> N;
  for(int i=0;i<N-1;i++){
    std::cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  dfs(-1, 1);
  //for(int i=1;i<=N;i++) std::cout << dp[i][0] << " " << dp[i][1] << '\n';
  std::cout << (dp[1][0]+dp[1][1])%P << '\n';
  return 0;
}


Measured memory_bytes: 12800
h, w = [int(i) for i in input().split()]
s = ["."*(w+2)]
for hi in range(h):
  s.append("." + input() + ".")
s.append("."*(w+2))
ans = [""] * h
for hi in range(1,h+1):
  for wi in range(1,w+1):
    if s[hi][wi] == ".":
      ans[hi-1] += str((s[hi-1][wi-1:wi+2]+s[hi][wi-1]+s[hi][wi+1]+s[hi+1][wi-1:wi+2]).count("#"))
    else:
      ans[hi-1] += "#"
for hi in range(h):
  print(ans[hi])

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

int main(){
  int n;
  int i,j;
  int a[100004];
  int max = 0;
  int cnt = 0;

  scanf("%d", &n);

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

  i = 0;
  while(i < n - 1){
    cnt = 0;
    j = i;
    while(j < n - 1 && a[j] >= a[j + 1]){
      cnt++;
      j++;
    }
    if(max < cnt) max = cnt;

    i = j + 1;
  }

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

  return 0;
}


Measured memory_bytes: 512
import math
n=int(input())
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

f=[a,b,c,d,e]
g=[0,0,0,0,0,n]
ans=0

print(math.ceil(n/min(f))+4)


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

int main()
{
    string str;
    cin >> str;
    int tmp;
    int ans = 1000;
    for(int i = 0; i < str.size() - 2; i++){
        tmp = stoi(str.substr(i, 3));
        ans = min(ans, abs(tmp - 753));
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
w,h,n=map(int,input().split())
li=[list(map(int, input().split())) for _ in range(n)]
hi=[0]*h;wi=[0]*w
for i in range(n):
    x=li[i][0]
    y=li[i][1]
    if li[i][2]==1:
        for j1 in range(x):
            wi[j1]=1
    elif li[i][2]==2:
        for j2 in range(x,w):
            wi[j2]=1
    elif li[i][2]==3:
        for j3 in range(y):
            hi[j3]=1
    else:
        for j4 in range(y,h):
            hi[j4]=1
res=w*h
res-=sum(wi)*h
res-=(sum(hi))*(w-sum(wi))
print(res)

Measured memory_bytes: 65168
// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
// clang-format on

const int N = 200010;
const int INF = INT_MAX;

int a[N];
vector<int> G[N];

int ans[N];
int dp[N];
void dfs(int v, int p) {
    int idx = lower_bound(dp, dp + N, a[v]) - dp;
    int t = dp[idx];
    dp[idx] = a[v];
    ans[v] = lower_bound(dp, dp + N, INF) - dp - 1;

    for (int c : G[v])
        if (c != p) dfs(c, v);

    dp[idx] = t;
}

int main() {
    int n;
    cin >> n;
    rep(i, n) cin >> a[i];

    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }

    fill(dp, dp + N, INF);
    dp[0] = 0;
    dfs(0, -1);

    rep(i, n) cout << ans[i] << "\n";
    return 0;
}


Measured memory_bytes: 31232
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
#define ll long long
#define rep(i,n) for (i = 0; i < n; ++i) 
#define REP(i,k,n) for (i = k; i <= n; ++i) 
#define REPR(i,k,n) for (i = k; i >= n; --i)
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int check(ll n)
{
  ll s=sqrt(n);
  if(s*s==n)
    return 1;
  else
    return 0;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
#ifndef ONLINE_JUDGE 
   freopen("input.txt", "r", stdin); 
   //freopen("error.txt", "w", stderr); 
  freopen("output.txt", "w", stdout); 
#endif 
   
 ll T = 1 ;
 //cin>>T;
 for(ll t=1;t<=T;t++)
 {
  ll n;
  cin>>n;
  if(n>=30)
  cout<<"Yes";
  else
  cout<<"No";
 }

  return 0;
}


Measured memory_bytes: 3660
#include<stdio.h>
int main(){
  int a, b;
  int x;

  scanf("%d%d",&a,&b);
  if((a+b)%2!=0){
    printf("IMPOSSIBLE\n");
  }
  else {
    x=(a+b)/2;
    printf("%d\n",x);
  }
}
    

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e16;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)

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

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//
//modpow.cpp
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll cnt[100005];
int main() {
    init();
    ll N;
    cin >> N;
    rep(i,N){
        ll a;
        cin >> a;
        cnt[a]++;
    }

    bool isok = true;
    if(N%2){
        if (cnt[0] != 1) isok = false;
        repe(i,1,N/2+1){
            if (cnt[i * 2] != 2) isok = false;
        }
    }
    else{
        repe(i,1,N/2+1){
            if (cnt[i * 2 - 1] != 2) isok = false;
        }
    }

    if(!isok){
        cout << 0 << endl;
        return 0;
    }

    cout << modpow(2, N / 2, MOD) << endl;
}

Measured memory_bytes: 1024
N = int(input())
arr = list(map(int, input().split()))
count = 0

for i in range(1,N-1):
    if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
        continue
    if arr[i] < arr[i-1] and arr[i] < arr[i+1]:
        continue
    count += 1

print(count)

Measured memory_bytes: 3060
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            String a = in.next();
            String b = in.next();
            if (a.length() != b.length()) {
                out.println(a.length() > b.length() ? "GREATER" : "LESS");
                return;
            }
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    out.println(a.charAt(i) > b.charAt(i) ? "GREATER" : "LESS");
                    return;
                }
            }
            out.println("EQUAL");
        }

    }

    static class FastScanner {
        private InputStream in;
        private byte[] buffer = new byte[1024];
        private int bufPointer;
        private int bufLength;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (bufPointer >= bufLength) {
                if (bufLength == -1)
                    throw new InputMismatchException();

                bufPointer = 0;
                try {
                    bufLength = in.read(buffer);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (bufLength <= 0)
                    return -1;
            }
            return buffer[bufPointer++];
        }

        private static boolean isPrintableChar(int c) {
            return c >= 33 && c <= 126;
        }

        public String next() {
            StringBuilder sb = new StringBuilder();

            int b = readByte();
            while (!isPrintableChar(b))
                b = readByte();

            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }

            return sb.toString();
        }

    }
}



Measured memory_bytes: 21460
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
	string a, b;
	cin >> a >> b;
	if (a.length() < b.length()) {
		cout << "LESS" << endl;
	}
	else if (a.length() > b.length()) {
		cout << "GREATER" << endl;
	}
	else {
		for (int i = 0; i < a.length(); i++) {
			if (a[i] - 'a' > b[i] - 'a') {
				cout << "GREATER" << endl;
				return 0;
			}
			else if (a[i] - 'a' < b[i] - 'a') {
				cout << "LESS" << endl;
				return 0;
			}
		}
		cout << "EQUAL" << endl;
	}
	return 0;
}

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

using namespace std;

#define ll long long

signed main(void) {
    ll n;
    cin >> n;
    ll div5 = 0LL;
    if(n%2LL==1LL){
        cout << 0LL << endl;
        return 0;
    }
    for(ll i=1LL;;i++){
        ll temp = pow(5LL,i);
        if(temp>n) break;
        div5 += n/(temp*2LL);
    }
    cout << div5 << endl;
    return 0;
}

Measured memory_bytes: 512
s=input()
mod=pow(10,9)+7
dp=[0]*4
dp[0]=1
for si in s:
  if si=='A':
    dp[1]+=dp[0]
  elif si=='B':
    dp[2]+=dp[1]
  elif si=='C':
    dp[3]+=dp[2]
  else:
    tmp3=dp[2]
    tmp2=dp[1]
    tmp1=dp[0]
    dp[3]*=3
    dp[3]+=tmp3
    dp[2]*=3
    dp[2]+=tmp2
    dp[1]*=3
    dp[1]+=tmp1
    dp[0]*=3
  dp[3]%=mod
  dp[2]%=mod
  dp[1]%=mod
  dp[0]%=mod
print(dp[3])


Measured memory_bytes: 9232
N = int(input())
X = [int(i) for i in input().split()]

min_p = min(X)
max_p = max(X)

ans = float("inf")
for p in range(min_p, max_p+1):
    hp = 0
    for i in range(N):
        hp += (X[i]-p)**2
    ans = min(ans, hp)
    
print(ans)

Measured memory_bytes: 3064
#pragma GCC optimize("O3")

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace __gnu_pbds;
using namespace std;
 
typedef
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 1e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int dp[N][13];

void upd (int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	
}

int main () {
	SpeedForce;

	cin >> s;
	n = sz(s);
	dp[0][0] = 1;
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < 13; j ++) {
		//	if (dp[i][j] > 0)
		//		cout << ' ' << i << ' ' << j << ' ' << dp[i][j] << '\n';
			if (s[i] == '?') {
				for (int k = 0; k < 10; k ++) {
					upd(dp[i + 1][(j * 10 + k) % 13], dp[i][j]);
				}
			} else {
				int k = s[i] - '0';
				upd(dp[i + 1][(j * 10 + k) % 13], dp[i][j]);
			}
		}
	}
	cout << dp[n][5];

	return Accepted;
}

// B...a

Measured memory_bytes: 5584
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 60


int main(){
  int n,m,l;
  int d,a,k,t;
  vector<pair<int,int> > vec[8*5+10];
  
  
  scanf("%d%d%d",&n,&m,&l);

  for(int i=0;i<m;i++){
    scanf("%d%d%d%d",&d,&a,&k,&t);
    int s = (d*n) + (a-1);
    vec[s].push_back({k,t});
  }

  int dp[8*5+10][301] = {};
  
  for(int i=0;i<=5*n;i++){
    for(int j=0;j<=l;j++){
      dp[i][j] = -INF;
    }
  }
  
  dp[0][0] = 0;
  
  for(int i=0;i<5*n;i++){

    for(int j=0;j<vec[i].size();j++){
      for(int k=0;k<l;k++){
        dp[i + vec[i][j].first][k+1] = max(dp[i + vec[i][j].first][k+1], dp[i][k] + vec[i][j].second);
      }
    }
    for(int j=0;j<=l;j++){
      dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
    }
  }

  int ans = 0;
  for(int i=0;i<=l;i++) ans = max(ans,dp[5*n][i]);
  
  printf("%d\n",ans);
  
  return 0;
}

Measured memory_bytes: 3284
import scala.io.StdIn

object Main {

  def main(args: Array[String]): Unit  = {
    val Array(aStr, bStr) = StdIn.readLine().split(" ")
    val a: Int = aStr.toInt
    val b: Int = bStr.toInt

    if (a > b) println("a > b") else if (a < b) println("a < b") else println("a == b")
  }
}

Measured memory_bytes: 43800
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N; cin >> N;
    vector<ll> H(N+1);
    if(N==1){
        cout << "Yes" << endl;
        return 0;
    }
    bool f=true;
    for(int i=0;i<N;i++){
        cin >> H[i];
    }
    H[N] = LNF;
    for(int i=N;i>0;i--){
        cerr << H[i-1] << "\t" << H[i] << "\t" << f << endl;
        if(H[i-1]>H[i]){
            if(H[i-1]-1==H[i]){
                H[i-1]--;
            }else{
                f=false;
                break;
            }
        }
    }

    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 1024
S = gets.to_i

m = S / (10 ** 9)
n = 10 ** 9 - (S % (10 ** 9))

if S == 10 ** 18
	puts '0 0 0 1000000000 1000000000 0'
else
	puts [n, 0, 0, m + 1, 10 ** 9, m]
end

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

using namespace std;

#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;

const int M = 100100;
const int A = 16;
const int B = 1 << A;
const int ROOT = 0;

vector<int> g[M], h[M];

int n;
int cnt[A];
int d[B];

void read() {
  cin >> n;
  for (int i = 0; i < n - 1; ++i) {
    int u, v, x;
    cin >> u >> v >> x;
    g[u].push_back(v);
    g[v].push_back(u);
    h[u].push_back(x);
    h[v].push_back(x);
  }
}

void dfs(int v, int from, int by) {
  int cur = 0;
  for (int i = 0; i < (int) g[v].size(); ++i) {
    int to = g[v][i];
    if (to == from)
      continue;
    cur ^= h[v][i];
    dfs(to, v, h[v][i]);
  }
  cnt[by ^ cur]++;
}

int bit(int mask, int i) {
  return (mask >> i) & 1;
}

bool good(int mask) {
  int res = 0;
  for (int i = 1; i < A; ++i)
    if (bit(mask, i))
      res ^= i;
  return res == 0;
}

int main() {
#ifdef LOCAL
  assert(freopen("f.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  int root = ROOT % n;
  dfs(root, -1, 0);

  int ans = 0;
  int rmask = 0;
 
  for (int i = 1; i < A; ++i) {
    ans += cnt[i] / 2;
    cnt[i] %= 2;
    if (cnt[i])
      rmask |= 1 << i;
  }

  d[0] = 0;
  for (int i = 1; i < B; ++i)
    d[i] = 1;

  assert(good(rmask));

  for (int c = 1; c < B; ++c)
    if (good(c)) {
      int rem = (B - 1) ^ c;
      for (int t = rem; ; t = (t - 1) & rem) {
        d[t ^ c] = max(d[t ^ c], 1 + d[t]);
        if (t == 0)
          break;
      }
    }

  ans += __builtin_popcount(rmask) - d[rmask];
  cout << ans << endl;
}



Measured memory_bytes: 18944
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define divceil(A, B) ((A + (B - 1)) / B)
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr

using namespace std;

int main(){

    ll n;
    cin >> n;
    ll ans = LLONG_MAX; 

    for(int i = 1; i <= 1000000; i++){
        if(n % i == 0){
            ans = min(ans, (i - 1) + (n / i - 1));
        }
    }

    cout << ans << endl;

}


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

using namespace std;

int main()
{
	long long int n,m;

	scanf("%lld %lld", &n, &m);

	long long int num = 0;

	if (n > m / 2)
	{
		num = m / 2;
	}else
	{
		num = n;
		m -= 2 * n;
		num += m / 4;
	}

	
	
	printf("%lld\n", num);

	return 0;
}
	

Measured memory_bytes: 256
#include <cstdio>
#include <map>

using namespace std;

int main() {
    int n, a, ans = 0;
    map<int, int> d;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        ++d[a];
    }
    for (auto i = d.begin(); i != d.end(); ++i) if ((*i).second % 2) ++ans;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 4864
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    val a = new Array[Int](n)
    for (i <- 0 until n) {
      a(i) = sc.nextInt
    }

    println(if (a.count(_ % 2 != 0) % 2 == 0) "YES" else "NO")
  }

}


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

int main(){
  int a,b;
  cin >> a >> b;
  int ans =1;
  while(true){
    if(b*ans >= a){
      cout<<ans <<endl;
      break;
    }
    ans++;
    
  }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    double r;
    cin >> r;

    printf("%.6lf %.6lf\n", r * r * M_PI, 2 * r * M_PI);
    //setprecision(7) <<
}


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

int main() {
	char n[4];
	cin >> n;
	for (int i = 0; i < 3; i++) {
		switch (n[i]) {
		case '1':
			n[i] = '9';
			break;
		case '9':
			n[i] = '1';
			break;
		default:
			break;
		}
	}
	for (int i = 0; i < 3; i++) {
		cout << n[i];
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    map<int, int> even;
    map<int, int> odd;
    for(int i=0;i<n;i++){
        int v;
        cin>>v;
        if(i%2==0){
            if(even.find(v)==even.end()){
                even[v]=1;
            }
            else{
                even[v]+=1;
            }
        }
        else{
            if(odd.find(v)==odd.end()){
                odd[v]=1;
            }
            else{
                odd[v]+=1;
            }
        }
    }
    int ke,ko,ev1=0,ev2=0,ov1=0,ov2=0;
    for(auto itr=even.begin();itr!=even.end();itr++){
        if(itr->second>=ev1){
            ev2=ev1;
            ev1=itr->second;
            ke=itr->first;
        }
        else if(itr->second>ev2){
            ev2=itr->second;
        }
    }
    for(auto itr=odd.begin();itr!=odd.end();itr++){
        if(itr->second>=ov1){
            ov2=ov1;
            ov1=itr->second;
            ko=itr->first;
        }
        else if(itr->second>ov2){
            ov2=itr->second;
        }
    }
    int half = n/2;
    if(ke!=ko)cout<<half-ev1+half-ov1<<endl;
    else cout<<min(half-ev1+half-ov2,half-ev2+half-ov1)<<endl;
    return 0;
}


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

int main(){
  string str;
  int count [26] = {};
  int i;
  getline(cin ,str);
  while(str[0]){
    i=0;
    while(str[i]){
      if('A' <= str[i] && str[i] <= 'z')
        count[(str[i]-'A')%('a'-'A')]++;
      i++;
    }
    getline(cin ,str);
  }
  for(int i=0; i<26; i++){
    cout << char('a'+ i) << " : " << count[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 3212
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
#define int long long
using namespace std;
using namespace __gnu_cxx;
typedef long long LL;
const int MAXN = 2e6+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
signed main(){ 
	int n; cin>>n;
	int k=n/100,p=n%100;
	if(p>(k*5)%100 && n<2000) puts("0"); else puts("1");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	int n;
	while(cin>>n,n){
	int mo[102]={0};
		bool l=0,r=0;
		int cnt=0;
		string mae="tmp";
		for(int i=0;i<n;i++){
			string tmp;
			cin>>tmp;
			if(tmp=="lu")l=1;
			else if(tmp=="ru")r=1;
			else if(tmp=="ld")l=0;
			else if(tmp=="rd")r=0;
			if(r==l&&mae[0]!=tmp[0])cnt++;
			mae=tmp;
		}
		cout<<cnt<<endl;
		}
	return 0;
}

Measured memory_bytes: 1220