akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;

int P[52];
int B[52];
int T[52];
int solve(int N, int X) {
	if (N == 0)return 1;
	if (X == 1)return 0;
	X--;

	if (X <= T[N - 1]) {
		return solve(N - 1, X);
	}
	X -= T[N - 1];
	
	if (X == 1)return 1 + P[N - 1];
	X--;

	if (X <= T[N - 1]) {
		return 1 + P[N - 1] + solve(N - 1, X);
	}
	X -= T[N - 1];


	return 1 + 2 * P[N - 1];
	
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	P[0] = 1;
	B[0] = 0;
	T[0] = 1;
	for (int i = 1; i < 51; i++) {
		P[i] = 2 * P[i - 1] + 1;
		B[i] = 2 * B[i - 1] + 2;
		T[i] = 2 * T[i - 1] + 3;
	}
	int N, X;
	cin >> N >> X;
	cout << solve(N, X) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
const int MOD(1e9 + 7);
int freq[62][2], n, curr, res;
long long x, p2[62];
int main() {
    DAU
    p2[0] = 1;
    for (int i = 1; i < 62; ++i)
        p2[i] = p2[i - 1] << 1;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        for (int bit = 0; bit < 62; ++bit)
            ++freq[bit][!!(x & p2[bit])];
    }
    for (int bit = 0; bit < 62; ++bit)
        res = (res + (1LL * ((1LL * freq[bit][0] * freq[bit][1]) % MOD) * (p2[bit] % MOD)) % MOD) % MOD;
    cout << res;
    PLEC
}


Measured memory_bytes: 3644
#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int n,m,i,k=1,cnt=0,a[100005];
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    while(a[n]!=a[0])
    {
        for(i=k;i<k+m;i++)
        {   if(i<=n)
              a[i]=a[k];
            else
                break;
        }
        k=k+m-1;
        cnt++;
        if(k>=n)
            break;
    }
    printf("%d",cnt);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, K, Q, A, B[100000];

int main() {
	cin >> N >> K >> Q;
	for (int i = 0; i < N; ++i) {
		B[i] = K - Q;
	}
	while (Q--) {
		cin >> A;
		++B[A - 1];
	}
	for (int i = 0; i < N; ++i) {
		if (B[i] > 0) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
 
using namespace std;

int main(){
    int X;  cin >> X;
    for(int i=1; i<100000; i++) if((i+1)*i/2 >= X){print(i); return 0;}
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define lo long long
using namespace std;
int n,d,A[15][15],say;
int main(){
	scanf("%d %d",&n,&d);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=d;j++) scanf("%d",&A[i][j]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int cev=0;
			for(int k=1;k<=d;k++){
				int t=A[j][k]-A[i][k];
				cev+=t*t;
			}
			int h=sqrt(cev);
			if(h*h==cev){
				say++;
			}
		}
	}
	printf("%d\n",say);
	return 0;
}




Measured memory_bytes: 256
# 入力
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]

# 出力
ans = sum(1 for a in A if sum(x * y for x, y in zip(a, B)) + C > 0)
print(ans)


Measured memory_bytes: 3316
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] p = new int[n];
    for(int i = 0; i < n; i++) {
      p[i] = sc.nextInt();
    }
    Arrays.sort(p);
    int ans = 0;
    for(int i = 0; i < k; i++) {
      ans += p[i];
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 38828
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,f[N],s[N],a[N];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=i;
    while(m--)
    {
        int x,y;scanf("%d%d",&x,&y);
        f[getf(x)]=getf(y);
    }
    for(int i=1;i<=n;i++)
        s[a[i]]=getf(i);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(getf(i)==s[i]) ans++;
    printf("%d\n",ans);
}


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


int main()
{
	string s;
	int  k;
	cin >> s >> k;
	for (int i = 0; i < k; i++) {
		if (s[i] != '1') {
			cout << s[i] << endl;
			return 0;
		}
	}
	cout << 1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <cmath>
#include <numeric>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long LL;

int main() {
  int K;
  cin >> K;
  
  vector<vector<int>> count(10, vector<int>());
  REP(i, 10) { count[i].push_back(i%3 == 0 ? 1 : 0); }
  for(int i=0; i<=18; ++i) {
    count[0].push_back(count[0][i] + count[1][i]);
    count[9].push_back(count[8][i] + count[9][i]);
    for(int j=1; j<=8; ++j){
      count[j].push_back(count[j-1][i] + count[j][i] + count[j+1][i]);
    }
  }
  LL ret = 0;
  for(int keta=1; keta<=18; ++keta) {
    for(int n=1; n<=9; ++n) {
      if(count[n][keta] < K) {
        K -= count[n][keta];
      } else {
        ret = n;
        while(--keta > 0) {
          if(n >= 1 && K <= count[n-1][keta]) {
            --n;
          } else {
            if(n >= 1) {
              K -= count[n-1][keta];
            }
            if(K > count[n][keta]) {
              K -= count[n][keta];
              ++n;
            }
          }
          ret = ret * 10 + n;
        }
        cout << ret << endl;
        return 0;
      }
    }
  }
} 

Measured memory_bytes: 256
n=int(input())
a=[0]*26
S=input()
for i in S:
    a[ord(i)-97]+=1
for _ in range(n-1):
    l=[0]*26
    S=input()
    for i in S:
        l[ord(i)-97]+=1
    for i in range(26):
        a[i]=min(a[i],l[i])
for i in range(26):
    print((chr(i+97)*a[i]),end="")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int n,m,x;
  cin>>n>>m>>x;
  vin a(m);
  rep(i,0,m)cin>>a[i];
  int cnt=0;
  rep(i,0,x){
    rep(j,0,m){
      if(i==a[j]) cnt++; 
    }
  }
  chmin(cnt,m-cnt);
  
  cout<<cnt<<endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int N,A,B[101][2],ans,ev,od;
int main(){
    cin>>N;
    for(int i{};i<N;++i){
        cin>>A;
        if(A%2)B[i][0]=2,B[i][1]=1;
        else B[i][0]=1,B[i][1]=2;
    }
    ev=B[0][0];
    od=B[0][1];
    for(int i{1};i<N;++i){
        ev=ev*(B[i][0]+B[i][1])+B[i][0]*od;
        od=od*B[i][1];
    }
    cout<<ev<<endl;
}


Measured memory_bytes: 256
from operator import itemgetter
n, k = map(int, input().split())
ab = []
A = 0
B = 1
for i in range(n):
    ab.append(list(map(int, input().split())))

ab.sort(key=itemgetter(0))
cnt = 0
ans = 0

for i in range(n):
    cnt += ab[i][B]
    if k <= cnt:
        ans = ab[i][A]
        break

print(ans)

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

#define PB push_back
#define MP make_pair
#define fi first
#define se second

typedef long long LL;

const double EPS=1e-9;
const double PI=acos(-1.0);
const int MAXN=100005;
const LL MOD=1000000007;
const int dx[8]={-1, 0, 1, -1, 1, -1, 0, 1}, dy[8]={-1, -1, -1, 0, 0, 1, 1, 1};

void base(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main(){
	base();
	int n, a, odd=0;
	cin>>n;

	while(n--){
		cin>>a;
		if(a%2){
			odd++;
		}
	}

	if(odd%2){
		cout<<"NO"<<endl;
	}
	else{
		cout<<"YES"<<endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
#define MAX (100005)
#define NIL (-1)

struct Node{
    int p,l,r;
};
Node T[MAX];
int n,D[MAX];
void print(int u){
    int i,c;
    cout<<"node "<<u<<": ";
    cout<<"parent = "<<T[u].p<<", ";
    cout<<"depth = "<<D[u]<<", ";
    if(T[u].p==NIL)cout<<"root, ";
    else if(T[u].l==NIL)cout<<"leaf, ";
    else cout<<"internal node, ";
    cout<<"[";
    for(i=0,c=T[u].l;c!=NIL;i++,c=T[c].r){
        if(i)cout<<", ";
        cout<<c;
    }
    cout<<"]"<<endl;
}
void rec(int u,int p){
    D[u]=p;
    if(T[u].r!=NIL)rec(T[u].r,p);
    if(T[u].l!=NIL)rec(T[u].l,p+1);
}
int main(void){
    int d,v,c,l,r;
    scanf("%d",&n);
    for(int i=0;i<n;i++)T[i].p=T[i].l=T[i].r=NIL;
    for(int j=0;j<n;j++){
        cin>>v>>d;
        for(int i=0;i<d;i++){
            cin>>c;
            if(i==0)T[v].l=c;
            else T[l].r=c;
            l=c;
            T[c].p=v;
        }
    }
    for(int i=0;i<n;i++){
        if(T[i].p==NIL)r=i;
    }
    rec(r,0);
    for(int i=0;i<n;i++)print(i);
    return 0;
}



Measured memory_bytes: 7748
let () =
    let split s =
        let rec loop i cur flag acc =
            if i = String.length s then ( if flag then cur :: acc else acc) else (
                match flag, s.[i] with
                | true,  ' ' -> loop (i + 1) "" false (cur :: acc)
                | false, ' ' -> loop (i + 1) "" false acc
                | true,  v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
                | false, v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
            )
        in
        List.map int_of_string (List.rev (loop 0 "" false []))
    in
    let rec proc left right acc = function
        | [_] -> acc
        | [] -> acc
        | hd :: tl ->  
                let left = left + hd in
                let right = right - hd in
                let acc = min acc (max left right - min left right) in
                proc left right acc tl
    in

    let main () =
        let _ = int_of_string (read_line ()) in
        let a = split (read_line ()) in
        let s = List.fold_left (+) 0 a in
        let r = match a with
        | hd :: tl -> proc hd (s - hd) (max hd (s - hd) - min hd (s - hd)) tl
        | _ -> 0
        in
        Printf.printf "%d\n" r
    in
    main ()

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

int main() {
	int n,a,b,i;
	string s;
	int inout=0,out=0;
	cin>>n>>a>>b;
	cin>>s;
	
	for(i=0;i<n;i++){
		if(s[i]=='a'){
			if(inout<a+b){
				cout<<"Yes"<<endl;
				inout++;
			}
			else{
				cout<<"No"<<endl;
			}
		}
		if(s[i]=='b'){
			if(inout<a+b&&out<b){
				cout<<"Yes"<<endl;
			inout++;
			out++;
			}
			else{
				cout<<"No"<<endl;
			}
		}
		if(s[i]=='c'){
			cout<<"No"<<endl;
		}
	}
}

Measured memory_bytes: 896
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;


public class Main {

	void solve(int n){
		Set<Integer> surplus=new HashSet<Integer>();
		int []appearance=new int[(n-1)/2];
		
		for(int i=1;i<n;++i){
			surplus.add((i*i)%n);
		}
		for(int a:surplus){
			for(int b:surplus){
				if(a==b)continue;
				int c=a-b;
				c=c<0?c+n:c;
				c=c>(n-1)/2?n-c:c;
				++appearance[c-1];
			}
		}
		for(int i=0;i<(n-1)/2;++i){
			System.out.println(appearance[i]);
		}
	}
	
	void io(){
		Scanner s=new Scanner(System.in);
		while(true){
			int n=s.nextInt();
			if(n==0)break;
			solve(n);
		}
		s.close();
	}

	public static void main(String[] args) {
		new Main().io();
	}

}

Measured memory_bytes: 13000
#include<iostream>
using namespace std;
int main() {
    int n;
    int a = 0;
    int w = 0;
    int t = 0;
    int r = 0;
    string s;
    cin >> n;
    for (int i = 0;i < n;++i) {
        cin >> s;
        if (s == "AC")
            ++a;
        else if (s == "WA")
            ++w;
        else if (s == "TLE")
            ++t;
        else if (s == "RE")
            ++r;
    }
    cout << "AC x " << a << "\nWA x " << w << "\nTLE x " << t << "\nRE x " << r;
}

Measured memory_bytes: 3588
#include<stdio.h>

int main (){
  int N = 0, x = 0;
  scanf("%d %d", &N, &x);

  int a[100] = {};
  for(int i1 = 0; i1 < N; i1++){
    scanf("%d", &a[i1]);
  }

  int m = 0;

  int s_a = 0;
  for(int i = 0; i < N; i++){
    s_a += a[i];
  }

  int min_a = 0;
  min_a = a[0];
  for(int i = 0; i < N; i++ ){
    if(min_a >= a[i]){
      min_a = a[i];
    }
  }

  m = ( x - s_a )/min_a ;
  printf ("%d", N + m);


  return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld double 
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define BOOST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(v) v.begin(),v.end()
#define sl(a) a.size()
#define mod 1000000007 
#define lcm(a,b) (a*b)/__gcd(a,b)
#define MAX1 100006
#define f first
#define s second
#define pi 2*acos(0.0)
set<ll> track;
vector<ll> graph[200005];
vector<bool> visited(200005,false);
void DFS(ll i)
{
    if(visited[i]) return;
    visited[i]=true;
    track.insert(i);
    for(ll j=0; j<sl(graph[i]); ++j)
    {
        if(!visited[graph[i][j]]) DFS(graph[i][j]);
    }
}
void solve()
{
    ll n,m; cin>>n>>m;
    set<pair<ll,ll>> se;
    rep(i,0,m)
    {
        ll u,v;  cin>>u>>v;
        if(se.count({u,v})||se.count({v,u}))  continue;
        graph[u].pb(v);
        graph[v].pb(u);
        se.insert({u,v});
        se.insert({v,u});
    }
    ll ans=1;
    rep(i,1,n+1)
    {
        if(!visited[i])
        {
            track.clear();
            DFS(i);
            ll temp=sl(track);
            ans=max(ans,temp);
        }
    }cout<<ans;
}
int main()
{
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt","r",stdin);
    //for getting error from error.txt
    freopen("error.txt", "w", stderr);
    // for writing output to output.txt
    freopen("output.txt","w",stdout);
    #endif
    BOOST
    int T=1;  //cin>>T;
    while(T--) solve();
    cerr<<"Time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<"\n";
    cerr<<"My CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";
    return 0;
}


Measured memory_bytes: 61612
#include <iostream>
#define MAX_BUF 1024
#define MAX_NUM 10000

using namespace std;

int inputline(char *inBuf){
	cin.get(inBuf,MAX_BUF);
	return 0;
}

int printline(char *buf){
	cout << buf << endl;
	return 0;
}

class stackc {
	int a[MAX_NUM];	// stack region
	int topnum;		// top position
public:
	int initialize(void);	// Initializing
	int isEmpty(void);		// is stack empty?
	int isFull(void);		// is stack full?
	int pop(bool*);			// statck pop
	int push(int);			// stack push
	int top(void);
};

/*void stackc::stackc(){
	topnum=-1;
}*/

int stackc::initialize(void){
	topnum=-1;
	return 0;
}

int stackc::isEmpty(void){
	return (int)(topnum==-1);
}

int stackc::isFull(void){
	return (int)(topnum==MAX_NUM-1);
}

int stackc::pop(bool *flag){
	if(!this->isEmpty()){
		topnum--;
		*flag=true;
		return a[topnum+1];
	} else{
		*flag=false;
		return 0;
	}
}

int stackc::push(int n){
	if(!this->isFull()){
		topnum++;
		a[topnum]=n;
		return 0;
	} else {
		return -1;
	}
}

int stackc::top(){
	return topnum;
}

int calcreverpolishnotation(char *seq,stackc *a){
	int i=0,j;
	int n,m,l;
	bool flag;
	while(!(seq[i]=='\n' || seq[i]=='\0')){
		if(seq[i]>='0' && seq[i]<='9'){
			j=0;
			while(seq[i]>='0' && seq[i]<='9'){
				j=j*10+(int)seq[i]-(int)'0';
				//cout << seq[i] << ' ' << (int)seq[i] << ' ' << (int)'0' << j << endl;
				i++;
			}
			a->push(j);
			//cout << j << endl;
		}else if(seq[i]=='+'){
			n=a->pop(&flag);
			m=a->pop(&flag);
			l=n+m;
			a->push(l);
			i++;
		}else if(seq[i]=='-'){
			n=a->pop(&flag);
			m=a->pop(&flag);
			l=m-n;
			a->push(l);
			i++;
		}else if(seq[i]=='*'){
			n=a->pop(&flag);
			m=a->pop(&flag);
			l=n*m;
			a->push(l);
			i++;
		}
		i++;
	}
	return i;
}

int main() {
	char inBuf[MAX_BUF];
	stackc s;
	int ans;
	bool flag;

	inputline(inBuf);

	//printline(inBuf);

	s.initialize();
	calcreverpolishnotation(inBuf,&s);

	ans=s.pop(&flag);

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3128
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#include <time.h> //for clock
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;
using ll = long long;

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

    vector<pair<ll ,ll>> v;
    ll a, b;
    ll i;

    for(i = 0; i < n; i++){
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }

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

    ll count = 0;
    ll ans = 0;
    for(i = 0; i < v.size(); i++){
        if(count + v[i].second >= m){
            ans += v[i].first * (m - count);
            break;
        }else{
            ans += v[i].first * v[i].second;
            count += v[i].second;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 2420
#include <algorithm>
#include <cstdio>
#include <climits>
#include <vector>
using namespace std;

int main() {
    while(true) {
        int n,k; scanf("%d%d", &n, &k);
        if(n==0) break;
        bool cards[100010];
        fill(cards, cards+n+1, false);
        for(int i = 0; i < k; i++) {
            int c; scanf("%d", &c); cards[c]=true;
        }
        int max_len = 0;
        if(cards[0]) {
            int cur_len1 = 0;
            int cur_len2 = 0;
            for(int i = 1; i <= n; i++) {
                if(cards[i]) {
                    cur_len1++;
                    cur_len2++;
                    max_len = max(max_len, cur_len1);
                } else {
                    cur_len1 = cur_len2+1;
                    cur_len2 = 0;
                }
            }
        } else {
            int cur_len = 0;
            for(int i = 1; i <= n; i++) {
                if(cards[i]) {
                    cur_len++;
                    max_len = max(max_len, cur_len);
                } else {
                    cur_len = 0;
                }
            }
        }
        printf("%d\n", max_len);
    }
    return 0;
}

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

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

int main() {
  string s, t;
  cin >> s >> t;
  int n = s.length(), m = t.length();

  string ans;
  REP(i, n - m + 1) {
    bool ok = true;
    REP(j, m) {
      if (s[i + j] != '?' && s[i + j] != t[j]) ok = false;
    }
    if (ok) {
      string tmp = s;
      REP(j, m) tmp[i + j] = t[j];
      REP(i, n) if (tmp[i] == '?') tmp[i] = 'a';
      if (ans.empty())
        ans = tmp;
      else
        ans = min(ans, tmp);
    }
  }

  cout << (ans.empty() ? "UNRESTORABLE" : ans) << endl;
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n, count int
	fmt.Scan(&n)
	var a = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
LOOP:
	for {
		for i := 0; i < n; i++ {
			if a[i]%2 == 0 {
				a[i] /= 2
			} else {
				break LOOP
			}
		}
		count++
	}
	fmt.Println(count)
}


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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	ll cnt = 0, ans = 0;
	REP(i, s.size()) {
		if (s[i] == 'B')cnt++;
		else ans += cnt;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1360
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] cities = new int[N];
        for (int i = 0; i < M * 2; i++) {
            int n = sc.nextInt();
            cities[n - 1]++;
        }
        for (int i = 0; i < N; i++) {
            System.out.println(cities[i]);
        }
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

i64 pow(i64 x, i64 n)
{
  i64 res = 1;
  if (n > 0)
  {
    res = pow(x, n / 2);
    if (n % 2 == 0)
    {
      res = (res * res);
    }
    else
    {
      res = ((res * res) * x);
    }
  }
  return res;
}

int main()
{
  i64 X;
  cin >> X;
  for (i64 i = 0;; i++)
  {
    i64 t = pow(i, 5);
    for (i64 j = 0; pow(j, 5) <= abs(X - t); j++)
      if (abs(X - t) == pow(j, 5))
      {
        if (0 < X - t)
          cout << i << " " << -j << endl;
        else
          cout << i << " " << j << endl;
        return 0;
      }
  }
  return 0;
}


Measured memory_bytes: 4096
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;

#define INF   (1e9 + 7)
#define MAX_N (100000)

int N, L, T;
ll X[MAX_N], P[MAX_N];
int W[MAX_N];

void solve() {
  for (int i = 0; i < N; i++) {
    P[i] = W[i] * T + X[i];
    P[i] = ((P[i] % L) + L) % L;
  }

  int cnt = 0;
  int round = 2 * T / L;
  int rest = 2 * T % L;
  for (int i = 1; i < N; i++) {
    if (W[i] != W[0]) {
      cnt += round;
      int d = X[i] - X[0];
      if (W[0] < 0) d = L - d;
      if (d < rest) cnt++;
    }
  }

  int p0 = P[0], i0;
  sort(P, P + N);
  if (W[0] > 0) {
    i0 = (int) (lower_bound(P, P + N, p0) - P);
  } else {
    i0 = (int) (upper_bound(P, P + N, p0) - P) - 1;
  }
  i0 = i0 - W[0] * cnt;
  i0 = ((i0 % N) + N) % N;

  for (int i = 0; i < N; i++) {
    printf("%lld\n", P[(i + i0) % N]);
  }
}

int main() {
  cin >> N >> L >> T;
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> W[i];
    W[i] = (W[i] == 1)? 1: -1;
  }

  solve();

  return 0;
}


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

int main()
{
	int l;
	scanf("%d", &l);
	std::vector<long long> a(l + 1);
	for (int i{1}; i <= l; i++)
		scanf("%lld", &a[i]);

	std::vector<long long[5]> dp(l + 1);
	for (auto& e: dp)
		std::fill(e, e + 5, 1LL << 60);
	dp[0][0] = 0;
	for (int l_i{1}; l_i <= l; l_i++)
	{
		int plus[5]{}, odd{}, even{};
		if (a[l_i] & 1) even = 1;
		else if (!a[l_i]) even = 2;
		if (~a[l_i] & 1) odd = 1;
		plus[0] = plus[4] = a[l_i];
		plus[1] = plus[3] = even;
		plus[2] = odd;
		for (int i{}; i < 5; i++)
			for (int j{}; j <= i; j++)
				dp[l_i][i] = std::min(dp[l_i][i], dp[l_i - 1][j] + plus[i]); 
	}
	printf("%lld\n", *std::min_element(dp.back(), dp.back() + 5));

	return 0;
}

Measured memory_bytes: 9600
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    a=int(input())
    b=int(input())
    h=int(input())
    print((a+b)*h//2)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

int main() {
    ll x, k, d;
    cin >> x >> k >> d;
    x = abs(x);

    if (x / d >= k) {
        cout << x - d * k << endl;
    } else {
        k -= x / d;
        x %= d;
        if (k % 2 == 0) {
            cout << x << endl;
        } else {
            cout << d - x << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(void)
{
	int n;
	long long int buf, min, max, sum = 0;
	scanf("%d", &n);
	n--;
	scanf("%lld", &min);
	max = min;
	sum += min;
	while (n--){
		scanf("%lld", &buf);
		if (max < buf){
			max = buf;
		}
		else if (buf < min){
			min = buf;
		}

		sum += buf;
	}

	printf("%lld %lld %lld\n", min, max, sum);
	return 0;
}

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

#define mod 1000000007

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

using namespace std;
typedef long long ll;
const long long INF = 1LL << 60;
 
int main(void){
	
	ll N, A, B;
    cin >> N >> A >> B;

    ll ans = N / (A + B);

    ll blue = ans * A;

    if(ans * (A + B) < N){
        blue += N - ans * (A + B);
        if(N - ans * (A + B) > A)
            blue -= N - ans * (A + B) - A;
    }

    cout << blue << endl;
	
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        bool hasMaxEvenNumFound = false;
        List<int> intList = new List<int>();
        
        for (int i = 1; i <= n; i++)
        {
            int tmp = i;
            int cnt = 0;
            int cnt2 = 0;
            
            bool isEven = true;
            while (isEven)
            {
                if (i % 2 == 0 && tmp != 0)
                {
                    tmp /= 2;
                    cnt++;
                }
                else
                {
                    isEven = false;
                    intList.Add(cnt);
                }
            }
            
        }

        Console.WriteLine(intList.IndexOf(intList.Max())+1);
    }
}


Measured memory_bytes: 13152
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(a) int((a).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

#define _deb(x) cout<<x;
void _print() {cerr << "]\n";} template <typename T, typename... V>void _print(T t, V... v) {_deb(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
template <class T, class U> void print_m(const map<T,U> &m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}
template<class T, class U>void debp(const pair<T, U> &pr, bool end_line=1){cout<<"{"<<pr.first<<" "<<pr.second<<"}"; cout<<(end_line ? "\n" : ", ");}
template <class T> void print_vp(const T &vp, int sep_line=0){if(vp.empty()){cout<<"Empty"<<endl; return;}if(!sep_line) cout<<"{ ";for(auto x: vp) debp(x,sep_line);if(!sep_line) cout<<"}\n";cout<<endl;}
template <typename T>void print(const T &v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<sz(v); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<endl;}
template <typename T>void print_vv(const T &vv){if(sz(vv)==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<sz(*vv.begin()); j++)cout<<setw(w)<<j<<" ";cout<<endl;int i = 0;for(auto &v: vv){cout<<i++<<" {";for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<"},\n";}cout<<endl;}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n, x, t;
    while(cin>>n>>x>>t){
        ll ans = (n + x-1)/(x) ;
        ans*=t;
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int h[100050][4];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,a,b,c;
    cin >> n;
    for(int i=0; i<3; i++)
    {
        cin >> h[0][i];
    }
    for(int i=1; i<n; i++)
    {
        cin>>a>>b>>c;
        h[i][0]=max(h[i-1][1]+a,h[i-1][2]+a);
        h[i][1]=max(h[i-1][0]+b,h[i-1][2]+b);
        h[i][2]=max(h[i-1][0]+c,h[i-1][1]+c);
    }
    cout << max(h[n-1][0],max(h[n-1][1],h[n-1][2])) << endl;
    return 0;
}


Measured memory_bytes: 3328
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# a〜z -- START --
alf=['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']
# a〜z --- END ---

def main():
  h,w=LI()
  l=[0]*len(alf)

  for _ in range(h):
    a=S()
    for x in a:
      l[alf.index(x)]+=1

  count4=count2=count1=0
  for i in range(len(alf)):
    count4+=l[i]//4
    l[i]%=4
    count2+=l[i]//2
    l[i]%=2
    count1+=l[i]

  # print(count1,count2,count4)

  if h%2==1 and w%2==1:
    if count1!=1:
      return 'No'

    x=count4-(h-1)*(w-1)//4
    if x<0:
      return 'No'
    count2+=x*2

    if count2!=w//2+h//2:
      return 'No'

    return 'Yes'
  elif h%2==1 and w%2==0:
    if count1!=0:
      return 'No'

    x=count4-(h-1)*w//4
    if x<0:
      return 'No'
    count2+=x*2

    if count2!=w//2:
      return 'No'

    return 'Yes'
  elif h%2==0 and w%2==1:
    if count1!=0:
      return 'No'

    x=count4-h*(w-1)//4
    if x<0:
      return 'No'
    count2+=x*2

    if count2!=h//2:
      return 'No'

    return 'Yes'
  elif h%2==0 and w%2==0:
    if count1!=0:
      return 'No'

    x=count4-h*w//4
    if x<0:
      return 'No'
    count2+=x*2

    if count2!=0:
      return 'No'

    return 'Yes'

# main()
print(main())


Measured memory_bytes: 5172
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    long long a[n],sum[n+1];
    sum[0]=0;
    int r=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i-1];
        sum[i]=sum[i-1]+a[i-1];
    }
    long long dp[n][n];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            dp[i][j]=0;
        }
    }
    for(int d=1;d<=n;d++)
    {
        for(int l=0;l<n-d;l++)
        {
            r=l+d;
            if(l>0) dp[l][r]=dp[l][l]+dp[l+1][r]+sum[r+1]-sum[l];
            else dp[l][r]=dp[l][l]+dp[l+1][r]+sum[r+1];

            for(int k=l;k<r;k++)
                {
                    if(l>0) dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r+1]-sum[l]);
                    else dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r+1]);
                }
        }
    }

    cout<<dp[0][n-1];
    return 0;
}


Measured memory_bytes: 1536
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

// #define int long long int
constexpr int INF = std::numeric_limits<int>::max();
constexpr int NINF = std::numeric_limits<int>::lowest();
using namespace std;

void solve() {
  string S, T;
  cin >> S >> T;
  vector<char> rs(26, -1);
  vector<char> rt(26, -1);

  bool ok = true;
  for (int i = 0; i < S.size(); i++) {
    char s = S[i] - 'a';
    char t = T[i] - 'a';
    if (rs[s] < 0) {
      rs[s] = t;
    }
    if (rt[t] < 0) {
      rt[t] = s;
    }

    if (rs[s] != t || rt[t] != s) {
      ok = false;
      break;
    }
  }

  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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


Measured memory_bytes: 916
#include <cstdio>
using namespace std;
int main(){
    long long h;
    scanf("%lld", &h);
    long long now = 1;
    long long res = 0;
    while(h){
        res += now;
        now *= 2;
        h /= 2;
    }
    printf("%lld\n", res);
    return 0;
}


Measured memory_bytes: 128
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
 
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct XORBasis{
    int n;
    vector<ull> p;
    vector<ull> ans;
    XORBasis(int k):n(k){
        p.resize(k+1);
    }
    void rebuilt(){
        ans.clear();
        for (int i=0;i<=n;++i){
            if (p[i]) ans.push_back(p[i]);
        }
    }
    void insert(ull u){
        for (int i=n;i>=0;--i){
            if (u&(1ull<<i)){
                if (p[i]) u^=p[i];
                else{
                    p[i]=u;
                    for (int j=i-1;j>=0;--j){
                        if (p[i]&(1ull<<j)) p[i]^=p[j];
                    }
                    for (int j=i+1;j<=n;++j){
                        if (p[j]&(1ull<<i)) p[j]^=p[i];
                    }
                    break;
                }
            }
        }
        rebuilt();
    }
    bool check(ull u){
        for (int i=n;i>-1;--i){
            if (u&(1ull<<i)) u^=p[i];
        }
        return (u==0);
    }
    ull kth(ull t){ // the k-th smallest, excluding 0.
        if (t>=(1ull<<sz(ans))) return -1;
        ull ret=0;
        for (int i=0;i<sz(ans);++i){
            if (t&(1ull<<i)) ret^=ans[i];
        }
        return ret;
    }
    ull total(){
        return (1ull<<sz(ans));
    }
};
 

const int maxn=2007;
int t,n;
int a[maxn];
string s;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>t;
    while (t--){
        XORBasis xo(60);
        cin>>n;
        rep(i,n) cin>>a[i];
        cin>>s;
        reverse(a,a+n);
        reverse(range(s));
        rep(i,n){
            if (s[i]=='0') xo.insert(a[i]);
            else if (!xo.check(a[i])){
                cout<<"1\n";
                goto cont;
            }
        }
        cout<<"0\n";
        cont:;
    }
    return 0;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define out(a) cout << a << endl
#define outa(a, n) rep(_, n) cout << a[_] << " "; cout << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)

ll dp[100001][13];
int main() {
    string s;
    cin >> s;
    fill_n(*dp, 100001 * 13, 0);
    dp[0][0] = 1;
    rep(i, SZ(s)) rep(k, 13) {
        if (s[i] == '?') {
            rep(l, 10) {
                (dp[i + 1][(k * 10 + l) % 13] += dp[i][k]) %= (ll)(1e9 + 7);
            }
        } else {
            (dp[i + 1][(k * 10 + (s[i] - '0')) % 13] += dp[i][k]) %= (ll)(1e9 + 7);
        }
    }
    out(dp[SZ(s)][5]);
    /*
    rep(i, SZ(s) + 1) {
        rep(j, 13) cout << dp[i][j] << " ";
        cout << endl;
    }
     */
}


Measured memory_bytes: 10624
#include <bits/stdc++.h>
using namespace std;
const unsigned int MOD = 1000000007;
#define ll long long
#define PI 3.1416
string day[]={"SUN","MON","TUE","WED","THU","FRI","SAT"};
int main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int r;
    while(cin>>r){
        cout<<r*r<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
if(m<2):
  print(0)
else:
  num=min(n,m//2)
  n-=num
  m-=2*num
  #print(n,m,num)
  if(m<2):
    print(num)
  else:
    num+=m//4
    print(num)
  

Measured memory_bytes: 2940
import math

A, B = map(int,input().split())

b = B*(100/10)
b_floor = math.floor(b)
b_sample = []

a = A*(100/8)
a_floor = math.floor(a)
a_sample = []

for i in range(-12,13):
    a_floor += i
    if a < 0:
        continue
    else:
        x = a_floor*(0.08)
        x_floor = math.floor(x)
        if x_floor == A:
            a_sample.append(a_floor)
            a_floor = math.floor(a)
            continue
        else:
            a_floor = math.floor(a)

for i in range(10):
    b_floor += i
    y = b_floor*(0.10)
    y_floor = math.floor(y)
    if y_floor == B:
        b_sample.append(b_floor)
        b_floor = math.floor(b)
        continue
    else:
        b_floor = math.floor(b)

ans = []
for x in a_sample:
    for y in b_sample:
        if x == y:
            ans.append(x)
            continue


if len(ans) > 0:
    print(min(ans))
else:
    print(-1)

        


Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

int main()
{
	int n, a, d[100000]={}, dist[100000];
  scanf("%d", &n);
  vector<int> v[100000];
  for(int i=1; i<=n-1; i++){
    scanf("%d", &a);
    a--;
    v[a].push_back(i);
  }
  dist[0]=0;
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int x=que.front();
    que.pop();
    for(int i=0; i<v[x].size(); i++){
      dist[v[x][i]]=dist[x]+1;
      que.push(v[x][i]);
    }
  }
  multimap<int, int> dmp;
  for(int i=0; i<n; i++){
    dmp.insert(make_pair(-dist[i], i));
  }
  for(auto itr=dmp.begin(); itr!=dmp.end(); itr++){
    int x=itr->second;
    int m=v[x].size();
    if(m>0){
    vector<int> w;
    for(int i=0; i<v[x].size(); i++){
      w.push_back(d[v[x][i]]);
    }
    sort(w.begin(), w.end());
    for(int i=0; i<v[x].size(); i++){
      w[i]=w[i]+m-i;
    }
    for(int i=0; i<v[x].size(); i++){
      if(d[x]<w[i]) d[x]=w[i];
    }
    }
  }
  printf("%d\n", d[0]);
	return 0;
}


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

#define int long long

#define inf 1000000007LL
#define mod 1000000007LL

#define rep(i, n) for(int i = 0; i < (n); i++)
#define trep(i, n) for(int i = 0; i <= (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define mfor(i, s, t) for(int i = (s); i < (t); i++)
#define tfor(i, s, t) for(int i = (s); i <= (t); i++)
#define rfor(i, s, t) for(int i = (t) - 1; i >= (s); i--)

int ans[334334];

signed main() {
  int n;
  cin >> n;
  rep(i, n) {
    int w;
    cin >> w;
    if(i % 2 == (n - 1) % 2) {
      ans[(n + 1) / 2 - 1 - i / 2] = w;
    }
    else {
      ans[(n + 1) / 2 + i / 2] = w;
    }
  }
  rep(i, n) {
    cout << ans[i];
    if(i < n - 1) {
      cout << " ";
    }
    else {
      cout << endl;
    }
  }
}


Measured memory_bytes: 3712
#include<iostream>

using namespace std;

int main(){
    int N,W;
    int dp[101][10001];
    int v[100],w[100];
    cin>>N>>W;
    for(int i=0;i<N;i++){
        cin>>v[i]>>w[i];
    }
    
    for(int i=0;i<=W;i++){
        dp[0][i]=0;
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<=W;j++){
            dp[i+1][j]=dp[i][j];
            if(j-w[i]>=0){
                dp[i+1][j]=max(dp[i+1][j-w[i]]+v[i],dp[i+1][j]);
            }
        }
    }
    cout<<dp[N][W]<<endl;
    return 0;
    
}



Measured memory_bytes: 7040
void main() {
	auto ip = readAs!(int[]), N = ip[0], M = ip[1];
	auto A = readAs!(int[]);
	
	int[] c = [2,5,5,4,5,6,3,7,6];
	auto dp = new string[](11000);
	dp[] = "ア!w";
	dp[0] = "";
	void chmax(ref string a, string b) {
		if(a == "ア!w") a = b;
		else if(a.length < b.length) a = b;
		else if(a.length == b.length && a < b) a = b;
	}
	
	foreach(i; 0..10000) {
		if(dp[i] == "ア!w") continue;
		foreach(v; A) chmax(dp[i+c[v-1]], dp[i] ~ v.to!string);
	}
	dp[N].writeln;
}

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

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


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

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; }
const long long INF = 1LL << 60;
int dp[3100][3100];

int main(){
    string a,b;
    cin >> a >> b;    
    for(int i=0;i<a.size();++i){
        for(int j=0;j<b.size();++j){
            chmax(dp[i+1][j+1],dp[i][j+1]);
            chmax(dp[i+1][j+1],dp[i+1][j]);
            if(a[i]==b[j]){
                chmax(dp[i+1][j+1],dp[i][j]+1);
            }
        }
    }

    // 復元
    string ans = "";
    int i = a.size();
    int j = b.size();
    while(i>0 && j>0){
        if(dp[i-1][j]==dp[i][j]){
            i--;
        } else if(dp[i][j-1]==dp[i][j]){
            j--;
        } else {
            ans = a[i-1] + ans;
            i--;j--;
        }
    }

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 37120
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();

        int n = sc.nextInt();
        int m = sc.nextInt();

        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        Map<Long, Integer> map = new TreeMap<>();
        for (int i = 0; i < m; i++) {
            int b = sc.nextInt();
            long c = sc.nextLong();
            if (map.containsKey(c))
                map.put(c, map.get(c) + b);
            else
                map.put(c, b);
        }

        Arrays.sort(a);

        long ans = 0;
        Object[] keys = map.keySet().toArray();
        int keysIndex = keys.length-1;
        for (int i = 0; i < n; i++) {
            long key = -1;
            if (keysIndex >= 0)
                key = (long)keys[keysIndex];

            if (a[i] < key) {
                ans += key;
                map.put(key, map.get(key)-1);
            } else {
                ans += a[i];
            }

            if (key >= 0 && map.get(key) <= 0)
                keysIndex = Math.max(-1, keysIndex-1);
        }

        System.out.println(ans);
    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

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

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

Measured memory_bytes: 57520
N,Q = map(int,input().split())
S = input()

ansLis = [0]
tmp = 0
flgA = False
for i in range(N):
    if flgA and S[i]=="C":
        tmp += 1
    ansLis.append(tmp)
    flgA = (S[i] == "A")
# print(ansLis)

ans = []
for _ in range(Q):
    l,r = map(int,input().split())
    num = ansLis[r] - ansLis[l]
    # if S[l-2] == "A" and S[l-1] == "C":
    #     num = max(0, num-1)
    ans.append(num)

print(*ans,sep="\n")

Measured memory_bytes: 11820
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
template<class T>bool chmin(T &a, const T &b){return(a=min(a,b))==b;}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

string s;
int n, d;

int dp[10010][2][111];

signed main() {

    cin >> s >> d;
    n = s.size();

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

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < d; j++) {
            for(int k = 0; k < 10; k++) {
                int *p = &dp[i+1][1][(j+k)%d];
                *p = (*p + dp[i][1][j]) % SMOD;
            }
            for(int k = 0; k < s[i]-'0'; k++) {
                int *p = &dp[i+1][1][(j+k)%d];
                *p = (*p + dp[i][0][j]) % SMOD;
            }

            int t = (s[i]-'0'+j)%d;
            dp[i+1][0][t] = (dp[i+1][0][t] + dp[i][0][j]) % SMOD;
        }
    }

    cout << (dp[n][1][0] + dp[n][0][0] - 1 + SMOD) % SMOD << endl;
    
    return 0;
}



Measured memory_bytes: 8960
def checkGo(x,y,t):
    if abs(x) + abs(y) > t or (t - (abs(x) + abs(y)) ) % 2 == 1:
        return False
    return True
count = int(input())
data = []
for i in range(count):
    data.append(list(map(int,input().split())))
passTime = 0
beforeX = 0
beforeY = 0
for i in data:
    time = i[0]
    x = i[1]
    y = i[2]
    if not checkGo(x - beforeX, y - beforeY, time - passTime):
        print("No")
        exit()
    passTime = i[0]
    beforeX = i[1]
    beforeY = i[2]
print("Yes")


Measured memory_bytes: 27380
object Main{
  object Solver extends InputReader{
    def solve(){
      try{
        while(true){
          val a = getInt()
          val b = getInt()
          println(a - b)
        }
      }catch{
        case _ : Throwable =>
      }
    }
  }

  // TEMPLATE ------------------------

  def main(args: Array[String]){
    Solver.solve()
  }

  trait InputReader{
    import java.io._
    import java.util._
    protected val stream = System.in
    private val reader = new BufferedReader(new InputStreamReader(stream))
    private var tokenizer = new StringTokenizer(reader.readLine())

    def getStr(): String = {
      while(!tokenizer.hasMoreTokens())
        tokenizer = new StringTokenizer(reader.readLine())
      tokenizer.nextToken()
    }

    def getInt(): Int = getStr().toInt
    def getLong(): Long = getStr().toLong
    def getDouble(): Double = getStr().toDouble
  }
}

Measured memory_bytes: 43944