akhauriyash/Code-Regression huggingface dataset:
def yumiri(L, n):
  for i in range(len(L)):
    if L[i] > n:
      return i - 1

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(input()) for _ in range(D)]
M = int(input())
dq = [list(map(int, input().split())) for _ in range(M)]

L = [0] * 26
ZL = [[0] for _ in range(26)]
SUMD = [0] * (D + 1)
for i in range(1, D + 1):
  SUMD[i] = SUMD[i - 1] + i

ans = 0
for i in range(D):
  ans += s[i][t[i] - 1]
  for j in range(26):
    if t[i] - 1 == j:
      L[j] = 0
      ZL[j].append(i + 1)
    else:
      L[j] += 1
      ans -= L[j] * c[j]
for i in range(26):
  ZL[i].append(D + 1)

for d, q in dq:
  rd = t[d - 1] - 1
  rq = yumiri(ZL[rd], d)
  ans += SUMD[ZL[rd][rq] - ZL[rd][rq - 1] - 1] * c[rd]
  ans += SUMD[ZL[rd][rq + 1] - ZL[rd][rq] - 1] * c[rd]
  ans -= SUMD[ZL[rd][rq + 1] - ZL[rd][rq - 1] - 1] * c[rd] 
  ZL[rd].remove(d)
  
  nd = q - 1
  nq = yumiri(ZL[nd], d)
  ans += SUMD[ZL[nd][nq + 1] - ZL[nd][nq] - 1] * c[nd]
  ans -= SUMD[d - ZL[nd][nq] - 1] * c[nd]
  ans -= SUMD[ZL[nd][nq + 1] - d - 1] * c[nd]
  ZL[nd].insert(nq + 1, d)

  ans -= s[d - 1][rd]
  ans += s[d - 1][nd]

  t[d - 1] = q

  print(ans)



Measured memory_bytes: 88668
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
char grid[1005][1005];
ll dp[1005][1005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> grid[i][j];
	for (int i = 1; i < n && grid[i][0] == '.'; ++i)
		dp[i][0] = 1;
	for (int i = 1; i < m && grid[0][i] == '.'; ++i)
		dp[0][i] = 1;
	for (int i = 1; i < n; ++i)
		for (int j = 1; j < m; ++j)
			if (grid[i][j] == '.')
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
	cout << dp[n - 1][m - 1] << '\n';
	return 0;
}

Measured memory_bytes: 9088
from collections import deque

N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
minMP = 10**5

p = deque()
p.append([-1] * len(L))
while p:
    stats = p.pop()
    stats = list(stats)
    a, b, c = 0, 0, 0
    MP = 0
    cntA = 0; cntB = 0; cntC = 0
    for i in range(N):
        if stats[i] == 1:
            a += L[i]
            cntA += 1
        elif stats[i] == 2:
            b += L[i]
            cntB += 1
        elif stats[i] == 3:
            c += L[i]
            cntC += 1

    if cntA >= 1 and cntB >= 1 and cntC >= 1:
        MP += abs(A - a) + abs(B - b) + abs(C - c) + 10 * (cntA+cntB+cntC-3)
        minMP = min(minMP, MP)

    if not -1 in stats:
        continue
    j = stats.index(-1)
    for k in range(4):
        stats[j] = k
        newStats = tuple(stats)
        p.append(newStats)

print(minMP)


Measured memory_bytes: 3316
#include <iostream>

int main()
{
	int A, B, K;
	std::cin >> K >> A >> B;
	B -= A-1;
	B += (A-1) % K;
	if (B < K) {
		std::cout << "NG";
	}
	else {
		std::cout << "OK";
	}
}

Measured memory_bytes: 3628
A = input()
B = input()
if A=="1" and B=="2":
    print("3")
elif A=="1" and	B =="3":
    print("2")
elif A=="2" and	B=="1":
    print("3")
elif A=="2" and	B=="3":
    print("1")
elif A=="3" and	B=="1":
    print("2")
elif A=="3" and	B=="2":
    print("1")

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define YES(n) cout << (n?"YES":"NO")<<endl;
#define Yes(n) cout << (n?"Yes":"No")<<endl;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(A*N, B) << endl;
}

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

int main() {
  int n;
  cin>>n;
  vector<long long int> vec(n);
  for(int i=0;i<n;i++){
    cin>>vec.at(i);
  }
  
  if(n%2==0){
    vector<long long int> before(n/2);
    vector<long long int> after(n/2);
    sort(vec.begin(),vec.end());
    
    for(int i=0;i<n/2;i++){
     before.at(i)=vec.at(i);
    }
    for(int i=0;i<n/2;i++){
     after.at(i)=vec.at(i+n/2);
    }
    
    
    reverse(before.begin(),before.end());
    reverse(after.begin(),after.end());
    
    long long int answer=0;
    for(int i=0;i<n/2-1;i++){
      answer+=abs(after.at(i)-before.at(i))+abs(after.at(i)-before.at(i+1));
    }
    answer+=abs(after.at(n/2-1)-before.at(n/2-1));
    cout<<answer<<endl;
  }
  
  else{
    vector<long long int> before(n/2);
    vector<long long int> after(n/2+1);
    
    vector<long long int> beforef(n/2+1);
    vector<long long int> afterf(n/2);
    sort(vec.begin(),vec.end());
    
    for(int i=0;i<n/2;i++){
     before.at(i)=vec.at(i);
    }
    for(int i=0;i<n/2+1;i++){
     after.at(i)=vec.at(i+n/2);
    }
    
    for(int i=0;i<n/2+1;i++){
     beforef.at(i)=vec.at(i);
    }
    for(int i=0;i<n/2;i++){
     afterf.at(i)=vec.at(i+n/2+1);
    }
    
    long long int u;
    u=after.at(1);
    after.at(1)=after.at(n/2);
    after.at(n/2)=u;
    
    u=beforef.at(0);
    beforef.at(0)=beforef.at(n/2-1);
    beforef.at(n/2-1)=u;
    
    long long int p=0,q=0;
    
    for(int i=0;i<n/2;i++){
      p+=abs(before.at(i)-after.at(i))+abs(before.at(i)-after.at(i+1));
    }
    for(int i=0;i<n/2;i++){
      q+=abs(afterf.at(i)-beforef.at(i))+abs(afterf.at(i)-beforef.at(i+1));
    }
    
    cout<<max(p,q)<<endl;
    
  }
    
}

Measured memory_bytes: 2560
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    S = input()
    N = len(S)
    T = input()
    M = len(T)
    ans = INF
    for i in range(N-M+1):
        cnt = 0
        for k in range(M):
            if S[i+k] != T[k]:
                cnt += 1
        ans = min(ans, cnt)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9392
s = input()
LOWER = "abcdefghijklmnopqrstuvwxyz"
trans = {}
for i in range(len(LOWER)):
    trans[LOWER[i]] = str.upper(LOWER[i])
    trans[str.upper(LOWER[i])] = LOWER[i]
print(s.translate(str.maketrans(trans)))



Measured memory_bytes: 5568
// Aizu 0536: Shuffle
// 2017.10.26 bal4u@uu

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

typedef struct { int x1, x2; } TABA;
TABA taba[2][10005]; int sz;
int k1, k2;

int split(int x)
{
	int s, i, k;

	for (s = 0, i = 0; ; i++) {
		k = taba[k1][i].x2 - taba[k1][i].x1 + 1;
		if (s + k == x) return i;
		if (s + k > x) break;
		s += k;
	}
	memmove(taba[k1]+i+1, taba[k1]+i, sizeof(TABA)*(sz-i)), sz++;
	x = (x-s)+taba[k1][i].x1-1;
	taba[k1][i].x2 = x, taba[k1][i+1].x1 = x+1;
	return i;
}

void shuffle(int x, int y)
{
	int i, j, s;

	i = split(x), j = split(y);
	s = 0;
	memcpy(taba[k2],   taba[k1]+j+1, sizeof(TABA)*(sz-j-1)); s += sz - j - 1;
	memcpy(taba[k2]+s, taba[k1]+i+1, sizeof(TABA)*(j-i));    s += j-i;
	memcpy(taba[k2]+s, taba[k1],     sizeof(TABA)*(i+1));
	k1 = k2, k2 = !k2;
}

int main()
{
	int n, m, p, q, r, x, y;
	int i, ans;

	while (scanf("%d", &n) && n > 0) {
		scanf("%d%d%d%d", &m, &p, &q, &r);
		taba[0][0].x1 = 1, taba[0][0].x2 = n, k1 = 0, k2 = 1, sz = 1;
		while (m-- > 0) {
			scanf("%d%d", &x, &y);
			shuffle(x, y);
		}
		x = 0; if (p > 1) x = split(p-1) + 1;
		y = split(q);
		for (ans = 0, i = x; i <= y; i++) {
			if (taba[k1][i].x1 > r) continue;
			if (taba[k1][i].x2 <= r) ans += taba[k1][i].x2 - taba[k1][i].x1 + 1;
			else 			         ans += r - taba[k1][i].x1 + 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1896
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c> {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
	~debug() { cerr << endl; }
	eni( != ) cerr << boolalpha << i; ris;
}
eni( == ) ris << range(begin(i), end(i));
}
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define prec fixed << setprecision(12)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define test int t; cin >> t; while(t--)
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;
int _x[] = {0, 0, -1, 1, -1, 1, -1, 1};
int _y[] = { -1, 1, 0, 0, 1, -1, -1, 1};

void solve() {
	int k, x;
    cin >> k >> x;
    if(k == 1){
        cout << x;
        return;
    }
    k--;
    for(int i = x-k; i <= x+k; ++i)
        cout << i << " ";
}

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


Measured memory_bytes: 3604
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n, q = map(int, read().split())
    uf = UnionFind(n)
    for _ in range(q):
        t, u, v = map(int, read().split())
        if t == 0:
            uf.union(u, v)
        else:
            print(int(uf.same(u, v)))


if __name__ == '__main__':
    main()


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

int main() {
	int N;
  	cin >> N;
	vector<int> A(N);
 	for(int i = 0; i < N; i++) cin >> A.at(i);

	string ans = "APPROVED";
    
      for(int i = 0; i < N; i++){
        if ( A.at(i) % 2 == 0 && A.at(i) % 3 != 0 && A.at(i) % 5 != 0){
            ans = "DENIED";
            break;
          }
      }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int A,B,X;
	scanf("%d%d%d",&A,&B,&X);
	
	 if(A+B>X)
	 {
	 	if(X>=A){
	 		printf("YES");
		 }
		 else
		 {
		 	printf("NO");
		 }
	 }
		else{
		
		printf("NO");
	}

}

Measured memory_bytes: 1724
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVETSE(c) reverse((c).begin(),(c).end())
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define ALL(a)  (a).begin(),(a).end()
// int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> T maxt(T x,T y) {
    if (x>y) return x;
    else return y;
}
template<class T> T mint(T x,T y) {
    if (x>y) return y;
    else return x;
}
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

//小数出力
double print_double(double d){printf("%.8f", d);}

long long m = 1e9+7, mod = 1e9+7;
//逆元　a/b の modをとるとき -> a*modinv(b)%mod
long long modinv(long long a, long long m = 1e9+7) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

//約数列挙
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

// int bfs

int main() {
  ll N,H;
  cin >> H >> N;
  Vi v(N);
  rep(i,N) cin >> v[i];
  ll s = SUM(v);
  if (s>=H) cout << "Yes\n";
  else cout << "No\n";
}

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

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int[] intArray = Arrays.stream(sc.nextLine().split(" "))
                           .mapToInt(Integer::parseInt)
                           .toArray();
    int a = intArray[0];
    int b = intArray[1];

    if(a == b)
    {
      System.out.printf("a == b\n");
    }
    else if(a < b)
    {
      System.out.printf("a < b\n");
    }
    else
    {
      System.out.printf("a > b\n");
    }
  }
}


Measured memory_bytes: 32024
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int A,B,H,M;
    double a,b,K,ans;
    cin>>A>>B>>H>>M;
    a=0.5*(H%12)*60+0.5*M;
    b=6*M;
    K=min(360-abs(a-b),abs(a-b));
    K=K*M_PI/180;
    ans=sqrt(pow(A,2)+pow(B,2)-2*A*B*cos(K));
    cout<<std::fixed << std::setprecision(20)<<ans<<endl;
}


Measured memory_bytes: 4192
#include <iostream>
#include <cmath>

using namespace std;

const int MAX_N = 1000000;
bool prime[MAX_N];

void eratos() {
    for (int i = 0; i < MAX_N; ++i) prime[i] = true;
	prime[0] = false;
	prime[1] = false;
	for (int i = 2; i < sqrt(MAX_N); ++i) {
		if (prime[i]) {
			for (int j = 0; i * (j + 2) < MAX_N; ++j) {
				prime[i * (j + 2)] = false;
			}
		}
	}
}

int main() {
	eratos();
	int n;
	while (cin >> n) {
		int ans = 0;
		for (int i = 2; i <= n; ++i) {
			if (prime[i]) ans++;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 2136
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        char ca[] = scanner.next().toCharArray();
        char cb[] = scanner.next().toCharArray();
        Arrays.sort(ca);
        Arrays.sort(cb);
        for (int i = 1;i <= cb.length;++i){
            if(i > ca.length){
                System.out.println("Yes");
                return;
            }
            if(ca[i - 1] > cb[cb.length - i]){
                System.out.println("No");
                return;
            }
            else if(ca[i - 1] < cb[cb.length - i]){
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
typedef long long int ll;
typedef long double ld;
#define PI 3.141592653589793
#define MOD 1000000007
#define ALL(obj) (obj).begin(),(obj).end()
template<class T>inline bool chmax(T& a,T b){if (a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T& a,T b){if (a>b){a=b;return 1;}return 0;}
const ll INF = 1LL << 60;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge{//グラフに使うヤツ
    ll from,to,cost;
};

typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

int main(){
    ll n;
    cin >> n;
    if (n>=30){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
s = input()

#奇数が1
countA = 0
for i in range(len(s)):
    if i%2==0 and s[i]=="0":
        countA += 1
    elif i%2==1 and s[i]=="1":
        countA += 1

#偶数が1
countB = 0
for i in range(len(s)):
    if i%2==0 and s[i]=="1":
        countB += 1
    elif i%2==1 and s[i]=="0":
        countB += 1

print(min(countA,countB))


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';x=(x<<1)+(x<<3)+ch-'0',ch=getchar());
	return x*f;
}
struct tree{
	int hea[maxn],nxt[maxn<<1],to[maxn<<1],tot;
	void add(int x,int y)
	{
		nxt[++tot]=hea[x];
		hea[x]=tot;
		to[tot]=y;
	}
}T[2];
int dep[maxn][2],jump[maxn][20],maxx;
void dfs(int now,int fa,int opt)
{
	dep[now][opt]=dep[fa][opt]+1;
	if(opt==1)jump[now][0]=fa;
	for(int i=T[opt].hea[now];i;i=T[opt].nxt[i])
	{
		int to=T[opt].to[i];
		if(to==fa)continue;
		dfs(to,now,opt);
	}
}
int lca(int x,int y)
{
	if(dep[x][1]<dep[y][1])swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[jump[x][i]][1]>=dep[y][1])
			x=jump[x][i];
	if(x==y)return x;
	for(int i=19;i>=0;i--)
		if(jump[x][i]!=jump[y][i])
			x=jump[x][i],y=jump[y][i];
	return jump[x][0];
}
void getans(int now,int fa)
{
	if(fa)
	{
		int p=lca(now,fa);
		if(dep[now][1]+dep[fa][1]-2*dep[p][1]>2)
		{
			puts("-1");
			exit(0);
		}
	}
	if(dep[now][0]>=dep[now][1])return;
	maxx=max(maxx,dep[now][1]);
	for(int i=T[0].hea[now];i;i=T[0].nxt[i])
	{
		int y=T[0].to[i];
		if(y==fa)continue;
		getans(y,now);
	}
}
int main()
{
	int n=read(),x=read(),y=read(),s,t;
	for(int ii=0;ii<2;ii++)
		for(int i=1;i<n;i++)
		{
			s=read(),t=read();
			T[ii].add(s,t);
			T[ii].add(t,s);
		}
	dfs(x,0,0),dfs(y,0,1);
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			jump[j][i]=jump[jump[j][i-1]][i-1];
	getans(x,0);
	printf("%d\n",2*maxx-2);
	return 0;
}

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

int main() {
  int n;
  scanf("%d", &n);
  int t = 0, x = 0, y = 0;
  bool succ = true;
  for (int i = 0; i < n; ++i) {
    int tt, xx, yy;
    scanf("%d %d %d", &tt, &xx, &yy);
    int r = tt - t, d = abs(x - xx) + abs(y - yy);
    if (r < d || (r - d) & 1) succ = false;
    t = tt, x = xx, y = yy;
  }
  if (succ)
    printf("Yes\n");
  else
    printf("No\n");

  return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
x=list(map(int,input().split()))
a=[[]for _ in range(m)]
for i in x:a[i%m].append(i)
b=[]
from collections import Counter
for i in range(m):
  d=Counter(a[i])
  ans=0
  for j in d:ans+=2*(d[j]//2)
  b.append([len(a[i]),ans])
ans=0
if m%2==0:ans+=len(a[m//2])//2
ans+=len(a[0])//2
for i in range(1,0--m//2):
  sc,sp=b[i]
  tc,tp=b[m-i]
  v=min(sc,tc)
  ans+=v
  ans+=min(sp,sc-v)//2
  ans+=min(tp,tc-v)//2
print(ans)

Measured memory_bytes: 76652
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());
        var back = 1000 - N % 1000;

        if (back == 1000) Console.WriteLine(0);
        else Console.WriteLine(back);
    }
}


Measured memory_bytes: 27536
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int cnt[20][20];
ll ans=0;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	
	long double t;
	ll val;
	rep(x,0,n){
		cin>>t;
		t*=1e9;
		val=floor(t+0.3);
		
		//cout<<val<<endl;
		
		int two=0,five=0;
		
		while (val%2==0){
			val/=2;
			two++;
		}
		while (val%5==0){
			val/=5;
			five++;
		}
		
		//cout<<two<<" "<<five<<endl;
		
		two=min(18,two),five=min(18,five);
		
		rep(x,18-two,20){
			rep(y,18-five,20){
				ans+=cnt[x][y];
			}
		}
		
		cnt[two][five]++;
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    string s;
    cin>>s;
    int l=s.size();
    ll num=0,sum=0,ans=0;
    for(int i=0; i<(1<<(l-1)); i++)
    {
        num=0;
        sum=0;
        for(int j=0; j<l; j++)
        {
            num=num*10+(s[j]-'0');
            if(i&(1<<j))
            {
                sum+=num;
                num=0;
            }
        }
        sum+=num;
        ans+=sum;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define mod ((ull)1e9+7)
#define MAX ((ull)1e6)

vector<ll> v(2*(ll)(1e5+1),0);
vector<ll> v_inv(2*(ll)(1e5+1),0);

ll pmod(ll n, ll p){
	ll m=n%mod;
	if(p==1) return m;
	ll ans=pmod((m*m)%mod, p/2)%mod;
	if(p%2==1) ans=ans*m%mod;
	return ans;
}

void factorial(ll n){
	v[0]=1;
	for(ll i=1; i<=n; i++){
		v[i]=v[i-1]*i%mod;
	}
	return;
}

void factorial_inv(ll n){
	for(ll i=0; i<=n; i++){
		v_inv[i]=pmod(v[i],mod-2);
	}
}

ll binom(ll n, ll k){
	ll tmp=v_inv[k]*v_inv[n-k]%mod;
	return v[n]*tmp%mod;
}

int main(){
	ll h, w, a, b;
	cin >> h >> w >> a >> b;
	factorial(h+w);
	factorial_inv(h+w);
	ll ans=0;
	for(ll j=b+1; j<=w; j++){
		ans+=binom(h-a+j-2, h-a-1)*binom(a+w-j-1, a-1)%mod;
	}
	cout << ans%mod << endl;
	return 0;
}

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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;

typedef long long int ll;

int main() {

	IOS

	ll a;
	cin >> a;

	string b;
	cin >> b;

	int i;
	for (i = 0; i < b.size(); i++)
		if (b[i] == '.')
			break;
	int b_i = stoi(b.substr(0, i));
	int b_f = stoi(b.substr(i+1));

	ll res = (a * b_i) + ((a * b_f) / 100);
	
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 3644
/*
    @uthor: Amit Kumar
    user -->GitHub: drviruses ; CodeChef: dr_virus_ ; Codeforces,AtCoder,Hackerearth,Hakerrank: dr_virus;
*/
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
/* #include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
#define ln mp::cpp_int */
#define ll    long long
#define ld    long double
#define ull   unsigned long long
#define endl "\n"
ll google_itr = 1;
#define google(x) cout<<"\Case #"<<x<<"\:"
#define pi 3.14159265358979323846264338327950L

const ll mod = 1e9+7;
const ll inf = 1e18;

ll popcount(ll num){
    num = num - ((num >> 1) & 0x55555555);
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    return ((num + (num >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}


void virus(){
   ld a,b;
  cin>>a>>b;
  ll c= a*b;
  cout<<c;
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
  /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/

    ll t=1;
   // cin>>t;
    while(t--){
           auto start = high_resolution_clock::now();
           virus();
           auto stop = high_resolution_clock::now();
           auto duration = duration_cast<seconds>(stop - start);
         //cout << "Time: "<<duration.count()<<endl;
        //your code goes here
    }
    return 0;
}

Measured memory_bytes: 3772
use proconio::input;

fn main() {
    input! {
        n: usize,
        s: [String; n],
    };
    let t: Vec<&str> = vec!["AC", "WA", "TLE", "RE"];
    let mut c = vec![0; 4];
    for s_i in s.iter() {
        match t.iter().position(|t_i| t_i == s_i) {
            Some(i) => c[i] += 1,
            None => unreachable!(),
        }
    }
    for (t_i, c_i) in t.iter().zip(c.iter()) {
        println!("{} x {}", t_i, c_i);
    }
}


Measured memory_bytes: 7812
#include <stdio.h>

int main(void){
int n,p;
p=0;
scanf("%d",&n);

if(n>=195){
p=5;
}else if(n>=189){
p=4;
}else if(n>=165){
p=3;
}else if(n>=135){
p=2;
}else if(n>=105){
p=1;
}
printf("%d\n",p);
return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int n, x;
int main() {
    while(1) {
        cin >> n >> x;
        if(n == 0 && x == 0) break;
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = i+1; j < n; ++j) {
                int check = x - (i+j);
                if(check >= j+1 && check <= n) cnt++;
            }
        }
        cout << cnt << endl;
    }
}


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

const int MAXN = 1e5 + 10;

struct dsu {
  vector<int> Rank, P;
  int V;
  dsu(int v = 0) : V(v) {
    Rank = vector<int>(v + 1, 0);
    P = vector<int>(v + 1, 0);
    for(int i = 0; i < P.size(); i++) {
      P[i] = i, Rank[i] = 1;
    }
  }
  int find_root(int x) { return x == P[x] ? x : P[x] = find_root(P[x]); }
  void merge(int x, int y) {
    int xr = find_root(P[x]), yr = find_root(P[y]);
    if(xr == yr) return ;
    if(Rank[xr] < Rank[yr]) swap(xr, yr), swap(x, y);
    Rank[xr] += Rank[yr];
    P[yr] = xr;
  }
};

vector<int> adj[MAXN];
bool vis[MAXN];
bool color[MAXN];
bool is_bp[MAXN];
int n, m;
bool dfs(int r) {
  vis[r] = true;
  bool ok = true;
  for(auto &elem: adj[r]) {
    if(vis[elem] == false) {
      color[elem] = color[r] ^ true;
      ok &= dfs(elem);
    } else if(vis[elem] and color[elem] == color[r]) {
      ok = false;
    }
  }
  return ok;
}

int main() {
  ios_base::sync_with_stdio(false);
  int a, b;
  cin >> n >> m;
  dsu tester(n + 1);
  for(int i = 0; i < m; i++) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    tester.merge(a, b);
  }
  int bp = 0, nbp = 0;
  LL res = n * (LL)n;
  LL sum = 0;
  for(int i = 1; i <= n; i++) {
    if(tester.find_root(i) == i && tester.Rank[i] > 1) {
      sum += tester.Rank[i];
      if(dfs(i)) {
        is_bp[i] = true;
        bp++;
      } else {
        nbp++;
      }
    }
  }
  for(int i = 1; i <= n; i++) {
    if(tester.find_root(i) == i and tester.Rank[i] > 1) {
      res -= tester.Rank[i] * sum;
      if(is_bp[i]) {
        res += 2 * bp;
        res += nbp;
      } else {
        res += nbp + bp;
      }
    }
  }
  cout << res << endl;
  return 0;
}


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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);


  ll k,x;cin>>k>>x;
  if(500*k>=x){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;

  }
  
  return 0;
}


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

int main(int argc, char **argv)
{
	string str; cin >> str;
	ll N = str.size();

	bool ok{true};
	
	string rev = str;
	reverse(rev.begin(), rev.end());
	if (rev != str)
		ok = false;

	string tmp = str.substr(0, (N-1)/2);
	rev = tmp;
	reverse(rev.begin(), rev.end());
	if (rev != tmp)
		ok = false;

	tmp = str.substr((N+3)/2-1);
	rev = tmp;
	reverse(rev.begin(), rev.end());
	if (rev != tmp)
		ok = false;

	std::cout << (ok ? "Yes" : "No")<< std::endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
int Gcd(int arr[], int n) 
{ 
    int result = arr[0]; 
    for (int i = 1; i < n; i++) 
    { 
        result = gcd(arr[i], result); 
  
        if(result == 1) 
        { 
           return 1; 
        } 
    } 
    return result; 
} 
  
 
int main()
{
    
        int n;
        ll sum = 0;
        cin>>n;
        int gcd;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1;j <= n ; j++)
            {
                for(int k = 1; k <= n; k++)
                {
                    int a[3] = {i,j,k}; 
                    
                    
                    sum += Gcd(a,3);
                }
            }
            
        }
        cout<<sum<<endl;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int A,B,Q;
vector<ll> S,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>Q;
	S.resize(A);
	T.resize(B);
	FOR(i,A) cin>>S[i];
	FOR(i,B) cin>>T[i];
	
	while(Q--) {
		ll v;
		cin>>v;
		ll mi=1LL<<60;
		
		
		x=lower_bound(ALL(S),v)-S.begin();
		if(x!=S.size()) {
			y=lower_bound(ALL(T),S[x])-T.begin();
			if(y!=T.size()) mi=min(mi,abs(v-S[x])+abs(S[x]-T[y]));
			if(y!=0) mi=min(mi,abs(v-S[x])+abs(S[x]-T[y-1]));
		}
		x--;
		if(x>=0) {
			y=lower_bound(ALL(T),S[x])-T.begin();
			if(y!=T.size()) mi=min(mi,abs(v-S[x])+abs(S[x]-T[y]));
			if(y!=0) mi=min(mi,abs(v-S[x])+abs(S[x]-T[y-1]));
		}
		
		x=lower_bound(ALL(T),v)-T.begin();
		if(x!=T.size()) {
			y=lower_bound(ALL(S),T[x])-S.begin();
			if(y!=S.size()) mi=min(mi,abs(v-T[x])+abs(T[x]-S[y]));
			if(y!=0) mi=min(mi,abs(v-T[x])+abs(T[x]-S[y-1]));
		}
		x--;
		if(x>=0) {
			y=lower_bound(ALL(S),T[x])-S.begin();
			if(y!=S.size()) mi=min(mi,abs(v-T[x])+abs(T[x]-S[y]));
			if(y!=0) mi=min(mi,abs(v-T[x])+abs(T[x]-S[y-1]));
		}
		cout<<mi<<endl;
		
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main(){
    long int s;
    long int keep;
    int n=1;
    int jud=0;
    long long int cou=1000;
    int ans=753;

    cin>>s;
    keep=s;
    while(s/10!=0){
        s/=10;
        n++;
    }

    for (int i=0;i<n-2;i++){
        if(i==n-3)s=keep/(cou/1000);
        else s=keep%cou/(cou/1000);
        cou*=10;
        jud=753-s;
        if(jud<0) jud=-jud;
        if(ans>jud) ans=jud;
    }

    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    char a;
    int b;
    cin>>a;
    b=a;
    if(b==97||b==101||b==105||b==111||b==117)
    {
        cout<<"vowel"<<endl;
    }
    else cout<<"consonant"<<endl;
    return 0;
} 

Measured memory_bytes: 256
//package atcoder;
 
import java.util.*;
 
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		String input = sc.next();
		//char in[] = new char[N];
	    char in[] = input.toCharArray();
	    
	    for(int i=0;i<N;i++) {
	   // System.out.println(in[i]);
	    }
	    int count = 0;
	    int countB = 0;
	    int countbatu = 0;
	    
	    for(int j=0;j<N;j++) {
	    	if(in[j] == 'c') {
	    		System.out.println("No");
	    	}
	    	if(in[j] == 'a') {
	    		count ++;
	    		if(countB>B) {
	    			if(count<A+B+1+(countB-B)) {
	    				System.out.println("Yes");
	    			}else {
	    				System.out.println("No");
	    			}
	    		}
	    		if(countB<=B) {
	    			if(count<A+B+1) {
	    				System.out.println("Yes");
	    			}else {
	    				System.out.println("No");
	    			}
	    		}
	    	}
	    	if(in[j] == 'b') {
	    		count ++;
	    		countB ++;
	    		if(count<A+B+1&&countB<B+1) {
	    			System.out.println("Yes");
	    		}else {
	    			System.out.println("No");
	    		}
	    	}
	    
	    }
	}
	    
}




Measured memory_bytes: 36648
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<list>
#include<set>
#include<bitset>
#include<stack>
#include<cctype>
#define sc(x) scanf("%d",&x);
#define pr(x) cout<<#x<<": "<<x<<" ";
#define prln(x) cout<<#x<<": "<<x<<endl;
#define bug() cout<<"bug: "<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps = 1e-4;
const int mod = 1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3+7;
const int maxm = 1e6+7;
const double pi = acos(-1.0);

int main(){
	int n; cin>>n;
	if(n%10==n/100)
		puts("Yes");
	else
		puts("No");
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//---------------------------------------------------------------------------

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

    ll a,b,m;
    cin>>a>>b>>m;
    
    ll ans=INF;
    vector<ll>aa(a),bb(b);
    for(ll i=0;i<a;i++)cin>>aa[i];
    for(ll i=0;i<b;i++)cin>>bb[i];
    for(ll i=0;i<m;i++){
        ll x,y,c;cin>>x>>y>>c;
        x--;y--;
        ll tmp=aa[x]+bb[y]-c;
        chmin(ans,tmp);
    }
    sort(all(aa));sort(all(bb));
    chmin(ans,aa[0]+bb[0]);
    cout<<ans<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


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

#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

using namespace std;

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

    string S;
    int Q;
    cin >> S >> Q;
    bool reversed = false;
    vector<char> rhead, tail;
    REP(_, Q) {
        int T;
        cin >> T;
        if (T == 1) {
            reversed = !reversed;
        } else { // if T == 2
            int F;
            char C;
            cin >> F >> C;
            if (reversed ^ (F == 1)) { // if (reversed and F == 2) or (not reversed and F == 1)
                rhead.push_back(C);
            } else {
                tail.push_back(C);
            }
        }
    }

    string result;
    if (reversed) {
        result = string(rall(tail)) + string(rall(S)) + string(all(rhead));
    } else {
        result = string(rall(rhead)) + S + string(all(tail));
    }
    cout << result << endl;

    return 0;
}


Measured memory_bytes: 1428
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int N; cin >> N;
	ll ans = 0;
	vector<vector<ll>> a(N, vector<ll>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a[i][j];
			ans += a[i][j];
		}
	}

	vector<vector<bool>> vi(N, vector<bool>(N));
	bool fl = true;
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (k != i && k != j && a[i][j] == a[i][k] + a[k][j] && !vi[i][j])
					ans -= a[i][j], vi[i][j] = true;
				else if (a[i][j] > a[i][k] + a[k][j]) {
					fl = false;
					break;
				}
			}
		}
	}

	if (fl) cout << ans/2 << endl;
	else cout << -1 << endl;
}


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


int main(){
    int n;cin >> n;
    vector<int> a(n);
    bool flag1 = false;
    rep(i,n) {
        char ch;
        cin >> ch;
        a[i] = ch - '1';
        if(a[i]==1) flag1 = true;
    }
    int oddeven = 0;
    int oddeven2 = 0;
    vector<int> bifact(n+1);
    for(int i = 1;i <= n;i++){
        bifact[i] = bifact[i-1];
        int x = i;
        while(x%2==0){
            if(x%2 == 0){
                bifact[i]++;
                x /= 2;
            }
        }
    }

    rep(i,n){
        if(bifact[n-1]-bifact[n-1-i]-bifact[i] > 0) continue;
        oddeven ^= a[i];
        oddeven2 ^= a[i]/2;
    }




    if(oddeven%2) cout << 1 << endl;
    else if(flag1) cout << 0 << endl;
    else cout << 2*(oddeven2%2) << endl;

    
    
}

Measured memory_bytes: 11164
#include <stdio.h>
#define N 10000

int arrayA[2000001],arrayC[N+1],arrayB[2000001];
int main()
{

  int k,i,j,max=0;
  //int arrayA[2000001],arrayC[N+1],arrayB[2000001];

  scanf("%d",&k);
  for(i = 0 ; i < k ; i++)
    {
      scanf("%d",&arrayA[i]);
      if(max<arrayA[i])max = arrayA[i];
    }




  for(i = 0 ; i <= max ; i++) arrayC[i] = 0;


  for(j = 0 ; j < k ; j++) arrayC[arrayA[j]]++;



  for(i = 1 ; i <= max ; i++)arrayC[i] = arrayC[i] + arrayC[i-1];



  for(j = k-1 ; j >= 0 ; j--)
    {
      arrayB[arrayC[arrayA[j]]]= arrayA[j];
      arrayC[arrayA[j]]--;

    }






  for(i = 1 ; i < k ; i++)
    {
      printf("%d ",arrayB[i]);
    }
  printf("%d",arrayB[k]);
  printf("\n");

  return 0;
}


Measured memory_bytes: 17360
import java.io.*;
import java.util.StringTokenizer;

public class Main {
  private static PrintWriter out;

  public static void main(String[] args) {
    Main main = new Main();
    Runtime.getRuntime().addShutdownHook(new Thread(() -> out.close()));
    try {
      main.run(args);
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  private void run(String[] arguments) throws Exception {
    MyScanner sc = new MyScanner();
    out = new PrintWriter(new BufferedOutputStream(System.out));

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

    boolean[][] checkNote = new boolean[n][k];

    for (int i = 0; i < k; i++) {
      int d = sc.nextInt();
      for (int j = 0; j < d; j++) {
        int a = sc.nextInt()-1;
        checkNote[a][i] = true;
      }
    }

    int counter = 0;
    for (int i = 0; i < checkNote.length; i++) {
      boolean isTrueContain = false;
      for (int j = 0; j < checkNote[i].length; j++) {
        if (checkNote[i][j]){
          isTrueContain = true;
          break;
        }
      }
      if (!isTrueContain) counter++;
    }

    out.println(counter);
    out.close();
  }

  /*          
   * Form: http://codeforces.com/blog/entry/7018
   */
  private class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    MyScanner() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

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

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

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }
}


Measured memory_bytes: 34880
def abc057_b():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    cd = [list(map(int, input().split())) for _ in range(m)]

    for i in range(n):
        tmp_index = 0
        d = 10 ** 9
        for j in range(m):
            tmp_d = abs(ab[i][0] - cd[j][0]) + abs(ab[i][1] - cd[j][1])
            if tmp_d < d:
                tmp_index = j
                d = tmp_d
        print(tmp_index + 1)


abc057_b()

Measured memory_bytes: 3064
import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))

for i in range(N):
    A[i]=-1*A[i]

heapq.heapify(A)

for i in range(M):
    temp=heapq.heappop(A)
    heapq.heappush(A,(temp+1)//2)

print(-1*sum(A))


Measured memory_bytes: 14180
// https://atcoder.jp/contests/abc158/tasks/abc158_a
function main(s) {
    var ans;
    for (var ch = s[0], i = 1; i < 3; i++) {
         if (ch !== s[i]) {
               ans = 1;
               break;
         }
    }
    console.log(ans? "Yes": "No");
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main(){
	int n,m;
	cin>>n>>m;
	//m gates
	int ansL = 1,ansR = n;
	for(int i = 0;i < m;i++){
		int l,r;
		cin>>l>>r;
		ansL = max(ansL, l);
		ansR = min(ansR, r);
	}
	if(ansL <= ansR){
		cout<<ansR-ansL+1<<endl;
	}
	else cout<<0<<endl;
	return 0;
}

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

using namespace std;
#define int long long

int32_t main()
{
    int n, A , B; cin >> n >> A >> B;
    if (A % 2 == B % 2) return cout << ((B - A)>>1) << "\n", 0;
    int x1 = A + n - B;
    x1++;
    int ans = ((n - x1)>>1) + n - B + 1;
    int x2 = B - (A - 1);
    x2--;
    ans = min(ans, ((x2 - 1)>>1) + A);
    cout << ans << "\n";
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    string s[n];
    rep(i, 0, n)
    {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
    }

    map<char, int> char_cnt;
    rep(i, 0, n)
    {
        map<char, int> now_char_cnt;
        int j = 0;
        while (j < s[i].size())
        {
            char now = s[i][j];
            int cnt = 0;
            for (;j < s[i].size() and s[i][j] == now; j++)
                cnt++;
            now_char_cnt[now] = cnt;
        }

        // merge
        if (i == 0)
            char_cnt = now_char_cnt;
        else
        {
            for (auto c_cn: char_cnt)
                char_cnt[c_cn.first] = min(c_cn.second, now_char_cnt[c_cn.first]);
        }
    }

    vector<char> ans;
    for (auto c_cn: char_cnt)
    {
        char c = c_cn.first;
        int cnt = c_cn.second;
        rep(i, 0, cnt)
            ans.push_back(c);
    }
    sort(ans.begin(), ans.end());
    rep(i, 0, ans.size())
        cout << ans[i];
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
//今調べているマスが'#'であり,かつ左下に#が存在したらImpossible (f = true)
#include <bits/stdc++.h>
using namespace std;
int main() {
  bool f = false;
  int H, W;
  cin >> H >> W;
  char a[10][10];
  for (int i = 0; i < H; i++)  {
    for (int j = 0; j < W; j++)  {
        cin >> a[i][j];
    }
  }
  //全部のマスを調べていく
  for (int i = 0; i < H; i++)  {
    for (int j = 0; j < W; j++)  {
      if (0 <= i < H && 0 <= j < W) {
        if (a[i][j] == '#' && a[i+1][j-1] == '#') f = true;
  //調べた所は全て'.'と置く           
          a[i][j] = '.';
             }
    }
    }
if(f) cout << "Impossible" << endl;
else cout << "Possible" << endl;
}

Measured memory_bytes: 256
(defun sqrtp (x)
  (equal 0.0 (rem (sqrt x) 1)))
(defun joint (x y)
  (if (eq y 100)
      (+ (* x 1000) 100)
      (if (> y 9)
          (+ (* x 100) y)
          (+ (* x 10) y))))
(defun yn (x)
  (if x "Yes" "No"))
 
(format t (yn (sqrtp (joint (read) (read)))))

Measured memory_bytes: 4960
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

typedef long long ll;
using namespace std;

int main() {
  ll A;
  double B;
  cin >> A >> B;
  ll ans = A * (ll)(B * 100 + 0.9999);
  cout << ans / 100 << endl;
  return 0;
}

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

int main(){
  string s,t;
  int num=0;
  cin >> s >> t;
  for(int i=0;i<s.size();i++){
    if(s[i]!=t[i]){
      num+=1;
    }
  }
  cout << num; 
}

Measured memory_bytes: 3516
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << 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...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  string s, t;
  cin >> s >> t;
  int n = s.size();
  bool found = false;
  for (int k = 0; k < n; ++k) {
    string cur;
    for (int i = 0; i < n; ++i) {
      cur += s[(i + k) % n];
    }
    if (cur == t) found = true;
  }
  cout << (found ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int n;
    scanf("%d",&n);
    int a[200000],i;
    long long b[200000]={0},x;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        a[i]=a[i]-1;
        b[a[i]]++;
    }
    for (i=0;i<n;i++)
    {
        x=x+b[i]*(b[i]-1)/2;
    }
    long long s;
    for (i=0;i<n;i++)
    {
        s=x;
        s=s-(b[a[i]]*(b[a[i]]-1)/2);
        s=s+(b[a[i]]-1)*(b[a[i]]-2)/2;
        printf("%lld\n",s);
    }
    return 0;
}


Measured memory_bytes: 4864