akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=100;

int main(){
	while(1){
		int n;
		int taro[N];
		int hanako[N];
		
		scanf(" %d", &n);
		if(n==0) break;
		for(int i=0; i<n; ++i) scanf(" %d", &taro[i]);
	
		sort(taro, taro+n);
		
		int t=0;
		int h=0;
		for(int i=1; i<=2*n; ++i){
			if(i==taro[t]) ++t;
			else{	
				hanako[h]=i;
				++h;
			}	
		}
		
		/*
		printf("hanako:\n");
		for(int i=0; i<n; ++i) printf("%d\n", hanako[i]);
		printf("%d %d\n", t, h);
		*/
		
		int field=0;
		while(t>0 && h>0){
			for(int i=0; i<n; ++i){
				if(taro[i]>field){
					field=taro[i];
					taro[i]=-1;
					t--;
					break;	
				}
				
				if(i==n-1) field=0;//pass	
			}
			//printf("now field=%d\n", field);
			
			if(t<=0) break;
			
			for(int i=0; i<n; ++i){
				if(hanako[i]>field){
					field=hanako[i];
					hanako[i]=-1;
					h--;
					break;
				}
				
				if(i==n-1) field=0;//pass
			}
			//printf("now field=%d\n", field);	
		}
		
		printf("%d\n%d\n", h, t); 	
	}
	return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
const ll Mod=1000000007;
const ll INF=999999999999999999;
const ll NN=(ll)(1e6+5);
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {
       ll n,m,x,y,k,i;
       cin>>n>>m>>k;
       map <ll,ll> r,c;
       map <pair<ll,ll>,ll> cnt;
       for(i=0;i<k;i++)
       {
           cin>>x>>y;
           cnt[{x,y}]++;
           r[x]++;
           c[y]++;
       }
       ll mxc=0,mxr=0,ans=0;
       set <ll> row,col;
       for(auto u:r)
        if(mxr<u.ss)
         mxr=u.ss;
       for(auto u:r)
        if(u.ss==mxr) 
         row.insert(u.ff);
       for(auto u:c)
        if(mxc<u.ss)
         mxc=u.ss;
       for(auto u:c)
        if(u.ss==mxc) 
         col.insert(u.ff);
       ll f=0;     
       for(auto u:row)
       {
           for(auto uu:col)
            if(!cnt[{u,uu}])
            {
             f=1;
             break;
            }
           if(f)
            break; 
       }     
       ans=mxc+mxr-1;
       if(f)
        ans++;
       cout<<ans;
   }
}

Measured memory_bytes: 87976
using System;
using System.Linq;
public class B{
    public static void Main(){
        int n = int.Parse(Console.ReadLine());
        int[] w = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int w1 = 0;
        int w2 = w.Sum();
        int ans = w2;
        for (int i=0;i<n;i++){
            w1 += w[i];
            w2 -= w[i];
            ans = Math.Min(ans,Math.Abs(w1-w2));
        }
        
        System.Console.WriteLine(ans);
    }
}


Measured memory_bytes: 13396
N,L = map(int,input().split())
lists = []
min = L + (N ) - 1
for i in range(1,N+1):
    lists.append(L + i - 1)
for i in range(len(lists)):
    if lists[i] >= 0 and lists[i] < min:
        min = lists[i]
print(sum(lists) - min)

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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int64_t> A(N);
  int64_t s = 0;
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++) s ^= A[i];
  for (int i = 0; i < N; i++) {
    printf("%ld", s ^ A[i]);
    if (i + 1 < N) {
      printf(" ");
    } else {
      printf("\n");
    }
  }

  return 0;
}


Measured memory_bytes: 4784
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
using namespace std;

#define INF 1e9
#define PI 3.141592653589793238
typedef long long ll;

int main() {
    int n;cin>>n;
    int a, flag=0;
    for(int i=0; i<n; i++){
        cin>>a;
        if(a%2==0){
            if(a%3!=0 && a%5!=0) flag=1;
        }
    }

    if(flag==0)cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;

    return 0;
}

Measured memory_bytes: 3600
# -*- coding: utf-8 -*-
import sys, copy, math, itertools
from copy import *
from collections import deque
import numpy as np
from heapq import *
from bisect import *
import scipy as sp
#from scipy.optimize import linprog
from scipy import ceil, ifft
from scipy.fftpack import fft

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

if A==B: print(C)
if B==C: print(A)
if C==A: print(B)

Measured memory_bytes: 13492
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define int long long
char m[] = {'0','1','2','3','5','7','8','9'};
signed main(){
	int a;
	while( scanf("%lld", &a) != EOF ){
		if (a==0) break;
		vector<int> x(0,0);
		int l = 0;
		while(a>0){
			x.push_back(a%8);
			a/=8;
			l++;
		}
		for(unsigned int i=0;i<l;i++){
			cout << m[x[l-i-1]];
		}
		cout << endl;
	}
	return 0;
}

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

#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 998244353 
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define mii unordered_map<int,int>
#define mll unordered_map<ll,ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pp pop_back
#define vii vector<int>
#define vll vector<ll>
#define vpp vector<pii>
#define all(c) c.begin(),c.end()
#define tr(it,c) for(it = c.begin() ; it!=c.end() ; it++)
int inf = INT_MAX ;
ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }
ll gcd(ll a,ll b){ return ((b==0) ? a:gcd(b,a%b));}

int main(){
	boost;
	

	string str;
	cin>>str;

	if(str[0]=='S'){
		cout<<"Cloudy";
		
	}

	if(str[0]=='R'){
		cout<<"Sunny";
	}
	
	if(str[0]=='C'){
		cout<<"Rainy";
		
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <deque>
using namespace std;
using P = pair<int,int>;
typedef long long int ll;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)

int main(){
    ll a,b,k; cin >> a >> b >> k;
    rep(i,k){
        if(i%2==0){
            if(a%2!=0){
                a--;
            }
            a = a/2;
            b += a;
        }else{
            if(b%2!=0){
                b--;
            }
            b = b/2;
            a += b;
        }
    }
    cout << a <<endl;
    cout << b << endl;    
    return 0;
}




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


int main(void){
   int N,K;
   cin>>N>>K;
   vector<int> p(N);
   for(int i=0;i<N;i++){
      cin>>p[i];
   }
   vector<double> sum(N+1);
   sum[0]=0.0;
   for(int i=0;i<N;i++){
      sum[i+1]=sum[i]+(double)(p[i]+1.0)/2.0;
   }
   double ans=0.0;
   for(int i=N;i>=K;i--){
      ans=max(ans,sum[i]-sum[i-K]);
   }
   cout<<fixed;
   cout<<setprecision(7)<<ans<<endl;
   return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int N;
	cin >> N;
	if (x1 > x2) {
		swap(x1, x2);
		swap(y1, y2);
	}
	vector<pair<int, int>> C;
	rep(i, N) {
		int x, y;
		cin >> x >> y;
		C.pb(mp(x, y));
	}
	sort(C.begin(), C.end());
	double d = 10 * (2 - acos(0));
	double kotae;
	int aru = 0;

	if (x1 == x2) {
		if (y1 > y2) swap(y1, y2);
		rep(i, N) {
			if (C[i].first == x1 && C[i].second > y1 && C[i].second < y2) aru = 1;
		}
		kotae = 100.0 * (y2 - y1);
		if (aru) kotae += 10 * (2 * acos(0) - 2);
	}
	else if (y1 == y2) {
		rep(i, N) {
			if (C[i].second == y1 && C[i].first > x1 && C[i].first < x2) aru = 1;
		}
		kotae = 100.0 * (x2 - x1);
		if (aru) kotae += 10 * (2 * acos(0) - 2);
	}
	else if (y2 > y1) {
		vector<int> V;
		V.pb(1e9);
		rep(i, C.size()) {
			int a = C[i].first;
			int b = C[i].second;
			if (a >= x1 && a <= x2 && b >= y1 && b <= y2) {
				aru = 1;
				auto p = lower_bound(V.begin(), V.end(), b);
				if (p == V.end()) V.pb(b);
				else *p = b;
			}
		}
		int B = V.size();
		kotae = 100.0 * (y2 - y1 + x2 - x1);
		if (aru) {
			kotae -= B * d;
			if (B == 1 + min(x2 - x1, y2 - y1)) kotae += 10 * (2 * acos(0) - 2) + d;
		}
	}
	else if (y2 < y1) {
		vector<int> V;
		V.pb(1e9);
		for (int i = (int)C.size() - 1; i >= 0; i--) {
			int a = C[i].first;
			int b = C[i].second;
			if (a >= x1 && a <= x2 && b >= y2 && b <= y1) {
				aru = 1;
				auto p = lower_bound(V.begin(), V.end(), b);
				if (p == V.end()) V.pb(b);
				else *p = b;
			}
		}
		int B = V.size();
		kotae = 100.0 * (y1 - y2 + x2 - x1);
		if (aru) {
			kotae -= B * d;
			if (B == 1 + min(x2 - x1, y1 - y2)) kotae += 10 * (2 * acos(0) - 2) + d;
		}
	}
	cout << fixed << setprecision(15) << kotae << endl;

	Would you please return 0;
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; 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 VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll n, k;
    cin >> n >> k;
    vector<double> p(n);
    REP(i, n) {
        cin >> p[i];
        p[i] = (p[i] + 1) / 2.0;
    }
    double sum = 0;
    REP(i, k) {
        sum += p[i];
    }
    double res = sum;
    REP(i, n - k) {
        sum += p[k + i] - p[i];
        res = max(res, sum);
    }
    cout << fixed << setprecision(10) << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>
#define min(x,y) ((x<y)?(x):(y))
int main(){
	int i,j,n,m,d[23][23],a,b;
	int used[23],v[23],s,g,ans,t,x;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){v[i]=10000000;used[i]=0;for(j=1;j<n;j++)d[i][j]=10000000;}
	for(i=0;i<m;i++){
		scanf("%d,%d,",&a,&b);
		scanf("%d,%d",&d[a][b],&d[b][a]);
	}
	scanf("%d,%d,%d,%d",&s,&g,&ans,&t);ans-=t;
	v[s]=0;
	while(1){
		x=-1;
		for(i=1;i<=n;i++)if(used[i]==0 && (x==-1 || v[i]<v[x]))x=i;
		if(x==-1)break;
		used[x]=1;
		//printf("v[%d]=%d\n",x,v[x]);
		for(i=1;i<=n;i++)v[i]=min(v[i],v[x]+d[x][i]);
	}ans-=v[g];
	for(i=1;i<=n;i++)v[i]=10000000,used[i]=0;
	v[g]=0;
	while(1){
		x=-1;
		for(i=1;i<=n;i++)if(used[i]==0 && (x==-1 || v[i]<v[x]))x=i;
		if(x==-1)break;
		used[x]=1;
		//printf("v[%d]=%d\n",x,v[x]);
		for(i=1;i<=n;i++)v[i]=min(v[i],v[x]+d[x][i]);
	}
	ans-=v[s];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 0
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int X = sc.nextInt();
		HashSet<Integer> A = new HashSet<Integer>();
		for (int i = 0; i < M; i++)
			A.add(sc.nextInt());
		sc.close();

		int ansLeft = 0;
		int ansRight = 0;

		for (int i = X; i >= 0; i--)
			if (A.contains(i))
				ansLeft++;
		for (int i = X; i <= N; i++)
			if (A.contains(i))
				ansRight++;

		System.out.println(Math.min(ansLeft, ansRight));
	}
}

Measured memory_bytes: 20688
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
using namespace std;

int main(){
    long long n, sum = 0, a;
    cin >> n;
    vector<long long> csum(n);
    for (int i = 0; i < n; i++) {
        cin >> a;
        sum += a;
        if(!i){
            csum[i] = a;
            continue;
        }
        csum[i] += csum[i-1] + a;
    }
    long long ans = 1LL<<58;
    for (int i = 0; i < n-1; i++) {
        ans = min(ans, abs(sum - 2*csum[i]));
    }
    cout << ans << endl;
    return 0;
}


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

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ldb long double 
#define db double
#define str string

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mpr make_pair

#define pi pair<int,int>
#define pll pair<ll,ll>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vll vector<ll>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >
#define vpll vector< pll >

#define mi map<int,int>
#define mll map<ll,ll>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int md = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18; 
const ldb PI = 4*atan((ldb)1);

ll power(ll a,ll n)
{
 ll res=1;
 while(n)
{
 if(n%2)
  res=(res%md*a%md)%md;
  a=(a%md*a%md)%md;
  n/=2;
}
res%=md;
return res;
}

ll abst(ll a)
{
 return ((a<0)?(-1*a):(a));
}
ll spf[2000001],pr[2000001];
int main()
{
fast;
for(int i=0;i<=2000000;i++)
 spf[i]=i,pr[i]=0;
  for(int i=2;i*i<=2000000;i++)
  {
      if(spf[i]==i)
      {
          for(int j=i*i;j<=2000000;j+=i)
          {
              if(spf[j]==j)
               spf[j]=i;
          }
      }
  }
    ll n;
    cin>>n;
    ll arr[n];
    for(int i=0;i<n;i++)
     cin>>arr[i];
    for(int i=0;i<n;i++)
    {
        ll c=arr[i];
        while(c>1)
        {
            ll z=spf[c];
            ll tmp=0;
            while(c%z==0)
            {
                c/=z;
                tmp++;
            }
            pr[z]=max(pr[z],tmp);
        }
    }
    ll lc=1;
    for(int i=2;i<=2000000;i++)
    {
        lc=(lc%md*power(i,pr[i])%md)%md;
    }
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        ll q=(lc%md*power(arr[i],md-2)%md)%md;
        sum=(sum%md+q%md)%md;
    }
    cout<<sum<<"\n";
    return 0;
}

Measured memory_bytes: 31616
s = input()

x,y = map(int,input().split())

l = []

for c in s:
    if l==[]:
        l.append([c,1])
    else:
        if c==l[-1][0]:
            l[-1][1]+=1
        else:
            l.append([c,1])

hori = True

h = []
v = []
if l[0][0]=='F':
    x-=l[0][1]
    l = l[1:]

for p in l:
    d = p[0]
    r = p[1]
    if d == 'T':
        hori ^= r%2
    
    elif d == 'F':
        if hori:
            h.append(r)
        else:
            v.append(r)

h.append(abs(x))
v.append(abs(y))
h.sort(reverse=True)
v.sort(reverse=True)
sh,sv = 0,0

for a in h:
    if sh > 0:
        sh -= a
    else:
        sh += a

if sh!=0:
    print("No")
    exit(0)

for b in v:
    if sv > 0:
        sv -= b
    else:
        sv += b

if sv!=0:
    print("No")
    exit(0)

print("Yes")


Measured memory_bytes: 3956
#include<stdio.h>
#include<string.h>
int main(void){
  
  int a=0;
  char s1[200005],s2[200005];
  
  scanf("%s",s1);
  scanf("%s",s2);
  int i;
  for(i=0;i<strlen(s1);i++){
   if(s1[i] != s2[i]) a++; 
  }
  
  printf("%d",a);
  
  return 0;
}
    

Measured memory_bytes: 2128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int A = in.nextInt();
            int B = in.nextInt();
            int C = in.nextInt();
            System.out.println(B + C >= A ? (B + C - A) : 0);
        }
    }
}


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

int main(void) {
	int a, b, c, d, e, f;
	cout << fixed << setprecision(3);
	while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) != EOF) {
		double x = (double)(c * e - f * b) / (a * e - d * b);
		if (abs(x) < 0.001) x = 0;
		double y = (c - a * x) / b;
		cout << x << " " << y << endl;
	}
}


Measured memory_bytes: 3184
w0, h0 = 0, 0
w, h, n = map(int, input().split())
for _ in range(n):
    x, y, a = map(int, input().split())
    if a == 1 and w0 < x:
        w0 = x
    elif a == 2 and x < w:
        w = x
    elif a == 3 and h0 < y:
        h0 = y
    elif a == 4 and y < h:
        h = y

print([0, (w - w0) * (h - h0)][w - w0 > 0 < h - h0])

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

class Program
{
    static void Main(string[] args)
    {
        var N = sc.ReadLong();
        long ans = 0;
        for (int i = 1; i <= Math.Sqrt(N); i++)
        {
            var m = (N - i) / i;
            if (m > 0 && N / m == N % m)
            {
                ans += m;
            }
        }
        Console.WriteLine(ans);
    }
    static Scanner sc = new Scanner();
}

class Scanner
{
    string[] S = new string[0];
    int Index = 0;
    char[] Separators = new char[] { ' ' };

    public string Next()
    {
        if (this.Index < this.S.Length) return this.S[this.Index++];
        var line = "";
        while (line == "") line = Console.ReadLine();
        this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
        if (this.S.Length == 0) return this.Next();
        this.Index = 0;
        return this.S[this.Index++];
    }
    public string ReadStr()
    {
        return this.Next();
    }
    public char ReadChar()
    {
        return this.Next()[0];
    }
    public int ReadInt()
    {
        return int.Parse(this.Next());
    }
    public uint ReadUInt()
    {
        return uint.Parse(this.Next());
    }
    public long ReadLong()
    {
        return long.Parse(this.Next());
    }
    public double ReadDouble()
    {
        return double.Parse(this.Next());
    }
    public int[] ReadIntArray(int n)
    {
        var array = new int[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadInt();
        }
        return array;
    }
    public long[] ReadLongArray(int n)
    {
        var array = new long[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadLong();
        }
        return array;
    }
    public double[] ReadDoubleArray(int n)
    {
        var array = new double[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadDouble();
        }
        return array;
    }
    public char[] ReadCharArray(int n)
    {
        var array = new char[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadChar();
        }
        return array;
    }
    public string[] ReadStrArray(int n)
    {
        var array = new string[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadStr();
        }
        return array;
    }
}


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

int main(void) {
	int A, B;
	scanf("%d %d", &A, &B);
	if ((A + B) % 2 == 0) {
		printf("%d\n", (A + B) / 2);
	} else {
		printf("IMPOSSIBLE");
	}
	return 0;
}


Measured memory_bytes: 256
class DisjointSet
  attr_accessor :n

  class Node
    attr_accessor :p, :rank

    def initialize
      @p, @rank = 0, 0
    end
  end

  def initialize(size)
    @n = Array.new(size) { Node.new }
    (0..size-1).each { |i| @n[i].p = i }
  end

  def unite(x, y)
    link(find_set(x), find_set(y))
  end

  def link(x, y)
    if @n[x].rank > @n[y].rank
      @n[y].p = x
    else
      @n[x].p = y
      @n[y].rank += 1 if @n[x].rank == @n[y].rank
    end
  end

  def find_set(x)
    if x != @n[x].p
      @n[x].p = find_set(@n[x].p)
    end
    return @n[x].p
  end

  def same(x, y)
    return find_set(x) == find_set(y)
  end
end

#main
n, q = gets.split.map &:to_i
ds = DisjointSet.new(n)
q.times do
  com, x, y = gets.split.map &:to_i
  case com
  when 0
    ds.unite(x, y)
  when 1
    puts ds.same(x, y) ? 1 : 0
  end
end

Measured memory_bytes: 8984
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define int long long 

typedef pair<int,int>pi;
typedef vector<int>vi;

const int MAXN=100005;
const int MOD=1000000007;
const int INF = 1e9+1;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

int N, M, A[MAXN], B[MAXN];

int plcm(int x, int y){
	if (x>=INF && y>=INF) return INF;
	int lcm = x*y/__gcd(x,y);
	return min(lcm,INF);
}

main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>M;
	int prb = -1;
	FOR(i,1,N){
		cin>>A[i];
		int tmp=A[i];
		while (tmp%2==0){
			tmp/=2;
			B[i]++;
		}
		if (prb == -1) prb = B[i];
		else if (prb != B[i]){
			cout<<0;
			exit(0);
		}
	}
	int totlcm = 1;
	FOR(i,1,N){
		totlcm = plcm(totlcm, A[i]/2);
	}
	if (totlcm > M) {
		cout<<0;
		exit(0);
	}
	int ans = (M-totlcm)/(2*totlcm);
	cout<<ans+1;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
  ll N,ans=0,cnt=0;
  cin>>N;
  vector<vector<char>> c(N,vector<char>(10));
  for(ll i=0;i<N;i++){
    for(int j=0;j<10;j++) cin>>c[i][j];
  }
  
  for(ll i=0;i<N;i++) sort(c[i].begin(),c[i].end());
  sort(c.begin(),c.end());
  
  for(ll i=0;i<N;i+=cnt+1){
    cnt=0;
    for(ll j=i+1;j<N;j++){
      if(c[i]==c[j]) cnt++;
      else break;
    }
    ans+=(cnt+1)*cnt/2;
  }
  cout<<ans<<endl;
}


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

int n;
set<int>s;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		int x;
		scanf("%d",&x);
		if( s.count(x)==1 ) s.erase(x);
		else if( s.count(x)==0 ) s.insert(x);
	}
	printf("%d\n",s.size());
}

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


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

if (b/a>=c) cout<< c << endl;
else cout << b/a << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言
#define MAX 100000

//問題をよく読もう！
//論理的に考えよう！
//サンプルを確認しよう!
//絶対に諦めるな！
//工夫をしろ！
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;

  int left = A + B;
  int right = C + D;

  if(left == right)
    cout << "Balanced" << endl;
  else if(left > right)
    cout << "Left" << endl;
  else
    cout << "Right" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Set         std::set
#define PQueue      std::priority_queue
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define HashMap     std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    template<class A, class B> A power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    template<class A, class B> A power ( A x, B n ) { return power( x, n, 1000000007 ); }
    template<class A> A gcd ( A x, A y ) { return x % y ? gcd( y, x % y ) : y; }
    template<class A, class B> A lcm   ( A x,  B y ) { return ( x / gcd(x, y) * y ); }
    template<class A> inline A abs ( A n ) { return ( n < 0 ) ? -n : n; }
    template<class A, class B> inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B> inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    signed call_of_Cthulhu( signed datum ) {

        llong x, y;
        read x >> y;
        int cnt = 0;
        for ( llong i = x; i <= y; i*=2 ) cnt++;
        echo cnt fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); int main_result = Rlyeh::call_of_Cthulhu(114514); return 0;}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back()
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

vector<int> l;
int n;
int ret=1e9;
void dfs(int x,int y,int z,int a,int b,int c,int i,int ans){
    if(i==n){
        if(a==0||b==0||c==0) return;
        int res=ans+abs(x-a)+abs(y-b)+abs(z-c);
        chmin(ret,res);
        return;
    }
    dfs(x,y,z,a+l[i],b,c,i+1,a?ans+10:ans);
    dfs(x,y,z,a,b+l[i],c,i+1,b?ans+10:ans);
    dfs(x,y,z,a,b,c+l[i],i+1,c?ans+10:ans);
    dfs(x,y,z,a,b,c,i+1,ans);
}
signed main(){
    int a,b,c; cin >> n >> a >> b >> c;
    l.resize(n);
    rep(i,n) cin >> l[i];
    dfs(a,b,c,0,0,0,0,0);
    cout << ret << endl;
}



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

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
vector< T > bellman_ford(Edges< T > &edges, int V, int s) {
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(V, INF);
  dist[s] = 0;
  for(int i = 0; i < V - 1; i++) {
    for(auto &e : edges) {
      if(dist[e.src] == INF) continue;
      dist[e.to] = min(dist[e.to], dist[e.src] + e.cost);
    }
  }
  for(auto &e : edges) {
    if(dist[e.src] == INF) continue;
    if(dist[e.src] + e.cost < dist[e.to]) return vector< T >();
  }
  return dist;
}

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

  int N, M, P;
  cin >> N >> M >> P;

  Edges<int> es;

  vector<int> G[3000], G2[3000];  

  for ( int i = 0; i < M; i++ ) {
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    G[a].emplace_back(b);
    G2[b].emplace_back(a);
    es.emplace_back(a, b, -(c-P));    
  }

  vector<int> cnt(3000, 0);
  {
    vector<bool> used(3000, false);
    queue<int> Q;
    Q.push(0);
    while ( !Q.empty() ) {
      int u = Q.front(); Q.pop();

      if ( used[u] ) continue;
      used[u] = true;
      cnt[u]++;

      for ( int v : G[u] ) {
	Q.push(v);	
      }
    }
  }
  {
    vector<bool> used(3000, false);
    queue<int> Q;
    Q.push(N-1);
    while ( !Q.empty() ) {
      int u = Q.front(); Q.pop();

      if ( used[u] ) continue;
      used[u] = true;
      cnt[u]++;

      for ( int v : G2[u] ) {
	Q.push(v);	
      }
    }
  }

  Edges<int> es2;
  for ( int i = 0; i < M; i++ ) {
    int a = es[i].src, b = es[i].to;
    if ( cnt[a] == 2 && cnt[b] == 2 ) es2.push_back(es[i]);    
  }

  auto dists = bellman_ford(es2, N, 0);
  if(dists.empty()) cout << -1 << endl;
  else cout << max(0, -dists[N-1]) << endl;

  return 0;
}



Measured memory_bytes: 768
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <map>
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

inline int getInt(){ int s; scanf("%d", &s); return s; }
inline string getStr(){ char s[16]; scanf("%s", s); return string(s); }

class UnionFind{
private:
  mutable vector<int> id;

  int getId(int i) const{
    if(i == id[i]) return i;
    return id[i] = getId(id[i]);
  }
public:
  UnionFind(int size = 0){ init(size); }
  ~UnionFind(){}
  void init(int size){
    id = vector<int>(size);
    for(int i = 0; i < size; i++)
      id[i] = i;
  }
  void unite(int i, int j){
    int next = min( getId(i), getId(j) );
    id[getId(i)] = id[getId(j)] = next;
  }
  int operator [](int i) const{ return getId(i); }
  int count() const{
    set<int> s;
    for(int i = 0; i < (int)id.size(); i++)
      s.insert(getId(i));
    return s.size();
  }
};


int main(){
  const int n = getInt();
  map<string, int> m;
  vector<int> x(n);

  REP(i,n){
    m[getStr()] = i;
    x[i] = getInt();
  }

  UnionFind uf(n);

  const int k = getInt();
  REP(i,k){
    const int s = m[getStr()];
    const int t = m[getStr()];
    uf.unite(s, t);
  }

  vector<int> mn(n, 1000000);
  REP(i,n){
    mn[uf[i]] = min(mn[uf[i]], x[i]);
  }

  int ans = 0;
  REP(i,n) ans += mn[uf[i]];

  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 1864
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

std::string s;

int main()
{
	in >> s;
	out << s[0] << s.length() - 2 << s[s.length() - 1] << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    string S;
    cin >> S;
    if(S == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }
    return 0;
}

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

using namespace std;

typedef long long ll;

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

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

ll F( ll a, ll b, ll c){
  ll res = 0;
  res += b / c; res -= ( a + c - 1) / c; res++;
  return res;}
  

int main(){
  ll A,B,C,D;  cin >> A >> B >> C >> D;
  
  ll res = 0;
  res += F( A, B, C);
  res += F( A, B, D);
  res -= F( A, B, lcm( C,D));
  
  cout << B - A + 1 - res << endl; return 0;}

 
    
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    for(long long i=sqrt(n);i>0;i--){
        if(n%i==0){
            if(n/i<10){
                cout<<1<<endl;
            }
            else if(n/i<100){
                cout<<2<<endl;
            }
            else if(n/i<1000){
                cout<<3<<endl;
            }
            else if(n/i<10000){
                cout<<4<<endl;
            }
            else if(n/i<100000){
                cout<<5<<endl;
            }
            else if(n/i<1000000){
                cout<<6<<endl;
            }
            else if(n/i<10000000){
                cout<<7<<endl;
            }
            else if(n/i<100000000){
                cout<<8<<endl;
            }
            else if(n/i<1000000000){
                cout<<9<<endl;
            }
            else if(n/i<10000000000){
                cout<<10<<endl;
            }
            return 0;
        }
    }
}

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

int main(){
  int a,b[300];
  cin>>a;
  for(int i=1;i<=a;i++){
    cin>>b[i];
  }
  for(int i=1;i<=a;i++){
    cout<<"node "<<i<<": key = "<<b[i]<<", ";
    if(i/2>0)cout<<"parent key = "<<b[i/2]<<", ";
    if(i*2<=a)cout<<"left key = "<<b[i*2]<<", ";
    if(i*2+1<=a)cout<<"right key = "<<b[i*2+1]<<", ";
    cout<<endl;
  }
  return 0;
}

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

int main(){
	//ios::sync_with_stdio(0);cin.tie(0);
	vector<ll> v;
	ll n;
	cin >> n;
	v.resize(n);
	for(auto& i:v)
		cin >> i;
	map<ll, ll, greater<ll>> cnt;
	for(const auto& i:v){
		if(cnt.find(i)==cnt.end())
			cnt[i]=0;
		cnt[i]++;
	}
	ll a, b;
	a=b=0;
	for(auto& i:cnt){
		if(i.second>=2){
			i.second-=2;
			a=i.first;
			break;
		}
	}
	for(auto& i:cnt){
		if(i.second>=2){
			b = i.first;
			break;
		}
	}
	cout << a*b << "\n";
	return 0;
}


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

bool isOver(int x, int y, int n)
{
	if (x<0||n<=x||y<0||n<=y) return true;
	return false;
}

int main()
{
	int d, i, n, j, k;
	int x, y, dir;
	int turn;
	char s[101][101];
	int dx[4] = {0, 1, 0, -1};
	int dy[4] = {-1, 0, 1, 0};
	int chkx[4] = {1, 1, -1, -1};
	int chky[4] = {-1, 1, 1, -1};
	cin>>d;
	for (i = 0; i < d; i++) {
		cin>>n;
		for (j = 0; j < n; j++)
			for (k = 0; k < n; k++)
				s[k][j] = ' ';
		x = 0; y = n-1; dir = 0;
		turn = 0;
		while (turn<4) {
			s[x][y] = '#';
			if ( isOver(x+dx[dir], y+dy[dir], n) ) {
				dir = (dir+1)%4;
				turn++;
				continue;
			}
			if ( !isOver(x+2*dx[dir], y+2*dy[dir], n) ) {
				if (s[x+2*dx[dir]][y+2*dy[dir]] == '#') {
					dir = (dir+1)%4;
					turn++;
					continue;
				}
			}
			if ( !isOver(x+chkx[dir], y+chky[dir], n) )
				if (s[x+chkx[dir]][y+chky[dir]] == '#') break;
			x += dx[dir];
			y += dy[dir];
			turn = 0;
		}
		if (i) cout<<endl;
		for (j = 0; j < n; j++) {
			for (k = 0; k < n; k++) {
				cout<<s[k][j];
			}
			cout<<endl;
		}
	}
	return 0;
}

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

int main(){
	int N, K, i, j;
	scanf("%d%d", &N, &K);
	double ans = 0;
	for(i = 1; i <= N; i++){
		double now = 1;
		for(j = i; j < K; j *= 2){
			now /= 2;
		}
		ans += now / N;
	}
	printf("%.12lf\n", ans);
	return 0;
}

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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define vi vector<int>

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int N = 1005;

int a[N], b[N];
int f[N][N];
vector<int> R[N * N], C[N * N];
int done_row[N], done_col[N];
const int mod = 1e9 + 7;
inline int mul(int a, int b){ return (a * (ll) b) % mod; }
int main(){
	int n, m; sd(n); sd(m);
	for(int i = 1; i <= n; i++){
		sd(a[i]);
		R[a[i]].push_back(i);
	}
	for(int i = 1; i <= m; i++){
		sd(b[i]);
		C[b[i]].push_back(i);
	}

	for(int i = 1; i <= n * m; i++){
		if(R[i].size() > 1 || C[i].size() > 1){
			printf("0\n");
			return 0;
		} 
	}
	
	int ans = 1, z = 0;
	int cols = 0, rows = 0, total = 0;
	for(int i = n * m; i >= 1; i--){
		if(R[i].size() + C[i].size() == 2){
			int r = R[i][0], c = C[i][0];
			f[r][c] = i;
			rows++; cols++; total++;
		}  else if(R[i].size() + C[i].size() == 1){
			if(!R[i].empty()){
				rows++;
				ans = mul(ans, cols);
			} else{
				cols++;
				ans = mul(ans, rows);
			}
		} else{
			ans = mul(ans, rows * cols - z);
		}
		z++;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 51584
#include <stdio.h>
int main(void)
{
  char str[100];
  int i;
  for(i=0;i<3;++i){
    scanf("%s", str+i);
    str[i] &= 0xdf;
  }
  str[i]='\0';
  printf("%s\n", str);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <cmath>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int count(int N)
{
        int cnt = 0;
        while (N)
        {
                cnt += N % 10;
                N /= 10;
        }
        return cnt;
}

int main()
{
        int N, M;
        cin >> N;
        map<string, int> blue;
        map<string, int> red;
        rep(i, N)
        {
                string a;
                cin >> a;
                blue[a]++;
        }
        cin >> M;
        rep(i, M)
        {
                string a;
                cin >> a;
                blue[a]--;
        }

        int ans = 0;
        for (auto itr = blue.begin(); itr != blue.end(); itr++)
        {
                ans = max(ans, itr->second);
        }
        cout << ans << endl;

        return 0;
}


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

int main () {
  int N,M;
  cin >> N >> M;
  priority_queue <int> q;
  for (int i = 0; i < N; i++) {
    int x;
    scanf("%d",&x);
    q.push(x);
  }
  
  for (int i = 0; i < M; i++) {
    int x = q.top();
    q.pop();
    q.push(x/2);
  }
  
  int64_t sum = 0;
  while(!q.empty()) {
    sum += q.top();
    q.pop();
  }
  cout << sum;
}

Measured memory_bytes: 892
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

class unionFind{
  constructor(n){this.a=Array(n+1).fill(-1);}
  root(i){
    return this.a[i]<0?i:this.a[i]=this.root(this.a[i]);
  }
  same(x,y){return this.root(x)===this.root(y);}
  unite(x,y){
    const a=this.a;
    x=this.root(x),y=this.root(y);
    if(x===y)return false;
    if(a[y]<a[x])a[y]+=a[x],a[x]=y;
    else a[x]+=a[y],a[y]=x;
    return true;
  }
  size(i){return -this.a[this.root(i)];}
}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));

function main(){
  var n = next();
  var a = [];
  for(var i = 0; i < n; i++){
    a.push([next(),next(),i]);
  }
  var g = [];
  a.sort((a,b)=>a[0]-b[0]);
  for(var i = 1; i < n; i++){
    var u = a[i-1][2], v = a[i][2], d = a[i][0] - a[i-1][0];
    g.push([u,v,d]);
  }
  a.sort((a,b)=>a[1]-b[1]);
  for(var i = 1; i < n; i++){
    var u = a[i-1][2], v = a[i][2], d = a[i][1] - a[i-1][1];
    g.push([u,v,d]);
  }
  g.sort((a,b)=>a[2]-b[2]);
  var ans = 0;
  var uf = new unionFind(n);
  for(var i = 0; i < g.length; i++){
    if(uf.unite(g[i][0],g[i][1]))ans += g[i][2];
  }
  return ans;
}

Measured memory_bytes: 89648
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::string s;
    std::cin >> s;
    int m = std::atoi(s.substr(5, 2).c_str());
    std::cout << (m < 5 ? "Heisei" : "TBD") << std::endl;

    return 0;
}


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

bool prm[1010];

int main(){
    int n; cin>>n;
    ll fct[100010];
    fct[1]=1;
    for(int i=2;i<=n;i++){
        fct[i]=(fct[i-1]*i)%MOD;
    }
    cout<<fct[n]<<endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main(void){
	int num[101]={0},cnt[100]={0},i,j=0,k;
	while(scanf("%d",&num[cnt[0]])!=EOF)cnt[0]++;
	for(i=0;i<cnt[0];i++){
		for(j=i+1;j<cnt[0];j++){
			if(num[i]>num[j]){
				num[100]=num[i];
				num[i]=num[j];
				num[j]=num[100];
			}
		}
	}
	for(i=0;i<j-1;i++)
		if(num[i]==num[i+1])
				cnt[num[i]]++;
	for(i=0;i<j-1;i++){
		for(k=i+1;k<j-1;k++){
			if(cnt[num[i]]<cnt[num[k]]){
				num[100]=num[i];
				num[i]=num[k];
				num[k]=num[100];
			}
		}
	}
	for(i=0;;i++){
		if(num[i]==0 || cnt[num[i]]!=cnt[num[i+1]])break;
		if(num[i-1]==num[i])continue;
		printf("%d\n",num[i]);
	}
	return 0;
}		

Measured memory_bytes: 596
#include <iostream>                                                                                    
using namespace std;                                                                                   
                                                                                                       
int main(int argc, char *argv[])                                                                       
{                                                                                                      
    int N, A, B;                                                                                       
                                                                                                       
        cin >> N;                                                                                      
        if (N == 1)                                                                                    
                cout << "Hello World\n";                                                               
        else if (N == 2) {                                                                             
                cin >> A >> B;                                                                         
                cout << A + B << endl;                                                                 
        }                                                                                              
                                                                                                       
        return 0;                                                                                      
}                

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif
 
typedef long long int ll;
typedef pair<int,int> pii;
template<typename T> using vec=std::vector<T>;
 
const int inf=1<<30;
const long long int infll=1LL<<62;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}
 
int myrand(){
    static random_device rd;
    static mt19937 eng(rd());
    return eng();
}
 
double pw,vw[100000],pf[100000],vf[100000],th[100000];
 
void solve(int n){
    scanf("%lf",&pw);
    rep(i,0,n) scanf("%lf%lf%lf%lf",vw+i,pf+i,vf+i,th+i);
 
    vector<double> v={0};
    rep(i,0,n) if(vw[i]!=0 and th[i]/vw[i]>=0) v.push_back(th[i]/vw[i]);
    //sort(v.begin(),v.end());
    //rep(i,0,v.size()-1) if(v[i+1]-v[i]<=1e-5) v[i+1]=v[i];
    //v.erase(unique(v.begin(),v.end()),v.end());
 
    double ans=inf;
    for(double w:v){
        if(v.size()>=8000 and myrand()%5==0) continue;
        double d=w*pw;
        rep(i,0,n){
            if(d>=ans) break;
            d+=pf[i]*max(0.,(th[i]-w*vw[i])/vf[i]);
        }
        ans=min(ans,d);
    }
    printf("%f\n",ans);
}
 
int main(){
    while(true){
        int n;
        scanf("%d",&n);
        if(!n) break;
        solve(n);
    }
    return 0;
}

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

int main(){
    int n; cin >> n;
    vector<int> a(n+5,0),s(n+5,0),t(n+5,0),u(n+5,0);
    REP(i,n) cin >> a[i+1];
    for(int i = 0; i <= n; ++i) s[i] = abs(a[i+1] - a[i]);
    for(int i = 0; i <= n; ++i) t[i+1] = t[i] + s[i];
    for(int i = n; i > 0; --i) u[i-1] = u[i] + s[i];
    for(int i = 1; i <= n; ++i) cout << t[i-1] + u[i] + abs(a[i+1] - a[i-1]) << endl;
}

Measured memory_bytes: 2816
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const int mod=1e9+7;

int main(){
    int n;
    cin>>n;
    int a[200020];
    ll sum1=0;
    ll sum2=0;
    rep(i,0,n){
        cin>>a[i];
        sum1+=a[i];
    }
    ll ans=100000000000000000;
    ll cnt=0;
    rep(i,0,n-1){
        sum2+=a[i];
        sum1-=a[i];
        ans=min(ans,abs(sum2-sum1));
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100005

vector<int>edge[MAX];
int in_degree[MAX], dp[MAX], ans = 0;

int dfs(int u)
{
	if(dp[u]!=0)
		return dp[u];

	for(auto v : edge[u])
		dp[u]=max(dp[u], 1+dfs(v));

	ans = max(ans, dp[u]);

	return dp[u];
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n, m;
    scanf("%d %d",&n, &m);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        in_degree[b]++;
        edge[a].push_back(b);
    }

    for(int i = 1; i <= n; i++)
    {
        if(!in_degree[i])
            dfs(i);
    }

    printf("%d", ans);

    return 0;
}


Measured memory_bytes: 9600