akhauriyash/Code-Regression huggingface dataset:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.link[x] == x:
            return x

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

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

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

N, M = map(int, input().split())
u = UnionFind(N)

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    u.unite(a, b)

d = defaultdict(int)
for i in range(N):
    x = u.find(i)
    d[x] += 1
print(max(d.values()))

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

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long long llong;
typedef long double ld;

using namespace std;

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
        cerr << (*i) << " ";
    }
    cerr << "\n";
}
const ll MAXN = 120000;
int n, m;
ll ad[MAXN];
ll go[MAXN];
int a[MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d", a + i), --a[i];
    int now = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] == now)
            continue;
        if (a[i] > now) {
            int g = a[i] - now;
            go[m - 1] += g;
            go[a[i]] -= g;
            ad[a[i]] += 1;
            ad[now] -= 1;
        }
        else {
            int g = m - (now - a[i]);
            go[a[i]] -= g;
            ad[a[i]] += 1;
            go[m - 1] += a[i] + 1;
            ad[m - 1] += 1;
            ad[now] -= 1;
        }
        now = a[i];
    }
    ll ans = 1e12;
    ll nnow = 0;
    ll d = 0;
    for (int i = m - 1; i >= 0; --i) {
        d += ad[i];
        nnow += go[i];
        nnow += d;
        ans = min(ans, nnow);
    }
    cout << ans << "\n";
    return 0;
}




Measured memory_bytes: 2176
N=int(input())
H=[int(i) for i in input().split()]
dp=[0]*(N+5)
dp[0]=0
dp[1]=abs(H[1]-H[0])
for i in range(2,N):
  dp[i]=min(dp[i-2]+abs(H[i-2]-H[i]),dp[i-1]+abs(H[i-1]-H[i]))
print(dp[N-1])

Measured memory_bytes: 13928
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9 + 7; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	vector<int> H;
	
	cin>>N;
	
	H.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>H[i];
	}
	
	reverse(H.begin(), H.end());
	
	for(int i = 1; i < N; i++){
		if(H[i-1] < H[i]) H[i]--;
		
		if(H[i-1] < H[i]){
			cout<<"No"<<endl;
			return 0;
		}
	}
	
	cout<<"Yes"<<endl;
	return 0;
}

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

int main() {
  long long X,K,D,tmp=0;
  cin>>X>>K>>D;
  X=abs(X);
  D=abs(D);
  tmp=X/D;
  if(K<=tmp){X=X-D*K;K=0;}
  else{X=X-D*tmp;K=K-tmp;}
  if(K%2==0){cout<<X<<endl;}else{cout<<abs(X-D)<<endl;}
}

Measured memory_bytes: 3604
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

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

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

int main(void) {
    string S;
    cin >> S;

    for (int i = 1; i < (int) S.size(); i++) {
        if (S[i - 1] == S[i]) {
            cout << "Bad" << endl;
            return 0;
        }
    }

    cout << "Good" << endl;

    return 0;
}


Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
//#pragma GCC target("popcnt")
//#pragma GCC target("sse4")
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(),a.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i > -1; i--)
#define rer(i, x, n) for (int i = x; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef long double ld;















signed main(){
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ro = 0;
    for (int i = 0; i < n - 1; i++){
        ro = max(ro, a[i + 1] - a[i]);
    }
    ro = max(ro, a[0] + k - a[n - 1]);
    cout << k - ro;




}


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

ll a, b, x;

ll f(ll n){
    if(n == -1) return 0;
    return n / x + 1;
}

int main(void){
    
    cin >> a >> b >> x;
    ll ans = f(b) - f(a - 1);
    cout << ans << endl; 
    
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
h=list(map(int,input().split()))
p=[i for i in range(1,n+1)]
q=[]
for i in range(m):
  a=list(map(int,input().split()))
  if h[a[0]-1]<=h[a[1]-1]:
    q.append(a[0])
  if h[a[0]-1]>=h[a[1]-1]:
    q.append(a[1])
p=set(p)
q=set(q)
print(len(p-q))

Measured memory_bytes: 29500
from collections import defaultdict
S = input()
T = input()
D = defaultdict(set)

for s, t in zip(S, T):
    D[s].add(t)

used = set()
for x in D.values():
    if len(x) > 1:
        print("No")
        break

    if list(x)[0] in used:
        print("No")
        break

    used.add(list(x)[0])

else:
    print("Yes")


Measured memory_bytes: 4136
import sys

a, b = map(int, sys.stdin.readline().split())

def main():
    flag = False
    if not a % 3: flag = True
    elif not b % 3: flag = True
    elif not (a + b) % 3: flag = True
    ans = 'Possible' if flag else 'Impossible'
    print(ans)

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 3060
fun main() {
    fun gcd(a: Int, b: Int): Int {
        return if (b == 0) a else gcd(b, a % b)
    }

    fun gcd(a: Int, b: Int, c: Int): Int {
        return gcd(gcd(a, b), c)
    }

    val k = readLine()!!.toInt()
    var ans = 0L
    for (a in 1..k) {
        for (b in 1..k) {
            for (c in 1..k) {
                ans += gcd(a, b, c)
            }
        }
    }
    println(ans)
}


Measured memory_bytes: 34596
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    s = ns()
    t = ns()
    ans = 0
    for i in range(len(s)):
        if s[i] != t[i]:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Measured memory_bytes: 67860
def solve():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        inp = [s for s in input()]
        if inp != ['.']*W:
            A.append(inp)
    Ans = list(zip(*A))
    P = ['.' for _ in range(len(A))]
    while tuple(P) in Ans:
        Ans.remove(tuple(P))
    Ans = list(zip(*Ans))
    for i in range(len(Ans)):
        Ans[i] = ''.join(Ans[i])
    return Ans
print(*solve(),sep='\n')

Measured memory_bytes: 3200
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<iostream>
#include<map>
#define ll long long
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
inline int gi(){
	int sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
int main(){
	int i,j,k,n,m;
	int a=gi(),b=gi();
	printf("%d\n",a+b/2);
	return 0;
}


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

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;

int n, a[N],cnt[16], dp[(1 << 16) + 10], XOR[(1 << 16) + 10];

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int mask = 0; mask < (1 << 16); mask++){
		for (int i = 0; i < 16; i++){
			if (mask & (1 << i)) XOR[mask] ^= i;
		}	
	}
	for (int i = 0; i < n - 1; i++){
		int v, u, x;
		cin >> v >> u >> x;
		a[v] ^= x, a[u] ^= x;
	}
	for (int i = 1; i <= n; i++) cnt[a[i]]++;
	int ans = 0;
	int M = 0;
	for (int i = 1; i <= 15; i++){
		ans += cnt[i] / 2;
		if (cnt[i] % 2 == 1) M ^= (1 << i);
	}
	dp[0] = 0;
	for (int mask = 1; mask < (1 << 16); mask++){
		for (int mask2 = mask; mask2 > 0; mask2 = (mask2 - 1) & mask){
			if (XOR[mask2] == 0) dp[mask] = max(dp[mask], dp[mask2 ^ mask] + 1);
		}
	}
	cout << ans + (__builtin_popcount(M)) - dp[M];
	return 0;
}


Measured memory_bytes: 4572
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int N;
	ll A, B, X[100010];
	cin >> N >> A >> B;
	for (int i = 0; i < N; i++) cin >> X[i];
	ll ans = 0;
	for (int i = 0; i < N - 1; i++) {
		ans += min((X[i + 1] - X[i]) * A, B);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
n = int(input())
length = 1000018
sosu = 500009
ht = [-1] * length


def convert(moji):
    l_moji = len(moji)
    num = 0
    for j in range(l_moji):
        keta = 10 ** (l_moji - j - 1)
        if moji[j] == 'A':
            num += keta * 1
        if moji[j] == 'C':
            num += keta * 2
        if moji[j] == 'G':
            num += keta * 3
        if moji[j] == 'T':
            num += keta * 4
    return num


def hash_in(nk, num, m):
    if m == 0:
        return False
    hash_num = nk + (num % m)
    if hash_num > length:
        hash_num -= length
    if ht[hash_num] == -1:
        ht[hash_num] = num
    elif ht[hash_num] != num:
        hash_in(hash_num, num, m-1)
    return


def find(nk, num, m):
    if m == 0:
        return 'no'
    hash_num = nk + (num % m)
    if hash_num > length:
        hash_num -= length
    if ht[hash_num] == -1:
        return 'no'
    elif ht[hash_num] != num:
        return find(hash_num, num, m-1)
    elif ht[hash_num] == num:
        return 'yes'


def main():
    output = list()
    for i in range(n):
        command = list(input().split())
        num = convert(command[1])
        if command[0] == 'insert':
            if hash_in(0, num, sosu) is not None:
                print('an error is occured')
                break
        if command[0] == 'find':
            output.append(find(0, num, sosu))

    for j in output:
        print(j)


if __name__ == '__main__':
    main()



Measured memory_bytes: 27016
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
static const long long INF = 1000000;
using p = pair<int,int>;
struct trio{
    int first;
    int second;
    int third;
};
int main(){
    int n;
    cin >> n;
    vector<int> norm(n);
    rep(i,n){
        norm[i] = i + 1;
    }
    vector<int> x(n);
    vector<int> y(n);
    rep(i,n){
        cin >> x[i];
    }
    rep(i,n){
        cin >> y[i];
    }
    int k = 0;
    int ansx = 0;
    int ansy = 0;
    while(next_permutation(norm.begin(),norm.end())){
        k++;
        if (norm == x){
            ansx = k;
        }
        if (norm == y){
            ansy = k;
        }
    }
    int ans = abs(ansx - ansy);
    cout << ans << endl;
    
}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int k=gi();
	    int x=gi();

	    //System.out.print(b+a);

        if (k*500>=x) {
        	System.out.print("Yes");
        }else {
        	System.out.print("No");
        }


	}
	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35504
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int[] v1 = {0,1,0,-1};
	static int[] v2 = {1,0,-1,0};
	static int count;
	static int[][] dis;
	static int min;
	static boolean[] already;
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(true){
			int w=cin.nextInt();
			int h=cin.nextInt();
			if(w+h==0){
				break;
			}
			min=999999999;
			int[][] a = new int[h+2][w+2];
			int[][] bangou = new int[h+2][w+2];
			int[][] coor = new int[11][2];
			count=1;
			for(int i = 0;i<h;i++){
				String str=cin.next();
				for(int j = 0;j<w;j++){
					if(str.charAt(j)=='.'){
						a[i+1][j+1]=1;
					}
					else if(str.charAt(j)=='o'){
						a[i+1][j+1]=3;
						coor[0][0]=i+1;
						coor[0][1]=j+1;
					}
					else if(str.charAt(j)=='x'){
						a[i+1][j+1]=0;
					}
					else if(str.charAt(j)=='*'){
						a[i+1][j+1]=2;
						coor[count][0]=i+1;
						coor[count][1]=j+1;
						bangou[i+1][j+1]=count;
						count++;
					}
				}
			}
			dis = new int[count][count];
			already = new boolean[count];
			for(int i = 0;i<count;i++){
				int[][] copy = new int[h+2][w+2];
				for(int x = 0;x<h+2;x++){
					for(int y = 0;y<w+2;y++){
						copy[x][y]=a[x][y];
					}
				}
				int x = coor[i][0];
				int y = coor[i][1];
				copy[x][y]=0;
				Integer[] pair ={x,y,0};
				Queue<Integer[]> q = new LinkedList<Integer[]>();
				q.add(pair);
				while(!q.isEmpty()){
					Integer[] p = q.poll();

					for(int c = 0;c<4;c++){
						int xx=p[0]+v1[c];
						int yy=p[1]+v2[c];
						int distance=p[2];
						if(copy[xx][yy]==1){
							Integer[] next={xx,yy,distance+1};
							copy[xx][yy]=0;
							q.add(next);
						}
						else if(copy[xx][yy]==2){
							dis[i][bangou[xx][yy]]=distance+1;
							Integer[] next={xx,yy,distance+1};
							copy[xx][yy]=0;
							q.add(next);
						}
						else if(copy[xx][yy]==3){
							dis[i][0]=distance+1;
							Integer[] next={xx,yy,distance+1};
							copy[xx][yy]=0;
							q.add(next);
						}
					}
				}
			}
			for(int i = 0;i<count;i++){
				for(int j=0;j<count;j++){
					//System.out.print(dis[i][j]+ " ");
				}
				//System.out.println();
			}
			already[0]=true;
			backtrack(0,0,0);
			if(min==999999999){
				System.out.println(-1);
			}
			else{
				System.out.println(min);
			}
		}
	}
	static void backtrack(int start,int sum,int cnt){
		//System.out.println(start+" " + sum+" " +cnt);
		if(sum>min){
			return;
		}
		if(cnt==count-1){
			min=Math.min(sum, min);
		}
		for(int i = 1;i<count;i++){
			if(dis[start][i]!=0&&!already[i]){
				int tmp=dis[start][i];
				dis[start][i]=dis[i][start]=0;
				already[i]=true;
				backtrack(i,sum+tmp,cnt+1);
				already[i]=false;
				dis[start][i]=dis[i][start]=tmp;
			}
		}
	}
}

Measured memory_bytes: 12000
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define BIT(b, i) (((b) >> (i)) & 1)
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

ll pow(int x, int n){
  return n == 0 ? 1 : x * pow(x, n - 1);
}


/*
n x
a1 .. an

n 100
x 10^9
ai 10^9
 */
int n;
ll x,a[100];

int main(){
  cin>>n>>x;
  REP(i,n){
    cin>>a[i];
  }

  sort(a, a+n);

  int ans = 0;
  REP(i,n){
    if(a[i] <= x){
      if(i==n-1 && a[i]!=x) break;
      x -= a[i];
      ans++;
    } else {
      break;
    }
  }

  cout<<ans<<endl;

  return 0;
}


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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 200010;
const double eps = 1e-6;



int main()
{
    char s[5];
    scanf("%s", s);
    int a, b, c, d;
    a = s[0] - '0', b = s[1] - '0', c = s[2] - '0', d = s[3] - '0';
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
            {
                int x = a;
                if(i) x += b;
                else x -= b;
                if(j) x += c;
                else x -= c;
                if(k) x += d;
                else x -= d;

                if(x == 7)
                {
                    printf("%d%c%d%c%d%c%d=7\n", a, i ? '+' : '-', b, j ? '+' : '-', c, k ? '+' : '-', d);
                    return 0;
                }
            }
    return 0;
}


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

const int MAX = 1000000;
bool A[MAX];

int main() {
    int x;
    cin >> x;
    for (int i = 0; i < MAX; ++i) A[i] = true;
    for (int i = 2; i < MAX; ++i) {
        if (!A[i]) continue;
        if (i >= x) {
            cout << i << endl;
            break;
        }
        int a = i * 2;
        while (a < MAX) {
            A[a] = false;
            a += i;
        }
    }
    return 0;
}

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

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;
typedef vector<string> VS;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(a * n, b) << ln;
    return 0;
}


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

typedef long long ll;
typedef pair<int, int> P;

const int INF = 1000000007;

int main(void){
	ll A,B;
	cin>>A>>B;
	int k;
	cin>>k;

	
	for(int i=0;i<k;i++){
		if(i % 2 == 0){
			if(A % 2 == 1) A--;
			B += (A/2);
			A /= 2;
		}
		else{
			if(B % 2 == 1) B--;
			A += (B/2);
			B /= 2;
		}

		//cout<<A<<" "<<B<<endl;
	}

	printf("%d %d\n", A, B);

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int s,c;
    double r;
    string a,b;
    cin>>a>>b;
    a+=b;
    stringstream foo(a);
    foo>>s;
    r=sqrt(s);
    if(r-floor(r)==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#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 {
#ifdef 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__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#define int  long long int
	#define pb push_back
	#define fe first
    #define lb lower_bound 
    #define ub upper_bound
    #define pii pair<pair<int,int>,pair<int,int> >
	#define se second
	#define endl "\n"
	#define pi pair<int, int>
	#define vi vector<int> 
	#define vvi vector<vi>
    #define bs   binary_search
	#define rep(i,a,b) for(int i=a;i<b;i++)
	#define rep1(i,a,b) for(int i=a;i<=b;i++)	
    #define all(c) (c).begin(),(c).end()
    #define sz(x)       (int)x.size() 
	#define PI 3.14159265358979323846
    
	 const int N =2e5+5;
    
     int mod= 1e9+7,INF=1e17;
     
     int dx[4]={0,0,+1,-1};
     int dy[4]={+1,-1,0,0};
 
     int h[N];
     void solve(){
         int n;
         cin>>n;
         
         vi v(n+1);
         rep(i,0,n)
           cin>>v[i+1];
       
       for(int i=n;i>0;i--){
		    int ty=(n/i)*i;
		    int ct=0;
		    for(int j=ty;j>0;j-=i){
				 if(h[j]==1)
				  ct++;
			}
			
		  if((ct%2==0 && v[i]==0) || (ct%2==1 && v[i]==1))
		     continue;
		  else
		   h[i]=1;	   
	   } 
	   
	   vi wyn;
	   
	   rep(i,1,n+1)
	     if(h[i])
	      wyn.pb(i);
	   
	   cout<<sz(wyn)<<endl;
	   
	   for(auto to:wyn)
	    cout<<to<<" ";   
          
         
               
	 }
	
      int32_t main() {
	    cool;
	    int t=1;
        //cin>>t;
	    while(t--)
	       solve();
	       
	       
	       return 0;	   
	   }


Measured memory_bytes: 4980
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>

#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n+1; i++)
#define repr(i,n) for(int i=n-1; i>=0; i--)
#define repr1(i,n) for(int i=n; i>0; i--)

typedef long long ll;

using namespace std;
int INF = 1000000000;
int amarilist[100005][10];
ll anslist[100005][13];
int bign = 1000000007;

int main(){

  string s;
  cin >> s;

  int famari = 0;


  rep(i,10) amarilist[0][i] = i;

  rep1(i,s.size()-1){
    rep(j,10){
      amarilist[i][j] = (amarilist[i-1][j] * 10) % 13;

    }
  }

  int n = s.size();


  repr(i,n){
    if (s[i] != '?'){
      int ind = s[i] - '0';
      famari += amarilist[n-1-i][ind];
      famari = famari % 13;
    }
  }

  anslist[0][famari] = 1;

  repr(i,n){
    if(s[i] != '?'){
      rep(j,13) anslist[n-i][j] = anslist[n-i-1][j];

    }
    else {

      rep(j,10){
        rep(k,13) anslist[n-i][k] += anslist[n-i-1][(k-amarilist[n-i-1][j]+13)%13];
      }
      rep(k,13)anslist[n-i][k] %= bign; 
      
    }

  }



  cout << anslist[n][5] << endl;


  return 0;

}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, m;
  cin >> n >> m;
  
  vector<int> a(m);
  int sum = 0;
  for (int i = 0; i < m; i++) {
    cin >> a.at(i);
    sum += a.at(i);
  }
  
  if (sum > n) cout << "-1\n";
  else cout << n - sum << '\n';
}

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

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

    int ans = 1;
    int unused = a;

    while (unused < b) {
        ans++;
        unused += a - 1;
    }
    if (b == 1) ans = 0;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
X = list(map(int, input().split()))


max = 10000000000000000000000000
for i in range(N - K + 1):
    # i = 0
    diff = X[i + K - 1] - X[i]
    t_1 = abs(X[i])
    t_1 += diff
    t_2 = abs(X[i + K - 1])
    t_2 += diff

    if t_1 < max:
        max = t_1
    if t_2 < max:
        max = t_2

print(max)


Measured memory_bytes: 14252
#include<cstdio>
#include<algorithm>

using namespace std;

int answer=0;
char str[100];

int main()
{
	while(scanf("%s",str)!=EOF)
	{
		int k=1;
		for(int i=80;i>=0;i--)
		{
			if('0'<=str[i]&&str[i]<='9')
			{
				answer+=k*(str[i]-'0');
				k*=10;
			}
			else k=1;
		}
		fill(str,str+100,'\0');
	}
	printf("%d\n",answer);
}

Measured memory_bytes: 968
parseline(str) = parse.(Int, split(str))
function Replacing()
    N = readline()
    A = parseline(readline())
    Q = parse(Int, readline())
    nums = zeros(Int, 10^5)
    ans = 0
    for a in A
        ans += a
        nums[a] += 1
    end
    for q in 1:Q
        B, C = parseline(readline())
        ans += (C - B) * nums[B]
        nums[C] += nums[B]
        nums[B] = 0
        println(ans)
    end
end
Replacing()

Measured memory_bytes: 206252
#!/usr/bin/env python3
import sys
import bisect


def solve(N: int, X: "List[int]"):
    S = sorted(X)
    later = S[N//2-1]
    earlier = S[N//2]
    for i in range(N):
        cur = X[i]
        index = bisect.bisect_left(S, cur)
        if index >= N//2:
            print(later)
        else:
            print(earlier)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, X)


if __name__ == '__main__':
    main()


Measured memory_bytes: 30844
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <string>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
using vl = vector<ll>;  // long longの1次元の型に vl という別名をつける
using vvl = vector<vl>; // long longの2次元の型に vvl という別名をつける
int MOD = 1000000007; //10^9 + 7

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  lINF = 1LL << 60;
const int iINF = 1 << 29;

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

  cout << 48-m << endl;
  return 0;
} 

Measured memory_bytes: 3548
#include<bits/stdc++.h>
#define int long long
#define v(T) vector<T>
#define vb vector<bool>
#define pi pair<int,int>
#define ppi pair<pair,int,int>, int>
#define vpi vector<pair<int,int>>
#define w(t) int t; cin>>t; while(t--)
#define FIO  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
void init() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
int32_t main() {
	FIO;
	init();
	int l, r, d; cin >> l >> r >> d;
	int c = 0;
	for (int i = l; i <= r; i++) {
		if (i % d == 0) c++;
	}
	cout << c << endl;
}

Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] array = new int[n-1][3];
		for(int i=0; i < n-1;i++){
			for(int j = 0; j < 3;j++){
				array[i][j] = sc.nextInt();
			}
		}
		for(int i =0; i < n-1;i++){
			int time = array[i][1];
			time += array[i][0];
			for(int j = i+1;j < n-1; j++){
				if(time < array[j][1]) time = array[j][1];
				else{
					int delay = (time - array[j][1]) % array[j][2];
					if(delay != 0) time += array[j][2] - delay;
				}
				time += array[j][0];

			}
			System.out.println(time);
		}
		System.out.println(0);
	}
}

Measured memory_bytes: 26708
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define why(n,x) int n;while(cin >>n,n!=x)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define unless(flg) if ( !(flg) )
#define read cin<<
#define echo cout<<
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define SWAP(a,b) ((a != b) && (a += b,b = a - b,a -= b))
#define cinf(n,x) for(int UNCH=0;UNCH<(n);UNCH++) cin >> x[UNCH];
#define fcin(n,x) for(int UNCH=1;UNCH<=(n);UNCH++) cin>> x[UNCH];
#define memmin(x) memset((x),-1,sizeof((x)))
#define memzer(x) memset((x), 0,sizeof((x)))
#define meminf(x) memset((x),0x3f,sizeof((x)))

typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
typedef map < string , int > mstit;
typedef vector < pii > vpi ;
typedef greater < pii > gpi;
typedef priority_queue < pii , vpi , gpi > dijk ;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
#define int long long

inline void solve(){
    int n,a,b;
    int ans = 0;
    cin >> n >> a >> b;
    if( a > b)
        ans = 0;
    else if(n==1){
        if(a == b) ans = 1;
        else ans = 0;
    }else{
        ans = (b-a)*(n-2)+1 ;
    }

    cout << ans fin;
        
}

struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;signed main(){solve();return 0;}



Measured memory_bytes: 256
#include<iostream>

int main (){
    std::cin.tie(0); 
	std::ios::sync_with_stdio(false);
    int N;std::cin >> N;
    long long D;std::cin >> D;
    int ans=0;
    long long X,Y;
    for (int i=0;i<N;++i){
        std::cin >> X >> Y;
        if (X * X + Y * Y <= D * D ) {
            ++ans;
        }
    }
    std::cout << ans;
    return 0 ;
}


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

using namespace std;

#define ll long long
#define ld long double

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

ll INF = (ll) 1e20;
int iINF = (int) 1e20;
ll mod = (ll) 1e9 + 7;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = 1;
    for(int i = 1; i < n; ++i) {
        if(s[i] != s[i - 1]) {
            ++ans;
        }
    }
    cout << ans;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

map<char, set<char> > m;

int main() {

	m['A'].insert('B');
	m['A'].insert('D');

	m['B'].insert('A');
	m['B'].insert('C');
	m['B'].insert('E');

	m['C'].insert('B');
	m['C'].insert('F');

	m['D'].insert('A');
	m['D'].insert('E');
	m['D'].insert('G');

	m['E'].insert('B');
	m['E'].insert('D');
	m['E'].insert('F');
	m['E'].insert('H');

	m['F'].insert('C');
	m['F'].insert('E');
	m['F'].insert('I');

	m['G'].insert('D');
	m['G'].insert('H');

	m['H'].insert('E');
	m['H'].insert('G');
	m['H'].insert('I');

	m['I'].insert('F');
	m['I'].insert('H');

	rep(i, 1000) {
		string s;
		cin >> s;

		bool flag = true;
		rep(j, s.size()-1) {
			if(m[s[j]].find(s[j+1]) == m[s[j]].end()) {
				flag = false;
				break;
			}
		}

		if(flag) cout << s << endl;
	}


	return 0;
}

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

int main(){
    int ans[4] = {0};
    int n;
    char buf[80];
    string b;

    while (scanf("%d,%s",&n,buf)!=EOF) {
        b = string(buf);
        if (b == "A") {
            ans[0]++;
        }
        else if (b == "B") {
            ans[1]++;
        }
        else if (b == "AB") {
            ans[2]++;
        }
        else if (b == "O") {
            ans[3]++;
        }
    }
    for (int i=0;i<4;i++) {
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

// dp[i][j][k]->iñÌòÎµWvðcµ,jsÚ,kñÚÉéÅ¬RXg
int dp[3][1001][77];
int field[151][1001];
const int INF=1000000000;

int main(){


	int n,m;
	while(cin>>n>>m&&!(n==0&&m==0)){
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 1001; j++)
				fill(dp[i][j],dp[i][j]+77,INF);

		int (*prv)[77]=dp[2];
		int (*pprv)[77]=dp[1];
		int (*cur)[77]=dp[0];
		memset(field,0,sizeof(field));
		for(int i = 0; i < n; i++){
			int k;
			cin>>k;
			for(int j = 0; j < k; j++){
				int x,d;
				cin>>x>>d;
				field[i][x-1]=d;
			}
		}
		// ún_ÌÝè
		for(int i = 0; i < 1001; i++){
			if(field[0][i]!=0)
				dp[0][i][m]=0;
		}
		if(m!=0){
			for(int i = 0; i < 1001; i++){
				if(field[1][i]!=0)
					dp[1][i][m-1]=0;
			}
		}

		// dpÅÅ¬RXgðßé
		for(int i = 1; i < n; i++){
			swap(cur,prv);
			swap(pprv,cur);
			if(m!=0&&i==1){

			}
			else{
				for(int j = 0; j < 1001; j++)
					fill(cur[j],cur[j]+77,INF);
			}
			// Ç±ÖWv·é©
			for(int j = 0; j < 1001; j++){
				if(field[i][j]==0)
					continue;
				// Ç±©çWv·é©
				for(int k = 0;  k < 1001; k++){
					if(field[i-1][k]==0&&(i<=1||field[i-2][k]==0))
						continue;
					// ÇÌRXgÅWv·é©
					for(int l = m; l >= 0; l--){
						// ÓÂ¤ÉWv
						int cost=((field[i-1][k]+field[i][j])*abs(k-j));
						cur[j][l]=min(cur[j][l],prv[k][l]+cost);
						if(i>=2&&l!=m){
							// êÂòÎµÅWv
							cost=((field[i-2][k]+field[i][j])*abs(k-j));
							cur[j][l]=min(cur[j][l],pprv[k][l+1]+cost);
						}
					}
				}
			}
		}
		int minRes=INF;
		for(int i = 0; i < 1001; i++){
			for(int j = 0; j <= m; j++)
				minRes=min(minRes,cur[i][j]);
			for(int j = 1; j <= m; j++)
				minRes=min(minRes,prv[i][j]);
		}
		cout<<minRes<<endl;
	}


	return 0;
}

Measured memory_bytes: 2360
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String w = sc.next();
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    for(int i = 0; i < w.length(); i++) {
      String s = String.valueOf(w.charAt(i));
      if(map.containsKey(s)) {
        map.put(s, map.get(s) + 1);
      } else {
        map.put(s, 1);
      }
    }
    String ans = "Yes";
    for(String str : map.keySet()) {
      if(map.get(str) % 2 == 1) ans = "No";
    }
    System.out.println(ans);
  }
}


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

int main( void ) 
{
	char Tarou[101];
	char Hanako[101];
	int n;
	int Tscore=0,Hscore=0;

    scanf( "%d", &n );
	while( n-- ) {
		scanf( "%s", Tarou );
		scanf( "%s", Hanako );

		if( 0 == strcmp( Tarou, Hanako ) ) {
			Tscore+=1;
			Hscore+=1;
		} else if(  0 < strcmp( Tarou, Hanako ) ) {
			Tscore+=3;
		} else {
			Hscore+=3;
		}
		
	}
	printf( "%d %d\n", Tscore, Hscore );	
	
	return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int i,j,n;
	static bool prime[1000001];
	for (i = 3; i <= 1000000; i += 2){
		prime[i] = true;
	}
	prime[2] = true;

	for (i = 3; i <= 1000; i += 2){
		if (prime[i] == 1){
			for (j = 3; j <= 1000000 / i; j += 2){
				prime[i * j] = false;
			}
		}
	}
	while(cin >> n && n){
		int count = 0;
		for(i=2;i<=n;i++){
			if(prime[i] == true) count++;
		}
		cout << count << endl;
	}
	return 0;
}

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

vector<int> res;

int main() {
  int l, r;
  cin >> l >> r;
  
  r = min(r, l + 2019*2);
  long long int minV = 2018;
  for (long long int i = l; i <= r; i++) {
    for (long long int j = i+1; j <= r; j++) {
      minV = min(minV, i * j % 2019);
    }
  }

  cout << minV << endl;
  return 0;
}


Measured memory_bytes: 256
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

const ll INF = 1LL << 50;

const ll mod = 1e9 + 7;

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

  vvll eds(n);
  rep(i, n) {
    ll u, k;
    cin >> u >> k;
    u--;
    rep(j, k) {
      ll v;
      cin >> v;
      v--;
      eds[u].push_back(v);
    }  // j
  }    // i

  vll ds(n);
  vll fs(n);
  ll t = 0;
  stack<ll> st;
  rep(i, n) {
    if (ds[i] > 0) continue;
    ds[i] = ++t;
    st.push(i);
    while (!st.empty()) {
      ll u = st.top();
      bool pc = true;
      rep(i, (ll)eds[u].size()) {
        ll v = eds[u][i];
        if (ds[v] > 0) continue;
        ds[v] = ++t;
        st.push(v);
        pc = false;
        break;
      }
      if(pc){
        fs[u] = ++t;
        st.pop();
      }
    }
  }

  rep(i, n) printf("%lld %lld %lld\n", i + 1, ds[i], fs[i]);

  return 0;
}



Measured memory_bytes: 3304
#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; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int N,H; cin >> N >> H;
    priority_queue<pair<int,int>> k;
    REP(i,N){
        int a,b; cin >> a >> b;
        k.push({a,0});
        k.push({b,1});
    }

    int ans = 0;
    while(H>0){
        auto sword = k.top(); k.pop();
        if(sword.second == 1){
            H -= sword.first;
            ans++;
        }else{
            ans += (H-1)/sword.first + 1;
            H = 0;
        }
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 5336
import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [list(map(int,input().split(" "))) for i in range(0,q)]

ans = sum(a)
anum = collections.Counter(a)

for i in range(q):
    x, y = b[i][0], b[i][1]
    ans += anum[x] * (y - x)
    anum[y] += anum[x]
    anum[x] = 0
    print(ans)

Measured memory_bytes: 40092
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll n,m;
	scanf("%lld%lld",&n,&m);
	if(n>m)
	{
		ll t=n;n=m;m=t;
	}
	if(n==1)
	{
		if(m==1)puts("1");else
		printf("%lld",m-2);
		return 0;
	}
	ll ans=(n-2)*(m-2);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 256
program ABC175C
    implicit none
    integer(8)X,K,D
    read*,X,K,D
    X=abs(X)

    if(X/D>=K)then
        print'(i0)',abs(X-D*K)
    else
        if(mod(X/D,2)==mod(K,2))then
            print'(i0)',abs(X-D*(X/D))
        else
            print'(i0)',min(abs(X-D*(X/D-1)),abs(X-D*(X/D+1)))
        end if
    end if
end program ABC175C

Measured memory_bytes: 2932
N = int(input())
MOD = 10**9+7
S = []
for i in range(2):
    t=[]
    s=input()
    for j in range(len(s)):
        t.append(s[j])
    S.append(t)
#i,jが一致するものと同じ色は使えない

l=[]
for i in range(N):
    if i>=1:
        if S[0][i]==S[0][i-1]:
            continue

    if S[0][i]==S[1][i]:
        l.append("x")
    else:
        l.append("y")
ans = 1

for i in range(len(l)):
    if i==0:
        if l[i]=="x":
            ans *= 3
        else:
            ans *= 6
        continue
    if l[i]=="x":
        if l[i-1]=="x":
            ans *= 2
        else:
            ans *= 1
    else:
        if l[i-1]=="x":
            ans *= 2
        else:
            ans *= 3
ans = ans%MOD
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define ppi pair<int,int>
#define ppl pair<ll,ll>
#define all(x) x.begin(),x.end()
#define ii int,int 
#define mm map<ii>
#define ff first    
#define ss second
#define forn(i,a,b) for(int i=a;i<b;i++)
#define forr(i,a,b) for(int i=a;i>=b;i--)
#define forv(i,m) for(auto i : m)
#define imx INT_MAX
#define imn INT_MIN
#define inf LONG_MAX
#define minf LONG_MIN
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sze size()
#define rvs reverse 
#define itr iterator 

/*
#define MODM(a,b,md) ((a%md)*(b%md))%md
#define MODA(a,b,md) ((a%md)+(b%md))%md
#define ull unsigned long long int
#define si short int
*/

/*
bool compare(int a,int b) {return a > b;}
bool compare1(ppi a,ppi b) {return a.ff > b.ff;}
bool compare2(ppi a,ppi b) {return a.ss < b.ss;}
ll Npower(ll a,ll b) {ll product = 1; while(b){if(b&1){product = product*a;}a = a*a;b = b>>1;} return product;}
ll power(ll a,ll b,ll md) {ll product = 1; while(b){if(b&1){product = MODM(product,a,md);}a = MODM(a,a,md);b = b>>1;} return product%md;}
ll GCD(ll a,ll b) {return b==0 ? a:GCD(b,a%b);}
ll LCM(ll a,ll b) {return (a/GCD(a,b))*b; }
*/


int main()
{
    fast

    int n;
    cin>>n;

    vi v(n);
    
    forn(i,0,n) cin>>v[i];

    sort(all(v));

    cout<<(v[n/2]-v[n/2-1]);



    return 0;
}

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
typedef long long LL;

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

	int N;
	int P[200002] = {0};
	int m[200002] = {0};
	
	cin >> N ;
	int min = N+1;
	for(int i=1; i<=N; i++){
		cin >> P[i];
		if(min > P[i]){
			min = P[i];
		}
		m[i] = min;
	}
	int ans = 0;
	for(int i=1; i<=N; i++){
		if(P[i] <= m[i]){
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

int main() {
    int n, y;
    cin >> n >> y;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n - i; j++) {
            if (10000 * i + 5000 * j + 1000 * (n - i - j) == y) {
                cout << i << ' ' << j << ' ' << (n - i - j) << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
double calc(double va,double vb,double ta,double tb){
    return (ta*va+tb*vb)/(va+vb);
}
 
int main(){
    double T,D,ta,tb,da,db;
    cin >> T >> D >> ta >> tb >> da >> db;
    double res = 1e9;
    for(int i = 0 ; i < 1010 ; i++){
	for(int j = 0 ; j < 1010 ; j++){
	    double va = da*i, vb = db*j;
	    if(i == 0 && j == 0) continue;
	    if(va + vb > D) continue;
	    res = min(res,abs(T-calc(va,vb,ta,tb)));
	}
    }
    printf("%.10f\n",res);
    return 0;
}

Measured memory_bytes: 3272
using System;

class Program
{
  static void Main(string[] args)
  {
    string S = Console.ReadLine();
    int N = S.Length;
    int[] A = new int[N];
    S += 'X';

    int start = 0;
    
    while (S[start] != 'X') {
      char status = S[start];
      int i = start + 1;
      int count = 0;
      while (S[i] == status) {
        ++i;
        ++count;
      }

      int curp = (count + 1) / 2;
      if (status == 'L') {
        A[start] += count - curp + 1;
        A[start-1] += curp;
      }
      else {
        A[i] += curp;
        A[i-1] += count - curp + 1;
      }
      start = i;      
    }

    for (int i = 0; i < N; ++i) {
      if (i > 0) {
        Console.Write(' ');
      }
      Console.Write(A[i]);
    }
    Console.WriteLine();
  }
}


Measured memory_bytes: 14048
n,k=[int(x) for x in input().split()]
x=[0]
for xi in input().split():
    xi=int(xi)
    if xi ==0:
        k-=1
    else:
        x.append(xi)
x=sorted(x)
ans=10**10

zero=x.index(0)
for i in range(max(0,zero-k-1),min(zero+1,n-k+1)):
    if x[i+k]<0 or x[i]>0:
        continue
    jogen=abs(x[i+k])
    kagen=abs(x[i])
    ans=min(ans,jogen*2+kagen,kagen*2+jogen)
print(ans)

Measured memory_bytes: 62576
/**
 *   created: 22 May 2019  22:00:21
**/
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef vector< pair<int , int> > vii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long , long long> pll;
typedef vector< pair<long long , long long> > vll;

#define PB push_back
#define PPB pop_back
#define all(c) (c).begin,(c).end()
#define F(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define INFLL 2000000000000000007
#define INF 2000000007
#define MOD 1000000007


#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


void optimizeIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

//                                        //AUTHOR: Kaushalesh Shukla

//=========================================================================================================

int main()
{
	optimizeIO();
	int tt=1;
	//cin>>tt;
	while(tt--){
		int n,k;
		cin>>n>>k;
		vi v(n);
		rep(i,0,n)
			cin>>v[i];
		vector< vi > mem(n,vi(k,INF));
		rep(i,0,k){
			mem[0][i] = 0;
		}
		vi mini(n);
		mini[0] = 0;
		rep(i,1,n){
			int temp = INF;
			rep(j,1,k+1){
				if(i-j<0)
					break;
				mem[i][j-1] = mini[i-j] + abs(v[i]-v[i-j]);
				temp = min(temp,mem[i][j-1]);
			}
			mini[i] = temp;
		}
		cout<<mini[n-1];
	}
	return 0;
}


Measured memory_bytes: 44032
program sum_of_three_integers
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: k,s,x,y,z,ans

    ans=0
    read*, k,s

    do x=0,k
        do y=0,k
            z = s-x-y
            if (0<=z .and. z<=k) ans=ans+1
        end do
    end do

    print'(i0)', ans
end program sum_of_three_integers

Measured memory_bytes: 384