akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) ((int)(a).size())
#define PB push_back
#define MP make_pair
const int maxn = 200009;
const int MOD = 1e9 + 7;
int X[maxn],Y[maxn];
char D[maxn];
int main(){
#ifdef LOCAL
  freopen(".a.in", "r", stdin);
#endif
  ios_base::sync_with_stdio(false),cout.tie(0),cin.tie(0);
  int n;cin>>n;
  for(int i=0;i<n;++i)cin>>X[i]>>Y[i]>>D[i];
  map<int,set<int>> MPu,MPd,MPl,MPr;
  for(int i=0;i<n;++i){
    if(D[i]=='U')MPu[X[i]].insert(Y[i]);
    else if(D[i]=='D')MPd[X[i]].insert(Y[i]);
    else if(D[i]=='L')MPl[Y[i]].insert(X[i]);
    else MPr[Y[i]].insert(X[i]);
  }
  int ans=2e9;
  for(auto i:MPu){
    if(!MPd.count(i.first))continue;
    for(auto j:i.second){
      auto it=MPd[i.first].lower_bound(j);
      if(it!=MPd[i.first].end()){
        ans=min(ans,(*it-j)*5);
      }
    }
  }
  for(auto i:MPr){
    if(!MPl.count(i.first))continue;
    for(auto j:i.second){
      auto it=MPl[i.first].lower_bound(j);
      if(it!=MPl[i.first].end()){
        ans=min(ans,(*it-j)*5);
      }
    }
  }
  MPu.clear();MPr.clear();MPd.clear();MPl.clear();
  for(int i=0;i<n;++i){
    if(D[i]=='U')
      MPu[X[i]-Y[i]].insert(Y[i]);
    else if(D[i]=='D')MPd[X[i]-Y[i]].insert(Y[i]);
    else if(D[i]=='L')MPl[X[i]-Y[i]].insert(Y[i]);
    else MPr[X[i]-Y[i]].insert(Y[i]);
  }
  for(auto i:MPu){
    if(!MPl.count(i.first))continue;
    for(auto j:i.second){
      auto it=MPl[i.first].lower_bound(j);
      if(it!=MPl[i.first].end()){
        ans=min(ans,(*it-j)*10);
      }
    }
  }
  for(auto i:MPr){
    if(!MPd.count(i.first))continue;
    for(auto j:i.second){
      auto it=MPd[i.first].lower_bound(j);
      if(it!=MPd[i.first].end()){
        ans=min(ans,(*it-j)*10);
      }
    }
  }
  MPu.clear();MPr.clear();MPd.clear();MPl.clear();
    for(int i=0;i<n;++i){
    if(D[i]=='U')
      MPu[X[i]+Y[i]].insert(Y[i]);
    else if(D[i]=='D')MPd[X[i]+Y[i]].insert(Y[i]);
    else if(D[i]=='L')MPl[X[i]+Y[i]].insert(Y[i]);
    else MPr[X[i]+Y[i]].insert(Y[i]);
  }
    for(auto i:MPl){
    if(!MPd.count(i.first))continue;
    for(auto j:i.second){
      auto it=MPd[i.first].lower_bound(j);
      if(it!=MPd[i.first].end()){
        ans=min(ans,(*it-j)*10);
      }
    }
  }
  for(auto i:MPu){
    if(!MPr.count(i.first))continue;
    for(auto j:i.second){
      auto it=MPr[i.first].lower_bound(j);
      if(it!=MPr[i.first].end()){
        ans=min(ans,(*it-j)*10);
      }
    }
  }
  if(ans==2e9)cout<<"SAFE";
  else cout<<ans<<"\n";
  return 0;
}
//2020.07.25 22:09:09


Measured memory_bytes: 33412
#include <iostream>
#include <vector>

using namespace std;

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

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

	int s1 = v[0];
	int s2 = v[1];
	for (int i = 2; i < n; i++) {
		s2 += v[i];
	}

	int min = ((s1 - s2) > 0 ? (s1 - s2) : (s2 - s1));
	int tmp;
	for (int i = 0; i < n - 2; i++) {
		s1 += v[i + 1];
		s2 -= v[i + 1];

		tmp = ((s1 - s2) > 0 ? (s1 - s2) : (s2 - s1));
		if (min > tmp) {
			min = tmp;
		}
	}
	cout << min << endl;

	return 0;
}

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

int main() {
  int a, b;
  int s;
  cin >> a >> b;
  
  s = a % 500;

  if (a >= 500 && s <= b) {
      cout << "Yes" << endl;
  } else if (a < 500 && a <= b) {
      cout << "Yes" << endl;
  } else {
      cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] != t[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3820
use std::cmp;
use std::fmt::Debug;
use std::str::FromStr;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where
    T: FromStr,
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim()
        .split_whitespace()
        .map(|c| T::from_str(c).unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_as_string() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn popcount(n: usize) -> usize {
    let mut n: usize = n;
    let mut ans = 0;
    while n > 0 {
        if n & 1 == 1 {
            ans += 1;
        }
        n >>= 1;
    }
    return ans;
}

fn f(x: usize) -> usize {
    let mut ans = 0;
    let mut x = x;
    while x != 0 {
        x = x % popcount(x);
        ans += 1;
    }
    return ans;
}

fn main() {
    let n: usize = read_as_vec()[0];
    let x: Vec<char> = read_as_string().chars().collect::<Vec<char>>();
    let nmax: usize = 200000;
    let mut fcache: Vec<usize> = vec![0; cmp::min(nmax, n) + 1];
    for i in 0..fcache.len() {
        fcache[i] = f(i);
    }

    let n1 = x.iter().filter(|x| **x == '1').count();
    // if n1 == 0 {
    //     for i in 0..n {
    //         println!("0");
    //     }
    //     return;
    // }

    let mut mod_n1_plus_1 = 0;
    let mut base = 1;
    for d in x.iter().rev() {
        if *d == '1' {
            mod_n1_plus_1 = (mod_n1_plus_1 + base) % (n1 + 1);
        }
        base = (base * 2) % (n1 + 1);
    }

    let mut mod_n1_minus_1 = 0;
    let mut base = 1;
    if n1 > 1 {
        for d in x.iter().rev() {
            if *d == '1' {
                mod_n1_minus_1 = (mod_n1_minus_1 + base) % (n1 - 1);
            }
            base = (base * 2) % (n1 - 1);
        }
    }

    let mut anses = vec![];
    let mut base_minus = 1;
    let mut base_plus = 1;
    for i in (0..n).rev() {
        //println!("calc = x{}", i);
        let y: usize;
        if x[i] == '1' {
            if n1 > 1 {
                y = (mod_n1_minus_1 + (n1 - 1) - base_minus) % (n1 - 1);
                anses.push(fcache[y] + 1);
            } else {
                anses.push(0);
            }
        } else {
            y = (mod_n1_plus_1 + base_plus) % (n1 + 1);
            anses.push(fcache[y] + 1);
        }

        if n1 > 1 {
            base_minus = (base_minus * 2) % (n1 - 1);
        }
        base_plus = (base_plus * 2) % (n1 + 1);
    }

    for i in (0..anses.len()).rev() {
        //println!("x{}", i);
        println!("{}", anses[i]);
    }
}


Measured memory_bytes: 6136
fun main(args: Array<String>) {
        val (n, m) = readNext().split(" ")
        val k = Integer.parseInt(n)
        val x =  Integer.parseInt(m)

        val min = if(x == 0) {
            x - (k - 1)
        }else {
            x - k + 1
        }
        val max = x + (k - 1)
        var i = min
        var result = ""
        while(i <= max) {
            result += i
            i++
            if ( i <= max ) {
                result += " "
            }
        }
        println(result)


    }


    fun readNext(): String {
        return readLine()!!
    }


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

#define pai 3.1415926535


int main(void){

	char S[51];
	scanf("%s", S);
	S[strlen(S) - 8] = '\0';
	printf("%s", S);

	return 0;


}

Measured memory_bytes: 128
#include <stdio.h>

int main(void) {
	int a,b,c,d;
	double e;
	scanf("%d%d",&a,&b);
	c=a/b;
	d=a%b;
	e = (double)  a/b;
	printf("%d %d %f\n",c,d,e);
	return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
void decimal(int x){cout<<fixed<<setprecision(x);}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

void solve() {
  ll n;
  string s;
  cin>>n>>s;
  if(n<=3){
    out(0); return;
  }
  ll r=0,g=0,b=0;
  rep(i,n){
    if(s[i]=='R') r++;
    else if(s[i]=='G') g++;
    else b++;
  }
  ll p=r*g*b;
  REP(j,1,(n-1)/2+1){
    rep(i,n-j*2){
      bool f=true;
      if(s[i]==s[i+2*j]) f=false;
      if(s[i]==s[i+j]) f=false;
      if(s[i+j]==s[i+j*2]) f=false;
      if(f) p--;
      //cout<<i<<j<<endl;
      //cout<<i<<i+j<<i+2*j<<endl;
    }
  }
  //if(p<0) out(0);
  out(p);
}

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


Measured memory_bytes: 3588
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
a, b, x = MAP()


print(b//x - (a-1)//x)

Measured memory_bytes: 5148
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <numeric>
#include <iomanip>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>

///////////////////////////////////////////////////////////////
// namespace
///////////////////////////////////////////////////////////////
using namespace std;
// namespace mp = boost::multiprecision;

///////////////////////////////////////////////////////////////
// types
///////////////////////////////////////////////////////////////
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
// using mpi = mp::cpp_int;
// using mpf = mp::number<mp::cpp_dec_float<1024>>;

///////////////////////////////////////////////////////////////
// mod https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
///////////////////////////////////////////////////////////////
// ll MOD = 1000000007;
//
//  ll mod(ll val) {
//      ll res = val % MOD;
//      if (res < 0) res += MOD;
//      return res;
//  }
//
// ll modinv(ll a) {
//     ll b = MOD, u = 1, v = 0;
//     while (b) {
//         ll t = a / b;
//         a -= t * b; swap(a, b);
//         u -= t * v; swap(u, v);
//     }
//     u %= MOD;
//     if (u < 0) u += MOD;
//     return u;
// }
//
// const int MAX = -1;
// ll fac[MAX], finv[MAX], inv[MAX];
// void com_init() {  // initialize nCk table with O(N)
//     fac[0] = fac[1] = 1;
//     finv[0] = finv[1] = 1;
//     inv[1] = 1;
//     for (int i = 2; i < MAX; i++){
//         fac[i] = fac[i - 1] * i % MOD;
//         inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
//         finv[i] = finv[i - 1] * inv[i] % MOD;
//     }
// }
// ll com(int n, int k){  // nCk
//     if (n < k) return 0;
//     if (n < 0 || k < 0) return 0;
//     return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
// }


int main() {
    ld a, b, x, ans;
    cin >> a >> b >> x;
    cout << setprecision(10);
    if (2 * x >= a * a * b) {
        ans = - atan(2 * x / a / a / a - 2 * b / a) * 180 / M_PI;
    } else {
        ans = 90 - atan(2 * x / a / b / b) * 180 / M_PI;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <list>
#include <cmath>
#include <stack>
#include <iomanip>

using namespace std;
typedef long long ll;
using Pll = pair<ll,ll>;

const ll INF = 1LL<<60;
const ll MOD = 1000000007;

//cout << fixed << setprecision(10);

int main() {
    ll A,B,C;
    cin >> A >> B >> C;
    ll K;
    cin >> K;
    if(K%2==0){
        cout << A-B << endl;
    }
    else{
        cout << B-A << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<stdio.h>
#include<stack>
#include<queue>
#include<stdlib.h>
#define LEN 100005

using namespace std;
typedef pair<int,string> P;
int main(){
    
    queue<pair<int,string> > q;
    int n,p;
    cin>>n>>p;
    int elaps=0;
    for(int i=0;i<n;i++){
        string name;
        int x;
        cin>>name>>x;
        q.push(make_pair(x,name));
    }
    while(!q.empty()){
        
        P u=q.front();
        q.pop();
        int c=min(u.first,p);
        u.first-=c;
        elaps+=c;
        if(u.first>0){
            q.push(u);
        }else{
            cout<<u.second<<" "<<elaps<<endl;
        }
        
        
        
    }
    return 0;
}



Measured memory_bytes: 6336
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

R = int(read())

if R < 1200:
    answer = 'ABC'
elif R < 2800:
    answer = 'ARC'
else:
    answer = 'AGC'
    

print(answer)



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

using namespace std;

int main(void){
    int N,K;
    cin>>N>>K;
    vector<int> h(N);
    for(int i=0;i<N;i++){
        cin>>h[i];
    }
    int count=0;
    for(int i=0;i<N;i++){
        if(h[i]>=K) count++;
    }
    cout<<count<<endl;
    return 0;
}

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

using namespace std;

#define INF 1<<30
#define LINF 1ll<<60ll
#define pb(a) push_back(a)
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vi>
#define P pair<int,int>
#define all(vec) (vec.begin()),(vec.end())
#define ll long long
#define sz(x) ((int)(x).size())
#define in(x) int x;cin>>x
#define bit(n) (1<<(n))

#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REP3(i, m, n) for(int i = m, i##_len=(n);i < i##_len;++i)
#define FORVEC(i, v) for(int i = 0;i < sz(v);++i)

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

#define fil0(i,n) cout<<swet(n)<<setfill('0')<<i<<resetiosflags(ios_base::floatfield)


int main(){
    ll n,t,tt;
    ll bef=0;
    cin>>n>>t;
    ll ans=0;
    cin>>tt;
    REP(i,n-1){
        cin>>tt;
        if(tt-bef<t){
            ans+=tt-bef;
        }else{
            ans+=t;
        }
        bef=tt;
    }
    ans+=t;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int MOD = 1000000007;

LL SN[55][55];

LL choose(int N, int K1, int K2) {
  if (N < K1 + K2) return 0;
  return SN[N][K1] * SN[N-K1][K2] % MOD;
}

LL DP[55][55][55];

int main() {
  // ios_base::sync_with_stdio(0);

    int N;
    scanf("%d", &N);

  REP(i,55) {
    SN[i][0] = SN[i][i] = 1;
    FOR(j,1,i) SN[i][j] = (SN[i-1][j-1] + SN[i-1][j]) % MOD;
  }

  DP[1][1][0] = 1;
  FOR(i,2,51) {
    for (int pos = 0; pos <= i; ++pos) {
      for (int neg = 0; pos + neg <= i; ++neg) {
        int left = i - pos - neg;
        for (int prev_pos = 0; prev_pos <= left; ++prev_pos)
          for (int prev_neg = 0; prev_pos+prev_neg <= left; ++prev_neg) {
            int up_pos = prev_pos - pos + neg;
            int up_neg = prev_neg - neg + pos;

            if (up_pos < 0 || up_neg < 0) continue;
            if (pos > neg && prev_pos < pos - neg) continue;
            if (neg > pos && prev_neg < neg - pos) continue;

            (DP[i][pos][neg] += DP[left][prev_pos][prev_neg] * choose(left, up_pos, up_neg)) %= MOD;
          }
      }
    }
  }

  LL result = 0;
  REP(pos,51)REP(neg,51) (result += DP[N][pos][neg] * choose(N,pos,neg)) %= MOD;
  printf("%lld\n", result);
}


Measured memory_bytes: 768
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#define rep(i,n) for(ll i=0;i<n;i++)
typedef long long ll;
using namespace std;

const ll MAX = 1000000;
const ll MOD = 1000000007;

ll fac[MAX];

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

ll pow_kai(ll a,ll n){//aのn乗を計算します。
  ll x = 1;
  while(n > 0){//全てのbitが捨てられるまで。
    if(n&1){//1番右のbitが1のとき。
      x = x*a%MOD;
    }
    a = a*a%MOD;
    n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
  }
  return x;
}

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    ll tmp=1;
    for(ll i=n;i>=n-k+1;i--) tmp = (tmp*i)%MOD;

    return (tmp * pow_kai(fac[k],MOD-2)) % MOD;
}

void chmax(ll &a,const ll &b){
    if(a<b) a=b;
}
void chmin(ll &a,const ll &b){
    if(a>b) a=b;
}


int main()
{

    ll N;
    cin >>N;

    ll tmp[100001],p,sum=0;;

    rep(i,100001) tmp[i]=0;

    rep(i,N){
        cin >> p;
        tmp[p]++;
        sum+=p;
    }

    ll Q;
    cin >> Q;

    rep(i,Q){
        ll B,C;
        cin >>B>>C;

        sum = sum - B*tmp[B] + C*tmp[B];

        tmp[C] += tmp[B];
        tmp[B]=0;

        cout <<sum<<endl;

    }
  



    return 0;


}

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

int n, ans, fl, a[1000005];
string s;

int f() {
	int i, j, re=0;
	for(i=0; i<n; i++) {
		j = n - 1 - i;
		if((i^j) == i+j) re += a[i];
	}
	return re%2;
}

int main() {
	int i;
	cin >> n >> s;
	for(i=0; i<n; i++) {
		a[i] = s[i] - '1';
		if(a[i]==1) fl = 1;
	}
	if(!fl) {
		for(i=0; i<n; i++) a[i] /= 2;
	}
	ans = f();
	if(!fl) ans *= 2;
	cout << ans;
	return 0;
}

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

using namespace std;
using LL = long long;

constexpr int MAXN = 55;

struct Node {
    Node() = default;
    Node(LL _c, string& _l, string& _r) : c(_c), l(_l), r(_r) {}
    LL c;
    string l, r;
    friend inline bool operator<(const Node& lhs, const Node& rhs) {
        return lhs.c > rhs.c;
    }
};
LL n, cost[MAXN];
string s[MAXN], emps("");

inline bool isPalindrome(const string& tmp) {
    for (int i = 0; i < tmp.size() /2 + 1; i++)
        if (tmp[i] != tmp[tmp.size() - 1 - i]) return false;
    return true;
}
/*@return l, r第一个不同的位置*/
inline int check(string& l, string& r) {
    int i = 0;
    for (; i < min(l.size(), r.size()); i++)
        if (l[i] != r[r.size() - 1 - i]) break;
    l = l.substr(i), r = r.substr(0, r.size() - i);
    return i;
}

priority_queue<Node, vector<Node>> q;
map<string, map<string, bool>> vis;
inline void search() {
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        if (vis[cur.l][cur.r]) continue;
        if (isPalindrome(cur.l) && cur.r.empty()) {
            cout << cur.c << endl;
            return;
        } else if (isPalindrome(cur.r) && cur.l.empty()) {
            cout << cur.c << endl;
            return;
        } else if (cur.l.empty() && cur.r.empty()) {
            cout << cur.c << endl;
            return;
        } else {
            for (int i = 1; i <= n; i++) {
                Node tmp(cur.c, cur.l, cur.r);
                if (tmp.l.size() >= tmp.r.size()) {
                    tmp.r = s[i] + tmp.r, tmp.c += cost[i];
                    int id = check(tmp.l, tmp.r);
                    if (id) q.push(tmp);
                } else {
                    tmp.l = tmp.l + s[i], tmp.c += cost[i];
                    int id = check(tmp.l, tmp.r);
                    if (id) q.push(tmp);
                }
            }
        }
        vis[cur.l][cur.r] = true;
    }
    cout << -1 << endl;
}

int main () {
    //freopen("test.in", "r", stdin);
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> cost[i];
        q.push(Node(cost[i], s[i], emps));
        q.push(Node(cost[i], emps, s[i]));
    }
    search();
    return 0;
}

Measured memory_bytes: 3836
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#define MN 505
using namespace std;
const int INF=1e9;
int c[MN],d[MN],bo[MN];
char s[MN][MN];
queue<int> q;
int n,mmh=INF,id=0,ma;
int main(){
	register int i,j;
   	scanf("%d",&n);
    for(i=1;i<=n;i++)
	for(scanf("%s",s[i]+1),j=1;j<=n;j++){
        s[i][j]=(s[i][j]=='#');
        c[i]+=s[i][j];ma=max(ma,c[i]);
    }
    if(!ma) return puts("-1"),0;
    for(i=1;i<=n;i++) d[i]=1;
    
    for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	if (s[i][j]) d[j]=0;
    
    for(i=1;i<=n;i++) if(d[i]!=INF&&n-c[i]<mmh) mmh=min(mmh,n-c[i]+d[i]),id=i;
    
    for(j=1;j<=n;j++) for(i=1;i<=n;i++) if (!s[i][j]) {mmh++;break;}
    printf("%d\n",mmh);
}

Measured memory_bytes: 512
#pragma GCC optimze("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
const ll inf=1e18, N=50005;
vector<ll> adj[N];
inline ll mult(ll x,ll y){x%=hell;y%=hell;return (1LL*x*y)%hell;}
inline ll add(ll x,ll y){x+=y;return x%hell;}
inline ll powMod(ll base,ll expo){
	if(base==0)return 0;
	ll ans=1;
	while(expo){
		if(expo&1)ans=mult(ans,base);
		base=mult(base,base); 
		expo>>=1;
	}
	return ans;
}
void solve(){
	ll n;
	cin>>n;
	vector<ll> v(n);
	rep(i,0,n)
		cin>>v[i];
	ll dp[n+2];
	dp[0]=0;
	dp[1]=abs(v[1]-v[0]);
	rep(i,2,n)dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]),dp[i-2]+abs(v[i]-v[i-2]));
	cout<<dp[n-1];
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0 ;
}


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

int main() {
  int n,m; cin >> n >> m;
  vector<int> x(m); for(int i = 0;i < m;i++) { cin >> x[i]; }
  sort(x.begin(),x.end());

  int ans = 0;
  vector<int> y(m-1); for(int i = 0;i < m-1;i++) { y[i] = x[i+1]-x[i]; }
  sort(y.begin(),y.end());

  for(int i = 0;i+n < m;i++) { ans += y[i]; }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <utility>
#include <tuple>
using namespace std;
using Int = long long;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n,m) for(int i=n;i<m;i++)
template <typename Container> void P(const Container &c) {
    for (const auto& x : c) cout << x << ' '; cout << '\n';
}
int main()
{
    int N, M; cin >> N >> M;
    vector<vector<pair<int, int>>> pref(N+1);
    vector<string> city(M+1);
    FOR(i, 1, M+1) {
        int p, y; cin >> p >> y;
        pref[p].push_back(make_pair(y, i));
    }
    FOR(i, 1, N+1) {
        sort(pref[i].begin(), pref[i].end());
        REP(j, pref[i].size()) {
            int y, id;
            tie(y, id) = pref[i][j];
            char buffer[1024];
            sprintf(buffer, "%06d%06d", i, j + 1);
            city[id] = buffer;
        }
    }
    FOR(i, 1, M+1) cout << city[i] << endl;
    return 0;
}


Measured memory_bytes: 12416
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define all(v) v.begin(), v.end()
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int s;
    cin>>s;
    int a=s/1000*10+(s-s/1000*1000)/100;
    int b=s-a*100;
    //aが前半2文字、bが後半2文字
    if(1<=a&&a<=12&&1<=b&&b<=12) cout<<"AMBIGUOUS"<<endl;
    else if(1<=a&&a<=12) cout<<"MMYY"<<endl;
    else if(1<=b&&b<=12) cout<<"YYMM"<<endl;
    else cout<<"NA"<<endl;
}

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

int main() {
  int n; cin >> n;
  int s[n], l[n], p[n];
  rep(i, n) {
    int a, b, c; cin >> a >> b >> c;
    s[i] = a; l[i] = b; p[i] = c;
  }
  
  int dp[n][395]; memset(dp, -1, sizeof(dp));
  rep(i, n) {
    rep(j, 395) {
      int ii = max(i-1, 0);
      int x = s[i], y = l[i];
      if (j < x) {
        dp[i][j] = dp[ii][j];
      }
      else if (j >= x && j <= y) {
        dp[i][j] = max(dp[ii][j], p[i]);
        for (int k = x; k <= j; k++) {
          if (dp[i][j-k] != -1) {
            dp[i][j] = max(dp[i][j], dp[i][j-k] + p[i]);
          }
        }
      }
      else {
        dp[i][j] = dp[ii][j];
        for (int k = x; k <= y; k++) {
          if (dp[i][j-k] != -1) {
            dp[i][j] = max(dp[i][j], dp[i][j-k] + p[i]);
          }
        }
      }
    }
  }
  
  int m; cin >> m;
  vector<int> point(m);
  bool finish = false;
  rep(i, m) {
    int w; cin >> w;
    if (dp[n-1][w] == -1) {
      finish = true;
      break;
    }
    point[i] = dp[n-1][w];
  }
  if (finish) {
    cout << -1 << endl;
    return 0;
  }
  else {
    rep(i, m) {
      cout << point[i] << endl;
    }
  }
}    


Measured memory_bytes: 3580
#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <cstdlib>
#include <iomanip>
#include <stdio.h>
#include <climits>

using namespace std;

int s[100];
int i=0;

void push(int v)
{
  //printf("push v %d i %d\n",v,i);
  s[i]=v;
  i++;
}

int pop()
{
  i--;
  //printf("pop s[i]%d i %d\n",s[i],i);
  if(i<0) exit(0);
  int r = s[i];
  return r;
}


int main(){
  int v1,v2;
  char buf[11];

  while(scanf("%s ",buf)!=EOF){
    v1 = atoi(buf);
    if(v1 != 0)
      push(v1);
    else if(buf[0]=='+'){
        v2 = pop();
        v1 = pop();
        push(v1+v2);
    }
    else if(buf[0]=='-'){
        v2 = pop();
        v1 = pop();
        push(v1-v2);
    }
    else if(buf[0]=='*'){
        v2 = pop();
        v1 = pop();
        push(v1*v2);
    }
  }
  printf("%d\n",pop());
}



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

#include <iostream>
#include <string>
using namespace std;

string s;
int N;

int main() {

	cin>>s;
	N=s.size();
	int ans=0;
	int a0,a1,a2,a3;

	for(a0=0; a0<N; a0=a3){
		for(a1=a0; s[a1]=='J'; a1++);
		for(a2=a1; s[a2]=='O'; a2++);
		for(a3=a2; s[a3]=='I'; a3++);
		if(a1-a0>=a2-a1 && a2-a1<=a3-a2)ans=max(ans,a2-a1);
	}


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

Measured memory_bytes: 3992
#include <iostream>
#include<time.h>
#include<string>
#include<cstring>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
#include<stack>
#include<set>
#include <limits>
#include <climits>
#include <numeric>
#include<cassert>
#include<cctype>
#include<iterator>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef vector<ll>VI;
typedef vector<bool>VB;
typedef pair<ll,ll>P;
typedef pair<double,double>P_D;
#define VV(T) vector<vector<T>>
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define reprev(i, n) for (ll i = (ll)n - 1; i >= 0; i--)
#define bitrep(bit,A) for(int bit=A; ;bit=(bit-1)&A)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) (ll)((a).size())
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
#define chmax(x,a) x=c_max(x,a)
#define chmin(x,a) x=c_min(x,a)
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define SORT(c) stable_sort(ALL(c))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX_6 1001001//6
#define MAX_7 10010010//7
#define SENTINEL 2000000000//9
#define NIL -1
const int MOD = 1000000007;
#define INF 1<<30
#define INFTY 1000000000000000001LL
#define MAX_INT INT_MAX
#define Endl '\n'
#define greater greater<int>()
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}
using Edge=pair<int,ll>;
using Graph=vector<vector<Edge> >;//ll or Edge
using Edge=pair<int,ll>;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// g++ -o a a.cpp -Wall -lm -std=c++14


int main(){
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    for(ll i=k;i<=n+1;i++){
        ans=(ans+(n-i+1)*i%MOD+1)%MOD;
        /*
        ll l=i*(i-1)/2;
        ll r=(2*n-i+1)*i/2;
        ans=(ans+r-l+1)%MOD;
        */
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>
#include <set>
#include <deque>

#define mod 1000000007
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOREACH(i, v) for(auto i = v.begin(); i != v.end(); i++)

using namespace std;
using ll = long long;

int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};

int gcd(int a, int b) {
    int x = max(a, b);
    int y = min(a, b);
    int z = x % y;
    if(z == 0){
        return y;
    }else{
        return gcd(y, z);
    }
}

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

void solve() {
    ll x, y;
    vector<pair<ll, ll> > v;
    ll n, k;
    cin >> n >> k;
    REP(i, n) cin >> x >> y, v.push_back(make_pair(x, y));     
    sort(v.begin(), v.end());
    REP(i, n){
        k -=v[i].second;
        if(k <= 0){
            cout << v[i].first << endl;
            return;
        }
    }
}

int main(){
    solve();
    return 0;
}

Measured memory_bytes: 2420
import std.stdio;

void main() {
  while(true) {
    uint[3][3] black, white;
    char[3][3] field;
    for(int i = 0; i < 3; i++)
      for(int j = 0; j < 3; j++) {
        scanf(j == 2 ? "%c\n" : "%c", &field[i][j]);
        if (field[i][j] == '0') goto end;
      }

    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 3; j++) {
        if (field[i][j] == 'b') {
          black[0][i]++;
          black[1][j]++;
        }
        else if (field[i][j] == 'w') {
          white[0][i]++;
          white[1][j]++;
        }
      }
    }

    for(int i = 0; i < 3; i++) {
      if (field[i][i] == 'b') black[2][0]++;
      if (field[i][i] == 'w') white[2][0]++;
      if (field[2 - i][i] == 'b') black[2][1]++;
      if (field[2 - i][i] == 'w') white[2][1]++;
    }
  
    for(int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (black[i][j] == 3) {writeln("b"); goto next;}
        if (white[i][j] == 3) {writeln("w"); goto next;}
      }
    }
    writeln("NA");
  next:;
  }
end:;
}

Measured memory_bytes: 1008
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;


class Unionfind{
    public:
    vector<int> par,rank;//par:親,rank:木の深さ

    Unionfind(int n){
        par.resize(n);
        rank.resize(n);
        rep(i,n){
            par[i] = i;
            rank[i] = 0;
        }
    }

    int find(int x){
        if(par[x]==x) return x;
        else return par[x] = find(par[x]);
    }

    void unite(int x,int y){
        x = find(x);
        y = find(y);
        if(x == y) return;

        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return find(x) == find(y);
    }
};

using pii = pair<int,int>;

bool comp(const pii &a ,const pii &b){
    if(a.first < b.first) return true;
    
    return false;
}
bool comp2(const pair<int,pii > &a ,const pair<int,pii > &b){
    if(a.first < b.first) return true;
    // else if(){//
    //     return true;
    // }
    
    return false;
}

int main(){
    int n;
    cin >> n;
    int x,y;
    Unionfind uf(n);
    vector<pii> vx(n),vy(n); 
    rep(i,n){
        cin >> x >> y;
        x--; y--;
        vx[i] = make_pair(x,i);//x座標準、頂点番号
        vy[i] = make_pair(y,i);//y座標準、頂点番号
    }

    sort(vx.begin(),vx.end(), comp);
    sort(vy.begin(),vy.end(), comp);

    vector<pair<int,pii > > dis(2*n-1);
    rep(i,n-1){
        dis[2*i]   = make_pair((vx[i+1].first - vx[i].first),make_pair(vx[i+1].second, vx[i].second));
        dis[2*i+1] = make_pair((vy[i+1].first - vy[i].first),make_pair(vy[i+1].second, vy[i].second));
    }

    dis[2*n-2] = make_pair(2e9,make_pair(0, 1));    
    sort(dis.begin(),dis.end() ,comp2);

    ll ans = 0;

    // rep(i,2*n-1){
    //     cout << dis[i].first << " (" << dis[i].second.first << ","  << dis[i].second.second << ")" << endl;
    // }

    rep(i,2*n-1){ 
        if(!uf.same(dis[i].second.first,dis[i].second.second)){
            ans += dis[i].first;
            uf.unite(dis[i].second.first,dis[i].second.second);
           //cout  << dis[i].first << " " << dis[i].second.first << "-" << dis[i].second.second << endl; 
        }
    }
    cout << ans << endl;
    return 0;
}


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

int n, m, p, q, c;
typedef pair<long long, long long> iPair;
map< long long, vector< pair<long long, int> > > G;

long long Find(long long x, long long y)
{
    return x*10000000000+y;
}

void Dijkstra(long long src)
{
    priority_queue< iPair, vector <iPair> , greater<iPair> > PQ;
    map<long long, long long> dist;

    PQ.push(make_pair(0, src));
    dist[src] = 0;

    while(!PQ.empty()) {
        iPair P = PQ.top();
        PQ.pop();
        long long u = P.second;

        if(dist[u] < P.first) continue;

        for(int i=0; i<G[u].size(); i++) {
            long long v = G[u][i].first;
            long long w = G[u][i].second;

            if (dist.find(v) == dist.end() || dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                PQ.push(make_pair(dist[v], v));
            }
        }
    }
    if(dist.find(Find(n, 0)) == dist.end()) cout << -1 << endl;
    else cout << dist[Find(n, 0)] << endl;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        cin >> p >> q >> c;
        G[Find(p, c)].push_back(make_pair(Find(q, c), 0));
        G[Find(q, c)].push_back(make_pair(Find(p, c), 0));
        G[Find(p, 0)].push_back(make_pair(Find(p, c), 1));
        G[Find(p, c)].push_back(make_pair(Find(p, 0), 0));
        G[Find(q, 0)].push_back(make_pair(Find(q, c), 1));
        G[Find(q, c)].push_back(make_pair(Find(q, 0), 0));
    }
    Dijkstra(Find(1, 0));

    return 0;
}


Measured memory_bytes: 101232
import java.util.*;

public class Main{

    static int h, w;
    static int[][] dir = new int[][]{{0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        while(true){
            w = sc.nextInt();
            h = sc.nextInt();
            if(w==0 && h==0)break;
            int[][] c = new int[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    c[i][j] = sc.nextInt();
                }
            }
            boolean[][] used = new boolean[h][w];
            int ans = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    ans += dfs(i, j, used, c);
                }
            }
            sb.append(ans + "\n");
        }
        System.out.print(sb.toString());
        sc.close();

    }
    private static int dfs(int vh, int vw, boolean[][] used, int[][] c) {
        if(vh < 0 || h <= vh || vw < 0 || w <= vw) return 0;
        if(used[vh][vw] || c[vh][vw] == 0) return 0;
        used[vh][vw] = true;
        for(int[] nex : dir){
            dfs(vh+nex[0], vw+nex[1], used, c);
        }
        return 1;
    }

}



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

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif

using namespace std;

int main() {
    string N; int K;
    cin >> N >> K;
    set<int> ds;
    for (int i = 0; i < K; ++i) {
        int d;
        cin >> d;
        ds.insert(d);
    }

    int min_not_in_ds = -1;
    for (int t = 0; t <= 9; ++t) {
        if (!ds.count(t)) {
            min_not_in_ds = t;
            break;
        }
    }
    assert(min_not_in_ds >= 0);

    bool can_pay = true;
    deque<int> res;
    for (int i = 0; i < N.size(); ++i) {
        int di = N[N.size() - 1 - i] - '0';
        if (can_pay) {
            for (int t = di; t <= 9; ++t) {
                if (!ds.count(t)) {
                    res.push_front(t);
                    if (t > di) {
                        for (int k = 1; k < res.size(); ++k) {
                            res[k] = min_not_in_ds;
                        }
                    }
                    goto next1;
                }
            }
            can_pay = false;
            res.push_front(min_not_in_ds);
next1:;
        } else {
            for (int t = di + 1; t <= 9; ++t) {
                if (!ds.count(t)) {
                    res.push_front(t);
                    for (int k = 1; k < res.size(); ++k) {
                        res[k] = min_not_in_ds;
                    }
                    can_pay = true;
                    goto next2;
                }
            }
            res.push_front(min_not_in_ds);
next2:;
        }
    }

    if (!can_pay) {
        for (int t = 1; t <= 9; ++t) {
            if (!ds.count(t)) {
                res.push_front(t);
                break;
            }
        }
    }
    for (auto d : res) {
        cout << d;
    }
    cout << endl;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)



Measured memory_bytes: 82040
#include <bits/stdc++.h>
using namespace std;
int main()
{
	unsigned long long a,b,c,d,n,mn;
	cin>>a>>b>>c>>d>>n;
	b=min(b,2*a);
	c=min(c,2*b);
	d=min(d,2*c);
	mn=c*(n%2)+d*(n/2);
	cout<<mn<<endl;
    }
	


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

// Define
using ll = int64_t;
using ul = uint64_t;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ul MAX = ULONG_MAX;
const char nl = '\n';

#define elif else if
#define def inline auto
#define run __attribute__((constructor)) def _

// Debug
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i < _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i > _##i; --i)
#define rep(i, n) inc(i, 0, n)
#define be(c) begin(c), end(c)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("-O3")
#pragma GCC target("avx")


signed main() {
    ll n;
    cin >> n;
    vector<ll> ts(5);
    rep(i, 5) cin >> ts[i];
    auto mini = *min_element(be(ts));
    cout << (n + mini - 1)/mini + 4 << nl;
}


Measured memory_bytes: 256
#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){
  int MOD=1e9+7; 
  /*
  long int kai[2000000];
  long int rekai[2000000];
  
  kai[0]=1;
  kai[1]=1;
  rekai[0]=1;
  rekai[1]=1;
  for(int i=2;i<2000000;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=MOD;

    rekai[i]=rekai[i-1]*modinv(i,MOD);
    rekai[i]%=MOD;
  }
  */

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

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

  for(int i=0;i<n;i++){
    scanf("%ld",&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: 5784
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    int n,step=0,x=0;
    cin>>n;
    while(x!=360)
    {
        step++;
        x=x+n;
        if(x>360)
        {
            x = x -360;
        }
    }
    cout<<step;
    return 0;
}

Measured memory_bytes: 3636
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

vector<vector<int> > edges;
map<pair<int, int>, double> memo;

double solve(int curr, int prev)
{
    if(edges[curr].size() == 0)
        return 0.0;
    if(prev != -1 && edges[curr].size() == 1)
        return 0.0;

    if(memo.find(make_pair(curr, prev)) != memo.end()){
        if(prev == -1)
            return memo[make_pair(curr, prev)] / edges[curr].size();
        else
            return memo[make_pair(curr, prev)] / (edges[curr].size() - 1);
    }
    if(memo.find(make_pair(curr, -1)) != memo.end()){
        double ans = memo[make_pair(curr, -1)];
        ans -= solve(prev, curr) + 1;
        memo[make_pair(curr, prev)] = ans;
        ans /= edges[curr].size() - 1;
        return ans;
    }

    auto it = memo.lower_bound(make_pair(curr, 0));
    if(it != memo.end() && it->first.first == curr){
        double ans = it->second;
        ans += solve(it->first.second, curr) + 1;
        memo[make_pair(curr, -1)] = ans;
        if(prev == -1){
            ans /= edges[curr].size();
        }
        else{
            ans -= solve(prev, curr) + 1;
            memo[make_pair(curr, prev)] = ans;
            ans /= edges[curr].size() - 1;
        }
        return ans;
    }

    double ans = 0.0;
    for(int next : edges[curr]){
        if(next != prev)
            ans += solve(next, curr) + 1;
    }
    memo[make_pair(curr, prev)] = ans;
    if(prev == -1)
        ans /= edges[curr].size();
    else
        ans /= edges[curr].size() - 1;
    return ans;
}

int main()
{
    int n;
    cin >> n;
    edges.assign(n, vector<int>());
    for(int i=0; i<n-1; ++i){
        int u, v;
        cin >> u >> v;
        -- u;
        -- v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    for(int i=0; i<n; ++i){
        double ans = solve(i, -1);
        printf("%.10f\n", ans);
    }

    return 0;
}


Measured memory_bytes: 39680
#include <bits/stdc++.h>
using namespace std;
using ld = long double;

int main()
{
    cout << fixed << setprecision(8);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for(int i = 0;i < M;i++){
        int s, t;
        cin >> s >> t; --s, --t;
        G[s].push_back(t);
    }
    vector<ld> dp(N);
    for(int i = N - 2;i >= 0;i--){
        int sz = G[i].size();
        for(int j = 0;j < sz;j++) {
            dp[i] += (dp[G[i][j]] + 1) / sz;
        }
    }
    ld res = dp[0];
    for(int i = 0;i < N;i++) if(G[i].size() > 1) {
        vector<ld> dp2(N);
        for(int j = N - 1;j >= 0;j--){
            int sz = G[j].size();
            if(j == i){
                int id = 0;
                for(int k = 1;k < sz;k++){
                    if(dp[G[j][k]] > dp[G[j][id]]) id = k;
                }
                for(int k = 0;k < sz;k++) if(k != id) {
                    dp2[j] += (dp2[G[j][k]] + 1) / (sz - 1);
                }
                continue;
            }
            for(int k = 0;k < sz;k++){
                dp2[j] += (dp2[G[j][k]] + 1) / sz;
            }
        }
        res = min(res, dp2[0]);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1408