akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath> 
#include <queue>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <cstdio>
#include <set>
using namespace std;
int a,b,c;
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>a>>b>>c;
	if (a+b+c==17)
		cout<<"YES";
	else
		cout<<"NO";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
const int inf=1e9;
int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	return f*x;
}
struct node {
	int v,son,size,fa,ch[2];
} a[500001];
int root,tot;
void rotate(int x) {
	int y=a[x].fa,z=a[y].fa,k=(a[y].ch[1]==x);
	a[z].ch[a[z].ch[1]==y]=x,a[x].fa=z;
	a[a[x].ch[k^1]].fa=y,a[y].ch[k]=a[x].ch[k^1];
	a[y].fa=x,a[x].ch[k^1]=y;
	a[x].son=a[x].size+a[a[x].ch[0]].son+a[a[x].ch[1]].son;
	a[y].son=a[y].size+a[a[y].ch[0]].son+a[a[y].ch[1]].son;
}
void splay(int x,int top) {
	while(a[x].fa!=top) {
		int y=a[x].fa,z=a[y].fa;
		if(z!=top)
			(a[y].ch[0]==x)^(a[y].ch[0]==y)?rotate(x):rotate(y);
		rotate(x);
	}
	if(!top) root=x;
}
void insert(int x) {
	int u=root,f=0;
	while(u&&a[u].v!=x)
		f=u,u=a[u].ch[x>a[u].v];
	if(u) {
		a[u].size++,splay(u,0);
		return ;
	}
	u=++tot;
	if(f) a[f].ch[x>a[f].v]=u;
	a[u].fa=f,a[u].size=a[u].son=1,a[u].v=x,splay(u,0);
}
void find(int x) {
	int u=root;
	while(a[u].v!=x&&a[u].ch[x>a[u].v]) u=a[u].ch[x>a[u].v];
	splay(u,0);
}
int Next(int x,int f) {
	find(x);
	if((f&&a[root].v>x)||(!f&&x>a[root].v)) return root;
	int u=a[root].ch[f];
	while(a[u].ch[f^1]) u=a[u].ch[f^1];
	return u;
}
void delet(int x) {
	int A=Next(x,0),B=Next(x,1);
	splay(A,0),splay(B,A);
	int u=a[B].ch[0];
	if(a[u].size>1) a[u].size--,splay(u,0);
	else a[B].ch[0]=0;
}
int kth(int x) {
	int u=root;
	if(a[u].son<x) return 0;
	while(1) {
		if(x>a[a[u].ch[0]].son+a[u].size)
			x-=a[a[u].ch[0]].son+a[u].size,u=a[u].ch[1];
		else if(a[a[u].ch[0]].son>=x)
			u=a[u].ch[0];
		else return a[u].v;
	}
}
int main() {
	int n=read(),ans=0;
	insert(inf);
	insert(-inf);
	for(int i=1; i<=n; i++) {
		int x=read();
		int now=a[Next(x,0)].v;
		if(now!=-inf) delet(now),insert(x);
		else insert(x),ans++;
	}
	cout<<ans<<endl;
	return 0;
}


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

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

	
	if(A==B&&B==C){
		cout << "Yes" << endl;
	}
	
	else{
		cout << "No" << endl;
	}
	}
	

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

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int n,segtree[2123456];
string s;

void init(int i=0, int l=0, int r=n){
	if(r-l>1){
		init(i*2+1,l,(l+r)/2);
		init(i*2+2,(l+r)/2,r);
		segtree[i] = (segtree[i*2+1]|segtree[i*2+2]);
	}else{
		segtree[i] = (1<<(s[l]-'a'));
	}
}

void update(int p, int v, int i=0, int l=0, int r=n){
	if(!(l<=p && p<r)){
		return;
	}else if(r-l>1){
		update(p,v,i*2+1,l,(l+r)/2);
		update(p,v,i*2+2,(l+r)/2,r);
		segtree[i] = (segtree[i*2+1]|segtree[i*2+2]);
	}else{
		segtree[i] = v;
	}
}

int query(int a, int b, int i=0, int l=0, int r=n){
	if(b<=l || r<=a){
		return 0;
	}else if(a<=l && r<=b){
		return segtree[i];
	}else{
		return (query(a,b,i*2+1,l,(l+r)/2)|query(a,b,i*2+2,(l+r)/2,r));
	}
}

int main(void){
	int q,t,i,j,l,r;
	char c;
	cin >> n;
	cin >> s;
	init();
	cin >> q;
	for(i=0; i<q; ++i){
		cin >> t;
		if(t>1){
			cin >> l >> r; --l;
			cout << __builtin_popcount(query(l,r)) << endl;
		}else{
			cin >> j >> c; --j;
			c -= 'a';
			update(j,(1<<c));
		}
	}
	return 0;
}


Measured memory_bytes: 7044
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long a,b,c,k;
  cin>>a>>b>>c>>k;
  if(abs(a-b)>1000000000000000000){
    cout << "unfair" << endl;
  }
  else{
    if(k%2 == 0){
      cout << a-b << endl;
    }
    else{
      cout << b-a << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N,A,B;
 cin >> N >> A >> B;
 int X = N * A;
 if (B > X) {
   cout << X << endl;
 }
 if (B < X) {
   cout << B << endl;
 }
 if (B == X) {
   cout << B << endl;
 }
 
}

Measured memory_bytes: 256
MOD = 1000000007

START = 0
SINGLE = 1
DOUBLE = 2

n = int(raw_input())

d = [raw_input() for i in xrange(2)]

ind = 0
prev = START
total = 1
while ind < n:
    x = d[0][ind]
    if x == d[1][ind]:
        if prev == START:
            total *= 3
        elif prev == SINGLE:
            total *= 2
        elif prev == DOUBLE:
            total *= 1

        prev = SINGLE
        
    elif ind + 1 < n and (x == d[0][ind+1] and d[1][ind] == d[1][ind+1]):
        if prev == START:
            total *= 6
        elif prev == SINGLE:
            total *= 2
        elif prev == DOUBLE:
            total *= 3

        ind += 1
        prev = DOUBLE

    ind += 1
    total %= MOD

print total

Measured memory_bytes: 28396
#include <cstdio>
int main() {
	int a, b;
    scanf("%d %d", &a, &b);
    if (a < b) {
        printf("a < b\n");
    } else if (a > b) {
        printf("a > b\n");
    } else {
        printf("a == b\n");
    }
}


Measured memory_bytes: 2604
# https://atcoder.jp/contests/abc055/tasks/arc069_b

# 先頭の2つの動物を仮定すれば後は決定的に決まる
# 決定的に決めた後に成り立つかどうか判定すれば良い 具体的にはs[0]と生成した文字列SのS[-1],S[0],S[1]を調べればよい
N = int(input())
s = input()


def simu(ret):
    for i, ss in enumerate(s[1:], start=1):
        if ret[i] == 'S' and ss == 'o':
            ret += ret[i - 1]
        elif ret[i] == 'S' and ss == 'x':
            ret += 'W' if ret[i - 1] == 'S' else 'S'
        elif ret[i] == 'W' and ss == 'o':
            ret += 'W' if ret[i - 1] == 'S' else 'S'
        elif ret[i] == 'W' and ss == 'x':
            ret += ret[i - 1]
    return ret


def check(ret):
    ss = s[0]
    if ret[-1] != ret[0]:
        return False
    if ret[0] == 'S' and ss == 'o':
        return ret[-2] == ret[1]
    elif ret[0] == 'S' and ss == 'x':
        return ret[-2] != ret[1]
    elif ret[0] == 'W' and ss == 'o':
        return ret[-2] != ret[1]
    elif ret[0] == 'W' and ss == 'x':
        return ret[-2] == ret[1]


# パターン1
for ret in ['SS', 'SW', 'WS', 'WW']:
    ret1 = simu(ret)
    # print(ret1)
    if check(ret1):
        print(ret1[:-1])
        exit()
print(-1)


Measured memory_bytes: 3700
/*
    ThunderClap and Flash.
    Raunaq Singh
*/
#include "bits/stdc++.h" 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
#define ThunderClap ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
#define debugg(something)   cout<<#something<<" - "<<something<<"\n";
#define vi vector
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define LB lower_bound
#define UB upper_bound
#define mp make_pair
#define pb push_back
#define in insert
#define s second
#define f first
#define pQueue priority_queue
#define maxElement *max_element
#define minElement *min_element
#define MAX 100000LL
#define mod 1000000007LL
#define inf 1000000000000000000LL
#define mI2 500000004LL
inline ll add(ll a, ll b){ return ((a%mod)+(b%mod))%mod;}
inline ll mul(ll a, ll b){ return ((a%mod)*(b%mod))%mod;}
inline ll sub(ll a, ll b){ return ((a%mod)-(b%mod)+mod)%mod;}

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

void Flash(){
    ll n,k;
    cin>>n>>k;
    ll ans=modexp(k,n);
    ll temp,tempVal;
    ll a[k+1];
    for(ll i=2;i<=k;i++){
        temp=(k/i);
        a[i]=modexp(temp,n);
    }
    for(ll i=k;i>=2;i--){
        for(ll j=2*i;j<=k;j+=i){
            a[i]=sub(a[i],a[j]);
        }
    }
    for(ll i=2;i<=k;i++){
        tempVal=a[i];
        //debugg(tempVal);
        ans=add(ans,mul(i-1,tempVal));
    }
    cout<<ans<<"\n";
}

int main(int argc, char const *argv[]){
    ThunderClap;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        Flash();
    }
    return 0;
}

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

using ll = long long;

void ANS (ll x, ll y) {
	cout << x << " " << y;
	exit(0);
}

map <ll, int> m;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	for (ll i=-2000; i<=2000; i++) {
		ll in = i*i*i*i*i;
		m[in] = i;
	}
	for (ll i=-2000; i<=2000; i++) {
		ll x = i*i*i*i*i;
		ll need = x-n;
		if (!m.count(need)) continue;
		ll y = m[need]; y = y*y*y*y*y;
		if (x-y == n) {
			ANS(i, m[need]);
		}
	}
	return 0;
}


Measured memory_bytes: 3908
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean flag = true;
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if(a%2==0) {
				if((a%3!=0)&&(a%5!=0)) {
					flag = false;
					break;
				}
			}
		}
		System.out.println(flag?"APPROVED":"DENIED");
		sc.close();
	}
}

Measured memory_bytes: 23760
N = int(input())
A = list(input().split())
#print(N,"\n", A)
temp = 0
el = 1
for i in range(0,N):
    temp = temp + el*int(A[i])
    el = el * (-1)

if N == 1:
    print(temp)
else:
    print(temp, end=' ')
    C = int(temp/2)
    for i in range(1,N-1):
        curr = int(A[i-1])-C
        #print('{}: '.format(i), end='')
        print(2*curr, end=' ')
        C = curr
    curr = int(A[N-2])-C
    print(2*curr)



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

int main()
{
	int n,w[100]={};
	int dp[100][100] = {};//縦から横まで
	int s1,s2,check;
	unsigned int ans=10000000;

	cin >> n;

	for(int i = 0;i<n;i++)
	{
		cin >> w[i];
	}

	for(int t = 0; t<=n-1;t++)
	{
		for(int made1 =0; made1 <= t; made1++)
		{
			if(made1==0)
			{
				dp[0][0] = w[0];
				continue;
			}

			dp[0][made1] = dp[0][made1-1] + w[made1];
		}
		for(int made2 =t + 1; made2 < n; made2++)
		{
			if(made2==t + 1)
			{
				dp[t + 1][t + 1] = w[t + 1];
				continue;
			}

			dp[t + 1][made2] = dp[t + 1][made2-1] + w[made2];
		}
		s1 = dp[0][t];
		s2 = dp[t + 1][n -1];
		check = s1 - s2;
		if(check<0)check = check * -1;
		//cout << t <<"madenokekkaha"<< check <<"desita"<<endl;
		if(check<ans)ans = check;
	}
	/*cout << "result dp" << endl;
	for(int i = 0;i<100;i++)
	{
		for(int j = 0;j<100;j++)
		{
			cout << dp[i][j] << " ";
			if(j==99)cout<<endl;
		}
	}*/
	cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, a,b, ans=0;
	scanf("%d", &n);
	while(n--) {
		scanf("%d%d", &a, &b);
		ans += (b-a+1);
	}
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

long long  p[110][4][4][4];
int A=0,G=1,C=2,T=3;

int main()
{
    int i,j,k,l,m;
    long long ans;
    int mod=pow(10,9)+7;
    int n;
    scanf("%d",&n);
    for(i=0; i<4; ++i)
    {
        for(j=0; j<4; ++j)
        {
            for(k=0; k<4; ++k)
            {
                if(i==A&&j==G&&k==C)
                    continue;
                if(i==A&&j==C&&k==G)
                    continue;
                if(i==G&&j==A&&k==C)
                    continue;
                p[3][i][j][k]=1;
            }
        }
    }
    for(i=3; i<n; ++i)
    {
        for(j=0; j<4; ++j)
        {
            for(k=0; k<4; ++k)
            {
                for(l=0; l<4; ++l)
                {
                    for(m=0; m<4; ++m)
                    {
                        if(k==A&&l==G&&m==C)
                            continue;
                        if(k==A&&l==C&&m==G)
                            continue;
                        if(k==G&&l==A&&m==C)
                            continue;
                        if(j==A&&k==G&&m==C)
                            continue;
                        if(j==A&&l==G&&m==C)
                            continue;
                        p[i+1][k][l][m]=(p[i+1][k][l][m]+p[i][j][k][l])%mod;
                    }
                }
            }
        }
    }
    for(i=0,ans=0; i<4; ++i)
    {
        for(j=0; j<4; ++j)
        {
            for(k=0; k<4; ++k)
            {
                ans=(ans+p[n][i][j][k])%mod;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define N 200
#define MAX 200
int top;
int S[MAX];
void initialize();
int isEmpty();
int isFull();
void push(int x);
int pop();

int main()
{
  int i,num,l,k;
  char n[N];
  
  initialize();
  while((scanf("%s",n)) != EOF){
    if(n[0] == '+'){
      l = pop();
      k = pop();
      push(l + k);
    }
    else if(n[0] == '-'){
      l = pop();
      k = pop();
      push(k -l);
    }
    else if(n[0] == '*'){
      l = pop();
      k = pop();
      push(l * k);
    }
    else{
      num = atoi(n);
      if(num >= 1000000) continue;
      push(num);
    }
  }
  printf("%d\n",pop());
  return 0;
}

void initialize(){
  top = 0;
}
int isEmpty(){
  if(top == 0){
  return -1;
  }
  return 0;
}
int isFull(){
  if(top >= MAX -1){
  return -1;
  }
  return 0;
}
void push(int x){
  if(isFull() == -1){
    printf("Error\n");
  }
  top++;
  S[top] = x;
}
int pop(){
  if(isEmpty() == -1){
    printf("Error\n");
  }
  top--;
  return S[top+1];  
}



Measured memory_bytes: 2100
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
    arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
    for (auto& i : arr) {
        fill_all(i, v);
    }
}

int32_t N;
int32_t A[20][2];
int32_t dp[55][1 << 18];
int32_t func(int pos, int min, std::bitset<18> mask)
{
    if (pos == N) { return 0; }
    auto& memo = dp[min][mask.to_ulong()];
    if (memo != -1) { return memo; }
    memo = 100100;
    int pos2 = pos % 2;
    int npos = -1;
    for (int32_t i = 0; i < N; i++)
    {
        if (mask[i]) {
            ++npos;
            if(min <= A[i][pos2]) {
                mask[i] = false;

                memo = std::min(memo, func(pos + 1, A[i][pos2], mask) + npos);
                mask[i] = true;
            }
        }
    }
    return memo;
}

int main()
{
    using std::endl;
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
    in.tie(nullptr);
    out.tie(nullptr);

    in >> N;
    for (size_t i = 0; i < N; i++)
    {
        in >> A[i][i % 2];
    }
    for (size_t i = 0; i < N; i++)
    {
        in >> A[i][(i + 1) % 2];
    }
    fill_all(dp, -1);
    auto res = func(0, 0, (1 << N) - 1);
    
    if (100100 <= res) {
        out << -1 << endl;
    }
    else { out << res << endl; }

    return 0;
}
#endif


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

using namespace std;
int main(){
    int in, out, a;
    out = 0;
    cin>>in;

    if(in>=500){
        a=in/500;
        out += a*1000;
        
        in=in%500;
    }
    if(in>=5){
        a = in/5;
        out += a*5;

    }
    cout<<out<<"\n";

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <deque>
#include <algorithm>
#include <math.h>
#include <random>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define int long long
#define double long double
#define Matrix vector<vector<int> >
#define kektor vector

using namespace std;

typedef long long ll;

int RanddInt(int min, int max) {
  if (max < min) {
    return 0;
  }
  random_device rd;
  mt19937 mt(rd());
  uniform_int_distribution<int> dist(min, max);
  return dist(mt);
}

const int maxn = 1e4, mod = 1e9 + 7;
bool debug = false;
int n;
char beg;
vector<int> even;

void binn() {
	int l = 0; 
	int m; 
	int r = even.size(); 
	while (l + 1 < r) {
		m = (l + r) / 2; 
		cout << even[m] << endl;
		string a; 
		cin >> a;
		if (a[0] == beg)  {
			l = m;
		} else if (a[0] == 'V') {
			cout << even[m] << endl; 
			exit(0); 
		} else {
			r = m; 
		}
	}	
	cout << even[l] + 1 << endl;
	exit(0);	
}

void solve()  {
	cin >> n;
	for (int i = 0; i < n; i += 2) {
		even.pb(i); 
	}
	cout << 0 << endl;
	string a;
	cin >> a;
	if (a[0] == 'M') {
		beg = 'M';
	} else if (a[0] == 'F') {
		beg = 'F';
	} else {   
		cout << 0 << endl; 
		exit(0);
	}
	binn();  
}


signed main() {
    /*!

    !*/
    cout.precision(10);
    cout << fixed;
    if (!debug) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    }
//	freopen("TASK.in", "r", stdin);
  // 	freopen("TASK.out", "w", stdout);
    solve();
    return 0;
}


Measured memory_bytes: 1488
n, m, v, p = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
thr = arr[p - 1]

ok, ng = 0, n

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    # midに全力投票した時のスコア
    x = arr[mid] + m
    # 残りの投票数
    rest = m * (v - 1)

    # 全力投票で届かない場合は探索を続行
    if x < thr:
        ng = mid
        continue

    # 全力投票で届く場合、残りの票を上手く処理できるか
    for i, a in enumerate(arr):
        # idxがp未満の場合は最大まで積める
        if i < p and arr[i] > thr:
            rest -= m
        elif i == mid:
            continue
        # idxがpより後ろの場合はmかx-aまで積める
        else:
            rest -= min(m, x - a)

    # 消化しきれていれば勝ち、そうでなければ負け
    if rest <= 0:
        ok = mid
    else:
        ng = mid

print(ok + 1)

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

int32_t main(){

	int n,k;
	cin>>n>>k;

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

	for (int i=0;i<n;i++){

		double tt = 1/arr[i];
		arr[i] = tt*((arr[i]*(arr[i]+1))/2);
	}

	int start=0,end=0;

	double sum=0;

	while (end!=k){
		sum+=arr[end];
		end++;
	}

	double fake=sum;

	while (end<n){

		fake-=arr[start];
		fake+=arr[end];

		sum=max(sum,fake);
		start++,end++;
	}

	cout<<fixed<<setprecision(10)<<sum<<'\n';



}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,m;
  cin>>n>>m;
  string a[n],b[m];
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<m;i++) cin>>b[i];
  bool f=0;
  for(int i=0;i<=n-m;i++){
    for(int j=0;j<=n-m;j++){
      bool ff=1;
      for(int k=0;k<m;k++)
	for(int l=0;l<m;l++)
	  ff&=a[i+k][j+l]==b[k][l];
      f|=ff;
    }
  }
  cout<<(f?"Yes":"No")<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <map>
#include <math.h>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> P;
#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fir first
#define sec second
#define pb push_back
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 int INF = 1<<30;
const ll LINF = 1LL<<58;
const int mod = 1000000007;

bool check(int a){
	for (int i = 1; i < 130; i++){
		int d = i*i;
		if(a==d) return true;
	}
	return false;
}

int main(){
	int n;
	cin >> n;
	vector<int> A(n);
	rep(i,n){
		cin >> A[i];
	}
	int a = 0, b = 0;
	rep(i,n){
		if(A[i] >= a){
			b = a;
			a = A[i];
		}
		else if(A[i] > b) b = A[i];
	}
	rep(i,n){
		if(A[i] == a) cout << b << endl;
		else cout << a << endl;
	}
	return 0;
}


Measured memory_bytes: 2432
#include <stdio.h>

int main(){
  int W, H, N;
  int x[110] = {}, y[110] = {}, a[110] = {};

  scanf("%d %d %d", &W, &H, &N);
  for(int i = 0; i < N; i++){
    scanf("%d %d %d", &x[i], &y[i], &a[i]);
  }

  int S = W*H;
  int x1 = 0, x2 = W, y3 = 0, y4 = H;

  for(int i = 0; i < N; i++){
    if(a[i] == 1 && x[i] > x1){
      x1 = x[i];
    }
    if(a[i] == 2 && x[i] < x2){
      x2 = x[i];
    }
    if(a[i] == 3 && y[i] > y3){
      y3 = y[i];
    }
    if(a[i] == 4 && y[i] < y4){
      y4 = y[i];
    }
  }

  if(x1 >= x2 || y3 >= y4){
    printf("%d\n", 0);
  }else{
    printf("%d\n", (x2 - x1)*(y4 - y3));
  }

  return 0;
}


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

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

const ll mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 1152921504606846976

int main()
{
    int h,w,d; cin >> h >> w >> d;
    int a[h][w]; rep(i,h) rep(j,w) cin >> a[i][j];
    int q; cin >> q;
    vector<pair<int,pair<int,int> > > g[d];
    vector<int> sum[d];
    rep(i,h) {
        rep(j,w){
            g[a[i][j] % d].push_back(make_pair(a[i][j],make_pair(i,j)));
        }
    }
    rep(i,d){
        sort(g[i].begin(),g[i].end());
    }
    rep(i,d){
        sum[i].push_back(0);
        rep(j,g[i].size()-1){
            sum[i].push_back(abs(g[i][j+1].second.first - g[i][j].second.first )+abs(g[i][j+1].second.second - g[i][j].second.second));
        }
    }
    rep(i,d){
        rep(j,g[i].size()-1){
            sum[i][j+1] += sum[i][j];
        }
    }
    rep(i,q){
        int l,r; cin >> l >> r;
        int tmp = l % d;
        cout << sum[tmp][(r-1)/d] - sum[tmp][(l-1)/d] << endl;
    }
}


Measured memory_bytes: 10624
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
const ll INF=(ll)1e18;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int a,b,c,d;cin>>a>>b>>c>>d;
    if(c/b+(c%b==0?0:1)<=a/d+(a%d==0?0:1))cout<<"Yes\n";
    else cout<<"No\n";
}


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

int n, m;
template <class T>
void readVector(int n, vector<T> &v){
	for(int i=0; i<n; ++i){
		T t;
		cin >> t;
		v.push_back(t);
	}
}

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0) return 0;
		vector<int> a, b;
		readVector(n, a);
		readVector(m, b);
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		int s = 0, t = 0;
		for(auto i : a) s += i;
		for(auto i : b) t += i;
		bool f = false;
		for(int i=0; i<n&&!f; ++i)
			for(int j=0; j<m; ++j)
				if(2 * (a[i] - b[j]) == s - t){
					cout << a[i] << " " << b[j] << "\n";
					f = true;
					break;
				}
		if(!f) cout << "-1\n";
	}
}


Measured memory_bytes: 3044
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll memo[105][100005];
ll prefix[105][100005];
ll arr[105];

const ll M=1e9+7;

ll getCost(int row,int left,int right){
    if(left==0) return prefix[row][right]%M;
    return ((prefix[row][right]%M-prefix[row][left-1]%M)+M)%M;
}
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    sort(arr,arr+n);
    
    for(int i=0;i<=n;i++){
        memo[i][0]=1;
        prefix[i][0]=1;
    }
    
    for(int i=0;i<=k;i++){
        prefix[0][i]=1;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            memo[i][j]=getCost(i-1,j-min(arr[i-1],(ll)j),j)%M;
            prefix[i][j]=(memo[i][j]%M+prefix[i][j-1]%M)%M;
            
            //cout<<memo[i][j]<<" ";
        }
        
        //cout<<endl;
    }
    
    
    cout<<memo[n][k]%M<<endl;
}

Measured memory_bytes: 160000
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
    // 頂点数と辺数
    int N, M; cin >> N >> M;

    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
         --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // BFS のためのデータ構造
    vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[0] = 0;
    que.push(0); // 0 を橙色頂点にする
     int ans[N]={0};
    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            ans[nv] = v;
            que.push(nv);
        }
    }

    cout << "Yes" << endl;
    for (int v = 1; v < N; ++v) cout << ans[v]+1 << endl;
    return 0;
}

Measured memory_bytes: 10580
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto ad = readln.chomp;
    int A = ad[0] - '0';
    int B = ad[1] - '0';
    int C = ad[2] - '0';
    int D = ad[3] - '0';
    
    foreach (o; 0..8) {
        int s = A;
        string o1, o2, o3;
        if (o & 1) {
            s += B;
            o1 = "+";
        } else {
            s -= B;
            o1 = "-";
        }
        if (o & 2) {
            s += C;
            o2 = "+";
        } else {
            s -= C;
            o2 = "-";
        }
        if (o & 4) {
            s += D;
            o3 = "+";
        } else {
            s -= D;
            o3 = "-";
        }
        if (s == 7) {
            writefln("%d%s%d%s%d%s%d=7", A, o1, B, o2, C, o3, D);
            return;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define s(x, n) memset(x, n, sizeof(x));
#define pb(x) push_back(x)
#define NIL -1
#define MAXN 2001

void solve()
{
    ll n;
    cin >> n;
    ll a = 1, b = 1, c = 1;
    for (int i = 1; i <= n; i++)
    {
        a *= 10 % mod;
        a %= mod;
        b *= 8 % mod;
        b %= mod;
        c *= 9 % mod;
        c %= mod;
    }
    cout << (a + b - (2 * c) % mod + mod) % mod << "\n";
}
int main()
{
#ifdef WIN32
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

#ifndef WIN32
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#endif
    int t;
    t = 1;
    /// cin >> t;
    for (int I = 1; I <= t; I++)
    {
        solve();
    }
    return 0;
}


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

using ll=long long; 

void solve(){
	int h,w;
	cin>>h>>w;
	vector<string > fld(h);
	for(auto& e:fld){
		cin>>e;
	}
	for(auto e:fld){
		cout<<e<<endl;
		cout<<e<<endl;
	}
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <cstring>
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ll X;
    ll fh = 0;
    ll f = 0;
    ll H = 0;

    cin >> X;

    fh = X/500;

    if(fh>0) {
        H = fh*1000;
        X -= fh*500;
    }

    f = X/5;

    if(f>0) {
        H += f*5;
    }

    cout << H << endl;
    
    return 0;

}

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

int n;
bool color[100010];
bool visited[100010];
vector< pair<int, bool> > graph[100010];

void paint(int node) {
    if(visited[node])
        return;

    visited[node] = true;
    for( auto x : graph[node] ) {
        int nn = x.first;
        color[nn] = (color[node] + x.second) % 2;
        paint(nn);
    }
}

int main() {
    cin >> n;
    for(int i = 0; i < n-1; i++) {
        int u, v;
        long long int w;
        cin >> u >> v >> w;
        u--; v--;
        graph[u].push_back( make_pair(v, (bool)(w % 2)) );
        graph[v].push_back( make_pair(u, (bool)(w % 2)) );
    }

    color[0] = 1;
    for(int node = 0; node < n; node++)
        paint(node);

    for(int node = 0; node < n; node++)
        cout << color[node] << endl;
}


Measured memory_bytes: 7424
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	nextReader = newScanner()
	n, k := nextInt(), nextInt()
	a := n % k
	b := abs(a - k)
	fmt.Println(min(a, b))
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

// ---------------------------------------------------------------
// I/O
// ---------------------------------------------------------------
var nextReader func() string

func newScanner() func() string {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, 1024), int(1e11))
	sc.Split(bufio.ScanWords)
	return func() string {
		sc.Scan()
		return sc.Text()
	}
}

func nextString() string { return nextReader() }

func nextInt() int { n, _ := strconv.Atoi(nextReader()); return n }

func nextInts(size int) []int {
	ns := make([]int, size)
	for i := 0; i < size; i++ {
		ns[i] = nextInt()
	}
	return ns
}


Measured memory_bytes: 1756
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>

using namespace std;

#define FOR(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define REP(i, n) FOR((i), 0, (n))

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T>
void print_container(T &container, string delim=" ") {
    bool first = true;
    for(auto &t: container){
        if(!first){
            cout << delim;
        }
        first = false;
        cout << t;
    }
    cout << endl;
}

int main() {
    int k;
    cin >> k;
    queue<ll> lun;
    IFOR(i, 1, 9)
        lun.push(i);

    REP(i, k-1){
        ll x = lun.front();
        lun.pop();
        if(x%10>0) lun.push(10*x+x%10-1);
        lun.push(10*x+x%10);
        if(x%10<9) lun.push(10*x+x%10+1);
    }
    cout << lun.front() << endl;


    return 0;
}

Measured memory_bytes: 4616
S = gets.chomp

divides = ['dream', 'dreamer', 'erase', 'eraser']
dp = S.size.times.map{false}
dp[0] = true

0.step (S.size - 1) do |i|
  next if !dp[i]
  divides.each do |d|
#    puts "#{i}: #{d}"
    dp[i + d.size] = true if S.slice(i, d.size) == d
  end
end
#p dp
puts dp[S.size] ? 'YES' : 'NO'

Measured memory_bytes: 2812
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
#define N 5000
int g[N+1][N+1];
void add(int n, int i, int j, int v) {
    if(1 <= i and i <= n and 1 <= j and j <= i) {
        g[i][j] += v;
    }
}
void update(int n, int a, int b, int x, int v = 1) {
    add(n, a, b, v);
    add(n, a, b + 1, -v);
    add(n, a + x + 1, b, -v);
    add(n, a + x + 1, b + x + 2, v);
    add(n, a + x + 2, b + 1, v);
    add(n, a + x + 2, b + x + 2, -v);
}
void sum(int n, int si, int sj, int di, int dj) {
    for(int i = si; i <= n; i++) {
        for(int j = sj; j <= i; j++) {
            g[i][j] += g[i-di][j-dj];
        }
    }
}
void resolve(int n) {
    sum(n, 1, 2, 0, 1);
    sum(n, 2, 1, 1, 0);
    sum(n, 2, 2, 1, 1);
}
template <typename Function>
void proc(int n, const Function& f) {
#ifdef DEBUG
    using actual_type = typename callable_traits<Function>::function_type;
    using expected_type = typename callable_traits<void(int, int)>::function_type;
    static_assert(is_same<actual_type, expected_type>::value, "proc 'f' must be void(int, int)");
#endif
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            f(i, j);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    memset(g, 0, sizeof g);
    for(int i = 0; i < m; i++) {
        int a, b, x;
        cin >> a >> b >> x;
        update(n, a, b, x);
    }
    resolve(n);
    int ans = 0;
    proc(n, [&](int i, int j) { ans += g[i][j] > 0; });
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 100892
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

#ifndef _DEBUG
#define main_ main
#endif
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<string> vs;

template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
	return left.second > right.second;
}

void init_global() {}

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

	int N; cin >> N;
	vl A(N); FOR(i, 0, N) cin >> A[i];

	ll sum = 0, cnt = 0;

	// (i) + - + - ...
	FOR(i, 0, N) {
		sum += A[i];
		if (i % 2 == 0 && sum <= 0) {
			cnt += abs(sum) + 1;
			sum = 1;
		}
		else if (i % 2 == 1 && sum >= 0) {
			cnt += abs(sum) + 1;
			sum = -1;
		}
	}

	ll ans = cnt;
	sum = cnt = 0;

	// (ii) - + - + ...
	FOR(i, 0, N) {
		sum += A[i];
		if (i % 2 == 0 && sum >= 0) {
			cnt += abs(sum) + 1;
			sum = -1;
		}
		else if (i % 2 == 1 && sum <= 0) {
			cnt += abs(sum) + 1;
			sum = 1;
		}
	}

	ans = min(ans, cnt);

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


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long a,b,c,x,x1;
  cin>>a>>b>>c;
   x=c-a-b;
   if(x<0)
   {
    cout<<"No"<<endl;
    return 0;
   }
   x=x*x;
   x1=4*a*b;
  if(x1<x)
  {
    cout<<"Yes"<<endl;
  }else
  {
    cout<<"No"<<endl;
  }
 return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; (i) < (n); ++ (i))
#define loop(i,a,n) for (int i = (a); (i) < (n); ++ (i))
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 0
//#define int ll
using namespace std;
typedef vector<int> vi;

signed main(){
    ll n,ta=0,ao=0,ans = 0;
    cin >> n;
    vector<ll> a(n),b(n);
    vector<pair<ll,ll>> total(n);
    rep(i,n) {
        cin >> a[i] >> b[i];
        total[i] = make_pair(a[i]+b[i],i);
    }
    sort(total.begin(),total.end(),greater<pair<ll,ll>>());
    int i = 0;
    while(i < n) {
        ta = a[total[i].second];
        i++;
        if(i == n) {
            ans += ta;
            break;
        }
        ao = b[total[i].second];
        ans += ta - ao;
        i++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
// #define int ll
// #define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N=40404;
struct line{
	int a,b,c,i;
	line(){}
}a[N];
double curx,cury;
bool compxminusinf(const line&p1,const line&p2){
	return (double)p1.a/p1.b>(double)p2.a/p2.b;
}
bool compyminusinf(const line&p1,const line&p2){
	return (double)p1.b/p1.a>(double)p2.b/p2.a;
}
bool compy(const line&p1,const line&p2){
	return (-p1.c-p1.a*curx)/p1.b<(-p2.c-p2.a*curx)/p2.b;
}
bool compx(const line&p1,const line&p2){
	return (-p1.c-p1.b*cury)/p1.a<(-p2.c-p2.b*cury)/p2.a;
}
int t[N];
int get(int i){
    int res=0;
    for(;i>=0;i=(i&(i+1))-1)res+=t[i];
    return res;
}
void add(int i,int x){for(;i<N;i|=i+1)t[i]+=x;}
int get(int l,int r){return get(r)-get(l-1);}
int32_t main(){
	int n;
	cin>>n;
	forn(i,n){
		cin>>a[i].a>>a[i].b>>a[i].c;
		a[i].c*=-1;
	}
	sort(a,a+n,compxminusinf);
	forn(i,n)a[i].i=i;
	double ansx,ansy;
	int all=n*(n-1)/2;
	{
		double l=-2e8,r=2e8;
		forn(it,60){
			double m=(l+r)/2;
			curx=m;
			sort(a,a+n,compy);
			memset(t,0,sizeof t);
			int inv=0;
			forn(i,n){
				inv+=get(a[i].i);
				add(a[i].i,1);
			}
			if(inv>=(all+1)/2)r=m;
			else l=m;
		}
		ansx=l;
	}
	sort(a,a+n,compyminusinf);
	forn(i,n)a[i].i=i;
	{
		double l=-2e8,r=2e8;
		forn(it,60){
			double m=(l+r)/2;
			cury=m;
			sort(a,a+n,compx);
			memset(t,0,sizeof t);
			int inv=0;
			forn(i,n){
				inv+=get(a[i].i);
				add(a[i].i,1);
			}
			if(inv>=(all+1)/2)r=m;
			else l=m;
		}
		ansy=l;
	}
	cout<<ansx<<' '<<ansy<<'\n';
    return 0;
}

Measured memory_bytes: 4568
a = [list(input().split()) for _ in range(3)]
check = [[0,0,0] for _ in range(3)]
n = int(input())
b = [] * n
for _ in range(n):
    c = input()
    b.append(c)
#
for i in range(n):
    for y in range(3):
        if b[i] in a[y]:
            check[y][a[y].index(b[i])] = 1
ans = 'No'
for k in range(3):
    if check[k][0] * check[k][1] * check[k][2] == 1:
        ans = 'Yes'
        break
    elif check[0][k] * check[1][k] * check [2][k] ==1:
        ans = 'Yes'
        break
if check[0][0] * check[1][1] * check[2][2] == 1 or check[0][2] * check[1][1] * check[2][0] == 1:
    ans = 'Yes'
print(ans)


Measured memory_bytes: 3064
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    ds = [int(x) for x in input().split()]

    ds.sort()

    n = N//2 - 1
    if ds[n] >= ds[n+1]:
        print(0)
        return
    print(ds[n+1]-ds[n])


# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc132","c",main)

Measured memory_bytes: 14556
k, n = map(int, input().split())
a_lis = list(map(int, input().split()))
a_lis = sorted(a_lis)
longest = 0
for i in range(n):
    if i != n-1:
        longest = max(longest, abs(a_lis[i+1]-a_lis[i]))
    else:
        longest = max(longest, abs(a_lis[n-1]-(a_lis[0]+k)))
print(k - longest)

Measured memory_bytes: 26444
N = int(input())


def f(v):
    if v % 2 == 1:
        return 0
    else:
        return f(v // 2) + 1


v = 1
cnt = 0
for i in range(2, N + 1):
    if f(i) > cnt:
        cnt = f(i)
        v = i
print(v)


Measured memory_bytes: 2940
#AGC024-B Backfront
"""
ある一要素を選んで数列の先頭もしくは最後尾に移動させる。
これを繰り返して昇順に並び替えるときの最小手数
解法：
O(N)で求める必要があるので、シュミレーション的な解法ではない。
増加部分列のうち、その増加分が1である制約を加えた場合の
部分列の長さをlとした時、
n-lが答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
for i in range(n):
    lst1.append(int(readline())-1)

lst2 = [0]*n
for i in range(n):
    lst2[lst1[i]] = i 
#lst2にlst1でのindex(場所)を保存した場合、
#左右の２要素について、右の要素が左より大きければ、
#その2要素については連続でその昇順に存在していることがわかる
#print(lst1)
#print(lst2)

ans = 0
res = 1
for i in range(1,n):
    if lst2[i] > lst2[i-1]:
        res += 1
    else:
        ans = max(ans,res)
        res = 1

ans = max(ans,res)
print(n-ans)

Measured memory_bytes: 47064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a =sc.nextInt();
        int b =sc.nextInt();
        int c =sc.nextInt();
        int d =sc.nextInt();
        int taka = c / b;
        if (c % b != 0) {
            taka++;
        }
        int ao = a / d;
        if (a % d != 0) {
            ao++;
        }
        
        if (taka <= ao) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35704
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
const ll M=1000000007;
//------------------------------------------//

int main(){
    ll X;cin>>X;
    ll ans=0;
    rep(i,45000){
        ans+=i;
        if(ans>=X){
            cout<<i<<endl;
            return 0;
        }
    }
}
    

Measured memory_bytes: 3564
#include <iostream>
using namespace std;
class Sq{
public: int x,y;
};

int main(){
  int N;
  int n,d;
  Sq sq[200];

  while( true ){
    cin >> N;
    if( !N ) break;

    sq[0].x=0; sq[0].y=0;
    int xmin=0,ymin=0, xmax=0,ymax=0;
    for( int i=1;i<N;i++ ){
      cin >> n >> d;
      sq[i].x=sq[n].x; sq[i].y=sq[n].y;      
      if( d==0 ) sq[i].x--;
      else if( d==1 ) sq[i].y--;
      else if( d==2 ) sq[i].x++;
      else sq[i].y++;

      if( xmin>sq[i].x ) xmin=sq[i].x;
      else if( xmax<sq[i].x ) xmax=sq[i].x;
      else if( ymin>sq[i].y ) ymin=sq[i].y;
      else if( ymax<sq[i].y ) ymax=sq[i].y;
    }
    cout << (xmax-xmin+1) << " "<<(ymax-ymin+1)<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

// 入力
int N, K;
long long h[100010];

// DPテーブル
long long dp[100010];

int main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> h[i];

  for (int i = 0; i < 100010; i++) dp[i] = INF;
  dp[0] = 0;

  for (int i = 0; i < N; i++) {
    for (int k = 1; k <= K; k++) {
      chmin(dp[i+k], dp[i] + abs(h[i] - h[i+k]));
    }
  }

  cout << dp[N-1] << endl;
}


Measured memory_bytes: 1792
Xd, K, D = map(int,input().split())
X = abs(Xd)

if X > K*D or abs(X-K*D)<=D:
    print(abs(X-K*D))
    exit()

if (K - Xd//D)%2==0:
    print(Xd%D)
else:
    print(abs(Xd%D-D))


Measured memory_bytes: 9116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

const ll mod=1e9+7;

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    sort(begin(s),end(s));
    sort(begin(t),end(t),greater<char>());
    if(s<t){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#if 1
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

#define LOADVECTOR(type,name,N) std::vector<type>name(N); \
for (i64 nnn = 0; nnn < N; ++nnn) { \
	cin >> name[nnn]; \
}

#define LOAD(type,name) type name; \
cin >> name;


struct Edge {
	i64 e0, e1;
};

class UnionFind {
	vector<i64> data;
public:
	UnionFind(i64 sz) {
		data.assign(sz, -1);
	}
	bool unite(i64 x, i64 y) {
		x = root(x), y = root(y);
		if (x == y) return false;
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return true;
	}
	i64 root(i64 k) {
		if (data[k] < 0) return k;
		return (data[k] = root(data[k]));
	}
	bool same(i64 k0, i64 k1) {
		return root(k0) == root(k1);
	}
	i64 size(i64 k) {
		return (-data[root(k)]);
	}
};


int main() {
	ios::sync_with_stdio(false);
	LOAD(i64, N);
	LOAD(i64, M);
	std::vector<Edge> edges(M);
	for (i64 m = 0; m < M; ++m) {
		cin >> edges[m].e0;
		cin >> edges[m].e1;
		--edges[m].e0;
		--edges[m].e1;
	}
	std::vector<i64> res(M);
	//
	UnionFind uf(N);
	i64 ans = N * (N - 1) / 2;
	for (i64 m = M - 1; m >= 0; --m) {
		res[m] = ans;
		if (!uf.same(edges[m].e0, edges[m].e1)) {
			ans -= 1LL * uf.size(edges[m].e0)*uf.size(edges[m].e1);
			uf.unite(edges[m].e0, edges[m].e1);
		}
	}
	for (i64 m = 0; m < M; ++m) {
		cout << res[m] << endl;
	}
	return 0;
}
#endif


Measured memory_bytes: 4480
#include <cstdio>

static const int maxn = 1000000 + 10;
int n, a[maxn], m, G[maxn];

void get_step(){
    if (n <= 3) {
        m = 1;
        G[0] = 1;
        return;
    }
    G[0] = n / 2;
    for (m = 1; m < n; m++) {
        G[m] = G[m-1] / 2;
        if (G[m] == 1)
            break;
    }
    m++;
}

void _out1(){
    printf("%d\n", m);
    for (int i = 0; i < m-1; i++)
        printf("%d ", G[i]);
    printf("%d\n", G[m-1]);
}

int insertionSort(int g){
    int cnt = 0, v, j;
    for (int i = g; i < n; i++) {
        v = a[i];
        j = i - g;
        while (j >= 0 && a[j] > v) {
            a[j+g] = a[j];
            j = j - g;
            cnt++;
        }
        a[j+g] = v;
    }
    return cnt;
}

int shellSort(){
    int cnt = 0;
    for (int i = 0; i < m; i++)
        cnt += insertionSort(G[i]);
    return cnt;
}

void _out2(){
    for (int i = 0; i < n; i++)
        printf("%d\n", a[i]);
}

int main(){
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    while(scanf("%d", &n) == 1){
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        get_step();
        _out1();
        printf("%d\n", shellSort());
        _out2();
    }
    return 0;
}



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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
vector<int>v;
int main()
{
   int n;
   cin>>n;
   n=!n;
cout<<n;

}


Measured memory_bytes: 3588