akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"bufio"
	"fmt"
	"os"
	"reflect"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	sc.Split(bufio.ScanWords)
	defer out.Flush() // !!!!coution!!!! you must use Fprint(out, ) not Print()
	/* --- code --- */
	N, M := nextInt(), nextInt()

	for i := 0; i < M; i++ {
		A := nextInt()
		N -= A
		if N < 0 {
			fmt.Println("-1")
			return
		}
	}

	fmt.Println(N)

}

// -*-*-*-*-*-*-*-*-
// * I/O utilities *
// -*-*-*-*-*-*-*-*-

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

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

func split(s string) []string {
	ret := make([]string, len([]rune(s)))
	for i, v := range []rune(s) {
		ret[i] = string(v)
	}
	return ret
}

func PrintOut(src interface{}, joinner string) {
	switch reflect.TypeOf(src).Kind() {
	case reflect.Slice:
		s := reflect.ValueOf(src)
		for idx := 0; idx < s.Len(); idx++ {
			fmt.Fprintf(out, "%v", s.Index(idx))
			if idx < s.Len()-1 {
				fmt.Fprintf(out, "%s", joinner)
			} else {
				fmt.Fprintln(out)
			}
		}
	default:
		fmt.Fprintln(out, "fuck")
	}
}

// -*-*-*-*-*-*-*-*-
// * tool snippets *
// -*-*-*-*-*-*-*-*-
func duplicate2Int(base [][]int) (ret [][]int) {
	ret = make([][]int, len(base))
	for i, v := range base {
		ret[i] = append([]int{}, v...)
	}
	return
}

// -*-*-*-*-*-*-*-*-*-*-*-*-*-
// * Algorithms Utility Zone *
// -*-*-*-*-*-*-*-*-*-*-*-*-*-

// -*-*-*-*-*-*-*-
// * 1. nibutan  *
// -*-*-*-*-*-*-*-
func lower_bound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := (l + r) / 2
		if arr[mid] < target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

func upper_bound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := (l + r) / 2
		if target < arr[mid] {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
// * math flavor typical theories *
// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
func gcd(a, b int) int {
	if a > b {
		return gcd(b, a)
	}
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func pow(a, b int) (ret int) {
	ret = a
	// 10^2 = 100ってことは10に10を1回掛けることだね
	// なので初期値を含めると上限b-1未満
	for i := 0; i < b-1; i++ {
		ret *= a
	}
	return
}

func powMod(n, m, mod int) (ret int) {
	ret = 1
	for m > 0 {
		if m&1 == 1 {
			ret *= n
			ret %= mod
		}
		n *= n
		n %= mod
		m >>= 1
	}
	return ret
}


Measured memory_bytes: 1776
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
main(){
    int A,B,C;
    cin >> A >> B >> C;
    if(!(A & 1) && A == B && B == C && C == A){
        cout << -1 << endl;
        return 0;
    }
    int num[] = {A,B,C},cnt = 0;
    for(;!(num[0]&1 || num[1]&1 || num[2]&1);cnt++){
        int tmp[3] = {num[1]/2+num[2]/2,num[0]/2+num[2]/2,num[0]/2+num[1]/2};
        num[0] = tmp[0];
        num[1] = tmp[1];
        num[2] = tmp[2];
    }
    cout << cnt << endl;
}   

Measured memory_bytes: 256
#include <iostream>

int main()
{
  int a, b , c;
  std::cin >> a >> b >> c;
  int abc_max = std::max(a, std::max(b, c));

  int min2 = 0, ans = 0;
  if (abc_max == a) min2 += (b+c);
  else if (abc_max == b) min2 += (a+c);
  else if (abc_max == c) min2 += (b+a);

  if (min2 % 2) {
    ans += (abc_max*2 - min2)/2 + 2 ;
  }
  else ans += (abc_max*2 - min2)/2 ;

  std::cout << ans << '\n';
}


Measured memory_bytes: 256
#include <iostream>

#include <map>
#include <string>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cinttypes>


using namespace std;

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

	for (size_t i = 0, n = s.size(); i < n; ++i)
		cout << 'x';
	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main (void)
{
	int a1,b1,a2,b2;
	scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
	if(a1>a2)
	{
	     int t=a1;
	     a1=a2;
	     a2=t;
	     int p=b1;
	     b1=b2;
	     b2=p;
	}
	if(a2>=b1)
	printf("0\n");
	else
	{
		int min=b1;
		if(min>b2)
		min=b2;
		printf("%d\n",min-a2);
	}
	return 0;
}

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

inline long long read(){
    long long s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int main(){
    int x = read(), y = read();
    if (y % 2 != 0) puts("No");
    else if ((y - x*2) % 2 != 0) puts("No");
    else if(y > x * 4) puts("No");
    else if(y < x * 2) puts("No");
    else puts("Yes");
    return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm(a, b) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

vector<int> Div(int n) {
    vector<int> ret;
    for(int i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);

            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++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;

    }
}

LL comb(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;

}

LL Bin(LL n, LL k) {
    if(k < 0 || n < k) {
        return 0;

    }
    LL ret = 1;
    for(LL i = 1; i <= k; ++i) {
        ret *= n--;
        ret /= i;

    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    LL h, w, a, b;
    cin >> h >> w >> a >> b;

    combInit();
    LL res = 0;
    for(int i = 0; i < h - a; ++i) {
        res += comb(i + b - 1, i) * comb(w - b - 1 + h - i - 1, w - b - 1) % MOD;

    }
    cout << res % MOD << endl;
    return 0;
}



Measured memory_bytes: 4992
import sys
import numpy as np
from math import ceil as C, floor as F
from collections import defaultdict as D
from functools import reduce as R

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if len(ss) > 1 else [ss]
def Is(): return _Is(I())

a, b = I()
print(a*b)

Measured memory_bytes: 27148
#include <stdio.h>
#include <math.h>

using namespace std;

int main(){
	double a,b,c,degree,S;
	scanf("%lf %lf %lf",&a,&b,&degree);
	S = (0.5)*a*b*sin(M_PI*degree/180);
	c = sqrt(a*a+b*b-2*a*b*cos(M_PI*degree/180));
	printf("%.8lf\n",S);
	printf("%.8lf\n",a+b+c);
	printf("%.8lf\n",2*S/a);
}

//naoto


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define here(x) cout << " #x = " << x << endl;
#define show(x) {for( auto ii : x) cout << ii << setw(4); cout << endl;}
#define shop(n,x) {for(int i = 0; i < n; i++) cout << x << setw(4); cout << endl;}
#define ff first
#define ss second
#define sq(x) (x*x)
#define endl '\n'
#define en " "
#define pb push_back
#define mpair make_pair
ll mod=1000000007;
double pi=3.1415926536;
int main()
{
	fastio();
	int tt = 1;
	//cin >> tt;
	while(tt--)
	{
		// go fast 		check		//		CHECK -> if()   else if()
		
		ll n, x=0, m=0, y=0, d=1, k=mod;
		cin >> n;
		double a[n + 1], dp[n + 1][n + 1] = {};
		dp[0][0] = 1;
		for(int i = 1; i <= n; i++)
		{
			cin >> a[i];
			dp[0][i] = dp[0][i - 1] * (1 - a[i]);
		}
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				dp[i][j] = a[j] * dp[i - 1][j - 1] + (1 - a[j]) * dp[i][j - 1];
		
		double f = 0;	
		for(int i = 1 + n / 2; i <= n; i++)
			f += dp[i][n];
		cout << fixed << setprecision(12) << f ;
	}
}

Measured memory_bytes: 70656
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, int> P;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

int main(void){
	int i,z[3];
	for(i=0; i<3; ++i){
		cin >> z[i];
	}
	sort(z,z+3);
	cout << ((z[0] == z[1])?z[2]:z[0]) << endl;
	return 0;
}


Measured memory_bytes: 256
memo = {}
def f(n):
    if n in memo:
        return memo[n]
    if n < 6:
        memo[n] = n
        return n
    ret = n
    for i in range(6, 0, -1):
        if 6 ** i <= n:
            t = f(n - 6 ** i) + 1
            if t < ret:
                ret = t

    for i in range(5, 0, -1):
        if 9 ** i <= n:
            t = f(n - 9 ** i) + 1
            if t < ret:
                ret = t

    memo[n] = ret
    return ret
def main():
    print(f(int(input())))

main()


Measured memory_bytes: 6172
#include<bits/stdc++.h>
#define ll long long int
const ll mod=1e9+7;
const int maxn=2e5+50;
using namespace std;
 main()
//int found; found=chaine.find(cara); if (found!=std::string::npos) how to verify if a caracter exists in a chaine
// toupper(caractere) ==> return the majuscule of a caractere
//floor(x) Returns the largest integer smaller than x
//ceil(x) returns  Returns the smallest integer greater
//printf("%.10f",res);
{
	int n,k;
	cin>>n>>k;
	double prob;
	prob=0.0;
	for(int p=1;p<=n;p++)
	{
		double actprob;
		actprob=1.0/n;
		
		int p1;
		p1=p;
		while(p1<k)
		{
			p1=p1*2;
			actprob=actprob*0.5;
		}
		prob+=actprob;
	}
	printf("%.10f",prob);
}


Measured memory_bytes: 256
//   PIGMEISTER™   //

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define sidha(i,x,n) for(ll i=(ll)(x);i<(ll)(n);++i)
#define ulta(i,x,n) for(ll i=(ll)(x);i>=(ll)(n);--i)
#define sab(a) a.begin(),a.end()
#define bas(a) a.rbegin(),a.rend()
#define test ll _;cin>>_;while(_--)
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD (ll)1000000007
//#define MOD (ll)998244353
#define MAX 100005

int main()
{
    jaldi;
    
    string s;
    ll k;
    cin >> k >> s;
    if (s.size() <= k) cout<<s;
    else{
        sidha(i, 0, k)cout<<s[i];
        cout<<"...";
    }
 
    return 0;
}

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)   
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

#include <bits/stdc++.h>
#define rep(i,a,n) for(ll i = a;i < n;i++)
typedef long long ll;
using namespace std;


int main(){ 
    string s;
    ll k;
    cin >> s >> k;
    ll n = (ll)s.size();

    ll dp[201][2][201];
    rep(i,0,201) rep(j,0,2) rep(k,0,201) dp[i][j][k] = 0;

    dp[0][0][0] = 1;

    rep(i,0,n){
        rep(j,0,n){
            if(s[i] == '0'){
                dp[i+1][0][j] += dp[i][0][j];
            }
            else{
                dp[i+1][0][j+1] += dp[i][0][j];
                dp[i+1][1][j+1] += ((ll)(s[i] - '0') - 1)*dp[i][0][j];
                dp[i+1][1][j] += dp[i][0][j];
            }

            dp[i+1][1][j+1] += 9*dp[i][1][j];
            dp[i+1][1][j] += dp[i][1][j];
        }
    }

    cout << dp[n][0][k] + dp[n][1][k] << endl;
}


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

int main(){
    long long N;
    long long count=0;
    cin >> N;
    long long a[N],b[N],c[N];

    for(long long i=0;i < N;i++){
        cin >> a[i];
    }
    for(long long i=0;i < N;i++){
        cin >> b[i];
    }
    for(long long i=0;i < N;i++){
        cin >> c[i];
    }


    sort(a,a+N);
    sort(b,b+N);
    sort(c,c+N);

    for(long long i= 0;i < N;i++){
       count += (lower_bound(a,a+N,b[i])-a) * (c+N-upper_bound(c,c+N,b[i]));
    }
    cout << count << endl;
}

Measured memory_bytes: 2688
#include<iostream>
#include<stdio.h>
using namespace std;
int t[10],v1,v2,sum;
double x;
char ch;
int main(){
  while(cin>>t[0]){
    sum=t[0];
    scanf("%c",&ch);
    for(int i=1;i<10;i++){
      cin>>t[i];
      sum+=t[i];
      t[i]=sum;
      scanf("%c",&ch);
    }
    cin>>v1>>ch>>v2; scanf("%c",&ch);
    //v1*t+v2*t==sum;
    //t*(v1+v2)==sum;
    //t==sum/(v1+v2);
    //v1*t==v1*(sum/(v1+v2));
    x=v1*((double)sum/(v1+v2));
    //cout<<x<<endl;
    for(int i=0;i<10;i++){
      //cout<<t[i]<<endl;
      if(x<=t[i]){cout<<i+1<<endl;break;}
    }
  }
  return 0;
}

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

using namespace std;

int main()
    {
    int n,c,x,y,cnt1=0;
    double cnt=0;
    vector<int>v;
string s;
cin>>n>>c;
cin>>s;
for(int i=0;i<n;i++){
    if(i==c-1){
        cout<<(char)(tolower(s[i]));
    }
    else{
        cout<<s[i];
    }
}
        return 0;
    }


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
using namespace std;
typedef long long ll;
ll s2l(string str){
  ll res;
  stringstream s;
  s<<str;
  s>>res;
  return res;
}

int check(string x,string y){
  if(x[0]=='0'&&x.size()>1||(y[0]=='0'&&y.size()>1))return 0;
  ll a = s2l(x);
  ll b = s2l(y);

  //a == c-d
  //b == c+d
  //a+b == c+c
  //a-b == -d-d
  if((a+b)%2==1)return 0;
  else if((a-b)%2==1)return 0;
  else if(a-b>0)return 0;
  else return 1;
}

int main(){
  int cnt=0;
  string str;
  cin>>str;
  for(int i=1;i<(int)str.size();i++){
    cnt+=check(str.substr(0,i),str.substr(i,str.size()-i));
  }
  cnt+=check("0",str);
  cout<<cnt<<endl;
  return 0;
}

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

using namespace std;

const long long MOD = 1e9 + 7;
long long n;
long long k;
long long s = 1, s1 = 1, s2 = 1, s3, s4;

long long C (long long n, long long m) {
	return n * (n - 1) / 2;
}

int main () {
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		s = s * 10 % MOD;
		s %= MOD;
	}
	for (int i = 1; i <= n; i ++ ) {
		s1 = s1 * 9 % MOD;
		s1 %= MOD;
	}
	for (int i = 1; i <= n; i ++ ) {
		s2 = s2 * 8 % MOD;
		s2 % MOD;
	}
	s = s + MOD;
	long long s4 = s - (s1 * 2 - s2) % MOD;
	s4 %= MOD;
	cout << s4 << endl;
	return 0;
}


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


#define _GLIBCXX_DEBUG
typedef long long ll ;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

#include <bits/stdc++.h>
using namespace std;

int main(){
string s;
cin>>s;
int n = s.size();
char a = s.at(n-1);
if(a=='3')cout<< "bon" <<endl;
else if(a=='0'||a=='1'||a=='6'||a=='8')cout<< "pon" <<endl;
else cout<< "hon" <<endl;
}



Measured memory_bytes: 3596
// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
using namespace std;

#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

int main() {
    ll N, M;
    cin >> N >> M;
    V<pair<ll, string>> vs(M);
    for (auto &&ele : vs) cin >> ele.first >> ele.second;
    V<ll> wav(N + 1);
    V<bool> acv(N + 1);
    ll a = 0, b = 0;
    for (auto &&ele : vs) {
        ll i;
        string s;
        tie(i, s) = ele;
        if (s == "WA") {
            wav[i]++;
        } else {
            if (acv[i]) continue;
            acv[i] = true;
            a++;
            b += wav[i];
        }
    }

    cout << a << ' ' << b << endl;
    return 0;
}


Measured memory_bytes: 7296
/******************************************
* AHAM BRAHMASHMI ;) *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define F first
#define S second

int main()
{

// #ifndef ONLINE_JUDGE
// 	// for getting input from input.txt
// 	freopen("input1.txt", "r", stdin);
// 	// for writing output to output.txt
// 	freopen("output1.txt", "w", stdout);
// #endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	int cand  = n%10;
	if(cand==2 or cand==4 or cand==5 or cand==7 or cand==9)
		cout<<"hon\n";
	else if(cand==0 or cand==1 or cand==6 or cand==8)
		cout<<"pon\n";
	else
		cout<<"bon\n";
	return 0;
}


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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで降順
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using vs  = vector<string>;
using pii = pair<int,int>;
constexpr ll inf = 1ll<<61;
constexpr ll mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>T add(const T &a, const T &b){return (a+b)%mod;}

signed main(){
  string s; cin >> s;
  if(s[0] == s[1] or s[1] == s[2] or s[2] == s[3]) cout << "Bad" << endl;
  else cout << "Good" << endl;
}


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

int main(){
	int n;
		cin >>n;
		for(int i=0;i<n;i++){
			int ans =0;
			int y,m,d;
			cin >> y >> m >> d;
			int syear =19*5+20*5;
			int byear =20*10;
			for (int j = y+1; j<=999; j++){
				if (j%3==0) ans+=byear;
				else ans+=syear;
			}
			for (int j= m+1; j<=10;j++){
				if(y%3==0)ans+=20;
				else if (j%2==0) ans +=19;
				else ans+=20;
			}
			if(y%3==0)ans+=20-d+1;
			else if (m%2==0)ans+=19-d+1;
			else ans+=20-d+1;
			cout << ans << endl;	
		}
	
	
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long int a[200000];
  long long int ans=1000000000000000;
  int n,b;
  int p;
  cin>>n;
  cin>>b;
  a[0]=b;
  for(int i=1;i<n;i++){
    cin>>b;
    a[i]=a[i-1]+b;
  }
  for(int i=0;i<n-1;i++){
    long long int d=a[n-1]-a[i];
    ans=min(ans,abs(a[i]-d));
  }
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

int main() {
  ll N; cin >> N;
  ll dp[100][64];
  for (ll i = 3; i < 100; i++) {
    for (ll j = 0; j < 64; j++) {
      dp[i][j] = 0;
    }
  }
  for (ll i = 0; i < 64; i++) {
      dp[2][i] = 1;
  }
  
  vector<ll> v[64];
  for (ll i = 0; i < 64; i++) {
    ll n = i;
    v[i].push_back(n / 16);
    n = n%16;
    v[i].push_back(n / 4);
    n = n%4;
    v[i].push_back(n);
  }
  for (ll i = 0; i < 64; i++) {
    if (v[i][0] == 0 && v[i][1] == 1 && v[i][2] == 2) {dp[2][i] = 0;}
    if (v[i][0] == 1 && v[i][1] == 0 && v[i][2] == 2) {dp[2][i] = 0;}
    if (v[i][0] == 0 && v[i][1] == 2 && v[i][2] == 1) {dp[2][i] = 0;}
  }
  
  for (ll i = 3; i < 100; i++) {
    for (ll j = 0; j < 64; j++) {
      for (ll k = 0; k < 4; k++) {
        vector<ll> w = v[j];
        w.push_back(k);
        bool ok = true;
        if (w[0] == 0 && w[1] == 1 && w[2] == 2) {ok = false;}
        if (w[0] == 1 && w[1] == 0 && w[2] == 2) {ok = false;}
        if (w[0] == 0 && w[1] == 2 && w[2] == 1) {ok = false;}
        if (w[1] == 0 && w[2] == 1 && w[3] == 2) {ok = false;}
        if (w[1] == 1 && w[2] == 0 && w[3] == 2) {ok = false;}
        if (w[1] == 0 && w[2] == 2 && w[3] == 1) {ok = false;}
        if (w[0] == 0 && w[2] == 1 && w[3] == 2) {ok = false;}
        if (w[0] == 0 && w[1] == 1 && w[3] == 2) {ok = false;}
        ll l = (j%16)*4 + k;
        if (ok) {
          dp[i][l] = (dp[i][l] + dp[i-1][j]) % mod;
        }
      }
    }
  }
  ll res = 0;
  for (ll i = 0; i < 64; i++) {
    res = (res+dp[N-1][i])%mod;
  }
  cout << res << endl;
}

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

using namespace std;

#define REPI(x) for(int i=0;i<x;i++)
#define REPJ(x) for(int j=0;j<x;j++)
#define SCANFD(x) scanf("%d",&x)

int main(){    
    int N;
    int a[200000];
    long long x,y;
    long long res;

    scanf("%d",&N);

    for(int i=0;i<N;i++)
        scanf("%d",&a[i]);
    
    x=a[0];
    y=0;
    for(int i=1;i<N;i++)
        y+=a[i];
    
    res = abs(x-y);

    for(int i=1;i<N-1;i++){
        x+=a[i];
        y-=a[i];
        res = min(res,abs(x-y));
    }

    printf("%lld\n",res);
    
    return 0;
}


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

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

    int l, r, ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        ans += r - l + 1;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    ll cnt=0;
    rep(i,s.size()){
        if(s[i]=='x'){
            cnt++;
        }
    }
    if(cnt>=8){
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
}

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

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;}


int main(){

  ll n;
  cin >> n;

  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  sort(a.begin(), a.end(), greater<ll>());
  priority_queue<ll, vector<ll>, less<ll> > q;
  // rep(i,n) cout << a[i] << endl;

  ll ans = 0;
  ans += a[0];
  q.push(a[1]);
  q.push(a[1]);

  if(n==2){
    cout << ans << endl;
    return 0;
  }

  for(ll i = 2; i < n; i++){
    ans += q.top();
    q.pop();
    q.push(a[i]);
    q.push(a[i]);
    // cout << ans << endl;
  
  }
  cout << ans <<endl;


  return 0;
} 



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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  
  if (N * A > B) {
    cout << B << endl;
  }
  
  if (B > N * A) {
    cout << N * A << endl;
  }
  
  if (N * A == B) {
    cout << B << endl;
  }
}


Measured memory_bytes: 256
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);
const long double PI=3.14159265358979;

// Required random number generators

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
    #ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen ("INPUT.txt" , "r" , stdin);
        //freopen ("OUTPUT.txt" , "w" , stdout);
    }
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t clk;
    clk = clock();
//-----------------------------------------------------------------------------------------------------------//

    string S,T;
    cin>>S>>T;
    ll ans=inf;
    ll N=S.length();
    ll M=T.length();
    FORI(i,0,N)
    {
        if(i+M<=N)
        {
            ll ans1=0;
            FORI(j,0,M)
            {
                if(S[i+j]!=T[j])
                {
                    ans1++;
                }
            }
            ans=min(ans,ans1);
        }
    }
    cout<<ans<<endl;

//-----------------------------------------------------------------------------------------------------------//


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

    return 0;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  if (a+b > c+d) {
    cout << "Left" << endl;
  }
  
  else if (a+b < c+d) {
    cout << "Right" << endl;
  }
  
  else {
    cout << "Balanced" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;cin >> N;
    vector<int> am(N),bm(N);
    rep(i,N)cin >> am[i];
    rep(i,N)cin >> bm[i];
    ll res = 0;
    for(int k=29;k>=0;k--){
        //vector<int> am(N),bm(N);
        ll T =(1<<k);
        rep(i,N){
            am[i]=am[i]%(2*T);
            bm[i]=bm[i]%(2*T);
        }
        sort(All(bm));

        ll is_one = 0;
        rep(i,N){
            int add = 0;
            if(am[i]<=T){
                add += lower_bound(All(bm),(2*T)-am[i])-lower_bound(All(bm),T-am[i]);
            }else{
                //add += lower_bound(All(bm),(1<<(k+1)))-bm.begin();
                //add -= lower_bound(All(bm),(3*(1<<k))-a[i])-lower_bound(All(bm),(1<<(k+1))-a[i]);
                add+=lower_bound(All(bm),(2*T)-am[i])-bm.begin();
                add+=lower_bound(All(bm),(2*T))-lower_bound(All(bm),(3*T)-am[i]);
            }
            is_one+=add;
        }
        if(is_one&1)res+=T;
    }
    cout << res << endl;
    return 0;
}

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

long long n, m, mod = 1000000007;

long long mulmod(long long a, long long b, long long m) {
    long long res = 0;
    while(b > 0) {
       if(b % 2 == 1) res = (res+a)%m;
       a = (a*2)%m;
       b /= 2;
    }
    return res % m;
}

long long fac(long long x){
	if(x == 1) return 1;
	return mulmod(fac(x-1), x, mod);
}

int main(){
	cin >> n >> m;
	if(abs(n-m) > 1){
		cout << 0;
		return 0;
	}
	if(n == m) cout << mulmod(mulmod(fac(n), fac(m), mod), 2, mod);
	else cout << mulmod(fac(n), fac(m), mod);
}

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

ll gcd(ll a, ll b) {
	if(a==0||b==0) return 0;
	if(a<b) swap(a,b);
	ll tmp = a%b;
	while(tmp!=0) {
		a = b;
		b = tmp;
		tmp = a%b;
	}
	return b;
}

ll fac(ll x) {
	ll f=1;
	for(ll i=2; i<x; i++) {
		f*=i;
	}
	return f;
}

ll npr(ll n, ll r) {
	ll result=1;
	for(ll i=r+1; i<=n; i++) result*=i;
	return result;
}

bool IsPrime(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}



int main() {
	string str; cin >> str;
	int size=str.size()-1;
	if(str.size()%2==0) size--;

	while(str.substr(0,size/2)!=str.substr(size/2,size/2)) size-=2;

	cout << size <<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int W,H,x,y,r;
    cin >> W >> H >> x >> y >> r;
    if(x>=r && x <= W-r && y>=r && y <= H-r)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
void ABC100(void);
void ABC101(void);
void ABC102(void);
void ABC103(void);
void ABC104(void);
void ABC105(void);
void ABC106(void);
void ABC107(void);
void ABC108(void);
void ABC109(void);

int main(void){
    ABC108();
}

void ABC108(){
    int x1,x2,y1,y2,dx,dy;
    cin>>x1>>y1>>x2>>y2;
    dx=x2-x1;
    dy=y2-y1;
    cout<<x2-dy<<" "<<y2+dx<<" "<<x2-dy-dx<<" "<<y2+dx-dy<<endl;
}


Measured memory_bytes: 256
import sys
from collections import Counter

n = int(input())
arr = list(map(int, input().split()))

if len(arr) % 2 == 0:
    if 0 in arr:
        print(0)
        sys.exit()
else:
    if arr.count(0) != 1:
        print(0)
        sys.exit()
    else:
        arr.remove(0)

cnt = Counter(arr)

values = list(cnt.values())

if values.count(2) != len(values):
    print(0)
    sys.exit()

mod = 10**9 + 7

print(2**(n // 2) % mod)

Measured memory_bytes: 14820
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main()
{
    string S;
    cin >> S;
    if (S[1] == 'B')
    {
        cout << "ARC" << endl;
        return 0;
    }
    else
    {
        cout << "ABC" << endl;
        return 0;
    }
    
    return 0;
}


Measured memory_bytes: 3628
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

int dist(int a, int b)
{
    if (a <= b)
    {
        return b - a;
    }
    else
    {
        return a - b + 2;
    }
}

int rev(int x)
{
    return -x;
}

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    cout << min(min(dist(a, b), dist(rev(a), b) + 1), dist(a, rev(b)) + 1) << '\n';
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.readline

def count(A, B, x):
    N = len(A)
    M = len(B)
    res = 0
    r = -1
    for l in range(N):
        a = A[l]
        while r < M-1 and B[r+1]*a <= x:
            r += 1
        res += r+1
    return res

def count2(A, x):
    res = 0
    for a in A:
        if a*a <= x:
            res += 1
    return res
        

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
Am = []
Ap = []

minus = 0
zero = 0
plus = 0
for a in A:
    if a < 0:
        minus += 1
        Am.append(-a)
    elif a == 0:
        zero += 1
    else:
        plus += 1
        Ap.append(a)

ms = minus*plus
zs = ms + zero*(minus+plus) + zero*(zero-1)//2

Am.sort()
Ap.sort()
Amr = Am[::-1]
Apr = Ap[::-1]

if K <= ms:
    K = ms+1-K
    ok = max(max(Am+[0]), max(Ap+[0]))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if count(Amr, Ap, med) >= K:
            ok = med
        else:
            ng = med
    ans = -ok
elif K <= zs:
    ans = 0
else:
    K -= zs
    ok = max(max(Am+[0]), max(Ap+[0]))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if (count(Amr, Am, med) + count(Apr, Ap, med) - count2(Am, med) - count2(Ap, med))//2 >= K:
            ok = med
        else:
            ng = med
    ans = ok

print(ans)
    
    



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

#define ll long long

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

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

  return;
}


//naosu
long int gcd(long int a,long int b){
  long int c;

  while (b > 0){
    c = a % b;
    a = b;
    b = c;
  }

  return a;
}

int upll(const void*a, const void*b){
  return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;
}

int downll(const void*a, const void*b){
  return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;
}

void sortup(ll*a,int n){
  qsort(a,n,sizeof(ll),upll);
}

void sortdown(ll*a,int n){
  qsort(a,n,sizeof(ll),downll);
}

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

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

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

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

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

  return;
}

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

  return;
}


long int lcm(long int a,long int b){
  return a/gcd(a,b)*b;
}


long int f(long int n,long int c,long int d){
  long int cnt=n/c+n/d-n/lcm(c,d);
  return n-cnt;
}


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

int main(void){
  long int n;
  scanf("%ld",&n);

  long int A[n];
  int B[n];
  for(int i=0;i<n;i++){
    A[i]=0;
  }

  for(int i=0;i<n;i++){
    scanf("%d",&B[i]);
    A[B[i]-1]++;
  }

  long int ans=0;
  for(int i=0;i<n;i++){
    ans+=A[i]*(A[i]-1)/2;
  }

  for(int i=0;i<n;i++){
    long int now=B[i];
    
    now--;
    ans-=A[now]*(A[now]-1)/2;
    ans+=(A[now]-1)*(A[now]-2)/2;
    printf("%ld\n",ans);

    ans-=(A[now]-1)*(A[now]-2)/2;
    ans+=A[now]*(A[now]-1)/2;
  }
  return 0;
}

Measured memory_bytes: 5032
use std::cmp;
use std::collections::BTreeMap;
use std::mem;

// median-of-medians.rs --- Median of Medians
// author: Seong Yong-ju <sei40kr@gmail.com>

// tanakah's input macro
// cf https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn count_invs(slice: &[i32]) -> (Vec<i32>, u64) {
    let len = slice.len();
    if len <= 1 {
        return (slice.to_vec(), 0);
    }

    let mid = len / 2;
    let (xs, xs_invs) = count_invs(&slice[..mid]);
    let (ys, ys_invs) = count_invs(&slice[mid..]);

    let mut result = Vec::with_capacity(len);
    let mut invs = xs_invs + ys_invs;

    let (mut i, mut j) = (0, 0);
    let (xs_len, ys_len) = (xs.len(), ys.len());
    while i < xs_len && j < ys_len {
        let (x, y) = (xs[i], ys[j]);
        if x <= y {
            result.push(x);
            i += 1;
        } else {
            result.push(y);
            j += 1;
            invs += (xs_len - i) as u64;
        }
    }

    result.extend_from_slice(&xs[i..]);
    result.extend_from_slice(&ys[j..]);

    (result, invs)
}

fn main() {
    input! {
      n: usize,
      xs: [i32; n]
    }

    let ms_len = n as u64 * (n as u64 + 1) / 2;

    let mut l = 0;
    let mut r = 1_000_000_001;
    while r - l > 1 {
        let mid = (l + r) / 2;

        let ts = xs
            .iter()
            .map(|&x| if mid <= x { 1 } else { -1 })
            .collect::<Vec<i32>>();

        let mut ss = vec![0; n + 1];
        for i in 0..n {
            ss[i + 1] += ss[i] + ts[i];
        }

        let invs = count_invs(&ss).1;
        if invs <= ms_len / 2 {
            l = mid;
        } else {
            r = mid;
        }
    }

    println!("{}", l);
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
typedef int64_t i64;

int main()
{
    int N;
    cin >> N;

    vector<int> a(N + 1);

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

    vector<int> p(N + 1);
    for (int i = 2; i < N + 1; i++)
    {
        int K = a[i];
        p[K]++;
    }

    for (int i = 1; i < N+1; i++)
    {
        cout << p[i] << endl;
    }
    
}


Measured memory_bytes: 4844
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			String s1 = scn.next();
			String s2 = scn.next();

			if(s1.equals(s2)) {
				System.out.println(0);
				return;
			}
			int cnt = 0;
			for(int i=0; i<s1.length(); i++) {
				if(s1.charAt(i) != s2.charAt(i)) {
					cnt++;
				}
			}
			System.out.println(cnt);
		}
	}
}


Measured memory_bytes: 41316
h,w,K = map(int,input().split())
c = [input() for _ in range(h)]
count = 0

for i in range(2 ** (h+w)):
    ans = 0
    a,b = [],[]
    for j in range(h+w):
        if ((i >> j) & 1):
            if j < h:
                a.append(j)
            else:
                b.append(j-h)
    for k in range(h):
        for l in range(w):
            if c[k][l] == '#' and k in a and l in b:
                ans += 1
    if ans == K:
        count += 1
print(count)

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

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

const int MAX { 100010 };

bitset<MAX> sieve;
vector<int> ps;

void precomp()
{
    sieve.set();

    ps.push_back(2);
    ps.push_back(3);

    for (ll i = 5, step = 2; i < MAX; i += step, step = 6 - step)
    {
        if (sieve[i])
        {
            ps.push_back(i);

            for (ll j = i * i; j < MAX; j += 2*i)
                sieve[j] = false;
        }
    }
}

ll solve(int X)
{
    return *lower_bound(ps.begin(), ps.end(), X);
}

int main()
{
    ios::sync_with_stdio(false);
    precomp();

    int X;
    cin >> X;

    auto ans = solve(X);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 384
import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()

Measured memory_bytes: 272344
def dfs(i, s, plus):
    if i == n - 1:
        return sum(list(map(int, s.split("+"))))
    return dfs(i + 1, s, plus) +\
           dfs(i + 1, s[:i + plus + 1] + "+" + s[i + plus + 1:], plus + 1)

s = input()
n = len(s)

print(dfs(0, s, 0))


Measured memory_bytes: 3060
#include<cstdio>
int r,c,n,x,y,t,a[10001],b[101][101];
int main()
{
	scanf("%d%d%d",&r,&c,&n);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	x=y=t=1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=a[i];j++)
		{
			b[x][y]=i;
			y+=t;
			if ((y>c)||(y<1))
			{
				t=0-t;
				x++;
				if (t==-1)y=c;
				else y=1;
			}
		}
	for (int i=1;i<=r;i++)
	{
		for (int j=1;j<=c;j++)printf("%d ",b[i][j]);
		printf("\n");
	}
}

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

int main()
{
    int n, *a, *skip;
    long long cost_sum{};
    scanf("%d", &n);
    a = new int[n + 2];
    skip = new int[n + 2];
    a[0] = a[n + 1] = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);

    for (int i = 1; i <= n + 1; i++)
        cost_sum += std::abs(a[i] - a[i - 1]);
    for (int i = 1; i <= n; i++)
        skip[i] = std::abs(a[i - 1] - a[i]) + std::abs(a[i] - a[i + 1]) - std::abs(a[i - 1] - a[i + 1]);

    for (int i = 1; i <= n; i++)
        printf("%lld\n", cost_sum - skip[i]);

    delete[] a;
    delete[] skip;

    return 0;
}

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


long long int dfs(long long int sum, long long int r,string s, int dp){
  if(dp>=s.size()){
    return sum + r;
  }
  else{
    long long int a = dfs(sum + r, s[dp]-'0', s, dp+1);//'+'in
    long long int b = dfs(sum, r*10+s[dp]-'0', s, dp+1);//not'+'in
    return a+b;
  }
}

int main(){
  string s;
  cin >> s;
  cout << dfs(0,s[0]-'0',s,1) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
namespace LCY{
    #define double long double
    const double EPS=1e-10;
    inline int dcmp(double x){if(fabs(x)<EPS)return 0;return (x<0)?-1:1;}
    struct Point{double x,y;Point(double _x=0,double _y=0){x=_x;y=_y;}};
    struct Vector{double x,y;Vector(double _x=0,double _y=0){x=_x;y=_y;}};
     
    Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
    Vector operator * (Vector a,double d){return Vector(a.x*d,a.y*d);}
    Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}
     
    inline double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
    inline double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
    inline double norm(Vector a){return dot(a,a);}
     
    struct Line{
        Point p1,p2;
        Line(Point _p1=Point(0,0),Point _p2=Point(0,0)){p1=_p1;p2=_p2;}
    };
     
    Point project(Line l,Point p){
        Vector base=l.p2-l.p1;
        double r=dot(p-l.p1,base)/norm(base);
        return l.p1+base*r;
    }
    Point reflect(Line l,Point p){
        Point q=project(l,p);
        Vector v=p-q;v.x=-v.x;v.y=-v.y;
        return q+v;
    }
}
using namespace LCY;
int main(){
    Point p1,p2;cin>>p1.x>>p1.y>>p2.x>>p2.y;
    int n;cin>>n;while(n--){
        Point q;cin>>q.x>>q.y;Point res=reflect(Line(p1,p2),q);
        cout<<setiosflags(ios::fixed)<<setprecision(10)<<res.x<<" "<<res.y<<endl;
    }
    return 0;
}



Measured memory_bytes: 3300
#include <bits/stdc++.h>
using namespace std;
int a[305][305], p[305];
bool ok[305];
int main(){
	int n, m, i, j, mmin = 0x7f7f7f7f, mmax, k;
	scanf("%d %d", &n, &m);
	for(i = 1 ; i <= n ; ++i)
		for(j = 1 ; j <= m ; ++j)
			scanf("%d", &a[i][j]);
	j = m;
	for(i = 1 ; i <= n ; ++i)
		a[i][0] = 1;
	while(j--){
		mmax = 0;
		for(i = 1 ; i <= n ; ++i){
			while(ok[a[i][a[i][0]]]) ++a[i][0];
			++p[a[i][a[i][0]]];
		}
		for(i = 1 ; i <= m ; ++i)
			if(mmax < p[i]){
				mmax = p[i];
				k = i;
			}
		mmin = min(mmin, p[k]);
		memset(p, 0, sizeof(p));
		ok[k] = 1;
	}
	printf("%d\n", mmin);
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#define Inf 1000000000000000ll
#define ll long long
using namespace std;



int main() {
    ll X,Y;
    cin>>X>>Y;
    
    int ct=0;
    while(1) {
        if (2*X > Y)
            break;
        ct++;
        X*=2;
    }
    
    cout << ct+1 << endl;
    
}

Measured memory_bytes: 256