akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
//#define PI 3.14159265358979

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	int M;
	if (N > 0)
		M = A[0].size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1 << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(11);
	}
};
initializer _____;

int N, M, K, T, Q;
signed main() {
	int H, W;
	cin >> H >> W;
	int h, w;
	cin >> h >> w;
	if (H % h == 0 && W % w == 0) {
		cout << "No" << endl;
		return 0;
	}
	bool f = false;
	if (W % w == 0) {
		swap(H, W);
		swap(h, w);
		f = true;
	}
	vector< int > ans(W);
	int sum = 0;
	queue< int > q;
	rep(i, W) {
		if (sum + 1000 >= w * 1000) {
			ans[i] = -sum - 1;
		} else {
			ans[i] = 1000;
		}
		sum += ans[i];
		q.push(ans[i]);
		if (q.size() >= w) {
			sum -= q.front();
			q.pop();
		}
	}
	cout << "Yes" << endl;
	rep(i, f ? W : H) {
		rep(j, f ? H : W) {
			cout << ans[f ? i : j] << " ";
		}
		cout << endl;
	}
	return 0;
}

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

int main()
{
	int a,b;
	cin >> a>>b;
	if (a <= 0 && b >= 0)
		cout << "Zero" << endl;
	else if (a > 0 && b > 0)
		cout << "Positive" << endl;
	else
	{
		if ((b - a) % 2 == 0)
			cout << "Negative" << endl;
		else
			cout << "Positive" << endl;
	}
	return 0;
}

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

#define mod      1e9+7;
#define INF      1e9+9;
#define ps(x,y)  fixed<<setprecision(y)<<x
# define PI 3.14159265358979323846264338327950 L
typedef long long ll;
typedef unsigned long long ull;
bool ispalin(string s){
	int n=s.length();
	for(int i=0;i<n/2;i++){
		if(s[i]!=s[n-1-i])
			return false;
	}
	return true;
}
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
	string s1,s2,s;
	cin>>s;
	int n=s.length(); 
	s1=s.substr(0,n/2);
	s2=s.substr(n/2+1,n/2);
	//cout<<s1<<"  "<<s2<<endl;
	if(ispalin(s1) && ispalin(s2) && ispalin(s)){
		cout<<"Yes\n";
		return 0;
	}
	cout<<"No\n";
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  long ans = 1000000;
  vector<int>data(n);
  for(int i = 0;i < n;i++){
    cin >> data[i];
  }
  sort(data.begin(),data.end());
  for(int i = data[0];i <= data[n-1];i++){
    long a = 0;
    for(int j = 0;j < n;j++){
      a += (data[j]-i)*(data[j]-i);
    }
    if(ans > a){
      ans = a;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#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.at(i);
  }
  vector<long> R(N + 1);
  for (int i = 1; i < N + 1; i++) {
    R.at(i) = R.at(i - 1) + A.at(i - 1);
  }
  long ans = 0;
  for (long l = 0, r = 0, now = 0; r < N; r++) {
    now ^= A.at(r);
    while (l <= r && now != R.at(r + 1) - R.at(l)) {
      now ^= A.at(l++);
    }
    ans += r - l + 1;
  }
  cout << ans << "\n";
}


Measured memory_bytes: 5620
n = int(input())
shops = [0 for i in range(n)]
for i in range(n):
    s = input()
    s = s.replace(" ","")
    s = int(s,2)
    shops[i] = s
# print(shops)
prof = [[] for i in range(n)]
for i in range(n):
    prof[i] = list(map(int,input().split()))

ans = -1000000000000
for i in range(1,1024):
    score = 0
    for j in range(n):
        temp = i&shops[j]
        num = bin(temp).count("1")
        score += prof[j][num]
    if score > ans:
        ans = score
print(ans)


Measured memory_bytes: 3064
/*
 * Code Author: Akshay Miterani
 * DA-IICT
 */
import java.io.*;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;

public class Main {

	static double eps=(double)1e-6;
	static long mod=(long)1e9+7;
	static final long INF = Long.MAX_VALUE / 100;
	public static void main(String args[]) throws FileNotFoundException{
		InputReader in = new InputReader(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		//----------------My Code------------------
		int n=in.nextInt();
		long k=in.nextInt();
		long a[]=new long[n];
		for(int i=0;i<n;i++){
			a[i]=in.nextLong();
		}
		long ans=0;
		for(int i=0;i<n-1;i++){
			long del=a[i+1]+a[i]-k;
			if(del<=0)
				continue;
			if(del<=a[i+1]){
				a[i+1]-=del;
			}
			else{
				a[i]-=del-a[i+1];
				a[i+1]=0;
			}
			ans+=del;
		}
		System.out.println(ans);
		out.close();
		//----------------The End------------------

	}
	static boolean isPrime(long x){
		for(int i=2;i<=Math.sqrt(x)+1;i++){
			if(x%i==0 && i!=x)
				return false;
		}
		return true;
	}
	static long modulo(long a,long b,long c) {
		long x=1;
		long y=a;
		while(b > 0){
			if(b%2 == 1){
				x=(x*y)%c;
			}
			y = (y*y)%c; // squaring the base
			b /= 2;
		}
		return  x%c;
	}
	static long gcd(long x, long y)
	{
		if(x==0)
			return y;
		if(y==0)
			return x;
		long r=0, a, b;
		a = (x > y) ? x : y; // a is greater number
		b = (x < y) ? x : y; // b is smaller number
		r = b;
		while(a % b != 0)
		{
			r = a % b;
			a = b;
			b = r;
		}
		return r;
	}
	static class Pair implements Comparable<Pair>{
		int x;
		int y;

		Pair(int xx,int yy){
			x=xx;
			y=yy;
		}
		@Override
		public int compareTo(Pair o) {
			if(Long.compare(this.x, o.x)!=0)
				return Long.compare(this.x, o.x);
			else
				return Long.compare(this.y, o.y);
		}
	}
	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream inputstream) {
			reader = new BufferedReader(new InputStreamReader(inputstream));
			tokenizer = null;
		}

		public String nextLine(){
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}
		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 long nextLong() {
			return Long.parseLong(next());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}     

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

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

    ll x = min(B-1, N);

    ll ans = (A * x) / B - A * (x / B);

    cout << ans << endl;

    return 0;
}



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

int main()
{
    int i,j=0,k=0,m,c=0;
    scanf("%d",&m);
    char ara1[m],ara2[m],ara3[m+m];
    scanf("%s%s",ara1,ara2);
    int len1=strlen(ara1),len2=strlen(ara2);
    for(i=0;i<m;i++)
    {
        ara3[c]=ara1[j];j++;c++;
        ara3[c]=ara2[k];k++;c++;


    }
    ara3[c]='\0';
    printf("%s\n",ara3);



    return 0;
}


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

int main(void){
    vector<bool> flg(101);
    fill(flg.begin(), flg.end(), true);
    int x, n;
    cin >> x >> n;
    rep(i, n){
        int p;
        cin >> p;
        flg[p] = false;
    }
    int ans = 101, mn = abs(x - 101);
    rep(i, 101){
        if(flg[i]){
            if(abs(x - i) < mn || (i < ans && abs(x - i) == mn)){
                mn = abs(x - i);
                ans = i;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[(" << __LINE__ << ") " << (#x) << "]: " << x << endl;

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

    int k, n;
    cin >> k >> n;
    int a[n];
    for (int& e : a) cin >> e;
    sort(a, a+n);

    int mx = 0;
    for (int i=0; i<n-1; i++) {
        mx = max(mx, a[i+1]-a[i]);
    }
    mx = max(mx, k-a[n-1]+a[0]);
    cout << k-mx << "\n";
}


Measured memory_bytes: 1024
N, M = map(int, input().split())

if N == 1:
    print(1)
else:
    s = [-1] * N
    s[0] = 1
    s[1] = 1

    for m in range(0, M):
        i = int(input())
        s[i] = 0

    for n in range(2, N):
        if s[n] == 0:
            continue
        s[n] = s[n - 1] + s[n - 2]

    print((s[N-1] + s[N-2]) % 1000000007)


Measured memory_bytes: 465808
N = int(input())
A = list(map(int,input().split()))

money=1000
pos = 1
kabu = 0

for i in range(1,N):
    if A[i-1]<A[i]:
        kabu = money//A[i-1]
        money += kabu*(A[i]-A[i-1])
            
print(money)

Measured memory_bytes: 9180
import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n)
    a = list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(n):
        bit.add(i+1, a[i])
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.sum(x) - bit.sum(p))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()


Measured memory_bytes: 90112
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Runtime.InteropServices;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;
    const char White = '.';
    const char Black = '#';

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var n = int.Parse(input.ReadLine());

        var hash = new HashSet<int>();
        for(int i=0; i<n; i++) {
            var a = int.Parse(input.ReadLine());
            if (hash.Contains(a)) hash.Remove(a);
            else hash.Add(a);
        }

        return hash.Count();
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 19420
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

struct td{
    int t;
    int d;
};

bool cmp_d   (struct td& lhs, struct td& rhs){ return lhs.d < rhs.d; }
bool cmp_gr_d(struct td& lhs, struct td& rhs){ return lhs.d > rhs.d; }

int main(){
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    
    uint N, K; cin >> N >> K;
    vector<struct td> vTD(N); for(uint i=0; i<N; ++i){ cin >> vTD[i].t >> vTD[i].d; }
    sort(vTD.begin(), vTD.end(), cmp_gr_d);
    
    unordered_map<int, int> htUN; // a hash table for counting number of used types
    vector<struct td> vTD_rm;     // for remove
    vector<struct td> vTD_add;    // for add
    
    int64 sum =0ll;
    for(uint i=0; i<K; ++i){
        sum += vTD[i].d;
        ++htUN[ vTD[i].t ];
        if(htUN[ vTD[i].t ]>=2){ vTD_rm.push_back( vTD[i] ); }
    }
    sort(vTD_rm.begin(), vTD_rm.end(), cmp_d);
    
    for(uint i=K; i<N; ++i){
        if( htUN[ vTD[i].t ] != 0 ){ continue; }
        vTD_add.push_back( vTD[i] );
    }
    sort(vTD_add.begin(), vTD_add.end(), cmp_gr_d);
    
    int64 numT = K - vTD_rm.size(); // num of type
    int64 point = sum + numT*numT;
    uint ri=0, ai=0;
    while( ri<vTD_rm.size() && ai<vTD_add.size() ){
        if( htUN[ vTD_rm [ri].t ] == 1 ){ ++ri; continue; }
        if( htUN[ vTD_add[ai].t ] >= 1 ){ ++ai; continue; }
        
        sum -= vTD_rm [ri].d; --htUN[ vTD_rm [ri].t ]; ++ri;
        sum += vTD_add[ai].d; ++htUN[ vTD_add[ai].t ]; ++ai;
        
        ++numT;
        
        int64 tmp = sum + numT * numT;
        point = max(point, tmp);
    }
    cout << point << endl;
    
    return 0;
}


Measured memory_bytes: 5540
n, k = map(int, input().split())
A = list(map(int, input().split()))

count_left = [0 for i in range(n)]
count_right = [0 for i in range(n)]

for i in range(len(A)):
    for j in range(i):
        if A[i] < A[j]:
            count_left[i] += 1
    
    for j in range(i + 1, n):
        if A[i] < A[j]:
            count_right[i] += 1

mod = 10 ** 9 + 7 
# print(count_left)
# print(count_right)
ans = 0
for i in range(n):
    ans += k * count_left[i]
    ans %= mod
    ans += (count_left[i] + count_right[i]) * (k - 1) * k // 2
    ans %= mod
print(ans)


Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int a,b,c;
    cin >> a;
    cin >> b;
    cin >> c;
    int A = min(a,min(b,c));
    int C = max(a,max(b,c));
    int B = a+b+c-A-C;
    cout << A << " " << B << " "<< C;
    cout << endl;
}



Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
const ll INF=1LL<<60;
int main(){
    string s;cin >> s;
    if(s=="AAA"||s=="BBB"){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
}

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

int main(){
  int A,B;
  bool a[3]={1,1,1};
  cin>>A>>B;
  a[A-1]=false;
  a[B-1]=false;
  for(int i=0;i<3;i++){
    if(a[i]!=false){
      cout<<i+1;
    }
    //cout<<a[i];
  }
}

    


Measured memory_bytes: 256
<?php
$n = trim(fgets(STDIN));
$a = explode(' ', trim(fgets(STDIN)));

asort($a);

$ans = [];

$i = 0;
foreach ($a as $k => $v) {
    $ans[$i] = $k + 1;
    $i++;
}

echo implode(" ", $ans) . PHP_EOL;


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

using namespace std;

template <class T>inline T updmax(T& a, T b) {return a = max(a, b);}
template <class T>inline T updmin(T& a, T b) {return a = min(a, b);}

class Solution {
public:
	void solve() {
		int n;
		cin >> n;
		vector<int> a(n, 0);
		for(int i=0; i<n; i++)cin >> a[i];
		vector<int> c(n, 0);
		for(int i=0; i < n; i++)c[a[i]-1]++;
		sort(c.begin(), c.end(), greater<int>());
		while(c.back()==0)c.pop_back();
		reverse(c.begin(), c.end());
		int k = c.size();
		vector<int> s(k+1, 0);
		for(int i=0; i < k; i++){
			s[i+1] = s[i] + c[i];
		}
		for(int t=1; t <= n; t++){
			int ok = 0, ng = n/t+1;
			while(abs(ok-ng)>1){
				int mid = (ok+ng)/2;
				bool flag = false;
				int ac = n;
				auto id = distance(c.begin(), lower_bound(c.begin(), c.end(), mid));
				ac = s[id] + (k-id)*mid;
				flag = (mid*t <= ac);
				if(flag)ok=mid;
				else ng=mid;
			}
			cout << ok << "\n";
		}
		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 4224
T = [[60, 80, 100, 120, 140, 160], [2, 5, 10, 15, 20, 25], [600, 800, 1000, 1200, 1400, 1600]].transpose.freeze
loop do
  n = gets.to_i
  break if n.zero?
  p n.times.map {
    x, y, h, w = gets.split.map(&:to_i)
    q = T.find {|a, b, _| x + y + h <= a && w <= b }
    q ? q[2] : 0
  }.inject 0, :+
end

Measured memory_bytes: 8992
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
int a[100010]; 
int main() {
	int n;
	cin >> n;
	rep(i,n) cin >> a[i];
	sort(a,a+n);
	ll ans = a[n-1] - a[0];
	for (int i = 1; i < n/2; i++)
	{
		ans += a[n-i] - a[i];
		ans += a[n-i-1] - a[i-1];
	}
	if (n % 2 == 1) {
		ans += max(a[n/2+1]-a[n/2],a[n/2]-a[n/2-1]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4024
/**
 *    author:  tourist
 *    created: 13.10.2018 16:06:24       
**/
#include <bits/stdc++.h>

using namespace std;

const int md = (int) 1e9 + 7;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  a %= md;
  if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(k), b(k);
  for (int i = 0; i < k; i++) {
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
  }
  vector<int> ways(n + 1);
  ways[0] = 1;
  for (int i = 1; i <= n; i++) {
    ways[i] = mul(ways[i - 1], 2 * i - 1);
  }
  int ans = ways[n - k];
  vector<vector<int>> dp(2 * n, vector<int>(2 * n, 0));
  vector<vector<int>> dps(2 * n, vector<int>(2 * n, 0));
  for (int x = 2 * n - 1; x >= 0; x--) {
    for (int y = x + 1; y < 2 * n - 1; y += 2) {
      int ok = 1;
      int sum = 0;
      for (int i = 0; i < k; i++) {
        int cc = (x <= a[i] && a[i] <= y) + (x <= b[i] && b[i] <= y);
        if (cc == 1) {
          ok = 0;
          break;
        }
        sum += cc / 2;
      }
      if (!ok) {
        continue;
      }
      int u = (y - x + 1) / 2 - sum;
      int v = (n - k) - u;
      dp[x][y] = dps[x][y] = ways[u];
      for (int z = x + 1; z < y - 1; z += 2) {
        sub(dp[x][y], mul(dp[x][z], dps[z + 1][y]));
      }
      add(ans, mul(dp[x][y], ways[v]));
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3072
#include <stdio.h>
int main(){
	double a,b,c,d,e,f,g,h;
	while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f,&g,&h)!=EOF){
     if(f<=d && b<=h){
		 if(e<=c && a<=g){
			 printf("YES\n");
			 continue;
		 }}
	 printf("NO\n");
	}
	return 0;
}

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

int main() {
  int A,B; cin >>A >>B;
  cout <<(A-1)*(B-1) <<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

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

  if (N == 1) {
    cout << "Hello World" << endl;
  } else {
    int A, B;
    cin >> A >> B;
    cout << A + B << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#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)
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

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

    int n;
    cin >> n;
    int k = 1;
    for (; ; ++k) {
        if (k*(k-1)/2 == n) break;
        if (k*(k-1)/2 > n) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    vector<vector<int>> ans(k);
    int num = 1;
    for (int l = 0; l < k; ++l) {
        for (int r = l+1; r < k; ++r) {
            ans[l].push_back(num);
            ans[r].push_back(num);
            num++;
        }
    }
    cout << k << endl;
    rep(i, k) {
        cout << k-1 << " ";
        rep(j, k-1) cout << ans[i][j] << (j == k-2 ? '\n' : ' ');
    }

}


Measured memory_bytes: 4088
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// #define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;

int t[4*N][26];

int query(int v, int tl, int tr, int l, int r, int i) {
	if (l > r) 
		return 0;
	if (l == tl && r == tr) {
		return t[v][i];
	}
	int tm = (tl + tr) / 2;
	return query(v*2, tl, tm, l, min(r, tm), i) + query(v*2+1, tm+1, tr, max(l, tm+1), r, i);
}

void update(int v, int tl, int tr, int pos, int new_val, int i) {
	if (tl == tr) {
		t[v][i] = new_val;
	} else {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update(v*2, tl, tm, pos, new_val, i);
		else
			update(v*2+1, tm+1, tr, pos, new_val, i);
		t[v][i] = t[v*2][i] + t[v*2+1][i];
	}
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i = 0; i < n; i++) {
		update(1, 0, n - 1, i, 1, s[i] - 'a');
	}
	int q;
	cin >> q;
	while(q--) {
		int c;
		cin >> c;
		if(c == 1) {
			int pos;
			char ch;
			cin >> pos >> ch;
			for(int i = 0; i < 26; i++) {
				if(query(1, 0, n - 1, pos - 1, pos - 1, i)) {
					update(1, 0, n - 1, pos - 1, 0, i);
					break;
				}
			}
			update(1, 0, n - 1, pos - 1, 1, ch - 'a');
		}
		else {
			int l, r;
			cin >> l >> r;
			int ans = 0;
			for(int i = 0; i < 26; i++) {
				if(query(1, 0, n - 1, l - 1, r - 1, i)) {
					ans++;
				}
			}
			cout << ans << endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 109468
import math
from itertools import combinations
N,D = map(int,input().split())
X = [list(map(float, input().split())) for i in range(N)]
counter = 0
for x0,x1 in combinations(X, 2):
    if math.sqrt(sum([(a-b)**2 for a, b in zip(x0,x1)])).is_integer():
        counter+=1
print(counter)


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a;
	cin>>a;
	if(a>17|a==4||a==7||a==8||a==11||a==12||a==14||a==15||a==16)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
} 

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long a =1, b=1;
    for (int i =1; i<=N; i++) {
      long T = sc.nextInt();
      long A = sc.nextInt();
      long k = Math.max(Math.max(1,a/T),Math.max(1,b/A));
      while (T * k < a  || A * k < b) {
        k++;
      }
      a = T * k;
      b = A * k;
    }
    System.out.println(a + b);
  }
}

Measured memory_bytes: 25396
#include<iostream>
#include<cstdio> 
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<cmath>
#include<algorithm>
#define lson node<<1,st,mid
#define rson node<<1|1,mid+1,ed
#define mem(a,x) memset(a,x,sizeof(a))
#define me(a) memset(a,0,sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) x&(-x)
typedef long long ll;
const ll mod=1e9+7;
const ll INF=0x3f3f3f3f;
const ll maxn=1e6+5;
const double pi = acos(-1.0);
using namespace std;
//ll a[maxn];
//int main(){
//	ll n;
////	a[1]=1;
////	a[2]=2;
////	a[3]=3;
////	for(ll i=4;i<=100;i++){
////		a[i]=i*a[i-2];
////	}
////	for(ll i=1;i<=100;i++){
////		cout<<a[i]<<endl;
////	}
//	cin>>n;
//	if(n<10) cout<<"0"<<endl;
//	n-=10;
//	if(n%2==0) {
//		if(n%10==0) n=n/10;
//		else n/=10+1;
//	}
//	else cout<<"0"<<endl;
//}
ll a[maxn];
int main(){
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
	}
	ll j=1;
	for(ll i=1;i<=n;i++){
		if(a[i]==j) j++;
	}
	if(j==1) cout<<"-1"<<endl;
	else cout<<n+1-j<<endl;
}

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

int main(){
        int H,W;
        cin >> H >> W;
        string a[H],ans[H];
        for(int i=0; i<W+2; i++) {
                cout << '#';
        }
        cout <<endl;
        for(int i=0; i<H; i++) {
                cin >> a[i];
                ans[i] = '#' + a[i] + '#';
                cout << ans[i] << endl;
        }
        for(int i=0; i<W+2; i++) {
                cout << '#';
        }
        return 0;

}


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

int main() {
    int n,x;
    cin>>n>>x;
    vector<int> a(n,0);
    for (size_t i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    int sum = 0;
    for (size_t i = 0; i < n; i++)
    {
        if (sum + a[i]>x){
            cout << i<<endl;
            return 0;
        }
        else {
            sum+= a[i];
        }
    }
    if (sum == x) {
        cout << n<<endl;
    }
    else {
        cout << n-1<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
	long long n,i,j,k,count=0,ans=0,l,r,x,y,sum=0,mx=0,m;
	cin>>n>>m;
	long long a[m];
	for(i=0;i<m;i++)
	{
	    cin>>a[i];
	    sum+=a[i];
	}
    if(sum>n)
    cout<<-1;
    else
    cout<<n-sum;
	return 0;
}

Measured memory_bytes: 3720
N = int(input())
P = list(map(int, input().split()))

ans = 0
tmp_min = P[0]

for i in range(N):
    if P[i] <= tmp_min:
        ans += 1
        tmp_min = min(P[i], tmp_min)
    else:
        tmp_min = min(P[i], tmp_min)

print(ans)

Measured memory_bytes: 24744
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
  int n;
  cin >> n;
  int a[n];

  for (int i = 0; i < n; i++)
  {
    int num;
    cin >> num;
    a[num-1] = i+1;
  }

  for (int i = 0; i < n; i++)
  {
    cout << a[i] << " ";
  }
  cout << "\n";
  
  return 0;
}

Measured memory_bytes: 1152
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}

template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}


signed main(void) {
	int n;
	cin >> n;
	vector<int>s(n);
	int ret = 0;
	rep(i, n) {
		cin >> s[i];
		ret += s[i];
	}
	if (ret % 10 != 0) {
		print(ret);
		return 0;
	}
	else {
		sort(s.begin(), s.end());
		rep(i, n) {
			if (s[i] % 10 != 0) {
				print(ret - s[i]);
				return 0;
			}
		}
		print(0);
	}

}

Measured memory_bytes: 3628
# https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
rr = range


def read_ints():
    return list(map(int, read().split()))


K, T = read_ints()
A = read_ints()
if T == 1:
    # コーナーケース
    print(K - 1)
    exit()

# 差が最も少なくなるように二分割すれば良い
# 二分探索でもいいが線形探索で愚直に合計値を計算しても十分間に合う
A.sort()
ans = 2**31
for i in rr(1, T):
    r = sum(A[:i])
    l = sum(A[i:])
    ans = min(ans, abs(r - l))
print(max(ans - 1, 0))


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

struct p{
  int co,x,y;
  p(int a,int b,int c){
    co=a;
    x=b;
    y=c;
  }
};
int a[1000][1000],b[1000][1000];
int main (){
  int h,w;
  queue<p> Q; 
  char ch;
  cin >>h>>w;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> ch;
      if(ch == '.'){
	a[i][j] = -1;
	Q.push(p(0,j,i));
      } else a[i][j] = ch-'0';
      b[i][j] = 0;
    }
  }
  int res = 0;
  while( !Q.empty() ){
    p np = Q.front();
    Q.pop();
    res = np.co;
    for(int i=-1;i<=1;i++)
      for(int j=-1;j<=1;j++){
	if(i==0 && j==0) continue;
	int nx = np.x+i;
	int ny = np.y+j;
	if(0>nx || nx>w-1 || 0>=ny || ny>h-1) continue;
	b[ny][nx]++;
	if(a[ny][nx] == b[ny][nx]) Q.push(p(np.co+1,nx,ny));
      }
  }
  cout << res<<endl;
  return 0;
}

Measured memory_bytes: 9296
import java.util.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args) {
    Main main = new Main();
    System.out.println(main.solve());
  }

  int n;
  int a[];

  public Main() {
    Scanner sc = new Scanner(System.in);
    try {
      n = sc.nextInt();
      a = IntStream.range(0, n - 1).map(i -> sc.nextInt()).toArray();
    } finally {
      sc.close();
    }
  }

  int solve() {
    int ans = 0;
    for (int i = 0; i < n; i++) ans += calc(i);
    return ans;
  }

  private int calc(int i) {
    if (i == 0) return a[0];
    if (i == n - 1) return a[n - 2];
    return a[i - 1] < a[i] ? a[i - 1] : a[i];
  }
}


Measured memory_bytes: 36456
#![allow(non_snake_case, unused_assignments, unused_mut, dead_code)]
use proconio::fastout;
use proconio::input;
//use proconio::marker::Usize1;
use proconio::marker::Chars;
//use std::collections::HashSet;
// use std::cmp::*;
//use std::collections::VecDeque;
//use std::collections::BTreeSet;

#[fastout]
fn main() {
    input! {
       N: usize,
       S:Chars
    }
    let mut r = 0i64;
    let mut g = 0i64;
    let mut b = 0i64;
    for &c in S.iter() {
        if c == 'R' {
            r += 1;
        }
        if c == 'G' {
            g += 1;
        }
        if c == 'B' {
            b += 1;
        }
    }
    let mut ans = r * g * b;

    for i in 0..(N - 1) {
        for j in (i + 1)..N {
            let k = 2 * j - i;
            if k >= N {
                continue;
            }
            if S[i] != S[j] && S[j] != S[k] && S[k] != S[i] {
                ans -= 1;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2164
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n;
    double ans = 0.0;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v.at(i);
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < n-1; i++) {
        if (i == 0) ans = (v.at(i) + v.at(i+1)) / 2.0;
        else ans = (ans + v.at(i+1)) / 2.0;
    }
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> vi;

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

	string w;
	cin >> w;
	int s=0;
	set<char> dif;
	multiset<char> many;
	for(int i=0; i<w.size(); i++) {
		dif.insert(w[i]);
		many.insert(w[i]);
	}
	for(auto i : dif) {
		if (many.count(i) % 2 == 0) {
			s++;
		}
	}
	if(s==dif.size()) {
		cout << "Yes";
		return 0;
	}
	cout << "No";
	
	return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16

ll n,mod;
vector<int> g[100010];
ll dp[100010];
ll res[100010];

void dfs(int v,int pre){
  for(int nv : g[v]){
    if(nv==pre)continue;
    dfs(nv,v);
  }
  dp[v]=1;
  for(int nv : g[v]){
    if(nv==pre)continue;
    (dp[v]*=(dp[nv]+1))%=mod;
  }
}

void dfs2(int v,int pre,ll t0){
  res[v]=dp[v]*(t0+1)%mod;
  vector<int> ch;
  for(int nv : g[v]){
    if(nv==pre)continue;
    ch.push_back(nv);
  }
  int sz=ch.size();
  vector<ll> prf(sz+1,1);
  vector<ll> suf(sz+1,1);
  rep(i,sz){
    prf[i+1]=prf[i]*(dp[ch[i]]+1)%mod;
  }
  for(ll i=sz-1;i>=0;i--){
    suf[i]=suf[i+1]*(dp[ch[i]]+1)%mod;
  }

  rep(i,sz){
    ll nt0=(((t0+1)*prf[i])%mod)*suf[i+1]%mod;
    dfs2(ch[i],v,nt0);
  }
}

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

  cin>>n>>mod;
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(0,-1);
  dfs2(0,-1,0);

  rep(i,n)cout<<res[i]<<endl;

  return 0;
}


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

typedef long long ll;

const int N = 100005;
int n, b[2 * N];
bool vis[N];
ll ans, suma, sumb;
pair<int, int> a[N];

int val(int x) {
	return x > 0 ? a[x].first : a[-x].second;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &a[i].first, &a[i].second);
		suma += a[i].first, sumb += a[i].second;
		b[2 * i - 1] = i, b[2 * i] = -i;
	}
	ans = min(suma, sumb);
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + 2 * n, [](int x, int y) { return val(x) < val(y); });
	ll sum = 0;
	for (int i = 1; i <= n; ++i)
		sum += val(b[i]);
	for (int i = 1; i <= n; ++i)
		if (vis[abs(b[i])]) {
			printf("%lld\n", min(ans, sum));
			return 0;
		} else
			vis[abs(b[i])] = true;
	for (int i = n + 1; i <= 2 * n; ++i)
		ans = min(ans, sum - (b[i] + b[n] ? val(b[n]) : val(b[n - 1])) + val(b[i]));
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1920
import java.util.Scanner

import scala.collection.mutable.ArrayBuffer


object Main {

  def read() = {
    val sc = new Scanner(System.in)

    val n = sc.nextInt()
    n
  }

  case class Edge(a: Int,b: Int)

  case class Graph(m :Int, edges: IndexedSeq[Edge])

  def solve(n: Int):  Graph = {
    val edges = ArrayBuffer.empty[Edge]
    if(n%2== 0){
      for(i <- 1 to n){
        for(j <- i+1 to n){
          if(i + j != n + 1){
            edges.append(Edge(i,j))
          }
        }
      }
    }else{
      for(i <- 1 to n){
        for(j <- i+1 to n){
          if(i + j != n){
            edges.append(Edge(i,j))
          }
        }
      }
    }
    Graph(edges.length, edges.toIndexedSeq)
  }

  def output(graph: Graph): Unit ={
    println(graph.m)
    graph.edges.foreach(edge => println(edge.a + " " + edge.b))
  }

  def main(args: Array[String]): Unit = {
    val n = read()
    output(solve(n))
  }
}

Measured memory_bytes: 27788
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
using namespace std;
const long long Mod=1e9+7;
long long inv[100005],finv[100005],fac[100005];
void make(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for (int i=2;i<=1e5+2;i++){
		fac[i]=fac[i-1]*(long long)i%Mod;
		inv[i]=(Mod-inv[Mod%i]*(Mod/i)%Mod)%Mod;
		finv[i]=finv[i-1]*inv[i]%Mod;
	}
}
long long C(int a,int b){
	if (a<b){
		return 0;
	}
	return fac[a]*(finv[b]*finv[a-b]%Mod)%Mod;
}
int id[100005];
int n;
int main(){
	make();
	scanf("%d",&n);
	memset(id,-1,sizeof(id));
	int s,t;
	for (int i=0;i<=n;i++){
		int a;
		scanf("%d",&a);
		a--;
		if (id[a]==-1){
			id[a]=i;
		}
		else{
			s=id[a];
			t=i;
		}
	}
	for (int i=1;i<=n+1;i++){
		long long ans=C(n+1,i);
		ans-=C(s+n-t,i-1);
		if (ans<0){
			ans+=Mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n , k;
    cin >> n >> k;
    long long arr[100001] = {};
    for (int i = 0 ; i < n ; i++){
        int num , qty;
        cin >> num >> qty;
        arr[num] += qty;
    }
    long long count = 0;
    for (int i = 1 ; i < 100001 ; i++ ){
       count += arr[i];
       if( count >= k ){
         cout << i;
         return 0;
       }
    }
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int h, w, n;
	cin >> h >> w >> n;
	int mx = max(h,w);
	int ans = n/mx;
	if(n%mx) ans++;
	cout << ans << endl;
	return 0;
}

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

int main(int argc, char const *argv[])
{
  int S;
  cin >> S;
  int h, m, s;
  h = S/3600;
  m = (S - 3600 * h)/60;
  s = S - 3600 * h - 60 * m;
  cout << h << ":" << m << ":" << s << endl;
  return 0;
}

Measured memory_bytes: 3096
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;
 
class Program
{
    static void Main()
    {
        const int Max = 50;
        string O = Console.ReadLine();
        string E = Console.ReadLine();
        for (int i = 0; i < Max; i++)
        {
            if(i < O.Length) Console.Write(O[i]);
            else break;
            if(i < E.Length) Console.Write(E[i]);
            else break;
        }
        Console.WriteLine();
    }
}

Measured memory_bytes: 13140
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

bool is_ok(long long X, long long K, vector<long long> &S1,
           vector<long long> &S2) {
  bool res = false;

  for (int a = 0; a <= X; a++) {
    int b = X - a;
    if (a < 0 || S1.size() - 1 < a) {
      continue;
    }
    if (b < 0 || S2.size() - 1 < b) {
      continue;
    }
    if (S1[a] + S2[b] <= K) {
      res = true;
    }
  }
  return res;
}

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

  long long N, M, K;
  cin >> N >> M >> K;

  vector<long long> A(N), B(M);
  vector<long long> S1(N + 1, 0), S2(M + 1, 0);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < M; i++) {
    cin >> B[i];
  }

  for (int i = 1; i <= N; i++) {
    S1[i] = S1[i - 1] + A[i - 1];
  }
  for (int i = 1; i <= M; i++) {
    S2[i] = S2[i - 1] + B[i - 1];
  }

  long long ok = 0, ng = N + M + 1;
  while (abs(ok - ng) > 1) {
    long long mid = (ok + ng) / 2;
    if (is_ok(mid, K, S1, S2)) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  cout << ok << "\n";

  return 0;
}

Measured memory_bytes: 9524
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data',function (chunk)
{
  var x = parseInt(chunk.trim(), 10);
  var h = Math.floor(x / 3600);
  var mod = x % 3600;
  var m = Math.floor(mod / 60);
  s = mod % 60;
  console.log(h + ":" + m + ":" + s);
});

Measured memory_bytes: 15468
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
void ABC80(void);
void ABC81(void);
void ABC82(void);
void ABC83(void);
void ABC84(void);
void ABC85(void);
void ABC86(void);
void ABC87(void);
void ABC88(void);
void ABC89(void);

int main(void){
    ABC82();
}

void ABC82(){
    string s1,s2;
    cin>>s1>>s2;
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
    reverse(s2.begin(),s2.end());
    if(s1<s2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 384
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, n, ans = 0;
  scanf("%lld", &n);
  ll d[n];
  for(i = 0; i < n; ++i) scanf("%lld", &d[i]);
  for(i = 0; i < n; ++i) for(j = i + 1; j < n; ++j) ans += d[i] * d[j];
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 128
li = list(map(int,input().split()))
n = li[0]
a = li[1]
b = li[2]
ans = 0
if (b-a)%2 == 0:
    ans = (b-a)//2
else:
    if a-1>n-b:
        ans+=n-b
        ans = ans-(-(b-a)//2)
    else:
        ans+=a-1
        ans = ans-(-(b-a)//2)
print(ans)




Measured memory_bytes: 3060
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;

const int N = 2e5 + 5;

int n, a, b;
string s;
ll ra[N], rb[N], p2a[N], p2b[N];

void calc(ll* r, ll* p, int mod) {
  r[0] = 0;
  p[0] = 1;
  for(int i = 1; i <= n; i++) {
    p[i] = (p[i - 1] * 2) % mod;
    r[i] = (r[i - 1] * 2 + s[i - 1] - '0') % mod;
  }
}

int solve(int n) {
  if(n == 0) return 0;
  int mod = __builtin_popcount(n);
  return 1 + solve(n % mod);
}

int main()
{
  cin >> n >> s;
  int popcount = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == '1')
      popcount++;
  }
  a = popcount + 1;
  b = popcount - 1;
  calc(ra, p2a, a);
  if(b > 0) calc(rb, p2b, b);
  for(int i = 0; i < n; i++) {
    int cur = s[i] - '0';
    if(cur == 0) { // change to 1
      int ans = (ra[n] + p2a[n - 1 - i]) % a;
      cout << 1 + solve(ans) << endl;
    } else { // change to 0
      if(b == 0) cout << 0 << endl;
      else {
        int ans = (rb[n] - p2b[n - 1 - i]) % b;
        ans = (ans + b) % b;
        cout <<  1 + solve(ans) << endl;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 10000
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

map<char, string> preS;
int main ()
{
    preS[' '] = "101";
    preS['\''] = "000000";
    preS[','] = "000011";
    preS['-'] = "10010001";
    preS['.'] = "010001";
    preS['?'] = "000001";
    preS['A'] = "100101";
    preS['B'] = "10011010";
    preS['C'] = "0101";
    preS['D'] = "0001";
    preS['E'] = "110";
    preS['F'] = "01001";
    preS['G'] = "10011011";
    preS['H'] = "010000";
    preS['I'] = "0111";
    preS['J'] = "10011000";
    preS['K'] = "0110";
    preS['L'] = "00100";
    preS['M'] = "10011001";
    preS['N'] = "10011110";
    preS['O'] = "00101";
    preS['P'] = "111";
    preS['Q'] = "10011111";
    preS['R'] = "1000";
    preS['S'] = "00110";
    preS['T'] = "00111";
    preS['U'] = "10011100";
    preS['V'] = "10011101";
    preS['W'] = "000010";
    preS['X'] = "10010010";
    preS['Y'] = "10010011";
    preS['Z'] = "10010000";
    
    char aft[] = {' ', '.', ',', '-', '\'', '?'};

    string str;
    while (getline(cin, str)) {
        string p;
        for (int i = 0; i < str.size(); i++) {
            p += preS[str[i]];
        }
        while (p.size() % 5 != 0) {
            p += '0';
        }
        int s = 0;
        int t = 16;
        for (int i = 0; i < p.size(); i++) {
            if (i % 5 == 0) {t = 16; s = 0;}
            s += p[i] == '1' ? t : 0;
            t /= 2;
            if (i % 5 == 4) {
                if (0 <= s && s < 26) {
                    cout << (char)('A' + s);
                } else {
                    s -= 26;
                    cout << aft[s];
                }
            }
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1192
import random
import sys
import time

input = sys.stdin.readline

def main():
    # start_time = time.time()
    # while True:
    #     elapsed_time = time.time() - start_time
    #     if elapsed_time >= 2.0:
    #         print(elapsed_time)
    #         return 0
    d = int(input())
    c = list(map(int, input().split()))
    s = []
    for _ in range(d):
        s.append(list(map(int, input().split())))
    for _ in range(d):
        print(1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9864
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppiii;

char buf[1005];
void solve() {
  int n, k;
  scanf("%d %d\n%s", &n, &k, buf);
  buf[--k] += ('a' - 'A');
  printf("%s\n", buf);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
  solve();
}


Measured memory_bytes: 256