akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
int main()
{
   string s,t;
   cin>>s>>t;
   int d=-1;
   for(int i=0;i<=(int)(s.size()-t.size());i++)
   {
       int c=1;
       for(int j=0;j<t.size();j++)
       {
           if(s[i+j]!='?' && s[i+j]!=t[j])
           {
			   c=0;
			   break;
		   }
       }
       if(c==1){
           d=i;
	   }
   }
    if(d==-1) cout<<"UNRESTORABLE";
    else
    {
        int j=0;
        while(j<t.size())
        {
            s[d+j]=t[j];
            j++;
        }
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='?')
                s[i]='a';
        }
        cout<<s;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 
  int N = 1,A = 0;
  cin >> N >> A;
  
  if (N - N/500 * 500 <= A)
    cout << "Yes" << endl;
  
  else
    cout << "No" << endl;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
int a,b,bj=0;
int main() {
    cin>>a>>b;
    if((!((a+b)%3))||(!(b%3))||(!(a%3)))puts("Possible");//!(a%3)就是a%3==0
    //在不知道各个运算符优先级的情况下，我们只有用一层一层括号套起来（反正加括号又不要钱） 
    else puts("Impossible");//puts自带换行 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>
using namespace std;
#define rep(i,n) for (int i=0; i < (n); i++)


typedef long long int ll;
typedef double D;      // ??§?¨?????????????double???long double?????????
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
typedef vector<P> VP;


const int INF = (1<<30) - 1;
const D EPS = 1e-9;

#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

class Block{
public:
    int label, start, size;
    Block(int label, int start, int size): label(label), start(start), size(size){};
};

class FileSystem{
private:
    vector<Block> blocks;
    
public:
    FileSystem(){
        blocks.push_back(Block(-1, 0, INF));
    }
    
    void write(int label, int size){
        for(int i=0; i<blocks.size(); i++){
            if(blocks[i].label == -1){
                if(size == blocks[i].size){
                    blocks[i].label = label;
                    break;
                    
                }else if(size < blocks[i].size){
                    int start = blocks[i].start;
                    int lest_size = blocks[i].size - size;
                    auto it = blocks.erase(blocks.begin() + i);
                    it = blocks.insert(it, Block(-1, start+size, lest_size));
                    blocks.insert(it, Block(label, start, size));
                    break;
                    
                }else{
                    blocks[i].label = label;
                    size -= blocks[i].size;
                }
            }
        }
    }
    
    void del(int label){
        //?????????????????£????????????????????????
        for(int i=0; i<blocks.size(); i++)
            if(blocks[i].label == label)
                blocks[i].label = -1;
        
    }
    
    void read(int pointer){
        for(int i=0; i<blocks.size(); i++)
            if(blocks[i].start <= pointer && pointer < blocks[i].start + blocks[i].size)
                cout << blocks[i].label << endl;
    }
};

void solve(int N){
    FileSystem file_system = FileSystem();
    char c;
    while(N--){
        cin >> c;
        if(c == 'W'){
            int label, size;
            cin >> label >> size;
            file_system.write(label, size);
        }
        if(c == 'D'){
            int label; cin >> label;
            file_system.del(label);
        }
        if(c == 'R'){
            int pointer; cin >> pointer;
            file_system.read(pointer);
        }
    }
}

//g++ -std=c++0x -msse4.2 -O3
//#include <bits/stdc++.h>
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.precision(10);
    
    int N;
    while(cin>>N, N){
        solve(N);
        cout << endl;
    }
    
    return 0;
}

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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

const int IINF = 2002002002;
const ll LINF = 9009009009009009009L;

//===

int dp[10010];


int main() {

	int num[10];
	num[1] = 2;
	num[2] = 5;
	num[3] = 5;
	num[4] = 4;
	num[5] = 5;
	num[6] = 6;
	num[7] = 3;
	num[8] = 7;
	num[9] = 6;


	int N, M;
	cin >> N >> M;

	Vi A(M);
	for (int i = 0; i < M; ++i) {
		cin >> A[i];
	}

	dp[0] = 0;
	for (int i = 1; i <= N; ++i) {
		dp[i] = -IINF;
	}

	for (int i = 1; i <= N; ++i) {
		int tmp = -IINF;
		for (auto& Ai : A) {
			if (i - num[Ai] >= 0) {
				tmp = max(tmp, dp[i - num[Ai]] + 1);
			}
		}
		dp[i] = tmp;
	}

	Vi ans(dp[N]);
	int k = N;
	for (int i = 0; i < dp[N]; ++i) {
		int tmp = 0;
		for (auto& Ai : A) {
			if (k - num[Ai] >= 0 && dp[k - num[Ai]] == dp[k] - 1) {
				tmp = max(tmp, Ai);
			}
		}
		ans[i] = tmp;
		k -= num[tmp];
	}

	for (int i = 0; i < dp[N] - 1; ++i) {
		cout << ans[i];
	}
	cout << ans[dp[N] - 1] << endl;
}

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


int main() {
  ll a, b, c, k, answer;
  cin >> a >> b >> c >> k;
  if(k < a) cout << k << endl;
  else if(k < a + b) cout << a << endl;
  else cout << a - (k - a - b) << endl;
}


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

int main() {
  int r;
  cin >> r;
  double ans = (double)2 * r * M_PI;
  cout << fixed << ans << setprecision(10) << endl;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
#define ll long long

struct ii
{
	int l,r,ind;
};

using namespace std;
const int N = 500100;
int n,t,a[N],ans[N],cnt,freq[N];
ii q[N];

const int rt = sqrt(N);

bool cmp(ii a, ii b)
{
	if( a.l/rt == b.l/rt )
		return a.r<b.r;
	return a.l<b.l;
}

int main()
{
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);

	for(int i=1;i<=t;i++)
	{
		q[i].ind = i;
		scanf("%d%d",&q[i].l,&q[i].r);
	}

	sort(q,q+t,cmp);
	int x,y,l = 1,r = 0;

	for(int i=1;i<=t;i++)
	{
		x = q[i].l;
		y = q[i].r;

		while( r < y )
		{
			r++;
			freq[a[r]]++;
			if( freq[a[r]] == 1 )
                cnt++;
		}
		while( r > y )
		{
		    freq[a[r]]--;
		    if( freq[a[r]] == 0 )
                cnt--;
			r--;
		}
		while( l > x )
		{
			l--;
			freq[a[l]]++;
			if( freq[a[l]] == 1 )
                cnt++;
		}
		while( l < x )
		{
		    freq[a[l]]--;
		    if( freq[a[l]] == 0 )
                cnt--;
			l++;
		}

		ans[q[i].ind] = cnt;
	}

	for(int i=1;i<=t;i++)
		printf("%d\n",ans[i]);
}


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

namespace ConsoleApp5
{
    class Program
    {

        static void Main(string[] args)
        {
            String S = Console.ReadLine();
            String[] L = S.Split(' ');
            int N = int.Parse(L[0]);
            int K = int.Parse(L[1]);

            S = Console.ReadLine();
            L = S.Split(' ');
            int[] h = new int[N];
            int ans = 0;

            for(int i=0; i<N; i++)
            {
                h[i] = int.Parse(L[i]);
                if(h[i] >= K)
                {
                    ans++;
                } 
            }

            Console.WriteLine(ans);




        }
    }
}

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

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

    int x, y, z;
    cin >> x >> y >> z;

    int res = x/(y+z);
    if(res*(y+z)+z <= x) cout << res << endl;
    else cout << res-1 << endl;

}

Measured memory_bytes: 256
package main

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

func Abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	var n int
	fmt.Scanln(&n)
	var sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	pt, px, py := 0, 0, 0
	for i := 0; i < n; i++ {
		sc.Scan()
		t, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		x, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		y, _ := strconv.Atoi(sc.Text())
		rt := (t - pt) - (Abs(x-px) + Abs(y-py))
		if rt < 0 || rt%2 != 0 {
			fmt.Println("No")
			return
		}
		pt, px, py = t, x, y
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 1792
r, g, b, n = gets.split.map(&:to_i)
r, g, b = [r, g, b].sort!.reverse!

ans = 0

0.upto(n / r) do |x|
  next if r * x > n
  if r * x == n
    ans += 1
    next
  end

  0.upto(n / g) do |y|
    next if r * x + g * y > n
    if r * x + g * y == n
      ans += 1
      next
    end

    rest = n - (r * x + g * y)
    ans += 1 if rest % b == 0
  end
end

puts ans


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

def sum_order(a, b):
    return max(len(str(a)), len(str(b)))

f_min = sum_order(1, n)
limit = int(pow(n, 1 / 2))
for i in range(2, limit + 1):
    if n % i == 0:
        f = sum_order(i, n // i)
        f_min = min(f_min, f)

print(f_min)



Measured memory_bytes: 39024
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn not(b: bool) -> bool {
    if b {
        false
    } else {
        true
    }
}

fn fact(n: u64) -> u64 {
    if n == 0 {
        1
    } else {
        (n * fact(n - 1)) % 1000000007
    }
}

fn main() {
    let n: u64 = read();
    println!("{}", (n * (n - 1)) / 2);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;
//stoi(s) : string→int stoll(s) :string→longlong


int main(){
    int n,m;
    cin >> n >> m;
    Graph G(n);
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<int> dist(n,-1);
    queue<int> que;
    //初期条件 最初に0を訪れた
    dist[0] = 0;
    que.push(0);

    while(!que.empty()){
        int v = que.front(); //qの先頭の数
        que.pop();

        for(int nv : G[v]){
            if(dist[nv] != -1) continue; //nvを訪れたことがあるなら飛ばす

            dist[nv] = dist[v] + 1;
            que.push(nv); //nvを探索待ちにする
        }
    }

    for(int i=0;i<n;i++){
        if(dist[i] == -1) {cout << "No" << endl; return 0;}
    }
    cout << "Yes" << endl;
    for(int i=1;i<n;i++){
        for(auto x:G[i]){
            if(dist[x] == dist[i] - 1) {cout << x+1 << endl;break;}
        }
    }

}

Measured memory_bytes: 10328
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	double x1, y1, x2, y2, x3, y3, x4, y4;
	double slope_ab, slope_cd;
	int loop;
	int i = 0;

	cin >> loop;

	while(cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4){

		++i;

		slope_ab = (y2-y1) / (x2-x1);
		slope_cd = (y4-y3) / (x4-x3);

		if(slope_ab==slope_cd){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}

		if(i==loop) break;
	}
}

Measured memory_bytes: 1224
from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
dist = [[0]*N for i in range(N)]
log = defaultdict(int)
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    for k in range(N):
      if cost[i][j]>=cost[i][k]+cost[k][j]:
        m = min(m,cost[i][k]+cost[k][j])
        if k != i and k!= j:
          log[(min(i,j),max(i,j))] = 1
    dist[i][j] = m
    dist[j][i] = m
ans = 0
for i in range(N):
  for j in range(i+1,N):
    flag = False
    if dist[i][j]<cost[i][j]:
      print(-1)
      flag = True
      break
    elif log[(i,j)]==0:
      ans += cost[i][j]
  if flag:
    break
else:
  print(ans)
  

Measured memory_bytes: 53212
#include <stdbool.h>
#include <stdio.h>
int main()
{
	int n, r, p, c, tmp;
	int *b;
	int bef[50], aft[50];

	while (true) {
		scanf("%d %d", &n, &r);
		if (!(n | r))
			break;
		b = bef;
		for (int i = n; i >= 1; i--)
			*b++ = i;
		for (int i = 0; i < r; i++) {
			scanf("%d %d", &p, &c);
			for (int j = 0; j < p - 1; j++)
				aft[c + j] = bef[j];
			for (int j = 0; j < c; j++)
				aft[j] = bef[p + j - 1];
			for (int j = c + p - 1; j < n; j++)
				aft[j] = bef[j];
			for (int j = 0; j < n; j++)
				bef[j] = aft[j];
		}
		printf("%d\n", bef[0]);
	}
	return 0;
}



Measured memory_bytes: 2028
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 hs[] = new int[n];
    boolean hjs[] = new boolean[n];
    int a,b;
    int count = 0;
    
    Arrays.fill(hjs,true);
    for(int i = 0;i < n;i++) hs[i] = sc.nextInt();
    for(int i = 0;i < m;i++) {
      a = sc.nextInt()-1;
      b = sc.nextInt()-1;
      if(hs[a] >= hs[b]) hjs[b] = false;
      if(hs[a] <= hs[b]) hjs[a] = false;
    }
    
    for(int i = 0;i < n;i++) {
      if(hjs[i]) count++;
    }
        
    System.out.println(count);
 
  }
}


Measured memory_bytes: 59464
#include <iostream>
#include <algorithm>

using namespace std;

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

	m = min({ a, b, c });
	if (m == a) n = min(b, c);
	if (m == b) n = min(a, c);
	if (m == c) n = min(a, b);

	cout << m + n << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repeq(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define rep1(i,x,n) for(int (i)=(x);(i)<(int)(n);(i)++)
#define rep1eq(i,x,n) for(int (i)=(x);(i)<=(int)(n);(i)++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
using namespace std;
using ll = long long;
using Int = long long;

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;
typedef pair<int,int> P;

//少数点表示
//cout << std::fixed << std::setprecision(14) << 値

int main(){
    cin.tie( 0 ); ios::sync_with_stdio( false );
    int x;
    cin >> x;
    int amari = 0;
    int happy = 0;
    if(x == 0){
        cout << 0;
        return 0;   
    }
    int z = x/500;
    happy += (1000*z);
    int y;
    if(z != 0){
        y = (x%(500*z))/5;
    }else{
        y = x/5;
    }
    happy+= (5*y);
    cout << happy;
}

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

/* #pragma */
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

/*alias*/
#define F first
#define S second

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define itn int

/*template*/
template<class T>inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

/* func */
int GCD(int a,int b){return b?GCD(b,a%b):a;}
long long GCD(long long a, long long b){return b ? GCD(b, a%b) : a;}
int LCM(int a, int b){return a * b / GCD(a, b);}
long long LCM(long long a, long long b){return a * b / GCD(a, b);}

/*struct*/
struct aaa {
	aaa() {
		cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);
	};
}aaaaaaa;

/* const */
const int INF = 1001001001;
const long long LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7; //10^9
const double EPS = 1e-9;
const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }, dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
//const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//Counterclockwise from the 6o'clock direction
//Take the x-axis downward and the y-axis right

//#define int long long

//g++ -std=c++14 -Wall --pedantic-errors -o template template.cpp
//g++ -std=c++14 -Wall --pedantic-errors template.cpp
//chcp 65001

/*global*/

signed main()
{
//	v.resize(n);
int n;
cin >> n;
vector<int> d(n);
int cnt{};
for(int i = 0, i_len = (int)n; i < i_len; ++i) cin >> d[i];
sort(d.begin(), d.end());

for(int k = 1; k <= (int)1e5; ++k){
	auto low1 = lower_bound(d.begin(), d.end(), k);
	auto up1 = upper_bound(d.begin(), d.end(), k);
/*	auto low2 = low1;
	while(low2 < up1){
		if((d.end()-low2) == (low2 - d.begin()))
		cnt += up1-low1;
		++low2;
	}
*/
	if((d.end()-low1) == (low1-d.begin()))++cnt;
}
cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;

ll dp[3005][3005][3];

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    dp[a][b][0] = 1;
    for(int i = a; i <= c; i++){
        for(int j = b; j <= d; j++){
            if(i == a){
                if(j == b){
                    continue;
                }
                else{
                    dp[i][j][0] = dp[i][j - 1][0] * a % MOD;
                }
            }
            else if(j == b){
                dp[i][j][0] = dp[i - 1][j][0] * b % MOD;
            }
            else{
                dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) * (j - 1) % MOD;
                dp[i][j][2] = (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2] * j) % MOD;
                dp[i][j][1] = (dp[i][j - 1][0] + dp[i][j - 1][2] + dp[i][j - 1][1] * i) % MOD;
            }
        }
    }
    cout << (dp[c][d][0] + dp[c][d][1] + dp[c][d][2]) % MOD << endl;
}


Measured memory_bytes: 214932
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N, M, Q;
vector<vector<int> > A;
int Ques[51][4];

void dfs(int idx, int pre, stack<int> st) {
  if (idx==N) {
    vector<int> v;
    rep(i, N) {
      v.push_back(st.top());
      st.pop();
    }
    A.push_back(v);
    return;
  }

  for (int i=pre; i<=M; i++) {
    st.push(i);
    dfs(idx+1, i, st);
    st.pop();
  }
} 

int main() {
  INCANT;
  cin >> N >> M >> Q;
  int a,b,c,d;
  rep(i, Q) {
    cin >> a >> b >> c >> d;
    a--;b--;
    Ques[i][0]=a;
    Ques[i][1]=b;
    Ques[i][2]=c;
    Ques[i][3]=d;
  }
  stack<int> st = {};
  dfs(0,1,st);
  int ans=0;
  for (auto vec: A) {
    assert(vec.size()==N);
    int tmp=0;
    rep(i, Q) {
      int a = Ques[i][0],b=Ques[i][1];
      if (vec[N-b-1]-vec[N-1-a]==Ques[i][2]) tmp+=Ques[i][3];
    }
    ans =max(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 9824
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cmath>
using namespace std;

class UnionFind {
public:
	vector<int>par;

	void init(int size_) {
		par.resize(size_, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u != v) par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

long long N, x[19], y[19], a[19]; long double r[1 << 17], dp[1 << 17];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> x[i] >> y[i] >> a[i];

	for (int i = 0; i < (1 << N); i++) {
		int bit[15], cnt = 0; for (int j = 0; j < N; j++) { bit[j] = (i / (1 << j)) % 2; cnt += bit[j]; }

		vector<tuple<long double, int, int>>vec;
		for (int j = 0; j < N; j++) {
			for (int k = j + 1; k < N; k++) {
				if (bit[j] == 1 && bit[k] == 1) {
					long double leng = sqrtl(1.0L * (x[j] - x[k]) * (x[j] - x[k]) + 1.0L * (y[j] - y[k]) * (y[j] - y[k]));
					vec.push_back(make_tuple(leng, j, k));
				}
			}
		}
		sort(vec.begin(), vec.end());

		UnionFind UF; UF.init(N); long double sum = 0;
		for (int j = 0; j < vec.size(); j++) {
			int to1 = get<1>(vec[j]), to2 = get<2>(vec[j]);
			if (UF.same(to1, to2) == false) {
				sum += get<0>(vec[j]); UF.unite(to1, to2);
			}
		}

		long double A = 0; for (int j = 0; j < N; j++) A += 1.0L * bit[j] * a[j];
		r[i] = 1.0L * (A - sum) / cnt;
	}

	dp[0] = 1e9;
	for (int i = 0; i < (1 << N); i++) {
		vector<int>vec; for (int j = 0; j < N; j++) { if ((i / (1 << j)) % 2 == 0) vec.push_back(j); }
		
		for (int j = 0; j < (1 << vec.size()); j++) {
			int S = 0; for (int k = 0; k < vec.size(); k++) { if ((j&(1 << k)) != 0) S += (1 << vec[k]); }
			dp[i + S] = max(dp[i + S], min(dp[i], r[S]));
		}
	}
	printf("%.12Lf\n", dp[(1 << N) - 1]);
	return 0;
}

Measured memory_bytes: 2944
k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        y=int(x[0])
        if y==1:
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        elif 2<=y<=8:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        else:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
        z=int(x[-1])
        if z==0:
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        elif 1<=z<=8:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        else:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
    ans[-1]=list(set(ans[-1]))
    d+=len(ans[-1])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

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

long long n, k, c;
vector<long long> t;

int main() {
  cin >> n >> c >> k;
  t.resize(n);
  for (int i = 0; i < n; ++i) cin >> t[i];
  sort(t.begin(), t.end());
  long long res = 0;
  for (int i = 0; i < n;) {
    long long now = t[i] + k, cnt = 0;
    while (i < n && now >= t[i] && cnt < c) {
      ++i;
      ++cnt;
    }
    ++res;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 1024
n=int(input())
l=list(map(int,input().split()))
ans=0
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
if n==1:
    ans=l[0]
else:
    element = gcd(l[0], l[1])
    if n==2:
      ans=element
    else:
        for i in range(2,n):
            element=gcd(element,l[i])
        ans=element
print(ans)

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;

  if (A + B < C + D) {
    cout << "Right" << endl;
  }
  else if (A + B == C + D) {
    cout << "Balanced" << endl;
  }  
  else if (A + B > C + D) {
    cout << "Left" << endl;
  }
}

Measured memory_bytes: 3604
#include<iostream>
#include<math.h>
using namespace std;
int main(){
    int D,N;
    cin >> D >> N;
    if(D==0){
        if(N==100){
            cout << 100+1 << endl;
        }
        else{
        cout << N << endl;
        }
    }
    else if(D==1){
        if(N==100){
            cout << 10100 << endl;
        }
        else{
        cout << pow(100,D)*N << endl;
        }
    }
    else if(D==2){
        if(N==100){
            cout << 1010000 << endl;
        }
        else{
            cout << pow(100,D)*N << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
	int N,M,K;
	cin >>N >> M >> K;
	
	for(int i=0; i<=N; i++)
		for(int j=0; j<=M; j++) {
			int num = i * j + (N - i) * (M-j);
			
			if(num == K) {
				cout << "Yes" << endl;
				return 0;
			}
			
		}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ctime>
#include <cctype>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <memory.h>
using namespace std;
#define ll long long 
int main()
{
	ll q,h,s,d,n;
	cin>>q>>h>>s>>d>>n;
	ll a1,a2,a3,a4;
	a1=q*8,a2=h*4,a3=s*2,a4=d;
	if(n==1){
		ll b1=a1/2,b2=a2/2,b3=a3/2,b4=a4;
		ll aa=min(b1,b2);
		ll bb=min(b3,b3);
		ll cc=min(aa,bb);
		cout<<cc;
		return 0;
	}
	if(n==0){
		cout<<"0";
		return 0;
	}
	ll a=min(a1,a2);
	ll b=min(a3,a4);
	ll c=min(a,b);
	if(c==a1){
		a1/=2;
		cout<<n*a1;
	}
	if(c==a2){
		a2/=2;
		cout<<n*a2;
	}
	if(c==a3){
		a3/=2;
		cout<<n*a3;
	}
	if(c==a4){
		if(n%2==0){
			cout<<n/2*a4;
		}
		else{
			ll mx;
			if(a<a3){
				if(a1<a2){
					mx=a1/2;
				}
				else{
					mx=a2/2;
				}
			}
			if(a3<a){
				mx=a3/2;
			}
			ll x=n/2*a4;
			cout<<mx+x;
			return 0; 
		}
	}
    return 0;
}

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

const int MAX = 100005;
int A[MAX];

int main() {
    int N, a;
    scanf("%d", &N);
    int ans = 0;
    for (int i= 0; i < N; i++) {
        scanf("%d", &a);
        if (a > N) ans++;
        else A[a]++;
    }
    for (int i = 0; i <= N; i++) {
        if (A[i] < i) ans += A[i];
        else ans += A[i] - i;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ll long long


int main()
{
    string s;
    cin >> s;
    int end = s.length() -1;
    int start = 0;
    int cnt = 0;
    while(start < end)
    {
        if(s[start] == s[end])
        {
            start++;
            end--;   
        }
        else if(s[start] == 'x')
        {
            start++;
            cnt++;
        }
        else if(s[end] == 'x')
        {
            end--;
            cnt++;
        }
        else
        {
            cout << -1 << endl;
            return 0;
        }

    }
    
    cout << cnt << endl;

}

Measured memory_bytes: 512
package main

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

func main() {
	S := ReadString()
	m := make(map[byte]bool)
	for _, c := range []byte(S) {
		m[c] = true
	}
	for c := byte('a'); c <= 'z'; c++ {
		if !m[c] {
			fmt.Println(string(c))
			return
		}
	}
	fmt.Println("None")
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


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


int main(){
    vector<string> S(3);
    cin >> S[0] >> S[1] >> S[2];
    vector<int> p(3, 0);
    char turn = 'a';
    while (true) {
        if (turn == 'a') {
            if (p[0] == (int)S[0].size()) break;
            turn = S[0][p[0]];
            p[0]++;
        }else if (turn == 'b') {
            if (p[1] == (int)S[1].size()) break;
            turn = S[1][p[1]];
            p[1]++;
        }else if (turn == 'c') {
            if (p[2] == (int)S[2].size()) break;
            turn = S[2][p[2]];
            p[2]++;
        }
    }
    if (turn == 'a') cout << "A" << endl;
    else if (turn == 'b') cout << "B" << endl;
    else cout << "C" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int MR=1e6+10;
typedef long long LL;

int main() {
	string a;
	cin>>a;
	if(a[2]==a[3] && a[4]==a[5]){
		printf("Yes\n");
	}
	else printf("No\n");
    return 0;
}

Measured memory_bytes: 256
N,Q=map(int,input().split())
S=input()
a=[0]
for i in range(1,N):
    if S[i-1]+S[i]=='AC':
        a.append(1)
    else:
        a.append(0)
#print(a)
b=[]
sum=0
b.append(sum)
for x in a:
    sum+=x
    b.append(sum)
#print(b)
for i in range(Q):
    l,r=map(int,input().split())
    print(b[r]-b[l])

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

#ifdef _DEBUG
inline void dump() { cerr << endl; }
template<typename Head> void dump(Head&& head) { cerr << head; dump(); }
template<typename Head, typename... Tail> void dump(Head&& head, Tail&&... tail) { cerr << head << ", "; dump(forward<Tail>(tail)...); }
#define debug(...) do {cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; dump(__VA_ARGS__); } while (false)
#else
#define dump(...)
#define debug(...)
#endif

template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////

const ll inf = 1LL<<60;

template<typename T>
struct Tsort {
  vector<T> max_costs;
  T max_cost;
  int n;
  WeightedGraph<T> g;
  vector<int> sorted_vertices;
  vector<int> indegree;

  Tsort(WeightedGraph<T> _g) {
    g = _g;
    n = _g.size();
    max_costs.assign(n, 0);
    indegree.assign(n, 0);
    for (int i=0; i<n; i++) {
      for (auto v : g[i]) indegree[v.to]++;
    }
    queue<int> que;
    for (int i=0; i<n; i++) {
      if (indegree[i] == 0) que.push(i);
    }
    while (!que.empty()) {
      int v = que.front(); que.pop();
      for (auto u : g[v]) {
        indegree[u.to] -= 1;
        max_costs[u.to] = max(max_costs[u.to], max_costs[v]+u.cost);
        if (indegree[u.to] == 0) que.push(u.to);
      }
      sorted_vertices.push_back(v);
    }
    max_cost = 0;
    for (int i=0; i<n; i++) max_cost = max(max_cost, max_costs[i]);
  }
};

int main()
{
  int n; cin >> n;
  int m; cin >> m;
  WeightedGraph<int> g(n);
  for (int i=0; i<m; i++) {
    int x, y; cin>>x>>y; x--; y--;
    g[x].push_back(edge<int>{y, 1});
  }
  Tsort<int> ts(g);
  cout << ts.max_cost << endl;

  return 0;
}


Measured memory_bytes: 21052
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//ここまでテンプレ
int main(){
	int N;
	cin>>N;
	int num[SIZE]={};
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		num[a]++;
		if((N%2 && a%2) || (N%2==0 && a%2==0)){
			cout<<0<<endl;
			return 0;
		}
	}
	if(num[0]>=2){
		cout<<0<<endl;
		return 0;
	}
	for(int i=1;i<SIZE;i++){
		if(num[i]!=0 && num[i]!=2){
			cout<<0<<endl;
			return 0;
		}
	}
	ll ans=1;
	for(int i=0;i<N/2;i++)
		ans=ans*2%MOD;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
n = int(input())
a = list(map(int,input().split()))
mod = 10**6 - 1
rec1 = {}
rec2 = {}
for i in range(n):
  tmp1 = i+1 - a[i]
  tmp2 = i+1 + a[i]
  try:
    rec1[tmp1] += 1
  except:
    rec1[tmp1] = 1
    rec2[tmp1] = 0
  try:
    rec2[tmp2] += 1
  except:
    rec2[tmp2] = 1
    rec1[tmp2] = 0
#print(rec1)
#print(rec2)
ans = 0
for x in rec1:
  ans += rec1[x] * rec2[x]
print(ans)

Measured memory_bytes: 167812
#include <iostream>
#include <algorithm>
#define int long long
#define rep(i, n) for (int i = 0; i < n; ++i)
 
using namespace std;

const int N = 1e5 + 10;
const int INF = 1e+18;

int n;
int a[N];

signed main() {
	cin >> n;
	rep(i, n) cin >> a[i];
	sort(a, a + n);
	
	int ans = 1;
	rep(i, n) {
		if (a[i] > INF / ans) {
			cout << "-1\n";
			return 0;
		}
		ans *= a[i];
		if (!ans) break;
	}
	if (ans > INF) cout << "-1\n";
	else cout << ans << '\n';
	
	return 0;
}

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

const int N = 6e2+5;

int n , d[2];
int vis[2][N][N] , cnt[3][3];
vector<pair<int , int> > v[2];

bool f(int x , int y){
	return (x > 0 and y > 0 and x <= 2 * n and y <= 2 * n);
}

void dfs(int fos , int i , int j , int col);

void g(int fos , int x , int y , int col){
	if(f(x , y) and vis[fos][x][y] == -1)dfs(fos , x , y , col);
}

void dfs(int fos , int i , int j , int col){
	vis[fos][i][j] = col;
	col ^= 1;
	for(auto it : v[fos]){
		g(fos , i + it.first , j + it.second , col);
		g(fos , i + it.first , j - it.second , col);
		g(fos , i - it.first , j + it.second , col);
		g(fos , i - it.first , j - it.second , col);
		if(it.first != it.second){
			g(fos , i + it.second , j + it.first , col);
			g(fos , i + it.second , j - it.first , col);
			g(fos , i - it.second , j + it.first , col);
			g(fos , i - it.second , j - it.first , col);
		}
	}
}

int main(){
	cin >> n >> d[0] >> d[1];
	for(int i = 0;i * i <= d[0]/2;i++){
		int j = d[0] - i * i;
		int k = sqrt(j);
		if(j == k * k){
			v[0].push_back(make_pair(i , k));
		}
	}
	for(int i = 0;i * i <= d[1]/2;i++){
		int j = d[1] - i * i;
		int k = sqrt(j);
		if(j == k * k){
			v[1].push_back(make_pair(i , k));
		}
	}
	memset(vis , -1 , sizeof(vis));
	for(int i = 1;i <= 2 * n;i++){
		for(int j = 1;j <= 2 * n;j++){
			if(vis[0][i][j] == -1)dfs(0 , i , j , 0);
			if(vis[1][i][j] == -1)dfs(1 , i , j , 0);
		}
	}
	for(int i = 1;i <= 2 * n;i++){
		for(int j = 1;j <= 2 * n;j++){
			cnt[vis[0][i][j]][vis[1][i][j]]++;
		}
	}
	int a = 0 , b = 0 , c = 0;
	for(int i = 0;i < 2;i++)for(int j = 0;j < 2;j++)if(c < cnt[i][j]){
		c = cnt[i][j];
		a = i;
		b = j;
	}
	int ans = n * n;
	for(int i = 1;i <= 2 * n;i++){
		for(int j = 1;j <= 2 * n;j++){
			if(vis[0][i][j] == a and vis[1][i][j] == b and ans > 0){
				cout << i - 1 << " " << j - 1 << endl;
				ans--;
			}
		}
	}
}

Measured memory_bytes: 37504
#include<stdio.h>
int main(){
    int h,r,gt;
    scanf("%d %d",&h,&r);
    if(h+r>0){
        gt=1;
    }else if(h+r==0){
        gt=0;
    }else{
        gt=-1;
    }
    printf("%d\n",gt);
    return 0;
}


Measured memory_bytes: 2768
fun main(arr:Array<String>) {
    val n = readLine()!!.toInt()
    val cards = readLine()!!.split(" ").map { it.toInt() }.sortedDescending()
    val alice = cards.indices.filter { it % 2 == 0 }.map { cards[it] }.sum()
    val bob = cards.sum() - alice
    println(alice - bob)
}

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

G = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)

check = [0] * (N + 1)
check[1] = 1
ans1 = [1]
stack = [1]
while stack:
    tmp = stack.pop()
    for next_ in G[tmp]:
        if check[next_] == 1:
            continue
        else:
           stack.append(next_)
           check[next_] = 1
           ans1.append(next_)
           break

# print (ans1)

ans2 = []
stack = [1]
while stack:
    tmp = stack.pop()
    for next_ in G[tmp]:
        if check[next_] == 1:
            continue
        else:
           stack.append(next_)
           check[next_] = 1
           ans2.append(next_)
           break

# print (ans2)

print (len(ans1) + len(ans2))
print (*ans2[::-1], end ='')
if len(ans1):
    print (' ', end = '')
else:
    print ()
print (*ans1)

Measured memory_bytes: 24940
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
char s[N], sta[N];
int top;
int main() {
    scanf("%s", s);
    int n = strlen(s);
    for (int i = 0; i < n; i++)
        if (top) {
            if (s[i] == 'S')
                sta[++top] = 'S';
            else if (sta[top] == 'S')
                top--;
            else
                sta[++top] = 'T';
        } else
            sta[++top] = s[i];
    printf("%d\n", top);
    return 0;
}


Measured memory_bytes: 640
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

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

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N = i_inpl()
    t = l_inpl()
    v = l_inpl()

    T = sum(t)
    max_v = [0]

    for i in range(N):
        max_v[-1] = min(v[i], max_v[-1])
        max_v.extend([v[i]]*t[i]*2)

    max_v[0] = 0
    for i in range(1, 2*T):
        max_v[i] = min(max_v[i-1]+0.5, max_v[i])

    max_v[-1] = 0
    for i in range(2*T-1, 0, -1):
        max_v[i] = min(max_v[i+1]+0.5, max_v[i])
    
    # for i, v in enumerate(max_v):
    #     print(i/2, v)
    ans = 0
    for i in range(2*T-1):
        ans += max_v[i] * 0.5 + (max_v[i+1]-max_v[i]) * 0.5
    
    print(ans)
if __name__ == "__main__":
    main()


Measured memory_bytes: 41584
#include<iostream>
#include<string>
using namespace std;
#define INFTY (int)(1e9+100)

void merge(pair<int,string> A[], int left, int mid, int right){
	int n1 = mid - left, n2 = right - mid;
	pair<int, string> L[n1+1], R[n2+1];
	for(int i = 0; i < n1; i++){
		L[i] = A[left + i];
	}
	for(int i = 0; i < n2; i++){
		R[i] = A[mid + i];
	}
	L[n1].first = INFTY;
	R[n2].first = INFTY;
	for(int k = left, i = 0, j = 0; k < right; k++){
		if(L[i].first <= R[j].first){
			A[k] = L[i];
			i++;
		} else {
			A[k] = R[j];
			j++;
		}
	}
}

void mergeSort(pair<int, string> A[], int left, int right){
	if(left+1 < right){
		int mid = (left + right)/2;
		mergeSort(A,left, mid);
		mergeSort(A,mid,right);
		merge(A,left,mid,right);
	}
}


int partition(pair<int, string> A[], int p, int r){
	int x = A[r].first;
	int i = p-1;
	for(int j = p; j < r; j++){
		if(A[j].first <= x){
			i++;
			swap(A[i], A[j]);
		}
	}
	swap(A[i+1],A[r]);
	return i+1;
}
int n;
void quickSort(pair<int, string> A[], int p, int r){
	// for(int i = 0; i < n; i++){
		// cout<<A[i].second<<" "<<A[i].first<<endl;
	// }cout<<endl<<endl;;
	if(p < r){
		int q = partition(A, p, r);
		// cout<<p<<" "<<q-1<<" "<<q+1<<" "<<r<<endl;
		// cout<<A[q].first<<endl;
		quickSort(A, p, q-1);
		quickSort(A, q+1, r);
		// cout<<p<<" "<<q-1<<" "<<q+1<<" "<<r<<endl;
	}
}
pair<int, string> A[100100];
pair<int, string> B[100100];
int main(){

	int  flag = true;;
	
	cin>> n;
	
	for(int i = 0; i < n; i++){
		cin>>A[i].second>>A[i].first;
		B[i] = A[i];
	}
	
	quickSort(A,0,n-1);
	mergeSort(B,0,n);
	
	for(int i = 0; i < n; i++){
		if(A[i] != B[i]){
			flag = false;
			break;
		}
	}
	
	cout<<(flag?"Stable":"Not stable")<<endl;
	// cout<<(flag?"Stable":"Not stable")<<endl;
	for(int i = 0; i < n; i++){
		cout<<A[i].second<<" "<<A[i].first<<endl;
	}
	return 0;
}


Measured memory_bytes: 12524
#include "bits/stdc++.h"
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 4e18;

// bellman-ford法
struct edge { int to, cost; };

bool bellman_ford(int s, int n, const vector<vector<edge>> &G, vector<ll> &d) {
    const int V = G.size();
    vector<vector<int>> rto(V);
    vector<bool> vis(V, false);
    vector<vector<edge>> G2(V);
    REP(i, V) {
        for (edge e : G[i]) {
            rto[e.to].push_back(i);
        }
    }
    stack<int> sta;
    sta.push(n);
    vis[n] = true;
    while (!sta.empty()) {
        int t = sta.top(); sta.pop();
        for (int k : rto[t]) {
            if (!vis[k]) {
                sta.push(k);
                vis[k] = true;
            }
        }
    }
    REP(i, V) {
        for (edge e : G[i]) {
            if (vis[e.to] && vis[i]) {
                G2[i].push_back(e);
            }
        }
    }
    d = vector<ll>(V, LLINF);
    d[s] = 0;
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            for (edge e : G2[j])
            {
                if (d[j] != LLINF && d[j] + e.cost < d[e.to]) {
                    d[e.to] = d[j] + e.cost;
                    if (i == V - 1) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    int n, m, p; cin >> n >> m >> p;
    vector<vector<edge>> G(n);
    vector<ll> dist(n);
    REP(i, m) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--; c -= p;
        c *= -1;
        G[a].push_back({b,c});
    }
    if (bellman_ford(0, n - 1, G, dist)) {
        cout << max(0LL, -dist[n - 1]) << endl;
    }
    else {
        cout << -1 << endl;
    }
    getchar(); getchar();
}

Measured memory_bytes: 768
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    
    table = [0] * 100001
    
    c = 0
    s = 0
    
    for i in A:
        table[i] += 1
        s += i
    
    for i in range(Q):
        B, C = map(int, input().split())
        c = table[B]
        s += (C - B) * c
        table[C] += table[B]
        table[B] = 0
        print(s)

main()

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



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

    int N,M;
    map<int,int> m;
    cin >> N;
    int D[N];
    rep(i,N) {
        cin >> D[i];
        m[D[i]]++;
    }
    string ans="YES";
    cin >> M;
    int T[M];
    rep(i,M) {
        cin >> T[i];
        m[T[i]]--;
        if(m[T[i]]<0) ans="NO";
    }
    cout << ans << endl;





}


Measured memory_bytes: 11264
// 418 Laver
// 2019.12.7 bal4u

#include <stdio.h>
#include <stdlib.h>

int x1[2], y1[2], x2[2], y2[2], w[2], h[2];
int x[4], xs;
int y[4], ys;
int s[4][4];

int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int xbsch(int a)
{
	int m, l = 0, r = xs;

    while (l < r) {
        m = (l + r) >> 1;
        if (x[m] < a) l = m + 1; else r = m;
    }
	return l;
}

int ybsch(int a)
{
	int m, l = 0, r = ys;

    while (l < r) {
        m = (l + r) >> 1;
        if (y[m] < a) l = m + 1; else r = m;
    }
	return l;
}

int uniq(int *a, int n)
{
	int i, j;
	
	for (i = 0, j = 1; j < n; j++) {
		while (j < n && a[j] == a[i]) j++;
		if (j < n) if (++i != j) a[i] = a[j];
	}
	return i+1;
}

int main()
{
	int i, w1, h1, w2, h2, a;
    int r, c;

	for (i = 0; i < 2; i++) {
        scanf("%d%d%d%d", x1+i, y1+i, w+i, h+i);
        x2[i] = x1[i]+w[i], y2[i] = y1[i]+h[i];
		x[xs++] = x1[i], y[ys++] = y1[i];
		x[xs++] = x2[i], y[ys++] = y2[i];
	}
	qsort(x, xs, sizeof(int), cmp); xs = uniq(x, xs);
	qsort(y, ys, sizeof(int), cmp); ys = uniq(y, ys);

	for (i = 0; i < 2; i++) {
		int c1 = xbsch(x1[i]), c2 = xbsch(x2[i]);
		int r1 = ybsch(y1[i]), r2 = ybsch(y2[i]);

		s[r1][c1]++, s[r1][c2]--;
		s[r2][c1]--, s[r2][c2]++;
	}

	a = 0;
	for (r = 0; r < ys; r++) for (c = 1; c < xs; c++) s[r][c] += s[r][c-1];
	for (r = 1; r < ys; r++) for (c = 0; c < xs; c++) s[r][c] += s[r-1][c];
	for (r = 0; r < ys; r++) for (c = 0; c < xs; c++) if (s[r][c]) {
		a += (x[c+1]-x[c])*(y[r+1]-y[r]);
	}
	printf("%d\n", 2*a-(w[0]*h[0]+w[1]*h[1]));
	return 0;
}


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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);


int main() {
	cin.sync_with_stdio(false);
	string N;
	cin >> N;
	int sum = 0;
	rep(i, N.size()-1) {
		if ((N[i] - '0') + (N[i + 1] - '0') <= (N[i] - '0' - 1) + 9) {
			cout <<sum+ (N[i] - '0' - 1) + 9 * (N.size() -i- 1) << endl;
			return 0;
		}
		else sum += N[i] - '0';
	}
	sum += N[N.size()-1] - '0';
	cout << sum << endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void) {
	double r, ensyu = 3.141592653589, menseki, ensyuu;
	cin >> r;
	menseki = r * r * ensyu;
	ensyuu = 2 * r * ensyu;
	printf("%.8lf %.8lf", menseki, ensyuu);
	return 0;
}


Measured memory_bytes: 3212
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int H, N;
    while(cin >> H >> N){
        vector<int> A(N), B(N);
        for(int i=0;i<N;i++) cin >> A[i] >> B[i];
        vector<int> dp(H+1, 1000000007);
        dp[0] = 0;
        for(int i=0;i<H;i++){
            for(int j=0;j<N;j++){
                dp[min(H, i+A[j])] = min(dp[min(H, i+A[j])], dp[i] + B[j]);
            }
        }
        cout << dp.back() << endl;
    }
}

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

using namespace std;

using ll = long long;

bool is_prime(int n) {
    if (n % 2 == 0) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return n != 1;
}

vector<int> divisor(int n) {
    vector<int> res;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    return res;
}

map<ll, ll> prime_factor(ll n) {
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

vector<int> sieve(int n) {
    vector<int> res;
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!is_prime[i]) continue;
        res.emplace_back(i);
        for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b;
    cin >> a >> b;
    ll g = __gcd(a, b);
    cout << prime_factor(g).size() + 1 << "\n";
    return 0;
}

Measured memory_bytes: 256