akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

int main(){

//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());
    
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    ll n,k;
    cin >> n >> k;

    ll a[n];
    //10^12が最高なので、
    ll b[42] = {};
    REP(i,n)
    {
        cin >> a[i];
    }

    REP(i,n)
    {
        ll j = 0;
        while(a[i] >= (1ull << j))
        {
            //bit立ってるなら
            if(a[i] & (1ull << j))
            {
                ++b[j];
            }
            ++j;
        }
    }
    ll num = 0;

    for(int i = 41; i >= 0; --i)
    {
        ll tmp = 1;
        for(int j = 0; j < i; ++j)tmp *= 2;
        
        if(tmp + num > k)continue;

        //1のが少ないならnumのbitを1にしたほうがよい
        if(n - 2 * b[i] > 0)
        {
            num += tmp;
        }
    }

    ll res = 0;
    REP(i,n)
    {
        //xorを求める
        ll tmp;

        tmp = num ^ a[i];
        res += tmp;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var nk = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var n = nk[0];
        var k = nk[1];
        var ts = new int[n];
        var ds = new long[n];
        for (int i = 0; i < ts.Length; i++)
        {
            var td = Console.ReadLine().Split().ToArray();
            ts[i] = int.Parse(td[0]);
            ds[i] = long.Parse(td[1]);
        }

        Array.Sort(ds, ts);
        Array.Reverse(ts);
        Array.Reverse(ds);

        var maximum = Solve(n, k, ts, ds);
        Console.WriteLine(maximum);
    }

    static long Solve(int n, int k, int[] ts, long[] ds)
    {
        var neta = 0L;
        var positiveBase = 0L;
        var nonpositiveBase = 0L;
        var nonpositive = new Stack<int>();
        var existingByNeta = new bool[n + 1];
        int i = 0;
        for (; i < k; i++)
        {
            if (existingByNeta[ts[i]])
            {
                nonpositiveBase += ds[i];
                nonpositive.Push(i);
            }
            else
            {
                positiveBase += ds[i];
                neta++;
                existingByNeta[ts[i]] = true;
            }
        }
        var point = positiveBase + nonpositiveBase + neta * neta;
        for (; i < n; i++)
        {
            if (!nonpositive.Any())
            {
                break;
            }

            if (existingByNeta[ts[i]])
            {
                continue;
            }

            positiveBase += ds[i];
            neta++;
            existingByNeta[ts[i]] = true;;
            nonpositiveBase -= ds[nonpositive.Pop()];
            point = Math.Max(point, positiveBase + nonpositiveBase + neta * neta);
        }
        return point;
    }
}


Measured memory_bytes: 18764
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
	int num;
	ll gen;
	scanf("%d%lld%", &num, &gen);
	ll r = 0;
	ll now = 0;
	for (int i = 0; i < num; i++)
	{
		ll z;
		scanf("%lld", &z);
		r += max(0LL, now + z - gen);
		now = max(0LL, min(z, gen - now));
	}
	printf("%lld\n", r);
}

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

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    int sum = 0;
    for (int i = 0; i < n; i++) cin >> s[i], sum += s[i];
    sort(s.begin(), s.end());
    if (sum % 10 != 0) {
        cout << sum << endl;
        return 0;
    } else {
        for (int i = 0; i < n; i++) {
            if ((sum - s[i]) % 10 != 0) {
                cout << sum - s[i] << endl;
                return 0;
            }
        }
    }
    cout << 0 << endl;
    return 0;
}

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

using namespace std;
using ll = long long;

int main(){
    ll n, q;
    cin>>n>>q;
    vector<queue<ll>> Q(n);

    int query, t, x;
    for(ll i=0; i<q; ++i){
        cin>>query>>t;
        if(query==0){
            cin>>x;
            Q[t].push(x);
        }else if(query==1){
            if(!Q[t].empty()){
                cout<<Q[t].front()<<endl;
            }else{
            }
        }
        else{
            if(!Q[t].empty()){
                Q[t].pop();
            }
        }
    }
}



Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,x,y) for(int i=(int)(x);i<(int)(y);++i)
#define FORE(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
typedef long long ll;
typedef pair<int,int> pii;
const int INF=2e9;
const int MOD=1e9+7;
const int MAXN=5e5+7;

ll ans=0;
int n,m,k,q,x,y,A,B,C;
int a[MAXN];
int b[MAXN];
int c[MAXN];
int r=0;
int ap,bp,cp;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>x>>y>>A>>B>>C;
    FOR(i,0,A)cin>>a[i];
    FOR(i,0,B)cin>>b[i];
    FOR(i,0,C)cin>>c[i];
    sort(a,a+A,greater<int>());
    sort(b,b+B,greater<int>());
    sort(c,c+C,greater<int>());
    while(x+y>r){
        if(x==0)a[ap]=-INF;
        if(y==0)b[bp]=-INF;
        if(c[cp]>a[ap]&&c[cp]>b[bp]){
            ++r;
            ans+=c[cp++];
        }else if(a[ap]>b[bp]){
            --x;
            ans+=a[ap++];
        }else{
            --y;
            ans+=b[bp++];
        }
    }
    cout<<ans<<"\n";
    return 0;
}


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

bool fc[110][110],fr[110][110];

int col(int x,int y,int d=1){
	if(fc[x+1][y]){
		fc[x+1][y]=false;
		return col(x+1,y,d+1);
	}else{
		return d;
	}
}

int row(int x,int y,int d=1){
	if(fr[x][y+1]){
		fr[x][y+1]=false;
		return row(x,y+1,d+1);
	}else{
		return d;
	}
}

int main(void){
	int n,m,d,i,j,ans=0,c,l;
	char s[110][110];
	cin >> n >> m >> d;
	fill(fc[0],fc[110],false);
	fill(fr[0],fr[110],false);
	d--;
	for(i=1; i<=n; i++){
		cin >> s[i];
		for(j=0; j<m; j++){
			if(s[i][j]=='.'){
				fc[i][j+1] = true;
				fr[i][j+1] = true;
			}
		}
	}
	for(i=1; i<=n; i++){
		for(j=1; j<=m; j++){
			if(fc[i][j] || fr[i][j]){
				fc[i][j] = false;
				fr[i][j] = false;
				c = col(i,j);
				l = row(i,j);
				ans += max(c-d,0);
				ans += max(l-d,0);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 214748360
#define long long long // for codeforces

int main(){
  int n,k;
  cin>>n>>k;
  vector<vector<int>> vec(10);
  rep(i,n){
    int a,b;
    cin>>a>>b;
    vec[b-1].pb(a);
  }

  vector<int> dp(k+1, -INF);
  dp[0] = 0;
  rep(gen,10){
    vector<int> tmp(k+1, -INF);
    tmp[0]=0;
    for(auto p : vec[gen]){
      for(int i=k; i>0; i--) if(tmp[i-1]>-INF) tmp[i] = max(tmp[i], tmp[i-1] + p + 2*(i-1));
    }

    vector<int> nxt(k+1, -INF);
    rep(i,k+1){
      nxt[i] = max(nxt[i], dp[i]);
      for(int j=1; i+j<=k; j++) nxt[i+j] = max(nxt[i+j], dp[i] + tmp[j]);
    }
    swap(nxt, dp);
  }

  cout << dp[k] << endl;

  return 0;
}

Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
     
#define int long long
#define hell 1000000007  
#define endl "\n"
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX_SIZE 10000000000


int32_t main()
{   
    io

    int n;
    cin>>n;

    int a[n];
    int s1=0, s2=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s2 += a[i];
    }

    int min_diff = abs(s2-s1);

    for(int i=0;i<n;i++)
    {
        s1 += a[i];
        s2 -= a[i];
        min_diff = min(min_diff, abs(s2-s1));
    }

    cout<<min_diff;


return 0;
}

Measured memory_bytes: 256
// In the name of god
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void solve()
{
  ll n,a1=0,a2=0,a3=0,a4=0;
  cin>>n;
  string s;
  while(n--)
  {
    cin>>s;
    if(s == "AC"){a1++;}
    else if(s == "WA"){a2++;}
    else if(s == "TLE"){a3++;}
    else if(s == "RE"){a4++;}
  }
  cout<<"AC x "<<a1<<'\n'<<"WA x "<<a2<<'\n'<<"TLE x "<<a3<<'\n'<<"RE x "<<a4<<'\n';


}



int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  solve();
}


Measured memory_bytes: 3660
import java.util.Scanner;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		String op = sc.next();
		int B = sc.nextInt();
		if(op.equals("+")) {
			System.out.println(A + B);
			sc.close();
			return;
		}else {
			System.out.println(A - B);
		}
		sc.close();
	}

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

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define DEBUG(val) cout << #val << " : " << val << endl
#define MOD 1000000007

int main() {
  string str;
  cin >> str;
  int s = 0;
  int t = 0;
  int remove_count = 0;
  REP(i, str.length()) {
    if (str[i] == 'S') {
      s++;
    } else {
      if (s > 0) {
        s--;
        remove_count += 2;
      }
    }
  }
  cout << str.length() - remove_count << endl;
}

Measured memory_bytes: 640
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	A = inputStr()

	if A.isupper():
		print("A")
	else:
		print("a")



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 70756
"""
難しい :(
"""

import sys
input = sys.stdin.readline
from functools import reduce
from fractions import gcd
from math import ceil

def is_same(A:list):
    exp = 0
    for i in range(len(A)):
        now = 0
        while A[i] % 2 == 0:
            A[i] >>= 1
            now += 1

        if i == 0:
            exp = now
            continue

        if exp != now:
            return False, exp
    
    return True, exp

def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    _,M = map(int,input().split())
    A = [int(i)//2 for i in input().split()]

    flag, exp = is_same(A)
    if not flag:
        print(0)
        exit()

    power = 2 ** exp
    MINX = lcm_list(A)

    ans = (M+MINX*power) // (2*power*MINX)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 16240
#include<bits/stdc++.h>
using namespace std;
#define dd double
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ll long long
#define ull unsigned long long
#define ld long double
#define mx 1000005
#define mod 1000000007
#define fr first
#define se second
#define End cout<<"\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define memo(Array,val) memset(Array, val, sizeof Array)
#define PI acos(-1)
bool check(ll n, ll pos){ return (n&(1<<pos)); }
bool Set(ll n, ll pos) {  return (n | (1<<pos)); }
ld LOG(ld b, ld e){ return log(b)/log(e); }

int tc=1;

void solve(int kk)
{
    int ass,day,tot=0;
    cin >> ass >> day;
    for(int i=1,a; i<=day; i++) cin >> a, tot+=a;
    int cc = ass-tot;
    if(cc<0) cc=-1;
    cout << cc << "\n";
}

int main()
{
   //freopen("text.txt", "r", stdin);
   //freopen("text2.txt", "w", stdout);
   fast;
   int kk=0;
   //cin >> tc;
   //scanf("%d", &tc);
   while(++kk<=tc) solve(kk);

   return 0;
}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
template< typename T >
T mod_pow(T x, T n, const T &p) {
  T ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret;
}
class bunsu
{
	public:
	ll a,b;
	bool pn;
	bunsu()
	{
		a = 0;
		b= 0;
		pn = false;
	}
	bunsu(ll a,ll b,ll pn)
	{
		this->a = a;
		this->b = b;
		this->pn = pn;
	}
	bool operator<(const bunsu& value)const
	{
		if(pn!=value.pn)return pn<value.pn;
		if(value.a!=a)return a<value.a;
		return b<value.b;
	}
};

int main()
{
	ll zero = 0;
	ll n;
	cin >> n;
	map<bunsu,ll> mp;
	map<bunsu,bool> exsit;
	vector<pair<ll,ll>> AB;
	vector<bunsu> vb;
	for(ll i = 0;i<n;i++)
	{
		ll a,b;
		cin >> a >> b;
		AB.emplace_back(a,b);
		if(a==0&&b==0)
		{
			vb.emplace_back(0,0,0);
			zero ++;
			continue;
		}
		else if(a==0)
		{
			//return 1;
			vb.emplace_back(1,0,0);
			continue;
		}
		else if(b==0)
		{
			//return 1;
			vb.emplace_back(0,1,0);
			continue;
		}
		
		ll G = __gcd(abs(a),abs(b));

		vb.emplace_back(abs(a/G),abs(b/G),(a<0&&b>0)||(a>0&&b<0));
	}
	for(ll i = 0;i<n;i++)
	{
		exsit[vb[i]] = true;
		
		mp[vb[i]]++;
		mp[bunsu(vb[i].b,vb[i].a,!vb[i].pn)]+=0;
	}
	//ll ans = 1;
	ll add = 0;
	vector<ll> ANS;
	
	for(auto i:mp)
	{
		if(i.first.a==0&&i.first.b==0)
		{
			continue;
		}
		
		bunsu alt(i.first.b,i.first.a,!i.first.pn);
		if(i.first.a==0) alt = bunsu(1,0,0);
		if(i.first.b==0) alt = bunsu(0,1,0);
		ll now =  mod_pow(0LL+2,i.second,MOD)-1;
		(now += MOD)%=MOD;
		now += mod_pow(0LL+2,mp[alt],MOD)-1;
		(now += MOD)%=MOD;
		(now +=1)%=MOD;
		if(exsit[i.first])
		{
			ANS.push_back(now);
			exsit[alt] = false;
		}
		//cout<<now<<endl;
		//cout<<mp[bunsu(i.first.b,i.first.a,!i.first.pn)]<<endl;
		//cout<<i.first.a<<' '<<i.first.b<<' '<<i.first.pn<<endl;
	}
	ll ans = 1;
	for(auto i:ANS)
	{
		//cout<<i<<endl;
		(ans *= i)%=MOD;
		//cout<<ans<<';'<<i<<endl;
	}
	cout<<(ans-1LL+add+MOD+zero)%MOD<<endl;
}

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

using namespace std;

#define sqr(x) x*x

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, d;
	int x;
	cin >> n >> d;
	vector <vector<int>> v(n);
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < d; ++ j){
			cin >> x;
			v[i].emplace_back(x);
		}	
	}
	int ans = 0;
	for (int i = 0; i < n - 1; ++i){
		for (int j = i+1; j < n; ++j){
			double s = 0;
			for (int k = 0; k < d; ++k){
				s += sqr(abs(v[i][k] - v[j][k]));
			}
			if (sqrt(s) == (int)sqrt(s)){
				++ans;
			}
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main() {
  ll n,k;
  cin>>n>>k;
  vector<ll> va,vf;
  rep(i,0,n){
    ll a;
    cin>>a;
    va.pb(a);
  }
  rep(i,0,n){
    ll a;
    cin>>a;
    vf.pb(a);
  }
  sort(all(va));
  sort(all(vf));
  reverse(all(vf));
  long long low = 0;
  long long high = 1000000000000000000LL;

  while(low < high){
    long long mid = (high + low) >> 1;

    vector<ll> v;
    rep(i,0,n){
      ll a = mid/vf[i];
      v.pb(a);
    }
    ll k1 = k;
    rep(i,0,n){
      if(va[i]>v[i]){
        k1 -= va[i]-v[i];
      }
    }
    if(k1>=0){
      high = mid;
    }
    else{
      low = mid + 1;
    }
  }
  cout << low << endl;
  return 0;
}

Measured memory_bytes: 7636
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a[8];
  int ans=0,lim=5;
  for(int i=0;i<lim;i++){
    scanf("%d",&a[i]);
    if(a[i]==0)ans=i+1;
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    vector<int> K(Q);
    for (int i = 0; i < Q; i++) cin >> K[i];

    vector<int> sum(N+1);
    for (int k : K) {
        ll D = 0, M = 0, ans = 0;
        ll cntDM = 0;
        for (int i = 0; i < S.size(); i++) {
            if (S[i] == 'D') D++;
            else if (S[i] == 'M') {
                // S[i]='M' => Mの個数++, [’D’, ’M’] の個数 += Dの個数
                M++;
                cntDM += D;
            }
            else if (S[i] == 'C') ans += cntDM;
            if (i >= k - 1) {
                if (S[i - (k - 1)] == 'D') {
                // S[i]='D' => Dの個数--, [’D’, ’M’] の個数 -= Mの個数
                    D--;
                    cntDM -= M;
                }
                else if (S[i - (k - 1)] == 'M') M--;
            }
        }
        cout << ans << '\n';
    }
}


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

int main(){
  int n,k; cin>>n>>k;
  long long count=0,count2=0;
  for(int i=1;i<=n;i++){
    if(i%k==0) count++;
    if(k%2==0&&i%k==k/2) count2++;
  }
  cout<<count*count*count+count2*count2*count2<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mid ((s + e) / 2)
#define makefast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define comp(x, y) (lower_bound(vec.begin(), vec.end(), make_pair(x, y)) - vec.begin())
#define lc (v * 2)
#define rc (v * 2 + 1)
long long M = 1e9 + 7;
//>>>>>>>>>>>>>>>>>>>

#define int long long

const int N = 1e5 + 7;

int a[N];

int32_t main() {
	makefast;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	if (n == 1) {
		cout << "Second";
		return 0;
	}
	int t = 1;
	while (1) {
		int odd = 0, eve = 0, one = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] % 2)
				odd++;
			else
				eve++;
			if (a[i] == 1)
				one = 1;
		}
		if (one) {
			if ((odd % 2 != n % 2 && t == 1) || (odd % 2 == n % 2 && t == 2))
			   cout << "First";
			else
			cout << "Second";
		return 0;	
		}
		if (odd % 2 != n % 2) {
			if (t == 1)
				cout << "First";
			else
				cout << "Second";
			return 0;
		}
		if (odd != 1) {
			if (t == 2)
				cout << "First";
			else
				cout << "Second";
			return 0;
		}
		for (int i = 1; i <= n; i++)
			if (a[i] % 2)
				a[i]--;
		int g = a[1];
		for (int i = 2; i <= n; i++)
			g = __gcd(a[i], g);
		for (int i = 1; i <= n; i++) {
			a[i] /= g;
		}
		t = 3 - t;
	}

}


Measured memory_bytes: 4444
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};


typedef struct node * Node;
#define NIL NULL

Node root;



int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

 
   for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    
     
   if ( com[0] == 'i' ){
      scanf("%d", &x);

      insert(x);
    }
     else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");

      preorder(root);
      printf("\n");
    }
  }
 return 0;
 
 
}

Node treeMinimum(Node x){


}

Node treeSearch(Node u, int k){
  if(u == NIL || k == u -> key){
    return u;
  }
  if(k < u -> key) return treeSearch(u -> left, k);
  else return treeSearch(u -> right, k);

}

Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y;
  Node x;



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
  while(x != NIL){
    y = x;

    if(z->key < x->key){
      x = x->left;
    }
    else x= x->right;
  }
  z->parent = y;


  if(y == NIL){
    root = z;
  }
  else if(z->key < y->key){
    y->left = z;
  }
  else y->right = z;
  
  
  
}

void inorder(Node u){
  if(u != NIL){
 inorder(u->left);
 printf(" %d",u->key);
 inorder(u->right);
  }
}
void preorder(Node u){
  if(u != NIL){
 printf(" %d",u->key);
 preorder(u->left);
 preorder(u->right);
  }
}

Measured memory_bytes: 24040
#include <cstdio>
#include <queue>
#include <limits.h>
#include <cstring>
using namespace std;

typedef pair<int, int> P;
const int MAXN = 1010;
char map[MAXN][MAXN];
int n, m, t, sx, sy, ex, ey;
int d[MAXN][MAXN];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1} };
P a[15];

int bfs()
{
    queue<P> q;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            d[i][j] = INT_MAX;
        }
    }
    d[sx][sy] = 0;
    q.push(P(sx, sy));
    while(!q.empty())
    {
        P p = q.front();  q.pop();
        if(p.first == ex && p.second == ey)
            break;
        for(int i = 0; i < 4; i++)
        {
            int x = p.first + dir[i][0];
            int y = p.second + dir[i][1];
            if(x >= 0 && x < n && y >= 0 && y < m
               && 'X' != map[x][y] && INT_MAX == d[x][y])
               {
                   q.push(P(x, y));
                   d[x][y] = d[p.first][p.second] + 1;
               }
        }
    }
    return d[ex][ey];
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    getchar();
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            scanf("%c", &map[i][j]);
            if('S' == map[i][j])
            {
                a[0] = P(i, j);
            }
            else
            {
                if('.' != map[i][j] && 'X' != map[i][j])
                {
                    a[map[i][j] - '0'] = P(i, j);
                }
            }
        }
        getchar();
    }
    int ans = 0;
    for(int i = 1; i <= t; i++)
    {
        sx = a[i-1].first;
        sy = a[i-1].second;
        ex = a[i].first;
        ey = a[i].second;
        ans += bfs();
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 6020
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<long long> nums(n);
    for (int i = 0; i < n; i++){
        cin >> nums[i];
    }
    vector<long long> keep(nums);
    sort(nums.begin(), nums.end());
    long long middle = nums[n / 2];

    for (int i = 0; i < n; i++){
        if(keep[i] < middle){
            cout << middle << endl;
        }else{
            cout << nums[n / 2 - 1] << endl;
        }
    }
}

Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const int N = 3e5+6;
const int mod = 1e9+7;
const int inf = 1e8;
vector<int>divs[N];
int bit[N];
int mx[N];
int ans[N];
void add(int idx){
    for(int i=idx;i>0;i-=(i&-i))bit[i]++;
}
void del(int idx){
    for(int i=idx;i>0;i-=(i&-i))bit[i]--;
}
int sm(int idx){
    int ret = 0;
    for(int i=idx;i<N;i+=(i&-i))ret+=bit[i];
    return ret;
}
int inc[N];
void solve(){
    int n,m;
    cin>>n>>m;
    priority_queue<pair<int,int>> pq;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        pq.push({-l,-i});
        pq.push({-r-1,i});
    }
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j+=i){
            divs[j].pb(i);
        }
    }
    int mxm = 0;
    int cnt = 0;
    for(int i=1;i<=m;i++){
        while(!pq.empty()){
            int x = -pq.top().fi;
            if(x!=i)break;
            int y = pq.top().se;
    //        cout<<i<<" "<<x<<" "<<y<<endl;
            if(y<0){
                cnt++;
                inc[-y] = cnt;
                add(cnt);
                mxm = max(mxm,cnt);
            }
            else{
                del(inc[y]);
            }
            pq.pop();
        }

        for(int j:divs[i]){
      //      cout<<i<<" "<<j<<" "<<mx[j]<<" "<<sm(mx[j]+1)<<endl;
            ans[j]+=sm(mx[j]+1);
            mx[j] = max(mx[j],mxm);
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--)solve();
    return 0;
}


Measured memory_bytes: 26728
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ar array
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mx *max_element
#define mn *min_element
#define fo(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define sortall(x) sort(all(x))
#define precision cout<<fixed<<setprecision(10)
#define w(t) ll t;cin>>t;while(t--)
#define setbits(x) __builtin_popcountll(x)
const double pi=3.1415926535897932384626;
//const ll mod = 998244353;
const ll mod=1e9+7;
ll r,c,k;
vector <vector<ll>> v(3000,vector<ll>(3000,0));
ll dp[3000][3000][3];
ll solve(ll p,ll q,ll u)
{
    if(p==r-1&&q==c-1){
        if(u<3)
        return v[p][q];
        else return 0;
    }
    if(q>=c||p>=r) return -1e15;
    if(u==3&&p==r-1) return 0;
    if(u==3){
        if(dp[p+1][q][0]!=-1) return dp[p+1][q][0];
        return solve(p+1,q,0ll);
    }
    if(dp[p][q][u]!=-1) return dp[p][q][u];
    return dp[p][q][u]=max({v[p][q]+solve(p+1,q,0ll),v[p][q]+solve(p,q+1,u+1),solve(p,q+1,u)});
}
int main()
{
  IOS
  cin>>r>>c>>k;
  fo(i,k){
    ll x,y,z;
    cin>>x>>y>>z;
    x--;y--;
    v[x][y]=z;
  }
  memset(dp,-1,sizeof(dp));
  cout<<solve(0ll,0ll,0ll)<<"\n";
  return 0;
}

Measured memory_bytes: 285480
#include <bits/stdc++.h>
using namespace std;
 
// vector<int> vec(3); = vector<int> vec={0,0,0}
// vec.at()
// sort(num.begin(),num.end(), greater<int>());
// reverse(num.begin(),num.end());
 
// 切り上げ　a/b+1
//  1からNの総和　N*(N+1)/2
 
int main() {
  int A,B;
  char op;
  cin >> A >> op >> B;

  if(op == '+'){
  	cout << A+B << endl;
  }else{
  	cout << A-B << endl;
  }
}

Measured memory_bytes: 256
from collections import deque
n, m = map(int, input().split())
ab = [[] for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

ans = [-1]*(n+1)
que = deque([1])

while que:
    q = que.popleft()
    for i in ab[q]:
        if ans[i] == -1:
            que.append(i)
            ans[i] = q

print("Yes")

for i in range(2,n+1):
    print(ans[i])


Measured memory_bytes: 34044
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

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

const int MOD=1000000007;
int INF=100100100100100;
map<int,int> ma;
int beki[200010];
int a[200010];
signed main(){
  int n,p;cin>>n>>p;
  string s;cin>>s;
  int ans=0;
  if(p==2 || p==5){
    rep(i,n){
      int t=s[i]-'0';
      if(t%p==0)ans+=i+1;
    }
    cout<<ans<<endl;
    return 0;
  }
  
  //p!=2,5の場合
  ma[0]++;
  rep(i,n){
    if(i==0)beki[i]=1;
    else beki[i]=(10*beki[i-1])%p;
    int t=s[n-1-i]-'0';
    if(i==0)a[0]=t%p;
    else {
      a[i]=(a[i-1]+beki[i]*t)%p;
    }
    //cout<<a[i]<<endl;
    ma[a[i]]++;
  }
  for(auto ite=ma.begin();ite!=ma.end();ite++){
    int po=ite->S;
    ans+=po*(po-1)/2;
  }
  cout<<ans<<endl;
  
  return 0;
}


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

const int MAX = 1e5 + 5;

#define dbg(a) cout << "-> " << __LINE__ << ": " << #a << " = " << a << endl

vector<int> col;
vector<pair<int, int>> G[MAX];

void dfs (int u, int p, int c) {
	int ptr = 1;
	for (auto v : G[u]) {
		if (v.first != p) {
			if (c == ptr) {
				++ptr;
			}
			col[v.second] = ptr;
			dfs(v.first, u, ptr);
			++ptr;
		}
	}
}

int main() {
    int n;
	scanf("%d", &n);
	col.resize(n - 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		G[u].emplace_back(v, i);
		G[v].emplace_back(u, i);
	}
	dfs(1, -1, 0);
	printf("%d\n", (int) (set<int> (col.begin(), col.end())).size());
	for (int v : col) {
		printf("%d\n", v);
	}
    return 0;
}


Measured memory_bytes: 9344
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

using namespace std;
#define int long long
using ll = long long;
const int MX = 1e6;
const ll inf = 1e13;
const int mod = 1e9+7;
int h,w;
int cx,cy;
int dx,dy;
int s[1003][1003];
int v[1003][1003];

signed main() {
    cin >> h>>w>>cx>>cy>>dx>>dy;
    cx--;cy--;
    dx--;dy--;
    rep(i,h) {
        string st;
        cin >>st;
        rep(j,w) {
            s[i][j]=st[j];
            v[i][j]=inf;
        }
    }
    v[cx][cy]=0;
    deque<pair<int,int>> q;
    q.push_back({cx,cy});
    
    vector<int> a;
    while(q.size()>0) {
        pair<int,int> p = q.front();
        q.pop_front();
        int x = p.first;
        int y = p.second;
        //cout << x <<" "<<y << endl;
        rep(i,5) {
            rep(j,5) {
                if(x-2+i<0 || x-2+i>=h || y-2+j<0 || y-2+j>=w) continue;
                if(s[x-2+i][y-2+j]=='.') {
                    if(v[x-2+i][y-2+j]==inf)q.push_back({x-2+i,y-2+j});
                    v[x-2+i][y-2+j]=min(v[x-2+i][y-2+j],v[x][y]+(int)1);
                }
            }
        }
        if(x+1<h) {
            if(s[x+1][y]=='.') {
                if(v[x+1][y]!=v[x][y])q.push_front({x+1,y});
                v[x+1][y] = min(v[x+1][y],v[x][y]);
            }
        }
        if(y+1<w) {
            if(s[x][y+1]=='.') {
                if(v[x][y+1]!=v[x][y])q.push_front({x,y+1});
                v[x][y+1] = min(v[x][y+1],v[x][y]);
            }
        }
        if(x-1>=0) {
            if(s[x-1][y]=='.') {
                if(v[x-1][y]!=v[x][y])q.push_front({x-1,y});
                v[x-1][y] = min(v[x-1][y],v[x][y]);
            }
        }
        if(y-1>=0) {
            if(s[x][y-1]=='.') {
                if(v[x][y-1]!=v[x][y])q.push_front({x,y-1});
                v[x][y-1] = min(v[x][y-1],v[x][y]);
            }
        }

    }
    
    // rep(i,h) {
    //     rep(j,w) {
    //         if(v[i][j]!=inf) cout << v[i][j] << flush;
    //         else cout << "x" << flush;
    //     }
    //     cout << "" << endl;
    // }
    if(v[dx][dy]==inf) cout << -1 << endl;
    else cout << v[dx][dy] << endl;
    

    return 0;
}



Measured memory_bytes: 19396
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

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;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    set<string> st;
    rep(i, n) {
        string tmp; cin >> tmp;
        st.insert(tmp);
    }
    cout << (int)st.size() << endl;
    return 0;
}

Measured memory_bytes: 19264
#include<bits/stdc++.h>
#define ll long long int 
#define pb push_back
#define mp make_pair
#define ff first
#define se second
#define MAX 1000001
#define MAXN 100005
#define mod 1000000007 
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    ll i,count=0;
    stack<char> st;
    for(i=0;i<s.size();i++){
        if(st.empty()==true){
            st.push(s[i]);
        }
        else{
            char ch=st.top();
            if(ch!=s[i]){
                count+=2;
                st.pop();
            }
            else{
                st.push(s[i]);
            }
        }
    }
    cout<<count;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define For(i, s, e) for(ll i = s;i <= e;i++)
#define Sort(v, n) sort(v, v+n);
#define VSort(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define cY cout<<"Yes";
#define cN cout<<"No";
#define cA(a) cout<<a;
const ll MOD = 1000000007;



int main() {
    ll a,b,n;cin>>a>>b>>n;
    ll x;
    ll ans = -1;
    For(i,1,100000000) {
        if(i<=n)ans = max(ans,(a*i/b) - a*(i/b));
    }
    if(n <= 100000000) {
        cout << ans;
        return 0;
    }
    x = (n+1)/b;
    ans = max((a*(x*b-1))/b - a*((x*b-1)/b),ans);
    ans = max(ans,(a*(n-1)/b) - a*((n-1)/b));
    cout << ans;
}

Measured memory_bytes: 3624
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
D = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if i * j * k > K:
                break
            D.append(A[i] + B[j] + C[k])
D.sort(reverse=True)
for d in D[:K]:
    print(d)


Measured memory_bytes: 137660
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int a[105];

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int cnt=0;
	bool flag=true;
	for(int i=0;i<n-1;i++){
		int mini=i;
		for(int j=i;j<n;j++){
			if(a[j]<a[mini]){
				mini=j;
			}
		}
		if(i!=mini){
			swap(a[i],a[mini]);
			cnt++;
		}
	}
	for(int i=0;i<n;i++){
		printf("%d%c",a[i],i==n-1?'\n':' ');
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 2712
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  long long int n;
  cin>>n;
  if(n%1000==0){
    cout<<0<<endl;
  }else{
    cout<<1000-n%1000<<endl;
  }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    pr((N+1)/2);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;


signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int> A(N);
	rep(i,N) cin >> A[i];
	sort(A.begin(), A.end());
	int num = A[0];
	int ans = 0;
	if(A[0] <= 0 && A[N-1] >= 0){
		rep(i,N){
			ans += abs(A[i]);
		}
		cout << ans << endl;
		for(int i=N-2;i>=0;i--){
			if(A[i] > 0){
				cout << A[0] << ' ' << A[i] << endl;
				A[0] -= A[i];
			}
			else{
				num = i;
				break;
			}
		}
		for(int i=0;i<=num;i++){
			cout << A[N-1] << ' ' << A[i] << endl;
			A[N-1] -= A[i];
		}
	}
	else if(A[0] >= 0){
		for(int i=1;i<N;i++){
			ans += A[i];
		}
		cout << ans-A[0] << endl;
		for(int i=0;i<N-2;i++){
			cout << A[i] << ' ' << A[i+1] << endl;
			A[i+1] = A[i] - A[i+1]; 
		}
		cout << A[N-1] << ' ' << A[N-2] << endl;
	}
	else{
		for(int i=0;i<N-1;i++){
			ans -= A[i];
		}
		cout << ans+A[N-1] << endl;
		for(int i=N-1;i>0;i--){
			cout << A[i] << ' ' << A[i-1] << endl;
			A[i-1] = A[i]-A[i-1];
		}
	}

}

Measured memory_bytes: 2688
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  while (cin >> n, n) {
    vector<int> all(2*n);
    for (int i = 0; i < 2*n; ++i)
      all[i] = i;
    vector<int> players[2];
    for (int i = 0; i < n; ++i) {
      int c; cin >> c; --c;
      players[0].push_back(c);
    }
    sort(players[0].begin(), players[0].end());
    for (int i = 0; i < n; ++i)
      swap(all[i], all[players[0][i]]);
    players[1].assign(all.begin() + n, all.end());
    sort(players[1].begin(), players[1].end());

    int play = -1;
    for (int turn = 0; ; turn = !turn) {
      vector<int>& player = players[turn];
      auto it = lower_bound(player.begin(), player.end(), play);
      if (it == player.end()) {
        play = -1;
      } else {
        play = *it;
        player.erase(it);
        if (player.empty())
          break;
      }
    }

    cout << players[1].size() << endl << players[0].size() << endl;
  }
}

Measured memory_bytes: 1220
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(N, M):
    ans = []
    now = 0
    for d in range(M, 0, -2):
        ans.append((now, now + d))
        now += 1

    now = M + 1
    for d in range(M - 1, 0, -2):
        ans.append((now, (now + d) % N))
        now += 1

    return ans


def main():
    N, M = map(int, input().split())
    ans = solve(N, M)
    for x in ans:
        print(f"{x[0] + 1} {x[1] + 1}")


if __name__ == '__main__':
    main()


Measured memory_bytes: 21764
import sys
input = sys.stdin.readline
import fractions 
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  count = 1
  ans = 0
  for i in range(n):
    if a[i] != count:
      ans += 1

    else:
      count += 1
  if count == 1:
    print(-1)
  else:
    print(ans)
  
  
solve()

Measured memory_bytes: 27168
#include <stdio.h>

int main(void)
{
	int k, s;
	int x, y, z;
	int count = 0;
	
	scanf("%d %d", &k, &s);
	
	for(x=0; x<=k; x++){
		if( (x+2*k) < s )
			continue;
		else if(x > s)
			break;
		
		for(y=0; y<=k; y++){
			if( (x+y+k) < s )
				continue;
			else if( (x+y) > s )
				break;
			else if( s-(x+y) >= 0 )
				count++;
			//for(z=0; z<=k; z++)
		}
	}
	
	printf("%d\n", count);
	
	
	return 0;
}


Measured memory_bytes: 128
N=int(input())
A=[int(input()) for _ in range(N)]
mod=10**9+7
B=[A[0]-1]
for i in range(1,N):
  if A[i]!=A[i-1]:
    B.append(A[i]-1)
n=len(B)
used=[-1]*(max(A)+1)
used[B[0]]=0
dp=[0]*n
dp[0]=1
for i in range(1,n):
  if used[B[i]]==-1:
    dp[i]=dp[i-1]
  else:
    a=used[B[i]]
    dp[i]=(dp[i-1]+dp[a])%mod
  used[B[i]]=i
print(dp[-1])

Measured memory_bytes: 28428
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[105];
struct node{
    int x,y;
}b[105];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
        scanf("%d",a+i);
    sort(a,a+n);
    if(a[0]==a[n-1]){
        printf("0\n");
        return 0;
    }
    int l=0;
    int q=a[0],p=a[n-1];
    b[l].x=a[0],b[l].y=1;
    for(int i=1;i<n;i++){
        if(a[i]==b[l].x)
            b[l].y++;
        else{
            l++;
            b[l].x=a[i];
            b[l].y=1;
        }
    }
    int sum=800000009;
    for(int i=q;i<=p;i++){
        int sum2=0;
        for(int j=0;j<=l;j++){
        //        printf("%d %d %d\n",b[j].x,b[j].y,i);
            sum2+=(b[j].x-i)*(b[j].x-i)*b[j].y;
        }
        if(sum2<sum)
            sum=sum2;
    }
    printf("%d\n",sum);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265359
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef vector<pair<ll,ll> > vpii;
typedef vector<ll> vi;
const ll INF=1e13+7;
void input(ll *a,ll n){
    for(ll i=0;i<n;i++)cin>>a[i];
}
ll lcm(ll a,ll b){return (a*b)/__gcd(a,b);}
bool isprime(ll n){
    if(n==1)return false;
    if(n==2 || n==3)return true;
    for(ll i=2;i<=sqrt(n);i++){
        if(n%i==0)return false;
    }
    return true;
}
//ll x[100001]={0};
ll a[200001]={0};
//ll b[100001]={0};

//bool c[1000001]={0};
//vector<pair<ll,ll> > adj[100001];
//vector<ll> adj[200001];
//vpii edges;
//bool visited[200001]={0};
//bool color[200001]={0};
//ll dist[100001]={0};
ll binary_expon(ll a,ll b){
    ll res=1;
    while(b){
        if(b%2)res=(res*a)%INF;
        a=(a*a)%INF;
        b/=2;
    }
    return res%INF;
}

void sieve(ll n,bool *a)
{
    for (ll p=2; p*p<=n; p++){
        if (!a[p]){
            for (ll i=p*p;i<=n;i+=p)
                a[i]=true;
        }
    }
}

ll fact(ll n){
    ll res=1;
    for(ll i=1;i<=n;i++)res*=i;
    return res;
}

double distance(ll x1,ll y1,ll x2,ll y2){
    return (sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)));
}

/*void tree_dfs(ll curr,ll prev){
    for(auto u:adj[curr]){
        if(u!=prev){
            tree_dfs(u,curr);
        }
    }
}*/

/*void dfs(ll x,ll y){
    if(x<0 || y<0 || x>=n || y>=m)return;
    //if(grid[x][y]!=color)return;
    if(visited[x][y] || Map[x][y]=='#'){
        //f=true;
        return;
    }
    visited[x][y]=true;
    Map[x][y]='#';
    //if(px!=(x+1) || py!=y)
        dfs(x+1,y);
    //if(px!=(x-1) || py!=y)
        dfs(x-1,y);
    //if(px!=(x) || py!=y+1)
        dfs(x,y+1);
    //if(px!=(x) || py!=y-1)
        dfs(x,y-1);
}*/

/*bool isVowel(char c){
    return(c=='a'||c=='e'||c=='i'||c=='o'||c=='u');
}*/
//ll grid[1001][1001]={0};
/*void dfs(ll s){
    if(visited[s])return;
    visited[s]=true;
    for(auto u:adj[s]){
        dfs(u);
    }
}*/
//set<pair<ll,ll> >edges;
/*vector<ll> z(string s) {
    ll n=s.length();
    vector<ll> z(n);
    ll x=0,y=0;
    for(ll i=1;i<n;i++) {
        z[i]=max(0ll,min(z[i-x],y-i+1));
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]]){
            x = i; y = i+z[i]; z[i]++;
        }
     }
    return z;
}*/

void solve(){

    ll n,w;
    cin>>n>>w;
    vector<vector<ll> >dp(n+1,vector<ll>(w+1)); 
    vpii v(n+1);
    for(ll i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
    }

    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=w;j++){
            dp[i][j]=dp[i-1][j];
            if(j-v[i-1].first>=0)
                dp[i][j]=max((ll)dp[i][j],dp[i-1][j-v[i-1].first]+v[i-1].second);
        }
    }
    cout<<dp[n][w];

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    //sieve(1000001,c);
    ll t=1;
    //cin>>t;
    for(ll i=0;i<t;i++){
        solve();
    }
}


Measured memory_bytes: 83036
from sys import stdin
r = 0

for i in range(500):
    if i ** 5 - (i - 1) ** 5 > 10 ** 9:
        r = i

x = int(stdin.readline().rstrip())

for a in range(-r, r):
    for b in range(-r, r):
        if a ** 5 - b ** 5 == x:
            print(a, b)
            break
    else:
        continue
    break



Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll n,c,k;
  cin >> n >> c >> k;
  vl t(n);
  rep(i,n){
    cin >> t[i];
  }
  sort(t.begin(),t.end());
  ll bus=1;
  ll start=t[0];
  ll i=0;
  ll cnt=0;
  while(i<n){
    if(start+k>=t[i]&&cnt<c){
      cnt++;
    }
    else{
      start=t[i];
      cnt=1;
      bus++;
    }
    i++;
  }
  cout << bus << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<limits.h>

int main(){
	int diff[100000]={0};
	int n,i,temp;
	int max=0;
	int isEven=0;
	scanf("%d",&n);

	scanf("%d",&temp);
	diff[temp]++;
	if(temp>max){
			max=temp;
	}

	if(temp%2==0){
		isEven=1;
	}
	for(i=1;i<n;i++){
		scanf("%d",&temp);
		diff[temp]++;
		if(temp>max){
			max=temp;
		}
	}
	
/* 	for(i=0;i<=max;i++){
		printf("%d\n",diff[i]);
	} */
	
	int isPossible=1;
	
	if(isEven){//diffが1020202...{02}の並びになる
		for(i=0;i<=max;i++){
			if(i==0){
				if(diff[i]!=1){
					isPossible--;
					break;
				}
			}else if(i%2==1){
				if(diff[i]!=0){
					isPossible--;
					break;
				}
			}else{//iが0以外の偶数なので2になるべき
				if(diff[i]!=2){
					isPossible--;
					break;
				}
			}
		}
	}else if(!isEven){//diffが020202...{02}の並びになる
		for(i=0;i<=max;i++){
			if(i%2==0){//iが偶数ならdiff[i]は0になるべき
				if(diff[i]!=0){
					isPossible--;
					break;
				}
			}else{//iが奇数なら2
				if(diff[i]!=2){
					isPossible--;
					break;
				}
			}
		}
	}
	
	long long int pattern=1;
	
	if(!isPossible){
		puts("0");
	}else{
		if(isEven){//2^(max/2)通り
			for(i=0;i<max/2;i++){
				pattern *=2;
				pattern %= 1000000007;
			}
			printf("%lld\n",pattern);
		}else{//2^(max+1)/2
			for(i=0;i<(max+1)/2;i++){
				pattern *=2;
				pattern%= 1000000007;
			}
			printf("%lld\n",pattern);
		}
		
	}
	
	return 0;
}

Measured memory_bytes: 512