akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 1; i < (int)(n+1); i++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void p(vector<char> A){rep(i,A.size()){cout << A[i];}cout << endl;}
void print(vector<int> A){rep(i,A.size()){cout << A[i] << " ";}cout << endl;}

int main(){
    int n;
    cin >> n;
    ll power = 1;
    const int c = 1000000007;//10^9
    rep(i,n){
        power = (power*i)%c;
    }
    cout << power;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

const int64_t kRem = 998244353;

int64_t pow_rem(int64_t x, int64_t m, int64_t rem)
{
	if (m == 0) {
		return 1;
	}
	if (m == 1) {
		return x;
	}

	if (m & 1) {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		val *= x;
		val %= rem;
		return val;
	}
	else {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		return val;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	string s; cin >> s;

	vector<int64_t> minus_rem(n);

	int64_t minus = 0;
	FOR_LT(i, 1, n) {
		if (n % i != 0) continue;
		if (!((n / i) & 1)) continue;

		int64_t m = 0;
		int v = 1;
		FOR_LT(j, 0, i) {
			if (s[i - 1 - j] == '1') {
				m += v;
				m %= kRem;
			}
			v *= 2;
			v %= kRem;
		}

		bool is_ng = false;
		FOR_LT(j, 0, n) {
			int p = (j / i);
			int pr = j % i;

			char pc = ' ';
			if (p & 1) {
				if (s[pr] == '1') {
					pc = '0';
				}
				else {
					pc = '1';
				}
			}
			else {
				if (s[pr] == '1') {
					pc = '1';
				}
				else {
					pc = '0';
				}
			}

			if (s[j] > pc) {
				break;
			}
			if (s[j] < pc) {
				is_ng = true;
				break;
			}
		}
		if (!is_ng) m++;

		m -= minus_rem[i];
		if (m < 0) m += kRem;

		for (int j = i * 2; j < n; j += i) {
			minus_rem[j] += m;
			minus_rem[j] %= kRem;
		}

		minus += (m * (2 * n - 2 * i));
		minus %= kRem;
	}

	int64_t m = 1;
	{
		int v = 1;
		FOR_LT(i, 0, n) {
			if (s[n - 1 - i] == '1') {
				m += v;
				m %= kRem;
			}
			v *= 2;
			v %= kRem;
		}
	}

	int64_t ans = m * (n * 2) % kRem;

	ans -= minus;
	if (ans < 0) ans += kRem;

	cout << ans << endl;

	return 0;
}

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

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int gcd(int a,int b){
  while(b!=0){
    a%=b;
    swap(a,b);
  }
  return a;
}

int kaizyou(int N){
  int num=1;
  for(int i=1;i<=N;i++){
  num*=i;
  }
  return num;
}

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

signed main() {
  int x;
  cin >> x;
  int ans=0;
  int num=x/500;
  ans+=num*1000;
  int num2=(x-num*500)/5;
  ans+=num2*5;
  cout << ans << endl;
}

  
  
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define mex 1000005
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector<int> adj[mex];
		
int main(){
	fast
	double l;
	cin>>l;
	double a=l/3,b=l/3;
	double c=l-a-b;
	long double s=a*b*c;
	cout<<fixed<<setprecision(10)<<s; 
	
}



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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

typedef pair<ll, ll> P;

int MAX = 1000000000;

int main() {
    int N, K, S;
    cin >> N >> K >> S;
    vector<int> a(N);
    rep(i, N) {
        if (i < K) {
            a[i] = S;
        } else {
            if (S == MAX) a[i] = 1;
            else a[i] = MAX;
        }
    }

    rep(i, N) {
        cout << a[i];
        if (i != N - 1) cout << " ";
    }
}

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

int n, x, sol[200005];
vector<pair<int, int>> v;

int main() {
    
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        v.push_back(make_pair(x, i));
    }
    sort(v.begin(), v.end());
    sol[v[n - 1].second] = v[n - 2].first;
    for(int i = n - 2; i >= 0; i--) {
        sol[v[i].second] = v[n - 1].first;
    }
    for(int i = 1; i <= n; i++) {
        cout << sol[i] << '\n';
    }
    return 0;
}

Measured memory_bytes: 5432
#include <iostream>
#include <cstdio>
#define N 100005
using namespace std;

typedef long long ll;
ll d[N][5];
ll M = 1e9 + 7;
string a;
int main()
{
	ll i, j;
	cin >> a;
	a = ' ' + a;
	d[0][0] = 1;
	for (i = 1; i < a.size(); i++) {
		if (a[i] == '?') {
			d[i][0] = d[i - 1][0] * 3 % M;
			for (j = 1; j <= 3; j++) d[i][j] = (d[i - 1][j] * 3 + d[i - 1][j - 1]) % M;
		} else {
			for (j = 0; j <= 3; j++) d[i][j] = d[i - 1][j];
			d[i][a[i] - 'A' + 1] = (d[i][a[i] - 'A' + 1] + d[i - 1][a[i] - 'A']) % M;
		}
	}
    cout << d[a.size() - 1][3] << endl;
    return 0;
}

Measured memory_bytes: 4348
#include <iostream>

using namespace std;

int main()
{
	int N;
	long long int ans,L[87];

	cin >> N;

	L[0] = 2; L[1] = 1;

	for (int l = 2; l < 87; l++) {
		L[l] = L[l - 2] + L[l - 1];
	}

	cout << L[N];

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
typedef long long int ll;

int n,k;
vector<int> G[2100];

int dfs(int t,int f,int k,int depth=0){
	int cnt=0;
	if(depth>=k)cnt++;
	for(auto d:G[t]){
		if(d==f)continue;
		cnt+=dfs(d,t,k,depth+1);
	}
	return cnt;
}

int main(){
	cin >> n >> k;
	for(int i=0;i<n-1;i++){
		int a,b; cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int ans=n;
    if(k%2==0){
	    for(int i=0;i<n;i++){
		    int cnt=0;
		    for(int t:G[i]){
			    cnt+=dfs(t,i,k/2);
		    }
    	ans=min(ans,cnt);
    	}
    }
    else{
    	for(int i=0;i<n;i++){
    		for(int t:G[i]){
    			int cnt=dfs(t,i,(k+1)/2)+dfs(i,t,(k+1)/2);
    			ans=min(ans,cnt);
    		}
	    }
    }
	cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
signed main() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && a == c) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=15000007;
const ll MAX=9187201950435737471;
const int N=100005;
const ll INF=1e17;
const long double PI=acos(-1);



void solve(int T){
   ll a,b,c,d;
   cin>>a>>b>>c>>d;
   ll x=max(a*d,a*c),y=max(b*c,b*d);
   cout<<max(x,y);
}

int main() {
    fastio
    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
        //if(i<T)cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3652
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        int i = 0;
        while(i < 3000){
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(a != 0 || b != 0){
                if(a < b){
                    System.out.println(a + " " + b);
                }else{
                    System.out.println(b + " " + a);
                }
                
            }else{
                break;
            }
        }
    }
}



Measured memory_bytes: 35520
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if((a+b)%2==0){
        cout << abs(((a+b)/2)) << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;

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

  int first=-1;
  int last=-1;
  int num[26];
  vector < vector<int> > pos(26);

  for(int i=0;i<s.length();i++){
    int ch=(int)(s[i]-'a');
    (pos.at(ch)).push_back(i);
  }
  for(auto itr=pos.begin();itr!=pos.end();itr++){
    int tmp=-1;
    for(auto itr2=(*itr).begin();itr2!=(*itr).end();itr2++){
      if(tmp == -1){
	tmp=*itr2;
      }else{
	if(*itr2 -tmp<= 2){
	  cout << tmp+1 << " " <<*itr2+1<<endl;
	  return 0;
	}
	tmp=*itr2;
      }
    }
  
  }
  
  cout << "-1 -1"<<endl;
}


Measured memory_bytes: 1144
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define sec second
#define fir first
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
typedef vector<int> Vec;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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;};



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

	int n, m;
	cin >> n >> m;
	string a;
	if(n == 1) a = "0";
	if(n == 2) a = "10";
	if(n == 3) a = "100";
	int fixed[n] = {};

	rep(i, m) {
		int s;
		char c;
		cin >> s >> c; s--;
		if(n != 1 && s == 0 && c == '0') {
			puts("-1");
			return 0;
		}
		if(fixed[s] && a[s] != c) {
			puts("-1");
			return 0;
		}
		fixed[s] = 1;
		a[s] = c;
	}
	cout << a << endl;
	return 0;
}

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

using namespace std;

#define int long long int
#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(), (x).end()
#define capi(x) int x;cin>>x
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using vi = vector<int>;

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

#define P (1'000'000'007)

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

    vi vl;

    rep(i, n) {
        capi(l);
        vl.push_back(l);
    }

    sort(all(vl));

    int ans = 0;

    rep(i, n) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (vl[i] + vl[j] > vl[k] && vl[i] != vl[j] && vl[j] != vl[k] && vl[k] != vl[i]) ++ans;
            }
        }
    }
    
    cout << ans;

    return 0;
}

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

int main(){
    string N;
    cin >> N;
    int count = 0;
    for(char i : N){
        count += i - '0';
    }
    if(count % 9 == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
}

Measured memory_bytes: 3712
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const ll INF = ll(1e18)+1;


int main(void) {
  int  n, m;
  cin >> n >> m;
  vector<pair<int, int>> sc(m);
  rep(i, m) {
    int s, c;
    cin >> s >> c;
    sc[i].first = s-1;
    sc[i].second = c;
  }
  sort(sc.begin(), sc.end());
  vector<int> num(n, -1);
  rep(i, m) {
    if(num[sc[i].first] == -1) {
      num[sc[i].first] = sc[i].second;
    } else if(num[sc[i].first] != sc[i].second) {
      cout << -1 << endl;
      return 0;
    }
  }

  if(n == 1) {
    if(num[0] == -1) {
      num[0] = 0;
      cout << num[0] << endl;
    } else {
      cout << num[0] << endl;
    }
  } else if(n == 2) {
    if(num[0] == 0) {
      cout << -1 << endl;
    } else if(num[0] == -1) {
      num[0] = 1; {
        if(num[1] == -1) num[1] = 0;
      }
      cout << num[0] << num[1] << endl;
    } else {
      if(num[1] == -1) num[1] = 0;
      cout << num[0] << num[1] << endl;
    }
  } else if(n == 3) {
    if(num[0] == 0) {
      cout << -1 << endl;
    } else if(num[0] == 0 && num[1] == 0) {
      cout << -1 << endl;
    } else if(num[0] == -1) {
      num[0] = 1;
      if(num[1] == -1) num[1] = 0;
      if(num[2] == -1) num[2] = 0;  
      cout << num[0] << num[1] << num[2] << endl;
    } else {
      if(num[1] == -1) num[1] = 0;
      if(num[2] == -1) num[2] = 0;
      cout << num[0] << num[1] << num[2] << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, k) = (v[0], v[1]);
    let a = read_vec::<i64>();

    let mut sum = vec![0; n + 1];
    sum[0] = 0;
    for i in 1..n + 1 {
        sum[i] = sum[i - 1] + a[i - 1];
    }

    let mut sums = vec![];
    for i in 0..n {
        for j in i + 1..n {
            sums.push(sum[j + 1] - sum[i]);
        }
    }

    sums.sort();
    sums.reverse();

    let mut unused = vec![false; sums.len()];
    let digit_num = format!("{:b}", sums.iter().max().unwrap()).len();
    let mut decided_bit = vec![];

    for i in (0..digit_num).rev() {
        if exists(&sums, &unused, i, k) {
            for j in 0..sums.len() {
                if (sums[j] >> i) & 1 == 0 {
                    unused[j] = true;
                }
            }
            decided_bit.push(i);
        }
    }
    // debug!(decided_bit, digit_num, unused);
    let mut ans = 0i64;
    for num in decided_bit {
        ans += 1 << num;
    }
    println!("{}", ans);
}

fn exists(sums: &Vec<i64>, unused: &Vec<bool>, i: usize, k: usize) -> bool {
    let mut count = 0;
    for (j, &sum) in sums.iter().enumerate() {
        if unused[j] {
            continue;
        }
        if (sum >> i) & 1 == 1 {
            count += 1;
            if count == k {
                return true;
            }
        }
    }
    false
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 9976
#include <bits/stdc++.h>
#include <stdint.h>
#include <algorithm>
#include <vector>


using namespace std;

int main() {
	int n;
	
	cin >> n;
	
	vector<int>h(n,0);
	
	for (int i = 0; i < n; i++) {
		cin >> h.at(i);
	}
	bool ans = true;
	
	for(int i = 1; i < n; i++) {
		if ( h.at(i) - h.at(i-1) < -1) {
			cout << "No" << endl;
			return 0;
		} else if ( h.at(i) - h.at(i-1) == -1){
			if (ans) {
				ans = false;
			} else {
				cout << "No" << endl;
				return 0;
			}
		} else if (h.at(i) - h.at(i-1) > 0) {
			ans = true;
		}
	}
	//if (ans == false) {
	//	cout << "No" << endl;
	//} else {
		cout << "Yes" << endl;
//}
	


	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
typedef long long ll;

ll calc_gcd(ll a, ll b){
    ll  r, tmp;

    //大小入れ替え
    if( a < b ){
        tmp = a;
        a = b;
        b = tmp;
    }

    //ユークリッドの互除法
    r = a % b;
    while( r ){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll calc_lcm(ll a, ll b){
    return (a*b) / calc_gcd(a, b);
}

int main(){
    ll a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", calc_lcm(a,b));
    return 0;
}

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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)2e18);
const int ninf=((int)-2e18);
const int mod=1000000007;

using namespace std;

int power(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;
}

bool vowel(char c)
{
    return(c=='a' or c=='e' or c=='i' or c=='o' or c=='u' or c=='A' or c=='E' or c=='I' or c=='U' or c=='O');
}

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("in.txt","w",stdout);
    //FILE *fptr2=freopen("out.txt","w",stdout);

    string s;
    cin>>s;

    if(s=="MON") cout<< "6";
    else if(s=="TUE") cout<< "5";
    else if(s=="WED") cout<< "4";
    else if(s=="THU") cout<< "3";
    else if(s=="FRI") cout<< "2";
    else if(s=="SAT") cout<< "1";
    else cout<< "7";


    return 0;
}


Measured memory_bytes: 3616
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[] a = new int[N];

		for(int i=0;i<N;i++) a[i] = sc.nextInt();

		int max = 0;

		int n = 0;

		for(int i=0;i<N;i++) {

			if(a[i] == 0) n = 0;

			else n++;

			if(max<n) max = n;

		}

		System.out.println(max+1);

	}

}



Measured memory_bytes: 26420
import java.util.*;

public class Main {
  private static int N;
  private static long K;
  private static int[] A;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    K = sc.nextLong();
    A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    Arrays.sort(A);
    
    long ok = -1_000_000_000_000_000_005L;
    long ng = 1_000_000_000_000_000_005L;
    while (ok+1 < ng) {
      long m = (ok+ng)/2;
      if (isOk(m)) {
        ok = m;
      } else {
        ng = m;
      }
    }
    System.out.println(ok);
  }
  private static boolean isOk(long x) {
    long count = 0;
    for (int i = 0; i < N; i++) {
      count += calcCount(i, x);
      if (count >= 2*K) return false;
    }
    return count/2 < K;
  }
  private static int calcCount(int idx, long x) {
    if (A[idx] >= 0) {
      long max = (long)A[idx]*A[N-1];
      long min = (long)A[idx]*A[0];
      if (max < x) {
        return N-1;
      }
      if (x <= min) {
        return 0;
      }
      int ok = 0;
      int ng = N-1;
      while (ok+1 < ng) {
        int m = (ok+ng)/2;
        if ((long)A[idx]*A[m] < x) {
          ok = m;
        } else {
          ng = m;
        }
      }
      return idx <= ok ? ok : ok+1;
    } else {
      long max = (long)A[idx]*A[0];
      long min = (long)A[idx]*A[N-1];
      if (max < x) {
        return N-1;
      }
      if (x <= min) {
        return 0;
      }
      int ok = N-1;
      int ng = 0;
      while (ng+1 < ok) {
        int m = (ok+ng)/2;
        if ((long)A[idx]*A[m] < x) {
          ok = m;
        } else {
          ng = m;
        }
      }
      return idx >= ok ? N-ok-1 : N-ok;
    }
  }
}

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

typedef long long ll;
typedef unsigned long long ull;

vector<ll> b(51);

ll calc(ll depth, ll pos) {
  // P
  if (depth == 0) return 1;
  
  // BPPPB
  // ^
  if (pos == 1) return 0;

  ll mid = b[depth] / 2 + 1;
  if (mid == pos) {
    // BPPPB
    //   ^
    return (b[depth-1] / 2 + 1) + 1;
  } else if (mid < pos) {
    // BPPPB
    //    ^
    return ((b[depth-1] / 2 + 1) + 1) + calc(depth-1, pos-(b[depth]/2+1));
  } 
  // BPPPB
  //  ^
  return calc(depth-1, pos-1);
}

int main() {
  ll n, x;
  cin >> n >> x;
  
  b[0] = 1;
  for (ll i = 1; i <= n; ++i) {
    b[i] = 2*b[i-1]+3;
  }

  cout << calc(n, x) << endl;
 
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(r: int):
    print(3 * r * r)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    r = int(next(tokens))  # type: int
    solve(r)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
def M(x,L):
    l = list(str(x))
    while(len(l) != L):
        l.append("0")
    res = ""
    l.sort()
    for i in range(len(l)):
        res += l[len(l)-1-i]
    return int(res)

def m(x,L):
    l = list(str(x))
    while(len(l) != L):
        l.append("0")
    res = ""
    l.sort()
    for i in range(len(l)):
        res += l[i]
    return int(res)

def solve(a,L):
    checked = [-1 for i in range(1000000)]
    for i in range(30):
        if(checked[a] != -1):
            print(checked[a],a,i-checked[a])
            return
        checked[a] = i
        a = M(a,L) - m(a,L)

while(True):
    a,L = map(int,input().split())
    if(a == 0 and L == 0):
        break
    solve(a,L)


Measured memory_bytes: 15468
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
#define pi 3.141592653589793
#define mod 998244353
#define pb push_back
#define all(v) v.begin(),v.end()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;

int main() {
	fast_io;
	ll n, W;
	cin >> n >> W;
	vl w(n + 1), v(n + 1);
	for (int i = 1;i <= n;i++)
		cin >> w[i] >> v[i];
	ll dp[n + 1][W + 1] = {};
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= W;j++) {
			if (w[i] <= j) {
				dp[i][j] = max(dp[i - 1][j], dp[i- 1][j - w[i]] + v[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	ll ans = 0;
	for (int i = 1;i <= W;i++)
		ans = max(ans, dp[n][i]);
	cout << ans << '\n';
}


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

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

    for (int i = 0; i < n-1; i++)
    {
        if (d[i] == d[i+1])
        {
            continue;
        }
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
//#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define PB push_back
#define MP make_pair
#define INF 1073741824
#define inf 1152921504606846976
#define pi 3.14159265358979323846
//#pragma comment(linker,"/STACK:10240000,10240000")
//mt19937 rand_(time(0));
const int N=3e5+7,M=2e6;
const long long mod=1e9+7;
inline int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(;isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;return f?ret:-ret;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}//逆元
//int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;}

char str[12000];
int num[12000];
ll dp[12000][120];
int k;
ll dfs(int pos,bool up,int sum){
    if(pos==1){
        if(sum%k==0) return 1;
        return 0;
    }
    if(dp[pos][sum]!=-1&&!up) return dp[pos][sum];
    ll res=0;
    for(int i=0;i<=(up?num[pos-1]:9);i++){
        if(up&&i==num[pos-1]){
            res+=dfs(pos-1,1,(sum+i)%k);
        }
        else {
            res+=dfs(pos-1,0,(sum+i)%k);
        }
//        cout<<res<<endl;
        res%=mod;
    }
//    cout<<pos<<' '<<sum<<' '<<res<<endl;
    if(!up) dp[pos][sum]=res;
    return res;
}
ll solve(){
    int len=strlen(str);
    int ant=0;
    for(int i=len-1;i>=0;i--){
        num[++ant]=str[i]-'0';
//        cout<<num[ant]<<' ';
    }
//    cout<<endl;
    return dfs(ant+1,1,0);
}
int main(){
    //freopen("1.txt","r",stdin);
    //ios::sync_with_stdio(false);
    scanf("%s",str);
    scanf("%d",&k);
    memset(dp,-1,sizeof(dp));
    printf("%lld\n",(solve()-1+mod)%mod);
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}





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

using namespace std;

int main(){
	int n,k;
	cin >> n >> k;
	long long sum=0;
	for(int i=0;i<k;i++){
		int a;
		cin >> a;
		sum+=a;
	}
	n-=sum;
	if(n>=0) cout << n << endl;
	else cout << -1 << endl;
}

Measured memory_bytes: 3600
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	vector<ll> a(n);
	vector<ll> b(n);
	REP(i, n) cin >> a[i] >> b[i];
	vector<pll> c(n);
	REP(i, n) c[i].first = a[i] + b[i];
	REP(i, n) c[i].second = i;
	sort(ALL(c)); reverse(ALL(c));
	ll tak = 0, aoki = 0;
	REP(i, n) {
		if(i % 2 == 0) tak += a[c[i].second];
		else aoki += b[c[i].second];
	}
	cout << tak - aoki << endl;
	return 0;
}

/* --------------------------------------- */


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

using namespace std;
using ll = long long;

#define int ll
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define pb push_back
#define sz(x) int(x.size())

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);

	string a, b;
	cin >> a >> b;
	cout << b + a << endl;

	return 0;
}


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

int main(){
    string N;
    cin >> N;
    if(N[0] == N[1] && N[1] == N[2]) cout << "Yes" << endl;
    else if(N[1] == N[2] && N[2] == N[3]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3624
// ABC071B - 

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

typedef unsigned long long int ull;
typedef long long int ll;

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

	map<int, int> t;
	for (int i = 0; i < S.size(); i++) {
		t[S[i]]++;
	}

	for (int i = 'a'; i <= 'z'; i++) {
		if (t[i] == 0) {
			cout << (char)i << endl;
			return 0;
		}
	}

	cout << "None" << endl;

	return 0;
}


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

int main() {
	ll n,d;cin>>n>>d;
	int count=0;
	for(int i=0;i<n;i++)
	{   ll x,y;cin>>x>>y;
	    if(d*d>=(x*x) + (y*y))
	    count++;
	}
	cout<<count;
	return 0;
}

Measured memory_bytes: 3592
h,w,k = map(int,input().split())
y1,x1,y2,x2 = map(int,input().split())
grid = []
grid.append(['@']*(w+2))
for i in range(h):
    grid.append(['@']+list(input())+['@'])
grid.append(['@']*(w+2))

q = set()
next_q = set()
next_q.add((y1,x1))
ans = 0
while True:
    if not next_q:
        print(-1)
        exit()
    for y,x in next_q:
        grid[y][x] = '@'
    q = next_q
    next_q = set()
    while q:
        y,x = q.pop()
        if (y,x) == (y2,x2):
            print(ans)
            exit()
        for i in range(1,k+1):
            if grid[y+i][x] == '@':
                break
            next_q.add((y+i,x))
        for i in range(1,k+1):
            if grid[y-i][x] == '@':
                break
            next_q.add((y-i,x))
        for i in range(1,k+1):
            if grid[y][x+i] == '@':
                break
            next_q.add((y,x+i))
        for i in range(1,k+1):
            if grid[y][x-i] == '@':
                break
            next_q.add((y,x-i))
    ans += 1

Measured memory_bytes: 159024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 998244353;
ll mul(ll a, ll b){
    return ((a%mod) * (b%mod))%mod;
}
ll power(ll a, ll b){
    ll z = 1; ll x = a;
    while(b>0){
        if (b&1)z = mul(z, x);
        x = mul(x, x);
        b >>= 1;
    }
    return z;
}
int main()
{
    ll n;
    cin>>n;
    vector<ll> a(n);
    for (int i=0; i<n; i++)cin>>a[i];
    ll sum = 0;
    sort(a.begin(), a.end());
    ll ans = a[n-1];
    map<ll, ll> m;
    m[a[n-2]]+=2;
    ll min = a[n-2];
    // cout<<ans<<" ";
    for (int i=n-3; i>=0; i--){
        ll x = a[i];
        // cout<<min<<" ";
        ans += min;
        m[min]--;
        m[x]+=2;
        if (m[min] == 0){
            m.erase(min);
            auto it = m.end(); it--;
            min = it->first;
            
        }
    }
    // cout<<endl;
    cout<<ans<<endl;
}


Measured memory_bytes: 11104
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <complex>
#include <queue>
#include <stack>
#include <sstream>
using namespace std;
const int maxn = 2e5 + 5;
bool okb[maxn], oka[maxn];
int main()
{
	std::ios::sync_with_stdio(false);
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	string s;
	cin >> s;
	s = "*" + s;
	okb[b] = 1;
	for(int i = b + 1; i <= d; i ++)
		if(s[i] == '.' && (okb[i - 1] || okb[i - 2]))
			okb[i] = 1;
	oka[a] = 1;
	for(int i = a + 1; i <= c; i ++)
		if(s[i] == '.' && (oka[i - 1] || oka[i - 2]))
			oka[i] = 1;
	if(c > d)
	{
		bool check = 0;
		for(int i = b; i <= d; i ++)
			if(okb[i] && oka[i - 1] && oka[i + 1])
				check = 1;
		if(!check)
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << (oka[c] && okb[d] ? "Yes" : "No") << endl;
	
	return 0;
}

Measured memory_bytes: 792
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()

    if S[2] == S[3] and S[4] == S[5]:
        print('Yes')
    else:
        print('No')

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 61808
using System;
using System.Linq;

namespace ABC153
{
    class B
    {
        static void Main(string[] args)
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int H = input[0];
            int N = input[1];
            int[] A = Console.ReadLine().Split().Select(int.Parse).ToArray();

            int sum = A.Sum();

            if (H <= sum) { Console.WriteLine("Yes"); }
            else { Console.WriteLine("No"); }
        }
    }
}


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

using namespace std;

#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ELEM(array) (sizeof (array)/sizeof *(array))
#define MAX_N 100
#define SAFE_FREE(ptr) if( ptr != NULL ){ free(ptr); ptr = NULL; }
typedef unsigned int UINT;
typedef long long ll;


int n, k;
int ans = 0;
void dfs(int i,int j, int sum)
{
	if (i == n)
	{
		if (sum == k)ans++;
	}
	else if (j<=9&&sum<=k)
	{
		dfs(i + 1, j + 1, sum + j);
		dfs(i, j + 1, sum);
	}
}

int main()
{
	while (cin>>n>>k)
	{
		if (n == 0 && k == 0)return 0;
		ans = 0;
		dfs(0, 0, 0);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
// use gp_hash_table<int,int,custom_hash> m;
// in place of map
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define repba(i,b,a) for(int i=b;i>=a;--i)
#define repab(i,a,b) for(int i=a;i<b;++i)
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define msi map<string,int>
#define mii map<int,int>
#define viip vector<pair<int,pair<int,int> > > 
#define mp make_pair
#define vip vector<pair<int,int> >
#define pb push_back 
#define po pop_back
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define s(v) v.size()
ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//use rng()%n for numbers in range [0,n-1]
// This custom_hash is for unordered_map 
// use map<int, int, custom_hash> mp;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int n;
const int maxn = 1e5 + 10;
vi v[maxn];
bool vis[maxn];
vi disa(maxn);
vi dist(maxn);
void dfs(int u,int c){
	vis[u] = true;
	for(auto x:v[u]){
		if(c == 1 && !vis[x]){
			disa[x] = disa[u] + 1;
			dfs(x,1);
		}
		else if(c == 2 && !vis[x]){
			dist[x] = dist[u] + 1;
			dfs(x,2);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	#ifndef ONLINE_JUDGE
  //  	freopen("input.txt", "r", stdin);
    //	freopen("output.txt", "w", stdout);
//	#endif
	// int n;
	cin>>n;
	int a,t;
	cin>>t>>a;
	int x,y;
	rep(i,n-1){
		cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	disa[a] = 0;
	dist[t] = 0;
	dfs(a,1);
	rep(i,maxn){
		vis[i] = false;
	}
	dfs(t,2);
	int ans = 0;
	// repa(i,1,n+1){
	// 	cout<<disa[i]<<" "<<dist[i]<<"\n";
	// }
	repa(i,1,n+1){
		if(dist[i] < disa[i]){
			int temp = disa[i] - dist[i];
			// cout<<i<<" "<<temp<<"\n";
			int s1 = s(v[i]);
			if(s1 == 1){
				continue;
			}
			if(temp % 2 == 0 && temp != 0){
				ans = max(ans,disa[i]);
				// ans = max(ans,temp - 2 + disa[i]);
			}
			else if(temp % 2 == 1){
				// if(temp == 1)continue;
				ans = max(ans,disa[i]);
				// continue;
				// ans = max(ans, temp - 1 + disa[i]);
			}
			// cout<<i<<ans<<"\n";
		}
	}
	int min1 =  INT_MAX;
	repa(i,1,n+1){
		if(disa[i] == dist[i]){
			min1 = min(min1,dist[i]);
		}
	}
	if(min1 == INT_MAX)min1 = 0;
	ans = max(ans,min1);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 10496
n = gets.chomp.to_i
h = gets.chomp.split.map(&:to_i)
 
dp = Array.new(n)
dp[0] = 0
dp[1] = (h[0] - h[1]).abs
 
for i in 2..(n - 1)
  dp[i] = [dp[i - 2] + (h[i - 2] - h[i]).abs, dp[i - 1] + (h[i - 1] - h[i]).abs].min
end
 
puts dp[n - 1]

Measured memory_bytes: 11780
import java.util.*;

class Main{
 public static void main(String[] args){
  Scanner s = new Scanner(System.in);

while(s.hasNext()){
 int a = s.nextInt();
 int b = s.nextInt();
 a += b;
 String c = String.valueOf(a);
 System.out.println(c.length());
  }
 }
}

Measured memory_bytes: 20444
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------

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

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

    map<int,int> mp;
    for(int i = 0; i < n; i++){
        mp[a[i]]++;
    }

    int kind = 0;
    for(auto i : mp){
        if(i.second > 0){
            kind++;
        }
    }

    if(kind == 3){
        if(n % 3 != 0){
            cout << "No" << endl;
            return 0;
        }

        int bit = 0;

        for(auto i : mp){
            if(i.second > 0 && i.second != n / 3){
                cout << "No" << endl;
                return 0;
            }
            bit ^= i.first;
        }

        if(bit == 0){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    } else if(kind == 2){
        if(n % 3 != 0){
            cout << "No" << endl;
            return 0;
        }

        if(mp[0] == n / 3){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    } else if(kind == 1){
        if(mp[0] > 0){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    } else {
        cout << "No" << endl;
    }
}


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

int n;
string x;

lli pop_count(lli n){
    lli ret = 0;
    while(n){
        if(n&1) ret++;
        n>>=1;
    }
    return ret;
}

int main(void){
    cin >> n;
    cin >> x;
    lli m, m1, m2;
    m=0;
    for(lli i = 0; i < n; i++) if(x[i] == '1') m++;
    m1 = m-1;
    m2 = m+1;
    vector<lli> mod1(n), mod2(n); //2^i mod m1, m2
    lli b1, b2;
    b1 = b2 = 1;
    for(lli i = n-1; i >= 0; i--){
        if(m1 > 0){
            mod1[i]=b1%m1;
            b1<<=1;
            b1%=m1;
        }
        mod2[i]=b2%m2;
        b2<<=1;
        b2%=m2;
    }
    lli x1, x2;
    x1 = x2 = 0;
    for(lli i = 0; i < n; i++){
        if(x[i] == '1'){
            if(m1 > 0){
                x1 += mod1[i]%m1;
                x1%=m1;
            }
            x2 += mod2[i]%m2;
            x2%=m2;
        }
    }
    for(lli i = 0; i < n; i++){
        lli xi;
        if(x[i] == '1'){
            if(m1 == 0){
                cout << 0 << endl;
                continue;
            }
            xi = x1;
            xi -= mod1[i];
            xi%=m1;
            if(xi < 0) xi+=m1;
        }else{
            xi = x2;
            xi += mod2[i];
            xi %= m2;
        }
        lli res = 1;
        while(xi){
            xi%=pop_count(xi);
            res++;
        }
        cout << res << endl;
    }
    return 0;
}


Measured memory_bytes: 6820
#include<stdio.h>
#include<string.h>
#include<math.h>
int main(void)
{
	int a,s[1000][3],d[1000],f,g,h,i,j,k;
	scanf("%d",&a);
	for(i=0;i<a;i++){
		for(j=0;j<3;j++) scanf("%d",&s[i][j]);
		for(j=0;j<2;j++){
			for(k=j+1;k<3;k++){
				if(s[i][j]>s[i][k]){
					f=s[i][j]; s[i][j]=s[i][k]; s[i][k]=f;
				}
			}
		}
	}
	f=0;
	for(i=0;i<a-1;i++){
		if(s[i][0]!=0){
			for(j=i+1;j<a;j++){
				g=0;
				if(s[j][0]!=0){
					for(k=0;k<3;k++){
						if(s[i][k]!=s[j][k]){
							g=1;
							break;
						}
					}
					if(g==0){
						s[j][0]=0; s[j][1]=0; s[j][2]=0;
						f++;
					}
				}
			}
		}
	}
	printf("%d\n",f);
	return 0;
}

Measured memory_bytes: 2748
using System;
 
namespace AOJ.ALDS
{
    public class Allocation
    {
        public static void Main()
        {
            var input = Console.ReadLine().Split(' ');
            int pack_num = int.Parse(input[0]);
            int track_num = int.Parse(input[1]);
 
            ulong[] list = new ulong[pack_num];
            for (int i = 0; i < pack_num; i++) { list[i] = ulong.Parse(Console.ReadLine()); }
 
            // ?£?????£?????£?????£?????£?????£?????£????
            ulong max = 100000 * 10000; // ?\?????¨?????£?????§?????¨???????????£???????????\???§?\????
            ulong min = 1;
            while (max > min)
            {
                ulong mid = (min + max) / 2;
 
                // ?£?????£?????£?????£?????£?????¨?????§?????£?????§?????£????
                int cnt = 1;
                ulong current = 0;
                for (int i = 0; i < pack_num; i++)
                {
                    // ?¨?????§?????£?????\???§?£?????£?????£?????§?????¨???????????£?????¨?¶???£?????£?????£?????\???±??????
                    if (list[i] > mid)
                    {
                        cnt = track_num + 1;
                        break;
                    }
 
                    if (current + list[i] > mid)
                    {
                        // ???¬???£?????£?????£?????£?????£?????£????
                        cnt++;
                        current = list[i];
                    }
                    else { current += list[i]; }
                }
                // ?¨?????§?????£?????§?????£?????£?????£?????\?????\????
                if (cnt <= track_num) { max = mid; }
                else { min = mid + 1; }
            }
            Console.WriteLine(max);
        }
    }
}

Measured memory_bytes: 10860
n, m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]

def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

l = []
pre = -1
for x in a:
    l.append(Fib(x-pre-1 +1))
    pre = x

l.append(Fib(n-pre +1))

if l.count(0) > 0:
    print(0)
    exit()

res = 1
for x in l:
    res *= x

print(res % 1000000007)

Measured memory_bytes: 55384
import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.Scanner;

import javax.swing.plaf.synth.SynthSeparatorUI;

public class Main {
 
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner sc = new Scanner(file);
		
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();
		if(A % 2 != 0 && B % 2 != 0) System.out.println("Yes");
		else System.out.println("No");
	}
}

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


signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout << fixed << setprecision(20);

    string s;
    cin>>s;
    int n=s.size();
    int cnt[26]={};
    for(int i=0;i<n;i++){
        cnt[s[i]-'a']++;
    }
    int odd=0;
    for(int i=0;i<26;i++){
        if(cnt[i]%2)odd++;
    }
    cout << odd/2 << endl;
    return 0;
}


Measured memory_bytes: 3224
import sys
from math import *

sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    en = []
    n0 = n
    for _ in range(n0):
        x, y = map(int, input().split())
        if (x, y) == (0, 0):
            n -= 1
            continue
        en.append([atan2(y, x), x, y])
    en.sort()
#    print(en)

    ans = 0
    for l in range(n):
        sx = sy = 0
        arg_l = en[l][0]
        r = l
        for _ in range(n):
            if (en[r][0] - arg_l) % (2 * pi) > pi: break
            sx += en[r][1]
            sy += en[r][2]
            ans = max(ans, (sx ** 2 + sy ** 2))
            r = (r + 1) % n
    print(ans ** 0.5)

main()


Measured memory_bytes: 3188
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

ans = 1
num_color = [-1, -1, -1]
for a in A:
  ans = (ans * num_color.count(a-1)) % MOD
  try:
    num_color[num_color.index(a-1)] = a
  except:
    print(0)
    quit()

print(ans)

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

int main(){
 int N,T,A;
 cin >> N >> T >> A;
 int H;
 int ans = 0;
 double M = 999999;
 for(int i =1 ; i <= N; i++){
   cin >> H;
   double average;
   average = T - H * 0.006;
   double sa;
   sa = abs(average - A);
   if(sa < M){
     M = sa;
     ans = i;
   }     
 }
 cout << ans << endl;


}

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

const int maxn = 1e5 + 10;

using namespace std;

int n, root = -1;
vector<int> v[maxn];

int dfs(int son, int fa)
{
    int ans = 0, flag = 0;
    for(int i = 0; i < v[son].size(); i++)
    {
        if(v[son][i]==fa)
            continue;
        int res = dfs(v[son][i], son);//判断是否为一条链
        if(res==0 && flag==1)
        {
            ans++;
        }
        if(res==0 && flag==0)
        {
            flag = 1;
        }
        ans += res;
    }
    return ans;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n-1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 0; i < n; i++)
    {
        if(v[i].size() > 2)
        {
            root = i;
            break;
        }
    }
    if(root==-1)
    {
        puts("1");
    }
    else
    {
        printf("%d\n", dfs(root, -1));
    }
    return 0;
}


Measured memory_bytes: 9984
import sys,heapq
n=int(sys.stdin.readline())
a=[int(e) for e in sys.stdin.readline().split()]
r=[]
x=[]
y=[]
for i in range(1,n+1):
	heapq.heappush(x,a[i-1])
	heapq.heappush(y,a[n-i])
	while x and y and x[0]==y[0]:
		heapq.heappop(x)
		heapq.heappop(y)
	if not x and not y: r.append(i)
print(' '.join(str(e) for e in r))


Measured memory_bytes: 17348