akhauriyash/Code-Regression huggingface dataset:
// May this submission get accepted!

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) do { cerr << "[DEBUG] " #q ": ["; REP(i, (q).size()) { cerr << (q)[i] << (i == i_len-1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; } while (false)
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
#define CHOKUDAI_ const
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using cll = DANCE_ DANCE_ CHOKUDAI_;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll n; cin >> n;
    string s; cin >> s;

    // clock_t st = clock();

    ll ans = 0;
    REP(i, n) {
        ll len = 0, index = 0, jndex = 0;
        REP(j, n-i) {
            bool okay = s[j] == s[j+i];
            if (okay) {
                if (len == 0) {
                    index = j;
                    jndex = j+i;
                }
                len++;
            }
            if (!okay || j==j_len-1) {
                chmax(ans, min(i, len));
            }
            if (!okay) {
                len = 0;
            }
        }
    }
    // DUMP((double)(clock() - st) / CLOCKS_PER_SEC);
    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int board[3][3];

int main(){
	char c;
 	while(cin >> c){
		
		if(c == '0'){
			return 0;
		}
		
		//テ、ツスツソテァツ板ィテ」ツδ愿」ツδシテ」ツδ嘉」ツつ?テ」ツ?ァテ・ツ按敕ヲツ慊淌・ツ個?
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				board[i][j] = 0;
			}
		}
		
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(c == 'b'){
					board[i][j] = 1;
				}else if(c == 'w'){
					board[i][j] = -1;
				}
				if((i == 2) && (j == 2)){
				}else{
					cin >> c;
				}
			}
		}
		
		/*
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				cout << board[i][j] << " ";
			}
			cout << endl;
		}*/
		
		int n=0;
		for(int i=0;i<3;i++){
			if((board[i][0] == board[i][1]) && (board[i][0] == board[i][2])){
				if(board[i][0] == 1){
					cout << "b" << endl;
					n = 1;
				}else if(board[i][0] == -1){
					cout << "w" << endl;
					n = 1;
				}
			}
		}
		for(int j=0;j<3;j++){
			if((board[0][j] == board[1][j]) && (board[0][j] == board[2][j]) && (n != 1)){
				if(board[0][j] == 1){
					cout << "b" << endl;
					n = 1;
				}else if(board[0][j] == -1){
					cout << "w" << endl;
					n = 1;
				}
			}
		}
		if((board[1][1] == board[0][0]) && (board[1][1] == board[2][2]) && (n != 1)){
			if(board[1][1] == 1){
				cout << "b" << endl;
				n = 1;
			}else if(board[1][1] == -1){
				cout << "w" << endl;
				n = 1;
			}
		}
		if((board[1][1] == board[0][2]) && (board[1][1] == board[2][0]) && (n != 1)){
			if(board[1][1] == 1){
				cout << "b" << endl;
				n = 1;
			}else if(board[1][1] == -1){
				cout << "w" << endl;
				n = 1;
			}
		}
		if(n == 0){
			cout << "NA" << endl;
		}
	}
		
		return 0;
}

Measured memory_bytes: 1136
N, L = map(int, input().split())
A = []
s = 0
for i in range(N):
    A.append(L + i)
    s += L + i

mi = float('inf')
t = 0
for i in range(N):
    tmp = 0
    for j in range(N):
        if i != j:
            tmp += A[j]

    if abs(tmp - s) < mi:
        mi = abs(tmp - s)
        t = tmp


print(t)


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

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define sz(s) (int)s.size()

int main() {
    unordered_map<int, int> odd, even;
    int n;
    cin >> n;
    rep(i, 0, n) {
        int x;
        cin >> x;
        if (i & 1) odd[x]++;
        else even[x]++;
    }
    int half = n / 2;
    map<int, vector<int>> a, b;
    for (auto it : odd) a[it.second].push_back(it.first);
    for (auto it : even) b[it.second].push_back(it.first);
    if (a.rbegin()->second.size() > 1 || b.rbegin()->second.size() > 1) {
        cout << half - a.rbegin()->first + half - b.rbegin()->first;
        return 0;
    }
    if (a.rbegin()->second[0] != b.rbegin()->second[0]) {
        cout << half - a.rbegin()->first + half - b.rbegin()->first;
        return 0;
    }

    int ans = int(1e9);
    if (a.size() > 1) {
        auto it = next(a.rbegin());
        ans = min(ans, half - it->first + half - b.rbegin()->first);
    }

    if (b.size() > 1) {
        auto it = next(b.rbegin());
        ans = min(ans, half - it->first + half - a.rbegin()->first);
    }

    if (a.size() == 1 && b.size() == 1) ans = min(ans, half);
    cout << ans << '\n';
}

Measured memory_bytes: 5016
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "]"; return os; }


// import here

LL countDigit(LL v){
    LL ans = 0;
    while(v > 0){
        ans += v % 10;
        v /= 10;
    }
    return ans;
}

int main(){
    LL n;
    cin >> n;
    LL ans = 100000;
    for(LL a = 1; a <= n/2; ++a){
        LL b = n - a;
        LL total = countDigit(a) + countDigit(b);
        ans = min<LL>(ans, total);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
import java.io.PrintWriter

val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val (c11, c12, c13) = next().toList()
    val (c21, c22, c23) = next().toList()
    println(if (c11 == c23 && c12 == c22 && c13 == c21) "YES" else "NO")
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun listOfString() = next().split(" ")
fun listOfInt()= listOfString().map { it.toInt() }

fun println(value : Any) {
    pw.println(value)
}

Measured memory_bytes: 31860
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
# @lru_cache(None)






n,m=l()
if not (n==m or n+1==m or n==m+1):
    print(0)
    exit()
nf=1
mf=1
for i in range(1,n+1):
    nf=(nf*i)%mod
for i in range(1,m+1):
    mf=(mf*i)%mod
if(m==n):
    mf*=2
print((mf*nf)%mod)


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

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int a, b;

int main(){
  cin >> a >> b;
  cout << 6 - a - b <<endl;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int x, y;
  cin >> x >> y;

  if ( y % 2 == 1) {
    cout << "No" << endl;
    return 0;
  }

  if ( x * 2 <= y && y <= x * 4) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;

}


Measured memory_bytes: 3588
n = int(input())
r = [int(input()) for i in range(n)]
start = r[0]
score = r[1] - r[0]
for i in range(1,n):
    if r[i] - start > score: score = r[i] - start
    if r[i] < start: start = r[i]
print(score)


Measured memory_bytes: 13592
#include<iostream>
#include<cstdio>
#include<cstring>
template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}
namespace fucker
{
	typedef long long ll;
	const int N=100100,M=N*2;
	int begin[N],next[M],to[M],w[M];
	int col[N];
	int n,m,e;
	ll ans;
	void add(int x,int y,int z=1,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		w[e]=z;
		if(k)add(y,x,2,0);
	}
	void initialize()
	{
		read(n),read(m);
		for(int u,v;m--;)
			read(u),read(v),add(u,v);
	}
	int cnt[3],tmp;
	bool dfs(int p)
	{
		cnt[col[p]]++;

		bool ret=1;
		for(int i=begin[p],q;i;i=next[i])
		{
			q=to[i],tmp++;

			if(col[q]>=0) {ret&=(col[q]==((col[p]+w[i])%3));continue;}
			col[q]=(col[p]+w[i])%3;
			ret&=dfs(q);
		}
		return ret;
	}
	void solve()
	{
		initialize();
		for(int i=1;i<=n;i++)col[i]=-1;

		ans=0;
		for(int i=1;i<=n;i++)
			if(col[i]<0)
			{
				tmp=cnt[0]=cnt[1]=cnt[2]=col[i]=0;
				if(dfs(i))
				{
					if(cnt[0] && cnt[1] && cnt[2])
						ans+=(ll)cnt[0]*cnt[1]+(ll)cnt[1]*cnt[2]+(ll)cnt[0]*cnt[2];
					else ans+=tmp/2;
				}
				else ans+=(ll)(cnt[0]+cnt[1]+cnt[2])*(cnt[0]+cnt[1]+cnt[2]);
			}

		printf("%lld\n",ans);
	}
}
int main()
{
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	fucker::solve();
	return 0;
}


Measured memory_bytes: 8064
#include <iostream>

using namespace std;

int main()
{
    int x[200];
    int i,r,d;
    cin>>r>>d>>x[0];
    for (i=0;i<10;i++){
        x[i+1]=(r*x[i])-d;
        cout<<x[i+1]<<endl;}
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>


#define i_cin(X) scanf("%d", &X)
#define i_cin2(X,Y) scanf("%d %d",&X,&Y)
#define i_cin3(X,Y,Z) scanf("%d %d %d",&X,&Y,&Z)
#define l_cin(X) scanf("%ld",&X)
#define f_cin(X) scanf("%f",&X)
#define l_cin2(X,Y) scanf("%ld %ld",&X,&Y)
#define s_cin(X) scanf("%s",&X)

#define  i_cout(X) printf("%d\n",X)
#define  f_cout(X) printf("%g\n",X)
#define  i_cout2(X,Y) printf("%d %d\n",X,Y)
#define  l_cout(X) printf("%ld\n",X)
#define  s_cout(X) printf("%s\n",X)
#define  ll_cout(X) printf("%lld\n",X)

typedef long long  ll;
#define rept(x, s, n) for (int x = s; x < n; x++)

#define Yes_RTN s_cout("Yes");return 0
#define No_RTN  s_cout("No");return 0
#define YES_RTN s_cout("YES");return 0
#define NO_RTN  s_cout("NO");return 0


int i_cins(int n, int* A);
int l_cins2(int n, long* A,long* B);
int s_dsort(const void* a, const void* b);
int s_asort(const void* a, const void* b);

int  _gcd(int a, int b);

int s_asorts(const void* a, const void* b);


int main(void) {
	int tmp,n;
	char A[4], B[4], TMP[7];
	memset(TMP, 0x00, sizeof(TMP));

	s_cin(A); tmp = strlen(A);
	s_cin(B);
	memcpy(TMP, A, tmp);
	memcpy(&TMP[tmp], B, strlen(B));
	n = atoi(TMP);

	tmp = (int)sqrt(n);
	if (n == tmp * tmp) { Yes_RTN; }
	No_RTN;
}
	
//昇順
int s_asorts(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}
	
int s_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int s_asort(const void* a, const void* b) {
	return(*(int*)a -*(int*)b);
}
int l_cins2(int n, long* a, long* b) {
	int i;
	rept(i, 0, n) {
		l_cin2(*(a + i), *(b + i));
	}
	return 0;
}
int i_cins(int n, int* a) {
	int i;
	for (i = 0; i < n; i++) {
		i_cin(*(a + i));
	}

	return 0;
}

int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(int i=s;i<n;i++)
 
int main()
{
  int N;
  cin >> N;
  int ac=0,re=0,tle=0,wa=0;
  string str;
  rep(i,0,N){
    cin >> str;
    if(str=="AC")
      ac++;
    if(str=="RE")
      re++;
    if(str=="TLE")
      tle++;
    if(str=="WA")
      wa++;
  }
   cout << "AC x " << ac <<endl;
  cout << "WA x " << wa << endl;
  cout << "TLE x " <<tle << endl;
  cout << "RE x " <<re << endl;
}

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

int main(){

	int n;
	for(cin >> n;n > 0;--n){
		int a, b, c, t;
		cin >> a >> b >> c;
		if(a>b && a>c){t=a;a=c;c=t;}
		if(a<b && b>c){t=b;b=c;c=t;}
		if(a*a + b*b == c*c)cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

Measured memory_bytes: 1116
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll= long long;
using ld= long double;
using vi= vector<int>;
using vl= vector<ll>;
using vd= vector<ld>;
using vs= vector<string>;
using vb= vector<bool>;
using vvi= vector<vector<int>>;
using vvl= vector<vector<ll>>;
using vvd= vector<vector<ld>>;
using vvs= vector<vector<string>>;
using vvb= vector<vector<bool>>;
using pll= pair<ll, ll>;
constexpr ll mod= 1e9 + 7;
#define ALL(x) (x).begin(), (x).end()
#define _overload(_1, _2, _3, name, ...) name
#define REPBASE(i, a, b) for(ll(i)= (a); (i) < (b); (i)++)
#define RREPBASE(i, a, b) for(ll(i)= (a); (i) >= (b); (i)--)
#define REPB(i, n) REPBASE(i, 0, n)
#define REPS(i, n) REPBASE(i, 1, n + 1)
#define RREP(i, n) RREPBASE(i, n - 1, 0)
#define RREPS(i, n) RREPBASE(i, n, 1)
#define REP(...) _overload(__VA_ARGS__,REPBASE,REPB)(__VA_ARGS__)
#define EACH(x,c) for(auto& x : c)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())
#define YES(n) ((n) ? "YES" : "NO")
#define Yes(n) ((n) ? "Yes" : "No")
#define yes(n) ((n) ? "yes" : "no")
#define SZ(x) ((ll)(x).size())
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 op(int a, int b) { return max(a, b); };
    int e() { return (int)(0); };

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    int N, K;
    cin >> N >> K;
    vi A(N);
    EACH(x,A)cin >> x;
    segtree<int, op, e> seg(300001);
    EACH(x,A){
        seg.set(x, seg.prod(max(0, x - K), min(300001, x + K + 1)) + 1);
    }
    cout << seg.all_prod() << "\n";
}

Measured memory_bytes: 9812
N = int(input())
v = list(map(int,input().split()))
vo = dict({})
ve = dict({})
for i,e in zip(v[0::2],v[1::2]):
    if i in ve :
        ve[i] += 1
    else:
        ve[i] = 1
    if e in vo :
        vo[e] += 1
    else:
        vo[e] = 1
if len(vo)==1 and len(ve)==1:
    if v[0]!=v[1]:
        print(0)
    else:
        print(N//2)
else:
    vo = sorted([(i,vo[i]) for i in vo.keys()], key = lambda x:x[1], reverse = True)
    ve = sorted([(i,ve[i]) for i in ve.keys()], key = lambda x:x[1], reverse = True)
    if vo[0][0]!=ve[0][0]:
        print(N-vo[0][1]-ve[0][1])
    else:
        print(N-max(vo[0][1]+ve[1][1],vo[1][1]+ve[0][1]))

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

int a[100001];
long long sum[100001], possum[100001];



int main(void) {
	int N, K, cnt = 0;
	cin >> N >> K;

	sum[0] = possum[0] = 0;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
		sum[i] = a[i] + sum[i-1];
		possum[i] = std::max(0, a[i]) + possum[i-1];
	}

	long long ans = 0;
	for (int i = 1; i <= N-K+1; i++) {
		ans = std::max(ans, possum[i-1] + possum[N] - possum[i+K-1]); // paste white
		ans = std::max(ans, possum[i-1] + possum[N] - possum[i+K-1] + sum[i+K-1] - sum[i-1]); // paste black
	}
	
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 2176
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node { int p, l, r; };
struct Node T[MAX];
int n;

void preParse(int u) {
	if (u == NIL)return;
	printf(" %d",u);
	preParse(T[u].l);
	preParse(T[u].r);
}

void inParse(int u) {
	if (u == NIL)return;
	inParse(T[u].l);
	printf(" %d",u);
	inParse(T[u].r);
}

void postParse(int u) {
	if (u == NIL)return;
	postParse(T[u].l);
	postParse(T[u].r);
	printf(" %d",u);
}

int main() {
	int i, v, l, r, root;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		T[i].p = NIL;
	}

	for (i = 0; i < n; i++) {
		scanf("%d %d %d ", &v, &l, &r);
		T[v].l = l;
		T[v].r = r;
		if (l != NIL)T[l].p = v;
		if (r != NIL)T[r].p = v;
	}

	for (i = 0; i < n; i++)if (T[i].p == NIL)root = i;

	printf("Preorder\n");
	preParse(root);
	printf("\n");
	printf("Inorder\n");
	inParse(root);
	printf("\n");
	printf("Postorder\n");
	postParse(root);
	printf("\n");

	return 0;
}


Measured memory_bytes: 2076
n, d = map(int, input().split())
xy = [0]*n
for i in range(n):
  xy[i] = list(map(int, input().split()))
  
def judge(x, y):
  return (((x**2 + y**2)**0.5))

cnt = 0
for i in range(n):
  dis = judge(xy[i][0], xy[i][1])
  if dis <= d:
    cnt += 1
    
print(cnt)

Measured memory_bytes: 45716
#include<bits/stdc++.h>
using namespace std;
    int main(){
        char a, b, c, d, e, f;
            cin >> a >> b >> c >> d >> e >> f;
                if(a == f && b == e && c == d){
                    cout << "YES" << endl;
                }else{
                    cout << "NO" << endl;
                }
    return 0;}

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

using namespace std;

int main(){
    
     long long int a,b,k;

    cin>>a>>b>>k;

    if(a == 0 && b == 0) cout<<0<< " " << 0 <<"\n";
    else{
        if(a-k<=0 && b +a-k >0 ) cout<< 0 << " "<< b+a-k<<"\n";
        else if(a-k<=0 && b+a-k <= 0) cout<< 0 << " "<< 0<<"\n";
        else if(a-k>0) cout<<a-k<< " "<< b <<"\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
int d[500050],f[500050],p[500050],n,q,i;
main(){scanf("%d%d",&n,p);for(i=1;i<=n;++i)scanf("%d",d+i),p[i]=(p[i-1]>=d[i]?p[i-1]-d[i]:(d[i]-p[i-1]<p[i-1]?d[i]-p[i-1]:p[i-1]));f[n+1]=1;for(i=n;i;--i)f[i]=(d[i]>=f[i+1]*2?f[i+1]:d[i]+f[i+1]);scanf("%d",&q);while(q--){scanf("%d",&i);puts(p[i-1]>=f[i+1]?"YES":"NO");}}

Measured memory_bytes: 7680
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#undef min
#undef max
#else
#define NDEBUG
#include <bits/stdc++.h>
#endif

using namespace std;
using large = long long;
constexpr auto mod = 1'000'000'007;

static array<array<int, 13>, 100'005> dp;

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

    dp[0][0] = 1;

    const auto n = int(s.length());
    for (auto i = 0; i < n; ++i) {
        fill(dp[i + 1].begin(), dp[i + 1].end(), 0);

        auto low = 0, high = 9;
        if (s[i] != '?')
            low = high = s[i] - '0';

        for (auto d = low; d <= high; ++d) {
            for (auto rem = 0; rem < 13; ++rem) {
                auto x = (rem * 10 + d) % 13;
                dp[i + 1][x] += dp[i][rem];
                dp[i + 1][x] %= mod;
            }
            continue;
        }
    }
    cout << dp[n][5] << endl;
    return 0;
}


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

int main(void) {
  char s[11] = {0};
  char t[11] = {0};
  scanf("%s", s);
  scanf("%s", t);
  int len = strlen(s);
  int i;
  for(i = 0;i < len;i++) {
    if(s[i] != t[i]) break;
  }
  puts(i == len ? "Yes" : "No");
  
  return 0;
}

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

int f(int x) {
  int y = 0;
  while (x != 0) {
    y += x % 10;
    x /= 10;
  }
  
  return y;
}

int main() {
  int N;
  cin >> N;
  int ans = 1e9;
  for (int i = 1; i < N; i++) ans = min(ans,f(i) + f(N-i));
  cout << ans << endl;
}

Measured memory_bytes: 256
# 2020/07/24
# AtCoder Regular Contest 098 - C

# Input
n = int(input())
s = input()

# Init
acme = list()
acmw = list()
acme.append(0)
acmw.append(0)
ans = n+1

# Make accumed list
for i in range(n):
    if s[i] == 'E':
        acme.append(acme[i] + 1)
        acmw.append(acmw[i])
    elif s[i] == 'W':
        acme.append(acme[i])
        acmw.append(acmw[i] + 1)

acme.append(acme[n])
acmw.append(acmw[n])

# Calc
for i in range(1, n+1):
    ecnt = acme[n] - acme[i]
    wcnt = acmw[i-1]
    wcnt = ecnt + wcnt
    ans = min(ans, wcnt)

# Output
print(ans)

Measured memory_bytes: 23432
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
const int MOD = (int)1e9 + 7;

// EnumerativeSemiring
template<class T> using Rig = pair<T, long long>;
template<class T> Rig<T> add(Rig<T> a, Rig<T> b) {
    if (a.first != b.first) return min(a, b);
    return Rig<T>(a.first, (a.second + b.second) % MOD);
}
template<class T> Rig<T> mul(Rig<T> a, Rig<T> b) {
    return Rig<T>(a.first + b.first, a.second * b.second % MOD);
}

using edge = pair<int, long long>;
using Graph = vector<vector<edge>>;

template<typename T>
vector<Rig<T>> dijkstra(const vector<vector<pair<int, T>>> &g, int s) {
    const T INF = numeric_limits<T>::max();
    vector<Rig<T>> dp(g.size(), Rig<T>(INF, 0));
    vector<bool> done(g.size());
    using P = pair<T, int>;
    priority_queue<P, vector<P>, greater<P>> que;
    dp[s] = Rig<T>(0, 1); que.emplace(0, s);
    while (!que.empty()) {
        int u = que.top().second; que.pop();
        if (done[u]) continue;
        done[u] = true;
        for (auto &e: g[u]) {
            int v; T c; tie(v, c) = e;
            dp[v] = add(dp[v], mul(dp[u], Rig<T>(c, 1)));
            que.emplace(dp[v].first, v);
        }
    }
    return dp;
}

int main() {
    int n, m; cin >> n >> m;
    int s, t; cin >> s >> t; s--, t--;
    Graph g(n);
    while (m--) {
        int u, v, d; cin >> u >> v >> d; u--, v--;
        g[u].emplace_back(v, d);
        g[v].emplace_back(u, d);
    }
    auto dp_s = dijkstra(g, s);
    auto dp_t = dijkstra(g, t);
    #define distS(v) dp_s[v].first
    #define patS(v) dp_s[v].second
    #define distT(v) dp_t[v].first
    #define patT(v) dp_t[v].second
    #define sq(x) ((x) * (x) % MOD)
    long long all = sq(patS(t));
    long long bad = 0;
    long long d = distS(t);
    for (int u = 0; u < n; u++) {
        if (distS(u) + distT(u) == d && distS(u) == distT(u)) {
            bad += sq(patS(u) * patT(u) % MOD);
            bad %= MOD;
        }
    }
    for (int u = 0; u < n; u++) for (auto &e: g[u]) {
        int v; long long c; tie(v, c) = e;
        if (distS(u) + c + distT(v) != d) continue;
        if (distS(u) * 2 < d && distT(v) * 2 < d) {
            bad += sq(patS(u) * patT(v) % MOD);
            bad %= MOD;
        }
    }
    cout << (all - bad + MOD) % MOD << endl;
    return 0;
}


Measured memory_bytes: 19144
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a[] = new int[n];
    int temp;
    for (int i=0 ; i<n ; i++) {
      a[i]=sc.nextInt();
    }

    for (int i=0 ; i<n-1 ; i++) {
      for (int j=i+1 ; j<n ; j++) {
        if (a[i] < a[j]) {
          temp=a[i];
          a[i]=a[j];
          a[j]=temp;
        }
      }
    }

    int s=(a[0]-a[n-1]);

    System.out.println(s);
  }
}


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

int main() {
  int a, b;
  cin >> a >> b;
  if (a == b) {
    cout << "Draw" << endl;
  }
  else if (a == 1) {
    cout << "Alice" << endl;
  }
  else if (b == 1) {
    cout << "Bob" << endl;
  }
  else if (a > b) {
    cout << "Alice" << endl;
  }
  else {
    cout << "Bob" << endl;
  }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1000000007;
vl a1(5);
vl sousuu,pat;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
ll solve(ll a,ll x) {
  if(x==0) return 0;
  if(a < 2) return a1[x];
  if(x <= sousuu[a-2]) return solve(a-1,x-1);
  else if(x == sousuu[a-2]+1) return pat[a-2] + 1;
  else if(x >= sousuu[a-1]-1) return pat[a-1];
  else return solve(a-1,x-sousuu[a-2]-2) + pat[a-2] + 1;
}
int main(){
  ll n,x;
  cin >> n >> x;
  sousuu.assign(n,0),pat.assign(n,0);
  sousuu[0] = 5;
  pat[0] = 3;
  a1[0] = 0;
  a1[1] = 1;
  a1[2] = 2;
  a1[3] = 3;
  a1[4] = 3;
  REP(i,n-1) {
    sousuu[i+1] = 2 * sousuu[i] + 3;
    pat[i+1] = 2 * pat[i] + 1;
  }
  cout << solve(n,x-1) << endl;
  
}
 

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#include <cstring>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<ll>> vvll;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;
}
struct io
{
    io()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-9;


int main(void){
    ull a;
    double b;
    cin >> a >> b;
    ull c = b * 100 + 0.1;
    
    cout << (ull)(a * c) /100;
}


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

int n;
struct P {
	double x, y;
};
vector<P> p;

double dist(P a, P b){
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx*dx + dy*dy);
}

double f(double x, double y){
	double res = 0;
	for(int i = 0; i < n; i++){
		res = max(res, dist((P){x, y}, p[i]));
	}
	return res;
}

double g(double x){
	double l = 0, r = 1000;
	for(int i = 0; i < 100; i++){
		double c1 = (l*2+r)/3;
		double c2 = (l+r*2)/3;
		if(f(x, c1) > f(x, c2)) l = c1;
		else r = c2;
	}
	return f(x, l);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	p = vector<P>(n);
	for(int i = 0; i < n; i++){
		cin >> p[i].x >> p[i].y;
	}
	double l = 0, r = 1000;
	for(int i = 0; i < 100; i++){
		double c1 = (l*2+r)/3;
		double c2 = (l+r*2)/3;
		if(g(c1) > g(c2)) l = c1;
		else r = c2;
	}
	double ans = g(l);
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}

Measured memory_bytes: 384
N = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(str(i))
            if i != n // i:
                divisors.append(str(n//i))
    return divisors
group = make_divisors(N)
if len(group) % 2 == 1:
  print(len(str(int(N**0.5))))
else:
  print(max(len(group[len(group) - 2]), len(group[len(group) - 1])))

Measured memory_bytes: 3064
#include<cmath>
#include<cstdio>
using namespace std;
int main() {
	int Q;
	scanf("%d",&Q);
	for(int i=1; i<=Q; i++) {
		long long a,b;
		scanf("%lld %lld",&a,&b);
		long long pr=a*b;
		long long t=sqrt(pr),ans;
		if(t*(t+1)<pr)
			ans=t*2-1;
		else if(t*t==pr) {
			ans=(t-1)*2;
			if(a!=b) ans--;
		} else
			ans=(t-1)*2;
		printf("%lld\n",ans);
	}
	return 0;
}

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

def main():
    input = sys.stdin.readline
    n = int(input())
    Z = []
    W = []
    for _ in range(n):
        x, y = map(int, input().split())
        z = x + y
        w = x - y
        Z.append(z)
        W.append(w)
    Z.sort()
    W.sort()
    print(max(abs(Z[0] - Z[-1]), abs(W[0] - W[-1])))



if __name__ == '__main__':
    main()


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

int main() {
  
  int s;
  cin >> s;
  
  int a = s/100;
  int b = s%100;
  
  int c = 0;
  if (b == 0 || b > 12) c += 1;
  if (a == 0 || a > 12) c += 2;
  
  if (c == 0) cout << "AMBIGUOUS" << endl;
  if (c == 1) cout << "MMYY" << endl;
  if (c == 2) cout << "YYMM" << endl;
  if (c == 3) cout << "NA" << endl;
  
}

Measured memory_bytes: 256
n = int(input())

L11= [0] * 10
L12= [0] * 10
L13= [0] * 10
L21= [0] * 10
L22= [0] * 10
L23= [0] * 10
L31= [0] * 10
L32= [0] * 10
L33= [0] * 10
L41= [0] * 10
L42= [0] * 10
L43= [0] * 10

for i in range(n):
 b,f,r,v = map(int, input().split())
 r -= 1
 if b == 1:
  if f == 1:
   L11[r] += v
  if f == 2:
   L12[r] += v
  if f == 3:
   L13[r] += v
 if b == 2:
  if f == 1:
   L21[r] += v
  if f == 2:
   L22[r] += v
  if f == 3:
   L23[r] += v
 if b == 3:
  if f == 1:
   L31[r] += v
  if f == 2:
   L32[r] += v
  if f == 3:
   L33[r] += v
 if b == 4:
  if f == 1:
   L41[r] += v
  if f == 2:
   L42[r] += v
  if f == 3:
   L43[r] += v

def PV(L):
 for i in range(9):
  print(" "  + str(L[i]), end="")
 print(" " + str(L[9]))

def PL():
 print("#" * 20)

PV(L11)
PV(L12)
PV(L13)
PL()
PV(L21)
PV(L22)
PV(L23)
PL()
PV(L31)
PV(L32)
PV(L33)
PL()
PV(L41)
PV(L42)
PV(L43)

Measured memory_bytes: 7844
//msol2020_b.cpp
//Sun Aug  2 20:38:46 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007
#define rep(i,n) for (int i=0;i<(n);++i)

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

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

	int count = 0;
	while (a>=b){
		b = b*2;
		count++;
	}
	while (b>=c){
		c = c*2;
		count++;
	}

	if (count <= k){
		cout << "Yes" << endl;
	}else {
		cout << "No" << endl;
	}
//	printf("%.4f\n",ans);
}

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

int main()
{   int n,a,b,i,m,k,x,y,c;
    scanf("%d",&n);
    char s[n+1];
    scanf("%s",s);
    scanf("%d",&k);
    for(i=0;i<n;i++){
        if(s[i]==s[k-1]){
            printf("%c",s[i]);
        }else{
            printf("*");
        }
    }

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const ll MOD=10000000007;

int main() {
  int N,M;
  cin >> N >> M;
  priority_queue<int> pq;
  for (int i=0;i<N;i++){
    int x;
    cin >> x;
    pq.push(x);
  }
  for (int i=0;i<M;i++){
    int x=pq.top();
    pq.pop();
    x/=2;
    pq.push(x);
  }
  ll ans=0;
  while(!pq.empty()){
    int x=pq.top();
    ans+=x;
    pq.pop();
  }
  cout << ans << endl;
}

Measured memory_bytes: 1020
(N, Q) = map(int, input().split())
S = input()
my_list = []
for i in range(Q):
    (l, r) = map(int, input().split())
    my_list.append((l, r))

# print("N:", N)
# print("S:", S)
# print("my_list:", my_list)

my_str_list = [0]
count = 0
for i in range(1, len(S)):
    if (S[i] == 'C' and S[i-1] == 'A'):
        count = count + 1
    my_str_list.append(count)
#print(my_str_list)

for i in range(Q):
    (l, r ) = my_list[i]
#    print(l, r)
    ret = my_str_list[r-1] - my_str_list[l-1]
    if (S[l-2] == 'A'):
#        ret = ret - 1
        ret = 0 if ret < 0 else ret
    print(ret)

Measured memory_bytes: 19784
#include<bits/stdc++.h>
// #include"testlib.h"

using namespace std;

#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()

const int MX = (int)5e5 + 10;
const int mod = 998244353;

int main(int argc, char* argv[]){

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);

    // registerGen(argc, argv, 1);

    int n, a, b;
    cin >> n >> a >> b;

    int res = min(a * n, b);

    cout << res << endl;

    return 0;
}

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

const int Max = 333, Mod = 1e9+7;

int n, m, dp[Max][Max][Max];
vector<pair<int, int>> a[Max];

bool check(const int &r, const int &g, const int &b) {
	if ((r == g && r) || (r == b && r) || (g == b && b)) {
		return false;
	}
	int pos = max(max(r, g), b);
	if (pos > n) {
		return false;
	}
	for (auto it = a[pos].begin(); it != a[pos].end(); ++it) {
		int cnt = (r >= it->first) + (g >= it->first) + (b >= it->first);
		if (cnt != it->second) {
			return false;
		}
	}
	return true;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int l, r, x; m--; ) {
		scanf("%d%d%d", &l, &r, &x);
		a[r].push_back({l, x});
	}
	int ans = 0;
	dp[0][0][0] = 1;
	for (int r = 0, pos, cur; r <= n; ++r) {
		for (int g = 0; g <= n; ++g) {
			for (int b = 0; b <= n; ++b) {
				cur = dp[r][g][b];
				if (r == n || g == n || b == n) {
					ans = (ans+cur)%Mod;
				}
				pos = max(max(r, g), b);
				if (check(pos+1, g, b)) {
					dp[pos+1][g][b] = (dp[pos+1][g][b]+cur)%Mod;
				}
				if (check(r, pos+1, b)) {
					dp[r][pos+1][b] = (dp[r][pos+1][b]+cur)%Mod;
				}
				if (check(r, g, pos+1)) {
					dp[r][g][pos+1] = (dp[r][g][pos+1]+cur)%Mod;
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;
 
const int MaxN = (int)1e5 + 10;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int a[MaxN];

int main() {
//	freopen("input.txt", "r", stdin);
//	ios::sync_with_stdio(false); cin.tie(NULL);
	int n;
	scanf("%d", &n);
	int mx = 0, mn = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		mx = max(mx, a[i]);
	}
	mn = mx;
	for (int i = 1; i <= n; ++i) {
		if (mn == mx || abs(2 * a[i] - mx) < abs(2 * mn - mx)) {
			mn = a[i];
		}
	}
	cout << mx << ' ' << mn << '\n';
	return 0;
} 


Measured memory_bytes: 640
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long int64;
inline int64 read(int f = 1, int64 x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
int64 m; 
int n, bit[17], ans;
int main()
{
    m = read();
    while(m) bit[n++] = m%10, m /= 10;
    reverse(bit, bit+n);
    for(int i = 0, j = 0; i < n; ++i) 
        if(bit[i]) ans = max(ans, j+bit[i]-(i < n-1)+(n-i-1)*9), j += bit[i];
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main()
{
	int d=1000000000;
	int a,b,c,a1,b1,c1,i,j;
	scanf("%d %d %d",&a,&b,&c);
	a1=c/1000;
	b1=c/500;
	for(i=0;i<a1+2;i++){
		for(j=b1+1;j>=0;j--){
			if(i*1000+j*500>=c){
				c1=i*a+j*b;
				if(c1<=d) d=c1;
			}
		}
	}
	printf("%d\n",d);
	return 0;
}


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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

struct UFT{
  int * p;
  
  UFT(int N):p(new int[N]){fill(p,p+N,-1);}  
  ~UFT(){delete[] p;}  
  int par(int a)   { if( p[a] >= 0 ){ p[a] = par( p[a] ); return p[a]; } return a;  }
  int size(int a)  { return -p[par(a)]; }
  bool	same(int a, int b) { return par(a) == par(b); }
  void unite(int a, int b){
    a = par(a);  b = par(b);
    if( a == b ) return;
    if( size(a) < size(b) )a^=b^=a^=b;
    p[a] -= size(b);
    p[b] = a;
  }
};


int main(){
  int n,m; cin >> n >> m;
  vector<int> v(n); cin >> v;
  UFT uft(n);
  for(int i = 0; i < m; ++i){
    int x,y; cin >> x >> y; x--; y--;
    uft.unite(x,y);
  }
  int ans = 0;
  vector<set<int>> vs(100010);
  for(int i = 0; i < n; ++i){
    v[i]--;
    if(uft.par(i) == -1){
      if(i == v[i]) ans++;
      continue;
    }
    vs[uft.par(i)].insert(i);
  }
  for(int i = 0; i < n; ++i){
    if(vs[uft.par(i)].find(v[i]) != vs[uft.par(i)].end()) ans++;
  }
  cout << ans << endl;
  return 0;  
}


Measured memory_bytes: 10368
H,W=map(int,input().split())

field=[[-2]*(W+2)]
for _ in range(H):
    field.append([-1] + list(map(int,input().split())) + [-1])
field.append([-1]*(W+2))


result=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if(field[i][j]%2==1):
            if(j!=W):
                field[i][j]-=1
                field[i][j+1]+=1
                result.append([i,j,i,j+1])
            elif(i!=H):
                field[i][j]-=1
                field[i+1][j]+=1
                result.append([i,j,i+1,j])

print(len(result))
for youso in result:
    print(" ".join(list(map(str,youso))))

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

void solve_abc_c() {
	ll n;
	ll ans = 0;

	cin >> n;

	V a(n);
	rep(i, n) {
		cin >> a[i];
	}

	unordered_map<ll, ll> map;
	V s;
	ll val;
	rep(i, n) {
		auto itr = map.find(a[i]);
		if (itr != map.end()) {
			val = map.at(a[i]);
			map.erase(a[i]);
			map.emplace(a[i], val + 1);
		}
		else {
			map.emplace(a[i], 1);
			s.push_back(a[i]);
		}
	}

	sort(ALL(s));

	rep(i, s.size()) {
		if (s[i] > map.at(s[i])) {
			val = map.at(s[i]);
		}
		else {
			val = map.at(s[i]) - s[i];
		}
		ans += val;
	}

	cout << ans << "\n";
}

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

	solve_abc_c();

	return 0;
}

Measured memory_bytes: 5788
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define dpr(x) cerr<<#x<<": "<<x<<endl;
#define dprc(c) do{cerr<<#c<<":";for(auto&_i:(c)){cerr<<" "<<_i;}cerr<<endl;}while(0)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
int INF = 1e9+7;
#define all(c) begin(c), end(c)
#define tr(i,c) for(auto i=begin(c);i!=end(c);i++)
#define rtr(i,c) for(auto i=(c).rbegin();i!=(c).rend();i++)
#define rep(i,b) for(auto i=0;i<(b);i++)
#define pb push_back
#define sz(c) int((c).size())

int n;
vi R;

int main(int argc, char **argv)
{
  int n, minv, maxd;
  cin >> n;
  cin >> minv;
  maxd = -INF;
  for (int i = 1; i < n; i++) {
    int r;
    cin >> r;
    if (r - minv > maxd) maxd = r - minv;
    if (r < minv) minv = r;
  }
  cout << maxd << endl;
  return 0;
}

Measured memory_bytes: 3096
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a;
    cin>>a;
    if(a<1000)cout<<"ABC"<<endl;
    else cout<<"ABD"<<endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

void solve_abc148_d() {
	ll N;
	cin >> N;

	vector<ll> a(N);
	rep(i, N) {
		cin >> a[i];
	}

	ll ans = 0;
	ll cnt = 1;
	rep(i, N) {
		if (a[i] == cnt) {
			cnt++;
		}
	}

	if (cnt == 1) {
		ans = -1;
	}
	else {
		ans = N - cnt + 1;
	}
	
	cout << ans << "\n";
}

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

	solve_abc148_d();

	return 0;
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC046A {
	class Program {
		static void Main(string[] args) {
			string[] input = Console.ReadLine().Split(' ');
			int count = 0;

			for (int i = 1; i < 3; i++) {
				if (input[0] == input[i]) {
					count++;
				}
			}

			if (input[1] == input[2]) {
				count++;
			}

			Console.Write(count == 3 ? 1 : 3 - count);
		}
	}
}

Measured memory_bytes: 2648
#include<bits/stdc++.h>
#define pi 3.14159265358979323846264338327950288
using namespace std;
inline long long read(){
	long long ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
long long X1,Y1,X2,Y2;
long long a[200005],c[200005],n=0,m,len,iter;
struct node{
	long long x,y;
};
node tmp[200005];
bool cmp(node a,node b){
	if (X1>X2){
		return a.x>b.x;
	}
	return a.x<b.x;
}
int main(){
    //freopen("loveround.in","r",stdin);
    //freopen("loveround.out","w",stdout);
	X1=read();Y1=read();X2=read();Y2=read();
	if (Y1>Y2){
		swap(X1,X2);
		swap(Y1,Y2);
	}
	m=read();
	for (long long i=1;i<=m;i++){
		tmp[i].x=read(),tmp[i].y=read();
	}
	sort(tmp+1,tmp+1+m,cmp); 
	for (long long i=1;i<=m;i++){
		if (min(X1,X2)<=tmp[i].x&&tmp[i].x<=max(X1,X2)){
			if (min(Y1,Y2)<=tmp[i].y&&tmp[i].y<=max(Y1,Y2)){
				a[++n]=tmp[i].y;
			}
		}
	}
	c[1]=a[1];
	len=1;
	for (long long i=2;i<=n;i++){
		if (a[i]>c[len]){
			len++,c[len]=a[i];
		}else{
			iter=lower_bound(c+1,c+len,a[i])-c,c[iter]=a[i];
		}
	}
	if (n==0){
		len=0;
	}
	double pre=1.00*(abs(X2-X1)+abs(Y2-Y1));
	double stp=20-pi*5; 
	if (X1==X2||Y1==Y2){
		stp=20-pi*10;
		printf("%.13lf\n",pre*100*1.00-len*1.00*stp);
		return 0;
	}
	if(len==min(abs(X2-X1)+1,abs(Y2-Y1)+1)){
		printf("%.13lf\n",pre*100*1.00-len*1.00*stp+pi*5);
	}else{
		printf("%.13lf\n",pre*100*1.00-len*1.00*stp);
	}
	return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
int main() {
  int k;
  cin >> k;
  long long ans = 0;
  for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) for(int l=1;l<=k;l++) {
    ans += gcd(gcd(i, j), l);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3592
N,K = map(int,input().split())
S = input()

maxHappiness = N-1
nowHappiness = 0
for i in range(N-1):
    if S[i+1] == S[i]:
        nowHappiness += 1
nowHappiness = nowHappiness + 2 * K
print(min(nowHappiness,maxHappiness))

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> nums(N);
    ll hiNum = 0;
    for (int i = 0; i < N; i++)
    {
        ll A;
        cin >> A;
        nums.at(i) = A;
        hiNum = max(hiNum, A);
    }
    ll answer = 0;
    if(K == 0)
    {
        for(int i = 0; i < N; i++)
        {
            answer += nums.at(i);
        }
        cout << answer << endl;
        return 0;
    }
    int aKeta = 0;
    ll tmpHiNum = hiNum;
    while (tmpHiNum)
    {
        tmpHiNum /= 2;
        aKeta++;
    }
    int kKeta = 0;
    ll tmp = K;
    while (tmp)
    {
        tmp /= 2;
        kKeta++;
    }
    //aKetaからkKetaまでをそのまま加算する処理
    ll checkBit = 1LL << (aKeta - 1);
    for (int i = 0; i < aKeta - kKeta; i++)
    {
        for (ll num : nums)
        {
            answer += num & checkBit;
        }
        checkBit = checkBit >> 1;
    }
    //kKetaからのaの各桁のbitを算出
    vector<ll> bitCounts(kKeta); // Kの最大桁の左(大きい順)から0, 1 ,2で1が経っている数(0はN - bitCountで取得)
    checkBit = 1LL << (kKeta - 1);
    for (int i = 0; i < kKeta; i++)
    {
        for (ll num : nums)
        {
            if (num & checkBit)
            {
                bitCounts.at(i)++;
            }
        }
        checkBit = checkBit >> 1;
    }
    vector<vector<ll>> dp(2, vector<ll>(kKeta + 1)); //0が境界、1がそれよりsmallerでの左からi桁まででXORした時の最大値
    checkBit = 1LL << (kKeta - 1);
    //必ず最初はbitが立っている
    dp.at(0).at(1) = (N - bitCounts.at(0)) * checkBit;
    dp.at(1).at(1) = bitCounts.at(0) * checkBit;
    checkBit = checkBit >> 1;
    for (int i = 1; i < kKeta; i++)
    {
        ll bitCount = bitCounts.at(i);
        ll zeroCount = N - bitCount;

        ll hiCount = max(zeroCount, bitCount);
        ll hiSum = hiCount * checkBit;
        if (K & checkBit)
        {
            //1が境界
            dp.at(0).at(i + 1) = dp.at(0).at(i) + zeroCount * checkBit;
            //smallerの方はsmallerのうち、最大の結果を格納
            //(今まで境界から0になったものと、既に境界未満のものから最大で取ったものの大きい方)
            dp.at(1).at(i + 1) = max(dp.at(0).at(i) + bitCount * checkBit, dp.at(1).at(i) + hiSum);
        }
        else
        {
            //0が境界
            dp.at(0).at(i + 1) = dp.at(0).at(i) + bitCount * checkBit;
            //smallerの方はsmallerのうち、最大の結果を格納
            dp.at(1).at(i + 1) = dp.at(1).at(i) + hiSum;
        }
        checkBit = checkBit >> 1;
    }
    answer += max(dp.at(0).at(kKeta), dp.at(1).at(kKeta));
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Negative":" Positive")
	typedef vector<int>
		Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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 long long INFLL = 1LL<<60;
const int INF = 1<<30;// ne(1) po(0)
const double PI=acos(-1);
int main(){
	int a,b;
	bool ans=0;
	cin >>a>>b;
	ans = (min(b+1, 0) - min(0, a)) %2;
	if((a >=0 )^ (b>=0)){
		cout<<"Zero"<<endl;
	}else{
	cout<<solve(ans)<<endl;
}
}

Measured memory_bytes: 256