akhauriyash/Code-Regression huggingface dataset:
//#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cctype>
#include <cstdlib>      // srand,rand


using namespace std;
#define modd 1000000007



typedef pair<long long, long long> pl;


typedef string::const_iterator State;
class ParseError {};




#define ll long long




class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};


class SegmentTree {
private:
	int n;
	vector <ll> node;

public:
	// 元の配列　v をセグメントツリーで表現する。
	SegmentTree(vector<ll> v) {
		//最下段のノード数は元配列のサイズ以上になる最小の2冪->これをnとおく。
		//セグ木全体で必要なノード数は2n-1個である。
		int sz = v.size();
		n = 1; 
		while (n < sz)n *= 2;

	}

};




long long N, M, K, a, b, c, d, e, H, W, L,T;
ll A[300005] = {};
ll B[300005] = {};
ll C[100][3005] = {};
bool f, ff;
string S,SS;
set <long long>sll;
pl bufpl;
vector <long long>vl[100005];
vector <long long>vll;
vector <pl>vpl;
vector <string> vs;
set<ll> llset[50];
multiset<ll> llmset;
queue<ll> ql;


struct ST
{
	ll first;
	ll second;
	ll kaisuu;
	

	bool operator<(const ST& another) const
	{
		return first < another.first;//比較
	};

};



/*vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}


ll minn, maxx;
double ansa;

ll zettai(ll aa) {

	if (aa < 0) {
		aa *= -1;
	}
	return aa;

}


bool itta[300000];

int main() {
	
	cin >> a>>b;

	d = a + b;
	if (d % 2 == 1) {
		d++;
	}
	d /= 2;


	cout << d << endl;

	//cout << fixed << setprecision(10) << ansa << endl;
	return 0;



}


Measured memory_bytes: 4096
n = int(input())
hhh = map(int, input().split())

max_num = 0
num = 0
h_before = 0
for h in hhh:
  if h_before >= h:
    num += 1
  else:
    if max_num < num:
      max_num = num
    num = 0
  h_before = h
if max_num < num:
  max_num = num
    
print(max_num)

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

int main(){
    int N,count = 0,max = 0;
    cin >> N;
    int H[N];
    for(int i = 0; i < N; i++){
        cin >> H[i];
    }
    
    for(int j = 1; j < N; j++){
        if(H[j] <= H[j-1]){
            count++;
        }else{
            if(count > max){
                max = count;
            }
            count = 0;
        }
        if(j == N - 1){
            if(count > max){
                max = count;
            }
            count = 0;
        }
   //     cout << "j = " << j << endl <<"c = " << count << endl << "m = " << max << endl << endl;
    }
    
    cout << max << endl;
    
    return 0;
}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif

    string S;
    cin >> S;
    bool ok = true;

    if (S[2] != S[3]) {
        ok = false;
    }

    if (S[4] != S[5]) {
        ok = false;
    }

    cout << (ok ? "Yes\n" : "No\n");

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(ll i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(ll i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n;
    cin>>n;
    string st;
    cin>>st;
    vi a(n),b(n);
    REP(i,n){
        if(st[i]=='W'){
            a[i]++;
        }else{
            b[i]++;
        }
    }
    REP(i,n-1){
        a[i+1]+=a[i];
    }
    REPR(i,n-2){
        b[i]+=b[i+1];
    }
    int ans=INF;
    REP(i,n){
        int p=0;
        if(i-1>=0){
            p+=a[i-1];
        }
        if(i+1<n){
            p+=b[i+1];
        }
        chmin(ans,p);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3076
N = int(input())
A = list(map(int, input().split()))
sign = 0
for a in A:
    if a <= 0:
        sign += 1
absA = [abs(a) for a in A]
if sign % 2 == 0:
    print(sum(absA))
else:
    print(sum(absA) - min(absA) * 2)


Measured memory_bytes: 14412
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

typedef long double ld;

const int EMPTY   = 0;
const int BATTERY = 1;
const int STORE   = 2;
const int WALL    = 3;

struct Point {
public:
  int x, y;
  Point() { }
  Point(int x, int y): x(x), y(y) { }
};

struct State {
public:
  Point p;
  int battery;
  State() { };
  State(Point p, int battery): p(p), battery(battery) { }
};

Point int2point(int n) {
  return Point(1 + n % 3, 1 + n / 3);
}

int field[5][5];

ld dp[16][5][5];
int main() {
  int n, s, t, b;
  while (true) {
    cin >> n;
    if (n == 0) break;
    char cs, ct, cb;
    cin >> cs >> ct >> cb;
    s = cs - 'A';
    t = ct - 'A';
    b = cb - 'A';
    
    memset(field, EMPTY, sizeof(field));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < 5; i++) {
      field[0][i] = WALL;
      field[4][i] = WALL;
      field[i][0] = WALL;
      field[i][4] = WALL;
    }
    Point batteryPoint = int2point(t);
    field[batteryPoint.x][batteryPoint.y] = BATTERY;
    Point storePoint = int2point(b);
    field[storePoint.x][storePoint.y] = STORE;
    State nowState(int2point(s), n);

    dp[0][nowState.p.x][nowState.p.y] = 1.0f;
    int dx[] ={1,0,-1,0},dy[] ={0,1,0,-1};
    for(int i = 0; i < nowState.battery; i++){
      for(int j = 1; j <= 3; j++){
        for(int k = 1; k <= 3; k++){
          for(int l = 0;l < 4; l++){
            int nx = j + dx[l], ny = k + dy[l];
            if(field[nx][ny] == STORE || field[nx][ny] == WALL) {
              nx = j, ny = k;
            }
            dp[i+1][nx][ny] += dp[i][j][k] / 4.0;
          }
        }
      }
    }
    printf("%.15llf\n", dp[nowState.battery][batteryPoint.x][batteryPoint.y]);
  }
  return 0;
}

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

int gcd(int x, int y)
{
	if (x == 0 | y == 0) return 0;
	
	while (x != y) {
		if (x > y) x -= y;
		else y -= x;
	}
	
	return x;
}

int lcm(int x, int y)
{
	if (x == 0 | y == 0) return 0;
	
	return x / gcd(x, y) * y;
}

int main()
{	
	int x, y;
	
	while(cin >> x >> y) 
		cout << gcd(x, y) << " " << lcm(x, y) << endl;
	
	return 0;
}

Measured memory_bytes: 1160
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <assert.h>
#include <sstream>
#include <string>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater <>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
using namespace std;
using ll = long long;
typedef std::pair<int,int> P;
#include <boost/multiprecision/cpp_int.hpp>
 
using bint = boost::multiprecision::cpp_int;



int main(){
    int n; cin >> n;
    cout << (n%2==0? n: (ll) n*2);
}

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

using namespace std;
 
bool c(int x)
{
    int e = x % 10; x /= 10;
    while (x > 0) {
        if (x % 10 + 1 != e) {
            return 0;
        }
        e = x % 10;
        x /= 10;
    }
    return 1;
}

int main()
{
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    int res = -1;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int b = a[i] * a[j];
            if (c(b) && res < b) res = b;
        }
    }
    cout << res << endl;
    return 0;
}

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

#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define PI 3.14159265358979323846264338327950L
typedef long long ll;
using namespace std;
const int MAX = 0x7ffffff;
int t;

void slove()
{
	int n;cin >> n;
	cout << (ll)n * (n - 1) / 2 << endl;
}
int main()
{
	SIS;
	slove();
}

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

int main(){
    string s;
    cin >> s;
    vector<char> ans;
    for(int i = 0; i < (int)s.size(); i++)
    {
        if(s[i]=='B'&&(int)ans.size()>0) ans.pop_back();
        else if(s[i]=='0'||s[i]=='1')
        {
            ans.push_back(s[i]);
        }
    }
    for(int i = 0; i < (int)ans.size(); i++)
    {
        cout << ans[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
N = int(input())
L = []

for i in range(N):
  l = list(map(int,input().split()))
  L.append(l)
  
dp = [[0,0,0] for i in range(N)]
dp[0] = [L[0][0],L[0][1],L[0][2]]

for i in range(1,N):
  for j in range(3):
    dp[i][j] = max(dp[i - 1][(j + 1) % 3],dp[i - 1][(j + 2) % 3]) + L[i][j]
    
print(max(dp[N - 1]))

Measured memory_bytes: 47384
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
typedef pair<int , int> P;
typedef vector<P> vP;
typedef vector<vector<ll>> vvi;
typedef vector<vector<P>> vvP;
#define INF 10000000000

ll n;
vi Max; vi Min;
vvi e;
void f(int); void g(int);
vi S;
vi ans;
 int main() {
	cin >> n;
	e.resize(n);
	for (ll i = 0; i < n - 1; i++) {
		ll a, b; 
		cin >> a >> b; a--; b--;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	
	ll k;
	cin >> k;
	ll a, b;
	Max.resize(n, INF); Min.resize(n, -INF);
	for (ll i = 0; i < k; i++) {
		cin >> a >> b; a--;
		Max[a] = b;
		Min[a] = b;
	}
	S.resize(0); S.resize(n, 0); S[a] = 1;
	f(a);
	S.resize(0); S.resize(n, 0); S[a] = 1;
	queue<int> que; que.push(a);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		S[v] = 1;
		for (int i = 0; i < e[v].size(); i++) {
			int nv = e[v][i];
			if (S[nv] == 1)continue;
			Max[nv] = min(Max[nv], Max[v] + 1);
			Min[nv] = max(Min[nv], Min[v] - 1);
			que.push(nv);
		}
	}
	ans.resize(n, 0);
	S.resize(n, 0); S[a] = 1; ans[a] = Min[a];
	for (int i = 0; i < n; i++) {
		if (Max[i] < Min[i]) {
			cout << "No" << endl; return 0;
		}
	}
	for (int i = 0; i < n ; i++) {
		for (int j = 0; j < e[i].size(); j++) {
			int x = e[i][j];
			if ((Min[i] - Min[x]) % 2 == 0) {
				cout << "No" << endl; return 0;
			}
		}
	}
	cout << "Yes" << endl;
	for (ll i = 0; i < n; i++) {
		cout << Min[i] << endl;
	}
	return 0;
}
 void f(int v) {
	 S[v] = 1;
	 for (ll i = 0; i < e[v].size(); i++) {
		 ll nv = e[v][i];
		 if (S[nv] == 1)continue;
		 f(nv);
		 Max[v] = min(Max[v], Max[nv] + 1);
		 Min[v] = max(Min[v], Min[nv] - 1);
	 }
 }
 


Measured memory_bytes: 14208
N=int(input())
A=[int(input()) for _ in range(N)]
B=sorted(A,reverse=True)
if B[0]==B[1]:
    for _ in range(N):
        print(B[0])
else:
    for a in A:
        if a!=B[0]:
            print(B[0])
        else:
            print(B[1])

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

int main() {
    int N;
    cin >> N;
    string s;
    cin >> s;
    vector<int> w(N + 1, 0), b(N + 1, 0);
    for (int i = 0; i < N; i++) {
        if (s[i] == '.') {
            w[i + 1]++;
        } else {
            b[i + 1]++;
        }
        w[i + 1] += w[i];
        b[i + 1] += b[i];
    }
    int minv = 1e9;
    for (int i = 0; i <= N; i++) {
        int sum = (b[i] - b[0]) + (w[N] - w[i]);
        minv = min(sum, minv);
    }
    cout << minv << endl;
}

Measured memory_bytes: 2180
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        c: [Chars; h],
    }
    let mut ans = 0;
    for hi in 0..1 << h {
        for wj in 0..1 << w {
            let mut cnt = 0;
            for (i, ci) in c.iter().enumerate() {
                if hi >> i & 1 == 1 {
                    continue;
                }
                for (j, cij) in ci.iter().enumerate() {
                    if wj >> j & 1 == 1 {
                        continue;
                    }
                    if *cij == '#' {
                        cnt += 1;
                    }
                }
            }
            if cnt == k {
                ans += 1;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2172
//============================================================================
// Name        : AOL.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int H[14]={};
	int S[14]={};
	int C[14]={};
	int D[14]={};
	int n;
	int a;
	char chr;
    cin>>n;

	for(int i=0;  i<n; i++){
		cin>>chr>>a;
		if(chr=='H')H[a]=1;
	    if(chr=='S')S[a]=1;
	    if(chr=='C')C[a]=1;
	    if(chr=='D')D[a]=1;
	}
	for(int i=1;i<14; i++){
		if(S[i]==0) cout<<"S "<<i<<endl;
	}
	for(int i=1;i<14; i++){
		if(H[i]==0) cout<<"H "<<i<<endl;
	}
	for(int i=1;i<14; i++){
		if(C[i]==0) cout<<"C "<<i<<endl;
	}
	for(int i=1;i<14; i++){
		if(D[i]==0) cout<<"D "<<i<<endl;
	}
}

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

vector<bool> dp(mx,false);

int main(){  
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i,n){ cin >> a[i]; }
  rep(i,k+1){ rep(j,n){
    if(a[j]<=i){ dp[i] = dp[i] || !dp[i-a[j]]; }
  } }

  cout << (dp[k]?"First":"Second") << endl;
  return 0;
}

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

#define REP(i,x)for(__typeof(x) i=0;i<x;i++)

int main(void){
  int R,C;
  while(cin>>R>>C,R){
    vector<vector<int>> a(R,vector<int>(C,0));
    REP(i,R)REP(j,C){
      cin>>a[i][j];
    }
    int ans=0;
    REP(i,1<<R){
      int a_cnt=0;
      REP(j,C){
        int c_cnt=0;
        REP(k,R)
          c_cnt += (i>>k&1)^a[k][j];
        a_cnt += max(c_cnt, R - c_cnt);
      }
      ans = max(ans, a_cnt);
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 1592
# coding: utf-8

import math

def RadToDeg(rad):
	return rad*180/math.pi

def DegToRad(deg):
	return deg*math.pi/180

deg = 90
x = 0.
y = 0.

while True:
	d, theta = map(int, raw_input().split(","))
	if d == 0 and theta == 0:
		break
	else:
		x += d * math.cos(DegToRad(deg))
		y += d * math.sin(DegToRad(deg))
		deg -= theta
print(int(x))
print(int(y))



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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector <long long> a(n);
    int mi=0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(abs(a[i])>abs(a[mi])){
            mi=i;
        }
    }
    vector <pair <int,int>> ans;
    if(a[mi]>=0){
        for(int i=1;i<n;i++){
            if(a[i]>=a[i-1]){
                continue;
            }
            else{
                if(a[i-1]>=0 && a[i]>=0){
                    ans.emplace_back(i-1,i);
                    a[i]+=a[i-1];
                }
                else if(a[i-1]<0 && a[i] <0){
                    ans.emplace_back(mi,i);
                    a[i]+=a[mi];
                }
                else if(a[i-1]>=0 && a[i]<0){
                    ans.emplace_back(mi,i);
                    ans.emplace_back(i-1,i);
                    a[i]+=a[mi];
                    a[i]+=a[i-1];
                }
            }
        }
    }
    else{
        for(int i=n-2;i>=0;i--){
            if(a[i]<=a[i+1]){
                continue;
            }
            else{
                if(a[i]>=0 && a[i+1]>=0){
                    ans.emplace_back(mi,i);
                    a[i]+=a[mi];
                }
                else if(a[i]<0 && a[i+1]<0){
                    ans.emplace_back(i+1,i);
                    a[i]+=a[i+1];
                }
                else if(a[i]>=0 && a[i+1]<0){
                    ans.emplace_back(mi,i);
                    ans.emplace_back(i+1,i);
                    a[i]+=a[mi];
                    a[i]+=a[i+1];
                }
            }

        }

    }
    for(int i=2;i<n;i++){
        assert(a[i]>=a[i-1]);
    }
    cout << ans.size() << endl;
    for(int i=0;i<ans.size();i++){
        cout << ans[i].first+1 << " " << ans[i].second+1 << endl;
    }
    return 0;
}

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

int main() {
    int n,s,t,counter=0;
    vector<int> v;
    for(int i=0;i<3;i++){
        cin >> n;
        v.push_back(n);
    }
    sort(v.begin(),v.end());
    s = v[2] - v[0];
    t = v[2] - v[1];
    counter += s/2;
    s -= (s/2)*2;
    counter += t/2;
    t -= (t/2)*2;
    if(s + t == 2)counter += 1;
    else if(s + t == 1)counter += 2;
    cout << counter << endl;
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	n        int
	e        [][]int
	col      []int
	to       [][]int
	maxColor int
)

func dfs(v, p, c int) {
	if maxColor < c {
		maxColor = c
	}

	var tmpC int
	for _, i := range to[v] {
		u := e[i][0]
		if u == v {
			u = e[i][1]
		}
		if u == p {
			continue
		}
		tmpC++
		if tmpC == c {
			tmpC++
		}
		col[i] = tmpC
		dfs(u, v, tmpC)
	}
}

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	fmt.Fscan(r, &n)
	e = make([][]int, n-1)
	to = make([][]int, n)
	col = make([]int, n-1)
	for i := 0; i < n-1; i++ {
		var a, b int
		fmt.Fscan(r, &a, &b)
		a--
		b--
		e[i] = []int{a, b}
		to[a] = append(to[a], i)
		to[b] = append(to[b], i)
	}

	dfs(0, 0, 0)
	fmt.Fprintln(w, maxColor)
	for i := 0; i < n-1; i++ {
		fmt.Fprintln(w, col[i])
	}
}


Measured memory_bytes: 23680
if __name__ == '__main__':
    N = int(input())

    rev_answer = ""
    while N != 0:
        rem = N % (-2)
        if rem < 0:
            rem += 2
        N = (N - rem) // (-2)
        rev_answer += str(rem)

    answer = rev_answer[::-1]
    if answer == "":
        answer = 0

    print(answer)

Measured memory_bytes: 3064
until [0,0] == (num,max = gets.split.map &:to_i)
  next if num.nil?
  ary = gets.split.map &:to_i
  ary.sort!{|a, b| b <=> a }
  c,sum = 0,0
  ary.each do |x|
    c+=1
    sum+=x if ((c%max)!=0) 
  end
  p sum
end

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

typedef long long lint;

#define rb(x) ((x)&(-(x)))

const int MAXN = 100010;
const lint MAXL = 1ll << 60;

int N;
lint L;
string S[MAXN];
lint ans;

void f(int s, int e, int i, string &str) {
	if(s > e) ans ^= rb(L - i + 1);
	else if(s < e || i < S[s].size()) {
		str.push_back('1');
		int l = lower_bound(S, S + N, str) - S;
		f(l, e, i + 1, str);
		str.pop_back();
		str.push_back('0');
		f(s, l - 1, i + 1, str);
		str.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> L;
	for(int i = 0; i < N; i++) cin >> S[i];

	sort(S, S + N);
	string str = "";
	f(0, N - 1, 0, str);
	cout << (ans ? "Alice" : "Bob") << "\n";
	return 0;
}


Measured memory_bytes: 10704
N, M = map(int,input().split())
s = []
c = []
for i in range(M):
  S, C = map(int,input().split())
  s.append(S)
  c.append(C)


for i in range(10 ** (N + 1)):
  Str = str(i)

  if len(Str) == N and all([Str[s[j] - 1] == str(c[j]) for j in range(M)]):
      print(Str)
      exit()

print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vi L(n); rep(i, n) cin >> L[i];
  sort(all(L));

  ll ans = 0;
  rep(a, n-2){
    int right = a+2;
    for (int left = a+1; left < n-1; left++) {
      while (right < n && L[a] > L[right] - L[left]) {
        right++;
      }
      ans += right - left - 1;
    }
  }
  std::cout << ans << '\n';
}


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

int main() {
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < 4; i++) {
		if (s.at(i) == '+') ans++;
		else ans--;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>//swapでaとbの値を入れ替える
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
#define s(s) sort(s.begin(),s.end())
#define r(s) reverse(s.begin(),s.end())
using namespace std;
int main() {
	int a,b,ans,c,d;
	cin >> a>>b>>c>>d;
	int abc = max(a, max(b, c));
	int aaa = a + b + c;
	ans = abc;
	rep(i, d)abc *= 2;
	cout << abc-ans+aaa << endl;

	return 0;
}
	



Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;

const int MAX = 2000000;
int heap[MAX+1];
int heap_size=0;
void swap(int *x, int *y){
    int k = *y;
    *y = *x;
    *x = k;
}
int left(int x){
    return 2*x;
}
int right(int x){
    return 2*x+1;
}
void max_heapify(int A[], int i){
    int l, r, largest;
    l = left(i);
    r = right(i);
    if (l <= heap_size && heap[l] > heap[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if (r <= heap_size && heap[r] > heap[largest])
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(&A[i], &A[largest]);
        max_heapify(A, largest);
    }   
}
void build_maxheap(int A[]){
    for (int i = heap_size/2; i >= 1; i--)
    {
        max_heapify(A, i);
    }
    
}
void insert(int x){
    heap_size++;
    heap[heap_size] = x;
    int i = heap_size;
    while(i > 1 && heap[i/2] < heap[i]){
        swap(&heap[i], &heap[i/2]);
        i/=2;
    }
}

int extract_max(){
    int heap_max = heap[1];
    heap[1] = heap[heap_size];
    heap_size--;
    max_heapify(heap,1);
    return heap_max;
}

int main(){
    while (true){
        char str[10];
        int x;
        scanf("%s", str);
        if (str[0] == 'i')
        {
            scanf("%d", &x);
            insert(x);
        }
        else if (str[1] == 'x')
        {
            cout << extract_max() << endl;
        }
        else
        {
            break;
        }
        
    }
}


Measured memory_bytes: 7036
#include<stdio.h>
#include<math.h>
 
int main(){
  int a,b,C;
  double S,L,h;
 
  scanf("%d %d %d",&a,&b,&C);
 
  S = (double)0.5 * (double)a * (double)b * (double)sin((double)C/180*M_PI);
  L = (double)a + (double)b + sqrt ( pow ( (double)a , 2 ) + pow ( (double)b , \
2) - 2 * (double)a * (double)b * cos((double)C/180*M_PI ) );
  h = (double)b * sin((double)C/180*M_PI);
 
  printf("%lf\n%lf\n%lf\n",S,L,h);
 
  return 0;
}

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

int main(){
	int a,b;
	cin >> a >> b;
	int c = b-a;
	int ans = (1+c)*c/2 - b;
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys

import math
import itertools
import random
def next(index, lis):
    for i in range(index, 0):
        if (i != 0):
            return i

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
cnt = 1
tmp=1
while (True):
    if (cnt == n-1):
        break
    ans += a[tmp]
    cnt+=1
    if (cnt == n-1):
        break
    ans += a[tmp]
    cnt+=1
    tmp+=1
print(ans)   


Measured memory_bytes: 104464
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void print_YES_NO(bool answer){cout<<(answer?"YES":"NO")<<endl;}
void print_Yes_No(bool answer){cout<<(answer?"Yes":"No")<<endl;}
void print_POSSIBLE_IMPOSSIBLE(bool answer){cout<<(answer?"POSSIBLE":"IMPOSSIBLE")<<endl;}

int s[3005][2];

int min(int a,int b,int c,int d){
	return min(min(a,b),min(c,d));
}

int main(){
	int n,m;
	int i,j,k;
	int a,b,c;
	cin>>n>>m;
	for(i=0;i<m;i++){
		cin>>a>>b;
		a=min(a,n-a+1,b,n-b+1);
		a=(a-1)%3+1;
		cout<<a<<endl;
	}
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, w;
	cin >> h >> w;
	vector<string> s(h);
	rep(i, h) cin >> s[i];
	rep(i, h) {
		rep(j, w) {
			if (s[i][j] == '.') continue;
			bool elf = false;
			rep(k, 4) {
				int nx = i + dx[k], ny = j + dy[k];
				if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
				if (s[nx][ny] == '#') elf = true;
			}
			if (!elf) {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILL(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};


int main(){

  int n,m;
  cin >> n >> m;
  priority_queue<P,vector<P>,less<P>> que;
  vector<ll> v(n);
  REP(i,n){
    cin >> v[i];
    que.push({v[i],i});
  }
  ll ovalue = -1;
  REP(i,m){
    P value = que.top();que.pop();
    value.first /= 2;
    v[value.second] = value.first;
    que.push(value);
  }
  ll res = 0;
  REP(i,n)res += v[i];
  cout << res;

  return 0;
}


Measured memory_bytes: 3188
#include <iostream>

using namespace std;

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



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());

        int[] A = new int[M];
        int sum=0;

        for(int i=0; i<M; i++){
            A[i] = Integer.parseInt(sc.next());
            sum += A[i];
        }

        if(sum > N){
            System.out.println(-1);
        }else{
            System.out.println(N - sum);
        }

    }
}

Measured memory_bytes: 41672
//    ____       ____                 _           
//   |  _ \ _ __|  _ \  ___ _ __   __| |_ __ ___  
//   | | | | '__| | | |/ _ \ '_ \ / _` | '__/ _ \ 
//   | |_| | |_ | |_| |  __/ | | | (_| | | | (_) |
//   |____/|_(_)|____/ \___|_| |_|\__,_|_|  \___/ 
//                                                

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

using namespace std;
using namespace __gnu_pbds;


#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define f first
#define s second
#define pb push_back
#define ll long long

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll LLOO = 1e18+7;
const ll OO = 1e9+7;
const int MOD = 1e9+7;
const int N = 1e5+7;



int main()
{
	
	string str;
	cin >> str;
	if (str[2] == str[3] && str[4] == str[5]) printf("Yes\n");
	else printf("No\n");
	
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/


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

    array<int,26> ar;
    rep(i,26) ar[i]=0;
    rep(i,n) ar[s[i]-'a']++;


    ll ans = n * (n-1) / 2 + 1;

    rep(i,26){
        ll t = ar[i];
        ans -= t*(t-1)/2;
    }

    cout << ans << endl;
}


Measured memory_bytes: 640
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
s = input()
yes = True
if "N" in s:
    if "S" not in s:
        yes = False
if "S" in s:
    if "N" not in s:
        yes = False
if "E" in s:
    if "W" not in s:
        yes = False
if "W" in s:
    if "E" not in s:
        yes = False
if yes:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 5308
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,m;
int a[102][102];
int b[102][102];
int sum;
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&a[j][i]);
			b[j][i]=a[j][i];
		}
	}
	for(int i=0;i<n;i++){
		int maxsc=0;
		for(int j=0;j<=m;j++){
			int sc=0;
			for(int k=0;k<j;k++){
				sc+=a[k][i];
				a[k+1][i]^=1;
			}
			for(int k=m-1;k>=j;k--){
				sc+=a[k][i];
				a[k-1][i]^=1;
			}
			for(int k=0;k<m;k++)a[k][i]=b[k][i];
			maxsc=max(maxsc,sc);
		}
		sum+=maxsc;
		for(int j=0;j<m;j++){
			a[j][i+1]^=1;
			b[j][i+1]^=1;
		}
	}
	printf("%d\n",sum);
	return 0;
}


Measured memory_bytes: 3272
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    ll a = n/100;
    ll b = n%10;

    if(a == b) {
        out("Yes");
    }
    else {
        out("No");
    }

    re0;
}

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

int main() {
  string S;
  cin >> S;
  int ball = 0;
  for(int i = 0; i < S.size(); i++){
    if(S[i] == '1'){
      ball++;
    }
  }
  cout << ball << endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
    public static void AssertEquals<T>(
				       T expected,
				       T actual,
				       [CallerLineNumber] int lno = 0
				       )
	where T : IComparable
    {
	if (expected.CompareTo(actual) != 0)
	{
	    WriteLine($"Assertion Error at line {lno}:");
	    WriteLine($"\texpected: {expected}");
	    WriteLine($"\t  actual: {actual}");
	    Environment.Exit(1);
	}
    }
}

class Program
{
    static int n;
    static int[,] map;

    static HashSet<int>[] v;
    static bool[] visiting;
    static int[] depths;
    static bool cyclic = false;
    
    public static void Main()
    {
	n = int.Parse(ReadLine());

	// initialize the map : (i,j) to match number
	map = new int[n+1,n+1];
	int m = 0;
	for (int i = 1; i <= n-1; i++)
	    for (int j = i+1; j <= n; j++)
		map[i,j] = map[j,i] = m++;
	AssertEquals(n*(n-1)/2, m);

	int[] starts = new int[n];
	v = new HashSet<int>[m];
	for (int i = 0; i < m; i++)
	    v[i] = new HashSet<int>();
	
	for (int i = 1; i <= n; i++)
	{
	    int[] a = ReadIntArray();
	    int last = map[i, a[0]];
	    starts[i-1] = last;

	    for (int j = 1; j < n-1; j++)
	    {
		int next = map[i, a[j]];
		v[last].Add(next);
		last = next;
	    }
	}

	int md = 0;
	depths = new int[m];
	visiting = new bool[m];
	for (int i = 1; i <= n; i++)
	{
	    int node = starts[i-1];
	    md = Math.Max(md, dfs(node, 1));
	}

	if (cyclic)
	{
	    WriteLine(-1);
	    return;
	}
	WriteLine(md);
    }

    static int dfs(int x, int depth)
    {
	if (cyclic || visiting[x])
	{
	    cyclic = true;
	    return -1;
	}
	
	if (depths[x] > 0)
	{
	    return depths[x] + depth - 1;
	}
	
	visiting[x] = true;

	int m = depth;
	foreach (int y in v[x])
	    m = Math.Max(m, dfs(y, depth + 1));

	depths[x] = m - depth + 1;
	visiting[x] = false;
	return m;
    }
}


Measured memory_bytes: 151008
# ref https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
import sys
input = sys.stdin.readline

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

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = (mod + 1) // 2
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)


Measured memory_bytes: 59600
#include <stdio.h>

int main(void)
{
	int Se;
	int h;
	int m;
	int s;
	
	scanf("%d", &Se);
	
	h = Se / 3600;
	m = Se % 3600 / 60;
	s = Se % 3600 % 60;  
	printf("%d:%d:%d\n", h, m, s);
	
	return 0;
}

Measured memory_bytes: 592
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	ll ans;
	cin >> ans;
	rep(i,n-1){
		ll a;
		cin >> a;
		ans = gcd(ans, a);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
n = int(input())
d = defaultdict(int)
k = 2
while n > 1 and k * k <= n:
    if n % k == 0:
        d[k] += 1
        n //= k
    else:
        k += 1
if n > 1:
    d[n] += 1
ans = 0
for k,v in d.items():
    a = 1
    while v >= a:
        v -= a
        a += 1
        ans += 1
print(ans)

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

using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;


int32_t main() {
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    
    ins(x);
    int tmp[x.size()];
    FOR(i,0,x.size())tmp[i] = 0;
    int rr1 = 0;
    int rr2 = 0;
    FOR(i,1,x.size()+1){
        if(x[i-1] == 'R'){
            if(x[i] == 'L'){
                tmp[i-1]++;
                tmp[i]++;
                if(i%2 == 0){
                    tmp[i-1]+=rr2;
                    tmp[i]+=rr1;
                }
                else{
                    tmp[i-1]+=rr1;
                    tmp[i]+=rr2;
                }
                rr1 = 0;
                rr2 = 0;
            }
            else{
                if(i%2 == 0)rr2++;
                else rr1++;
            }
        }
    }
    int ll1 = 0;
    int ll2 = 0;
    for(int i = x.size();i>=1;i--){
        if(x[i-1] == 'L'){
            if(x[i-2] == 'R'){
                if(i%2 == 0){
                    tmp[i-1]+=ll2;
                    tmp[i-2]+=ll1;
                }
                else{
                    tmp[i-1]+=ll1;
                    tmp[i-2]+=ll2;
                }
                ll1 = 0;
                ll2 = 0;
            }
            else{
                if(i%2 == 0)ll2++;
                else ll1++;
            }
        }
    }
    FOR(i,0,x.size()){cout<<tmp[i]<<" ";}
    
    
    
    
    return 0;
}


Measured memory_bytes: 1488
#include<stdio.h>

int main()
{
  int n,x;
  int a[100001],b[100001],c[100001];
  int i;
  int ans=-1;
  scanf("%d",&n);
  for(i=0;i<=100000;i++){
    b[i]=0;
  }
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    b[a[i]]++;
  }
  for(i=0;i<=100000;i++){
    c[i]=b[i];
  }
  b[0]+=b[1];
  b[n]+=b[n-1];
  for(i=1;i<100000;i++){
    b[i]+=c[i-1]+c[i+1];
    if(b[i]>ans) ans=b[i];
  }
  printf("%d\n",ans);
  return 0;
}


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

int main(){
    int A,B;cin>>A>>B;
    if(A>B)swap(A,B);
    if(A==1 and B==2)cout<<3<<endl;
    else if(A==1 and B==3)cout<<2<<endl;
    else cout<<1<<endl;
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < n; i++)

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    ll H, W, N; cin >> H >> W >> N;
    ll cnt[10] = {};
    cnt[0] = (H-2)*(W-2);

    vector<pair<ll, ll>> A(N);
    rep(i, N){
        int a, b; cin >> a >> b;
        A[i] = make_pair(a, b);
    }

    sort(A.begin(), A.end());

    map<pair<ll, ll>, int> sq;
    rep(i, N){
        for(ll j = -2; j <= 0; j++){
            for(ll k = -2; k <= 0; k++){
                ll x = A[i].first + j, y = A[i].second + k;
                if(1 <= x && x <= H-2 && 1 <= y && y <= W-2){
                    pair<ll, ll> op = make_pair(x, y);
                    if(sq.count(op)){
                        sq[op] += 1;
                    }
                    else sq[op] = 1;
                }
            }
        }
    }

    for(auto elem : sq){
        //cout << "(" <<  elem.first.first << ", " << elem.first.second << "): " << elem.second << endl;
        cnt[elem.second]++;
        cnt[0]--;
    }

    rep(i, 10) cout << cnt[i] << endl;
    return 0;
}

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

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

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

int main() {
    int X, ans = 1;
    cin >> X;
    for (int b = 2; b * b <= X; b++) {
        for (int a = b * b; a <= X; a *= b) {
            ans = max(ans, a);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
    
#define endl '\n'
//#define int long long

const int INF = 100000000;

using namespace std;
signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m, x;
    cin >> n >> m >> x;
    int books[n][m + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            cin >> books[i][j];
        }
    }
    int ans = INF;
    for (int mask = 0; mask < (2 << n); mask++) {
        int tc = 0;
        vector<int> tp(m, 0);
        for (int i = 0; i < n; i++) {
            if ((mask >> i) % 2) {
                tc += books[i][0];
                for (int j = 1; j <=m; j++) {
                    tp[j - 1] += books[i][j];
                }
            }
        }
        bool ha = true;
        for (int i = 0; i < m; i++) {
            if (tp[i] < x) {ha = false; break;}
        }
        if (ha) ans = min(ans, tc);
    }

    if (ans == INF) cout << -1;
    else cout << ans;
}


Measured memory_bytes: 3668
n = int(input())
s=[input() for _ in range(n)]
s.sort()

c=1
m=0
for i in range(n-1):
  if s[i]==s[i+1]:
    c+=1
  else:
    if c > m:
      ans=[s[i]]
      m=c
      c=1
    elif c==m:
      ans.append(s[i])
      c=1
    else:
      c=1
if c > m:
  ans=[s[n-1]]
elif c==m:
   ans.append(s[n-1])
for i in range(len(ans)):
  print(ans[i])

Measured memory_bytes: 20676
#include <stdio.h>
#include <math.h>
main(){
  int i,j,n,code;
  char cm[7],op,dict[262145];
  for(i=0,scanf("%d",&n);i<n;i++){
    scanf("%s",cm);
    for(j=code=op=0;op!='\n';scanf("%c",&op))
      if(op=='A') code+=1*pow(4,j++);
      else if(op=='C') code+=2*pow(4,j++);
      else if(op=='G') code+=3*pow(4,j++);
      else if(op=='T') code+=4*pow(4,j++);
    if(cm[0]=='i') dict[code] = 1;
    if(cm[0]=='f') dict[code] ? printf("yes\n") : printf("no\n");
  }
  return 0;
}

Measured memory_bytes: 496