akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define maxn 100005
using namespace std;
typedef long long ll;
struct nod
{
	ll dis,id;
	nod(ll x,ll y)
	{
		dis=x;
		id=y;
	}
	nod(){}
};
bool operator<(nod a,nod b)
{
	return a.dis>b.dis;
}
int n,m,tot;
int head[maxn],nex[maxn<<2],to[maxn<<2],deg[maxn];
ll val[maxn<<2];
void add(int x,int y,ll z)
{
	to[++tot]=y; val[tot]=z; nex[tot]=head[x]; head[x]=tot;
}
ll dis[maxn];
bool vis[maxn],flag=true;
priority_queue<nod> q;
void spfa(int now)
{
//	q.push(nod(0,start)); dis[start]=0;
//
//	while(!q.empty())
//	{
//		int now=q.top().id; q.pop();
//		if(vis[now]) continue;
//		vis[now]=1;
//
//		for(int i=head[now];i;i=nex[i])
//		{
//			if(dis[to[i]]==-1 || dis[to[i]]>dis[now]+val[i])
//			{
//				dis[to[i]]=dis[now]+val[i];
//				q.push(nod(dis[to[i]],to[i]));
//			}
//		}
//	}
	if(!flag) return;
	if(vis[now]) return;
	vis[now]=1;
	for(int i=head[now];i;i=nex[i])
	{
		if(!vis[to[i]])
		{
			if(dis[to[i]]==-1 || dis[to[i]]!=dis[now]+val[i])
			{
				dis[to[i]]=dis[now]+val[i];
//				vis[to[i]]=1;
				spfa(to[i]);
			}
		}
		else
		{
			if(dis[to[i]]!=dis[now]+val[i])
			{
				flag=false;
				return;
			}
		}
	}
	vis[now]=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y; ll z;
		scanf("%d%d%lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,-z);
	}

	memset(dis,-1,sizeof(dis));

	for(int i=1;i<=n;i++)
		if(dis[i]==-1)
		{
			spfa(i);
			if(!flag)
			return printf("No\n"),0;
		}

	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=nex[j])
		{
			if(dis[to[j]]!=dis[i]+val[j])
			{
				return printf("No\n"),0;
			}
		}
	}

	printf("Yes\n");
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,n,m,j,k,l,o,p;
    cin>>n;
    vector<int>outputvec,v;
    for(i=0;i<n;i++)
    {
        cin>>l;
        v.push_back(l);
        if(i==0)
        {
            outputvec.push_back(l);
        }
        else
        {
            int V=-1;
            int I=0;
            int J=outputvec.size()-1;
            while(I<=J)
            {
                m=(I+J)/2;
                if(outputvec[m] < l)
                {
                    V=m;
                    I=m+1;
                }
                else
                {
                    if(outputvec[m] >= l)
                    {
                        J=m-1;
                    }
                }
            }
            if(V==-1)
            {
                auto it = lower_bound(outputvec.begin(),outputvec.end(),l)-outputvec.begin();
                outputvec.insert(outputvec.begin()+it,l);
            //    cout<<Y<<endl;
               // outputvec.insert(v.begin()+Y,l);
            }
            else
            {
                outputvec[V]=l;
            }
        }
    }
    cout<<outputvec.size();
}

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

int gcd(int a, int b);
int lcd(int a, int b);

int main(){
    int n; cin >> n;
    int a[n]; cin >> a[0];
    int G = a[0];
    for(int i = 1; i < n; i++){
        cin >> a[i];
        if(G < a[i]){
            G = lcd(G,a[i]);
        }else{
            G = lcd(a[i],G);
        }
    }

    cout << G << endl;

    return 0;
}

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

int lcd(int a, int b){
    return a*b/gcd(a,b);
}


Measured memory_bytes: 3088
N = int(input())
a = [int(input()) for i in range(N)]
ch = [0] * (10**5 + 1)
numB = 1
ch[1] = numB
c = 1
while True:
    numB = a[numB-1]
    if numB == 2:
        print(c)
        break
    if ch[numB] == 1:
        print(-1)
        break
    c += 1
    ch[numB] = 1


Measured memory_bytes: 7852
n=int(input())
A,B,C=[sorted(list(map(int,input().split()))) for _ in range(3)]
cnt=0
a,c=0,0
for b in range(n):
	while a<n and A[a]<B[b]:
		a+=1
	while c<n and B[b]>=C[c]:
		c+=1
	if c==n:break
	cnt+=a*(n-c)
print(cnt)

Measured memory_bytes: 24096
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;


int gcd(int a,int b){
  if (a>b) swap(a,b);
  if (a==0) return b;
  return gcd(b%a,a);
}


int main(void){
  int n,m,i;
  ll a[100005];
  set<int> r;
  
  cin >> n >> m;
  for (i=0;i<n;i++){
    cin >> a[i];
    a[i]/=2;
  }
  
  for (i=0;i<n;i++){
    int t=a[i],s=0;
    while (t%2==0){
      t/=2;
      s++;
    }
    r.insert(s);
  }
  
  if (r.size()>1){
    cout << 0 << endl;
    return 0;
  }
  
  ll lcm=1;
  for (i=0;i<n;i++){
    lcm=lcm/gcd(lcm,a[i])*a[i];
    if (lcm>m){
      cout << 0 << endl;
      return 0;
    }
  }
  
  cout << (m+lcm)/(lcm*2) << endl;
  
  return 0;
}

Measured memory_bytes: 1024
import math
a, b, x = map(int, input().split())

if x <= a * a * b / 2:
    c = 2 * x / (a * b)
    ans = math.atan2(b, c)
    ans *= 360 / (2 * math.pi)
else:
    c = 2 * b - 2 * x / (a**2)
    ans = math.atan2(c, a)
    ans *= 360 / (2 * math.pi)

print(ans)


Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}
template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}
constexpr int INF = 1e18;

 struct Doubling {
     const long long LOG;
     const int N;
     vector<vector<int>> nexted;
 
     Doubling(int N, long long log = 60) : N(N), LOG(log) {
         nexted.assign(LOG + 1, vector<int>(N + 1, -1));
     }
 
     inline void set_init_next(const int v, const int x) {
         nexted[0][v] = x;
     }
 
     void build() {
         for (int k = 0; k < LOG; k++) {
             for (int v = 0; v < N; v++) {
                 if (nexted[k][v] == -1) nexted[k + 1][v] = -1;
                 else nexted[k + 1][v] = nexted[k][nexted[k][v]];
             }
         }
     }
 
     inline int query(int v, long long p) {
         for (long long i = LOG; i >= 0; i--) {
             if (v < 0) return -1;
             if (p & (1LL << i)) {
                 v = nexted[i][v];
             }
         }
         return v;
     }
 };

signed main(){
	int N,Q; // 全体の要素
cin >> N >> Q;
int LOG_N = floor(log2(N)); // = floor(log_2(N))
vector<int>a(N);
REP(i,N){
	cin >> a[i];--a[i];
}
	Doubling d(N);
	REP(i,N)d.set_init_next(i,a[i]);
	d.build();
	out(d.query(0,Q) + 1);
}

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin >> A[i];
  }

  vector<int> B(N);
  B = A;
  sort(B.begin(),B.end());
  int max = B[N-1];
  int s_max = B[N-2];

  if(max == s_max){
    for(int i=0; i<N; i++){
      cout << max << endl;
    }
  }else{
    for(int i=0; i<N; i++){
      if(A[i] == max){
        cout << s_max << endl;
      }else{
        cout << max << endl;
      }
    }
  }
}

Measured memory_bytes: 3200
'use strict';
class Queue {
    constructor(size) {
        this.arr = new Array(size);
        this.head = this.tail = 0;
    }
    is_full() {
        return this.head == (this.tail + 1) % this.arr.length;
    }
    push(v) {
        if (this.is_full()) {
            this.arr.length *= 2;
        }
        this.arr[this.tail] = v;
        this.tail = (this.tail + 1) % this.arr.length;
    }
    is_empty() {
        return this.head == this.tail;
    }
    pop() {
        if (this.is_empty()) {
            throw -1;
        }
        let v = this.arr[this.head];
        this.head = (this.head + 1) % this.arr.length;
        return v;
    }
    maxsize() {
        return this.arr.length;
    }
}
function main(input) {
    let lines = input.split('\n');
    let v = lines[0].split(' ').map((n) => parseInt(n));
    let h = v[0];
    let w = v[1];
    let c = [];
    let d = [];
    for (let i = 1; i < h + 1; i++) {
        c.push(lines[i]);
        d.push([]);
    }
    let q = new Queue(1000000);
    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            if (c[i][j] == '#') {
                q.push([i, j]);
                d[i][j] = 0;
            }
            else {
                d[i][j] = -1;
            }
        }
    }
    let p = q.pop();
    let max = 0;
    const dx = [1, 0, -1, 0];
    const dy = [0, 1, 0, -1];
    while (true) {
        const xx = p[0];
        const yy = p[1];
        for (let i = 0; i < 4; i++) {
            let x = xx + dx[i];
            let y = yy + dy[i];
            if (x < 0 || x > h - 1 || y < 0 || w - 1 < y || d[x][y] >= 0) {
                continue;
            }
            if (c[x][y] == '.') {
                q.push([x, y]);
                let count = d[xx][yy] + 1;
                if (max < count) {
                    max = count;
                }
                d[x][y] = count;
            }
        }
        if (q.is_empty()) {
            break;
        }
        p = q.pop();
    }
    console.log(max);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 132800
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <regex>

#define FOR(i, f, n) for(int (i) = (f); (i) < (n); (i)++)
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (n); (i)--)
#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define RREP(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)++)
#define p(...) printf(__VA_ARGS__); cout << endl;
#define in(...) __VA_ARGS__; input__(__VA_ARGS__);
#define input(...) in(__VA_ARGS__)
#define out(...) output__(__VA_ARGS__);
#define output(...) out(__VA_ARGS__)
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](const a, const b){ return c ;}
#define key(t, x, compare) [](const t& a, const t& b){ return a x compare b x ;}

using namespace std;

using pii = pair<int, int>;

template <class... T>
void input__(T &...a) {
  for(auto v: {&a...}) {
    cin >> *v;
  }
}

template <class... T>
void output__(T ...a) {
  for(auto v: {a...}) {
    cout << v << " ";
  }
  cout << endl;
}

int main(){
  int in(a, b) out((a - 1) * (b - 1));
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#include <set>
#include <map>
#include <stack>
#include <iomanip>
#include <tuple>
#define ll long long
using namespace std;
struct all_init
{
    all_init()
    {
        cout << fixed << setprecision(12);
    }
} All_init;


int main()
{
    ll a, b;
    cin >> a >> b;
    string sa="", sb="";
    for (ll i = 0; i < b; i++)
    {
        sa += to_string(a);
    }
    for (ll i = 0; i < a; i++)
    {
        sb += to_string(b);
    }
    cout << min(sa, sb) << endl;
}


Measured memory_bytes: 256
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int h,w,h2,w2;

int main()
{
	cin>>h>>w>>h2>>w2;
	cout<<h*w-h2*w-(w2*h-w2*h2)<<endl;
	rt0;
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<math.h>
#include<numeric>
#include<cassert>
#include<random>
#include<deque>
#include<chrono>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
const ll E=1e18+7;
#define F first
#define S second
#define MK make_pair
const ll MOD=1000000007;

vector<vector<ll>> c;

void mk_c(){
    c.resize(2100);
    for(int i=1;i<2100;i++){
        c[i].resize(2100);
        c[i][0]=1;
        c[i][i]=1;
        for(int t=1;t<i;t++){
            c[i][t]=(c[i-1][t-1]+c[i-1][t])%MOD;
        }
    }
}

int main(){
    ll n,k;
    cin>>n>>k;
    if(n>k){cout<<0<<endl; return 0;}
    mk_c();
    cout<<c[k][n]<<endl;
    
    
    
    
    return 0;
}


Measured memory_bytes: 37424
/* 十 聖イシドールスよ、迷えるプログラマを導き給え！ 十 */
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; i++)
 
//const long long INF = 1LL << 60;
const int INF = 1e9;
using ll = long long;

int main()
{
	int N;
	std::cin >> N;
	std::priority_queue<double, std::vector<double>, std::greater<double>> v;
	rep(i, N)
	{
		double tmp;
		std::cin >> tmp;
		v.push(tmp);
	}

	while(true)
	{
		double a, b;
		a = v.top();
		v.pop();
		b = v.top();
		v.pop();
		v.push((a + b) / 2);

		if(v.size() == 1)
		{
			break;
		}
	}

	std::cout << v.top() << std::endl;

	return 0;
}

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors
divisors = make_divisors(N)
ans = 0
for d in divisors:
    t = d - 1
    if t != 0 and N % t == N // t:
        ans += t
print(ans)


Measured memory_bytes: 39024
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

s = S()
q = I()
# Q = LS(q)

# print(Q)

# a = 'A'
flag = True
r = []
l = []
for i in range(q):
    d = input().split()
    if len(d)==1:
        flag = not flag
    elif d[1]=='1':
        c = d[2]
        if flag:
            l.append(c)
        else:
            r.append(c)
    elif d[1]=='2':
        c = d[2]
        if flag:
            r.append(c)
        else:
            l.append(c)
# print(l)
# print(r)
l = "".join(l[::-1])
r = "".join(r)
ans = l+s+r
if flag:
    print(ans)
else:
    print(ans[::-1])

Measured memory_bytes: 97404
n, k = map(int, input().split())
h_list = list(map(int, [input() for _ in range(n)]))
h_list = sorted(h_list, reverse=True)

min_diff = 10 ** 9
for i in range(n-k+1):
    h_max = h_list[i]
    h_min = h_list[i+k-1]
    h_diff = h_max - h_min
    if min_diff > h_diff:
        min_diff = h_diff
    if min_diff == 0:
        print(0)
        exit()
print(min_diff)

Measured memory_bytes: 14236
def main():
    n, A, B = list(map(int, input().split()))
    S = input()
    a, b = 0, 0
    for s in S:
        if s == 'a':
            if a + b < A + B:
                print('Yes')
                a += 1
            else:
                print('No')
        elif s =='b':
            if a + b < A + B and b < B:
                print('Yes')
                b += 1
            else:
                print('No')
        else:
            print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 51928
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX=100020;
const ll INF=1ll<<62;
ll N,M,A[MAX],B[MAX],Q[MAX],par[MAX],W[MAX],Btot[MAX],chk[MAX];
vector<ll> conn[MAX],rec;
bool cmp(ll x,ll y){
    return A[x]-B[x]<A[y]-B[y];
}
ll fnd(ll x){
    if(par[x]==x) return x;
    return par[x]=fnd(par[x]);
}
ll uni(ll x,ll y){
    x=fnd(x); y=fnd(y);
    if(x==y) return 0;
    par[x]=y; return 1;
}
int main(){
    scanf("%lld%lld",&N,&M);
    for(ll i=1;i<=N;i++) scanf("%lld%lld",&A[i],&B[i]);
    for(ll i=0;i<M;i++){
        ll t1,t2;
        scanf("%lld%lld",&t1,&t2);
        conn[t1].push_back(t2);
        conn[t2].push_back(t1);
    }
    for(ll i=1;i<=N;i++) Q[i]=i,par[i]=i;
    sort(Q+1,Q+1+N,cmp);
    for(ll i=1;i<=N;i++){
        ll cnt=0,idx;
        chk[Q[i]]=1;
        W[Q[i]]=INF;
        for(ll j=0;j<conn[Q[i]].size();j++) if(chk[conn[Q[i]][j]]) {
            idx=fnd(conn[Q[i]][j]);
            if(idx!=Q[i]) rec.push_back(idx), par[idx]=Q[i];
        }
        for(ll j=0;j<rec.size();j++) Btot[Q[i]]+=Btot[rec[j]];
        if(rec.size()==0) W[Q[i]]=max(A[Q[i]],B[Q[i]]);
        else {for(ll j=0;j<rec.size();j++) W[Q[i]]=min(W[Q[i]],Btot[Q[i]]-Btot[rec[j]]+max(A[Q[i]],B[Q[i]]+W[rec[j]]));}
        Btot[Q[i]]+=B[Q[i]];
        rec.clear();
    }
    printf("%lld\n",W[Q[N]]);
}


Measured memory_bytes: 12536
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long x = 1;
		for (int i = 2; i <= n; i++) {
			x = x * i;
		}
		System.out.println(x);
	}
}

Measured memory_bytes: 24060
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			int n = sc.nextInt();
			if(n == 0) break;
			HashMap<String, String> map = new HashMap<String, String>();
			for(int i=0;i<n;i++) map.put(sc.next(), sc.next());
			Strs[] obts = new Strs[2];
			for(int i=0;i<2;i++) obts[i] = new Strs();
			String src = sc.next(), dst = sc.next();
			int cnt = 0; obts[0].add(src);
			boolean ok = false;
			HashSet<String> used = new HashSet<String>(); used.add(src);
			for(;!obts[cnt%2].isEmpty();cnt++) {
//				debug(obts[cnt%2]);
				obts[(cnt+1)%2].clear();
				for(String str: obts[cnt%2]) {
					if(str.equals(dst)) {
						ok = true;
						break;
					}
					for(Map.Entry<String, String> entry: map.entrySet()) {
						String rep = str.replace(entry.getKey(), entry.getValue());
						if(rep.length() <= dst.length() && !used.contains(rep)) {
							obts[(cnt+1)%2].add(rep);
							used.add(rep);
						}
					}
				}
				
				if(ok) break;
			}
			
			System.out.println((ok? cnt:-1));
		}
	}
	
	class Strs extends HashSet<String>{}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 67796
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;


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

	cin >> N;
	R = 0;
	L = 100;
	vector<int>num(200,0);
	for (int i = 0; i < N; i++) {
		cin >> M;
		num[M]++;
		L = min(L, M);
		R = max(R, M);
	}
	if ((R + 1) / 2 != L || (R % 2 && num[L] != 2) || (R % 2 == 0 && num[L] != 1)) {
		cout << "Impossible\n";
		return 0;
	}
	K = num[R];
	for (int i = R; i >= L + 1; i--) {
		if (num[i] <= 1) {
			cout << "Impossible\n";
			return 0;
		}
		K = num[i];
	}
	if (K < num[L]) {
		cout << "Impossible\n";
		return 0;
	}
	cout << "Possible\n";
	return 0;
}


Measured memory_bytes: 256
N,A,B,C=gets.split(/ /).map{|s| s.to_i}
$cmds = []
1.upto(N) do
    $cmds << gets.chomp.to_sym
end

def fun(a,b,c,i)
  cmd=$cmds[i] or return []
  case cmd
  when :AB
    if a >= 1
        if ret = fun(a-1,b+1,c, i+1)
            ret.unshift("B")
            return ret
        end
    end
    if b >= 1
        if ret = fun(a+1,b-1,c, i+1)
            ret.unshift("A")
            return ret
        end
    end
    return nil
  when :BC
    if b >= 1
        if ret = fun(a,b-1,c+1, i+1)
            ret.unshift("C")
            return ret
        end
    end
    if c >= 1
        if ret = fun(a,b+1,c-1, i+1)
            ret.unshift("B")
            return ret
        end
    end
    return nil
  when :AC
    if a >= 1
        if ret = fun(a-1,b,c+1, i+1)
            ret.unshift("C")
            return ret
        end
    end
    if c >= 1
        if ret = fun(a+1,b,c-1, i+1)
            ret.unshift("A")
            return ret
        end
    end
    return nil
  end
end

r = fun(A,B,C,0)
if r
    puts "Yes"
    r.each  {|s| puts s }
else 
    puts "No"
end










Measured memory_bytes: 35372
#include <stdio.h>

int main( void ) {
  int i, n, cnt;
  int a[200];

  scanf( "%d", &n );

  i = 0;
  while ( i <= n ) {
    scanf( "%d", &a[i] );
      i++;
  }

  cnt = 0;
  i = 0;
  while ( (a[i] % 2) == 0 ) {
    a[i] = a[i] / 2;

    if ( i == (n - 1) ) {
      i = 0;
      cnt++;
      continue;
    }
    i++;
  }
  
  printf( "%d\n", cnt );
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
using namespace std;
int main(){
  int A,o;
  string ans;
  cin >> A;
  o = (A % 100)%10;
  if (A/100 == o){
    ans = "Yes";
  }else {
    ans = "No";
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int k;
	scanf("%d", &k);
	int a[40] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
	printf("%d\n", a[k - 1]);
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    ll ans = 1;
    cin >> N;
    rep(i, N) {
        ll temp;
        cin >> temp;
        ans = temp / __gcd(temp, ans) * ans ;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s,t;
  cin>>s>>t;
  if(s.length()!=t.length())
    cout<<"0";
  else
  {//sort(s.begin(),s.end());
   //sort(t.begin(),t.end());
    int c=0;
    for(int i=0;i<s.length();i++)
    {
      if(s[i]!=t[i])
        c++;
    }
   cout<<c;
  }
   cout<<"\n";
}

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

const ll MX = 1e18;

int main() {
  int n;
  cin >> n;
  ll ans = 1;
  bool ng = false;
  rep(i,n) {
    ll a;
    cin >> a;
    if (a == 0) {
      cout << 0 << endl;
      return 0;
    }
    if (ng || __int128(ans)*a > MX) {
      ng = true;
    }
    ans *= a;
  }
  if (ng) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

const int M = 100000;

int n, m;
vector<int> g[M];

bool dfs(int v, int x, int y, int p) {
	if(v == y) { return false; }
	if(v == x && p != -1) { return true; }
	
	bool f = false;
	RF(e, g[v]) {
		if(e == p) { continue; }
		f |= dfs(e, x, y, v);
	}
	
	return f;
}


int main() {
	cin >> n >> m;
	inc(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	
	bool f = true;
	int c6 = 0;
	vector<int> c4;
	inc(i, n) {
		f &= (SI(g[i]) % 2 == 0);
		if(SI(g[i]) == 4) { c4.PB(i); }
		if(SI(g[i]) >= 6) { c6++; }
	}
	
	bool ans = (f && (c6 > 0 || SI(c4) > 2));
	if(f && c6 == 0 && SI(c4) == 2) {
		ans = dfs(c4[0], c4[0], c4[1], -1);
	}
	
	cout << (ans ? "Yes" : "No") << endl;
	
	return 0;
}



Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int A[3][3];
  rep(i, 3) {
    rep(j, 3) {
      cin >> A[i][j];
    }
  }
  int B[3][3]={0};
  int N;
  cin >> N;
  rep(k, N) {
    int b;
    cin >> b;
    rep(i, 3) {
      rep(j, 3) {
        if(A[i][j] == b){
          B[i][j] = 1;
        }
      }
    }
  }
  int flg = 0;
  rep(i, 3) {
    if(B[i][0]==1&&B[i][1]==1&&B[i][2]==1) flg = 1;
    if(B[0][i]==1&&B[1][i]==1&&B[2][i]==1) flg = 1;
  }
  if(B[0][0]==1&&B[1][1]==1&&B[2][2]==1) flg = 1;
  if(B[0][2]==1&&B[1][1]==1&&B[2][0]==1) flg = 1;
  if(flg==1) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

N,M=map(int,input().split())
X=[0 for i in range(M)]
Y=[0 for i in range(M)]
Z=[0 for i in range(M)]
for i in range(0,M):
    X[i],Y[i],Z[i]=map(int,input().split())

u=UnionFindVerSize(N)
for i in range(0,M):
    u.unite(X[i]-1,Y[i]-1)
print(u.calc_group_num())

Measured memory_bytes: 71456
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    int n,m;
    cin>>n>>m;
    if(n%2) rep(i,m) cout<<i+1<<" "<<n-i<<"\n";
    else{
        rep(i,min(m,n/4)) cout<<i+1<<" "<<n/4*2-i<<"\n";
        rep(i,max(0,m-n/4)) cout<<n/4*2+2+i<<" "<<n-i<<"\n";
    }
}

Measured memory_bytes: 3636
#include <stdio.h>
int main(void){
   
   int r, c;
   int i, t;
   int table[1000][1000] = {0};
   
   scanf("%d %d\n", &r, &c);
   for(i = 0; i < r; i++){
       for(t = 0; t < c; t++){
            scanf("%d", &table[i][t]);
       }
       
   }
   
    for(i = 0; i < r; i++){
       for(t = 0; t < c; t++){
            table[i][c] += table[i][t];
            table[r][t] += table[i][t];
       }
       
       table[r][c] += table[i][t];
   }
   
   
      for(i = 0; i < r + 1; i++){
       for(t = 0; t < c + 1; t++){
            if(t != 0) printf(" ");
            printf("%d", table[i][t]);
       }
       printf("\n");
   }
   
    return 0;
}

Measured memory_bytes: 4520
from collections import deque
S=deque(input())
Q=int(input())
T=[]
m=0
for i in range(Q):
  T.append(input().split())
for i in range(Q):
  if T[i][0]=="1":
    if len(S)>1:
      if m==0:
        m=1
      else:
        m=0
        
  else:
    if T[i][1]=="1":
      if m==0:
        S.appendleft(T[i][2])
      else:
        S.append(T[i][2])
   
    else:
      if m==0:
        S.append(T[i][2])
      else:
        S.appendleft(T[i][2])
if m==0:
  print("".join(S))
else:
  S.reverse()
  print("".join(S))

Measured memory_bytes: 44660
#include<bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

signed main(){
  fastio
  int n;cin>>n;
  ll a[n+1];
  for(int i=1;i<=n;i++)  cin>>a[i];
  map<ll,ll>m;
  ll ans=0;
  for(int i=1;i<=n;i++){
    ans+=m[i-a[i]];
    m[i+a[i]]++;
  }
  cout<<ans<<"\n";
  return 0;
}

Measured memory_bytes: 27800
N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)

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

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

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; }

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

const int MAX = 100005;
const int INF = 1001001001;
const int MOD = 1000000007;

struct mint {
    long long x;
    mint(long long x=0):x(x % MOD + (0 <= x ? 0 : MOD)) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint& a) { if ((x += a.x) >= MOD) x -= MOD; return *this; }
    mint& operator-=(const mint& a) { if ((x -= a.x) < 0) x += MOD; return *this; }
    mint& operator*=(const mint& a) { (x *= a.x) %= MOD; return *this; }
    mint operator+(const mint& a) const { return mint(x) += a; }
    mint operator-(const mint& a) const { return mint(x) -= a; }
    mint operator*(const mint& a) const { return mint(x) *= a; }

    // for prime mod
    mint inv() const {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        return mint(u);
    }
    mint& operator/=(const mint& a) { return *this *= a.inv(); }
    mint operator/(const mint& a) const { return mint(x) /= a; }
};
istream& operator>>(istream& is, const mint& a){ return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a){ return os << a.x; }

struct Combination{
    vector<long long> fac, finv, inv;
    Combination(int n=100100):fac(n+1), finv(n+1), inv(n+1) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i <= n; i++){
            fac[i] = fac[i - 1] * i % MOD;
            inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
            finv[i] = finv[i - 1] * inv[i] % MOD;
        }
    }
    long long operator()(int n, int k) const {
        if (n < k || n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
};

vector<int> G[MAX];

Combination com;
mint ans;

void dfs(int v, int c, int p=-1) {
    if (p < 0) {
        ans *= c;
        int n = G[v].size();
        ans *= com(c-1, n);
        ans *= com.fac[n];
    } else {
        int n = G[v].size() - 1;
        ans *= com(c-2, n);
        ans *= com.fac[n];
    }

    for (int u : G[v]) {
        if (u == p) continue;
        dfs(u, c, v);
    }
}

int main(){
    int N, K;
    cin >> N >> K;

    rep(i, N-1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ans = 1;
    dfs(0, K);
    cout << ans << endl;
}

Measured memory_bytes: 11520
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Queue, PriorityQueue}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)


  val N = in.next().toInt
  val _L = new Array[Int](N+1)
  for (i <- 1 to N)
    _L(i) = in.next().toInt


  val L = _L.sorted



  //
  def check(i: Int, j: Int, k: Int): Boolean =
    L(k) < L(i) + L(j)


  // 条件を満たす最大の値を返す
  def binarySearch(min: Int, max: Int, i: Int, j: Int): Int = {
    val mid: Int = (max + min) / 2
      (max - min) match{
      case 0 | 1 =>
        check(i,j,max) match{
          case true  => max
          case false => min
        }
      case _ =>
        (check(i,j,mid)) match{
          case true  => binarySearch(mid, max,i,j)
          case false => binarySearch(min, mid,i,j)
        }
    }
  }
  var ans = 0L

  for (i <- 1 to N-2) {
    for (j <- i+1 to N-1) {
      val k = binarySearch(j+1, N, i, j)

      if(check(i, j, k)) {

        ans += k-j
      }
    }
  }

  println(ans)
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 27460
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
typedef long long ll;
using namespace std;

int main() {
	ll n,a,b,c;
	cin>>n;
	for(int i=n;i<1000;i++){
		a=i/100;
		b=(i%100)/10;
		c=i%10;
		if(a==b && b==c){
			cout << i<<endl;
			return 0;
		}

	}
	return 0;
}




Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.call(in,out);
        out.close();
    }

    static class TaskA {
        public void call(InputReader in, PrintWriter out) {
            int n ,k  ,sum=0  ;
            n = in.nextInt();
            k = in.nextInt() ;
            int[] arr= new int[n];
            for (int i = 0; i <arr.length ; i++) {
                arr[i] = in.nextInt();
            }

            Arrays.sort(arr);
            for (int i = 0; i <k ; i++) {
                sum+=arr[i];

            }
            out.println(sum);

        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong(){
            return Long.parseLong(next());
        }

    }
}

Measured memory_bytes: 33236
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] w = sc.next().toCharArray();
		int[] c = new int[26];
		for (int i=0; i<w.length; i++) {
			c[w[i]-'a'] ++;
		}
		for (int i=0; i<c.length; i++) {
			if ( c[i]%2 == 1 ) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}
}


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

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=b-1;i>=a;--i)

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template <typename T1, typename T2>
void chmax(T1 &a, const T2 &b) {
  if(a < b) a = b;
}

template <typename T1, typename T2>
void chmin(T1 &a, const T2 &b) {
  if(a > b) a = b;
}

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i != (int)(s.size())-1) cout << " ";
  }
  cout << "\n";
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

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

  map<int, bool> mp;
  bool ok = false;
  REP(i, n) {
    if(a[i] == 1) {
      mp[1] = true;
      ok = true;
    }
    else if(mp[a[i]-1]) mp[a[i]] = true;
  }

  if(!ok) {
    cout << -1 << endl;
    return 0;
  }

  int ma = 0;
  for(auto &e: mp) {
    if(e.second) chmax(ma, e.first);
  }

  cout << n - ma << endl;


}


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



int main() {
    int X,Y,Z;
    cin>>X>>Y>>Z;
    cout<<Z<<" "<<X<<" "<<Y<<endl;
}

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

using namespace std;

const int MAX   = 1000100;
const int MAX_M = 1000100;
const int W = 1020;
bool prime[MAX];
int n, m;

void sieve(){
    fill(prime, prime+MAX, true);
    prime[0] = prime[1] = false;

    for(int i=0; i < MAX; i++){
        if(!prime[i]) continue;
        for(int j=i+i; j < MAX; j += i){
            prime[j] = false;
        }
    }
}

int cave[W][W] = {};
pair<int, int> memo[W][W];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

pair<int, int> bfs(int x, int y){
    if(memo[x][y].first != -1) return memo[x][y];

    pair<int, int> ret = make_pair(0, 0);
    for(int i=-1; i <= 1; i++){
        if(n < cave[x+1][y+i] || cave[x+1][y+i] == -1) continue;
        ret = max(ret, bfs(x+1, y+i));
    }
    if(prime[cave[x][y]]){
        if(ret.first == 0) ret.second = cave[x][y];
        ret.first++;
    }
    memo[x][y] = ret;
    return ret;
}

int main(){
    sieve();
    int x = W/2, y = W/2;
    int d = 1, p = 2;
    for(int i=0; i< W; i++)for(int j=0; j< W; j++) cave[i][j] = -1;
    for(int i = 1; i <= MAX_M; i++){
        for(int j = 0; j < d && i <= MAX_M; j++, i++){
            cave[x][y] = i;
            x += dx[p%4]; y += dy[p%4];
        }
        p++; i--;
        if(p%2 == 0) d++;
    }
    while(cin >> n >> m, n+m){
        for(int i=0; i< W; i++)for(int j =0; j < W; j++) memo[i][j] = make_pair(-1, -1);
        d = 1; p = 2;
        x = W/2; y = W/2;
        while(cave[x][y] != m){
            for(int j=0; j < d && cave[x][y] != m; j++){
                x += dx[p%4]; y += dy[p%4];
            }
            p++;
            if(p%2 == 0) d++;
        }
        pair<int, int> ret = bfs(x, y);
        cout << ret.first << " " << ret.second << endl;
    }
}

Measured memory_bytes: 14420
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;
#define MAX 3000

int main(){
    ll n,m; cin >> n >> m;
    vl x(m), y(m);
    rep(i,m) {
        cin >> x[i] >> y[i];
        x[i]--; y[i]--;
    }
    vl box(n, 1);
    set<ll> red;
    red.insert(0);
    rep(i,m){
        if(red.find(x[i]) != red.end()){
            if(box[x[i]] == 1) red.erase(x[i]);
            if(red.find(y[i]) == red.end()) red.insert(y[i]);
        }
        box[x[i]]--; box[y[i]]++;
        if(box[x[i]] == 0){
            if(red.find(x[i]) != red.end()) red.erase(x[i]);
        }
    }
    cout << red.size() << endl;
}

Measured memory_bytes: 7296
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define ALL(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
const int MAX = (int)2e5 + 5;

int main() {
	int N;
	string s, t;
	cin >> N >> s >> t;
	rep(i, N) {
		if (s.substr(i, N - i) == t.substr(0, N - i)) {
			cout << N + i << endl;
			return 0;
		}
	}
	cout << 2 * N << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
T = [0]
X = [0]
Y = [0]

for i in range(N):
    t, x, y = map(int, input().split())
    T.append(t)
    X.append(x)
    Y.append(y)

for i in range(1, N+1):
    if abs(T[i-1] - T[i]) < abs(X[i-1] - X[i]) + abs(Y[i-1] - Y[i]):
        print('No')
        exit()
    else:
        if T[i] % 2 != 0 and (X[i]+Y[i]) % 2 == 0:
            print('No')
            exit()
        elif T[i] % 2 == 0 and (X[i]+Y[i]) % 2 != 0:
            print('No')
            exit()

print('Yes')

Measured memory_bytes: 11716
S = input()
total = 0
for i in range(1 << (len(S) - 1)):
    tmp = ""
    for j in range(len(S)):
        tmp += S[j]
        if (i >> j) & 1 == 1:
            tmp += "+"
    else:
        total += eval(tmp)
else:
    print(total)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    ll a[n];
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
        sum %= mod;
    }
    ll prod = 0;
    for (int i = 0; i < n; i++)
    {

        sum -= a[i];
        if(sum<0) sum+=mod;
        prod += a[i] * sum;
        prod %= mod;
    }
    cout << prod;
    return 0;
}

Measured memory_bytes: 5216
#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    int A,B = 0;
    int result = 0;
    
    scanf("%d",&A);
    scanf("%d",&B);
    
    if (A>=13) {
        result = B;
    }else if(6 <= A && A <= 12){
        result = B/2;
    }else{
        result = 0;
    }
    
    printf("%d",result);
}


Measured memory_bytes: 128
#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;
long long a,b;
int main()
{
    cin>>a>>b;
    if(a>0||(abs(b)-abs(a))%2!=0)
    {
    	cout<<"Positive";
    	return 0;
    }    
	if(a==0||a<0&&b>0)
    {
    	cout<<"Zero";
    	return 0;
    }    
    cout<<"Negative";
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<(int)(n);i++)
#define N 200010


int main() {
	bool a[N];
	int b[N];
	f(i, N) {
		a[i] = false;
		b[i] = 0;
	}
	char c[3];
	c[0] = 0;
	c[1] = 0;
	c[2] = 0;
	int n, m, x, y;
	scanf("%d %d", &n, &m);
	f(i, m) {
		scanf("%d", &x);
		scanf("%s", c);
		if (c[0] == 'A')a[x - 1] = true;
		else if (!a[x - 1])b[x - 1]++;
		c[0] = 0;
		c[1] = 0;
		c[2] = 0;
	}
	x = 0;
	y = 0;
	f(i, n) {
		if (a[i]) {
			x++;
			y += b[i];
		}
	}
	printf("%d %d\n", x, y);

	return 0;
}


Measured memory_bytes: 1152