akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 1000000007

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

const int FACT_MAX = 200005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint n;
llint a[605];
vector<llint> vec, comp;
bool used[605], mark[605];
llint dp[2][605][605];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	make_fact();
	
	cin >> n;
	for(int i = 1; i <= 2*n; i++) cin >> a[i];
	
	for(int i = 1; i <= n; i++){
		llint x = a[2*i-1], y = a[2*i];
		if(x != -1 && y != -1) used[x] = used[y] = true;
		else{
			if(x != -1) vec.push_back(x);
			if(y != -1) vec.push_back(y);
		}
	}
	sort(vec.begin(), vec.end());
	
	for(int i = 1; i <= 2*n; i++){
		if(!used[i]) comp.push_back(i);
	}
	llint m = comp.size();
	if(m == 0){
		cout << 1 << endl;
		return 0;
	}
	
	for(int i = 0; i < vec.size(); i++){
		vec[i] = lower_bound(comp.begin(), comp.end(), vec[i]) - comp.begin() + 1;
		mark[vec[i]] = true;
	}
	
	llint nj, nk;
	dp[0][0][0] = 1;
	for(int i = 0; i < m; i++){
		for(int j = 0; j <= m; j++){
			for(int k = 0; k <= m; k++){
				dp[(i+1)%2][j][k] = 0;
			}
		}
		for(int j = 0; j <= m; j++){
			for(int k = 0; k <= m; k++){
				if(mark[i+1]){
					if(k+1 <= m) dp[(i+1)%2][j][k+1] += dp[i%2][j][k], dp[(i+1)%2][j][k+1] %= mod;
					if(j-1 >= 0) dp[(i+1)%2][j-1][k] += dp[i%2][j][k]*j%mod, dp[(i+1)%2][j-1][k] %= mod;
				}
				else{
					if(j+1 <= m) dp[(i+1)%2][j+1][k] += dp[i%2][j][k], dp[(i+1)%2][j+1][k] %= mod;
					if(k+1 <= m) dp[(i+1)%2][j][k+1] += dp[i%2][j][k], dp[(i+1)%2][j][k+1] %= mod;
					if(k-1 >= 0) dp[(i+1)%2][j][k-1] += dp[i%2][j][k], dp[(i+1)%2][j][k-1] %= mod;
				}
			}
		}
	}
	
	llint ans = dp[m%2][0][0];
	llint num = m/2 - (int)vec.size();
	ans *= fact[num], ans %= mod;
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template <typename T> 
struct WeightedUnionFind{
  Int n;
  T d;
  vector<Int> r,p;
  vector<T> ws;
  WeightedUnionFind(){}
  WeightedUnionFind(Int sz,T d_):
    n(sz),d(d_),r(n,1),p(n),ws(n,d){iota(p.begin(),p.end(),0);}
  Int find(Int x){
    if(x==p[x]){
      return x;
    }else{
      Int t=find(p[x]);
      ws[x]+=ws[p[x]];
      return p[x]=t;
    }
  }
  T weight(Int x){
    find(x);
    return ws[x];
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y,T w){
    w+=weight(x);
    w-=weight(y);
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y),w=-w;
    r[x]+=r[y];
    p[y]=x;
    ws[y]=w;
  }
  T diff(Int x,Int y){
    return weight(y)-weight(x);
  }
};

signed main(){
  Int n,m;
  cin>>n>>m;
  WeightedUnionFind<Int> wuf(n+1,0);
  for(Int i=0;i<m;i++){
    Int l,r,d;
    cin>>l>>r>>d;
    l--;r--;
    if(wuf.same(l,r)){
      if(wuf.diff(l,r)!=d){
	cout<<"No"<<endl;
	return 0;
      }
    }else{
      wuf.unite(l,r,d);
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}


Measured memory_bytes: 2560
A,B,K = map(int,input().split())

def eating(A,B,K):
  if A+B <= K:
    return 0, 0
  elif A > K:
    return A-K, B
  elif A <= K:
    return 0, B-(K-A)

out1, out2 = eating(A,B,K)
print(out1,out2)

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	long long int h;
	cin >> h;

	int n(0);

	while (h > 0)
	{
		h /= 2;
		n++;
	}
	long long int ans(1);

	for (int i = 0; i < n; i++)
	{
		ans *= 2;
	}
	cout << ans - 1;

	return 0;
}

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

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

const int INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;

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

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    vector<int> a(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (s[i - 2] == 'A' and s[i - 1] == 'C') {
            a[i] = 1;
        }
    }

    vector<int> b(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        b[i] = b[i - 1] + a[i];
    }

//    for (int i = 1; i <= n; i++) {
//        cout << a[i] << " " << b[i] << "\n";
//    }

    while (q--) {
        int l, r;
        cin >> l >> r;

        int ans = b[r] - b[l];
        cout << ans << "\n";
    }

    return 0;
}

Measured memory_bytes: 2640
////////////////////////
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
namespace my {
char itoc(int i) { return i + '0'; }
int ctoi(char c) { return c - '0'; }
ll gcd(ll a, ll b) {
  a = abs(a);
  b = abs(b);
  if (a < b) swap(a, b);
  while (b != 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
ll lcm(ll a, ll b) { return a * b / my::gcd(a, b); }
vector<pair<ll, ll>> primeFac(ll n) {
  vector<pair<ll, ll>> ret;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i != 0) continue;
    ll exp = 0;
    while (n % i == 0) {
      n /= i;
      exp++;
    }
    ret.push_back(make_pair(i, exp));
  }
  if (n != 1) ret.push_back(make_pair(n, 1));
  return ret;
}
}  // namespace my
////////////////////////

int main() {
  int a;
  cin >> a;
  cout << a + a * a + a * a * a << endl;
}

Measured memory_bytes: 3572
import sys

N = int(input())
L = map(int, input().split(' '))

L = sorted(L)

c = 0

if N < 3:
    print(0)
    sys.exit()

for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            li, lj, lk = L[i], L[j], L[k]
            if li == lj or lj == lk or lk == li:
                continue
            if max(li, lj, lk) < (li + lj + lk - max(li, lj, lk)):
                c += 1

print(c)

Measured memory_bytes: 9200
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    a, b, x = map(int, readline().split())

    if b == 0:
        ans = 1
    elif a == 0:
        ans = b // x + 1
    else:
        ans = b // x - (a - 1) // x

    print(ans)
    return


if __name__ == '__main__':
    main()


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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int a = in.nextInt();
            int b = in.nextInt();
            if (a + b == 15)
                out.println("+");
            else if (a * b == 15)
                out.println("*");
            else
                out.println("x");
        }

    }

    static class InputReader {
        StringTokenizer st;
        BufferedReader br;

        public InputReader(InputStream is) {
            BufferedReader br = new BufferedReader(new InputStreamReader(is));
            this.br = br;
        }

        public String next() {
            if (st == null || !st.hasMoreTokens()) {
                String nextLine = null;
                try {
                    nextLine = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (nextLine == null)
                    return null;
                st = new StringTokenizer(nextLine);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21332
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int A = scanner.nextInt();
		int B = scanner.nextInt();
		int K = scanner.nextInt();
		scanner.close();

		int max = A + K;
		int min = B - K + 1;
		if(max >= min) {
			for(int i = 0; i <= B - A; i++) {
				System.out.println(A + i);
			}
		}else {
			for(int i = 0; i < K; i++) {
				System.out.println(A + i);
			}
			for(int i = 0; i < K; i++) {
				System.out.println(B - K + i + 1);
			}
		}
	}
}

Measured memory_bytes: 23764
n = int(input())
liw = [input() for i in range(n)]

if len(set(liw)) < len(liw):
  print("No")
  exit()
  
for i in range(n-1):
  if liw[i][-1] != liw[i+1][0]:
    print("No")
    exit()

print("Yes")

Measured memory_bytes: 3060
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  int H, W;
  while (cin >> H >> W){
    if (H == 0 && W == 0) return 0;

    for (int j = 0; j < W; j++) cout << '#';
    cout << endl;
    for (int i = 1; i < H - 1; i++){
      cout << '#';
      for (int j = 1; j < W - 1; j++) cout <<  '.';
      cout << '#';
      cout << endl;
    }
    for (int j = 0; j < W; j++) cout << '#';
    cout << endl;


    cout << endl;
  }   

  return 0;
}



Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//using P = pair<int,int>;
//pow(x,n)
//cout << fixed << setprecision(桁数);
//string = to_string(数値)
//int = stoi(文字列)
//(int)(char-'0')
//string = itoa(int)


int main() {
    /*int n; cin >> n;
    cout << fixed << setprecision(10);
    cout << n*2*M_PI << endl;*/

    int n,m; cin >> n >> m;
    vector<int> A(m);
    rep(i,m) {
        cin >> A[i];
        n-=A[i];
    }
    if(n>=0) cout << n << endl;
    else cout << -1 << endl;
}





Measured memory_bytes: 3640
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include <functional>
#include <queue>
#include <regex>

using namespace std;

constexpr int MOD = 1000000007;
constexpr int INF = 1050000000;

#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl

#define Tof(x) (x) ? Yes : No
#define TOF(x) (x) ? YES : NO
#define tof(x) (x) ? yes : no

using ll = long long;


/*vectorの要素を全部確認するやつだよ。


for (vector<int>::iterator itr = ans.begin(); itr != ans.end(); ++itr) {
	cout << *itr << " ";
}


*/


/*for文でx,yを上下左右確認するやつだよ。

int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };


for (int i = 0; i < 4; i++) {
	int ny = y + dy[i];
	int nx = x + dx[i];
}
*/

/*繰り返し二乗法だよ。modもとってくれるよ。n^kをmodで割った余りでやってくれるよ。

ll POW_MOD(ll n, ll k, ll mod) {
	ll r = 1;

	for (; k > 0; k >>= 1) {
		if (k & 1) {
			r = (r * n) % mod;
		}
		n = (n * n) % mod;
	}
	return r;
}


*/

/*2重for文書くのめんどくなった時用だよ。

for (int i = 0; i < h; i++) {
	for (int j = 0; j < w; j++) {

	}
}

*/


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

	int l, r;

	int ans = 0;

	for (int i = 0; i < n; i++) {
		cin >> l >> r;
		ans += r - l + 1;
	}

	cout << ans << endl;









}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fore(a,b,c) for(int a = b; a < c; a++)
using namespace std;

typedef long long ll;
const int N = 405;
ll n, a[N], dp[N][N];

ll sum(int l, int r) {
    ll ret = 0;
    for(int i = l; i <= r; i++) ret += a[i];
    return ret;
}

ll solve(int l, int r) {
    if (l == r) return 0;
    ll &res = dp[l][r];
    if (res != -1) return res;
    res = 1e18;
    fore(i,l, r) {
        res = min(res, solve(l, i) + solve(i+1, r) + sum(l,r));
    }

    return res;
}

int main() {
    cin >> n;
    fore(i,0,n) cin >> a[i];

    fore(i,0,n)fore(j,0,n)dp[i][j]=-1;

    cout << solve(0, n-1) << endl;

}

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

int main() {
  ll n;
  cin >> n;
  ll ans = 1001001001001001;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ll j = n / i;
      ans = min(ans, i + j - 2);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main(){

  long long n , k, sum = 0, tmp;
  cin >> n >> k;
  priority_queue <int> q;
  
  for(int i = 0; i < n; i++){
    cin >> tmp;
    q.push(tmp);
  }

  for(int i = 0; i < n; i++){
    if(i >= k) sum += q.top();
    q.pop();
  }

  cout << sum;

}

Measured memory_bytes: 1400
using System;
using System.Text;

public class Program
{
    public static void Main(string[] args)
    {
        var output = new StringBuilder();
        string inputO = Console.ReadLine();
        string inputE = Console.ReadLine();

        for (var i = 0; i < inputO.Length; i++)
        {
            output.Append(inputO[i]);
            if (i <= inputE.Length - 1)
            {
                output.Append(inputE[i]);
            }
        }
        Console.WriteLine(output.ToString());
    }
}


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

l,r,t,b = [0],[W],[H],[0]

for i in range(N):
    x,y,a = map(int,input().split())
    if a==1: l.append(x)
    elif a==2: r.append(x)
    elif a==3: b.append(y)
    elif a==4: t.append(y)
        
W = min(r)-max(l) if min(r)-max(l)>=0 else 0
H = min(t)-max(b) if min(t)-max(b)>=0 else 0
        
print(W*H)

Measured memory_bytes: 3064
#include <stdio.h>
int M, N;	char A[51][51], B[51][51];	bool same_flag;
 
int main(void){
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) { 
      scanf("%s", &A[i]);
    }
	for (int i = 0; i < M; ++i) { 
      scanf("%s", &B[i]);
    }
 
	for (int i = 0; i <= (N - M); ++i){
		for (int j = 0; j <= (N - M); ++j){
			same_flag = true;
			for (int x = 0; x < M; ++x){
				for (int y = 0; y < M; ++y){
					if (A[i + x][j + y] != B[x][y]){
						same_flag = false;	break;
					}
				}
				if (same_flag == false){
					break;
				}
			}
			if (same_flag == true){
				printf("Yes\n");	return 0;
			}
		}
	}
	printf("No\n");
}

Measured memory_bytes: 128
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	k, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	s := sc.Text()
	fmt.Println(tripleDots(s, k))
}

func tripleDots(s string, k int) string {
	chars := []rune(s)
	if len(chars) <= k {
		return s
	}
	return string(chars[:k]) + "..."
}


Measured memory_bytes: 1756
N=int(input())
ln =[ int(i) for i in input().split(" ")]

n=N-1
while True:
    if n<=1:
        print("Yes")
        break
    if ln[n-1]<=ln[n] :
        n-=1
    elif (ln[n-1]-ln[n])<2:
        ln[n-1]=ln[n-1]-1
        n-=1
    else:
        print("No")
        break

Measured memory_bytes: 14396
#include<stdio.h>
#define INF 1000000
void warshall_floyd(void);
int min(int,int);
int graph[101][101];
int n,c,d;

int main(void){
  int k,i,j,x,e,a,b;

  while(scanf("%d %d",&n,&k),n,k){

    for(i=0;i<=n;i++)
      for(j=0;j<=n;j++)
	graph[i][j]=(i==j?0:INF);

    for(i=0;i<k;i++){
      
      if(scanf("%d",&x),x){
	scanf("%d %d %d",&c,&d,&e);
	if(graph[c][d]>e){
	graph[c][d]=graph[d][c]=e;
	warshall_floyd();
	}
      }
      else{
	scanf("%d %d",&a,&b);
	if(graph[a][b]<INF)printf("%d\n",graph[a][b]);
	else printf("-1\n");
      }
    }
  }
  return 0;
}

void warshall_floyd(void){
  int i,j;
  
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      graph[i][j]=graph[j][i]=min(graph[i][j],graph[i][c]+graph[c][d]+graph[d][j]);
    }
  }
}

int min(int x,int y){
  return (x<y)?x:y;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> heal(n);
    for (int i = 0; i < n; i++){
        cin >> heal.at(i);
    }
    int sum = 0;
    for (int a = 0; a < n - 1; a++){
        for (int b = a + 1; b < n; b++){
            sum += heal.at(a) * heal.at(b);
        }
    }
    cout << sum << endl;
}

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

const double PI= acos(-1.0);

int gcd_func(int a, int b){
    return b? gcd_func(b, a%b) : a;
} 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("in.txt","r",stdin);
    //reopen("out.txt","w",stdout);
    long long a, b; cin >> a >> b;
    cout << a*b;
    return 0;
}

Measured memory_bytes: 3648
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
constexpr int MOD = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}

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

    int n,p;
    cin >> n >> p;
    int maxv = (n == 1 ? p : 1);

    for(int i = 2;i * i <= p;++i){
        if(p % i == 0){
            int tmp = p,cnt = 0;
            while(true){
                if(tmp % i == 0) tmp /= i;
                else break;
                ++cnt;
            }
            if(cnt >= n) chmax(maxv,i);
            tmp = p,cnt = 0;
            int m = p / i;
            while(true){
                if(tmp % m == 0) tmp /= m;
                else break;
                ++cnt;
            }
            if(cnt >= n) chmax(maxv,m);
        }
    }

    cout << maxv << '\n';

    return 0;
}


Measured memory_bytes: 256
let () =
  let open Queue in
  let que = create () in
  let (n, q) = Scanf.scanf "%d %d\n" (fun n q -> (n, q)) in
  let rec read i =
    if i < n then (Scanf.scanf "%s %d\n" (fun s t -> add (s, t) que); read (i + 1))
  in
  read 0;
  let rec doit cnt =
    if not (is_empty que) then begin
      let (s, t) = take que in
      let rest = t - q in
      if rest <= 0 then (let x = cnt + t in Printf.printf "%s %d\n" s x; doit x)
      else (add (s, rest) que; doit (cnt + q))
    end
  in
  doit 0

Measured memory_bytes: 13228
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define opf(i) cout<<fixed<<setprecision(10)<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;


void solve(long long X, long long A){
  cout<<(X<A? 0:10)<<endl;
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long X;
    scanf("%lld",&X);
    long long A;
    scanf("%lld",&A);
    solve(X, A);
    return 0;
}


Measured memory_bytes: 256
n, x, d = map(int, input().split())

if d == 0:
    if x == 0:print(1)
    else:print(n+1)
    exit(0)

ranges = {}

for k in range(n+1):
    mod = k * x % d
    l = k * x // d + k * (k-1)//2
    r = k * x // d + k * (2*n-k-1)//2
    if mod not in ranges:
        ranges[mod] = []
    ranges[mod].append((l,-1)) 
    ranges[mod].append((r+1, 1))

ans = 0
    
for mod in ranges:
    lrs = ranges[mod]
    lrs.sort()
    cnt = 0
    last = -1
    for x,y in lrs:
        if cnt == 0:last = x
        cnt += y
        if cnt == 0:
            ans += x - last

print(ans)
    

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

using namespace std;
int a[200020],b[200020];

struct edge{
    int x,y;
    bool operator<(const edge& t)const{
        return y<t.y;
    }
};

set<edge> s;
multiset<int> ms;

int main() {
    int h,w;
    cin >> h >> w;
    for(int i=1;i<=h;i++)cin >> a[i] >> b[i];
    for(int i=1;i<=w;i++){
        s.insert({i,i});
        ms.insert(0);
    }
    for(int i=1;i<=h;i++){
        int ma=0;
        auto u=s.lower_bound({0,a[i]});
        while(u!=s.end()&&u->y<=b[i]+1){
            auto v=ms.find(u->y-u->x);
            ms.erase(v);
            ma=max(ma,u->x);
            u=s.erase(u);
        }
        if(ma>0&&b[i]<w){
            s.insert({ma,b[i]+1});
            ms.insert(b[i]+1-ma);
        }
        if(s.empty()){
            cout << "-1" << endl;
        } else {
            cout << *(ms.begin())+i << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 23944
//コンパイラ最適化用
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef pair<ll, ld> pld;
typedef pair<pii, int> ppiii;
typedef pair<pii, ll> ppiill;
typedef pair<pll, ll> ppllll;
typedef pair<pli, int> pplii;
typedef map<int, int> mii;
typedef deque<ll> dll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqrll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvint;
typedef vector<vector<pll>> vvpll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define cin(x) cin >> x

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //入力
    string S;
    cin >> S;


    //本文
    ll size = S.size();
    ll ans  = 0;
    ll current = 0;
    for(int i =0; i<size;i++){
        if(S[i]=='A'||S[i]=='T'||S[i]=='G'||S[i]=='C'){
            current ++;
        }
        else{
            current=0;
        }
        ans = max(current,ans);
    }
    //出力
    cout << ans << endl;
    //REP(i,N) cout << ans.at(i) <<endl;
  return 0;
}

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

int main() {
  string o, e;
  cin >> o >> e;
  
  if (o.size() == e.size()) {
    for (int i = 0; i < o.size(); i++) {
      cout << o.at(i) << e.at(i);
    }
  }
  else {
    for (int i = 0; i < e.size(); i++) {
      cout << o.at(i) << e.at(i);
    }
    cout << o.at(o.size() - 1);
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100
int main(){
  int n,i,j,count=0;
  int A[N];
  int minj;
  int temp;
  scanf("%d",&n);
  for(i=0;i<n;i++){  
scanf("%d",&A[i]);
  }
  for(i=0;i<n;i++){    
   minj=i;
    for(j=i;j<n;j++){
      if(A[j]<A[minj]){
	minj=j;
        }
    }
    if(A[i]!=A[minj]){
   	temp=A[minj];
       A[minj]=A[i];
       A[i]=temp;
       count++;
    }
  }
 for(i=0;i<n-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[n-1]);
  printf("%d\n",count);

  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF=(ll)1e9;
const ll MOD=(ll)1e9+7;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};

int main(){
  ll D,G,ans=INF;
  cin>>D>>G;
  vector<pair<ll,ll>> p(D);
  for(ll i=0;i<D;i++) cin>>p[i].first>>p[i].second;
  for(ll i=0;i<(1<<D);i++){
    bitset<10> b(i);
    ll k=0,m=0;
    for(ll j=0;j<D;j++){
      if(b.test(j)){
        k+=(j+1)*100*p[j].first+p[j].second;
        m+=p[j].first;
      }
    }
    if(k<G){
      for(ll j=D-1;j>=0;j--){
        if(!b.test(j)){
          for(ll l=0;l<p[j].first-1;l++){
            k+=(j+1)*100;
            m++;
            if(k>=G) break;
          } 
        }
        if(k>=G) break;
      }
    }
    if(k>=G) ans=min(ans,m);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()


int main(){
    ll k;
    cin >> k;
    string s;
    cin >> s;
    if(s.size() > k){
        s.resize(k);
        REP(i, 3){ s.push_back('.'); }
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3628
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <assert.h>
#include <sstream>
#include <string>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater <>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
using namespace std;
using ll = long long;
typedef std::pair<ll,ll> P;
//#include <boost/multiprecision/cpp_int.hpp>
//using bint = boost::multiprecision::cpp_int;



int main(){
    string s;
    cin >> s;
    rep(i,s.size()){
        cout << "x";
    }
}


Measured memory_bytes: 256
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

n=r()
a=rl()
cnt=0
for i in range(0,n,2):
    if a[i]%2==1:
        cnt+=1
print(cnt)

Measured memory_bytes: 70996
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		
		try(Scanner scan = new Scanner(System.in)){
			//本数
			int n = scan.nextInt();
			//セットX
			int a = scan.nextInt();
			int b = scan.nextInt();
			int sumX = 0;
			//セットY
			int c = scan.nextInt();
			int d = scan.nextInt();
			int sumY = 0;
			
			for(int i=0; i<n; i+=a) {
				sumX += b;
			}
			
			for(int i=0; i<n; i+=c) {
				sumY += d;
			}
			
			System.out.println(Math.min(sumX, sumY));
		}
	}
}


Measured memory_bytes: 26360
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <deque>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

ll f(ll x) {
  if(x == 1) return 1;
  ll a = f(x/2);
  return a*2+1;
}

int main() {
  ll H; cin >> H;
  cout << f(H) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define downque(que)  priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
typedef long long ll;
const int MOD = 1e9+7;

ll GCD(ll p,ll q){
    ll r=p%q;
    
  while(r>0){
      p=q;
      q=r;
      r=p%q;
  }
  return q;
}


int main(){
 int n; cin>>n;
 ll t[n]; REP(i,n)cin>>t[i];
 ll gcd=1;
 ll l=t[0]; 

 for(int i=1;i<n;i++){
   //cout<<l<<' '<<t[i]<<endl;
    gcd=GCD(l,t[i]);
    l=(l/gcd)*t[i];
   //cout<<gcd<<' '<<l<<endl;
 }
 cout<<l<<endl;
}

Measured memory_bytes: 256
N, Y = map(int, input().split())
result = [-1, -1, -1]
# a = 0, 1, ..., N
for a in range(0, N + 1):
    # b = 0, 1, ..., N-a
    for b in range(0, N - a + 1):
        c = N - a - b
        if 10000 * a + 5000 * b + 1000 * c == Y:
            result = [a, b, c]
print(*result)

Measured memory_bytes: 9068
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        s: String,
        t: String
    }
    let n = s.len();
    let sc: Vec<char> = s.chars().collect();
    let tc: Vec<char> = t.chars().collect();

    let mut ans = 0;
    for i in 0..n {
        if sc[i] != tc[i] { ans += 1 }
    }

    println!("{}", ans);



}


Measured memory_bytes: 4424
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
template<typename T>
void chmax(T& a, T b) {
	a = max(a, b);
}

template<typename T>
void chmin(T& a, T b) {
	a = min(a, b);
}

template<typename T>
void IN(vector<T> &A,int N=-1) {
	if (N == -1) {
		N = A.size();
	}
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
}

template<typename T>
void SO(vector<T> &A,bool F=false) {
	sort(A.begin(), A.end());
	if (F) {
		reverse(A.begin(), A.end());
	}
}
//////////////
bool check(LL A, LL B,LL X) {
	bool ans = true;
	LL A1, A2, B1, B2;
	if (X % 2 == 1) {
		A1 = (X + 1) / 2;
		B1 = (X + 1) / 2;
		if (A<=(X+1)/2) {
			A1++;
		}
		if (B <= (X + 1) / 2) {
			B1++;
		}
		if (A1 * B1 >= A * B) {
			ans = false;
		}
	}
	else {
		A1 = X / 2;
		A2 = A1 + 1;
		B1 = X / 2;
		B2 = B1 + 1;

		if (A <= X) {
			if (A < 1 + X / 2) {
				A1 = X / 2 + 1;
				A2 = A1 + 1;
			}
			else if (A == 1 + X / 2) {
				A1 = X / 2;
				A2 = A1 + 2;
			}
			else {//A > 1+X/2
			}
		}

		if (B < 1 + X / 2) {
			B1 = X / 2 + 1;
			B2 = B1 + 1;
		}
		else if (B == 1 + X / 2) {
			B1 = X / 2;
			B2 = B1 + 2;
		}
		if (A1 * B2 >= A * B) {
			ans = false;
		}
		if (A2 * B1 >= A * B) {
			ans = false;
		}
	}
	return ans;
}
void solve() {
	int Q;
	cin >> Q;
	vector<LL>ans(Q);
	for(int i=0;i<Q;++i){
		LL A, B;
		cin >> A >> B;

		LL L = 0;
		LL R = INF*2;
		while (L + 1 < R) {
			LL mid = (L + R) / 2;
			bool flag = check(A, B, mid);
			if (flag == true) {
				L = mid;
			}
			else if(flag == false){
				R = mid;
			}
		}
		ans[i] = L;
	}
	for (int i = 0; i < Q; ++i) {
		cout << ans[i] << endl;
	}
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
char a[1000];
int b,c;
for(int d=0;;d++){
  scanf("%s",&a);
  if(a[0]=='0')
  break;
  b=0;
  for(c=0;a[c]!='\0';c++)
  b+=a[c]-'0';
  printf("%d\n",b);
}
  return 0;
}


Measured memory_bytes: 2104
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cmath>
#include<bitset>
#include<string>
typedef long long ll;
#define PB	push_back
#define FOR(n)			for(int i = 0; i < n; ++i)
#define RFOR(n)			for(int i = n; i >= 0; --i)
#define FORR(start,end) for(int i = start; i < end; ++i)
#define COUT(n)			cout << n << " " << flush
#define vi(v)			vector<int> v
#define vii(v)			vector<pair<int,int>> v
#define pii(p)			pair<int,int> p
#define mii(m)			map<int, int> m
#define msi(m)			map<string, int, less<>> m
#define mmsi(m)			multimap<string, int, less<>> m
#define mkp(a,b)		make_pair(a,b)
#define ALL(obj)		obj.begin(), obj.end()
const double PI	 = 3.141592;
const int	 MOD = 1e9 + 7;
using namespace std;

void solve() {
	ll n, a, b, ans = 0;
	cin >> n >> a >> b;
	ans += a * (n / (a + b));
	n -= (a+b) * (n/(a+b));
	if(n >= a) ans += a;
	else ans += n;
	cout << ans << endl;
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
void answer(int val, vector<pair<int, int>>& ans) {
    cout << val << '\n';
    for (auto &p : ans) cout << p.first << ' ' << p.second << '\n';
    exit(0);
}
int main()
{
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> A(N); for (auto &a : A) cin >> a;
    vector<int> Pos, Neg, Zero;
    int abssum = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] > 0) Pos.push_back(A[i]);
        if (A[i] < 0) Neg.push_back(A[i]);
        if (A[i] == 0) Zero.push_back(A[i]);
        abssum += abs(A[i]);
    }
    vector<pair<int, int>> ans;
    while (Zero.size() > 1) {
        ans.emplace_back(0, 0);
        Zero.pop_back();
    }
    if (Zero.size() == 1 && Pos.size() == 0) {
        Pos.push_back(0);
        Zero.pop_back();
    }
    if (Zero.size() == 1) {
        Neg.push_back(0);
        Zero.pop_back();
    }
    sort(rbegin(Pos), rend(Pos));
    sort(begin(Neg), end(Neg));
    if (Pos.size() >= 3 && Neg.size() == 0) {
        ans.emplace_back(Pos[Pos.size()-1], Pos[Pos.size()-2]);
        Neg.push_back(Pos[Pos.size()-1] - Pos[Pos.size()-2]);
        Pos.pop_back();
        Pos.pop_back();
    }
    if (Neg.size() >= 2 && Pos.size() == 0) {
        ans.emplace_back(Neg[Neg.size()-1], Neg[Neg.size()-2]);
        Pos.push_back(Neg[Neg.size()-1] - Neg[Neg.size()-2]);
        Neg.pop_back();
        Neg.pop_back();
    }
    while (Pos.size() >= 2 && Neg.size() >= 1) {
        ans.emplace_back(Neg.back(), Pos.back());
        int x = Neg.back() - Pos.back();
        Neg.pop_back();
        Pos.pop_back();
        Neg.push_back(x);
    }
    while (Pos.size() == 1 && Neg.size() >= 1) {
        ans.emplace_back(Pos.back(), Neg.back());
        int x = Pos.back() - Neg.back();
        Neg.pop_back();
        Pos.back() = x;
    }
    if (Pos.size() == 2 && Neg.size() == 0) {
        ans.emplace_back(Pos[0], Pos[1]);
        answer(Pos[0] - Pos[1], ans);
    }
    answer(Pos[0], ans);
    return 0;
}


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

namespace Contest
{
    class ABC
    {
        static void Main()
        {
            Solve();
        }

        private static void Solve()
        {
            int N = int.Parse(Console.ReadLine());
            string INPUT = Console.ReadLine();
            List<char> list = INPUT.ToList();
            for(int i = 0; i < list.Count - 1; i++)
            {
                if(list[i] == list[i + 1])
                {
                    list.RemoveAt(i);
                    i--;
                }
            }
            Console.WriteLine(list.Count);
            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 13268
str = gets.chomp
opnum = gets.to_i

opnum.times do
    opary = gets.chomp.split
    a, b = opary[1].to_i, opary[2].to_i
    case opary[0]
    when "print"
        for i in a..b
            print str[i]
        end
        puts ""
    when "reverse"
        str = str[0...a] + str[a..b].reverse + str[(b + 1)...str.size]
    when "replace"
        str[a..b] = opary[3]
    end
end

Measured memory_bytes: 6128
#include <iostream>
#include <vector>
#include <climits>

void merge(std::vector<int> *A, int left, int mid, int right, int *count) {
  int n1 = mid - left;
  int n2 = right - mid;
  
  std::vector<int> *L = new std::vector<int>(n1 + 1, 0);
  std::vector<int> *R = new std::vector<int>(n2 + 1, 0);

  for (int i = 0; i < n1; i++) {
    L->at(i) = A->at(left + i);
  }

  for (int i = 0; i < n2; i++) {
    R->at(i) = A->at(mid + i);
  }
  
  L->at(n1) = INT_MAX;
  R->at(n2) = INT_MAX;

  int i = 0;
  int j = 0;

  for (int k = left; k < right; k++) {
    if (L->at(i) <= R->at(j)) {
      A->at(k) = L->at(i);
      i++;
    } else {
      A->at(k) = R->at(j);
      j++;
    }

    (*count)++;
  }

  delete R;
  delete L;
}

void merge_sort(std::vector<int> *A, int left, int right, int *count) {
  if (left + 1 < right) {
    int mid = (left + right) / 2;
    merge_sort(A, left, mid, count);
    merge_sort(A, mid, right, count);
    merge(A, left, mid, right, count);
  }
}

int main(void) {
  int n = 0;

  std::cin >> n;
  
  std::vector<int> *A = new std::vector<int>(n, 0);

  for (int i = 0; i < n; i++) {
    int v = 0;
    
    std::cin >> v;

    A->at(i) = v;
  }

  int count = 0;

  int left = 0;
  int right = A->size();
  int mid = (left + right) / 2;

  merge_sort(A, left, right, &count);

  for (int i = 0; i < n; i++) {
    if (i < (n -1)) {
      std::cout << A->at(i) << " ";
    } else {
      std::cout << A->at(i) << std::endl;
    }
  }

  std::cout << count << std::endl;
  
  return 0;
}

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

const int N = 3141;

double dp[N];

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    dp[0] = 1.0;
    for (int i=0; i<n; i++) {
        double p;
        cin >> p;
        for (int j=i+1; j>=0; j--) {
            dp[j] *= 1-p;
            if (j > 0) {
                dp[j] += dp[j-1]*p;
            }
        }
    }
    double ans = 0;
    for (int k=(n+1)/2; k<=n; k++) {
        ans += dp[k];
    }
    cout << fixed << setprecision(10) << ans << '\n';
}


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();
    int m = sc.nextInt();
    int x = sc.nextInt();
    int[] a = new int[n];

    for (int i = 0; i < m; i++) {
      a[sc.nextInt()] = 1;
    }

    int c1 = 0;
    int c2 = 0;

    for (int i = x; i < n; i++) {
      if (a[i] == 1) {
        c1++;
      }
    }

    for (int i = x; i > 0; i--) {
      if (a[i] == 1) {
        c2++;
      }
    }

    System.out.println(Math.min(c1,c2));
  }

}


Measured memory_bytes: 23636
from fractions import gcd
a,b=map(int,input().split())
n=gcd(a,b)

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

#素因数分解
from collections import defaultdict
primelist=primes(int(n**0.5+1))+[n+1]
factors=defaultdict(lambda :0)
for prime in primelist:
    if prime>n:
        factors[n]+=1
        break
    while n%prime==0:
        n=n//prime
        factors[prime]+=1
factors[n]=1
factors[1]=0
print(len(factors))

Measured memory_bytes: 11836
h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

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

struct init_ { init_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } init_;

template<class C> using iodef_rng_t = typename enable_if<decltype(declval<C>().begin(), true_type{})::value && !is_same<C, string>::value>::type;
template<class C, class = iodef_rng_t<C>> istream& operator>>(istream& in, C& c) { for (auto& v : c) { in >> v; } return in; }
template<class C, class = iodef_rng_t<C>> ostream& operator<<(ostream& out, const C& c) { int i = 0; for (const auto& v : c) { if (i++) { out << ' '; } out << v; } return out; }
template<size_t N, class T, class R> using when_last = typename enable_if<N == tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N, class T, class R> using when_init = typename enable_if<N != tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_last<N, T, istream&> { return in >> get<N>(t); }
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_init<N, T, istream&> { return operator>><N + 1>(in >> get<N>(t), forward<T>(t)); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_last<N, T, ostream&> { return out << get<N>(t); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_init<N, T, ostream&> { return operator<<<N + 1>(out << get<N>(t) << ' ', t); }

#ifdef LOCAL
template<class T> void trace_(const char* s, const T& v) { cerr << s << "=" << v; }
template<class T, class... Ts> void trace_(const char* s, const T& v, const Ts&... vs) { for (; *s != ','; ++s) { cerr << *s; } cerr << "=" << v << ","; trace_(++s, vs...); }
#define TRACE(...) (cerr << "\033[2m\033[33m", trace_(#__VA_ARGS__, __VA_ARGS__), cerr << "\033[0m\n")
#else
#define TRACE(...)
#endif


int n, k;
set<int> ds;
int ans = numeric_limits<int>::max();
void dfs(int v) {
    for (auto d : ds) {
        auto w = v * 10 + d;
        if (w >= n) {
            ans = min(ans, w);
        } else if (w != 0) {
            dfs(w);
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < 10; i++) {
        ds.emplace(i);
    }
    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;
        ds.erase(d);
    }
    dfs(0);
    cout << ans << '\n';
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
using ll = long long;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IN(v) if (scanf("%d", &v)<1);
const int MOD = 1e9+7;
const int MAX = 2001;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

ll comb(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  int N, K;
  IN(N); IN(K);
  COMinit();

  int red = N-K, blue = K;

  FOR(i, 1, K + 1) {
    printf("%d\n", (int)((comb(red+1, i) * comb((blue - i) + (i-1), i-1)) % MOD));
  }

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int A,B,C,x,y;
  
  x=0;
  scanf("%d%d%d",&A,&B,&C);
  x=B/A;
  if(x>C) y=C;
  else    y=x;
  printf("%d\n",y);
  
  return 0;
}

Measured memory_bytes: 128
//...START BY DOING WHAT IS NECESSARY, THEN WHAT IS POSSIBLE AND SUDDENLY YOU ARE DOING THE IMPOSSIBLE... 
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
typedef long long ll;
#define endl '\n'
#define M 1000000007
#define pdqueue priority_queue< ll,vector<ll> ,greater< ll > >
bool comp(int x,int y)
{
    return x > y;   
}

/*....................code starts here..............................*/

int main() {
    //FAST_IO;
    int t=1;
   // cin >> t;
    //string s;
    while(t--)
    {
        int n;
        cin >> n;
        if(n%1000 == 0)
        cout << 0 << endl;
        else
        cout << 1000*(n/1000+1)-n << endl;
        
    }
}

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
  ll a, b;
  cin >> a >> b;

  ll gcd_v = gcd(a, b);

  ll ans = 1;
  for (ll i = 2; i*i <= gcd_v; i++) {
    if (gcd_v % i != 0) continue;
    ans++;
    while (gcd_v % i == 0) gcd_v /= i;
  }
  if (gcd_v != 1) ans++;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define mod 1000000007 //10^9+7
#define div 998244353
#define rep(i,n) for(int i=0;i<n;i++)
int n,cnt=0;
signed main(){
    cin>>n;
    int i=0;
    for(;cnt<n;i++){
        cnt+=i;
        if(cnt>=n)break;
    }
    if(i==n)cout<<i<<endl;
    else{
        while(n>0){
            if(i<=n){
                cout<<i<<endl;
                n-=i;
                i--;
            }
            else{
                cout<<n<<endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#しーあるさんより

n,k=map(int,input().split())
s='1'+input()
i=j=0
while j<n:
  #print(k,i,j)
  k-=  '10'==s[j:j+2]
  i+=k<0
  k+=k<0 and '01'==s[i:i+2]
  j+=1
  #print("End",k,i,j)
print(n-i)


Measured memory_bytes: 3316