akhauriyash/Code-Regression huggingface dataset:
#pragma warning(disable:4996)
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

#define lson root<<1
#define rson root<<1|1
#define mid (l+r)>>1

#define mem(arr, in) memset(arr, in, sizeof(arr))
using namespace std;

const int maxn = 4000005;

int n;
bitset<maxn> bs;

int main()
{
	while (cin >> n) {
		int res = 0;

		bs[0] = 1;
		for (int i = 1; i <= n; i++) {
			int tp;
			cin >> tp;
			res += tp;
			bs |= bs << tp;
		}

		int m = (res + 1) / 2;
		for (int i = m; i <= res; i++) if (bs[i]) {
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 1664
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cmath>
#define ll long long
using namespace std;
const int maxn=200000+20;
int a[maxn];
ll pre[maxn];
ll nxt[maxn];
bool cmp(int a,int b)
{
	return a>b;
}
ll min(ll a,ll b)
{
	return a<b?a:b;
}
int main()
{
	/*ll g=200000000000000;
	cout<<g<<endl;*/
	int n,m;
	scanf("%d",&n);
	ll sum=0;
	pre[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		pre[i]=pre[i-1]+a[i];
		sum+=a[i];
	}
	
	for(int i=1;i<n;i++)
	{
		nxt[i]=sum-pre[i];
	}
	ll ans=abs(pre[1]-nxt[1]);
	//for(int i=1;i<=n;i++) cout<<pre[i]<<" "<<nxt[i]<<endl;
	for(int i=2;i<n;i++)
	{
		ll t=abs(nxt[i]-pre[i]);
		ans=min(ans,t);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define MOD ((int)1e9+7)
#define N ((int)2e5+123)
void reads(string& x){ char kk[N]; scanf("%s",kk); x = kk;}

int ans, n;
string s;
void solve(){
    scanf("%d", &n);
    n = n%1000;
    if(n)n = 1000-n;
    printf("%d\n", n);
}

int main(){
    ios_base::sync_with_stdio(0);
    int t = 1; //scanf("%d",&t);
    for(int caso=1;caso<=t;caso++){
        solve();
    }
}

Measured memory_bytes: 3816
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



int main()
	
{	
	int n;
	long int a;
	long int m = 2000000, M = -2000000, s = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a;
		m = min(m, a);
		M = max(M, a);
		s += a;
	}

	cout << m << " " << M << " " << s << endl;

	return 0;
}



Measured memory_bytes: 3088
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

    class Program
    {
        static void Main(string[] args)
        {
            int num = int.Parse(Console.ReadLine());
            string strInput = Console.ReadLine();
            string[] strInputArray = strInput.Split(' ');
            int[] inputArray = Array.ConvertAll<string, int>(strInputArray, delegate(string value) { return int.Parse(value); });
            Array.Reverse(inputArray);
            string output = string.Join(" ", inputArray);

            Console.WriteLine(output);
            Console.ReadLine();
        }
    }


Measured memory_bytes: 16028
program prob1
    implicit none
    integer::n
    read(*,*) n
    if(mod(n/10,111) == 0 .or. mod(n,1111) == 0 .or. mod(n-n/1000*1000,111) == 0) then
        write(*,'(a)') "Yes"
    else
        write(*,'(a)') "No"
    end if
    stop
end program

Measured memory_bytes: 2932
use proconio::input;
use std::cmp::min;
 
fn main() {
  input! {
    n: usize,
    w: usize,
    vals: [(usize, usize);n]
  }
 
  let mw = 100_001;
  let mut dp: Vec<Vec<usize>> = vec![vec![1<<60;mw];n+1];
  dp[0][0] = 0;
  
  for i in 0..n {
    for ii in 0..mw {
      let (weight, value) = vals[i];
      if value <= ii {
        dp[i+1][ii] = min(dp[i][ii-value] + weight, dp[i+1][ii]);
      }
      dp[i+1][ii] = min(dp[i][ii], dp[i+1][ii]);
    }
  }
  let mut max = 0;
  for i in 0..mw {
    if dp[n][i] <= w {
      max = i;
    }
  }
  println!("{}", max);
}

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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

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

  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }

  sort(a.begin(), a.end());
  int count = 0;

  for (int i = 0; i < n; i++) {
    x -= a.at(i);

    if (x < 0) {
      break;
    }
    count++;

    /* if (x >= 0) { */
    /*   count++; */
    /* } */
  }

  if (x > 0) {
    count--;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python
def solve():
    N = input()
    a = input().split()
    a.sort()
    n = 0
    for i in range (0, len(a) - 1):
        n += int(a[i+1]) - int(a[i])
    print(n)


if __name__ == '__main__':
    solve()


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


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

    for(int i = 1; i < 10; i++){
        for(int j = 1; j < 10; j++){
            if(i * j == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;

    return 0;
}


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

int main(){
while(1){
	int a,b,n,x,y,dp[18][18];
	bool c[18][18];
	for(int i=0;i<18;i++)for(int j=0;j<18;j++){dp[i][j]=0; c[i][j]=true;}
	scanf("%d%d",&a,&b);
if(a==0&&b==0)break;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d",&x,&y);
		c[x][y]=false;
	}
	dp[1][1]=1;
	for(int i=1;i<a+1;i++)for(int j=1;j<b+1;j++){
		if(c[i][j]&&!(i==1&&j==1)){
			dp[i][j]=dp[i-1][j]+dp[i][j-1];
		}
	}
	printf("%d\n",dp[a][b]);
}
}

Measured memory_bytes: 1172
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,l;
  cin>>n>>l;
  vector<string> v(n);
  for(int i=0;i<n;i++) cin>>v[i];
  sort(v.begin(),v.end());
  for(int i=0;i<n;i++) cout<<v[i];
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repR(i, n) for(int i = (n) - 1; i > -1; i--)
#define rep1(i, n) for(int i = 1; i < (int)(n + 1); i++)
#define rep1R(i, n) for(int i = (n); i > 0; i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main() {
  int N; cin >> N;
  for (int n = 0; 4 * n <= N; n++) {
    if ((N  - 4 * n) % 7 == 0) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
  
int main(void){
    int k;
    cin >> k;
    string s;
    cin >> s;
    

    if(s.size() <= k) {
        cout << s << endl;
    } else {
        for(int i=0; i<k; i++) {
            cout << s[i];
        }
        cout << "..." << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  re0 x=0,f=1;rec c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
inline void read(rel &x){
  x=0;re0 f=1;rec c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  x=f?x:-x;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return pc(48);
  if (x<0) x=-x,pc('-');
  re0 bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  }
inline char fuhao(){
  rec c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;

int main(){
string a,b;
cin>>a>>b;
for (re0 i=0;i<=999;++i){
  if (i*i==stoi(a+b)) return puts("Yes"),0; 
  }puts("No");
}

Measured memory_bytes: 256
N = int(input())


info = [[0,0,0] for i in range(N)]

for n in range(N):
    info[n][0],info[n][1],info[n][2] = map(int,input().split())

info.sort(key=lambda x:x[2],reverse=True)
for cx in range(101):
    for cy in range(101):
        cnt = 1
        H = info[0][2] + abs(info[0][0]-cx) + abs(info[0][1]-cy)
        for n in range(1,N):
            cnt += 1 
            if info[n][2] != max(H-abs(info[n][0]-cx)-abs(info[n][1]-cy),0):
                break
            if cnt == N:
                print(cx,cy,H)
                exit()

Measured memory_bytes: 3064
#include <iostream>
#include <string>
using namespace std;
int main(){
  int ans,A,B,C,D,AB,CD;
  cin >> A >> B >> C >> D;
  AB = A * B;
  CD = C * D;
  if (AB < CD){
    ans = CD;
  }else if (CD <= AB){
    ans = AB;
  }
  cout << ans << endl;
}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int N; cin >> N;
    vector<int> p(N); REP(i,N) cin >> p[i];
    sort(ALL(p));

    int ans = 0;
    REP(i,N){
        if(i==N-1){
            ans += p[i]/2;
        }else{
            ans += p[i];
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

  int n;
  cin >> n;
  vector<int> t(n);
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
  }
  int m;
  cin >> m;
  vector<int> p(m), x(m);
  for (int i = 0; i < m; ++i) {
    cin >> p[i] >> x[i];
  }
  for (int i = 0; i < m; ++i) {
    int sum = 0;
    for (int j = 0; j < n; ++j) {
      if (p[i] == j + 1) {
        sum += x[i];
      } else {
        sum += t[j];
      }
    }
    cout << sum << "\n";
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;    
typedef long double ld;  
#define pb push_back     
using namespace std;


const int N = 555;
int c[N], s[N], f[N];
int n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i = 1; i < n; i++) cin >> c[i] >> s[i] >> f[i];

    for(int i = 1; i <= n; i++){
        int t = 0;
        for(int j = i; j < n; j++){
            if(t <= s[j]){
                t = s[j];
            }
            else{
                if(t % f[j] != 0) t = (t - (t % f[j])) + f[j];
            }

            t += c[j];
        }
        cout << t << endl;
    }	


    return 0;

}


Measured memory_bytes: 256
const input = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');

for (let i = 0; i < input.length; i++) {
    let num = input[i].split(' ').map(Number);
       if (num[0] === 0 && num[1] === 0) {
        break;
    }
    num.sort(function (a, b) {return a - b; });
    console.log(num[0], num[1]);
}



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

int main(){
  int N;
  int a[110];
  cin >> N;
  for (int i = 0; i < N; ++i) cin >> a[i];
  sort(a, a + N, greater<int>()); 
  int Alice = 0;
  int Bob = 0;
  for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) { // Alice のターン
            Alice += a[i];
        }
        else { // Bob のターン
            Bob += a[i];
        }
    }
    cout << Alice - Bob << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<sstream>
using namespace std;
typedef long long ll;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		string sss;
		set<string> ss;
		cin>>sss;
		string s,t,rs,rt;
		for(int i=1;i<sss.size();i++)
		{
			s=sss.substr(0,i);
			t=sss.substr(i);
			rt=t;
			rs=s;
			reverse(rt.begin(),rt.end());
			reverse(rs.begin(),rs.end());
			ss.insert(t+s);
			ss.insert(t+rs);
			ss.insert(rt+s);
			ss.insert(rt+rs);
			ss.insert(rs+rt);
			ss.insert(rs+t);
			ss.insert(s+rt);
			ss.insert(rs+rt);
			ss.insert(s+t);
		}
	cout<<ss.size()<<endl;
	}
	return 0;
}

Measured memory_bytes: 1296
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    if (Integer.valueOf(S.substring(0, 4)) <= 2019) {
      if (Integer.valueOf(S.substring(5, 6)) != 0) {
        System.out.println("TBD");
        return;
      }
      if (Integer.valueOf(S.substring(6, 7)) < 5 && (int) Integer.valueOf(S.substring(8, 10)) < 31) {
        System.out.println("Heisei");
        return;
      }
    }
    System.out.println("TBD");
  }
}

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

using namespace std;
vector<int>v;
int n,k;
bool chk(int mn){
    int tmk=0;
    for(int i=0;i<n;i++){
        tmk+=v[i]/mn+!!(v[i]%mn)-1;
    }

    return tmk<=k;
}
int main()
{///{}
    cin>>n>>k;
    v.resize(n);
    for(int i=0;i<n;i++)
        cin>>v[i];

    int l=1,r=1e9+5;
    int ans;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(chk(mid)){
            r=mid-1;
            ans=mid;
        }else{
            l=mid+1;
        }

    }

    cout<<ans<<'\n';

    return 0;
}


Measured memory_bytes: 3932
#include <bits/stdc++.h>
using namespace std;
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


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

  ll sum = 0;
  rep(i, n) sum += a[i];

  ll nn = n*(n+1)/2;

  if (sum % nn != 0) {
    cout << "NO" << endl;
    return 0;
  }

  ll k = sum / nn;

  ll bsum = 0;  
  rep(i, n) {
    int i0 = (i-1+n)%n;
    ll b = 0;
    b = a[i0] - a[i] + k;
    if (b < 0 || b % n != 0) {
      cout << "NO" << endl;
      return 0;
    }
    b /= n;
    bsum += b;
  }

  if (bsum == k) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################

signed main(){
	//a < b < d,a < c
	int n,a,b,c,d;cin >> n >> a >> b >> c >> d;
	a--;b--;c--;d--;
	string s;cin >> s;
	//a c b  d
	auto check = [&](int l,int r){
		vector<int> dp(r-l+5);
		dp[0] = 1;
		for(int i = l;i < r;i++){
			if(s[i] == '#')continue;
			dp[i-l+1] |= dp[i-l];
			dp[i-l+2] |= dp[i-l];
		}
		//trace(l,r,dp);
		return dp[r-l];

	};
	auto ok = [&](int l,int r){
		r++;
		for(int i = l,j;i < r;i = j){
			for(;i < r&& s[i] == '#';i++);
			if(i == r)break;
			for(j = i+1;j < r&& s[j] != '#';j++);
			int len = j-i;
			//trace(i,j,len);
			if(len >= 3){
				return true;
			}
		}
		
		return false;
	};
	if(a < c && c < b){
		if(check(a,c)&& check(b,d))cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	//a b c d
	else if(b < c && c < d){
		if(check(a,c)&& check(b,d))cout << "Yes" << endl;
		else cout << "No" <<endl;

	}
	//a b d c
	else{
		if(check(b,d)&&check(a,c)&&ok(b-1,d+1))cout << "Yes" << endl;
		else cout << "No" << endl;

	}
	trace(ok(0,n-1));

	
	
	return 0;
}

Measured memory_bytes: 4980
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let (n, k): (usize, usize) = read();

    let l = k*2;
    let mut white_tbl = vec![vec![0; l]; l];
    let mut black_tbl = vec![vec![0; l]; l];

    for _i in 0..n {
        let (x, y, c): (usize, usize, String) = read();
        if c.chars().nth(0).unwrap() == 'B' {
            black_tbl[x%l][y%l] += 1;
        } else {
            white_tbl[x%l][y%l] += 1;
        }
    }

    let mut white_tbl_sum = vec![vec![0; l+1]; l+1];
    let mut black_tbl_sum = vec![vec![0; l+1]; l+1];

    for i in 1..l+1 {
        for j in 1..l+1 {
            black_tbl_sum[i][j] = black_tbl[i-1][j-1] - black_tbl_sum[i-1][j-1] + black_tbl_sum[i-1][j] + black_tbl_sum[i][j-1];
            white_tbl_sum[i][j] = white_tbl[i-1][j-1] - white_tbl_sum[i-1][j-1] + white_tbl_sum[i-1][j] + white_tbl_sum[i][j-1];
        }
    }

    let mut best = 0;
    for i in 0..l {
        for j in 0..l {
            best = max(best, solve(i, j, &black_tbl_sum, &white_tbl_sum));
        }
    }
    println!("{}", best);
}

fn solve(i: usize, j: usize, black_tbl: &Vec<Vec<i32>>, white_tbl: &Vec<Vec<i32>>) -> i32 {
    let l = black_tbl.len()-1;
    let k = l / 2;

    square_sum(i, j, k, black_tbl) + square_sum((i+k)%l, (j+k)%l, k, black_tbl)
     + square_sum((i+k)%l, j, k, white_tbl) + square_sum(i, (j+k)%l, k, white_tbl)
}

fn split(fi: usize, k: usize) -> Vec<(usize, usize)> {
    let l = k*2;
    let mut a = vec![];
    let ti = min(fi+k, l);
    a.push((fi, ti));
    if fi+k > l {
        a.push((0, fi+k-l));
    }
    a
}

fn square_sum(fi: usize, fj: usize, k: usize, tbl: &Vec<Vec<i32>>) -> i32 {
    let mut ret = 0;
    for x in split(fi, k) {
        for y in split(fj, k) {
            ret += rect_sum(x.0, y.0, x.1, y.1, tbl);
        }
    }
    ret
}

fn rect_sum(fi: usize, fj: usize, ti: usize, tj: usize, tbl: &Vec<Vec<i32>>) -> i32 {
    tbl[ti][tj] - tbl[fi][tj] - tbl[ti][fj] + tbl[fi][fj]
}


Measured memory_bytes: 69884
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define EPS 1e-9
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;

#define MAX_N 1001
#define MAX_M 10001
#define MAX_R 1001
#define MAX_Q 50

int N, M;
int r;
int q;

const int GETA = 540;

vector<int> ans_list;

int main(){

  while(true){

    cin >> N >> M;
    if(N == 0)
      break;

    int L[MAX_M];
    int PC[MAX_N][1000];
    memset(PC,0,sizeof(PC));

    cin >> r;

    for(int i = 0; i < r; i++){
      int t,n,m,s;
      cin >> t >> n >> m >> s;
      t -= GETA;
      if(s == 1)
	L[n] = t;
      else{
	for(int i = L[n]; i < t; i++){
	  PC[n][i] = m;
	}
      }
    }

    cin >> q;
    for(int i = 0; i < q; i++){
      int ts, te, m;
      cin >> ts >> te >> m;
      int ans = 0;
      ts -= GETA;
      te -= GETA;
      //cout << "******  " << i << endl;
      for(int t = ts; t < te; t++){
	for(int j = 1; j <= N; j++){
	  if(PC[j][t] == m){
	    //cout << j << " " << t << endl;
	    ans++;
	    break;
	  }
	}
      }
    
      ans_list.push_back(ans);
    }

  }

  for(int i = 0; i < ans_list.size(); i++){
    cout << ans_list[i] << endl;
  }
  
  
  
  return 0;
  
}

Measured memory_bytes: 5148
#include <bits/stdc++.h>
#define int long long
#define double long double
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,sse")
using namespace std;

vector<int> polina(1e7 + 1);
vector<int> f(1e7 + 1);
const int INF = 1e8;

int get(int x, int base) {
    int now = 1;
    int cnt = 0;
    while (now < INF) {
        if (now == x) {
            return cnt;
        }
        now *= base;
        cnt++;
    }
    return -1;
}

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

    for (int i = 2; i <= 1e7; i++) {
        if (polina[i] == 0) {
            for (int j = i; j <= 1e7; j += i) {
                polina[j] = i;
            }
        }
    }
    f[1] = 1;
    for (int i = 2; i <= 1e7; i++) {
        if (i == polina[i]) {
            f[i] = 2;
        } else {
            int p = polina[i];
            int a = 1;
            int b = i;
            int s = 0;
            while (b % p == 0) {
                a *= p;
                b /= p;
                s++;
            }
            if (b == 1) {
                f[i] = s + 1;
            } else {
                f[i] = f[a] + f[b] + (f[a] - 1) * (f[b] - 1) - 1;
            }
        }
    }

    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += (i * f[i]);
    }
    cout << res << '\n';

    fflush(stdout);
    return 0;
}


Measured memory_bytes: 159340
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    c = input()
    boin = {'a', 'e', 'i', 'o', 'u'}

    if c in boin:
        ans = 'vowel'
    else:
        ans = 'consonant'

    print(ans)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 3060
<?php

//1行入力
$numOfQ = trim(fgets(STDIN));
$time = trim(fgets(STDIN));
//不要な改行コードを取り除く
$time = str_replace(array("\r\n","\r","\n"), '', $time);
//スペースで分解して配列に格納
$array = explode(" ", $time);
$numOfDrink = trim(fgets(STDIN));

for($i = 0; $i < $numOfDrink; $i++){
  $sum = 0;
  fscanf(STDIN, "%d %d", $a, $b);
  for($j = 0; $j < count($array); $j++){
    if(($a - 1 )==$j){
      $sum += $b;
    }else{
      $sum += $array[$j];
    }
  }
  echo $sum."\n";
}

?>

Measured memory_bytes: 4728
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

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

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>
#define vll vector<vl>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

vector<int> i2g;          // i2g[i] := アイテム i の所属するグループの番号(find)
vector<vector<int>> g2i;  // g2i[g] := グループ g に所属するアイテムたち

void union_init(int n) {
  i2g.resize(n);
  g2i.resize(n);
  for (int i = 0; i < n; ++i) {
    // 最初はアイテム i はグループ i に所属
    i2g[i] = i;
    g2i[i].assign(1, i);
  }
}

int find(int i){
  return i2g[i];
}

// アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする
void merge(int ia, int ib) {
  if(i2g[ia]==i2g[ib])return;
  // ia の所属するグループが ib の所属するグループより小さくならないようにする
  if (g2i[i2g[ia]].size() < g2i[i2g[ib]].size()) {
    swap(ia, ib);
  }
  int ga = i2g[ia], gb = i2g[ib];
  // グループ gb に所属する全てのアイテムをグループ ga に移す
  for (int j : g2i[gb]) i2g[j] = ga;
  g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end());
  g2i[gb].clear();
}

// アイテム ia とアイテム ib は同じグループに所属しているか？
bool is_same_group(int ia, int ib) {
  return i2g[ia] == i2g[ib];
}


int main(){
	LL n,m;
    cin>>n>>m;
    vl a(m),b(m);
    vi used(n,0);
    union_init(n);
    
    FOR(i,0,m){
        cin>>a[i]>>b[i];
        a[i]--;b[i]--;
        if(!is_same_group(a[i],b[i])){
            merge(a[i],b[i]);
        }
    }
    int ans=0;
    FOR(i,0,n){
        int g=i2g[i];
        if(used[g]){

        }else{
            ans++;
        }
        used[g]=1;
    }
    cout<<ans-1<<endl;
    
    
}


Measured memory_bytes: 12148
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007LL;
int main(){
    long long n,m;
    cin >> n >> m;
    bool fl = false;
    long long ans;
    vector<long long> yakusuu;
    for(int i = 1;i<=int(sqrt(m));i++){
        if(m%i == 0){
            yakusuu.push_back(i);
            yakusuu.push_back(m/i);
        }
    }
    sort(yakusuu.begin(),yakusuu.end(),greater<long long>());
    rep(i,yakusuu.size()){
        if(m/yakusuu[i] >= n){
            ans = yakusuu[i];
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
//#include <windows.h>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VVC = vector<VC>;
using VS = vector<string>;
using VVS = vector<VS>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
const int INF = 2e9;
const LL MOD = 1e9 + 7;

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

void END(){cout << 1 << endl; exit(0);}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<PII> data(n);
  REP(i, n)
  {
    int x, l;
    cin >> x >> l;
    data[i] = {x+l, x-l};
  }
  SORT(data);
  int ans = 0;
  int ll = -INF;
  REP(i, n)
  {
    int right = data[i].first, left = data[i].second;
    if (left >= ll)
    {
      ans++;
      ll = right;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(int (i)=(n)-1; (i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

string N;
int K;
int dp[101][2][4];

int rec(int k = 0, bool is = true, int sum = 0) {
	if (K < sum)return 0;
	if (k == N.size())return sum == K;

	int x = N[k] - '0';
	int r = (is ? x : 9);

	int& res = dp[k][is][sum];
	if (~res)return res;
	res = 0;

	rep(i, r + 1) {
		res+=rec(k + 1, is && i == x, sum + (i!=0));
	}
	return res;
}

int main() {
	init();

	cin >> N >> K;
	memset(dp, -1, sizeof(dp));
	cout << rec() << "\n";

	return 0;
}

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

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<double> point;
#define F first
#define S second



int main()
{
	#ifdef DGC
		//freopen("a.in", "r", stdin);
		//freopen("b.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

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

	vector<vector<int>> p(n, vector<int>(n));
	vector<vector<int>> e(n, vector<int>(n));
	for (int i = 0; i < n; ++i)
	{
		function<void(int, int)> dfs = [&](int u, int a)
		{
			for (auto v : adj[u])
				if (v.F != a)
				{
					dfs(v.F, u);
					e[i][v.F] = v.S;
					p[i][v.F] = u;
				}
		};
		p[i][i] = e[i][i] = -1;
		dfs(i, -1);
	}

	int m;
	cin >> m;
	vector<ll> r(m);
	for (auto &i : r)
	{
		int u, v;
		cin >> u >> v;
		--u, --v;
		while (v != u)
		{
			i |= 1LL<<e[u][v];
			v = p[u][v];
		}
	}

	ll ans = 0;
	for (int i = 0; i < 1<<m; ++i)
	{
		ll mp = 0;
		for (int j = 0; j < m; ++j)
			if (i >> j & 1)
				mp |= r[j];
		ans += (1LL << (n-1 - __builtin_popcountll(mp))) * ((__builtin_popcount(i)&1) ? -1 : +1);
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import itertools as it
import numpy as np
from collections import Counter
d = {}
def _gcd(a,b):
    a, b = max(a,b), min(a,b)
    while b:
        if d.get((a, b), False):
            return d[(a, b)]
        else:
            a, b = b, a%b

    d[(a, b)] = a
    return a

# def _gcd(a,b):
#     a, b = max(a,b), min(a,b)
#     if b == 0:
#         d[(a, b)] = a
#         return a
#     elif d.get((a, b), False):
#         return d[(a, b)]
#     else:
#         ans = _gcd(b, a%b)
#         d[(a, b)] = ans
#         return ans

def gcd(a,b,c):
    return _gcd(a, _gcd(b,c))

def solve(K: int):
    # val_arr = np.zeros(201,201)
    # cnt_arr = np.zeros(201,201)
    r = range(1, K+1)

    arr = []
    for (a,b) in it.product(r,r):
        arr.append(_gcd(a,b))
        # val_arr[a,b] += _gcd(a,b)
        # cnt_arr[a,b] += 1

    ans = 0
    cnt_dict = Counter(arr)
    for i in r:
        for key, cnt in cnt_dict.items():
            ans += _gcd(i,key)*cnt

    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 27472
import java.util.*;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        int n = Integer.parseInt(a.split(" ")[0]);
        int k = Integer.parseInt(a.split(" ")[1]);

        String s = sc.nextLine();
        char[] ans = new char[n];
        for (int i = 0; i < n; i++) {
            if (k == i + 1) {
                ans[i] = s.toLowerCase().charAt(i);
            } else {
                ans[i] = s.charAt(i);
            }
        }

        System.out.println(ans);

        return;
    }
}


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

using namespace std;

int main(){
    int N = 0;
    int check;
    vector<int> v(10000);
    for(int i=0;i<10000;i++){
        cin >> check;
        if(check == 0)
            break;
        v.at(i) = check;
        N++;
    }
    for(int i=0;i<N;i++){
        cout << "Case " << i+1 << ": " << v.at(i) << endl;;
    }
    return 0;
}


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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    ll n, k; cin >> n >> k;
    vector<ll> flag(n, 0), dist1(n, -1), dist2(n, -1);
    vector<vector<ll> > tree(n);
    REP(i, 0, n){
        ll a; cin >> a;
        a--;
        tree[i].pb(a);
    }
    ll now = 0;
    ll count = 0;
    flag[0] = 1;
    dist1[0] = 0;
    while(1){
        count++;
        ll next = tree[now][0];
        if(flag[next] == 0){
            dist1[next] = count;
        }else if(flag[next] == 1){
            dist2[next] = count;
        }else{
            break;
        }
        flag[next]++;
        now = next;
    }
    vector<ll> check(n, -1);
    ll kk;
    REP(i, 0, n){
        if(flag[i] == 2){
            kk = dist2[i] - dist1[i];
        }
    }
    REP(i, 0, n){
        if(flag[i] == 1){
            if( k   ==  dist1[i] ){
                cout << i+1 << endl;
                return 0;
            }
        }
    }
    REP(i, 0, n){
        if(flag[i] == 2){
            if( (k - dist1[i]) % kk   ==  0 ){
                cout << i+1 << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 20368
//abc159_b.cpp
//Sat Apr 18 22:45:52 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

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

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

	for (int i=0;i<(s.length()-1)/2;i++){
		if (s[i]!=s[s.length()-1-i]){
			cout << "No" << endl;
			return 0;
		}
	}

	int start = 0;
	int end = (s.length()-1)/2-1;
	while (start<end){
		if (s[start]!=s[end]){
			cout << "No" << endl;
			return 0;
		}
		start++;
		end--;
	}

	start = (s.length()+3)/2-1;
	end = s.length()-1;
	while (start<end){
		if (s[start]!=s[end]){
			cout << "No" << endl;
			return 0;
		}
		start++;
		end--;
	}


	cout << "Yes" << endl;
//	printf("%.4f\n",ans);
}

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

using namespace std;
typedef long long ll;

const int N = int(1e8) + 7;

void init(){

}

void solve(){
    int a;
    scanf("%d", &a);
    int b = a%100;
    a = a/100;
    if(a > 0 && a <= 12 && b > 0 && b <= 12)
        printf("AMBIGUOUS\n");
    else if(a > 0 && a <= 12)
        printf("MMYY\n");
    else if(b > 0 && b <= 12)
        printf("YYMM\n");
    else
        printf("NA\n");
}

const bool mtc = false;

int main(){
    int t;
    if(mtc){
        scanf("%d", &t);
        while(t--) solve();
    }
    else solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

int nCr(int n, int r)
{
	if(n<r) return 0;
	if(r==0 || n==r) return 1;
	return (n%2>=r%2)*nCr(n/2,r/2);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, ans=0;
	bool chk=false;
	string s;
	cin>>N>>s;
	for(auto &c: s) if(--c=='1') chk=true;
	for(int i=0;i<N;i++) {
		if(chk) {
			if((s[i]-'0')&1) ans^=nCr(N-1,i);
		}
		else if(s[i]-'0') ans^=nCr(N-1,i);
	}
	cout<<(chk ? ans:2*ans)<<'\n';
	return 0;
}

Measured memory_bytes: 1948
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;

int main(){
	int h, w, s;
	cin >> h >> w;
  	int a[h+1][w+1];
  	for (int i = 0; i < h; i++){
      s = 0;
      for (int j = 0; j < w; j++){
    	cin >> a[i][j];
        s += a[i][j];
        cout << a[i][j] << " ";
      }
      a[i][w] = s;
      cout << s << endl;
    }
  	for (int j = 0; j < w+1; j++){
      s = 0;
      for (int i = 0; i < h; i++){
        s += a[i][j];
      }
      cout << s;
      if (j != w) cout << " ";
      else cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long Q,H,S,N;long double D;cin>>Q>>H>>S>>D>>N;
  vector<long double>YASU(4);
  YASU[0]=Q*4;YASU[1]=H*2;YASU[2]=S;YASU[3]=D/2;
  long double K=D/2;
  sort(YASU.begin(),YASU.end());
  if(YASU[0]==K){
    if(N%2==0){
      cout<<(long long)(D*N/2)<<endl;
    }
    else{
      cout<<(long long)(D*(N-1)/2+YASU[1])<<endl;
    }
  }
  else{
    cout<<(long long)(YASU[0]*N)<<endl;
  }
}

Measured memory_bytes: 3700
#include<iostream>
#include<climits>
#include<math.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int mini = INT_MAX;
    int maxi = INT_MIN;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        mini = mini<a[i]?mini:a[i];
        maxi = maxi>a[i]?maxi:a[i];
    }
    cout<<abs(mini-maxi)<<"\n";
    
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef priority_queue<int, vector<int>, greater<int> > min_p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int mon[20]={31,28,31,30,31,30,31,31,30,31,30,31};
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
inline int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
int f(int x){
  if (x==0) return 0;
  return f(x%__builtin_popcount(x))+1;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int	n;
	cin>>n;
	string s;
	cin>>s;
	vector<int>x(n);
	rep(i,n)x[i]=s[i]-'0';
	int pc=0;
	rep(i,n)pc+=x[i];
	vector<int>ans(n,0);
	rep(b,2){
		int npc=pc;
		if(b==0)
			npc++;
		else
			npc--;
		if(npc<=0)continue;
		int r0=0;
		rep(i,n){
			r0=(r0*2)%npc;
			r0+=x[i];
		}
		int k=1;
		for(int i=n-1;i>=0;i--){
			if(x[i]==b){
				int r=r0;
				if(b==0)
					r=(r+k)%npc;
				else
					r=(r-k+npc)%npc;
				ans[i]=f(r)+1;
			}
			k=(k*2)%npc;
		}
	}
	rep(i,n)cout<<ans[i]<<endl;
	return 0;
}


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

int main() {
  int N, K, v, ans = 0;
  cin >> N >> K;
  vector<int> p;
  for (int i=0; i<N; i++) {
    cin >> v;
    p.push_back(v);
  }
  sort(p.begin(), p.end());
  for (int i=0; i<K; i++) {
    ans += p[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
double p[3005];
double dp[3005][3005];
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>p[i];
    }
    dp[0][0] = 1;

    for(int i=1;i<=n;i++) {
        dp[i][0] = dp[i-1][0] * (1-p[i]);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=i;j++) {
            double x = 1-p[i];
            dp[i][j] = dp[i-1][j] * x + dp[i-1][j-1] * p[i];
        }
    }
    double sum = 0.0;
    for(int i=n/2+1;i<=n;i++) {
        sum+=dp[n][i];
    }
    cout<<fixed<<setprecision(10)<<sum<<endl;
}


Measured memory_bytes: 68992
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
		
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		String s=sc.next();
		long k=sc.nextLong();
		int i;
		int l=s.length();
		int ans=1;
		
		for(i=0;i<l;i++) {
			if(k==0) {
				break;
						
			}
			if(ans==1&&s.charAt(i)!='1') {
				ans=s.charAt(i)-'0';
				
			}
			k--;
		}
		System.out.println(ans);
	}

	
	
//----------------------------------------------------------
	static int l_min(int[] a) {
		Arrays.sort(a);
		return a[0];
	}
	static int l_max(int[] a) {
		int l=a.length;
		Arrays.sort(a);
		return a[l-1];
	}
	
	public static PrintWriter out;

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}
	

}


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

int main() {
	

	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);

	A[0] = 0;
	B[0] = 0;

	for (int i = 1; i < N; i++)
	{
		cin >> A[i];
		B[i] = 0;
	}
	
	sort(A.begin(), A.end());

	


	for (int i = 0; i < N; i++)
	{
		if (A[i - 1] != A[i])
		{
			B[A[i]] = 1;
		}
	}

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

		if (A[i] == A[i + 1])
		{
			B[A[i]] += 1;
		}
	}

	
	

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

	}
	cout << 0 << endl;

	return 0;
}




Measured memory_bytes: 4824
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<math.h>
#include<bitset>
#include<random>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(17)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<char,P> Q;
//ll longinf=1ll<<60;
int inf=1<<29;
ll longinf=(1ll<<60);

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

int N;
int M;
int ans;
vector<int> nxt[100000];

ll dp[100001];

ll dfs(ll x){
    if(dp[x]==longinf) dp[x]=0;
    for(auto y:nxt[x]){
        if(dp[y]!=longinf){
            dp[x]=max(dp[x],dp[y]+1);
        }
        else{
            dp[x]=max(dp[x],dfs(y)+1);
        }
    }
    return dp[x];
}


signed main(){
    cin>>N>>M;
    rep0(i,M){
        int x,y;
        cin>>x>>y;
        x--,y--;
        nxt[x].push_back(y);
    }
    fill(dp,dp+N,longinf);
    rep0(i,N) dfs(i);
    ll ans=0;
    rep0(i,N){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 7808
#include <bits/stdc++.h>
using namespace std;
inline void chmax (int& a, int b) {
  if (a < b) a = b;
}
int n, m;
vector<int> a;
bool ck (int k) {
  int c = k + n;
  for (int i = 2 * k; i < c; i++) {
    int j = 2 * c - i - 1;
    if (a[i] + a[j] < m) return false;
  }
  return true;
}
int cal (int k) {
  int ret = 0;
  for (int i = 0; i < k; i++) {
    int j = 2 * k - i - 1;
    chmax(ret, a[i] + a[j]);
  }
  return ret;
}
int dal (int k) {
  int ret = 0;
  int c = n + k;
  for (int i = 2 * k; i < c; i++) {
    int j = 2 * c - i - 1;
    chmax(ret, a[i] + a[j]);
  }
  return ret - m;
}
int main() {
  cin >> n >> m;
  a.resize(2 * n);
  for (int i = 0; i < 2 * n; i++) {
    cin >> a[i];
    a[i] %= m;
  }
  sort(a.begin(), a.end());
  int ng(-1), ok(n);
  while (ok - ng > 1) {
    int md = (ng + ok) >> 1;
    if (ck(md)) {
      ok = md;
    } else {
      ng = md;
    }
  }
  int ret = 0;
  chmax(ret, cal(ok));
  chmax(ret, dal(ok));
  cout << ret << '\n';
  return 0;
}

Measured memory_bytes: 1024