akhauriyash/Code-Regression huggingface dataset:
import sys

class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.root[self.find(x)]

def main():
	input = sys.stdin.buffer.readline
	n, m = map(int, input().split())
	lang = [[] for _ in range(m)]
	uf = UnionFind(n)
	for i in range(n):
		k, *ls = map(int, input().split())
		for l in ls:
			lang[l - 1].append(i)
	for speakers in lang:
		for x, y in zip(speakers, speakers[1:]):
			uf.unite(x, y)
	print("YES" if uf.size(0) == n else "NO")

if __name__=="__main__":
	main()

Measured memory_bytes: 16584
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
tree = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    tree[a].append(b)
    tree[b].append(a)

ans = [0 for _ in range(n)]

for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

checked = [False] * n
checked[0] = True


def function(now, count):
    ans[now] += count
    for i in tree[now]:
        if checked[i] == False:
            checked[i] = True
            function(i, ans[now])

function(0, 0)

for a in ans:
    print(a)

Measured memory_bytes: 221892
#![allow(unused_macros, unused_imports, dead_code)]
use std::io;

fn read_line() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s
}

macro_rules! from_line {
    ($($a:ident : $t:ty), +) => {
        $(let $a: $t;)+
        {
            let _line = read_line();
            let mut _it = _line.trim().split_whitespace();
            $($a = _it.next().unwrap().parse().unwrap();)+
            assert!(_it.next().is_none());
        }
    };
}

fn main() {
    from_line!(a1: u32, b1: u32);
    let fa = a1 as f64;
    let fb = b1 as f64;
    println!("{} {} {:.5}", a1/b1, a1%b1, fa/fb);
}



Measured memory_bytes: 5044
//abc098_a.cpp
//Sat May 26 20:47:09 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	int a,b;
	cin >> a >> b;

	int ans = a+b;

	if (ans < a*b){
		ans = a*b;
	}

	if (ans < a-b){
		ans = a-b;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1].append(b-1)
    X[b-1].append(a-1)

l, r = a-1, b-1
L, R = [l], [r]
D = [0] * N
D[l] = D[r] = 1
while True:
    for x in X[l]:
        if D[x] == 0:
            D[x] = 1
            l = x
            L.append(x)
            break
    else: break
while True:
    for x in X[r]:
        if D[x] == 0:
            D[x] = 1
            r = x
            R.append(x)
            break
    else: break
print(len(L+R))
print(*([a+1 for a in L[::-1] + R]))

Measured memory_bytes: 28268
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
BA = []
BC = []
x = 0
for i in range(N):
	while True:
		if A[x] < B[i]:
			if x == N - 1:
				BA.append(N)
				break
			else:
				x += 1
		else:
			BA.append(x)
			break
x = 0
for i in range(N):
	while True:
		if C[N - 1 - x] > B[N - 1 - i]:
			if x == N - 1:
				BC.append(N)
				break
			else:
				x += 1
		else:
			BC.append(x)
			break
BC = BC[::-1]

S = 0
for i in range(N):
	S += BA[i] * BC[i]

print(S)

Measured memory_bytes: 24012
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

s = list(input())
ans = 0
left = 0
right = len(s)-1

while left < right:
    if s[left] == s[right]:
        left += 1
        right -= 1
    elif s[left] == 'x':
        ans += 1
        left += 1
    elif s[right] == 'x':
        ans += 1
        right -= 1
    else:
        print(-1)
        exit()

print(ans)

Measured memory_bytes: 49520
def check(i,N,Ls):
    count=0
    for j in range(N):
        if (i>>j)%2==1:
            for k in Ls[j]:
                if ((i>>(k[0]-1))%2)!=k[1]:
                    return 0
            count+=1
    return count
                
N=int(input())
A_ls=[]
Ls=[]
for i in range(N):
    A=int(input())
    A_ls.append(A)
    ls=[]
    for j in range(A):
        x,y=map(int,input().split())
        ls.append((x,y))
    Ls.append(ls)

ans=0
for i in range(2**N):
    num=check(i,N,Ls)
    if num>ans:
        ans=num
print(ans)

Measured memory_bytes: 74428
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
 
int n, h;
int a[1010], b[1010];
ll dp[10010];
int main() {
  cin >> h >> n;
  rep(i,n) {
    cin >> a[i] >> b[i];
  }
  rep(i,10010) dp[i] = INF;
  dp[h] = 0;
  for (int i = h; i >= 0; i--)
  {
    rep(j,n) {
      if (i >= a[j]) dp[i-a[j]] = min(dp[i-a[j]], dp[i]+b[j]);
      else dp[0] = min(dp[0], dp[i]+b[j]);
    }
  }
  cout << dp[0] << endl;
  return 0;
}

Measured memory_bytes: 3696
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)

int m, k;

int main()
{
	cin >> m >> k;

	if (!m)
	{
		if (!k)
			cout << "0 0" << endl;
		else
			cout << -1 << endl;
		return 0;
	}

	if (m == 1)
	{
		if (k == 0)
			cout << "0 0 1 1" << endl;
		else
			cout << -1 << endl;
		return 0;
	}

	if (k >= (1 << m))
	{
		cout << -1 << endl;
		return 0;
	}

	REP(i, 1 << m)
		if (i != k)
			cout << i << " ";
	cout << k << " ";

	RREP(i, 1 << m)
		if (i != k)
			cout << i << " ";
	cout << k << endl;

}


Measured memory_bytes: 1792
#include <stdio.h>
#include <string.h>

int main(){
	int x,y;
	scanf("%d",&x);
	char a[10000];
	scanf("%s",a);
	int len=strlen(a);
	for(int i=0; i<len;i++){
		a[i]+=x;
		if(a[i]>'Z'){
			a[i]-=26;
		}
		printf("%c",a[i]);
	}
	return 0;
}

Measured memory_bytes: 1656
#include<iostream>
using namespace std;
int main() {
	int n;
	double a[101], b[101];
	cin >> n;
	double sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[i] = 1 / a[i];
		sum += b[i];
	}
	cout << 1 / sum << endl;
	return 0;
	
}

Measured memory_bytes: 256
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    int m;
    cin >> m;
    cout << 48-m << endl;
}

Measured memory_bytes: 256
//17
#include<iostream>

using namespace std;

int main(){
  int n;
  cin>>n;
  int a[3];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=1;i<=100000000;i++){
    int j;
    for(j=0;j<n;j++){
      if(a[j]%i)break;
    }
    if(j==n){
      cout<<i<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1160
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    ans = ""

    while N > 0:
        N, m = divmod(N, 26)
        if m == 0:
            N -= 1
            ans = chr(0x7A) + ans
        else:
            ans = chr(0x60 + m) + ans

    return ans


if __name__ == "__main__":
    print(main())

Measured memory_bytes: 9176
//
//  main.cpp
//  AOJ1173
//
//  Created by aki33524 on 2014/07/09.
//  Copyright (c) 2014年 aki33524. All rights reserved.
//

#include <iostream>
#include <string>
#include <stack>
using namespace std;

string S;

void solve(){
    stack<char> st;
    for(int i=0; i<S.size(); i++){
        char c = S[i];
        if(c != '(' && c != ')' && c != '[' && c != ']')
            continue;
        
        if(c == '(' || c == '[')
            st.push(c);
        else if(c == ')' || c == ']'){
            if(st.empty()){
                cout << "no" << endl;
                return;
            }else if((st.top() == '(' && c == ']') || (st.top() == '[' && c == ')')){
                cout << "no" << endl;
                return;
            }
            st.pop();
        }
    }
    cout << (st.empty() ? "yes" : "no") << endl;
}

int main(int argc, const char * argv[])
{
    while(getline(cin, S), S!="."){
        solve();
    }
    return 0;
}

Measured memory_bytes: 1176
//AAAAAAAAAAAAAAAAAAAAAAAAAAgneyan
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define pb(x) push_back(x)
#define HAYAKU_HAYAKU ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    HAYAKU_HAYAKU; 
    string s,t;
    cin>>s>>t;
    int ans = 0;
    for (int i = 0; i < s.length(); i++)
        if(s[i] != t[i])
            ans++;
    cout<<ans;  
}

Measured memory_bytes: 3772
#include <bitset>
#include <cstdio>

std::bitset<4000010> bs;

int main()
{
	int n; scanf("%d", &n);
	bs[0] = 1;
	for(int i = 1; i <= n; i++)
	{
		int x; scanf("%d", &x);
		bs |= bs << x;
	}
	int o = bs.count();
	int cnt = 0;
	for(int i = 0; i <= 4000000; i++)
	{
		if(bs[i])
		{
			cnt++;
			if(cnt == o / 2 + 1) return 0 * printf("%d\n", i);
		}
	}
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
//#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define popcount(n) __builtin_popcount(n)
#define popcountll(n) __builtin_popcountll(n)

using namespace std;
//using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI = acos(-1.0), EPS = 1e-6;
const long long inf = 2e12 + 12;
const int MAXN = 100005, MAXM = 1003, Mod = 1000000007 , MAXLog = 20;



int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "rt", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(9), cout << fixed;

    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (arr[i] > arr[i - 1] && arr[i] < arr[i + 1] || arr[i] < arr[i - 1] && arr[i] > arr[i + 1])
            ++ans;
    }
    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
void main() {
    string s = readln.chomp;
    string t;
    foreach (x; s) {
        if (x == 'B') {
            if (!t.empty) t.popBack;
        } else {
            t ~= x;
        }
    }
    t.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
#include <stdio.h>

int swap(int *x,int *y);
int gcd(int x,int y);
int main()
{
  int x,y;

  scanf("%d%d",&x,&y);

  if(x < y)swap(&x,&y);

  printf("%d\n",gcd(x,y));

  return 0; 
}

int swap(int *x,int *y)
{
  int tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}
int gcd(int x,int y)
{ 
  int r;
  while(y>0){
    r = x % y;
    x = y;
    y = r;
  }
    return x;
}

Measured memory_bytes: 592
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int A[100];
double d[100];

int main() {
  int N;
  int i;
  double result;
  scanf ("%d", &N);
  
  for (i=0;i<N;i++) {
      scanf("%d", &A[i]);
  }
  
  result = 0;
  for (i=0;i<N;i++) result += 1.0/A[i];
  result = 1.0 / result;
  
  printf("%20.18f", result);
  return 0;
}




Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

void get() {}

template <class Head, class... Tail>
void get(Head& head, Tail&... tail) {
  cin >> head;
  get(tail...);
}

template <class T>
void getv(vector<T>& vec) {
  for (int i = 0; i < vec.size(); ++i)
    cin >> vec[i];
}

int main() {
  ll N, K;
  get(N, K);
  vector<int> A(N);
  getv(A);
  vector<int> next(N);
  map<int, int> first, last;
  unordered_set<int> visit;
  for (int i = N - 1; i >= 0; --i) {
    if (visit.count(A[i])) {
      next[i] = last[A[i]];
    } else {
      next[i] = i;
    }
    last[A[i]] = i;
    visit.insert(A[i]);
  }
  last.clear();
  visit.clear();
  for (int i = 0; i < N; ++i) {
    if (!visit.count(A[i])) {
      first[A[i]] = i;
    }
    if (next[i] <= i) {
      next[i] = first[A[i]];
    }
    visit.insert(A[i]);
  }
  int now = 0;
  vector<int> list;
  unordered_set<int> hold;
  while (1) {
    int nxt = next[now];
    if (nxt <= now || nxt == N - 1) {
      if (!hold.count(now)) {
        list.push_back(now);
        hold.insert(now);
      } else {
        break;
      }
    }
    if (now == nxt && now == N - 1) {
      list.push_back(now + 1);
      hold.insert(now + 1);
    }
    // debug(now, nxt);
    now = (nxt + 1) % N;
  }
  int pos = list[(K - 1) % list.size()];
  // debug(list, pos);
  vector<int> ima;
  for (int i = pos; i < N; ++i) {
    if (next[i] > i && next[i] < N)
      i = next[i];
    else if (next[i] <= i)
      ima.push_back(A[i]);
  }
  for (int x : ima)
    cout << x << " ";
  return 0;
}

Measured memory_bytes: 31560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;

long long Max = -INF;

int main(){
    ll N; cin >> N;
    map<ll, ll> M;
    for(ll i = 0; i < N; i++){
        ll a; cin >> a;
        M[a]++;
    }
    vector<ll> V;
    for(auto m : M){
        if(m.second > 1) {
            V.push_back(m.first);
            if(m.second > 3) V.push_back(m.first); 
        }
    }
    if(V.size() < 2) cout << 0 << endl;
    else {
        sort(V.rbegin(), V.rend());
        cout << V[0]*V[1] << endl;
    }
    
}


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

int n;
int a[110];

int main () {

	cin >> n;
	int sol = 0, kol = 1;
	for (int i = 0; i < n; i ++) {
		cin >> a[i];
		if (i > 0) {
			if (a[i] != a[i-1]) {
				sol += kol/2;
				kol = 1;
			}
			else {
				kol ++;
			}
		}
	}
	
	sol += kol/2;
	cout << sol;

	return 0;
}

Measured memory_bytes: 256
def sumS(s):
  L = []
  if len(s) == 1:
    L.append(s)
  else:
    for formula in sumS(s[1:]):
      L.append(s[0] + "+" + formula)
      L.append(s[0] + formula)
  return L

S = input()
result = 0
for formula in sumS(S):
  result += eval(formula)

print(result)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
    #define REP(i, n) for(int i = 0;i < n;i++)
    #define REPR(i, n) for(int i = n;i >= 0;i--)
    #define FOR(i, m, n) for(int i = m;i < n;i++)
    #define FORR(i, m, n) for(int i = m;i >= n;i--)
    #define SORT(v, n) sort(v, v+n);
    #define VSORT(v) sort(v.begin(), v.end());
    #define llong long long
    #define pb(a) push_back(a)
    #define INF 999999999
    using namespace std;
    typedef pair<int, int> P;
    typedef pair<llong, llong> LP;
    typedef pair<int, P> PP;
    typedef pair<llong, LP> LPP;

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

    int main()
    {
       int a,b,k;
       cin>>a>>b>>k;
       int cnt=0;
       int ans=0;
       for(int i=min(a,b); i>=1; i--)
       {
           if(a%i==0&&b%i==0)
           {
               ++cnt;
           }
           if(cnt==k)
           {
               ans=i;
               break;
           }
       }
       cout<<ans<<endl;
    }



Measured memory_bytes: 256
import sys

args = []
for l in sys.stdin:
  args.append(l.strip('\n'))


l0 = args[0].split()
row_n = int(l0[0])
col_n = int(l0[1])

print('#' * (col_n + 2))
for i in range(row_n):
  l = '#' + args[1 + i] + '#'
  print(l)
print('#' * (col_n + 2))
  

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	string s;
	cin>>n>>s;
	int red[n]={0};
	for(int i=0; s[i]; i++){
		if(s[i]=='R') red[i]++;
		if(i) red[i]+=red[i-1];
	}
	
	int minchange = red[n-1];
	for(int i=0; i<n; i++){
		 int before_white = (i+1)-red[i];
		 int after_red = red[n-1]-red[i];
		 minchange = min(minchange,max(before_white,after_red));
	}
	cout<<minchange;
}

Measured memory_bytes: 4476
N, Ma, Mb = map(int, input().split())

G = []
for i in range(N):
 a, b, c = map(int, input().split())
 G.append( (a,b,c) )

M = 1 + max(sum([ a for a, b, c in G ]),
            sum([ b for a, b, c in G ]) )
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for a, b, c in G:
  for i in reversed(range(0, M - a)):
    for j in reversed(range(0, M - b)):
      dp[(i+a)*M+(j+b)] = min(dp[(i+a)*M+(j+b)], dp[i*M+j] + c)
ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x * M + Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)


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

using namespace std;

#define ll long long
#define ss stringstream
#define rep(i,n) for(int i=1;i<=(n);i++)
#define rep0(i,n) for(int i=0;i<(n);i++)

const ll INF=1e9+7;

int main()
{
	/*freopen("input.txt","r",stdin);
	freopen("outcout<<put.txt","w",stdin);*/
	ll n;
	cin>>n;
	cout<<(n&1?n*2:n);
	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 pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
ll a[252521];

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%lld",a+i);
  multiset<ll> S;
  REP(i,n)S.insert(a[i]);
  int ans = 0;
  while(S.size()){
    ll x = *S.rbegin(); S.erase(S.find(x));
    ll y;
    FORR(i,0,32){
      ll sum = 1ll<<i;
      y = sum - x;
      if(S.count(y)>0)break;
      y = -1;
    }
    if(y!=-1){
      S.erase(S.find(y));
      ans++;
    }
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 11136
n = int(input())
v = list(map(int, input().split()))

while len(v) != 1:
    min_1 = min(v)
    del v[v.index(min_1)]
    min_2 = min(v)
    del v[v.index(min_2)]
    v.append((min_1 + min_2)/2)
    
print (v[0])

Measured memory_bytes: 3060
a = [int(item) for item in input().rstrip()]

for i in range(2**3):
    val = a[0]
    for j in range(3):
        if i & 1<<j:
            val += a[j+1] 
        else:
            val -= a[j+1] 
    if val == 7:
        print(a[0], end="")
        if i & 1:
            print("+", end="")
        else:
            print("-", end="")
        print(a[1], end="")
        if i & 1<<1:
            print("+", end="")
        else:
            print("-", end="")
        print(a[2], end="")
        if i & 1<<2:
            print("+", end="")
        else:
            print("-", end="")
        print(a[3], end="")
        print("=7")
        exit()

print("Wrong input")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
int main() {
    i64 A, B;
    cin >> A >> B;
    cout << ((A - B) & 1 ? "IMPOSSIBLE" : to_string((A + B) / 2)) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

#define LOOP(x) for( int i = 0; i < x; ++i )

using namespace std;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    vector<int> *A = new vector<int>;
    A->reserve(N);
    LOOP(N){
        int a;
        cin >> a;
        A->push_back(a);
    }
    
    int ans = 0;
    bool isContinue = false;
    do {
        vector<int> *A_next = new vector<int>;
        A_next->reserve(N);
        
        int even_counter = 0;
        isContinue = false;
        for( auto it = begin(*A); it != end(*A); ++it ) {
            A_next->push_back(int((*it)/2));
            if((*it) % 2 == 0) {
                ++even_counter;
                
            }
        }
        
        if( even_counter == N ) {
            ++ans;
            isContinue = true;
            delete A;
            A = A_next;
        }

    }while(isContinue);
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,t=0;
  string a;
  cin>>n>>a;
  int ans=0;
  for(int i=0;i<n;i++){
    if(a[i]=='I')t++;
    else if(a[i]=='D')t--;
    if(ans<t)ans=t;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
# define _CRT_SECUREj_NO_WARNINGS 1
# define _USE_MATH_DEFINES
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
using namespace std;
# define INF ((int)(1<<25))
# define REP(i,n) for(int i=0;i<(int)n;i++)
# define FOR(i,n) REP(i,n)
# define TORAD 2.0*M_PI/360.0
# define INT(x) int x;cin>>x;
# define ALL(x) (x).begin(),(x).end()
# define RALL(x) (x).rbegin(),(x).rend()
# define DEBUG(x) cout<<#x<<" :"<<x<<endl;
# define EPS 1e-12
template<class T> void debug(T a) { for (auto iiiiiiiiii : a)cout << iiiiiiiiii << endl; }
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };

int main()
{
	int n;
	while (cin >> n&&n)
	{
		vi a;
		FOR(i, n)
		{
			INT(x);
			a.push_back(x);
		}
		int j = 32,k=0;
		for (int i = 0;; i++)
		{
			if (i % 2)
			{
				j -= min(a[k%a.size()],j);
				k++;
			}
			else
			{
				j -= (j - 1) % 5;
			}
			cout << j << endl;
			if (!j)break;
		}
	}
}

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

int main()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;

    while (k > 0) {
        if (a >= b) {
            b *= 2;
            k--;
            continue;
        }
        if (b >= c) {
            c *= 2;
            k--;
            continue;
        }
        break;
    }

    string result = (a < b && b < c) ? "Yes" : "No";

    cout << result << endl;
    
    return 0;
}


Measured memory_bytes: 3608
# ABC124C - Coloring Colorfully
import sys
input = sys.stdin.readline

s = input().rstrip()
a = s[0]
ans = 0
for i, j in enumerate(s):
    if i % 2 == 0:
        if j != a:
            ans += 1
    else:
        if j == a:
            ans += 1
print(ans)

Measured memory_bytes: 3188
s = input()
n,m = 0,0
for i in range(len(s)):
    if i%2==0 and s[i]=='0': n+=1
    if i%2==1 and s[i]=='1': n+=1
for i in range(len(s)):
    if i%2==0 and s[i]=='1': m+=1
    if i%2==1 and s[i]=='0': m+=1
print(min(n,m))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, K;
  cin >> N >> K;
  vector<int> x(N);
  for(int i=0; i<N; i++){
    cin >> x.at(i);
  }
  int sum = 0;
  for(int i=0; i<N; i++){
    sum += 2*min(x.at(i),K-x.at(i));
  }
  cout << sum << endl;
}

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

int main()
{
	int N;
	cin >> N;
	int tmp = N, S = 0;
	while (tmp) {
		S += tmp % 10;
		tmp /= 10;
	}
	puts(N % S == 0 ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod_) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod_;
		}
		x = x * x % mod_;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}
/*--------Library Zone!--------*/

struct union_find {
	int par[214514], size_[214514];
	union_find(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};

int n, a, b;
signed main() {
	cin >> n >> a >> b;
	union_find car(n), train(n);
	rep(i, a) {
		int f, t; cin >> f >> t;
		car.unite(f - 1, t - 1);
	}
	rep(i, b) {
		int f, t; cin >> f >> t;
		train.unite(f - 1, t - 1);
	}
	map<P, int>mp;
	rep(i, n) {
		mp[{car.find(i), train.find(i)}]++;
	}
	rep(i, n) {
		cout << mp[{car.find(i), train.find(i)}] << " ";
	}cout << endl;
}

Measured memory_bytes: 18560
hitachi = input()
#type(hitachi)
flag = 0
if(len(hitachi) == 1):
    hitachi += " "
elif(len(hitachi) >= 11):
    hitachi = " "
elif(len(hitachi) % 2 ==1):
    hitachi += " "
for x in range(len(hitachi)):
    if(hitachi[x] == " "):
        break
    if(x %2 == 0):
        if(hitachi[x] + hitachi[x+1] == "hi"):
            #print(hitachi[x] + hitachi[x+1])
            flag += 1
        else:
            #print(hitachi[x] + hitachi[x+1])
            print("No")
            break
if(not len(hitachi) == 0):
    if(flag == len(hitachi)//2):
        print("Yes")

Measured memory_bytes: 3064
/*
AtCoder Regular Contest 024 A - くつがくっつく
結果:
*/

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

//#define DEBUG1
//#define DEBUG2
//#define DEBUGF

int main() {
	static int i, j, ans;
	static int A, B;

	scanf("%d %d", &A, &B);
	if (A%B != 0) {
		printf("%d\n", 1);
	}
	else {
		printf("%d\n", 0);
	}

#ifdef DEBUGF
	getch();
#endif
	return 0;
}


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

int getNumsInt32(int32_t *buf, int32_t num)
{
  int32_t i;

  for (i = 0; i < num; i++) {
    if (scanf("%d", &buf[i]) == EOF) {
      return -1;
    }
  }
  return 0;
}

int main()
{
  int32_t K, N, i;
  char s[10 + 1];

  if (getNumsInt32((int32_t *)&N, (int32_t)1) == -1) {
    return -1;
  }

  if (scanf("%s", s) == EOF) {
    return -1;
  }

  if (getNumsInt32((int32_t *)&K, (int32_t)1) == -1) {
    return -1;
  }
  
  for (i = 0; i < N; i++) {
    if (s[i] != s[K - 1]) {
      s[i] = '*';
    }
  }

  printf("%s\n", s);

  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String [] args){
		Scanner scan = new Scanner(System.in);
		
		int i,j;
		
		while(true){
			
			int h = scan.nextInt();
			int w = scan.nextInt();
			
			if(h == 0 && w == 0){
				break;
			}
			
			for(i=0; i<h; i++){
				for(j=0; j<w; j++){
					System.out.print('#');
				}
				System.out.println();
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 27128
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;
static import std.ascii;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long n, m, d;
    scan(n, m, d);

    if (d == 0)
    {
        writefln("%.10f", (1.0 / n) * (m - 1));
        return;
    }

    writefln("%.10f", (1.0 / n) ^^ 2 * (n - d) * (m - 1) * 2);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	bool ok = false;
	if (s[0] == '7' || s[1] == '7' || s[2] == '7') yn

	return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
#define for(i,s,n) for(int i=s;i<=n;i++)
using namespace std;
void solve(){
    ll n;
    cin>>n;
    ll arr[n+1],dp[n+1];
    for(i,1,n) cin>>arr[i];
    dp[1]=0;
    dp[2]=abs(arr[1]-arr[2]);
    for(i,3,n) {
        dp[i] = min(abs(arr[i]-arr[i-1])+dp[i-1],abs(arr[i]-arr[i-2])+dp[i-2]);
    }
    
    cout << dp[n]<<"\n";


}
int main(){
    solve();
}

Measured memory_bytes: 5108
# 重複を引いて求める

MOD = 10 ** 9 + 7
table_len = 10 ** 5 + 10

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)

finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

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

last = [-1] * (N+1)
for i, A in enumerate(As):
    if last[A] == -1:
        last[A] = i
    else:
        l = last[A]
        r = N - i
        break

for k in range(1, N+2):
    ans = fac[N+1] * finv[k] % MOD * finv[N+1 - k] % MOD
    if l + r >= k - 1:
        ans -= fac[l+r] * finv[k-1] % MOD * finv[l+r-k+1] % MOD
        ans %= MOD
    print(ans)

Measured memory_bytes: 90800
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll n,x=0;
    int i,j,k;
    cin>>n;
    for(i=1; i<=n; i++)
    {

        for(j=1; j<n; j++)
        {
            x+=__gcd(i,__gcd(j,k));
            for(k=1; k<n; k++)
            {
                x+=__gcd(i,__gcd(j,k));

            }
            x+=__gcd(i,__gcd(j,k));

        }
        x+=__gcd(i,__gcd(j,k));

    }

    cout<<x<<endl;


    return 0;
}





Measured memory_bytes: 3620
using System;
using System.Collections.Generic;

class Program
{
    #region library
    static int n = 0;
    static int m = 0;
    static int r = 0;
    static int c = 0;
    static int x = 0;
    static int y = 0;
    static int[] arr;
    static string s = "";
    static string[] ss;
    static string alpha = "abcdefghijklmnopqrstuvwxyz";
    static long sum = 0;
    static long cnt = 0;
    static long max = -1;
    static long min = 2147483647;
    static bool flg = false;
    static bool flg2 = false;
    static char[,] map;
    static int[,] imap;
    static string rl()
    {
        return Console.ReadLine();
    }
    static string[] rls()
    {
        return Console.ReadLine().Split();
    }
    static void wl(object obj = null)
    {
        Console.WriteLine(obj);
    }
    static void w(object obj)
    {
        Console.Write(obj);
    }
    static int Int(string s)
    {
        return int.Parse(s);
    }
    static void yes()
    {
        wl("YES");
    }
    static void no()
    {
        wl("NO");
    }
    static void Sum()
    {
        wl(sum);
    }
    static void Cnt()
    {
        wl(cnt);
    }
    static void setarray(int num = -1)
    {
        arr = new int[n];
        if(num == -1) ss = rls();
        for (int i = 0; i < n; i++)
        {
            if (num == -1)
                arr[i] = Int(ss[i]);
            else
                arr[i] = num;
        }
    }
    static void setmap(char def = '@')
    {
        if (r == 0 && c == 0)
        {
            ss = rls();
            r = Int(ss[0]);
            c = Int(ss[1]);
        }
        map = new char[r, c];
        for (int i = 0; i < r; i++)
        {
            if (def == '@') s = rl();
            for (int j = 0; j < c; j++)
            {
                map[i, j] = (def == '@') ? s[j] : def;
            }
        }
    }
    static void setimap(int def = -1)
    {
        if (r == 0 && c == 0)
        {
            ss = rls();
            r = Int(ss[0]);
            c = Int(ss[1]);
        }
        imap = new int[r, c];
        for (int i = 0; i < r; i++)
        {
            if (def == -1) s = rl();
            for (int j = 0; j < c; j++)
            {
                imap[i, j] = (def == -1) ? Int(s[j].ToString()) : def;
            }
        }
    }
    #endregion

    static void Main(string[] args)
    {
        n = Int(rl());
        ss = rls();
        arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int(ss[i]) - (i + 1);
        }

        Array.Sort(arr);

        int b = arr[arr.Length / 2];

        for (int i = 0; i < n; i++)
        {
            sum += Math.Abs(Int(ss[i]) - (b + i + 1));
        }
        min = sum;

        if (arr.Length % 2 == 0)
        {
            b = arr[arr.Length / 2 - 1];
            sum = 0;
            for (int i = 0; i < n; i++)
            {
                sum += Math.Abs(Int(ss[i]) - (b + i + 1));
            }
            min = Math.Min(min, sum);
        }

        wl(min);
    }


}



Measured memory_bytes: 31648
# coding: utf-8
S = input()
Q = int(input())
# print("S:", S, "Q:", Q)

lst = [input() for _ in range(Q)]
# print("lst:", lst)
flg = True
# print("S:", S)
left = ""
right = ""
for i in lst:
    if i[0] == '1':
        flg = not flg
    else:
        if flg == False:
            if i[2] == '1':
                right = right + i[4] 
                # print("right:", right)
            else:
                left = i[4] + left
                # print("left:", left)
        else:
            if i[2] == '1':
                left = i[4] + left
                # print("left:", left)
            else:
                right = right + i[4]
                # print("right:", right)
S = left + S + right
if flg == False:
    print(S[::-1])
else:
    print(S)

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

void trace(int A[], int N){
	for(int i = 0; i < N; i++){
		cout<<A[i];
		if(i < N - 1) cout<<" ";
	}
	cout<<endl;
}

int Bubble_Sort(int A[], int N) {
	int count = 0;
	int flag = 1;

	while(flag){
		flag = 0;
		for(int j = N - 1; 1 <= j; j--){
			if(A[j] < A[j - 1]){
				swap(A[j], A[j - 1]);
				count++;
				flag = 1;
			}
		}
	}

	trace(A, N);

	return count;
}

int main(){	
	int N, A[100];

	cin>>N;

	for(int i = 0; i < N; i++) cin>>A[i];
	
	cout<<Bubble_Sort(A, N)<<endl;
	
	return 0;
}


Measured memory_bytes: 3104
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		Array.Sort(A);
		long[] B = new long[N];
		B[0] = A[0];
		for(int i=1;i<N;i++){
			B[i] = A[i] + B[i-1];
		}
		int ans = 1;
		for(int i=N-2;i>=0;i--){
			if(B[i] * 2 < A[i+1]) break;
			ans++;
		}
		Console.WriteLine(ans);
		
	}
	int N;
	long[] A;
	public Sol(){
		N = ri();
		A = rla();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 26460
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
int P;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
    R int res=1;
    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
    return res;
}
const int N=155;
int n,p;
inline int max(R int x,R int y){return x>y?x:y;}
int solve(int n,int p){
    static int f[N][N];memset(f,0,sizeof(f));
    f[0][0]=1;
    fp(i,0,n-1)fp(j,0,p)if(f[i][j])upd(f[i+1][0],f[i][j]),upd(f[i+1][j+1],f[i][j]);
    R int res=0;fp(i,0,p)upd(res,f[n][i]);
    return res;
}
int f[N][N][N];
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d%d%d",&n,&p,&P);
    if(p&1^1)return printf("%d\n",mul(solve(n>>1,p>>1),solve((n+1)>>1,p>>1))),0;
    f[0][0][0]=1;
    fp(i,1,n+1){
        R int r=(i<<1),l=r-p;
        R bool fr=(r>=1&&r<=n),fl=(l>=1&&l<=n);
        fp(j,0,n)fp(k,0,p)if(f[i-1][j][k]){
            upd(f[i][0][0],f[i-1][j][k]);
            if(fr)upd(f[i][j+1][0],f[i-1][j][k]);
            if(fl)upd(f[i][0][k?k+1:k],f[i-1][j][k]);
            if(fl&&fr)upd(f[i][j+1][max(k+1,j+1)],f[i-1][j][k]);
        }
    }
    printf("%d\n",f[n+1][0][0]);
    return 0;
}

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

using namespace std;

int a,b;

int main()
{
    scanf("%d %d",&a,&b);
    int dem=0,s=1;
    while (s<b)
    {
        s+=a;
        dem++;
        s--;
    }
    cout<<dem;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define inf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define inv(x) Power(x, mod - 2)
#define fi first
#define se second
#define MP make_pair
#define PB push_back

typedef std::vector<int> Poly;
typedef std::pair<int,int> Pair;
typedef unsigned long long ull;
typedef long double ld;
typedef long long ll;

const int maxn = 400, maxm = 1e5, MAX = 1e6 + 5, mod = 998244353;
//template{{{
const long double Pi = 3.14159265358979323846l, Eps = 1e-4;
template <class T> inline bool equal(T x, T y) { return fabs(x - y) < Eps; }
inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; };
inline void inc(int &x, int y) { x += y; x -= (x >= mod ? mod : 0); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int Power(int x, int y, int Mod = mod) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = (ll) ans * x % Mod;
		x = (ll) x * x % Mod, y >>= 1;
	} return ans;
}

/*char buf[1<<23],obuf[1<<23],*p1=buf,*p2=buf, *O = obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
void print(int x) {
    if(x > 9) print(x / 10);
    *O++=x%10+'0';
} */

template <class T> inline T	input() {
	T x; char ch; bool flag = false;
	while (!isdigit(ch = getchar())) flag |= ch == '-';
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	return flag ? -x : x;
}

template <class T> inline bool chkmin(T &x, T y) { x = x < y ? x : y; return x == y; }
template <class T> inline bool chkmax(T &x, T y) { x = x > y ? x : y; return x == y; }
template <class T> inline T gcd(T x, T y) { return !y ? x : gcd(y, x % y); }
template <class T> inline T sqrm(T x) { return (ll) x * x % mod; }
template <class T> inline T sqr(T x) { return x * x; }

struct {
	inline operator int () { return input<int>(); }
	inline operator long long () { return input<long long>(); }
	template <class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read; //}}}

int T, n;
ll a[maxn + 5], d[100];
char s[maxn + 5];

void insert(ll x) {
	for (int i = 62; ~i; --i)
		if (1ll << i & x) {
			if (!d[i]) { d[i] = x; break; }
			else x ^= d[i];
		}
}

bool query(ll x) {
	for (int i = 62; ~i; --i)
		if (1ll << i & x) {
			if (!d[i]) return false;
			x ^= d[i];
		}
	return true;
}

void solve() {
	memset(d, 0, sizeof d);
	n = read;
	for (int i = 1; i <= n; ++i) read(a[i]);
	scanf("%s", s + 1);

	for (int i = n; i; --i) {
		if (s[i] == '0') insert(a[i]);
		else if (!query(a[i])) return puts("1"), void();
	}
	puts("0");
}

signed main() {
#ifdef local
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	freopen("log", "w", stderr);
#endif

	read(T);
	while (T--) solve();
	return 0;
}


Measured memory_bytes: 3656
N,X = map(int,input().split())
ans = 0
while X != 1 and X != 2**(N+1)-1 and X != 2**(N+2)-3:
    if 1 < X < 2**(N+1)-1:
        X -= 1
        N -= 1
    else:
        ans += 2**N
        X -= 2**(N+1)-1
        N -= 1
if X == 2**(N+1)-1:
    ans += 2**N
elif X == 1:
    ans += 0
else:
    ans += 2**(N+1)-1
print(ans)


Measured memory_bytes: 3060
def op(x,y,i):
    if i==0:
        return x+y
    elif i==1:
        return x-y
    elif i==2:
        return x*y
    return

def check(x, n):
    x0,x1,x2,x3 = x[0],x[1],x[2],x[3]
    s='+-*'
    for i1 in range(3):
        a1 = op(x0,x1,i1)
        for i2 in range(3):
            a2 = op(a1,x2,i2)
            for i3 in range(3):
                a3 = op(a2,x3,i3)
                if a3==n:
                    b1,b2,b3 = s[i1],s[i2],s[i3]
                    s0 = '((({0} {1} {2}) {3} {4}) {5} {6})'
                    eq = s0.format(x0,b1,x1,b2,x2,b3,x3)
                    return eq
            a2 = op(x2,x3,i2)
            for i3 in range(3):
                a3 = op(a1,a2,i3)
                if a3==n:
                    b1,b2,b3 = s[i1],s[i3],s[i2]
                    s0 = '(({0} {1} {2}) {3} ({4} {5} {6}))'
                    eq = s0.format(x0,b1,x1,b2,x2,b3,x3)
                    return eq
    return ''

def permutations(L):
    if L == []:
        return [[]]
    else:
        return [[h]+t for i,h in enumerate(L)
                      for t   in permutations(L[:i]+L[i+1:])]

n=10
while True:
    x = map(int,raw_input().split())
    if x==[0,0,0,0]:break
    x = permutations(x)
    for e in x:
        s = check(e,n)
        if s!='':
            print s
            break
    else:
        print ('0')

Measured memory_bytes: 4340
#include<bits/stdc++.h>
#include<ios>
#include<limits>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  int s=0,p=0;
  for(int i=1;i<n;i++){
    s=s+i;
  }
  for(int i=1;i<m;i++){
    p=p+i;}
  cout<<s+p;
  return 0;}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define DB double
#define INF 1145141919810364364
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define ERR 0.00000001
#define NUM 200010

void swap(LL* a,LL* b){LL tmp=*a;*a=*b;*b=tmp;}
void YN(int a){if(a==1)printf("Yes\n");if(a==0)printf("No\n");}
LL lpow(LL a,LL n){LL ans=pow(a,n)*10;if(ans%10<5)return ans/10;return ans/10+1;}
LL dup(LL a,LL d){if(a%d==0)return a/d;else return a/d+1;}
LL GCD(LL a,LL b){LL c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int lcmpr(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return -1;if(*(LL*)a<*(LL*)b)return 1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int ccmpr(const void* a,const void* b){return *(char*)b-*(char*)a;}
int scmp(const void* a,const void* b){return strcmp(*(char**)a,*(char**)b);}
int scmpr(const void* a,const void* b){return strcmp(*(char**)b,*(char**)a);}
LL mod(LL a,LL m){if(a<0)return a%m+m;else return a%m;}
LL DIV(LL a,LL d){LL m=MOD,x=1,y=0,k;while(m){k=d/m;d-=k*m;swap(&m,&d);x-=k*y;swap(&x,&y);}return mod(a*mod(x,MOD),MOD);}
LL FAC(LL a){LL i,ans=1;FOR(i,1,a+1){ans*=i;if(MOD>0&&ans>MOD)ans%=MOD;}return ans;}
LL POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return ans;}
LL fact[NUM],finv[NUM],inv[NUM];
void comi(){LL i;fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}

int main(){
  LL K,n[102],i,j,l,dp[105][5][2]={0},ans=0;
  char N[102];
  scanf("%s%lld",N,&K);
  l=strlen(N);
  FOR(i,0,l)n[i]=N[i]-'0';
  dp[0][0][1]=1;
  FOR(i,0,l)FOR(j,0,4){
    dp[i+1][j][0]+=dp[i][j][0];
    dp[i+1][j+1][0]+=dp[i][j][0]*9;
    if(n[i]==0)dp[i+1][j][1]+=dp[i][j][1];
    else{
      dp[i+1][j+1][1]+=dp[i][j][1];
      dp[i+1][j+1][0]+=dp[i][j][1]*(n[i]-1);
      dp[i+1][j][0]+=dp[i][j][1];
    }
  }

  printf("%lld\n",dp[l][K][0]+dp[i][K][1]);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll gcl(ll a,ll b){
  if(a%b==0){
    return b;
  }
  else{
    return gcl(b,a%b);
  }
}
int main(){
  ll a;
  cin>>a;
  ll b;
  cin>>b;
  vector<ll>vec(a);
  for(ll i=0;i<a;i++){
    ll c;
    cin>>c;
    vec.at(i)=abs(c-b);
  }
  if(a==1){
    cout<<vec.at(0)<<endl;
    return 0;
  }
  sort(vec.begin(),vec.end());
  ll g=gcl(vec.at(0),vec.at(1));
  for(ll i=0;i<a;i++){
    if(vec.at(i)%g==0){
      continue;
    }
    else{
      g=gcl(vec.at(i),g);
    }
  }
  cout<<g<<endl;
    
    
  
  return 0;
}



Measured memory_bytes: 4056