akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>

using namespace std;

const int MAXN = 200000 + 1000;

int n;
vector<int> edg[MAXN], redg[MAXN];
vector<int> cir;
bool onc[MAXN], vis[MAXN];
int val[MAXN];

int find_circle(int x)
{
	vis[x] = true;
	for(int i = 0; i < redg[x].size(); i++)
	{
		int y = redg[x][i], tmp = vis[y] ? y : find_circle(y);
		if(tmp)
		{
			cir.push_back(x), onc[x] = true;
			return x == tmp ? 0 : tmp;
		}
	}
	return 0;
}

bool h[MAXN];

// bool check_one(int x)
// {
// 	for(int i = 0; i < edg[x].size(); i++)
// 		h[val[edg[x][i]]] = true;
// 	int t = 0;
// 	while(h[t]) t++;
// 	for(int i = 0; i < edg[x].size(); i++)
// 		h[val[edg[x][i]]] = false;
// 	return t == val[x];
// }

// int tot = 0;
// bool check()
// {
// 	for(int x = 1; x <= n; x++)
// 	{
// 		if(!check_one(x))
// 			cerr << "ERROR!!!" << ' ' << (++tot) << endl;
// 	}
// }

void assign_tree(int x)
{
	for(int i = 0; i < edg[x].size(); i++)
		assign_tree(edg[x][i]);
	for(int i = 0; i < edg[x].size(); i++)
		h[val[edg[x][i]]] = true;
	val[x] = 0;
	while(h[val[x]])
		val[x]++;
	for(int i = 0; i < edg[x].size(); i++)
		h[val[edg[x][i]]] = false;
}

// void dfs(int x)
// {
// 	if(check_one(x))
// 		cerr << (++tot) << endl;
// 	cerr << x << ' ' << val[x] << endl;
// 	for(int i = 0; i < edg[x].size(); i++)
// 		cerr << x << ' ' << edg[x][i] << endl, dfs(edg[x][i]);
// }

void yes()
{
	cout << "POSSIBLE" << endl;
	exit(0);
}

void no()
{
	cout << "IMPOSSIBLE" << endl;
	exit(0);
}

void assign_circle()
{
	for(int i = (int)cir.size() - 1; i >= 0; i--)
	{
		int x = cir[i];
		for(int j = 0; j < edg[x].size(); j++)
			h[val[edg[x][j]]] = true;
		val[x] = 0;
		while(h[val[x]])
			val[x]++;
		for(int j = 0; j < edg[x].size(); j++)
			h[val[edg[x][j]]] = false;
	}
}

void work()
{
	int cir0 = cir[0];
	for(int i = 0; i < edg[cir0].size(); i++)
		if(!onc[edg[cir0][i]])
			h[val[edg[cir0][i]]] = true;
	int tmp1 = 0, tmp2 = 0;
	while(h[tmp1])
		tmp1++;
	tmp2 = tmp1 + 1;
	while(h[tmp2])
		tmp2++;
	for(int i = 0; i < edg[cir0].size(); i++)
		if(!onc[edg[cir0][i]])
			h[val[edg[cir0][i]]] = false;

	val[cir0] = tmp1;
	assign_circle();
	// for(int i = 1; i <= n; i++)
	// 	cout << val[i] << endl;
	if(val[cir0] == tmp1)
		yes();
	val[cir0] = tmp2;
	assign_circle();
	if(val[cir0] == tmp2)
		yes();
	no();
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		edg[x].push_back(i), redg[i].push_back(x);
	}
	find_circle(1);
	// cerr << cir.size() << endl;
	// assert(cir.size());

	// for(int i = 0; i < cir.size(); i++)
	// 	cerr << cir[i] << endl;

	for(int i = 0; i < cir.size(); i++)
		for(int j = 0; j < edg[cir[i]].size(); j++)
			if(!onc[edg[cir[i]][j]])
				assign_tree(edg[cir[i]][j]);
	// for(int i = 1; i <= n; i++)
	// 	cerr << i << ' ' << edg[i].size() << ' ' << redg[i].size() << endl;
	// check();
	work();


	return 0;
}


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

int main() {
	int a;
	int b;
	cin >> a >> b;
	int ave = (a + b) / 2;
	int amari = (a + b) % 2;
	if (amari != 0) {
		ave = ave + 1;
	}
	cout << ave << endl;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

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

LL cnt[128];
const LL M=1e9+7;
int main() {
	int N;
	string S;
	cin >> N>>S;
	for(auto c:S)
	{
		cnt[(int)c]++;
	}
	LL ret=1;
	for(int i='a';i<='z';i++)
	{
		ret*=cnt[i]+1;
		ret%=M;
	}
	cout << (ret+M-1)%M << endl;

	return 0;
}



Measured memory_bytes: 1144
def f(a):
    for i in a:
        if i % 2 == 0 and (i % 3 != 0 and i % 5 != 0):
            print('DENIED')
            break
    else:
        print('APPROVED')

n = int(input())
a = list(map(int, input().split()))
f(a)


Measured memory_bytes: 2940
#include<stdio.h>
int main(void){
  int n,k,x,y,a=0,i;
  scanf("%d%d%d%d",&n,&k,&x,&y);
  for (i=0;i<((k<n)?k:n);i++)
    a+=x;
  for (;i<n;i++)
    a+=y;
  printf("%d\n",a);
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>

int isprime(int);

int main() {
  static int sosu[1000000];
  int i;
  int size, in;

  sosu[0] = 2;
  size = 1;
  for(i = 3; i <= 999999; i += 2) {
    if(isprime(i)) sosu[size++] = i;
  }

  while(scanf("%d", &in) != EOF) {
    for(i = 0; i < size; i++) {
      if(sosu[i] == in) {
	i++;
	break;
      }
      if(sosu[i] > in) {
	break;
      }
    }
    printf("%d\n", i);
  }
  return 0;
}

int isprime(int x) {
  int i;
  if(x == 1) return 0;
  if(x == 2) return 1;
  if(x % 2 == 0) return 0;
  for(i = 3; i <= (int)sqrt(x); i += 2) {
    if(x % i == 0) return 0;
  }
  return 1;
}

Measured memory_bytes: 588
use std::cmp::min;
use std::io::stdin;

fn main() {
    let n: usize = {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        s.trim().parse().unwrap()
    };

    let mut a: Vec<i64> = {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        s.split(' ').map(|x| x.trim().parse().unwrap()).collect()
    };

    // 二分探索をする

    let mut lo = 0;
    let mut hi = min(a[0], a[n - 1]);

    loop {
        let mid = lo + (hi - lo) / 2;
        match check(&mut a.clone(), mid, false) {
            R::Ok => {
                check(&mut a, mid, true);
                return;
            }
            R::Much => hi = mid - 1,
            R::Little => lo = mid + 1,
        }
    }
}

enum R {
    Ok,
    Much,
    Little,
}

fn check(a: &mut [i64], mut v: i64, show: bool) -> R {
    if show {
        print!("{}", v * 2);
    }

    *a.last_mut().unwrap() -= v;
    for i in 0..a.len() {
        a[i] -= v;
        if a[i] < 0 {
            if i % 2 == 0 {
                return R::Much;
            } else {
                return R::Little;
            }
        }
        v = a[i];
        if show && i != a.len() - 1 {
            print!(" {}", v * 2);
        }
    }

    if show {
        println!();
    }

    match *a.last().unwrap() {
        0 => R::Ok,
        x if x > 0 => R::Little,
        x if x < 0 => R::Much,
        _ => unreachable!(),
    }
}



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

using namespace std;

using ll = long long;
using ld = long double;

#define mp make_pair

const int p = 999983;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}


mt19937 rnd(time(0));

/*struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};*/

/*
const int N = 1200000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    if (n<k) return 0;
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}
*/



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    ll a, b;
    cin>>a>>b;

    ll res = 0;


    ll MAXX = (1ll<<60);

    for (int i = 60; i>=0; i--)
    {

        ll N = (1ll<<i);
        if ((a&N) && (b&N))
        {
            a-=N; b-=N;
            MAXX-=N;
        }

        if (a==b && a<=MAXX)
        {
            res++; break;
        }

        if (((a&N) == 0) && ((b&N) != 0))
        {
            //cout<<i<<": "<<res<<' '<<a<<' '<<b<<' '<<MAXX<<endl;
            if (a+N<=b+1)
            {
                res+=(min(2*N, MAXX+1) - a);
                break;
            }
            else
            {
                res+=(N-a);
                if (MAXX>=N+a) res+=min(2*N-1, MAXX) - (a+N) + 1;
                MAXX = a-1;
                a = 0; b = b-N;

            }
        }
    }


    cout<<res;

}



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

unsigned long long luka(unsigned long long n,
                        vector<unsigned long long> &memo) {
  if (n == 0)
    return 2;
  else if (n == 1)
    return 1;
  else if (memo.at(n)) {
    return memo.at(n);
  } else {
    memo.at(n) = luka(n - 1, memo) + luka(n - 2, memo);
    return memo.at(n);
  }
}

int main() {
  unsigned long long n;
  scanf("%llu", &n);
  vector<unsigned long long> memo(87, 0);
  printf("%llu\n", luka(n, memo));
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  long a,b,c,x,y;
  scanf("%ld %ld %ld %ld %ld", &a, &b, &c, &x, &y);

  long price;
  if (a+b <= c*2) {
    price = a*x+b*y;
  } else {
    if (x <= y) {
      price = c*2*x;
      if (b <= c*2) {
        price += b*(y-x);
      } else {
        price += c*2*(y-x);
      }
    } else {
      price = c*2*y;
      if (a <= c*2) {
        price += a*(x-y);
      } else {
        price += c*2*(x-y);
      }
    }
  }
  printf("%ld\n", price);

  return 0;
}

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

int main(void) {
	string s;
	cin >> s;
	int ans = s.size();
	for (int i = 0; i < 2; i++) {
		int cnt = 0;
		for (int j = 0; j < s.size(); j++) {
			if (j % 2 == 0 && s[j] != (char)(i + '0')) cnt++;
			if (j % 2 == 1 && s[j] == (char)(i + '0')) cnt++; 
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 512
s=input()
kouho=set()
for i in range(2**4):
    word=list("AKIHABARA".replace("A","x"))# xの部分にAをいれるかいれないか
    if i&(1<<0):
        word[0]="A"
    if i&(1<<1):
        word[4]="A"
    if i&(1<<2):
        word[-3]="A"
    if i&(1<<3):
        word[-1]="A"
    k="".join(word)
    k=k.replace("x","")
    kouho.add(k)

if s in kouho:
    print('YES')
else:
    print('NO')
    


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));


int main(){	
	string N;
	cin >> N;
	ll res = 0, sum = 0;
	rep(i, N.length()) {
		ll now = N[i]-'0';
		if (now != 0) {
			res = max(res, sum+now-1+9*((ll)N.length()-1-i));
		}
		sum += now;
	}
	res = max(res, sum);
	cout << res << endl;
	return 0;
}



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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  
  for(int i = 0; i < n; ++i){
    cin >> a[i];
  }
  
  int ans = 0;
  
  while(true){
	bool odd = false;
	for(int i = 0; i < n; ++i){
		if(a[i]%2 != 0) odd = true;
	}
	if(odd) break;
	
	for(int i = 0; i < n; ++i){
		a[i] /= 2;
	}
	++ans;
  }
  cout << ans << endl;
	  
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.nextLine();
		
		char[] c = s.toCharArray();
		
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<c.length; i++) {
			if (c[i] == '0' | c[i] == '1') {
				sb.append(c[i]);
			} else if (c[i] == 'B') {
				if (sb.length() > 0) {
					sb.deleteCharAt(sb.length()-1);
				}
			}
		}
		
		System.out.println(sb.toString());
	}

}


Measured memory_bytes: 25300
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<map>
using namespace std;
int main(){
  int n;
  cin>>n;
  for(int i=1;i<10;i++){
    if(n%i==0&&n/i<10){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var N, ans int
	var now int
	fmt.Scan(&N)
	A := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&A[i])
	}
	for i := 1; i < 40; i++ {
		now = 1
		for j := 0; j < N; j++ {
			if A[j]%2 == 0 {
				A[j] /= 2
			}else{
				now = 0
				break
			}
		}
		if now == 0 {
			break
		}else{
			ans = i
		}
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
#include<iostream>
using namespace std;
int main(){
  int n,p[50],i,cnt=0;
  cin>>n;
  for(i=0; i<n; i++){
    cin>>p[i];
    if((i+1)!=p[i]){
      cnt++;
    }
  }
  if(cnt==0 || cnt==2){
    printf("YES\n");
  }
  else{
    printf("NO\n");
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

bool is_prime[1000010];
int main() {
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    for (int i = 0; i < k; ++i) {
        if(b <= a){
            b *= 2;
        }else if(c <= b){
            c *= 2;
        }
    }
    if(a < b && b < c){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
  int n,sub,maxi = 0,total = 0;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> sub;
    maxi = max(maxi,sub);
    total += sub;
  }
  cout << total - maxi / 2 << endl;
}

Measured memory_bytes: 256
/*
Dont BLUNDER
*/

// #pragma GCC optimize("O3")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<climits>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;


 */
//#define d long double
#define int long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define pi acos(-1)

#define init(x,a) memset(x,a,sizeof(x))
#define all(c) c.begin(),c.end()
int const mod1 = 998244353;
int const mod = 1000000007;
#define bitcount(x)       __builtin_popcountll(x)
#define l first
#define r second
const int inf = LLONG_MAX;
int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ) {stringstream ss; ss << number; return ss.str();}
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define haha ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// * Using PBDS *
/*typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
               os; */

struct cmp
{
	bool operator() (pii a, pii b) {
		return (a.l < b.l);
	}
};

int modexp(int x, int n) {
	if (n == 0) {
		return 1;
	}
	else if (n & 1) {
		return (modexp((x * x) % mod, n / 2) % mod * x % mod) % mod;
	}
	else {
		return (modexp((x * x) % mod, n / 2) % mod);
	}
}

int modinv(int n)
{
	return modexp(n, mod - 2);
}

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}



signed main()
{
	haha
#ifndef ONLINE_JUDGE

	freopen("inp.txt", "r", stdin);

	freopen("out1.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	int c = 0;
	int f = 0;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		if (x == y) {
			c++;
		}
		else
			c = 0;
		if (c >= 3)
			f = 1;

	}
	if (f == 1) {
		cout << "Yes";
	}
	else
		cout << "No";


















}


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

}

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

fn main(){
    let n = read_as_vec::<u64>()[0];
    println!("{}", ((n as f64).sqrt().floor() as u64).pow(2));
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define int long long int

bool sortbydec(const pair<int,int> &a , const pair<int,int> &b)
{
    return a.first>b.first;
}

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

Measured memory_bytes: 3912
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    int m;
    bool flg = false;
    for (int i = 0; i < (N / 4) + 1; i++) {
        m = N - 4 * i;
        if (m % 7 == 0) {
            flg = true;
        }
    }
    if (flg) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

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> P;
typedef pair<ll, ll> PL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define fout(x) cout << fixed << setprecision(10) << x << endl
//#define int long long int
const int MOD = 1000000007;
const ll LINF = (ll)1e18 - 1;
const int INF = 1e9 - 1;
const double EPS = 0.000000001;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

auto print = [](auto &v) {
  for(auto x : v) {
    cout << x << " ";
  }
  cout << endl;
};

int bfs(vector<vector<char>> &s, int i, int j, int h, int w) {
  queue<tuple<int, int, int>> q;
  vector<vector<bool>> vis(h, vector<bool>(w, false));
  q.push(make_tuple(j, i, 0));
  int ret = 0;
  vis[i][j] = true;
  while(!q.empty()){
    int x, y, d;
    tie(x, y, d) = q.front(); q.pop();
    ret = max(ret, d);
    rep(k, 4) {
      if(x + dx[k] < 0 || x + dx[k] > w - 1) continue;
      if(y + dy[k] < 0 || y + dy[k] > h - 1) continue;
      if(s[y + dy[k]][x + dx[k]] == '#') continue;
      if(vis[y + dy[k]][x + dx[k]]) continue;
      q.push(make_tuple(x + dx[k], y + dy[k], d + 1));
      vis[y + dy[k]][x + dx[k]] = true;
    }
  }
  return ret;
}

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ans = 0;
  int h, w;
  cin >> h >> w;
  vector<vector<char>> s(h, vector<char>(w));
  rep(i, h) rep(j, w) cin >> s[i][j];
  rep(i, h) rep(j, w) {
    if(s[i][j] == '#') continue;
    ans = max(ans, bfs(s, i, j, h, w));
  }
  out(ans);
  return 0;
}


Measured memory_bytes: 256
N,Y = map(int, input().split())

for i in range(N,-1,-1):
    for j in range(N-i,-1,-1):
        k = N - i - j
        if k >= 0 and 10000 * i + 5000 * j + 1000 * k == Y:
            print(i, j, k)
            break
    else:
        continue
    break
else:
    print('-1 -1 -1')

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

int A, B, C;

int main() {
    cin >> A >> B >> C;

    if(A % 2 == B % 2 && A % 2 == C % 2) {
        int mx = max(max(A, B), C);
        cout << (mx - A) / 2 + (mx - B) / 2 + (mx - C) / 2;
        return 0;
    }
    else if(A % 2 != B % 2 && A % 2 != C % 2) {
        B++;
        C++;
    }
    else if(B % 2 != A % 2 && B % 2 != C % 2) {
        A++;
        C++;
    }
    else {
        A++;
        B++;
    }
    int mx = max(max(A, B), C);
    cout << 1 + (mx - A) / 2 + (mx - B) / 2 + (mx - C) / 2;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
// #define INF __INT32_MAX__
#define INF 1e9
#define LINF __LONG_LONG_MAX__


int main() {
    int N; cin >> N;
    vector<pair<int, int>> G;

    rep(i, N) {
        int X, L; cin >> X >> L;
        auto p = make_pair(X + L, X - L);
        G.push_back(p);
    }

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

    int cnt = 0;
    int prev = -INF;
    rep(i, N) {
        int r = G[i].first;
        int l = G[i].second;

        if (prev <= l) {
            prev = r;
            cnt++;
        }
    }

    cout << cnt << endl;
}


Measured memory_bytes: 4272
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }




long long N, Z, W;
long long a[10001];

long long dp[5100][3];

long long rec(int cur, bool sente) {
    if (dp[cur][sente] != -1) return dp[cur][sente];
    long long aite = -1;
    if (cur == 0) aite = W;
    else aite = a[cur-1];
    
    if (cur == N-1) return abs(a[N-1] - aite);
    
    long long res = -1;
    if (sente) {
        long long Max = abs(aite - a[N-1]);
        for (int j = cur; j < N-1; ++j) {
            long long tmp = rec(j+1, false);
            chmax(Max, tmp);
        }
        res = Max;
    }
    else {
        long long Min = abs(aite - a[N-1]);
        for (int j = cur; j < N-1; ++j) {
            long long tmp = rec(j+1, true);
            chmin(Min, tmp);
        }
        res = Min;
    }
    
    //cout << cur << ", " << sente << ": " << res << endl;
    
    return dp[cur][sente] = res;
}





int main() {
    while (cin >> N >> Z >> W) {
        for (int i = 0; i < N; ++i) cin >> a[i];
        memset(dp, -1, sizeof(dp));
        cout << rec(0, true) << endl;
    }
}


















Measured memory_bytes: 512
# coding: utf-8

N, K = map(int, input().split())

kaijo_d = {0: 1}


def f(n):
    if n in kaijo_d.keys():
        return kaijo_d[n]

    already = max(kaijo_d.keys())

    output = kaijo_d[already]

    for i in range(already+1, n+1):
        output *= i
        kaijo_d[i] = output

    return output


for i in range(1, K+1):
    print((f(K-1) * f(N-K+1)) // (f(i-1) * f(K-i) * f(i) * f(N-K+1-i)) % (10**9 + 7))


Measured memory_bytes: 5876
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

//_____________________________________________________________
const int MAX_NODE=1000000;

vvi G = vv(MAX_NODE, 0, 0, int);
int dfs(int from, int now){
  int ret = 0;
  for(int i=0;i<G[now].size();i++) {
    if(from == G[now][i]) continue;
    ret = max(ret, dfs(now, G[now][i])+1);
  }
  return ret;
}
int cut(int from, int now, int K, int d){
  int ret = (d>K?1:0);
  for(int i=0;i<G[now].size();i++){
    if(from==G[now][i]) continue;
    ret += cut(now, G[now][i], K, d+1);
  }
  return ret;
}
bool check(int now, int k){
  int f = 0, s = 0;
  for(int i=0;i<G[now].size();i++){
    int tmp = dfs(now, G[now][i])+1;
    if(f<tmp) s = f, f = tmp;
    else if(s<tmp) s = tmp;
  }
  return (f>=k/2+(k%2==1?1:0) && s>=k/2);
}
void treeDFS(int from, int current, int dist, int &maxDist, int &maxVertex) {
    if (dist > maxDist) maxDist = dist, maxVertex = current;
    for (auto to : G[current]) {
        if (to == from) continue;
        treeDFS(current, to, dist + 1, maxDist, maxVertex);
    }
}
int getTreeDiameter(int s) {
    int start = s, end = 0, maxDist = 0;
    treeDFS(-1, start, 0, maxDist, end);
    start = end, end = 0, maxDist = 0;
    treeDFS(-1, start, 0, maxDist, end);
    //printf("start: %d, end: %d, diameter: %d\n", start, end, maxDist);
    return maxDist;
}
int dfd(int from, int now, int d, int m){
  if(d==m) return 1;
  int ret = 0;
  for(int i=0;i<G[now].size();i++){
    if(from==G[now][i]) continue;
    ret += dfd(now, G[now][i], d+1, m);
  }
  return ret;
}
int addd(int now, int m){
  int ma = 0;
  for(int i=0;i<G[now].size();i++){
    int tmp = dfd(now, G[now][i], 1, m);
    ma = max(ma, tmp);
  }
  return ma;
}
//_____________________________________________________________
int main(int argc, char const *argv[]) {
  int N, K, a, b;
  std::cin >> N >> K;
  for(int i=0;i<N-1;i++){
    std::cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  if(getTreeDiameter(1)<=K){
    std::cout << 0 << '\n';
    return 0;
  }
  int ans = 1000000007;
  for(int i=1;i<=N;i++){
    if(check(i, K)){
      int ad = (K%2==0?0:addd(i, (K+1)/2));
      ans = min(ans, cut(-1, i, K/2, 0)-ad);
    }
  }
  std::cout << ans << '\n';
  return 0;
}


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

int main(){
  int N, M;
  cin >> N >> M;
  
  vector<int> L(M);
  vector<int> R(M);
  
  for (int i = 0; i < M; i++) { 
    cin >> L.at(i) >> R.at(i);
  }
  
  int min_L, max_R;
  
  min_L = *max_element(L.begin(), L.end());
  max_R = *min_element(R.begin(), R.end());
  
  // cout << min_L << max_R << endl;
  
  if (max_R - min_L < 0){
    cout << 0 << endl;
  }
  
  else {
    cout << max_R - min_L + 1 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1024
n,m=map(int,input().split())
div=10**9+7
if abs(n-m)>1:
  print(0)
else:
  ans=1
  for i in range(1,min(m,n)+1):
    ans=ans*i%div
  ans*=ans
  if n!=m:
    ans*=max(m,n)
  if n==m:
    ans*=2
  print(ans%div)

Measured memory_bytes: 3188
from collections import deque

N = int(input())
vw = [[] for _ in range(N)]
for i in range(N-1):
    a, b, w = map(int, input().split())
    vw[a-1].append((b-1, w))
    vw[b-1].append((a-1, w))
ans = [-1] * N
q = deque([(0, 0)])
while q:
    a, w = q.popleft()
    ans[a] = w % 2
    for b, c in vw[a]:
        if ans[b] == -1:
            q.append((b, w + c))
print("\n".join(map(str, ans)))


Measured memory_bytes: 44952
#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 rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#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
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<P> vp;

const int MAX_N = 100005;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> vec(n);
    rep(i,n){
        cin >> vec[i];
        vec[i]--;
    }
    vector<int> a(n),b(n);
    rep(i,n){
        a[i] = n*(i+1);
        b[i] = n*(n-i);
    }
    rep(i,n){
        a[vec[i]] += i;
    }
    rep(i,n){
        cout << a[i] << " ";
    }
    cout << "\n";
    rep(i,n){
        cout << b[i] << " ";
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#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 all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
struct unionfind{
	int par[100000];
	void init(int N){rep(i,N) par[i]=i;}
	int find(int x){
		if(par[x]==x) return x;
		return par[x]=find(par[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x==y) return;
		par[y]=x;
	}
}UF;
vector<int> vc[100000];
int main(){
	int N,M;
	cin>>N>>M;
	rep(i,N){
		int K;
		cin>>K;
		int p=0;
		rep(j,K){
			int x;
			cin>>x;
			x--;
			vc[x].pb(i);
		}
	}
	UF.init(N);
	rep(i,M) if(vc[i].size()>0){
		for(int v:vc[i]) UF.unite(v,vc[i][0]);
	}
	int sz=0;
	rep(i,N) if(UF.find(i)==i) sz++;
	if(sz==1) puts("YES");
	else puts("NO");
}


Measured memory_bytes: 4860
#include <stdio.h>

int main(){
	int a,b;
	scanf("%d %d",&a,&b); //??\???
	if(-1000<=a&&b<=1000){ //??¶?´?
		printf("%s\n",(a<b)?"a < b":((a>b)?"a > b":"a == b")); //???????????????
	}
	else
	{
		printf("over\n"); //?????????
	}
}

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

typedef pair<int, int> P;
const int INF = 1000000000;
vector<int> dx{1, 0, -1, 0}, dy{0, 1, 0, -1};

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> maze(H);
    for (int i = 0; i < H; i++) cin >> maze[i];

    int res = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (maze[i][j] == '.') {
                queue<P> que;
                que.push(P(i, j));
                vector<vector<int>> dist(H, vector<int>(W, INF));
                dist[i][j] = 0;
                while (!que.empty()) {
                    P p = que.front(); que.pop();
                    for (int k = 0; k < 4; k++) {
                        int nx = p.first + dx[k];
                        int ny = p.second + dy[k];
                        if (nx >= 0 && nx < H && ny >= 0 && ny < W && maze[nx][ny] != '#' && dist[nx][ny] == INF) {
                            que.push(P(nx, ny));
                            dist[nx][ny] = dist[p.first][p.second] + 1;
                        }
                    }
                }
                int max_dist = 0;
                for (int k = 0; k < H; k++) {
                    for (int l = 0; l < W; l++) {
                        if (dist[k][l] != INF) max_dist = max(max_dist, dist[k][l]);
                    }
                }
                res = max(res, max_dist);
            }
        }
    }

    cout << res << endl;
    return 0;
}

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

using namespace std;

typedef long long int lli;

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

    int n, p[30];

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

    int ans = 0;
    for (int i=1; i<n-1; i++) {
        if (p[i-1] > p[i] && p[i] > p[i+1]) ans++;
        else if (p[i-1] < p[i] && p[i] < p[i+1]) ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<algorithm>
#include<cstdlib>
using namespace std;

bool cmp(const string& a,const string b)
{
  if(a.size() != b.size())
    return a.size() < b.size();
  if(a != b)
    return (atoi)(a.c_str()) < (atoi)(b.c_str());
  return false;
}

int main()
{
  int n;
  vector<string> vec;
  cin >> n; 
  vec.resize(n);

  int men = 100000000;  
  int Size[6];
  for(int i=0;i<6;i++)
    Size[i] = 0;
  for(int i=0;i<n;i++)
    cin >> vec[i],Size[vec[i].size()]++,men = min(men,(int)vec[i].size());

  sort(vec.begin(),vec.end(),cmp);
    
  if(Size[men] >= 4)
      cout << vec[0] << vec[3] << endl;
  else if(Size[men] == 3)
    cout << vec[1] << vec[0] << endl;
  else if(Size[men] == 2)
    {
      string a,b;
      a = vec[0]+vec[2];
      b = vec[2]+vec[0];
      cout << min((atoi)(b.c_str()),(atoi)(a.c_str())) << endl;
    }
  else if(Size[men] == 1)
    {
      vector<string> ans;
      for(int i=0;i<4;i++)
	for(int j=0;j<4;j++)
	  if(i != j)
	    ans.push_back(vec[i]+vec[j]);
      sort(ans.begin(),ans.end(),cmp);
      cout << ans[2] << endl;
    }


  


  return 0;
}

Measured memory_bytes: 1652
n,k=map(int,input().split())
if n==k:
    print(1)
    for i in range(k-1):
        print(0)
    exit()
mod=1000000007
Fact=[1] #階乗
for i in range(1,n+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(n+1) #階乗の逆元
Finv[-1]=pow(Fact[-1],mod-2,mod)
for i in range(n-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<0 or r<0:
        return 0
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod

for i in range(1,k+1):
    ans=comb(k-1,i-1)*comb(n-k-1,i-2)+comb(k-1,i-1)*comb(n-k-1,i-1)*2+comb(k-1,i-1)*comb(n-k-1,i)
    print(ans%mod)

Measured memory_bytes: 43760
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rpd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
#define pb push_back
using namespace std;
const int N=2e5+5;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,d;double ans;
int main(){
	n=read();m=read();d=read();
	ans=(double)(m-1)*(double)(n-d);
	if(d!=0)ans=ans*(double)2;
	ans=ans/(double)n;ans=ans/(double)n;
	printf("%f",ans);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 1000000007
#define LINF 100000000000000007
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repb(i, n) for (int i = n - 1; i >= 0; i--)
#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};

int ans;
int n,m;
int h,w,c[11][11];
int d[333][333];
void warshall_floyd(int n) {
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}

signed main(){
	
	cin>>h>>w;
	rep(i,10)rep(j,10){
		cin>>c[i][j];
		d[i][j]=c[i][j];
	}
	warshall_floyd(10);
	rep(i,h)rep(j,w){
		int a;
		cin>>a;
		if(a==-1)continue;
		ans+=d[a][1];
	}
	cout<<ans<<endl;
	
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define all(x) (x).begin(), (x).end()
int n, m;
struct Edge{
    int v, u, w;
};
bool comp(Edge A, Edge B)
{
    return A.w < B.w;
}
vector<Edge> edges;

int ans;
int root[500000];
int cnt[500000];
int sz[500000];
long long s[500000];

int Root(int x)
{
    if (x == root[x]) return x;
    return root[x] = Root(root[x]);
}

void Merge(Edge A)
{
    int u = A.u, v = A.v;
    u = Root(u);
    v = Root(v);
    if (u == v)
    {
        if (A.w <= s[v]) ans++;
        else cnt[v]++;
        return;
    }
    if (sz[u] > sz[v])
    {
        swap(v, u);
    }
    sz[v] += sz[u];
    s[v] += s[u];
    cnt[v] += cnt[u] + 1;
    root[u] = v;
    if (A.w <= s[v])
    {
        ans += cnt[v];
        cnt[v] = 0;
    }
    return;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i], sz[i] = 1, root[i] = i;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({a, b, c});
    }
    sort(all(edges), comp);
    for (int i = 0; i < m; i++)
    {
        Merge(edges[i]);
    }
    cout << m - ans;
}


Measured memory_bytes: 8824
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=205;
ll a[maxn],p[maxn];
char s[maxn];
int n,m;

void solve(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
		scanf("%s",s+1);
		if(s[n]=='1')	printf("1\n");
		else{
			int flag=0;
			memset(p,0,sizeof(p));
			for(int i=n;i>=1;i--){
				if(s[i]=='0'){
					ll tmp=a[i];
					for(int j=62;j>=0;j--){
						if((1ll<<j)&tmp){
							if(!p[j]){
								p[j]=tmp;break;
							}
							tmp^=p[j];
						}
					}
				}
				else if(s[i]=='1'){
					ll tmp=a[i];
					for(int j=62;j>=0;j--){
						if((1ll<<j)&tmp){
							if(!p[j])	break;
							tmp^=p[j];
						}
					}
					if(tmp){
						flag=1;break;
					}
				}
			}
			printf("%d\n",flag);
		}
	}
}
int main(){
	solve();
	return 0;
}

Measured memory_bytes: 1692
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <numeric>
#define rep(i, m, n) for(int i = m;i < n;i++)
#define repr(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define INF 999999999
using namespace std;

int main(){
    int n, k; cin >> n >> k;
    int x[100];
    rep(i, 0, n) cin >> x[i];

    int ans = 0;
    rep(i, 0, n){
        if(abs(x[i] - k) < x[i]) ans += abs(x[i] - k) * 2;
        else ans += x[i] * 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
ps = [list(input().split()) for _ in range(m)]

c = [0] * n
for p, s in ps:
    if s == 'AC':
        c[int(p)-1] = 1
d = [0] * n
wa = 0
ac = 0
for p, s in ps:
    if d[int(p)-1] == 0:
        if s == 'WA':
            if c[int(p)-1] == 1:
                wa += 1
        else:
            ac += 1
            d[int(p)-1] = 1
print(ac, wa)

Measured memory_bytes: 31860
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const ll Lmax=ll(1e18);
const ll Nmax=1e9;
const double pi=acos(-1);


//基本的に勝つ手をだす．
//勝つ手がなければ，K回後に勝つ手以外を出す．

int main(){
  long double a,b,x;
  cin>>a>>b>>x;

  if(x>=a*a*b/2){
     double ans=atan((a*a*b-x)*2/(a*a*a))*180/pi;
    printf("%.10f\n",ans);


  }else{
     double ans=atan(a*b*b/2/x)*180/pi;
    printf("%.10f\n",ans);


  }



}


Measured memory_bytes: 3808
#include<iostream>

using namespace std;
const int N = 500005, INF = 1e9+7;
long long sum = 0;
void merge(int A[], int p, int q, int r){
    int n1, n2;
    n1 = q - p + 1;
    n2 = r - q;
    int L[N], R[N];
    for (int i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (int i = 0; i < n2; i++)
        R[i] = A[q + i + 1];
    L[n1] = INF;
    R[n2] = INF;
    int i = 0, j = 0;
    for (int k = p; k <= r; k++)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
            sum++;
        }
        else 
        {
            A[k] = R[j];
            j++;
            sum++;
        }
    }    
}

void merge_sort(int A[], int p,int r){
    int q;
    if (p < r)
    {
        q = (p + r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q+1, r);
        merge(A, p, q, r);
    }
}

int main(){
    int A[500005];
    int n; cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    merge_sort(A, 0, n-1);
    for (int i = 0; i < n-1; i++)
    {
        cout << A[i] << " ";
    }
    cout << A[n-1];
    cout << "\n" << sum << endl;
}


Measured memory_bytes: 6912
#include <iostream>
#define rep(S, L) for (int i = S; i < L; ++i)
using namespace std;

int main() {
  int r;
  cin >> r;
  if (r < 1200) {
    cout << "ABC" << endl;
  } else if (r < 2800) {
    cout << "ARC" << endl;
  } else {
    cout << "AGC" << endl;
  }
  return 0;
}


Measured memory_bytes: 3040
#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int to;
    long long len;
};
vector<edge>G[100010];
long long dist[100010];
int visit[100010];
int q,k;
void dfs(int k)
{
    visit[k]=1;
    for(int i=0;i<G[k].size();i++)
    {
        edge temp=G[k][i];
        if(visit[temp.to]==0)
        {
            dist[temp.to]=dist[k]+temp.len;
            dfs(temp.to);
        }
    }
}
int main(void)
{
    memset(visit,0,sizeof(visit));
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        dist[i]=0;
    }
    int a,b,c;
    edge temp;
    for(int i=1;i<N;i++)
    {
        cin>>a>>b>>c;
        temp.to=b;
        temp.len=c;
        G[a].push_back(temp);
        temp.to=a;
        temp.len=c;
        G[b].push_back(temp);
    }
    cin>>q>>k;
    int x,y;
    dist[k]=0;
    dfs(k);
    for(int i=1;i<=q;i++)
    {
        cin>>x>>y;
        cout << dist[x]+dist[y]<<endl;
    }

    return  0;
}


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

int main(){
  int H, W;
  cin >> H >> W;
  
  vector<vector<char>> board(H, vector<char>(W));
  
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> board.at(i).at(j);
    }
  }
  
  vector<int> remove_yoko(0);
  
  for (int i = 0; i < H; i++){
    int num = 0;
    for (int j = 0; j < W; j++){
      if (board.at(i).at(j) == '.'){
        num++;
      }
      
      if (num == W){
        remove_yoko.push_back(i);
      }
      
    }
  }
  
  vector<int> remove_tate(0);
  
  for (int i = 0; i < W; i++){
    int num = 0;
    for (int j = 0; j < H; j++){
      if (board.at(j).at(i) == '.'){
        num++;
      }
      
      if (num == H){
        remove_tate.push_back(i);
      }
      
    }
  }
  
  for (int i = 0; i < H; i++){
    if (find(remove_yoko.begin(), remove_yoko.end(), i) != remove_yoko.end()){
      continue;
    }
    for (int j = 0; j < W; j++){
      if (find(remove_tate.begin(), remove_tate.end(), j) != remove_tate.end()){
        if (j == W - 1){
          cout << endl;
        }
        continue;
      }
      
      cout << board.at(i).at(j);
      
      if (j == W - 1){
        cout << endl;
      }
    }
  }
  
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, M, L;
  cin >> N >> M >> L;
  
  int64_t dist[N][N];
  int64_t INF = 1e18;
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      dist[i][j] = INF;
    }
  }
  
  for(int i=0; i<M; i++){
    int64_t a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    dist[a][b] = c;
    dist[b][a] = c;
  }
  
  for(int k=0; k<N; k++){
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  
  int64_t charge[N][N];
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      if(dist[i][j] <= L){
        charge[i][j] = 1;
      }
      else{
        charge[i][j] = INF;
      }
    }
  }
  
  for(int k=0; k<N; k++){
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        charge[i][j] = min(charge[i][j], charge[i][k] + charge[k][j]);
      }
    }
  }
  
  int Q;
  cin >> Q;
  for(int i=0; i<Q; i++){
    int n, m;
    cin >> n >> m;
    n--; m--;
    int64_t ans = charge[n][m]-1;
    if(charge[n][m] == INF){
      ans = -1;
    }
    cout << ans << endl;
  }

}

Measured memory_bytes: 1920
// Why am I so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = 50 + 5;

int a[MAXN], b[MAXN];

ll pw[MAXN];

ll ans;

int n;

void pre() {
    pw[0] = 1;

    for (int i = 1; i <= 50; ++i) {
        pw[i] = (pw[i - 1] << 1);
    }
}

bool bit(ll m, int ps) {
    return m & pw[ps];
}

bool check(set<int> S) {
    for (int i = 1; i <= n; ++i) {
        ll m = pw[a[i]];

        for (auto it = S.rbegin(); it != S.rend(); ++it) {
            int x = *it;

            for (int p = 1; p <= 50; ++p) {
                if (bit(m, p)) {
                    m |= pw[p % x];
                }
            }
        }

        if (!bit(m, b[i])) {
            return 0;
        }
    }

    return 1;
}

void solve() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
    }

    set<int> S;

    for (int i = 1; i <= 50; ++i) {
        S.insert(i);
    }

    if (!check(S)) {
        printf("-1\n");
        return;
    }

    for (int cur = 50; cur > 0; --cur) {
        S.erase(cur);

        if (!check(S)) {
            S.insert(cur);
        }
    }

    for (int x : S) {
        ans += pw[x];
    }

    printf("%lld\n", ans);
}

int main() {
    int tt = 1;

    pre();

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 256