akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) ((vec).begin(),(vec).end())
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
using namespace std;
string a;
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>a;
	if(a[0]>='A'&&a[0]<='Z') cout<<'A'<<endl;
	else cout<<'a'<<endl;
	return 0;
}


Measured memory_bytes: 3608
n = gets.chomp.to_i
pp = gets.chomp.split.map(&:to_i)
qq = gets.chomp.split.map(&:to_i)

i = 0
a = nil
b = nil


(1..n).to_a.permutation(n) do |perm|
  a = i if perm == pp
  b = i if perm == qq
  i += 1
end
p (a - b).abs

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

#define LL long long
#define COIN const int
#define ite iterator
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>

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

#define ALL(c) (c).begin(), (c).end()
#define LEN(s) (s).size()
#define CLEAR(x) memset(x,0,sizeof x);

#define MP make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define X first
#define Y second

#define VI vector<int>
#define VS vector<string>
#define VII vector<PII>
#define VVI vector<VI>

#define PIII 3.1415926
#define PI 3.14
/*****************************************************************************/

using namespace std;

LL n,num=1,k;

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >>n >>k;
	int i=1;
	while (1)
	{
		if (num>n)
		{
			cout <<i-1;
			return 0;
		}
		num*=k;
		i++;
	}
	return 0;
}
/******************************************************************************
******************************************************************************/


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next()+"+";
        int k = sc.nextInt();
        LinkedHashSet<String> hashset = new LinkedHashSet<>();
        for (int i=1;i<=k;i++){
            for (int j=0;j<=s.length()-i-1;j++){
                hashset.add(s.substring(j,j+i));
            }
        }
        ArrayList<String> array = new ArrayList<>(hashset);
        Collections.sort(array);
        System.out.println(array.get(k-1));
    }
}


Measured memory_bytes: 41880
#include <stdio.h>
#include <math.h>

int main()
{
    int n, a, b, k;
    scanf("%d%*d%*d%*d%d%d",&a,&b,&k);
    n=b-a;
    if(n>k)
        printf(":(\n");
    else

    printf("Yay!\n");
    return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

int main2() {
  int N = nextInt();
  set<int> s;
  REP(i, N) {
    int x = nextInt();
    s.insert(x);
  }
  cout << s.size() << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	string s1,s2;
	cin>>s1>>s2;
	int j=0,k=0;
	for(int i=0;i<2*n;++i)
	{
		if(i&1)
			cout<<s2[j++];
		else
			cout<<s1[k++];
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
typedef long long ll;
const int mod = 1e9 + 7;
int main() {

    int n;
    string s;
    cin >> n >> s;

    vector<int> v(10, 0);
    rep(i, n){
        v[s[i]-'0']++;
    }

    int cnt = 0, ans = 0;
    int b[10] = {};
    rep(i, n-2){
        v[s[i]-'0']--;
        if(b[s[i]-'0']==1){
            continue;
        }
        b[s[i]-'0']++;
        vector<int> tmp = v;
        int a[10] ={};
        for(int j=i+1; j<n-1; j++){
            tmp[s[j]-'0']--;
            if(a[s[j]-'0'] == 1){
                continue;
            }
            a[s[j]-'0']++;
            cnt = 0;
            for(int j=0; j<10; j++){
                if(tmp[j] >= 1){
                    cnt++;
                }
            }
            if(cnt == 0){
                break;
            }
            ans += cnt;
        }
    }
    cout << ans;


    return 0;
}   

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class mod;

#define MOD 1000000007

using lli = long long int;
using ulli = unsigned long long int;

#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

lli N, K;
lli A[100001]={};	//配列保存
lli a, b;	//入力

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

	for(lli l = 0; l < N; l++){
		cin >> a >> b;
		A[a-1] += b;
	}
	lli sum = 0;
	for(lli l = 0; ; l++){
		sum += A[l];
		if(sum >= K){
			cout << l+1 << endl;
			break;
		}
	}
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
struct Data {
  int x,y,dir;
};
 
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
 
int H,W;
string G[100];
bool used[100][100][4];
 
void count(){
  int cnt = 0;
  rep(i,H)rep(j,W) {
    rep(k,4){
      if( used[i][j][k] ) {
	++cnt;
	break;
      }
    }
  }
  cout << cnt << endl;
}
 
void compute(){
  int sp = -1;
  int idir = -1;
  rep(i,H) rep(j,W) if( G[i][j] == '>' || G[i][j] == '<' || G[i][j] == '^' || G[i][j] == 'v' ) {
    sp = j + i * W;
    if( G[i][j] == '^' ) idir = 0;
    if( G[i][j] == '>' ) idir = 1;
    if( G[i][j] == 'v' ) idir = 2;
    if( G[i][j] == '<' ) idir = 3;
    G[i][j] = '.';
    goto Skip;
  }
 Skip:;
 
  int tmpx = sp % W + dx[(idir+1)%4], tmpy = sp / W + dy[(idir+1)%4];
  if( G[tmpy][tmpx] != '#' ) {
    cout << "-1" << endl;
    return;
  }
 
 
  deque<Data> deq;
  deq.push_back((Data){sp%W,sp/W,idir});
  used[sp/W][sp%W][idir] = true;
  while(!deq.empty()){
    Data data = deq.front(); deq.pop_front();
    if( G[data.y][data.x] == 'G' ) {
      count();
      return;
    }
 
    int nx = data.x + dx[data.dir], ny = data.y + dy[data.dir];
    if( G[ny][nx] == '#' ) {
      if( used[data.y][data.x][(data.dir+3)%4] ) {
	cout << -1 << endl;
	return;
      }
      used[data.y][data.x][(data.dir+3)%4] = true;
      deq.push_back((Data){data.x,data.y,(data.dir+3)%4});
      continue;
    }
 
    if( G[ny][nx] == 'G' ) {
      used[ny][nx][data.dir] = true;
      count();
      return;
    }
 
    int hand_x = nx + dx[(data.dir+1)%4], hand_y = ny + dy[(data.dir+1)%4];
    if( G[hand_y][hand_x] == '#' ) {
      if( used[ny][nx][data.dir] ) { puts("-1"); return; }
      used[ny][nx][data.dir] = true;
      deq.push_back((Data){nx,ny,data.dir});
    } else {
      used[ny][nx][data.dir] = true;
      used[ny][nx][(data.dir+1)%4] = true;
      nx += dx[(data.dir+1)%4], ny += dy[(data.dir+1)%4];
      if( used[ny][nx][(data.dir+1)%4] ) { puts("-1"); return; }
      used[ny][nx][(data.dir+1)%4] = true;
      deq.push_back((Data){nx,ny,(data.dir+1)%4});
    }
  }
}
 
int main(){
  cin >> H >> W;
  H+=2, W+=2;
  rep(i,H) G[i].resize(W,'#');
  REP(i,1,H-1) REP(j,1,W-1) cin >> G[i][j];
  compute();
  return 0;
}

Measured memory_bytes: 1248
package main

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

func main() {
	io, flush := NewIO()
	defer flush()

	n, _ := io.ScanInt2()
	likedFoodCountMap := map[int]int{}
	for i := 0; i < n; i++ {
		k := io.ScanInt()
		likedFoods := io.ScanInts(k)
		for _, food := range likedFoods {
			likedFoodCountMap[food] += 1
		}
	}

	var allLikedFoodNum int
	for _, count := range likedFoodCountMap {
		if count == n {
			allLikedFoodNum++
		}
	}
	fmt.Println(allLikedFoodNum)
}

type IO struct {
	scanner *bufio.Scanner
	writer  *bufio.Writer
}

func NewIO() (*IO, func()) {
	io := &IO{
		scanner: newScanner(),
		writer:  newWriter(),
	}
	return io, func() { io.writer.Flush() }
}

func newScanner() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Buffer(make([]byte, 10000000), 10000000)
	s.Split(bufio.ScanWords)
	return s
}

func newWriter() *bufio.Writer {
	return bufio.NewWriter(os.Stdout)
}

func (io *IO) ScanBytes() []byte {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Bytes()
}

func (io *IO) ScanString() string {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Text()
}

func (io *IO) ScanStrings(n int) []string {
	strs := make([]string, n)
	for i := 0; i < n; i++ {
		strs[i] = io.ScanString()
	}
	return strs
}

func (io *IO) Scan2DStrings(y, x int) [][]string {
	strings := make([][]string, y)
	for i := 0; i < y; i++ {
		strings[i] = io.ScanStrings(x)
	}
	return strings
}

func (io *IO) Scan2DGraph(y int) [][]string {
	strs := make([][]string, y)
	for i := 0; i < y; i++ {
		strs[i] = strings.Split(io.ScanString(), "")
	}
	return strs
}

func (io *IO) ScanInt() int {
	return int(io.ScanInt64())
}

func (io *IO) ScanInt2() (int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt3() (int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt4() (int, int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInts(n int) []int {
	ints := make([]int, n)
	for i := 0; i < n; i++ {
		ints[i] = io.ScanInt()
	}
	return ints
}

func (io *IO) Scan2DInts(y, x int) [][]int {
	ints := make([][]int, y)
	for i := 0; i < y; i++ {
		ints[i] = io.ScanInts(x)
	}
	return ints
}

func (io *IO) ScanInt64() int64 {
	i, err := strconv.ParseInt(io.ScanString(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *IO) ScanFloat64() float64 {
	i, _ := strconv.ParseFloat(io.ScanString(), 64)
	return i
}

func (io *IO) ScanFloat64s(n int) []float64 {
	floats := make([]float64, n)
	for i := 0; i < n; i++ {
		floats[i] = io.ScanFloat64()
	}
	return floats
}

func (io *IO) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}


Measured memory_bytes: 2216
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

    int N; cin >> N;
    int d[N][N],A[N][N];
    int ans=0;
    rep(i,N) rep(j,N){
        cin >> A[i][j];
        d[i][j]=A[i][j];
        ans+=d[i][j];
    }
    ans/=2;
    rep(k, N) rep(i, N) rep(j, N)
    d[i][j] = min(d[i][k] + d[k][j], d[i][j]);
    rep(i,N) rep(j,N){
        if(i>=j) continue;
        bool frag = false;
        rep(k,N){
            if(i==k || j==k) continue;
            if(A[i][j] > d[i][k]+d[k][j]){
                cout << -1 << endl;
                return 0;
            } else if(A[i][j] == d[i][k]+d[k][j] && !frag){
                ans-=A[i][j];
                frag = true;
            }
        }
    }
    cout << ans << endl;
}

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

int main(){
  int n,m;
  cin>>n;
  vector<string> blue(n);
  
  for (int i=0;i<n;i++){
    cin>>blue.at(i);
  }
  
  cin>>m;
  vector<string> red(m);
  for (int i=0;i<m;i++){
    cin>>red.at(i);
  }
  
  int answer=0;
  
  for (string text:blue){
    
    
    int number=0;
    
    for (string tmp1:blue){
      number+=(text==tmp1);
    }
    
    for (string tmp2:red){
      number-=(text==tmp2);
    }
    
    if (number>answer){
      answer=number;
    }
  }
  
  cout<<answer<<endl;
  
}

  













Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define local
//if you find any bug in my code, please tell me.
int graph[10][10],a[10];
int main()
{
#ifdef local
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif
    int n,m,i,ans=0;
    cin>>n>>m;
    for(i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        graph[a][b]=graph[b][a]=1;
    }
    for(i=0; i<n-1; i++) a[i]=i+2;
    sort(a,a+n-1);
    do
    {
        int now=1;
        for(i=0; i<n-1; i++)
        {
            if(!graph[now][a[i]]) break;
            now=a[i];
        }
        if(i==n-1) ans++;
    }while(next_permutation(a,a+n-1));
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7

ans=0

for i in range(n):
    before=0
    whole=0
    ai=a[i]
    for j in range(n):
        if ai>a[j]:
            whole+=1
            before+=1
            if i>j:
                before-=1
    
    ans+=whole*(k*(k-1))//2 + before*k
    ans%=mod

print(ans)


Measured memory_bytes: 3188
n = int(input())
numbers = list(map(int, input().split()))

def checkCondition():
  for i in range(n-1):
    if numbers[i] > numbers[i+1]:
      if numbers[i] - numbers[i+1] > 1:
        return False
  for i in range(-1, -n, -1):
    sub = numbers[i-1] - numbers[i]
    if sub == 1:
      numbers[i-1] -= 1
    elif sub > 1:
      return False
  return True

if n == 1:
  print('Yes')
else:
  if checkCondition():
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
    int n,W;
    cin >> n >> W;
    int v[n],w[n];
    rep(i,n){
        cin >> v[i] >> w[i];
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(W + 1, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= W; j++){
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if(j - w[i] < 0) continue;
            dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
        }
    }
    cout << dp[n][W] << endl;
    return 0;
}


Measured memory_bytes: 10804
#include <bits/stdc++.h>
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define sz(v) (int)(v).size()
using namespace std;
typedef long long ll;
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	ll A, B, K;
	cin >> A >> B >> K;

	if (A >= K)
	{
		cout << A - K << ' ' << B << '\n';
	}
	else
	{
		if (A + B > K)
			cout << 0 << ' ' << A + B - K << '\n';
		else
			cout << 0 << ' ' << 0 << '\n';

	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;


int main(void)
{
	int N;

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

	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var N, t, x, y int
	fmt.Scan(&N)

	ts := []int{0}
	xs := []int{0}
	ys := []int{0}
	for i := 0; i < N; i++ {
		fmt.Scan(&t)
		fmt.Scan(&x)
		fmt.Scan(&y)
		ts = append(ts, t)
		xs = append(xs, x)
		ys = append(ys, y)
	}

	for i := 1; i <= N; i++ {
		if !canMove(ts[i] - ts[i - 1], xs[i] - xs[i - 1], ys[i] - ys[i - 1]) {
			fmt.Println("No")
			return
		}
	}

	fmt.Println("Yes")
}

func canMove(turn, dx, dy int) bool {
	if turn % 2 == 0 {
		return abs(dx + dy) <= turn && abs(dx + dy) % 2 == 0
	} else {
		return abs(dx + dy) <= turn && abs(dx + dy) % 2 == 1
	}
}

func abs(x int) int {
	if x < 0 {
		return -1 * x
	} else {
		return x
	}
}

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


int N, K;
vector<int> H;


void input() {
    cin >> N >> K;
    H = vector<int>(N);
    rep(i, N) cin >> H[i];
}


int main() {
    input();
    sort(H.begin(), H.end());
    int ans = 1e9 + 1;
    rep(i, N - K + 1) {
        ans = min(ans, H[i+K-1] - H[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
N,T = map(int,input().split())
A = list(map(int,input().split()))
B = [(0,-1) for _ in range(N)]
amax = A[-1]
ind = N-1
bmax = 0
for i in range(N-2,-1,-1):
    a = A[i]
    if a>amax:
        amax = a
        ind = i
    else:
        B[i] = (amax-a,ind)
        if bmax<amax-a:
            bmax = amax-a
C = []
for i in range(N):
    if B[i][0]==bmax:
        if B[i][1] not in C:
            C.append(B[i][1])
print(len(C))

Measured memory_bytes: 63508
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int s = sc.nextInt();
        ArrayList list = new ArrayList<Integer>();

        list.add(s);

        int ans = 0;
        for (int i = 0; i <= 1000000; i++) {
            if ((int)list.get(i) % 2 == 0) {
                if (list.contains((int)list.get(i) / 2)) {
                    ans = i + 2;
                    break;
                }
                list.add((int)list.get(i) / 2);
            } else {
                if (list.contains(3 * (int)list.get(i) + 1)) {
                    ans = i + 2;
                    break;
                }
                list.add(3 * (int)list.get(i) + 1);
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 23252
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, M = rdi()

PY = []
for i in range(M):
        p, y = rdi()
        PY.append( (p, y, i) )

spy = sorted(PY)

codes = []
lastp = -1
pj = 0
for k in range(M):
        p, y, i = spy[k]
        if p != lastp:
                lastp = p
                cj = 1
        else:
                cj = cj + 1
        code = "%06d%06d" % (int(p), cj)
        codes.append( (i, code) )

codes = sorted(codes)

for i in range(M):
        print codes[i][1]



Measured memory_bytes: 39140
#include<stdio.h>
#include<math.h>
int main()
{
	int n;
	double v;
	double neededv;

	while(scanf("%lf",&neededv)!=EOF)
	{
		n=0;
		do
		{
			n++;
			v=sqrt(2*9.8*(5*n-5));
		}while(v<neededv);
		printf("%d\n",n);
	}
	return 0;
}

Measured memory_bytes: 0
using System;
using System.Linq;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class program{
  static void Main(string[] args){
    program p = new program();
    p.Run();
  }
  void Run(){
	int[] inp = Readint();
    int res = inp[0]-inp[1]+1;
    WriteLine(res.ToString());
  }

  int[] Readint(){
    string[] s = ReadLine().Split();
    int[] res=new int[s.Length];
    Parallel.For(0,s.Length,i=>{
      res[i]=int.Parse(s[i]);
    });
    return res;
  }
}




Measured memory_bytes: 13532
#include<queue>
#include<map>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int p;
string s="";
queue<pair<string,int> > q;
void f(int a,int b){
  char c;
  c=s[a];
  s[a]=s[b];
  s[b]=c;
  q.push(make_pair(s,p+1));
  c=s[a];
  s[a]=s[b];
  s[b]=c;
  return;
}
void g(){
  if(s[0]==0){
    f(0,2);
  }
  if(s[1]==0){
    f(1,2);
    f(1,5);
  }
  if(s[2]==0){
    f(2,0);
    f(2,1);
    f(2,3);
    f(2,6);
  }
  if(s[3]==0){
    f(3,2);
    f(3,7);
  }
  if(s[4]==0){
    f(4,5);
  }
  if(s[5]==0){
    f(5,1);
    f(5,4);
    f(5,6);
    f(5,9);
  }
  if(s[6]==0){
    f(6,2);
    f(6,5);
    f(6,7);
    f(6,10);
  }
  if(s[7]==0){
    f(7,3);
    f(7,6);
    f(7,8);
    f(7,11);
  }
  if(s[8]==0){
    f(8,7);
  }
  if(s[9]==0){
    f(9,5);
    f(9,10);
  }
  if(s[10]==0){
    f(10,6);
    f(10,9);
    f(10,11);
    f(10,12);
  }
  if(s[11]==0){
    f(11,7);
    f(11,10);
  }
  if(s[12]==0){
    f(12,10);
  }
  return;
}
int main(){
  int i;
  int a;
  int mn;
  map<string,int> m,n;
  for(i=0;i<12;i++)
    s+=i;
  s+=(char)0;
  q.push(make_pair(s,1));
  for(;;){
    s=q.front().first;
    p=q.front().second;
    q.pop();
    if(p>11)
      break;
    if(m[s]==0){
      m[s]=p;
      g();
    }
  }
  while(cin>>a&&a!=-1){
    s="";
    s+=a;
    for(i=0;i<12;i++){
      cin>>a;
      s+=a;
    }
    if(m[s])
      cout<<m[s]-1<<endl;
    else{
      mn=21;
      while(q.empty()==0)
	q.pop();
      q.push(make_pair(s,1));
      n.clear();
      for(;;){
	s=q.front().first;
	p=q.front().second;
	q.pop();
	if(p>11)
	  break;
	if(m[s]&&mn>m[s]+p-2)
	  mn=m[s]+p-2;
	if(n[s]==0){
	  n[s]=p;
	  g();
	}
      }
      if(mn==21)
	cout<<"NA"<<endl;
      else
	cout<<mn<<endl;
    }
  }
  return 0;
}

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

using namespace std;

#pragma GCC optimize "-O3"

#define watch(x) cout << (#x) << " is " << (x) << endl

#define rep(i,a,b)  for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a-1;i>=b;i--)
#define nl          cout<<endl;
#define test()      lli t;cin>>t;while(t--)
#define sp(n)       setprecision(n)

#define lli     long long int
#define ulli    unsigned long long int
#define ld      long double
#define uld     unsigned long double
#define S       string
#define C       char
#define elif    else if
 
#define pb      push_back
#define pp      pop_back
#define plli    pair<lli,lli>
#define vlli    vector<lli>
#define vulli   vector<ulli>
#define vld     vector<ld>
#define vs      vector<string>

#define bs      binary_search
#define ub      upper_bound
#define lb      lower_bound

#define vsort(v) sort(v.begin(),v.end())

#define max1 1000001    //10^6 + 1
#define max2 10000001   //10^7 + 1
#define max3 1000000007 //10^9 + 7
#define inf  1000000009 //10^9 + 9

const int N = 1e5+5;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    lli n;
    cin >> n;
    lli h[n+1];
    for (int i = 1; i < n+1; ++i)
    {
    	cin >> h[i];
    }
    lli dp[n+1];
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = abs(h[2]-h[1]);
    for (int i = 3; i < n+1; ++i)
    {
    	dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]));
    }
    cout << dp[n] << '\n';

       
    
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp> 
using namespace std; 

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

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

    // Input
    vector<int> A(N, 0);
    for (int i = 0; i < N; ++i){
        cin >> A[i];
    } 
    
    // 総得票数を計算する
    int allVote = 0;
    for (int i = 0; i < A.size(); ++i){
        allVote += A[i];
    }

    // 総得票数の1/4Mを求める
    double wgt = (1.0 / (4 * M));
    double border = allVote * wgt;
    
    // 選べるかチェックする（M <= iを満たせなければNo)
    sort(A.rbegin(), A.rend());
    int i = 0;
    for (; i < A.size(); ++i){
        if (A[i] < border){
            break;
        }
    }
    if (M <= i){
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }

    return 0;
}

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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b,c,k; cin>>a>>b>>c>>k;
	int mx=max({a,b,c});
	int ret=a+b+c-mx;
	ret+=mx<<k;
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main(){
  var N, M int
  
  fmt.Scanf("%d %d\n", &N, &M)
  
  arr := make([]int, N)
  for i := 0; i < N; i++ {
    arr[i] = -1
  }
  
  for i := 0; i < M; i++ {
    var s, c int
    fmt.Scanf("%d %d\n", &s, &c)
    if arr[s-1] > 0 && arr[s-1] != c {
      fmt.Println(-1)
      return
    }
    arr[s-1] = c
  }
  
  if N == 1 {
    if arr[0] == -1 {
      arr[0] = 0
    }
    fmt.Println(arr[0])
    return
  }
  
  if arr[0] == 0 {
    fmt.Println(-1)
    return
  }
  if arr[0] == -1 {
    arr[0] = 1
  }
  for i := 0; i < N; i++ {
    if arr[i] == -1 {
      arr[i] = 0
    }
    fmt.Printf("%d", arr[i])
  }
  
}

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

using namespace std;
vector<long long> factors;
#define ll long long


#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

template<typename T>
int BS(vector<T> &mas, T val)
{
	int l, r;
	l = 0;
	r = mas.size() - 1;
	while (r - l > 1)
	{
		int mid = l + (r - l) / 2;
		if (mas[mid] < val)
		{
			l = mid;
		} else
			r = mid;
	}
	if (mas[r] == val)
		return r;
	if (mas[l] == val)
		return l;
	return -1;
}
template<typename T>
int UBS(vector<T> &mas, T val)
{
	int l, r;
	l = 0;
	r = mas.size() - 1;
	while (r - l > 1)
	{
		int mid = l + (r - l) / 2;
		if (mas[mid] < val)
		{
			l = mid;
		} else
			r = mid;
	}

	if (mas[l] >= val)
		return l;
	if (mas[r] >= val)
		return r;
	return -1;
}

ll mod(ll a, ll m)
{ return (a + (abs(a) / m) * m + m) % m; }



int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	double a,b,c;
	cin >> a >>b >> c;
	cout << a * b /2;
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) throws Exception {
		// TODO ?????????????????????????????????????????????
			Scanner sc = new Scanner(System.in);
			int a = sc.nextInt();
			double b=0,c=0,d=0,e=0;
			int x[]=new int[a];
			for(int z=0;z<a;++z){
				x[z] = sc.nextInt();
			}
			for(int z=0;z<a;++z){
				x[z] -= sc.nextInt();
				if(x[z]<0){
					x[z]=x[z]*-1;
				}
				if(e<x[z]){
					e=x[z];
				}
			}
			for(int z=0;z<a;++z){
				b = b + x[z];
			}
			
			for(int z=0;z<a;++z){
				c = c + Math.pow(x[z], 2);
			}
			c = Math.sqrt(c);
			for(int z=0;z<a;++z){
				d = d + Math.pow(x[z], 3);
			}
			d = Math.pow(d,(double)1/3);
			System.out.println(b);
			System.out.println(c);
			System.out.println(d);
			System.out.println(e);
	}

}

Measured memory_bytes: 26508
n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(1, len(p)-1):
    if p[i-1] <= p[i] and p[i] < p[i+1]:
        cnt += 1
    elif p[i-1] > p[i] and p[i] >= p[i+1]:
        cnt += 1
print(cnt)


Measured memory_bytes: 3060
import numpy as np

x1, y1, x2, y2 = map(int, input().split())
A = np.array([[0, -1], [1, 0]])
x = np.array([[x2 - x1], [y2 - y1]])
tmp = np.dot(A, x) + np.array([[x1], [y1]])
x4, y4 = tmp[0][0], tmp[1][0]

center = np.array([(x2 + x4)/2, (y2 + y4)/2])
tmp = np.array([x1, y1]) + 2 * (center - np.array([x1, y1]))
x3, y3 = int(tmp[0]), int(tmp[1])

print(x3, y3, x4, y4)

Measured memory_bytes: 12960
/*　　　＿
　 '´　　 ヽ
 ./ ﾉﾉ））)）〉＜そーなのかー
〈《.! ﾟ ヮﾟﾉ》
　⊂!::V::!つ
　 く::::::::〉
　　 し'ﾉ*/
#include <bits/stdc++.h>
using namespace std;

int main() {
  int a;
  cin >> a;
  vector<int>b(a);
  for(int i=0;i<a;i++){
  cin >> b.at(i);
  }
  int64_t d=20000000000;
  for(int i=0;i<=100;i++){
  int c=0;
    for(int j=0;j<a;j++){
    c+=(b.at(j)-i)*(b.at(j)-i);
    }
    if(d>c){
    d=c;
    }  
  }
  cout << d << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdint>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#define REP(i,n) for(LL i=0, i##_len=(n); i<i##_len; ++i)

int main() {
  int N,K;
  std::string S;
  std::cin >> N >> K;
  std::cin >> S;

  int current = 0;
  for(int i=0; i<N-1; i++) {
    if(S[i] == S[i+1]) {
      current += 1;
    }
  }

  int ans = std::min(current + 2*K, N-1);
  std::cout << ans << std::endl;

  return 0;
}



Measured memory_bytes: 512
/**
 *    author:  Sushil Sekhar Satapathy
 *    created: 30.Jul.2020 18:38:25
 *
 *    Only the ladder is real!! The climb is all there is.
 *
**/

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long int
#define mod 1000000007
#define vi vector<int>
#define pint pair<int,int>
#define vint vector<vector<int>>
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 1e6+5;
int A[N];

unordered_map<int, list<int>> mp;

void addEdge(int u, int v)
{
    mp[u].push_back(v);
    //mp[v].push_back(u);
}

int solve(int n, int src)
{
    vi dist(n, INT_MAX);
    //vi look(n, INT_MAX);
    //priority_queue<int> pq;
    queue<int> q;
    set<int> s;

    q.push(src);
    dist[src] = 0;
    s.insert(src);
    //look[src] = 0;
    //pq.push(src);
    int i, left = 0;

    while(!q.empty())
    {
        int curr = q.front();
        q.pop();

        for(auto neigh: mp[curr])
        {
            if(dist[neigh] == INT_MAX)
            {
                q.push(neigh);
                dist[neigh] = dist[curr] + 1;
                s.insert(neigh);
                //pq.push(neigh);

                /*int top = pq.top();
                int minimum = INT_MAX;

                for(i=neigh; i<=top; i++)
                    minimum = min(minimum, dist[i]);
                if(dist[neigh] > minimum)
                    dist[neigh] = minimum;*/
                /*if(neigh >= left)
                {
                    for(i=left+1;i<=neigh;i++)
                        look[i] = min(look[i], dist[neigh]);
                    left = neigh;
                }
                else
                    dist[neigh] = min(dist[neigh], look[neigh]);*/

                auto ub = upper_bound(s.begin(), s.end(), neigh);
                if(ub != s.end())
                    dist[neigh] = min(dist[neigh], dist[*ub]);
            }
        }
    }

    int sum = 0;
    for(auto x: dist)
    {
        //cout<<x<<" ";
        sum += x;
    }
    //cout<<endl;
    return sum;
}

int32_t main()
{
    //code
	IOS;
	//#ifndef ONLINE_JUDGE
    //freopen("alchemy_input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //#endif

    int t,n,m,a,b,x,y,i,j,z;
    //cin>>t;
    t=1;
    while(t--)
    {
        cin>>x;
        if(x>=30) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

	return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <typeinfo>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    ll n, tmp;

    cin >> n;
    vector<int> a(n + 1, 0);
    rep(i, n - 1)
    {
        cin >> tmp;
        a[tmp]++;
    }
    rep(i, n)
    {
        cout << a[i + 1] << endl;
    }
    // cout << endl;
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int MaxSize = 100005;
int main()
{
    ll n;
    cin >> n;
    int hund = n/100;
    int fract = n % 100;
    int tFract = 0;
    tFract += fract / 5;
    fract = fract % 5;
    tFract += fract / 4;
    fract = fract % 4;
    tFract += fract / 3;
    fract = fract % 3;
    tFract += fract/2;
    fract = fract % 2;
    tFract += fract/1;
    if(hund >= tFract)
    {
        cout << "1" << endl;
    }
    else
    {
        cout << "0" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

int main(int argc, char* argv[]){
	vector<int> v;
	int A, B, C;
	
	for(int i=0; i<3; i++){
		int d;
		cin >> d;
		v.push_back(d);
	}
	sort(v.begin(), v.end());

	A = v[0], B = v[1], C = v[2];
	int s = B - A;
	int t = C - B;

	int ans = 0;
	if(s % 2 == 0){
		ans = s / 2 + t;
	}
	else{
		ans = 1 + (s + 1)/2 + t;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int ans = 0;
	string s, t;
	cin >> s >> t;
	int len = s.length();
	for (int i = 0; i < len; i++) {
		if (s[i] != t[i]) ans++;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;
  if (m1 != m2) {
    puts("1");
  } else {
    puts("0");
  }

  return 0;
}


Measured memory_bytes: 3620
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;

#define FST first
#define SND second

#define MAX_N   (100000)                  // 10^5
// #define MAX_N   (1000000000)              // 10^9
// #define MAX_N   (1000000000000000000)     // 10^18
#define BASE    (1000000000 + 7)          // 10^9 + 7
#define INFI    (1000000000 + 7)          // 10^9 + 7
#define INFL    (1000000000000000000 + 7) // 10^18 + 7

int H, W;

int split_T(int x, int y, int w, int h) {
  int s1 = x * h;
  int s2 = (w - x) * y;
  int s3 = (w - x) * (h - y);
  int d1 = abs(s1 - s2);
  int d2 = abs(s2 - s3);
  int d3 = abs(s3 - s1);
  return max(d1, max(d2, d3));
}

int split_choco() {
  int ans = INFI;
  if (H % 3 == 0) return 0;
  ans = min(ans, W);
  if (W % 3 == 0) return 0;
  ans = min(ans, H);
  int x = W / 3;
  int y = H / 2;
  ans = min(ans, split_T(x, y, W, H));
  ans = min(ans, split_T(x + 1, y, W, H));
  x = W / 2;
  y = H / 3;
  ans = min(ans, split_T(y, x, H, W));
  ans = min(ans, split_T(y + 1, x, H, W));
  return ans;
}

void solve() {
  int ans = split_choco();
  cout << ans << endl;
}

int main() {
  cin >> H >> W;

  solve();

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    sort(d.begin(), d.end());
    int ok = 0, ng = d[0] + 1;
    while (ng - ok > 1) {
        int mid = (ng + ok) / 2;
        vector<int> t(n, -1);
        int cur = 0;
        for (int i = 0; i < n; i++) {
            if (d[i] - cur >= mid) {
                cur = d[i];
                t[i] = d[i];
            } else {
                t[i] = 24 - d[i]; 
            }
        }
        bool flag = true;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = abs(t[i] - t[j]);
                if (min(tmp, 24 - tmp) < mid) {
                    flag = false;
                    break;
                }
            }
            if (!flag) break;
        }
        if (flag) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void readInt(int &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x*=f;
}
inline void readLong(ll &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x*=f;
}
/*================Header Template==============*/
int n,k;
struct node{
	ll a,b;
	bitset<32> s;
}x[100050];
bitset<32> now;
int main() {
	readInt(n);
	readInt(k);
	for(int i=1;i<=n;i++) {
		readLong(x[i].a);
		readLong(x[i].b);
		x[i].s.reset();
		for(int j=30;j>=0;j--) {
			int tmp=pow(2,j);
//			cout<<x[i].a<<" "<<tmp<<endl;
			if(x[i].a>=tmp) {
				x[i].a-=tmp;
				x[i].s[j]=1;
			}
		}
//		for(int j=0;j<30;j++)
//			cout<<x[i].s[j];
//		cout<<endl;
	}
	ll afo=k;
	for(int i=30;i>=0;i--) {
		int tmp=pow(2,i);
		if(afo>=tmp) {
			afo-=tmp;
			now[i]=1;
		}
	}
//	cout<<"====================="<<endl;
//	for(int i=0;i<30;i++)
//		cout<<now[i];
//	cout<<endl;
	ll mx=0;
	bitset<32> tmp;
	tmp.reset();
	for(int i=1;i<=n;i++) {
		bitset<32> fk;
		fk=tmp|x[i].s;
		bool f=1;
		for(int j=0;j<=30;j++)
			if(fk[j]==1&&now[j]==0) {
				f=0;
				break;
			}
		if(!f)
			continue;
		tmp|=x[i].s;
//		for(int j=0;j<30;j++)
//			cout<<tmp[j];
//		cout<<endl;
		mx+=x[i].b;
	}
	for(int i=30;i>=0;i--) {
		if(now[i]==0)
			continue;
		bitset<32> xx;
		xx.reset();
		for(int j=30;j>i;j--)
			xx[j]=now[j];
		xx[i]=0;
		for(int j=i-1;j>=0;j--)
			xx[j]=1;
		ll sum=0;
		bitset<32> tmp;
		tmp.reset();
		for(int p=1;p<=n;p++) {
			bitset<32> fk;
			fk=tmp|x[p].s;
			bool f=1;
			for(int j=0;j<=30;j++)
				if(fk[j]==1&&xx[j]==0) {
					f=0;
					break;
				}
			if(!f)
				continue;
			tmp|=x[p].s;
			sum+=x[p].b;
		}
		mx=max(mx,sum);
	}
	printf("%lld\n",mx);
	return 0;
}

Measured memory_bytes: 2560
#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 <<"Left";
  }
  else{
    if (a+b<c+d){
      cout <<"Right";
    }
    else{
      cout <<"Balanced";
    }
  }
}


Measured memory_bytes: 256
// Copyright 2017 wu_qing
#include <cstdint>
#include <cstdio>
int64_t n, x;
inline int64_t gcd(int64_t a, int64_t b) {
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    scanf("%lld%lld", &n, &x);
    printf("%lld\n", 3 * (n - gcd(n, x)));
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const long INF = 1e9;
const long MOD = 1e9 + 7;
#define repi(i, n, init) for (int i = init; i < int(n); i++)

vector<string> bubbleSort(vector<string> A)
{
    bool state = true;
    int cnt = 0;
    while (state)
    {
        state = false;
        repi(i, A.size(), 1)
        {
            if (A[i][1] < A[i - 1][1])
            {
                swap(A[i], A[i - 1]);
                state = true;
                cnt++;
            }
        }
    }
    return A;
}
vector<string> selectionSort(vector<string> &A)
{
    int m, cnt = 0;
    repi(i, A.size(), 0)
    {
        m = i;
        repi(j, A.size(), i + 1)
        {
            if (A[j][1] < A[m][1])
            {
                m = j;
            }
        }
        if (A[i][1] != A[m][1])
        {
            cnt++;
            swap(A[i], A[m]);
        }
    }
    return A;
}
int main()
{
    int n;
    cin >> n;
    vector<string> A(n), B, S;
    vector<vector<char>> order(9);
    repi(i, n, 0)
    {
        cin >> A[i];
        order[A[i][1] - '0' - 1].push_back(A[i][0]);
    }
    B = bubbleSort(A);
    S = selectionSort(A);

    bool state = true;
    int j = 0;
    repi(i, n, 0)
    {
        cout << B[i] << ((i + 1) % n ? " " : "");
        if (i > 0)
        {

            if (B[i][1] == B[i - 1][1])
            {
                if (B[i - 1][0] != order[B[i  - 1][1] - '0'- 1][j])
                {
                    state = false;
                }
                j++;
            }
            else
            {
                j = 0;
            }
        }
    }
    cout << endl
         << (state ? "Stable" : "Not Stable") << endl;
    state = true;
    j = 0;
    repi(i, n, 0)
    {
        cout << S[i] << ((i + 1) % n ? " " : "");
        if (i > 0)
        {

            if (S[i][1] == S[i - 1][1])
            {
                if (S[i - 1][0] != order[S[i  - 1][1] - '0'- 1][j])
                {
                    state = false;
                }
                j++;
            }
            else
            {
                j = 0;
            }
        }
    }
    cout << endl
         << (state ? "Stable" : "Not stable") << endl;
    return 0;
}


Measured memory_bytes: 3248
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,p[(1<<16)+2],ans,sum,f[(1<<16)+2][20],a[30][30];
int main()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	memset(f,-1,sizeof(f));
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z,a[y][x]=z;
		sum+=z;
	}
	for(int i=1;i<(1<<n);i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(1<<(j-1)&i)
			{
				for(int k=1;k<=n;k++)
				{
					if(1<<(k-1)&i)
					{
						p[i]+=a[j][k];
					}
				}
			}
		}
		p[i]>>=1;
	}
	f[1][1]=0;
	for(int i=1;i<(1<<n);i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(f[i][j]==-1) continue;
			for(int k=1;k<=n;k++)
			{
				if(i&(1<<(k-1))) continue;
				if(!a[j][k]) continue;
				f[i|(1<<(k-1))][k]=max(f[i|(1<<(k-1))][k],f[i][j]+a[j][k]);
			}
			int tmp=(((1<<n)-1)^i)|(1<<(j-1));
			for(int k=tmp;k;k=(k-1)&tmp)
			{
				f[i|k][j]=max(f[i|k][j],f[i][j]+p[k]);
			}
		}
	}
	for(int i=1;i<(1<<n);i++)
	{
		ans=max(ans,f[i][n]);
	}
	cout<<sum-ans;
	return 0;
}


Measured memory_bytes: 5504
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
vector<char> a,b,c,d;
int main(){
  cin>>n>>s;
  a.push_back('S');
  a.push_back('S');
  b.push_back('S');
  b.push_back('W');
  c.push_back('W');
  c.push_back('S');
  d.push_back('W');
  d.push_back('W');
  for(int i=1;i<n;i++){
    if(a[i]=='S'){
      if(s[i]=='o'){
        if(a[i-1]=='S'){
          a.push_back('S');
        }else{
          a.push_back('W');
        }
      }else{
        if(a[i-1]=='S'){
          a.push_back('W');
        }else{
          a.push_back('S');
        }
      }
    }else{
      if(s[i]=='o'){
        if(a[i-1]=='S'){
          a.push_back('W');
        }else{
          a.push_back('S');
        }
      }else{
        if(a[i-1]=='S'){
          a.push_back('S');
        }else{
          a.push_back('W');
        }
      }
    }
    if(b[i]=='S'){
      if(s[i]=='o'){
        if(b[i-1]=='S'){
          b.push_back('S');
        }else{
          b.push_back('W');
        }
      }else{
        if(b[i-1]=='S'){
          b.push_back('W');
        }else{
          b.push_back('S');
        }
      }
    }else{
      if(s[i]=='o'){
        if(b[i-1]=='S'){
          b.push_back('W');
        }else{
          b.push_back('S');
        }
      }else{
        if(b[i-1]=='S'){
          b.push_back('S');
        }else{
          b.push_back('W');
        }
      }
    }
    if(c[i]=='S'){
      if(s[i]=='o'){
        if(c[i-1]=='S'){
          c.push_back('S');
        }else{
          c.push_back('W');
        }
      }else{
        if(c[i-1]=='S'){
          c.push_back('W');
        }else{
          c.push_back('S');
        }
      }
    }else{
      if(s[i]=='o'){
        if(c[i-1]=='S'){
          c.push_back('W');
        }else{
          c.push_back('S');
        }
      }else{
        if(c[i-1]=='S'){
          c.push_back('S');
        }else{
          c.push_back('W');
        }
      }
    }
    if(d[i]=='S'){
      if(s[i]=='o'){
        if(d[i-1]=='S'){
          d.push_back('S');
        }else{
          d.push_back('W');
        }
      }else{
        if(d[i-1]=='S'){
          d.push_back('W');
        }else{
          d.push_back('S');
        }
      }
    }else{
      if(s[i]=='o'){
        if(d[i-1]=='S'){
          d.push_back('W');
        }else{
          d.push_back('S');
        }
      }else{
        if(d[i-1]=='S'){
          d.push_back('S');
        }else{
          d.push_back('W');
        }
      }
    }
  }
  if(a.front()==a.back()){
    if(s[0]=='o'&&a[1]==a[n-1]||s[0]=='x'&&a[1]!=a[n-1]){
      for(int i=0;i<n;i++){
        cout<<a[i];
      }
      return 0;
    }
  }
  if(b.front()==b.back()){
    if(s[0]=='o'&&b[1]==b[n-1]||s[0]=='x'&&b[1]!=b[n-1]){
      for(int i=0;i<n;i++){
        cout<<b[i];
      }
      return 0;
    }
  }
  if(c.front()==c.back()){
    if(s[0]=='o'&&c[1]!=c[n-1]||s[0]=='x'&&c[1]==c[n-1]){
      for(int i=0;i<n;i++){
        cout<<c[i];
      }
      return 0;
    }
  }
  if(d.front()==d.back()){
    if(s[0]=='o'&&d[1]!=d[n-1]||s[0]=='x'&&d[1]==d[n-1]){
      for(int i=0;i<n;i++){
        cout<<d[i];
      }
      return 0;
    }
  }
  cout<<-1;
}

Measured memory_bytes: 1120
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;

int N;
unordered_set<int> visited;
map<int, vector<int>> edges;
map<int, vector<int>> subtree_sizes;

ll mod_exp(ll x, ll exp) {
    ll ans = 1;
    ll base = x % MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            ans = (ans * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return ans;
}

ll mod_inv_prime(ll x) {
    return mod_exp(x, MOD-2);
}

int dfs(int v) {
    // cout << v << endl;
    visited.insert(v);
    int total_size = 0;
    for (int ne : edges[v]) {
        // cout << "attempt visit " << ne << endl;
        if (!visited.count(ne)) { 
            int subtree_size = dfs(ne) + 1;
            // cout << "subtree size " << subtree_size << endl;
            if (subtree_size > 0) {
                subtree_sizes[v].push_back(subtree_size);
            }
            total_size += subtree_size;
        }
    }
    if (N - 1 - total_size > 0) {
        subtree_sizes[v].push_back(N-1-total_size);
    }
    return total_size;
}

int main() {
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
    }

    dfs(0);

    ll ev = 0;
    ll two_inv = mod_inv_prime(2);
    vector<ll> two_inv_pow = {1};
    ll curr = 1;
    for (int i = 0; i < N; i++) {
        curr = (curr * two_inv) % MOD;
        two_inv_pow.push_back(curr);
    }

    for (int i = 0; i < N; i++) {
        if (subtree_sizes[i].size() < 2) continue;
        ll p_all_white = 1;
        for (int subtree_size : subtree_sizes[i]) {
            p_all_white = (p_all_white * two_inv_pow[subtree_size]) % MOD;
        }
        ll p_one_black = 0;
        for (int subtree_size : subtree_sizes[i]) {
            ll p_t_white = two_inv_pow[subtree_size];
            ll p_t_black = (1 - p_t_white + MOD) % MOD;
            ll prob = (p_t_black * mod_inv_prime(p_t_white)) % MOD;
            p_one_black = (p_one_black + prob) % MOD;
        }
        p_one_black = (p_one_black * p_all_white) % MOD;
        ll cond_prob = (1 - ((p_all_white + p_one_black) % MOD) + MOD) % MOD;
        // ll total_prob = (two_inv * cond_prob) % MOD;
        ev = (ev + cond_prob) % MOD;
    }

    ev = (two_inv * ev) % MOD;

    cout << ev << endl;

}


Measured memory_bytes: 68680
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned ll
using namespace std;
inline int read(){
	int s=0,t=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*t;
}
const int N=1e5+5;
char s[N];
int n,a[N];
void Exit(){puts("-1"),exit(0);}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++)a[i]=s[i]-'0';
	for(int i=0;i<=n;i++)if(a[i]^a[n-i])Exit();
	if(!a[1])Exit();a[n]=1;
	int tot=1,lst=1;
	for(int i=2;i<=n;i++)
	if(a[i]){
		printf("%d %d\n",i,tot);
		for(int j=lst+1;j<i;j++)printf("%d %d\n",i,++tot);
		lst=tot=i;
	}
	return 0;
}


Measured memory_bytes: 4252