akhauriyash/Code-Regression huggingface dataset:
"""
T E S T
"""

from collections import Counter, deque

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

cnt_a = Counter(A)
cnt_b = Counter(B)

cnt_ab = cnt_a + cnt_b

for i in cnt_ab.values():
    if i > N:
        print("No")
        exit()


print("Yes")
dq_a = deque(A)
dq_b = deque(B)

ans = []

dq_b.rotate(N // 2)

while dq_a:
    if dq_a[0] != dq_b[0]:
        dq_a.popleft()
        p = dq_b.popleft()
        ans.append(p)
        # ans.append(b.popleft())
    else:
        dq_b.rotate()
print(*ans)


Measured memory_bytes: 191504
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int a = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i-1; j < n; ++j) {
            string w;
            for (int k = 0; k < n; ++k) {
                if(i <= k && k <= j) continue;
                else w += s[k];
            }
            if(w.size() == 7){
                if(w == "keyence"){
                    a++;
                }
            }
        }
    }
    puts(a ? "YES" : "NO");
    return 0;
}


Measured memory_bytes: 256
def main():
    L, R = map(int, input().split())
    # 60 の相異なる素因数は 3, 673 の 2つ
    if L + 672 <= R:
        print(0)
        return
    elif L % 2019 == 0:
        print(0)
        return
    elif L % 673 == 0 and L + 2 <= R:
        print(0)
        return
    elif R % 673 < L % 673 and L + 2 <= R:
        print(0)
        return
    print(min(i * j % 2019 for i in range(L, R + 1)
              for j in range(i + 1, R + 1)))
    return


main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    if(S.size() == 1) {
        cout << 1 << endl;
        return 0;
    }
    int ans = 0;
    string LAST = "";
    for(int i = 0; i < S.size(); i++) {
        if(i + 2 == S.size()) {
            if(S[i] == S[i+1]) {
                ans++;
                i += 2;
                continue;
            }
        }
        if(S.substr(i, 1) == LAST) {
            LAST = S.substr(i, 2);
            i++;
        } else {
            LAST = S.substr(i, 1);
        }
        ans++;
    }
    cout << ans << endl;
    return 0;
}


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

pair<int,int> h1[120000],h2[120000];
int n;
int a[120000];
int mxh1,mxh2;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i+=2)
	{
		h1[a[i]].first++;
	}
	for(int i=2;i<=n;i+=2)
	{
		h2[a[i]].first++;
	}
	for(int i=1;i<=100000;i++)
	{
		h1[i].second=h2[i].second=i;
	}
	sort(h1+1,h1+100001);
	sort(h2+1,h2+100001);
	if(h1[100000].second!=h2[100000].second) printf("%d",n-h1[100000].first-h2[100000].first);
	else printf("%d",n-max(h1[99999].first+h2[100000].first,h1[100000].first+h2[99999].first));
}

Measured memory_bytes: 2176
d={}
for _ in[0]*int(input()):
 k,v=input().split()
 d[k]=d.get(k,0)+int(v)
for k in sorted(d,key=lambda x:(sum(27**i*(ord(k)-64)for i,k in enumerate(x[::-1])),x)):
 print(k,d[k])


Measured memory_bytes: 5692
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n, m;
  cin >> n >> m;
  vector<int> x(m);
  rep(i, 0, m) cin >> x[i];
  sort(x.begin(), x.end());

  vector<int> absdiff(m - 1);
  rep(i, 1, m) absdiff[i - 1] = abs(x[i] - x[i - 1]);

  sort(absdiff.rbegin(), absdiff.rend());
  ll ans = 0;
  rep(i, n - 1, m - 1) ans += absdiff[i];

  cout << ans << endl;
}


Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<int,P>
#define vpp vector<PP>
#define fi first
#define se second
#define INF (1<<30)
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    double a,b;
    cin>>a>>b;
    cout<<(int)(pow(2,b)*((a-b)*100+b*1900))<<endl;
    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

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

		while(true){
			int H = stdIn.nextInt();
			int W = stdIn.nextInt();

			if( H == 0 && W == 0) {
				break;
			}

			for (int i = 0; i < H; i ++) {
				for (int j = 0; j < W; j++) {
					if(i == 0 || i == (H-1)) {
						System.out.print("#");
					} else {
						if(j==0 || j ==(W-1)){
							System.out.print("#");
						} else {
							System.out.print(".");
						}
					}
				}
				System.out.println();
			}
			System.out.println();
		}
		stdIn.close();

	}
}



Measured memory_bytes: 35720
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong n;
llong a[300005];
llong bi[64];
const llong mod = (llong)(1e9) + 7;

void cnt(llong a) {
    llong c = 0;

    while (a > 0) {
        if (a & 1) bi[c]++;

        c++;
        a >>= 1;
    }
}

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

    cnt(a[n - 1]);
    llong ans = 0;
    llong m = 1;
    for (int i = n - 2; i >= 0; i--) {
        llong c = 0;
        llong mul;
        
        cnt(a[i]);
        m++;
        while (c < 60) {
            if (a[i] & 1) {
                mul = m - bi[c];
            }
            else {
                mul = bi[c];
            }

            ans += (1ll << c) % mod * mul % mod;
            ans %= mod;

            c++;
            a[i] >>= 1;
        }
        
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2560
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

#define MAXN (1 << 20)

int a[MAXN];

int main() {
	cout << fixed << setprecision(12);	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll cur = 0;
	ll ret = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] > cur) {
			cur = a[i];
		} else {
			ret += cur - a[i];
		}
	}
	cout << ret << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 4412
#![allow(unused_imports)]
// use itertools::Itertools;
use proconio::{input, marker::*};

fn main() {
    input! {
        n: usize,
        aa: [usize; n]
    };
    if n == 1 {
        println!("0");
        return;
    }
    let mut sum = 0;
    let mut pre_height = aa[0];
    for &a in &aa[1..n] {
        if a < pre_height {
            let diff = pre_height - a;
            sum += diff;
        } else {
            pre_height = a
        }
    }
    println!("{}", sum);
}


Measured memory_bytes: 5592
// Problem : E - Flatten
// Contest : AtCoder Beginner Contest 152
// URL : https://atcoder.jp/contests/abc152/tasks/abc152_e
// Memory Limit : 1024.000000 MB 
// Time Limit : 2000.000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor)

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

#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;

int aray[10004], gcdForw[10004], gcdBack[10004];

int qpow(int base, int expo) {
	if(expo == 0) return 1;
	if(expo == 1) return base;
	ll v = qpow(base, expo>>1);
	v = (v * v % MOD);
	if(expo&1) v = (v * base % MOD);
	return v;
}

int modinv(ll val) {
	return qpow(val%MOD, MOD-2);
}

int mx[1000006];

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int N; cin >> N;
	ll lcm = 1;
	rep(i, N) {
		cin >> aray[i];
		int x = aray[i];
		for(int v=2; v*v<=x; v++) {
			if(x%v) continue;
			int cur = 0;
			while(x%v == 0) {
				cur++;
				x /= v;
			}
			mx[v] = max(mx[v], cur);
		}
		if(x != 1) mx[x] = max(mx[x], 1);
	}
	rep(i, 1000006) {
		if(mx[i]) lcm = (lcm * qpow(i, mx[i])) % MOD;
	}
	log(lcm);
	ll su = 0;
	rep(i, N) su = (su + lcm * modinv(aray[i])) % MOD;
	cout << su << endl;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
long long arr [110000];

int main ()
{
int n,w;
int wi,vi;
cin >>n>>w;
int i,j;
for (i = 1 ;i <= n;i++)
{
cin >>wi>>vi;
for (j = w - wi;j >= 0;j --)
{
arr [j + wi] = max (arr [j + wi] , arr [j] + vi);
}
}
long long t ;
t = 0;
for (i = 0 ; i <= w;i ++)
{
t = max (t , arr [i]);
}
cout <<t<<'\n';

}

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

#define SIZE 100009

int N;
int arr[SIZE];
int ans[SIZE];

void solve()
{
     ans[1] = 0;
     ans[2] = abs(arr[1] - arr[2]);
     for(int i = 3 ; i <= N ; i++){
        ans[i] = min(ans[i-1] + abs(arr[i] - arr[i-1]) , ans[i - 2] + abs(arr[i] - arr[i - 2]));
     }
}

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

    cin >> N;
    for(int i = 1 ; i <= N ; i++){
        cin >> arr[i];
    }
    solve();
    cout << ans[N] << '\n';
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();
        String word = scanner.next();
        String answer = "";
        for(int i = 0; i < word.length(); i ++){
            int current = word.charAt(i);
            if(current + number > 90){
                answer+= (char)( current + number - 90 + 64 );
            }
            else{
                answer += (char)(current + number);
            }
        }
        System.out.println(answer);
    }
}

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

int main() {
    int K, S;
    cin >> K >> S;
    int count=0;
    for (int i=0; i<=K; i++){
        for (int j=0; j<=K; j++){
            if (0<=S-i-j && S-i-j<=K) count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,s,n) for(i=s;i<n;i++)
#define ff first
#define ss second
#define pb push_back
ll i,j;

int main() {
   ll n;
   cin>>n;
   ll ac = 0,wa = 0, re = 0,tle = 0;
   string s[n];
   f(i,0,n)
   {
       cin>>s[i];
       if(s[i].compare("AC")==0)
       ac++;
       if(s[i].compare("WA")==0)
       wa++;
       if(s[i].compare("RE")==0)
       re++;
       if(s[i].compare("TLE")==0)
       tle++;
       
   }
   cout<<"AC x "<<ac<<endl;
   cout<<"WA x "<<wa<<endl;
   cout<<"TLE x "<<tle<<endl;
   cout<<"RE x "<<re<<endl;
	return 0;
}

Measured memory_bytes: 6748
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from time import time
from random import randint
from copy import deepcopy

start_time = time()

def calcScore(t, s, c):
    scores = [0]*26
    lasts = [0]*26
    for i in range(1, len(t)):
        scores[t[i]] += s[i][t[i]]
        dif = i - lasts[t[i]]
        scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
        lasts[t[i]] = i
    for i in range(26):
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2
    return scores

def update(socre, day, t, q):
    p = t[day]
    t[day] = q
    scores[p] = 0
    scores[q] = 0
    lasts = [0]*26
    for i in range(1, len(t)):
        if t[i] == p or t[i] == q:
            scores[t[i]] += s[i][t[i]]
            dif = i - lasts[t[i]]
            scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
            lasts[t[i]] = i
    for i in [p, q]:
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2

def greedy(c, s):
    day_lim = len(s)
    socres = [0]*26
    t = [0]*day_lim
    lasts = [0]*26
    for i in range(1, day_lim):
        pls = [v for v in socres]
        mns = [v for v in socres]
        for j in range(26):
            pls[j] += s[i][j]
            mns[j] -= c[j] * (i - lasts[j])
        sum_mns = sum(mns)
        pt = sum_mns - mns[0] + pls[0]
        idx = 0
        for j in range(1, 26):
            tmp = sum_mns - mns[j] + pls[j]
            if pt < tmp:
                pt = tmp
                idx = j
        t[i] = idx
        lasts[idx] = i
        for j in range(26):
            if j == idx:
                socres[j] = pls[j]
            else:
                socres[j] = mns[j]
    return socres, t

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))

scores, t = greedy(c, s)
sum_score = sum(scores)

while time() - start_time < 1.75:
    day = randint(1, D)
    q = randint(0, 25)
    if q == t[day]:
        continue
    tmp_t = deepcopy(t)
    tmp_t[day] = q
    tmp_scores = calcScore(tmp_t, s, c)
    sum_tmp_score = sum(tmp_scores)
    if sum_score < sum_tmp_score:
        sum_score = sum_tmp_score
        t = tmp_t
        scores = tmp_scores

for v in t[1:]:
    print(v+1)

Measured memory_bytes: 91736
#include <bits/stdc++.h>
#include <string.h>
#define rep(i, n) for(int i = 0; i<(n); i++)
using namespace std;
typedef long long ll;
static const int MAX = 200000; 
//pi = 3.14159265358979323846

int main() {

    double n, sum = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        if(i % 2 != 0)sum++;
    }
    double ans = 0;
    ans = sum / n;

    cout << ans;

}




Measured memory_bytes: 256
class DisjointSets:#Union-Find
    def __init__(self, n):
        self.nodes = [-1] * n #根にサイズを負の値で格納する。
    def find(self, i):
        if self.nodes[i] < 0: #値が負の場合は根
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) #縮約
            return self.nodes[i]
    def unite(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: #サイズ比較してiの方がサイズが大きいようにする
            i, j = j, i
        self.nodes[i] += self.nodes[j] #大きい方に小さい方を統合しサイズを登録する。
        self.nodes[j] = i # jの親はi
    
    def size(self, i): # 所属する集合の大きさを返す
        i = self.find(i)
        return -self.nodes[i]

n, m, k = map(int, input().split())
ds = DisjointSets(n)
friends_count = [0] * n

for _ in range(m):
    a, b = map(lambda x:int(x)-1, input().split())
    friends_count[a] += 1
    friends_count[b] += 1
    ds.unite(a, b)
block_count = [0] * n
for _ in range(k):
    a, b = map(lambda x:int(x)-1, input().split())
    if ds.find(a) == ds.find(b):
        block_count[a] += 1
        block_count[b] += 1

print(' '.join([str(ds.size(i) - friends_count[i] - block_count[i] - 1) for i in range(n)]))


Measured memory_bytes: 88944
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
typedef pair<ld, ld> pdd;

const int mod = 1e9 + 7;

void add(int &x, int y) {
    x += y;
    x %= mod;
}

int mul(int x, int y) {
    return (llong)x * y % mod;
}

int pw(int x, int p) {
    int r = 1;
    while (p) {
        if (p & 1) r = mul(r, x);
        x = mul(x, x);
        p >>= 1;
    }
    return r;
}

int fac[1001];
int rev[1001];

int nCr(int n, int r) {
    return mul(fac[n], mul(rev[r], rev[n - r]));
}

void init(int N) {
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = mul(fac[i - 1], i);
    rev[N] = pw(fac[N], mod - 2);
    for (int i = N; i--; ) rev[i] = mul(rev[i + 1], i + 1);
}

int dp[1001][1001];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    init(n);
    dp[a - 1][0] = 1;
    for (int i = a; i <= b; ++i) {
        for (int j = 0; j <= n; ++j) {
            add(dp[i][j], dp[i - 1][j]);
            int it = fac[n - j];
            for (int k = 1; k <= d && k * i + j <= n; ++k) {
                it = mul(it, rev[i]);
                if (k < c) continue;
                int val = mul(it, mul(rev[k], rev[n - j - k * i]));
                add(dp[i][k * i + j], mul(dp[i - 1][j], val));
            }
        }
    }
    printf("%d\n", dp[b][n]);
    return 0;
}

Measured memory_bytes: 4224
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>
#include <queue>
#include <unordered_set>
#include <climits>
#include <set>
#include <list>
#include <cmath>

using namespace std;
typedef long long ll;

struct Edge;
struct Node{
	ll cost;
	bool isClosed;
	vector<Edge*> edges;
	Node* last;
	int id;
	
	Node(){}
};

struct NODE{
	Node* node;
	ll costWhenPushed;
	bool operator<(const NODE& rhs) const { return costWhenPushed > rhs.costWhenPushed; } // 逆にする
	NODE(Node* n, ll cost){
		node = n;
		costWhenPushed = cost;
	}
};

struct Edge{
	Node* node0;
	Node* node1;
	ll cost;
};

vector<Node> Nodes;
vector<Edge> Edges;

ll Dijkstra_Find(Node* s, Node* g){
	// 初期化
	for(int i = 0; i < Nodes.size(); i++){
		Nodes[i].cost = &Nodes[i] == s ? 0 : LLONG_MAX / 2;
		Nodes[i].isClosed = false;
		Nodes[i].last = nullptr;
	}
	priority_queue<NODE> que;
	que.push(NODE(s, 0));
	
	while(!que.empty()){
		Node* n = que.top().node;
		ll costWhenPushed = que.top().costWhenPushed;
		que.pop();
		if(n->cost < costWhenPushed){
			continue;
		}
		n->isClosed = true;
		
		int size = (n->edges).size();
		for(int i = 0; i < size; i++){
			Node* processNode = (n->edges)[i]->node0 == n ? (n->edges)[i]->node1 : (n->edges)[i]->node0;
			if(processNode->isClosed){
				continue;
			}
			
			ll newCost = n->cost + (n->edges)[i]->cost;
			if( newCost < processNode->cost ){
				processNode->cost = newCost;
				processNode->last = n;
				que.push(NODE(processNode, newCost));
			}
		}
	}
	
	return g->cost;
}



int main()
{
	int N, M;
	cin >> N >> M;
	for(int i = 0; i <= N; i++){
		Node node;
		node.id = i;
		Nodes.push_back(node);
	}
	for(int i = 0; i <= M; i++){
		Edge edge;
		Edges.push_back(edge);
	}
	
	for(int i = 1; i <= M; i++){
		int A, B;
		cin >> A >> B;
		Edge* edge = &Edges[i];
		Node* nodeA = &Nodes[A];
		Node* nodeB = &Nodes[B];
		edge->node0 = nodeA;
		edge->node1 = nodeB;
		(nodeA->edges).push_back(edge);
		(nodeB->edges).push_back(edge);
		edge->cost = 1;
	}
	
	Dijkstra_Find(&Nodes[1], &Nodes[N-1]);
	
	cout << "Yes" << endl;
	for(int i = 2; i <= N; i++){
		cout << Nodes[i].last->id << endl;
	}
	
	return 0;
}

Measured memory_bytes: 23132
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N;
    vector< vector<int> > poly;
    cin >> N;
    for(int i=0;i<N;i++){
        vector<int> v;
        int x,y,z;
        cin >> x >> y >> z;
        v.push_back(x);
        v.push_back(y);
        v.push_back(z);
        sort(v.begin(),v.end());
        poly.push_back(v);
    }
    sort(poly.begin(),poly.end());
    poly.erase(unique(poly.begin(), poly.end()), poly.end());
    cout << N-poly.size() << endl;
}


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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = euclid(b, a % b, y, x);
        return y -= a/b * x, d; }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1) ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1); return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this ^ (e / 2); r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);

    int a, b, c; cin >> a >> b >> c;
    if (a <= c && c <= b || a >= c && c >= b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define ll long long
#define $1 first
#define $2 second
#pragma warning(disable : 4996)

using namespace std;

void solve_case();

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

	solve_case();

	return 0;
}

void solve_case() {
	char c;

	cin >> c;

	if (c == 'A')
		cout << "T\n";
	else if (c == 'T')
		cout << "A\n";
	else if (c == 'G')
		cout << "C\n";
	else
		cout << "G\n";
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[32]:


import numpy as np


# In[22]:


N = int(input())
A = list(map(int, input().split()))


# In[41]:


a = np.array(A)
b = a - np.arange(1,N+1)
c = np.median(b)
d = abs(b-c).sum()
print(int(d))


# In[ ]:






Measured memory_bytes: 49316
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;

public class Main {

	Scanner sc = new Scanner(in);
	
	int n, len;
	String s;
	boolean wa() {
		if (s.charAt(n) != 'm' || n+2 >= len) return false;
		n++;
		if (s.charAt(n) == 'm') {
			if (!wa())
				return false;
		}
		if (n >= len || s.charAt(n) != 'e') return false;
		n++;
		if (n >= len) return false;
		if (s.charAt(n) == 'm') {
			if (!wa())
				return false;
		}
		if (n >= len || s.charAt(n) != 'w') return false;
		n++;
		return true;
	}
	
	void run() {
		s = sc.next();
		len = s.length();
		if (len == 0) {
			out.println("Cat");
			return;
		}
		n = 0;
		if (wa() && n == len)
			out.println("Cat");
		else
			out.println("Rabbit");
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

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

using ll = long long;
using ull = unsigned long long;

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9 + 7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(a) begin(a), end(a)

int main(void) {
    string S;
    cin >> S;
    int N = S.size();
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; i + j - 2 < N; j++) {
            string sub = S.substr(i, j);
            // sort(ALL(sub));
            // auto res = unique(ALL(sub));
            // sub.erase(res, sub.end());
            // cout << sub << endl;
            bool ACGT = true;
            REP(i, sub.size()) {
                char c = sub[i];
                if (c == 'A' || c == 'C' || c == 'G' || c == 'T') {
                } else
                    ACGT = false;
            }
            if (ACGT) ans = max(ans, (int)sub.size());
        }
    }
    cout << ans << endl;
    return 0;
}


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

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORTASC(c) sort((c).begin(),(c).end())
#define SORTDESC(c,t) sort((c).begin(),(c).end(), std::greater<t>());
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define VMAX(a) *max_element(ALL(a))
#define VMIN(a) *min_element(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double PI  = acos(-1.0);

using ll = long long;
using namespace std;

int main() {
    char c;
    
    cin >> c;
    
  	c = c+1;
    
  	cout << c << endl;

    return 0;
}

Measured memory_bytes: 256
#include "iostream"
using namespace std;
int main(void)
{
	int w,h;
	while (cin>>h>>w,h) {
		int d=h*h+w*w;
		int ah=1000,aw=1000,ad=1000000;

		for (int i = 1; i < 151; i++) {
			for (int j = i+1; j < 151; j++) {
				int dd=i*i+j*j;
				if(dd>d)
				{
					if(dd<ad)
					{
						ah=i; aw=j; ad=dd;
					}
					else if(dd==ad)
					{
						if(i<ah)
						{
							ah=i; aw=j;
						}
					}
				}
				else if(dd==d)
				{
					if(i>h&&ad!=dd)
					{
						ah=i; aw=j; ad=dd;
					}
				}
			}
		}

		cout<<ah<<" "<<aw<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007; 
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

template<class T, class S> inline bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S> inline bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}






int main(){
    int A, B, H, M; std::cin >> A >> B >> H >> M;
    long double a((M_PI*(60*H+M))/360), b(M_PI * M / 30);
  /* std::cout << (long double)(60*H+M)/360 << std::endl;
    std::cout << A*std::cos(a) << " " << A*std::sin(a) << std::endl;
    std::cout << B*std::cos(b) << " " << B*std::sin(b) << std::endl;*/
    long double x(A*std::cos(a) - B*std::cos(b)), y(A*std::sin(a) - B*std::sin(b));
    long double ans(std::sqrt(x*x + y*y));
    std::cout << std::fixed << std::setprecision(10) << ans << std::endl;
    return 0;
}


Measured memory_bytes: 4164
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  string S; cin >> S;
  ll N = S.size();
  auto getcol = [&]() -> tuple<char, ll, ll> {
    if (N % 2 == 1) return {S[N/2], N/2 - 1, N/2 + 1};
    char col = S[N/2 - 1];
    ll c = S[N/2];
    if (col != c) {
      cout << N/2 << endl;
      exit(0);
    }
    return {col, N/2 - 2, N/2 + 1};
  };
  auto [col, p, q] = getcol();
  while (p >= 0 && q <= N-1 && S[p] == col && S[q] == col) {
    p--;
    q++;
  }
  cout << q << endl;

  return 0;
}



Measured memory_bytes: 3752
int main(){
 int end=0;
 int x,y;
	while(end==0){
		scanf("%d",&x);
		scanf("%d",&y);
		if(x==0&&y==0){
			end=1;
		}else{
			if(x<=y){
				printf("%d %d\n",x,y);
			}else{
				printf("%d %d\n",y,x);
			}
		}
	}
}


Measured memory_bytes: 2048
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>
#include<queue>
#include<map>
#include<math.h>

#define FASTREAD      ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define ll long long
#define dd double
#define scl(n)        scanf("%lld",&n)
#define scd(n)        scanf("%lf",&n)
#define scc(n)        scanf("%c",&n)
#define scs(n)        scanf("%s",&n)
#define ptl(n)        printf("%lld",n)
#define ptd(n)        printf("%f",n)
#define ptc(n)        printf("%c",n)
#define pts(n)        printf("%s",n)
#define nline         printf("\n")
#define pb            push_back
#define FOR(i,a,b)    for(ll i=a;i<=b;i++)
#define FORr(i,a,b)   for(ll i=a;i>=b;i--)
#define pi            2*acos(0.0)
#define pii           pair<ll,ll>
#define uu            first
#define vv            second

using namespace std;

int main()
{
    ll n,h[100150],dp[100150],k;
    scl(n);
    scl(k);
    FOR(i,1,n)
    {
        scl(h[i]);
    }
    FOR(i,n+1,n+k)
    {
        h[i]=999999999;
        dp[i]=999999999;
    }
    dp[n]=0;
    FORr(i,n-1,1)
    {
        dp[i]=9999999999;
        FOR(j,1,k)
        {
           dp[i]=min(dp[i],dp[i+j]+abs(h[i]-h[i+j]));
        }
      //  cout<<i<<" "<<dp[i]<<endl;
    }
    ptl(dp[1]);
    nline;
    return 0;
}



Measured memory_bytes: 5276
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
import numpy as np

def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))

N = int(input())

A = np.array(inpl())

ans = 0
while True:
    flag = True
    for i in range(len(A)):
        if A[i] % 2 ==0:
            A[i] = A[i]/2
        else:
            flag = False
            break
    if flag:
        ans += 1
    else:
        break

print(ans)

Measured memory_bytes: 12316
package main

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

const size = 1000000
var reader = bufio.NewReaderSize(os.Stdin,size)
func NextLine() string {
  var line,buffer []byte
  var isPrefix bool = true
  var err error
  for ;isPrefix; {
    line,isPrefix,err = reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
  }
  return string(buffer)
}
func NextInt() int {
  var n int
  n,_ = strconv.Atoi(NextLine())
  return n
}
func NextIntArray() []int {
  var s []string = strings.Split(NextLine()," ")
  var n int = len(s)
  var a []int = make([]int,n)
  for i:=0;i<n;i++ {
    a[i],_ = strconv.Atoi(s[i])
  }
  return a
}

func main() {
  var n int = NextInt()
  n *= 2
  var a []int = NextIntArray()
  sort.Sort(sort.Reverse(sort.IntSlice(a)))
  var m int64 = 0
  for i:=1;i<n;i+=2 {
    m += int64(a[i])
  }
  fmt.Println(m)
}

Measured memory_bytes: 17152
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, K = map(int, input().split())
A = list(map(int, input().split()))

lo = 1
hi = max(A) + 1

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

while lo < hi:
	tar = (lo + hi) // 2

	cuts = 0
	for v in A:
		x = ceildiv(v, tar)
		cuts += x - 1
		if cuts > K:
			lo = tar + 1
			break
	else:
		hi = tar

print(lo)


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

int main() {
  string S;
  cin>>S;
  if(S=="SUN") cout<<7<<endl;
  if(S=="MON") cout<<6<<endl;
  if(S=="TUE") cout<<5<<endl;
  if(S=="WED") cout<<4<<endl;
  if(S=="THU") cout<<3<<endl;
  if(S=="FRI") cout<<2<<endl;
  if(S=="SAT") cout<<1<<endl;
}


Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/


int a[3];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	for (int i = 0; i < 3; ++i)
		cin >> a[i];
	sort(a, a + 3);
	int x = a[2] - a[0];
	int y = a[2] - a[1];
	int ans = x / 2 + y / 2;
	x %= 2, y %= 2;
	if (x == y)
		ans += x;
	else
		ans += 2;
	cout << ans << "\n";
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
/*int find(int a){
     if(a==par[a])return a;
     return par[a]=find(par[a]);
}
void unite(int a,int b){
     a=find(a),b=find(b);
     if(a==b)return ;
     par[b]=a;
}
ll modexpo(ll a,ll b)
{
     int ans=1LL;
     while(b>0)
     {
          if(b&1)ans=(ans*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return ans;
}
*/















int s[200005],t[200005],c[100005];
int res[200005],tmp[200005];
int main(){
     int n;
     cin>>n;
     int a[n+1];
     int b[n+1]={0};
     for(int i=1;i<=n;i++){cin>>a[i];
     b[i]=a[i];}
     sort(b+1,b+n+1);     
     int res=0;
     for(int i=1;i<=n;i++){
          int t=a[i];
          int idx=lower_bound(b+1,b+n+1,t)-b;
         // cout<<i<<" "<<idx<<"\n";
          res+=(i%2==idx%2)?0:1;
     }
     cout<<res/2;

}



















































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

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

  ll A; cin >> A;
  ll V; cin >> V;
  ll B; cin >> B;
  ll W; cin >> W;
  ll T; cin >> T;

  ll D = abs(A - B);

  string ans = "NO";
  if (T * V >= T * W + D) ans = "YES";
  cout << ans << '\n';
  return 0;
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9


int main(){
  int a;
  string s;
  cin >> a >> s;
  cout << (a >= 3200 ? s : "red") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<numeric>
#include<utility>
#include<regex>

#pragma region _define

#define f(i,a,b) for(int i=a;i<b;i++)
#define f_vI(v,n) f(i,0,n)cin>>v[i]
#define f_v2I(v1,v2,n) f(i,0,n)cin>>v1[i]>>v2[i]
#define f_v3I(v1,v2,v3,n) f(i,0,n)cin>>v1[i]>>v2[i]>>v3[i]
#define f_vO(v,n) f(i,0,n)cout<<v[i]<<endl
#define all(a) a.begin(),a.end()
#define size(s) s.size()
#define endl "\n"
#define _y() cout<<"Yes"<<endl
#define _Y() cout<<"YES"<<endl
#define _n() cout<<"No"<<endl
#define _N() cout<<"NO"<<endl

#pragma endregion

#pragma region _using

using namespace std;

using LL = long long;
using st = string;
using vi = vector<LL>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vs = vector<st>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using si = stack<LL>;
using pi = pair<LL, LL>;
using v_pi = vector<pi>;

#pragma endregion

#pragma region _graph

#define node 50
//bool graph[node][node]; bool visited[node] = { false };
#define link(a,b) f(i,0,n){cin>>a[i]>>b[i]; a[i]--; b[i]--; graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;}

#pragma endregion

LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b) * b);
}

/*****************************************************************************/


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

	int n;
	cin >> n;
	vi x(n), y(n), h(n);
	f_v3I(x, y, h, n);
	f(X, 0, 101) {
		f(Y, 0, 101) {
			int top = -1;
			f(i, 0, n) {
				if (h[i] > 0) {
					LL tmp = h[i] + abs(X - x[i]) + abs(Y - y[i]);
					if (top == -1) {
						top = tmp;
					}
					else {
						if (top != tmp) {
							top = -2;
							break;
						}
					}
				}
			}
			if (top == -2) {
				continue;
			}
			f(i, 0, n) {
				if (h[i] == 0) {
					LL d = h[i] + abs(X - x[i]) + abs(Y - y[i]);
					if (top > d) {
						top = -2;
						break;
					}
				}
			}
			if (top == -2) {
				continue;
			}
			cout << X << " " << Y << " " << top;
		}
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args:Array<String>){
    val (h,n) = readLine()!!.split(" ").map{it.toInt()}
    val a = IntArray(n)
    val b = IntArray(n)
    for(i in 0 until n){
        val (x,y) = readLine()!!.split(" ").map{it.toInt()}
        a[i] = x
        b[i] = y
    }
    val dp = IntArray(h + 1){1000000000}
    dp[0] = 0
    for(i in 0 until n){
        for(j in 0 .. h){
            if(j + a[i] <= h) dp[j + a[i]] = Math.min(dp[j + a[i]], dp[j] + b[i])
            else dp[h] = Math.min(dp[h], dp[j] + b[i])
        }
    }
    println(dp[h])
}


Measured memory_bytes: 38504
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
  int L;
  cin >> L;
  vector<int> c(L);
  for (int i = 0; i < L; ++i)
    cin >> c[i];

  int ans = 0, c2[101] = {};
  stack<int> c3;
  for (int i = 0; i < L; ++i) {
    if (c[i] > 0)
      c3.push(c[i]), ++c2[c[i]];
    else if (c3.empty())
      ans = i + 1;
    else if (-c[i] == c3.top())
      c3.pop(), --c2[-c[i]];
    else
      ans = i + 1;
    if (c2[abs(c[i])] != 0 && c2[abs(c[i])] != 1)
      ans = i + 1;
    if (ans)
      break;
  }

  if (ans)
    cout << ans << endl;
  else
    cout << "OK" << endl;
}


Measured memory_bytes: 3120
N = int(input())
cnt_max = 0
ans = 1

for i in range(1, N + 1):
    cnt = 0
    num = i
    while True:
        if num % 2 == 0:
            cnt += 1
            num /= 2
        else:
            break
    if cnt_max < cnt:
        cnt_max = cnt
        ans = i

print(ans)


Measured memory_bytes: 9108
#include <bits/stdc++.h>
using namespace std;
#define ll long long
char a[1005][1005];
ll dp[1005][1005],n,m,MOD=1e9+7;
ll rec(ll i,ll j)
{
    if(i<0 || j<0 || a[i][j]=='#')
        return 0;
    if(j==0 && i==0)
        return 1;
    if(dp[i][j]!=-1)
        return dp[i][j];
    return dp[i][j]=((rec(i-1,j)%MOD)+(rec(i,j-1)%MOD))%MOD;
}
int main()
{
    cin>>n>>m;
    for(ll i=0 ; i<n ; i++)
        for(ll j=0 ; j<m ; j++)
            cin>>a[i][j];
    memset(dp,-1,sizeof dp);
    cout<<rec(n-1,m-1);
    return 0;
}



Measured memory_bytes: 9216
n = int(input())
x_y = [ list(map(int, input().split())) for _ in range(n)  ]
import math
d = []
for i in range(n):
    for j in range(n):
        if i != j:
            x1, y1 = x_y[i]
            x2, y2 = x_y[j]
            d.append(math.sqrt((x1-x2)**2+(y1-y2)**2))
print(sum(d)/n)

Measured memory_bytes: 9060
n = int(input())
data = [i*2 for i in range(1,n//2+1)]
def f(x):
    cnt = 0
    flg = 0
    while flg==0:
        if x%2==0:
            cnt += 1
            x = x/2
        else:
            flg = 1
    return cnt 
aim = 0
for i in data:
    if aim < f(i):
        aim = f(i)
        num = i
    else:
        continue
if n==1:
    print(1)
else:    
    print(num)    

Measured memory_bytes: 3064
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll inf = 1e9 + 7;
const ll Mod = 998244353;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

int N;
char ans[10];

int DFS(int turn, int cnt){
  if (turn == N){
    for (int i = 0; i < N; i++){
      cout << ans[i];
    }
    cout << endl;
    return 0;
  }

  for (int i = 0; i < cnt; i++){
    ans[turn] = 'a' + i;
    DFS(turn + 1, cnt);
  }
  
  ans[turn] = 'a' + cnt;
  DFS(turn + 1, cnt + 1);
  return 0;
}

int main(){
  cin >> N;
  DFS(0, 0);

  return 0;
}


Measured memory_bytes: 1536
#pragma warning( disable : 4996)
//头文件
#include<algorithm>
#include<cmath>
#include<cstring>
//#include<iomanip>
//#include<iosfwd>
#include<string>
//宏定义
//#define INF 0x3f3f3f3f
//#define EPSILON 1e-8
//#define PI 3.14159265
//#define WYTHOFFa 1.6180339887
//#define WYTHOFFb 0.6180339887
//其它
//std::ios::sync_with_stdio(false); 
#include<iostream>
using namespace std;
/*int numodd[50005],numeven[50005];
int rateodd[50005][2], rateeven[50005][2];
int N,i,j,tmp;
int findMostFrequent()
{
	sort(numodd, numodd + N);
	sort(numeven, numeven + N);
	for (i =j= 0; i < N; ++i)
	{
		tmp=numodd[i];
		rateodd[j][0] = tmp;

	}
}
int main()
{
	while (cin >> N)
	{
		N >> 1;
		for (i = 0; i < N; ++i)
			cin >> numodd[i]>>numeven[i];

	}
}*/
int main()
{
	char f;
	while (cin.get(f))
	{
		if (f == '1')
			cout << '9';
		else
			cout << '1';
		cin.get(f);
			if (f == '1')
				cout << '9';
			else
				cout << '1';
			cin.get(f);
			if (f == '1')
				cout << '9';
			else
				cout << '1';
			cin.get(f);
			cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include<set> 
#include<math.h>
#define pai arccos(-1);
#define keta(n) cout << fixed << setprecision((n));
#define ll long long;

int main(){
  
int x;
  cin>>x;
  if(x>=30)cout<<"Yes";
  else cout<<"No";
}


Measured memory_bytes: 3616
import java.io.*;

public class Main {
	public static void main(String[] args){
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		try{
			String line = reader.readLine();
			int number = Integer.parseInt(line);
			int answer = number * number * number;
			System.out.println(answer);
		} catch (IOException e){
			System.out.println(e);
		} catch (NumberFormatException e){
			System.out.println("値が不正です\n");
		}
	}
}


Measured memory_bytes: 24172
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <iterator>
#include <algorithm>
#include <cfenv>
#include <random>
#include <numeric>
#include <cmath>
#include <iosfwd>
#include <iostream>
#include <ios>
#include <streambuf>
#include <istream>
#include <ostream>
#include <iomanip>
#include <sstream>
#include <fstream>
 
typedef long long ll;
 
using namespace std;
 
int main(){
    ll N,M;
    ll sum=0;
    
    cin >> N >> M;
    for(ll i = 0 ; i < M ; i++){
        ll tmp;
        cin >> tmp;
        sum += tmp;
    }
    if(N - sum >= 0){
        cout <<N - sum;
    }else{
        cout << "-1";
    }

    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b;
    for(int i=0;i<10000;i++){
        if(a>=b){a=a-b;
        c=i;}else
        if(a>0){a=a-1;
        c=i;}
        if(a==0){break;}
    }
    cout<<c+1<<endl;
}


Measured memory_bytes: 3100
/* 
chirag11032000
Chirag Thakur
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;

template < typename T > using OrderedSet = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

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

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

const db PI = acos(-1);
const ll LINF = LLONG_MAX;
const int INF = INT_MAX, MOD = 1e9 + 7, N = 1e5 + 10;

void test_case();

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	test_case();
	cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
	return 0;
}

void test_case() {
	string s;
	cin >> s;
	vector < int > ans(2);
	for (int i = 0; i < s.size(); ++i) {
		if (i & 1) {
			ans[0] += s[i] == '0';
			ans[1] += s[i] == '1';
		} else {
			ans[0] += s[i] == '1';
			ans[1] += s[i] == '0';
		}
	}
	cout << min(ans[0], ans[1]) << "\n";
}

Measured memory_bytes: 512