akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::ops::Bound::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout]
fn main() {
    input! {
        n: usize, q: usize,
    }

    let mut dsu = DSU::new(n);
    for _ in 0..q {
        input! {
            t: u8, u: usize, v: usize,
        }
        if t == 0 {
            dsu.merge(u, v);
        } else {
            let res = dsu.same(u, v) as u8;
            println!("{}", res);
        }
    }
}

#[allow(dead_code)]
pub struct DSU {
    parent_or_size: Vec<isize>,
}

#[allow(dead_code)]
impl DSU {
    pub fn new(n: usize) -> Self {
        assert!(n <= std::isize::MAX as usize);
        Self {
            parent_or_size: vec![-1; n],
        }
    }

    pub fn merge(&mut self, a: usize, b: usize) -> usize {
        let mut x = self.leader(a);
        let mut y = self.leader(b);
        if x == y {
            return x;
        }
        if -self.parent_or_size[x] < -self.parent_or_size[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.parent_or_size[x] += self.parent_or_size[y];
        self.parent_or_size[y] = x as isize;
        x
    }

    pub fn same(&mut self, a: usize, b: usize) -> bool {
        self.leader(a) == self.leader(b)
    }

    pub fn leader(&mut self, a: usize) -> usize {
        if self.parent_or_size[a] < 0 {
            a
        } else {
            self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as isize;
            self.parent_or_size[a] as usize
        }
    }

    pub fn size(&mut self, a: usize) -> usize {
        let leader = self.leader(a);
        -self.parent_or_size[leader] as usize
    }

    pub fn groups(&mut self) -> Vec<Vec<usize>> {
        let mut leader_buf = vec![0usize; self.parent_or_size.len()];
        let mut group_size = vec![0usize; self.parent_or_size.len()];
        for i in 0..self.parent_or_size.len() {
            leader_buf[i] = self.leader(i);
            group_size[leader_buf[i]] += 1;
        }
        let mut result = vec![Vec::new(); self.parent_or_size.len()];
        for i in 0..self.parent_or_size.len() {
            result[i].reserve(group_size[i]);
        }
        for i in 0..self.parent_or_size.len() {
            result[leader_buf[i]].push(i);
        }
        result.retain(|v| !v.is_empty());
        result
    }
}

Measured memory_bytes: 5532
#include<stdio.h>

int main(){
	int a,b,i,j;
	char s[10];
	char num[11]={'0','1','2','3','4','5','6','7','8','9'};

	scanf("%d %d",&a,&b);
	scanf("%s",&s);

	if(s[a]=='-'){

		for(i=0;i<a+b+1;i++){
			if(i==a){
				continue;
			}
			for(j=0;j<10;j++){
				if(s[i]==num[j]){
					break;
				}
				else if(j==9){
					i+=100;
				}
			}
		}
		if(i==a+b+1){
			printf("Yes");
		}
		else{
			printf("No");
		}
	}
	else{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
multiset<int> s;
multiset<int>::iterator it;
int main(){
  int K,T,t,t1,t2,ans;
  scanf("%d %d",&K,&T);
  for(int i=1;i<=T;i++){
    scanf("%d",&t);
    s.insert(t);
  }
  while(s.size()>=2){
    it=s.end();
    it--;
    t2=*it;
    s.erase(it);
    it=s.end();
    it--;
    t1=*it;
    s.erase(it);
    s.insert(t2-t1);
  }
  ans=max(0,(*s.begin())-1);
  printf("%d",ans);
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std; 
  
const int MAX = 500005; 
// Code Snippet GeeksForGeeks
// structure to store queries 
struct Query 
{ 
    int l, r, idx; 
}; 
  
// cmp function to sort queries according to r 
bool cmp(Query x, Query y) 
{ 
    return x.r < y.r; 
} 
  
// updating the bit array 
void update(int idx, int val, int bit[], int n) 
{ 
    for (; idx <= n; idx += idx&-idx) 
        bit[idx] += val; 
} 
  
// querying the bit array 
int query(int idx, int bit[], int n) 
{ 
    int sum = 0; 
    for (; idx>0; idx-=idx&-idx) 
        sum += bit[idx]; 
    return sum; 
} 
  
void answeringQueries(int arr[], int n, Query queries[], int q) 
{ 
    // initialising bit array 
    int bit[n+1]; 
    memset(bit, 0, sizeof(bit)); 
  
    // holds the rightmost index of any number 
    // as numbers of a[i] are less than or equal to 10^6 
    int last_visit[MAX]; 
    memset(last_visit, -1, sizeof(last_visit)); 
  
    // answer for each query 
    int ans[q]; 
    int query_counter = 0; 
    for (int i=0; i<n; i++) 
    { 
        // If last visit is not -1 update -1 at the 
        // idx equal to last_visit[arr[i]] 
        if (last_visit[arr[i]] !=-1) 
            update (last_visit[arr[i]] + 1, -1, bit, n); 
  
        // Setting last_visit[arr[i]] as i and updating 
        // the bit array accordingly 
        last_visit[arr[i]] = i; 
        update(i + 1, 1, bit, n); 
  
        // If i is equal to r of any query  store answer 
        // for that query in ans[] 
        while (query_counter < q && queries[query_counter].r == i) 
        { 
            ans[queries[query_counter].idx] = 
                     query(queries[query_counter].r + 1, bit, n)- 
                     query(queries[query_counter].l, bit, n); 
            query_counter++; 
        } 
    } 
  
    // print answer for each query 
    for (int i=0; i<q; i++) 
        cout << ans[i] << endl; 
} 
  
int main()
{
    int n,q;
    cin>>n>>q;
    int arr[n];
    for(int i=0;i<n;i++)
     cin>>arr[i];
    Query qe[q]; 
    
    for(int i=0;i<q;i++)
    {
    	int x,y;
        cin>>x>>y;
        qe[i].l=x-1;
        qe[i].r=y-1;
        qe[i].idx=i;
    }
    sort(qe, qe+q, cmp); 
    answeringQueries(arr, n, qe, q); 
}

Measured memory_bytes: 17380
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
#include <cstdio>
using namespace std;

#define PI 4*atan(1);

int main(){
  string g;
  cin >> g;
  for(int i = 0; g[i] != '\0'; i++){
    if(g[i] == 'A'){
      g[i] = 'X';
    }else if(g[i] == 'B'){
      g[i] = 'Y';
    }else if(g[i] == 'C'){
      g[i] = 'Z';
    }else{
      g[i] -= 3;
    }
  }
  cout << g << endl;
}

Measured memory_bytes: 1180
w,h,n=map(int,input().split())
l=[[False]*w for _ in range(h)]

for _ in range(n):
    x,y,a=map(int,input().split())

    if a==1:
        s,t=range(h),range(x)
    elif a==2:
        s,t=range(h),range(x,w)
    elif a==3:
        s,t=range(y),range(w)
    elif a==4:
        s,t=range(y,h),range(w)

    for i in s:
        for j in t:
            l[i][j]=True

print(h*w-sum(map(sum,l)))

Measured memory_bytes: 42864
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

    int N; cin >> N;
    string S; cin >> S;
    int cnt=0;
    rep(i,N-2){
        if(S[i]=='A' && S[i+1]=='B' && S[i+2]=='C') cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main{
 public static void main(String[]args){

  Scanner sc= new Scanner(System.in);
  int n= sc.nextInt();
  for(int i=1;i<=n;i++){
   if(i%3==0||Integer.toString(i).contains("3"))
System.out.print(" "+i);
}
System.out.println();
}
}


Measured memory_bytes: 29408
#include<cstdio>
#include<algorithm>
using namespace std;

int n, a, b, c, d;

int main() {
  scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
  int ans1 = n / a;
  if (ans1 * a != n) ans1++;
  int ans2 = n / c;
  if (ans2 * c != n) ans2++;
  printf("%d\n", min(ans1 * b, ans2 * d));
}



Measured memory_bytes: 2732
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll ;
typedef double db;
const double pi = 3.141592654;
#define pb         push_back
#define forab(i,a,b)       for(int i=(a);i<=(b);i++)
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define pcase(z,x)     printf("Case %ld: %lld\n",z,x)
#define nw	 "\n"
#define mod 1000000007

ll w,e;
int main(void)
{
	CIN;
	ll tc,l,k=0,sum=0,x=0,y,z=0,m=1,n=0,ans=0,cnt=0;
	cin>>n>>k;sum=1e17;
	vector<ll>v(n);
	for(ll i=0;i<n;i++)cin>>v[i];
	sort(v.begin(),v.end());
	for(ll i=0;i<n-k+1;i++)
		sum=min(sum,v[i+k-1]-v[i]);
	cout<<sum;


}

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

using namespace std;

int main() {
  string s, p;
  cin >> s >> p;
  s = s + s;
  for (int i = 0; i < s.size(); i++) {
    if (s.substr(i, p.size()) == p) {
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}


Measured memory_bytes: 3212
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

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

int main(void) {
    string S;
    cin >> S;
    int slen = (int) S.size();

    set<char> cs;
    cs.insert('A');
    cs.insert('C');
    cs.insert('G');
    cs.insert('T');

    int ans = 0;
    for (int i = 0; i <= slen; i++) {
        for (int j = i + 1; j <= slen; j++) {
            // [i, j)
            bool ok = true;
            for (int k = i; k < j; k++) {
                if (cs.find(S[k]) == cs.end()) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                chmax(ans, j - i);
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

bool exists(int x, int n, string s) {
    if (x * 2 > n) return false;

    unordered_map <string, set <int> > ssm;
    set <int> epy {};
    string ss;

    for (int i = 0; i < n - x + 1; i++) {
        ss = s.substr(i, x);
        if (ssm.find(ss) == ssm.end()) {
            ssm[ss] = epy;
        }
        ssm[ss].insert(i);
    }
    set <int> si;
    for (auto itr = ssm.begin(); itr != ssm.end(); itr++) {
        si = itr->second;
        if (*si.rbegin() - *si.begin() >= x) return true;
    }

    return false;
}

int main(void) {
    int n, mi, md, ma;
    string s;
    cin >> n;
    cin >> s;

    mi = 0;  // Exist
    ma = 2501;  // Not exist
    for (int i = 0; i < 100; i++) {
        md = mi + (ma - mi) / 2;
        if (exists(md, n, s)) {
            mi = md;
        } else {
            ma = md;
        }
        if (ma - mi <= 1) break;
    }
    cout << mi << endl;

    return 0;
}


Measured memory_bytes: 6756
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <limits>
#include <iterator>
#include <cmath>
#include <numeric>
#include <stack>
#include <queue>
#include <cassert>
#include <forward_list>
#include <chrono>
#include <deque>
#include <list>
#include <random>
#include <cstdio>
#include <sstream>

using namespace std;

//最大公約数
template<class T>
T GCD(T m, T n)
{
	T temp;
	while (m % n != 0)
	{
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}

//最小公倍数
template<class T>
T LCM(T m, T n)
{
	return m * n / GCD(m, n);
}

int main()
{
	long long int W, H, x, y;
	cin >> W >> H >> x >> y;

	double area = static_cast<double>(W) * static_cast<double>(H) / 2;
	bool sign = 2 * x == W && 2 * y == H;

	cout << area << " " << sign << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <tuple>
#include <complex>
#include <cassert>
#include <exception>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << "\n"
static const int INF = 1e+9+7;
ll n,m,l;
string s,t;
ll d[200010],dp[300][300];
char field[200][200];

int main(){
  cin >> n;
  vi vec;
  rep(i,0,n){
    cin >> d[i];
    vec.pb(d[i]);
  }
  sort(all(vec));
  rep(i,0,n){
    if(d[i] < vec[n/2])print(vec[n/2]);
    else print(vec[n/2-1]);
  }
  return 0;
}

Measured memory_bytes: 4724
import sys
n,y = map(int,input().split())
flag = False
for i in range(n+1):
    for j in range(n-i+1):
        k = n-i-j
        total = 10000*i+5000*j+1000*k
        if(total == y):
            flag = True
            print(i, j, k)
            sys.exit()
if(flag==False):
    print(-1, -1, -1)


Measured memory_bytes: 3316
// AOJ ALDS1_3_C Doubly Linked List
// 2018.5.1 bal4u

#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void skip(int k) { while (k--) gc(); }

void out(int n)
{
	int i;
	char ob[20];

	if (!n) { pc('0'); return; }
	i = 0; while (n) ob[i++] = n%10 + '0', n/=10;
	while (i--) pc(ob[i]); 
}

int que[2000005]; int top, end;

int main()
{
	int n, i, t;
	char op;

	n = in(); top = 0, end = 1;
	while (n--) {
		if (gc() == 'i') {
			skip(6);
			que[end++] = in();
		} else {
			skip(5);
			op = gc();
			if (op == 'F') {
				skip(5);
				end--;
			} else if (op == 'L') {
				skip(4);
				top++;
			} else {
				que[top] = t = in();
				for (i = end-1; que[i] != t; i--);
				if (i > top) {
					for (i++; i < end; i++) que[i-1] = que[i];
					end--;
				}
			}
		}
	}
	t = 0;
	for (i = end-1; i > top; i--) {
		if (t) pc(' ');
		else t = 1;
		out(que[i]);
	}
	pc('\n');
	return 0;
}


Measured memory_bytes: 5512
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<complex<double>>  DFT(vector<complex<double>> a) {
	int n = a.size();
	if (n == 1) return a;
	vector<complex<double>> a0(n / 2), a1(n / 2);
	REP(i, n) {
		if (i % 2 == 0) {
			a0[i / 2] = a[i];
		}
		else {
			a1[i / 2] = a[i];
		}
	}
	vector<complex<double>> inversed_a0 = DFT(a0), inversed_a1 = DFT(a1);
	vector<complex<double>> inversed_a(n);
	for (int i = 0; i < n; ++i) {
		complex<double> zeta = complex<double>(cos(2 * Ma_PI * i / n), sin(2 * Ma_PI * i / n));
		inversed_a[i] = inversed_a0[i % (n / 2)] + zeta * inversed_a1[i % (n / 2)];
	}
	return inversed_a;
}
vector<complex<double>> IDFT(vector<complex<double>> inversed_a) {
	int n = inversed_a.size();
	vector<complex<double>> now = DFT(inversed_a);
	reverse(now.begin(), now.end());
	for (int q = now.size() - 1; q >= 1; --q) {
		swap(now[q], now[q - 1]);
	}
	REP(i, n) {
		now[i] /= complex<double>(n, 0);
	}
	return now;
}
vector<complex<double>> conv(vector<complex<double>> a, vector<complex<double>> b) {
	int deg = a.size() + b.size() - 1;
	int n = 1;
	while (n < deg) n <<= 1;
	a.resize(n);
	b.resize(n);
	vector<complex<double>> inversed_a = DFT(a),inversed_b = DFT(b);
	vector<complex<double>> inversed_c(n);
	REP(i, n) {
		inversed_c[i] = inversed_a[i] * inversed_b[i];
	}
	return IDFT(inversed_c);
}

int main() {
	int n, d;
	cin >> n >> d;
	int now = 1;
	int ans = 0;
	for (int q = 2; q <= n; ++q) {
		if (q - d >= now) {
			now = q + d + 1;
			ans++;
		}
	}
	if (now <= n) {
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 888
H,W = map(int,input().split())
a = [list(input()) for i in range(H)]
ver = []
hor = []
for j in range(W):
    tmp = []
    for i in range(H):
        tmp.append(a[i][j])
    if tmp == ["."]*H:
        ver.append(j)
for i in range(H):
    if a[i] == ["."]*W:
        hor.append(i)
ver = list(set(list(range(W)))-set(ver))
hor = list(set(list(range(H)))-set(hor))
ans = []
for i in hor:
    tmp = []
    for j in ver:
        tmp.append(a[i][j])
    ans.append(tmp)
for i in range(len(ans)):
    print("".join(ans[i]))

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for (int i = 0; i <= (n); ++i)
#define rip(i,n) for (int i = 1; i <= (n); ++i)
using namespace std;
int main() {
	int a; cin >> a;
	cout << 3 * a * a << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void){
    char s[4];
    scanf("%s",s);
    if(strcmp(s,"SUN")==0) printf("7");
    if(strcmp(s,"MON")==0) printf("6");
    if(strcmp(s,"TUE")==0) printf("5");
    if(strcmp(s,"WED")==0) printf("4");
    if(strcmp(s,"THU")==0) printf("3");
    if(strcmp(s,"FRI")==0) printf("2");
    if(strcmp(s,"SAT")==0) printf("1");
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;
#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif // LOCAL
using ll = long long ;
int a, b ;


int main(){
    cin >> a >> b;
    for(int i = 1 ;i <= 3 ;i ++){
        if(i != a && i != b)
            cout << i << endl;
    }
}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 256
N, M = map(int, input().split())
H = list(map(int, input().split()))

good = [True] * N

for _ in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    if H[A] <= H[B]:
        good[A] = False
    if H[B] <= H[A]:
        good[B] = False

print(good.count(True))


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

int main() {
    int ans = 0;
    int N;
    cin >> N;
    vector<char> c(N);
    for (int i = 0; i < N; i++) {
        cin >> c[i];
    }

    vector<char> d = c;

    sort(d.begin(),d.end());
    for (int i = 0; i < N; i++)  {
        ans += c[i]!=d[i];
    }
    cout << ans/2 << endl;
    return 0;
}


Measured memory_bytes: 3736
N = int(input())
ans = N
for i in range(N + 1):
	count = 0
	t = i
	while t > 0:
		count += int(t % 9)
		t = int(t / 9)
	t = N - i
	while t > 0:
		count += int(t % 6)
		t = int(t / 6)
	if count < ans:
		ans = count
print(ans)


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

int c[100000];

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

	int N, M;
	cin >> N >> M;
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		c[a]++;
		c[b]++;
	}
	for(int i = 0; i < N; i++) {
		if(c[i] % 2) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;
using pll = pair<ll, ll>;

int main(){
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; ++i){
  	cin >> a[i] >> b[i];
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  int mx = b[n/2 - 1] + b[n/2];
  int mn = a[n/2 - 1] + a[n/2];
  if(n % 2){
  	mx = b[n/2];
  	mn = a[n/2];
  }

  int ans = mx - mn + 1;
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4848
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF (1LL<<60)
#define MOD 1000000007
inline void chmax(long long &x, long long v) { if (x < v) x = v; }

int N, M, T, Q;
long long dp[20][1000];
long long S[2][1000];
void merge(long long O[], long long A[], long long B[]) {
  rep(a, T) {
    if (A[a] == -INF) continue;
    rep(b, T) {
      if (B[b] == -INF) continue;
      chmax(O[(a+b)%T], A[a]+B[b]);
    }
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M >> T;
  rep(k, 20) rep(i, T) dp[k][i] = -INF;
  dp[0][0] = 0;
  rep(i, N) {
    int a;
    cin >> a;
    chmax(dp[0][a%T], a);
  }
  rep(k, 19) merge(dp[k+1], dp[k], dp[k]);

  rep(i, T) S[0][i] = -INF; S[0][0] = 0;
  rep(k, 20) if ((M>>k)&1) {
    rep(i, T) S[1][i] = -INF;
    merge(S[1], S[0], dp[k]);
    swap(S[0], S[1]);
  }

  for (int i=T-2; i>=0; i--) chmax(S[0][i], S[0][i+1]);
  cin >> Q;
  rep(i, Q) {
    int a, b;
    cin >> a >> b;
    if (S[0][a] >= 1LL*T*b) cout << "yes\n";
    else cout << "no\n";
  }
  return 0;
}

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

int main(void){
    string s;
    cin >> s;
    string str = "";
    for(int i=0;i<s.size();++i){
        char in = s[i];
        switch(in){
            case '1': str += '1'; break;
            case '0': str += '0'; break;
            case 'B': if(str!=""){
                str.erase(str.end()-1);
            }
            break;
        }
    }
    cout << str << endl;
}

Measured memory_bytes: 256
w = input()

a = []
for i in w:
    a.append(i)

a = set(a)

for i in a:
    count = 0
    for j in w:
        if j == i:
            count += 1
    if count % 2 == 0:
        continue
    else:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define endl "\n"
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define ll long long
#define llu unsigned long long
#define MAX(a, b)  (((a) > (b)) ? (a) : (b))
#define MIN(a, b)  (((a) < (b)) ? (a) : (b))
#define ABS(X) ((X)< 0 ? -(X): (X))
#define LCM(X, Y)  ( ( (X) / (GCD( (X)  , (Y) ))) * (Y) )
#define MEM( A,  B) memset((A), (B), sizeof(A))
#define MEM_VEC(V, FILL ) fill( V.begin(), V.end(), FILL)
#define FOR_EACH(IT, V) for (auto IT = V.begin(); IT != V.end(); IT++)
#define DEBUG_ARRAY_PRINT(A,I) cout<<"at pos "<< I <<"  value is: "<< A[I]
#define TURBO ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0)
const double EPS =1e-9 ;
const double PI = 3.1415926535897932384626433832795 ;
using namespace std ;
inline ll GCD(ll A, ll B){
      if ( B == 0 ) return A;
      return GCD( (B) ,  (A % B) );
}
inline ll POW(ll BASE, ll EXP) {
   ll RES = 1;
   for(ll I= 0; I < EXP; I++) RES *= BASE ;
   return RES;
}

inline ll BIGMOD  ( ll a, ll p, ll m ) {
   ll res = 1 % m;
   ll x = a % m;
   while ( p > 0 ) {
       if ( (p & 1) > 0 ) res = ( res * x ) % m;
       x = ( x * x ) % m; p >>= 1;
   }
   return res;
}
inline void FILE_HANDLE( ){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

}

int main()
{
            TURBO;
            //FILE_HANDLE() ;
            int c ;
            cin >> c ;
            ll cst = 0 ;
            int x = c / 500 ;
            c = c % 500 ;
            cst += x * 1000 ;
            x = c / 5 ;
            cst += x * 5 ;
            cout << cst << endl ;

}



Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
const int N=2050000;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
	for(;!isdigit(ch);ch=getchar()) f=ch=='-';
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-48;
	return f?-x:x;
}
int n,B;
int head[N],to[N<<1],nxt[N<<1],sta[N],vis[N],a[N],al[N];
vector<int> scc;

void lnk(int x,int y){
	to[++B]=y,nxt[B]=head[x],head[x]=B;
}
void dfs(int x,int prt){
	if(vis[x]){
		//printf("-> %d %d %d %d\n",x,prt,vis[x],sta[0]);
		for(int i=vis[x];i<=sta[0];++i) scc.push_back(sta[i]);
		return;
	}
	sta[++sta[0]]=x,vis[x]=sta[0];
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt) dfs(to[i],x);
	vis[x]=0;--sta[0];
}
void DFS(int x,int prt){
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) DFS(to[i],x);
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) al[a[to[i]]]=1;
	while(al[a[x]]) ++a[x];
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) al[a[to[i]]]=0;
}
int main(){
	n=rd();
	for(int i=1;i<=n;++i) lnk(rd(),i);
	for(int i=1;i<=n;++i) if(!scc.size()) dfs(i,0);
	for(auto x:scc) vis[x]=1;
	for(auto x:scc) DFS(x,0);
	int mx=-n-100,mn=n+100;
	for(auto x:scc) mx=max(mx,a[x]),mn=min(mn,a[x]);
	puts((mx==mn&&scc.size()%2!=0)?"IMPOSSIBLE":"POSSIBLE");
}

Measured memory_bytes: 29300
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

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

ll gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;

void solve()
{
	int x,n;
	cin>>x>>n;
	vector<int>p(n);
	set<int>st;
	rep(i,n)cin>>p[i],st.emplace(p[i]);
	int ans=0;
	int minv=1e5;
	REP(i,-1000,1000){
		if(st.count(i))continue;
		if(chmin(minv,abs(x-i))){
			ans=i;
		}
	}
	cout<<ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


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

int main() {
    int a, cnt = 0;
    cin >> a;
    set<int> st;
    do {
       st.insert(a);
       cnt++;
       if(a % 2) a = 3 * a + 1;
       else a /= 2;
    } while(cnt == st.size());
    cout << cnt << endl;
}

Measured memory_bytes: 256
def main():
    h, w, a, b = map(int, input().split())
    s = [[] for _ in [0] * h]
    for i in range(b):
        s[i] = "0" * a + "1" * (w - a)
    for i in range(b, h):
        s[i] = "1" * a + "0" * (w - a)
    for i in s:
        print(i)
main()

Measured memory_bytes: 5108
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    VI a(n);
    int sum = 0;
    REP(i, n) {
        cin >> a[i];
        sum += a[i];
    }

    int ans1 = 0;
    int avr1 = sum / n;
    REP(i, n) ans1 += (a[i] - avr1) * (a[i] - avr1);
    int ans2= 0;
    int avr2 = (sum + n - 1) / n;
    REP(i, n) ans2 += (a[i] - avr2) * (a[i] - avr2);
    cout << min(ans1, ans2) << endl;
    return 0;
}


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

int main(){

  int A[5];
  cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4];
  if(!A[0]) cout << 1 << endl;
  if(!A[1]) cout << 2 << endl;
  if(!A[2]) cout << 3 << endl;
  if(!A[3]) cout << 4 << endl;
  if(!A[4]) cout << 5 << endl;

}

Measured memory_bytes: 3580
#include<iostream>
using namespace std;
int main()
{
  int a[2][2];
  for(int i=0;i<2;i++)
  {
    for(int j=0;j<2;j++)
    {
      cin>>a[i][j];
    }
  }
  if(a[0][0]==1)
  {
    if(a[0][1]==31)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==2)
  {
    if(a[0][1]==28)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==3)
  {
    if(a[0][1]==31)
      cout<<"1";
    else
      cout<<"0";
  }
   if(a[0][0]==4)
  {
    if(a[0][1]==30)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==5)
  {
    if(a[0][1]==31)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==6)
  {
    if(a[0][1]==30)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==7)
  {
    if(a[0][1]==31)
      cout<<"1";
    else
      cout<<"0";
  }
 else  if(a[0][0]==8)
  {
    if(a[0][1]==31)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==9)
  {
    if(a[0][1]==30)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==10)
  {
    if(a[0][1]==31)
      cout<<"1";
    else
      cout<<"0";
  }
 else  if(a[0][0]==11)
  {
    if(a[0][1]==30)
      cout<<"1";
    else
      cout<<"0";
  }
  else if(a[0][0]==12)
  {
    if(a[0][1]==31)
      cout<<"1";
    else
      cout<<"0";
  }
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;
const int LOG_N = 17;

vector<int> G[MAX_N];

int par[LOG_N][MAX_N];
int depth[MAX_N];

void dfs(int u,int p,int d)
{
    par[0][u] = p;
    depth[u] = d;
    rep(i,G[u].size()){
        if(G[u][i] != p){
            dfs(G[u][i],u,d+1);
        }
    }
}

int lca(int u,int v)
{
    if(depth[u] > depth[v]){
        swap(u,v);
    }
    rep(i,LOG_N){
        if((depth[v] - depth[u]) & (1 << i)){
            v = par[i][v];
        }
    }
    if(u == v){
        return u;
    }
    for(int i=LOG_N-1;i>=0;i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

int main()
{
    int n;
    cin >> n;
    rep(i,n){
        int m;
        scanf("%d",&m);
        rep(j,m){
            int x;
            scanf("%d",&x);
            G[i].pb(x);
        }
    }
    dfs(0,-1,0);
    rep(i,LOG_N-1){
        rep(j,n){
            if(par[i][j] < 0){
                par[i+1][j] = -1;
            }else{
                par[i+1][j] = par[i][par[i][j]];
            }
        }
    }
    int q;
    cin >> q;
    rep(i,q){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

Measured memory_bytes: 20336
#include <bits/stdc++.h>
using namespace std;
#define int long long int
void solve(){
  int N;
  cin>>N;
  int arr[N];
  int mx = 0;
  int ans = 0;
  for(int i=0;i<N;i++){
    cin>>arr[i];
    if(arr[i]<mx){
      ans += mx-arr[i];
      arr[i] = mx;
    }
    mx = max(arr[i], mx);
  }
  cout<<ans<<endl;
}
signed main(){
  // int t;
  // cin>>t;
  // while(t--)
    solve();
}


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

typedef long double ld;

const ld EPS = 1e-9;
const ld INF = 1e10;
const ld PI = M_PI;

struct Point{
  ld x, y;
  Point(ld x, ld y):x(x), y(y){}
  Point(){}
};

Point operator+(const Point &a, const Point &b){
  return Point(a.x + b.x, a.y + b.y);
}
Point operator-(const Point &a, const Point &b){
  return Point(a.x - b.x, a.y - b.y);
}
Point operator*(const Point &a, const ld b){
  return Point(a.x * b, a.y * b);
}
Point operator*(const Point &a, const Point &b){
  return Point(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
}
Point operator/(const Point &a, const ld b){
  return Point(a.x / b, a.y / b);
}

bool eq(ld a, ld b){
  return abs(a-b) < EPS;
}

// 外積
ld cross(const Point &a, const Point &b){
  return a.x*b.y - a.y*b.x;
}
// 内積
ld dot(const Point &a, const Point &b){
  return a.x*b.x + a.y*b.y;
}
ld norm(const Point &a){
  return dot(a, a);
}

bool operator<(const Point &a, const Point &b){
  return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}
bool operator==(const Point &a, const Point &b){
  return a.x == b.x && a.y == b.y;
}


typedef vector<Point> Polygon;
Point next(const Polygon &a, int x){
  return a[(x+1)%a.size()];
}
Point prev(const Polygon &a, int x){
  return a[(x-1+a.size()) % a.size()];
}

// Counter Clock Wise 判定
int ccw(Point a, Point b, Point c){
  b = b - a;
  c = c - a;
  if(cross(b, c) > EPS) return +1; // 反時計周り
  if(cross(b, c) < -EPS) return -1; // 時計周り
  if(dot(b, c) < 0) return +2; // c -- a -- b がこの順番に一直線上
  if(norm(b) < norm(c)) return -2; // a -- b -- c がこの順番に一直線上
  return 0; // a -- c -- b が一直線上
}

bool compare(const Point &a, const Point &b){
  if(eq(a.y, b.y)) return a.x < b.x;
  return a.y < b.y;
}


Polygon convex_hull(Polygon ps){
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end(), compare);
  Polygon ch(2*n);
  for(int i = 0 ; i < n ; i++){
    while(k > 1 && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;    
    ch[k++] = ps[i];
  }
  int t = k;
  for(int i = n-2 ; i >= 0 ; i--){
    while(k > t && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
    ch[k++] = ps[i];
  }
  ch.resize(k-1);
  return ch;
}

int main(){
  int n;
  while(cin >> n, n){
    Polygon poly;
    
    double x, y;
    for(int i = 0 ; i < n ; i++){
      scanf("%lf,%lf", &x, &y);
      poly.push_back(Point(x, y));      
    }
    
    Polygon con = convex_hull(poly);    
    int ans = poly.size() - con.size();
    cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1292
#include "bits/stdc++.h"
#define REP(i, m, n) for(long long i = m; i < n; ++i)
#define CO(n) cout << n << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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

int H,W;
int total = 0;
char s[50][50];
int d[50][50];

void bfs(){
    queue<P> que;
    REP(i,0,H){
        REP(j,0,W) d[i][j]=Inf;
    }
    que.push(P(0,0));
    d[0][0]=1;
    while (que.size()){
        P p = que.front(); que.pop();
        int x = p.first; int y = p.second;
        if (x == (H-1) && y == (W-1)) break;
        REP(i,0,4){
            int nx = x+dx[i]; int ny = y+dy[i];
            if (0<=nx && nx<H && 0<=ny && ny<W && s[nx][ny]!='#' && d[nx][ny]==Inf){
                que.push(P(nx,ny));
                d[nx][ny] = d[x][y]+1;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> H >> W;
    REP(i,0,H){
        REP(j,0,W){
            cin >> s[i][j];
            if (s[i][j]=='.') ++total;
        }
    }
    bfs();
    /*
    REP(i,0,H){
        REP(j,0,W) cout << d[i][j];
        cout << endl;
    }
    CO(total);*/
    CO(max(-1, total-d[H-1][W-1]));
    return 0;
}

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

#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<30)
#define INFLL (1LL<<62LL)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int I[3];
  cin >> I[0] >> I[1] >> I[2]; 
  sort(I, I + 3);

  if (I[0] == I[1] && I[1] == I[2]) {
    if (I[0] % 2) {
      cout << "0" << endl;
    } else {
      cout << "-1" << endl;
    }
    return 0;
  }

  int cnt = 0;
  while (true) {
    if (I[0] % 2 != 0 || I[1] % 2 != 0 || I[2] % 2 != 0) break;

    cnt += 1;
    int NI[3] = {(I[0] + I[1]) / 2, (I[1] + I[2]) / 2, (I[2] + I[0]) / 2};
    I[0] = NI[0];
    I[1] = NI[1];
    I[2] = NI[2];

    sort(I, I + 3);
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
//#include <windows.h>
#include <algorithm>
#include <cstdio>
#include <list>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <fstream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cstdlib>
#include <cmath>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define INF 1000000007
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef priority_queue<P, vector<P>, greater<P> > minPQ;
struct edge {int to,cost;};
//const int SIZE = 1<<18;

int main() {
	int A,B,C,D;
	cin >> A >> B >> C >> D;
	if(A*B > C*D) {
		cout << A*B << endl;
	} else {
		cout << C*D << endl;
	}
	return 0;
}

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

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

    long long int n,k;
    cin >> n >> k;

    if(n>k){
        cout << min(abs(n%k - k), n%k) << endl;
    }
    else{
        map<long long int, bool> visited;
        visited[n] = false;
        long long int minval = n;
        while(!visited[n]){
            visited[n] = true;
            minval = min(minval, n);
            n = abs(n-k);
        }
        cout << minval << endl;
    }
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> d(n);
    int ans = 0;

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

    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            ans += d[i]*d[j];
        }
    }
    cout << ans;
}

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

using namespace std;

int main() {
  long long N, K;
  
  cin >> N >> K;
  
  vector<long long> A;
  vector<long long> A_bits(60, 0);
  
  for (int i = 0; i < N; i++) {
    long long in;
    
    cin >> in;
    
    A.push_back(in);
    
    for (int j = 0; j < 60; j++) {
      if (in & (1ll << j)) {
        A_bits[j]++;
      }
    }
  }
  
  long long x = 0ll;
  long long ans = 0ll;
  
  for (int i = 60; i >= 0; i--) {
    if (A_bits[i] < N - A_bits[i] && (x | (1ll << i)) <= K) {
      x |= 1ll << i;
    }
  }
  
  for (int i = 0; i < N; i++) {
    ans += A[i] ^ x;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 1400
n,x = map(int,input().split())
narr = list(map(int,input().split()))
c=0
for i in range(1,n):
    total = narr[i]+narr[i-1]
    if(total <= x):
        continue
    else:
        c += (total - x)
        narr[i] = max(0,narr[i]-(total-x))
print(c)


Measured memory_bytes: 19952
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define eb emplace_back
#define mp make_pair
using namespace std;
const int MAX_N=1e6+10;
bool dp[MAX_N];
int n;
int main(){
    dp[0]=true;
    for(int i=100;i<=105;i++){
        for(int j=i;j<MAX_N;j++){
            if(dp[j-i]){
                dp[j]=true;
            }
        }
    }
    cin>>n;
    cout<<dp[n]<<endl;
    return 0;
}

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

using namespace std;


const int INF = 1e9;
const int MAX_V = 1000;

struct Flow{
    struct edge{
        int to, cap, rev;
    };
    vector<edge> G[MAX_V];//隣接リスト
    bool used[MAX_V];

    void add_edge(int from, int to, int cap){
        G[from].push_back((edge){to, cap, (int)G[to].size()});//from -> to
        G[to].push_back((edge){from, 0, (int)G[from].size() - 1});//to -> from
    }

    //増加パスを探す
    int dfs(int v, int t, int f){
        if(v == t) return f;
        used[v] = true;
        for (int i = 0; i < G[v].size(); ++i){
            edge &e = G[v][i];
            if(!used[e.to] && e.cap > 0){
                int d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    //sからtへの最大流
    int max_flow(int s, int t){
        int flow = 0;
        while(1){
            memset(used, 0, sizeof(used));
            int f = dfs(s, t, INF);
            if(f == 0) return flow;
            flow += f;
        }
    }
};

int main(){
int X,Y,E; cin >> X >> Y >> E;
  Flow mf;
  for(int i = 0; i < E; i++){ int x,y;  cin >> x >> y; y += X;
    mf.add_edge(x,y,1);// directed expression
                            }
  
  for(int i = 0; i < X; i++){
    mf.add_edge( X + Y, i, 1); }
  
  for(int j = 0; j < Y; j++){
    mf.add_edge(X + j, X + Y + 1, 1);}
  
  cout << mf.max_flow( X + Y,  X  +  Y  + 1 ) <<  endl;
  return 0;}
  
    


Measured memory_bytes: 3380
#include <bits/stdc++.h>
 
#define rep(i,x) for(int i=0;i<x;i++)    
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rep_to(a,i,x) for(int i=a;i<x;i++)
 
using namespace std;
 
int main()
{
    int x,y,s;
    while(cin >> x >> y >> s && s)
    {
    	int mx=0;
    	
    	for(int i=1;i<1000;i++)
    	{
    		int num1=i*(100+x)/100;
    		int num2=i*(100+y)/100;

    		for(int j=1;j<1000;j++)
    		{
    			int num3=j*(100+x)/100;
    			int num4=j*(100+y)/100;

    			if(num1+num3==s)mx=max(mx,num2+num4);
    		}
    	}
    	cout << mx << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<stdio.h>
long long dp[2][21];
int main(){
	int n;
	scanf("%d",&n);
	int i,j;
	for(i=0;i<=20;i++)dp[1][i]=0;
	int x;
	scanf("%d",&x);
	dp[1][x]=1;
	for(i=0;i<n-2;i++){
		int x;
		scanf("%d",&x);
		for(j=0;j<=20;j++){
			dp[i%2][j]=0;
			if(j+x<=20)dp[i%2][j]+=dp[(i+1)%2][j+x];
			if(j-x>=0)dp[i%2][j]+=dp[(i+1)%2][j-x];
		}
	}
	scanf("%d",&x);
	printf("%lld\n",dp[(n-1)%2][x]);
	return 0;
}

Measured memory_bytes: 1028
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        if(a < b){
            System.out.println("a < b");
        }else if (a > b){
            System.out.println("a > b");
        }else{
            System.out.println("a == b");
        }
        sc.close();
    }
}


Measured memory_bytes: 26224
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int L=4000005,N=2005,M=1e9+7;
int fac[L],inv[L],dp[N][N],n,m;
int ksm(int x,int y){
	if (!y)return 1;
	int z=ksm(x,y/2);
	z*=z;z%=M;
	if (y&1)z*=x;
	return z%M;
}
int C(int x,int y){
	return fac[x]*inv[y]%M*inv[x-y]%M;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	if (m==1){
		puts("1");
		return 0;
	}
	fac[0]=inv[0]=1;
	for (int i=1;i<L;i++)fac[i]=fac[i-1]*i%M;
	inv[L-1]=ksm(fac[L-1],M-2);
	for (int i=L-2;i>=0;i--)inv[i]=(i+1)*inv[i+1]%M;
	dp[0][0]=1;
	for (int i=1;i<=n;i++)
		for (int j=0;j<=i;j++)
			dp[i][j]=((j>0?dp[i][j-1]:0)+dp[i-1][j]*C((i-1)*m-(i-j-1)+m-2,m-2))%M;
	printf("%lld\n",dp[n][n]*fac[n]%M);		
}

Measured memory_bytes: 92672
N=int(input())
H=list(map(int,input().split()))

if N==1:
    print('Yes')
else:
    for i in range(N-1):
        if H[N-i-2]>= H[N-i-1]+2:
            print('No')
            exit()
        elif H[N-i-2]==H[N-i-1]+1:
            H[N-i-2]-=1
    
    for j in range(N-1):
        if  H[i]>H[i+1]:
            print('No')
            exit()
    print('Yes')
            

Measured memory_bytes: 20824
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f;
const double pi=acos(-1.0),eps=1e-8;
const ll mod = 1e9+7;
const int inf = 1e18;
const int maxn = 5e5+5;
int main()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = max(a * c, a * d);
    ans = max(ans, b * c);
    ans = max(ans, b * d);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#include "atcoder/all"

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

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

    vector<int> ps(n * n);
    rep(i, n * n) cin >> ps[i], ps[i]--;

    vector<vector<int>> theater(n, vector<int>(n));
    vector<vector<bool>> exists(n, vector<bool>(n, true));

    rep(y, n) {
        rep(x, n) {
            theater[y][x] = min({y, n - 1 - y, x, n - 1 - x});
        }
    }


    auto update = [&](int ys, int xs) {
        queue<P> q;
        q.push({ys, xs});

        struct Direction {
            int y, x;
        };

        vector<Direction> directions = {
                {0,  1},
                {1,  0},
                {0,  -1},
                {-1, 0},
        };
        auto reachable = [&](int y, int x) {
            if (x == -1 || x == n || y == -1 || y == n) return false;
            return true;
        };
        while (!q.empty()) {
            P p = q.front();
            int y = p.first;
            int x = p.second;
            q.pop();
            for (Direction d : directions) {
                int nx = x + d.x;
                int ny = y + d.y;
                if (!reachable(ny, nx)) {
                    continue;
                }

                if (theater[ny][nx] > theater[y][x] + exists[y][x]) {
                    theater[ny][nx] = theater[y][x] + exists[y][x];
                    q.push({ny, nx});
                }
            }

        }
    };

    ll ans = 0;
    for (ll p : ps) {
        int y = p / n;
        int x = p % n;

        ans += theater[y][x];
        exists[y][x] = false;
        update(y, x);
    }

    cout << ans << endl;

}


Measured memory_bytes: 5232