akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [int(i) for i in input().split()]

X = [0] * N
X[0] = sum(A) - 2 * sum(A[1::2])

for i in range(1,N):
    X[i] = 2 * A[i-1] - X[i-1]

print(' '.join(list(map(str,X))))

Measured memory_bytes: 19132
/*    特徴    */
// mapのkeyにpairを使う
// 座標で考える

/*    教訓    */
// 何かをグループ分けしたい時、バケツは強い
// mapもバケツの進化系
// % より * の方が演算の優先順位が高い
// 引き算のMOD計算の後は、正負判定して負なら+MODする

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

using ll = long long;
using ld  = long double;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-9; //微調整用（EPSより小さいと0と判定など）

#define begin_end(a) a.begin(),a.end() //sort(begin_end(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll) (n) ; i++ )
#define rep(i,n) REP(i,0,n)

// -------- template end - //


// - library ------------- //

ll llpow(ll a, ll b){
    if(b == 0){
        return 1;
    }
    ll ans = llpow(a, b / 2);
    ans = ans * ans % MOD;
    if(b % 2 == 1){
        ans = ans * a % MOD;
    }
    return ans;
}

// --------- library end - //



// - main() -------------- //

int main(){


  ll N;
  cin >> N;

  // イワシを入れるための二分割された四角いバケツ
  // key : <a, b>
  // value : <(a, b)であるイワシの数, (-a, b)であるイワシの数>
  // 同じバケツの違うセクションに入れられたイワシ同士は仲が悪い
  // それ以外の組み合わせのイワシは仲が良い（ただし、(0, 0)のイワシは全員と仲が悪い）
  map<pair<ll, ll>, pair<ll, ll> > sardine_buckets;

  // 孤高のイワシ（0, 0)の数
  ll double_zero_sardines = 0;

  rep(i, N){
    ll a, b;
    cin >> a >> b;

    // a, bを既約分数で表す（a, bを同じ割合のまま互いに素にする）
    // つまり、(a, b) の最大公約数で割ればいい
    ll gcd_ab = gcd(a, b);
    // (負, 負) -> (正, 正), (正, 負) -> (負, 正) に統一する
    // C++17 からの gcd() は正の値を返す（特殊な条件で負になることもあるらしいが不明）ので、処理をする必要がある
    // __gcd() を使うなら、__gcd(正, 負) もしくは __gcd(負, 負) とすると負の数を返すようなので、何もしなくても自動でひっくり返る
    if (b < 0){
      a = -a;
      b = -b;
    }

    if (gcd_ab == 0) {
      // 孤高のイワシの場合
      double_zero_sardines++;
    }
    else if (a != 0 && b != 0){
      // 通常のイワシの場合
      a /= gcd_ab;
      b /= gcd_ab;

      // (a, b) = (正, 正)のイワシは、普通に(a, b)のバケツに入れる
      if (a >= 0){
        pair<ll, ll> pair_ab = make_pair(a, b);
        // イワシをセクション1に放り込む
        sardine_buckets[pair_ab].first++;
      }
      // (a, b) = (負, 正)になっているイワシは、(b, -a)のバケツに入れればいいので、正にしてひっくり返す
      // ex) (-3, 2) のイワシは、(2, 3) のイワシと仲が悪いので、(2, 3)のラベルがついたバケツ（のセクション2）に入れればいい
      else {
        a = -a;
        swap(a, b);

        pair<ll, ll> pair_ab = make_pair(a, b);

        // イワシをセクション2に放り込む
        sardine_buckets[pair_ab].second++;
      }
    }
    else {
      // (0, *) or (*, 0) の場合
      pair<ll, ll> pair_ab = make_pair(0, 0);
      if (a == 0) sardine_buckets[pair_ab].first++;
      else sardine_buckets[pair_ab].second++;
    }
  }

  // イワシをバケツに入れ終わったので、後は計算する

  ll ans = 1;
  for (pair<pair<ll, ll>, pair<ll, ll> > p : sardine_buckets){
    ll s_pl = p.second.first; // セクション1に入れられた、(a, b)のイワシ
    ll s_mi = p.second.second; // セクション2に入れられた、(-b, a)のイワシ

    ll tmp = (llpow(2, s_pl) + llpow(2, s_mi) - 1) % MOD;
    // MODが負になっている場合は + MOD
    tmp = ( tmp < 0 ? tmp + MOD : tmp );
    ans = ans * tmp % MOD;
  }
  
  // 孤高のイワシは1つしか入れられない
  ans = (ans + double_zero_sardines) % MOD;

  // 最後に、「0匹のイワシが入っている」というパターンはNGなので、-1
  ans = (ans - 1) % MOD;
  // MODが負になっている場合は + MOD
  ans = ( ans < 0 ? ans + MOD : ans );

  cout << ans << endl;

// ---------- main() end - //
}

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

using lli = long long int;
using Vint = vector<int>;
using Vlli = vector<lli>;
using Wint = vector<Vint>;
using Wlli = vector<Vlli>;
using pii = pair<int, int>;
using pll = pair<lli, lli>;

const int MOD = 1e9 + 7;
const int INFi = 2e9 + 1;
const lli INFl = (lli)(9e18) + 1;
// const vector<pii> DXDY = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(i, vec) for(auto &(i) : (vec))
/*
template <class T>
int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
*/
template <class T> inline int argmin(vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


int main(void){
  int n, w; cin >> n >> w;
  Vint W(n), V(n);
  REP(i, n) cin >> W.at(i) >> V.at(i);
  int SUM = accumulate(V.begin(), V.end(), 0);
  /*  DP[i][j] := 0, 1, ..., i を用いて 重さ j になるものの価値最大
  *   (0, 1, ..., i) <-> (重さ w) <-> 価値 v : 3つが拘束
  *   => argDP[i][j] = 0, 1, ..., i を用いて価値 j となる時の最小の重さ
  *   ~~~ 関係式 ~~~
  *   argDP[i][j] ~> argDP[i + 1][j] : 選ばない
  *               ~> (i + 1, j + v[i + 1]) = min(self, argDP[i][j] + w[i + 1])
  *   ~~~ 初期値 ~~~
  *   argDP[i][0] = 0
  *   argDP[0][v[0]] = w[0]
  *   ~~~ res ~~
  *   argmax{k ∈ N | argDP[n-1][k] <= w}
  */
  Wlli argDP(n, Vlli(SUM + 1, INFi));
  REP(i, n) argDP[i][0] = 0; argDP[0][V.at(0)] = W.at(0);
  REP(i, n-1) REP(j, SUM + 1) if(argDP[i][j] != INFi){
    chmin(argDP[i + 1][j], argDP[i][j]);
    if(j + V[i + 1] <= SUM) chmin(argDP[i + 1][j + V[i + 1]], argDP[i][j] + W[i + 1]);
  }
  int res = -1;
  REP(i, SUM + 1) if(argDP[n-1][i] <= w) res = i; // 更新
  cout << res << "\n";
  return 0;
}

Measured memory_bytes: 79360
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>
#include<cmath>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    vector<int> a(n), b;
    for(int i = 0; i < n - 1; i++){
        if(s[i] == 'R' && s[i + 1] == 'L'){
            b.emplace_back(i);
        }
    }
    for(int i = 0; i < n; i++){
        auto itr = lower_bound(begin(b), end(b), i);
        if(s[i] == 'L'){
            itr--;
        }
        int t = abs(*itr - i);
        a[*itr + (t % 2)]++;
    }
    cout << a[0];
    for(int i = 1; i < n; i++){
        cout << " " << a[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 1280
import java.util.Scanner;

public class Main{
	private static Scanner scan;
	public static void main(String[] args) {
		scan = new Scanner(System.in);
		scan.useDelimiter("\\r\\n");
		while(scan.hasNext()){
        	String str = scan.nextLine();
        	int m = 0;
        	String string = null;
        	for(int i = 0; i < 26;i++){
        		char[] ch = str.toCharArray();
        		for(int j = 0;j < ch.length;j++){
        			if (ch[j] != '.' && ch[j] != ' '){
                        ch[j] = (char) ('a' + (ch[j] - 'a' + i) % 26);
        			}
        		}
        		string = String.valueOf(ch);
        		if(string.indexOf("the") != -1 || string.indexOf("this") != -1 ||string.indexOf("that") != -1){
        			m = 1;
        			break;
        		}
        	}
        	if(m == 1){
        		System.out.println(string);
        	}else{
        		System.out.println();
        	}
        }
		System.exit(0);
	}
}

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

using namespace std;

int main(){
    int a;
    string n; cin >> a >> n;

    int length = n.size()/2;
   

    string b = n.substr(length);
   // cout << "aの文字列は" << n.erase(length) << endl;

   //cout << "bの文字列は" << b << endl;

    if(n.size() == 1){
        cout << "No";
    }else if(n.erase(length) == b){
        cout << "Yes";
    }else{
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

        int figure = S.length()-2;
        char start = S.charAt(0);
        char end = S.charAt(S.length()-1);
        String s = S.valueOf(start);
        String e = S.valueOf(end);
        String f = S.valueOf(figure);
        
        System.out.println(s + f + e);
    }
}

Measured memory_bytes: 23252
import java.util.*;

public class Main {
    private static final Scanner scn = new Scanner(System.in);
    private static final int[][] tbl_;
    private static final int N = 101, X = 298;
    
    static {
        int[][] tbl = new int[N][X];
        for(int i = 3; i < N; i++) {
            double v = 1;
            for(int j = i + 3; j <= (i - 1) * 3; j++) {
                for(int k = i; k < N; k++) {
                    tbl[k][j] += (int)v;
                }
                if(j < i * 2) {
                    v += 0.5;
                } else {
                    v -= 0.5;
                }
            }
        }
        tbl_ = tbl;
    }
    
    public static void main(String[] args) {
        while(scn.hasNextInt()) {
            int n = scn.nextInt(), x = scn.nextInt();
            if(n > 0) {
                System.out.println(0 < x && x < X ? tbl_[n][x] : 0);
            }
        }
    }
}

Measured memory_bytes: 26768
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define all_acc(x) (x).begin(),(x).end(),0LL
#define int long long
#define absSort(v) sort(a.begin(), a.end(), [](int i, int j) -> bool {return abs(i) < abs(j);});
using namespace std;
using P=pair<int,int>;
using Graph=vector<vector<int>>;
using ll=long long;

//出力するよ
void output(vector<int> s){
    int n=s.size();
    for(int i=0;i<n;i++){
        if(i!=0) cout<<" ";
        cout<<s[i];//<<endl;
    }
    cout<<endl;
}

void insert(string s,set<string> se){
    se.insert(s);
}

string find(string s,set<string> se){
    if(se.count(s)) return "yes";
    else return "no";
}

int n,k;
vector<int> w;

//最大積載量がpで、車がk台あるときに、すべて積むことが出来るのか
bool able(int p){
    int car=1;
    int weight=0;
    bool possible=true;

    for(int i=0;i<n;i++){
        if(w[i]>p) return false;

        if(weight+w[i]>p){
            car++;
            weight=w[i];
        }else{
            weight+=w[i];
        }
    }

    if(car<=k) return true;
    else return false;
}

signed main(){
    cin>>n>>k;
    w.assign(n,0);
    for(int i=0;i<n;i++) cin>>w[i];

    int ok=10000*n;
    int ng=0;

    while((ok-ng)>1){
        int mid=(ok+ng)/2;
        if(able(mid)){
            ok=mid;
        }else{
            ng=mid;
        }
    }

    cout<<ok<<endl;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;





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

	while(true){
		if(a>b){
			a=a%b;	
		}else{
			b=b%a;
		}
		if(a==0||b==0){
			break;
		}
	}
	cout<<max(a,b)<<endl;

	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <numeric>
#include <vector>
#include <math.h>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
using namespace std; 

int main(){
    int a; cin >> a;
    int ans=0;
    for (int i=0;i<a;i++){
        int s; cin >> s;
        if (s%2==0){
            if (s%3!=0 && s%5!=0){
                ans=1;
            }
        }
    }
    if (ans==0) cout << "APPROVED" << "\n";
    else cout << "DENIED" << "\n";
    
}








Measured memory_bytes: 256
use std::io;

fn procon_read<T: std::str::FromStr>() ->  Vec<T> {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let iter = buf.split_whitespace();
	let mut v: Vec<T> = Vec::new();
	for i in iter {
		v.push(i.parse().ok().unwrap());
	}
	v
}

fn main() {
	let v:Vec<i32> = procon_read();
	if v[0] == 1 {
		println!("Hello World");
	}else{
		let v:Vec<i32> = procon_read();
		let a = v[0];
		let v:Vec<i32> = procon_read();
		let b = v[0];
		println!("{}", a+b);
	}
}

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

#define TASK ""
#define openfile ({freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);})

const int N = 100005;

int n;
int a[N];
map <int, int> f;
set <int> s;
set <int> :: iterator it;

int main() {
	//openfile;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), f[a[i]]++;
	for (int i = 1; i <= n; i++)
		if (f[a[i]] >= 2) s.insert(a[i]);
	long long ans = 0;
	for (it = s.begin(); it != s.end(); it++)
		if (f[*it] >= 4) ans = max(ans, 1ll * (*it) * (*it));
	if (s.size() == 1) return cout << ans, 0;
	int mx1 = 0, mx2 = 0;
	for (it = s.begin(); it != s.end(); it++) {
		if (f[*it] >= 2) {
			mx2 = mx1;
			mx1  = max(mx1, *it);
		}
	}
	ans = max(ans, 1ll * mx1 * mx2);
	cout << ans;
	return 0;
}

Measured memory_bytes: 5376
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>

typedef struct{
    int i;
    int p;
    int a;
    int b;
    int sum;
} unit_t;

int sortp(const void *a, const void *b){
    if (((unit_t*)a)->p-((unit_t*)b)->p>0){
        return -1;
    }
    if (((unit_t*)a)->p-((unit_t*)b)->p<0){
        return 1;
    }
    return 0;
}

int sorti(const void *a, const void *b){
    if (((unit_t*)a)->i-((unit_t*)b)->i>0){
        return 1;
    }
    if (((unit_t*)a)->i-((unit_t*)b)->i<0){
        return -1;
    }
    return 0;
}

int main(void){
    int n;
    scanf("%d",&n);
    unit_t unit[n];
    for (int i=0; i<n; i++){
        int p;
        scanf("%d",&p);
        unit[p-1].p=i;
        unit[i].i=i;
    }
    qsort (unit,n,sizeof(unit_t),sortp);
    for (int i=0; i<n; i++){
        unit[i].sum=(20000*n)-i;
    }
    qsort (unit,n,sizeof(unit_t),sorti);
    unit[0].a=1;
    unit[0].b=unit[0].sum-1;
    for (int i=1; i<n; i++){
        if (unit[i].sum>unit[i-1].sum){
            unit[i].b=unit[i-1].b-1;
            unit[i].a=unit[i].sum-unit[i].b;
        } else {
            unit[i].a=unit[i-1].a+1;
            unit[i].b=unit[i].sum-unit[i].a;
        }
    }
    for (int i=0; i<n; i++){
        printf("%d ",unit[i].a);
    }
    printf("\n");
    for (int i=0; i<n; i++){
        printf("%d ",unit[i].b);
    }
    printf("\n");
	return 0 ;
}

Measured memory_bytes: 1364
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;



int main()
{
	int S, h, m, s;

	cin >> S;

	h = S / 3600, S %= 3600;
	m = S / 60, S %= 60;
	s = S;

	printf("%d:%d:%d\n", h, m, s);

	return 0;
}



Measured memory_bytes: 3228
class Gemmm
	def initialize(x0, y0)
		@x = x0
		@y = y0
		@hit = false
	end
	
	attr_accessor :x
	attr_accessor :y
	attr_accessor :hit
end

def pick_gem(g, n, x, y)
	n.times do |i|
		if !g[i].hit && g[i].x == x && g[i].y == y then
			g[i].hit = true
			return
		end
	end
end

loop do
	n = gets.to_i
	if n == 0 then
		break
	end

	g = []
	d = []
	l = []

	n.times do |i|
		a, b = gets.split.map(&:to_i)
		g[i] = Gemmm.new(a, b)
	end
	
	m = gets.to_i

	m.times do |i|
		d[i], tmp = gets.split
		l[i] = tmp.to_i
	end

	x = 10
	y = 10
	m.times do |i|
		case d[i]
		when 'N'
			f = lambda{|x0, y0| return x0, y0 + 1 }
		when 'S'
			f = lambda{|x0, y0| return x0, y0 - 1 }
		when 'E'
			f = lambda{|x0, y0| return x0 + 1, y0 }
		when 'W'
			f = lambda{|x0, y0| return x0 - 1, y0 }
		end
		
		l[i].times do
			x, y = f.call(x, y)
			pick_gem(g, n, x, y);
		end
	end

	puts g.find_index{|v| v.hit == false }  ? "No" : "Yes"
end

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

int main() {
    int k, s;
    cin >> k >> s;

    int cnt = 0;
    for (int x = 0; x <= k; ++x) {
        for (int y = 0; y <= k; ++y) {
            int z = s - (x + y);
            if (z >= 0 && z <= k) ++cnt;
        } 
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
N = int(input())
S = input()

west = [0 for _ in range(N+1)]
east = [0 for _ in range(N+1)]

for i in range(N):
    west[i+1] = west[i]
    east[i+1] = east[i]
    if S[i] == 'W':
        west[i+1] += 1
    else:
        east[i+1] += 1

west = west[1:]
east = east[1:]

turn_nums = [0 for _ in range(N)]
turn_nums[0] = east[N-1] - east[0]
turn_nums[N-1] = west[N-2]
for i in range(1, N-1):
    turn_nums[i] = west[i-1] + east[N-1] - east[i]

print(min(turn_nums))


Measured memory_bytes: 30712
import sys
from io import StringIO
import unittest


def resolve():
    N, K = map(int, input().split())
    S = list(input())
    S[K - 1] = S[K - 1].lower()
    print(''.join(S))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 1
ABC"""
        output = """aBC"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 3
CABA"""
        output = """CAbA"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 51184
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int p[20] = {0};
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
        if (p[i-1] > p[i] && p[i] > p[i+1]) ans++;
        if (p[i-1] < p[i] && p[i] < p[i+1]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
const int N = 1e5;  // limit for array size
ll n;  // array size

int main(){
	int a,b;cin>>a>>b;
	
	if(a+b==15){
		cout<<'+'<<endl;
	}
	else if(a*b==15){
			cout<<'*'<<endl;
		}
	else{
		cout<<'x'<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  vector<string> word(50);
  for (int i = 0; i < H; i++) {
    cin >> word.at(i);
  }
  vector<int> dh(8);
  vector<int> dw(8);
  dh = {-1, -1, -1, 0, 0, 1, 1, 1};
  dw = {-1, 0, 1, -1, 1, -1, 0, 1};
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int num = 0;
      if (word.at(i).at(j) == '#') continue;
      
      for (int k = 0; k < 8; k++) {
        const int i8 = i + dh.at(k);
        const int j8 = j + dw.at(k);
        
        if ((i8 < 0) || (i8 >= H)) continue;
        if ((j8 < 0) || (j8 >= W)) continue;
        if (word.at(i8).at(j8) == '#') {
          num++;
        }
        
      }

      word.at(i).at(j) = char(num + '0');  
      
    }
  }
  for (int i = 0; i < H; i++) {
    cout << word.at(i) << endl;
  }
  
  return 0;
}

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

int main() {
  string S;
  cin >> S;
  if(S.at(0) == S.at(1) || S.at(1) == S.at(2) || S.at(2) == S.at(3)){
    cout << "Bad";
  }else{
    cout << "Good";
  }

  }


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

#define ll long long
#define el '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repi(i, a, b) for (int i = a; i >= b; i--)
#define VI vector<int>
#define VII vector<pair<int, int>>
#define PII pair<int, int>
#define MP make_pair
// #define log(fmt, ...) printf(fmt, ##__VA_ARGS__)
#define log(fmt, ...)
// #define check(...) assert(##__VA_ARGS__)
#define check(...)

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

    int h, w;
    cin >> h >> w;
    if (h == 1 || w == 1) {
        cout << 1;
    } else {
        ll area = (ll)h * w;
        if (area % 2 == 0) {
            cout << area / 2;
        } else {
            cout << area / 2 + 1;
        }
    }
}


Measured memory_bytes: 256
from collections import deque
from typing import List


def main():
    n = int(input())
    v = input().split(" ")
    print(*pp(n, v))


def pp(n: int, v: List[str]) -> List[str]:
    x = []
    y = deque([])

    if n % 2 == 0:
        for i in range(n):
            if i % 2 == 0:
                y.append(v[i])
            else:
                x.append(v[i])
    else:
        for i in range(n):
            if i % 2 == 0:
                x.append(v[i])
            else:
                y.append(v[i])

    x_len = len(x)
    ret = [""] * (x_len + len(y))
    for i in range(x_len):
        ret[i] = x.pop()

    for i in range(len(y)):
        ret[x_len + i] = y.popleft()

    return ret


if __name__ == "__main__":
    main()


Measured memory_bytes: 29056
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  string S;
  cin >> S;

  ll ans = 0;
  for (int bit = 0; bit < (1 << S.size() - 1); ++bit)
  {
    ll sum = 0, tmp = S[0] - '0';
    for (int i = 0; i < S.size() - 1; ++i)
    {
      if (bit & (1 << i))
      {
        sum += tmp;
        tmp = 0;
      }
      else
      {
        tmp *= 10;
      }
      tmp += S[i + 1] - '0';
    }
    sum += tmp;
    ans += sum;
  }
  cout << ans << endl;

  return 0;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1010;



int n, m;
string g[maxn];

ll dp[maxn][maxn];


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

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

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

    dp[0][0]=1;

    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    if (g[i][j]=='#') continue;
	    add(dp[i+1][j], dp[i][j]);
	    add(dp[i][j+1], dp[i][j]);
	}
    }

    ll res=dp[n-1][m-1];
    res%=mod;
    res+=mod;
    res%=mod;
    cout<<res<<endl;
  

    return 0;
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[100010], b[100010];
int main(){
    int n;
    while(cin>>n){
        ld ans=0, tmp=1;
        for(ll i=1; i<=n-2; ++i){
            tmp*=i;
        }
        tmp*=n-1;
        tmp*=2;
        ld tmp1;
        for(int i=0; i<n; ++i){
            scanf("%d%d",a+i, b+i);
            for(int j=0; j<i; ++j){
                tmp1=hypot(a[i]-a[j], b[i]-b[j]);
                ans+=tmp1*tmp;
            }
        }
        for(ll i=1; i<=n; ++i)
            ans/=i;
        cout<<fixed<<setprecision(9)<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
//int T[2005]={0};
int main(){
  ll n ,j ;
  cin>>n>>j;
ll ans=0;
  for(ll k=j;k<=n+1;k++){
  ll a=(((k-1)*k)/2)%MOD;
  ll b=(((n+n-k+1)*k)/2)%MOD;
  ans+=(b-a+1+MOD)%MOD;
  ans%=MOD;
  ///cout<<" "<<ans<<endl;
}

    cout<<ans<<endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main(){
  map<string,vector<int> >m;
  string s;int x,f;
  for(;cin>>s>>x;)
    m[s].push_back(x);
  map<string,vector<int> >::iterator it=m.begin();
  for(;it!=m.end();it++){
    cout<<(*it).first<<endl;
    vector<int>v=(*it).second;
    sort(v.begin(),v.end());
    for(f=0;f<v.size();f++){
      if(f)cout<<' ';
      cout<<v[f];
    }
    cout<<endl;
  }
}

Measured memory_bytes: 1244
def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

for j_ in range(n):
  print(d[IDs[j_]])

    



  
  
    
    

Measured memory_bytes: 110040
#include <cstddef>
#include <complex>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <limits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>

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

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

int main()
{
    using namespace std;

    int a, b, k;
    cin >> a >> b >> k;

    for (int i = 100, count = 0; i > 0; --i)
    {
        if (a % i == 0 && b % i == 0)
        {
            ++count;
        }
        if (count == k)
        {
            cout << i << endl;
            break;
        } 
    }

    return 0;
}


Measured memory_bytes: 256
object Main extends App {
  val n: Int = io.StdIn.readInt()
  val bt: BTree = Empty

  (0 until n).foldLeft[BTree](bt){(t, _) =>
    val op: Array[String] = io.StdIn.readLine().split(" ")
    op(0) match {
      case "print" => t.show; t
      case "insert" => t.insert(op(1).toInt)
      case "find" => {
        val key: Int = op(1).toInt
        println(if (t.find(key)) "yes" else "no")
        t
      }
      case _ => throw new Error("Unknown operation")
    }
  }

  trait BTree {
    def insert(x: Int): BTree
    def preorder: List[Int]
    def inorder: List[Int]
    def show: Unit = {
      println(" " + this.inorder.mkString(" "))
      println(" " + this.preorder.mkString(" "))
    }
    def find(x: Int): Boolean
  }
  object Empty extends BTree {
    def insert(x: Int): BTree = new Node(x, Empty, Empty)
    def preorder: List[Int] = Nil
    def inorder: List[Int] = Nil
    def find(x: Int): Boolean = false
  }
  class Node(v: Int, l: BTree, r: BTree) extends BTree {
    def insert(x: Int): BTree =
      if (x < v) new Node(v, l.insert(x), r)
      else new Node(v, l, r.insert(x))
    def preorder: List[Int] = v :: (l.preorder ::: r.preorder)
    def inorder: List[Int]  = l.inorder ::: (v :: r.inorder)
    def find(x: Int): Boolean =
      if (x == v) true
      else if (x < v) l.find(x)
      else r.find(x)
  }
}


Measured memory_bytes: 464956
#include<iostream>
#include<cstdio>

using namespace std;

struct Node{int p, l, r;};
// Parent Left-child Right-sibling

Node T[100001];
int n,D[100001];

void resprint(int u){
	printf("node %d: ",u);
	printf("parent = %d, ",T[u].p);
	printf("depth = %d, ",D[u]);
	if(T[u].p==-1)
	printf("root, ");
	else if(T[u].l==-1)
	printf("leaf, ");
	else
	printf("internal node, ");
	
	int c;
	printf("[");
	for(int i=0,c=T[u].l ; c!=-1 ; i++,c=T[c].r){
		if(i!=0)
		printf(", ");
		printf("%d",c);
	}
	printf("]\n");
}

void depth(int u, int p){
	D[u]=p;
	if(T[u].r!=-1)
	depth(T[u].r,p); //???????????????, ???????????±????¨????
	if(T[u].l!=-1)
	depth(T[u].l,p+1); //??????????????????, ???????????±???+1?¨????
}

int main(){
	int l,r,id,k,c;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		T[i].p=-1;
		T[i].l=-1;
		T[i].r=-1;
	}
	for(int i=0;i<n;i++){
		scanf("%d",&id);
		scanf("%d",&k);
		for(int j=0;j<k;j++){
			scanf("%d",&c);
			if(j==0)
			T[id].l=c;
			else
			T[l].r=c;
			l=c;
			T[c].p=id;
		}
	}
	for(int i=0;i<n;i++){
		if(T[i].p==-1)
		r=i;
	}
	depth(r,0);
	for(int i=0;i<n;i++){
		resprint(i);
	}
}

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

using namespace std;

int main(){
    int a,b,k,n,count = 0;
    cin >> a >> b >> k;

    n = min(a,b);

    for(int i = n;i >= 1;i--){
        if(a % i == 0 && b % i == 0)
            count++;
        if(count == k){
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

// #define FL fflush(stdout)

#define MOD 1000000007
#define INF 2000000000
#define MAXN 100010

int GLL(LL& x) {
  return scanf("%lld", &x);
}

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

LL n, m, t1, t2;
bool visited[MAXN];
LL previous[MAXN];
vector< vector<LL> > adj;
vector<LL> end_node;

void vis(LL parent, LL node) {
  previous[node] = parent;
  visited[node] = true;
  int max_use = 2 - (previous[node] != 0);
  int use = 0;

//  printf("%d --> [%d], max %d\n", parent, node, max_use);

//    for (auto b: adj[node]) printf("%d ", b);
//    printf("\n");

  for (int i = 0; i < adj[node].size(); i++) {
    if (!visited[adj[node][i]]) {
      vis(node, adj[node][i]);
      use++;
    }

    if (use >= max_use) break;
  }

  if (use < max_use) end_node.PB(node);
}

int main() {
  GLL(n);
  GLL(m);

  adj.resize(n+1);
  memset(visited, 0, sizeof visited);
  memset(previous, 0, sizeof previous);

  FORN(i, m) {
    GLL(t1);
    GLL(t2);

    adj[t1].PB(t2);
    adj[t2].PB(t1);
  }

//  for (auto a : adj) {
//    for (auto b: a) printf("%d ", b);
//    printf("\n");
//  }

  vis(0, 1);

  vector<LL> seg1, seg2;
  LL next = end_node[0];
  while (next != 1) {
    seg1.PB(next);
    next = previous[next];
  }
  
  next = end_node[1];
  while (next != 1) {
    seg2.PB(next);
    next = previous[next];
  }

//  printf("ends: ");
//  for (auto e : end_node) printf("%d ", e);
//  printf("\n");

  printf("%lld\n", seg1.size() + seg2.size() + 1);
  for (auto e : seg1) printf("%lld ", e);
  printf("1 ");
  for (int i = seg2.size()-1; i >=0; i--) printf("%lld ", seg2[i]);
  printf("\n");
  return 0;
}


Measured memory_bytes: 12404
#include<bits/stdc++.h>
using namespace std;
inline int_fast64_t read(){int_fast64_t x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
inline string read_s(){string s="";char c=getchar();while(c<'!'||c>'~'){c=getchar();}while(c>='!'&&c<='~'){s+=c;c=getchar();}return s;}
int ans;
void Main(){
    int A = read(), B = read(), C = read();
    ans = A+B+C-max(A, max(B, C));
    printf("%d\n", ans);
}
int main(){cin.tie(nullptr);ios::sync_with_stdio(false);Main();return 0;}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
using namespace std;

int main(void)
{
    int N;
    int a[10010];
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }
    int ans;
    for (int i = 0; i < N; i++)
    {
        while (a[i] % 2 == 0)
        {
            a[i] /= 2;
            ans++;
        }
    }
    cout << ans;

    return (0);
}

Measured memory_bytes: 256
s=input().rstrip()
if 'C' in s and 'F' in s:
  indC,indF=100,0
  for i in range(len(s)):
    if s[i] == 'C':
      indC = min(indC,i)
    elif s[i] == 'F':
      indF = max(indF,i)
    if indC < indF:
      print('Yes')
      exit()
  print('No')
else:
  print('No')

Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	ll X,Y;
	scan(X>>Y);
	if(X%Y==0) prin(-1);
	else prin(X);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.141592653589793238462
using namespace std;
typedef long long ll;
typedef double long db;
struct ppp{ll l,r,pos;}p[500005];
ll a[500005],tree[500005],ans[500005];
bool cmp(ppp x,ppp y){
    return x.r<y.r;
}
unordered_map<ll,ll> k;
void add(ll x,ll k){
    while(x<=500000){
        tree[x]+=k;
        x+=x&(-x);
    }
}
ll query(ll x){
    ll res=0;
    while(x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
int main(){
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=q;i++){
        cin>>p[i].l>>p[i].r;p[i].pos=i;
    }
    sort(p+1,p+1+q,cmp);ll now=1;
    for(int i=1;i<=q;i++){
        while(now<=p[i].r){
            if(k[a[now]]==0){
                k[a[now]]=now;
                add(now,1);
            }
            else{
                add(k[a[now]],-1);
                k[a[now]]=now;add(now,1);
            }
            now++;
        }
        ans[p[i].pos]=query(p[i].r)-query(p[i].l-1);
    }
    for(ll i=1;i<=q;i++){
        printf("%lld\n",ans[i]);
    }
}

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

#define for(i, a, b) for(ll (i)=a;(i)<(b);++(i))
#define rep(i, n)    for(i, 0, n)

const ll inf = 1e15;
const ll mod = 1e9+7;

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

int main() {
    ll N;
    cin >> N;
    
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    
    ll cur = 1;
    vector<bool> visit(N, false);
    visit[cur-1] = true;
    
    ll cnt = 0;
    while (true) {
        cnt++;
        
        ll next = a[cur-1];
        if (next == 2) {
            cout << cnt << endl;
            return 0;
        }
        if (visit[next-1]) break;
        visit[next-1] = true;
        
        cur = next;
    }
    cout << -1 << endl;
    
    return 0;
}

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

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (abs(a - c) <= d) cout << "Yes\n";
	else {
		if (abs(a - b) <= d && abs(b - c) <= d) cout << "Yes\n";
		else cout << "No\n";
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;


int main(){
  int x;
  cin >> x;
  if(x<1200) cout << "ABC" << endl;
  if(1200<=x) cout << "ARC" << endl;
}

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

class UnionFind
{
private:
	vector<int> par;
public:
	UnionFind(int n) : par(n) 
	{
		for (int i = 0; i < par.size(); i++) par[i] = i;
	}
	int root(int x)
	{
		return (par[x] == x ? x : par[x] = root(par[x]));
	}
	bool isSame(int x, int y)
	{
		return root(x) == root(y);
	}
	void unite(int x, int y)
	{
		x = root(x);
		y = root(y);
		par[x] = y;
	}
};


int main()
{
	int n, q;
	cin >> n >> q;
	UnionFind unionFind(n);

	while (q--)
	{
		int order, x, y;
		cin >> order >> x >> y;
		if (order == 0) unionFind.unite(x, y);
		if (order == 1) cout << unionFind.isSame(x, y) << endl;
	}

	return 0;
}

Measured memory_bytes: 3212
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq  priority_queue<double, std::vector<double>, std::greater<double>>

    int lcm(ll a, ll b)
{
    return a * b / __gcd(a, b);
}

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

int main()
{
    char B;
    cin >> B;
    if(B == 'A'){
        cout << 'T' << endl;
    }
    else if(B == 'T'){
        cout << 'A' << endl;
    }
    else if(B == 'G'){
        cout << 'C' << endl;
    }
    else{
        cout << "G" << endl;
    }
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <tuple>
#include <queue>
#include <deque>

template <class Tp>
constexpr Tp inf = Tp(1) << (8*sizeof(Tp)-3);

template <class Tp, class Compare>
using priority_queue = std::priority_queue<Tp, std::deque<Tp>, Compare>;

template <class Weight>
struct edge {
  using value_type = Weight;
  size_t src, dst;
  value_type cost;

  edge(size_t src, size_t dst, value_type cost=1):
    src(src), dst(dst), cost(cost)
  {}

  bool operator <(const edge<value_type> &rhs) const {
    if (cost != rhs.cost) return cost < rhs.cost;
    if (src != rhs.src) return src < rhs.src;
    return dst < rhs.dst;
  }
};

template <class Weight>
struct graph: public std::vector<std::vector<edge<Weight>>> {
  using value_type = Weight;
  graph(size_t n): std::vector<std::vector<edge<value_type>>>(n) {}

  void connect_with(size_t src, size_t dst, value_type cost=1) {
    (*this)[src].emplace_back(src, dst, cost);
    (*this)[dst].emplace_back(dst, src, cost);
  }

  void connect_to(size_t src, size_t dst, value_type cost=1) {
    (*this)[src].emplace_back(src, dst, cost);
  }
};

template <class Weight>
std::vector<Weight> shortest(const graph<Weight>& g, size_t s) {
  // based on Dijkstra algorithm
  std::vector<Weight> res(g.size(), inf<Weight>);
  priority_queue<std::pair<Weight, size_t>, std::greater<>> q;
  res[s] = 0;
  q.emplace(0, s);
  while (!q.empty()) {
    Weight w;
    size_t v;
    std::tie(w, v) = q.top();
    q.pop();
    if (w > res[v]) continue;

    for (const auto& e: g[v]) {
      if (res[e.dst] > w + e.cost) {
        res[e.dst] = w + e.cost;
        q.emplace(res[e.dst], e.dst);
      }
    }
  }
  return res;
}

int main() {
  size_t N;
  scanf("%zu", &N);

  graph<int> g(N);
  for (size_t i = 1; i < N; ++i) {
    size_t u, v;
    int w;
    scanf("%zu %zu %d", &u, &v, &w);
    --u;
    --v;
    w &= 1;
    g.connect_with(u, v, w);
  }

  auto dist = shortest(g, 0);
  for (size_t i = 0; i < N; ++i)
    printf("%d\n", dist[i] & 1);
}


Measured memory_bytes: 9728
package main

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

const MAX = 10000

func countingSort(A []int) []int {
	C := make([]int, MAX+1)
	for _, value := range A {
		C[value]++
	}
	for i := 1; i < len(C); i++ {
		C[i] = C[i] + C[i-1]
	}
	B := make([]int, len(A))
	for j := 0; j < len(A); j++ {
		B[C[A[j]]-1] = A[j]
		C[A[j]]--
	}
	return B
}
func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()

	n, _ := strconv.Atoi(sc.Text())
	A := make([]int, n)

	for i := range A {
		sc.Scan()
		A[i], _ = strconv.Atoi(sc.Text())
	}

	result := strings.TrimRight(fmt.Sprintf("%+v", countingSort(A))[1:], "]")
	fmt.Println(result)

}



Measured memory_bytes: 74288
import java.util.Scanner;
import java.util.Arrays;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    System.out.println(Math.max(Math.max(a,b),c)-Math.min(Math.min(a,b),c));
    
  }
}

Measured memory_bytes: 21716
#include<stdio.h>
#include<string.h>
char srx[100001];
int main()
{
    gets(srx);
    int n=strlen(srx);
    for(int i=0;i<n;++i)
    {if(i%2)
    continue;
    printf("%c",srx[i]);}
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES//(M_PIに使える（π）)

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<string.h>
#include<algorithm>
#include<numeric>
#include<random>
#include <functional>
using namespace std;

int main() {
	int N = 0;
	vector <long long> A;
	int ans = 0;
	int f = 0;
	cin >> N;
	for (int i = 0;i<N;i++) {
		int num = 0;
		cin >> num;
		A.push_back(num);
	}

	sort(A.begin(),A.end());
	ans++;
	f = 1;
	for (int i = 1;i<N;i++) {
		
			if (A[i]==A[i-1] && f==1) {
				f = 0;
				ans--;
			}
			else {

				ans++;
				f = 1;
			}
		
		
		

	}
	cout << ans << endl;



	return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int a[N],v[N],n,ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		int x=a[i];
		if(!v[x])
		{
			for(int j=x;j<=1000000;j+=x)
				v[j]=1;
			if(a[i]!=a[i+1])
				ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 8500
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t n,k,i,l,r,m,s;
  cin>>n>>k;
  vector<int64_t> a(n);
  for(i=0;i<n;i++) cin>>a.at(i);
  sort(a.begin(),a.end());
  l=0;
  r=a.at(n-1);
  while(r-l>1){
    m=(l+r)/2;
    s=0;
    for(i=0;i<n;i++){
      s+=a.at(i)/m-1;
      if(a.at(i)%m>0) s++;
      if(s>k) break;
    }
    if(s<=k) r=m;
    else l=m;
  }
  cout<<r<<endl;
}

Measured memory_bytes: 4776
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
#include <math.h>
using namespace std;

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	if (c - b == b - a) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
s=input()
for bit in range(1<<3):
    ans=int(s[0])
    f=s[0]
    
    for i in range(3):
        if bit&(1<<i):
            ans+=int(s[i+1])
            f+='+'
        else:
            ans-=int(s[i+1])
            f+='-'
        f+=s[i+1]
    if ans==7:
        print(f+'=7')
        exit()

Measured memory_bytes: 3060
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    zoro = 0
    for _ in range(N):
        x, y = map(int, input().split())
        if x == y:
            zoro += 1
        else:
            zoro = 0
        if zoro == 3:
            print("Yes")
            return
    print("No")



if __name__ == "__main__":
    main()


Measured memory_bytes: 62052
#include<stdio.h>
int main(){
int n,x;
while(1){
int count = 0;
scanf("%d %d",&n,&x);
if(n==0 && x==0){
    break;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int k=j+1;k<=n;k++){
if(i+j+k==x){
count++;
}

}

}
}
printf("%d\n",count);
}
return 0;
}



Measured memory_bytes: 2072
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
	int k=0;char ch=gt;
	while(ch<'-')ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return k;
}
int dp[305][305][305];
typedef std::pair<int,int> P;
#define mk std::make_pair
std::vector<P>G[305];
const int YL=1e9+7;
inline int MO(const int &a){return a>=YL?a-YL:a;}
inline bool check(int r,int b,int g,int now)
{
	for(int i=0,j=G[now].size();i<j;++i)
	{
		int cnt=0;
		if(G[now][i].first<=r)++cnt;
		if(G[now][i].first<=b)++cnt;
		if(G[now][i].first<=g)++cnt;
		if(cnt!=G[now][i].second)return 0;
	}
	return 1;
}
using std::max;
int main()
{
	int n=in(),m=in();
	for(int i=1;i<=m;++i)
	{
		int l=in(),r=in(),x=in();
		G[r].push_back(mk(l,x));
	}
	int ans=0;dp[0][0][0]=1;
	for(int r=0;r<=n;++r)
		for(int b=0;b<=n;++b)
			for(int g=0;g<=n;++g)
			{
				if(!dp[r][b][g])continue;
				int i=max(r,max(b,g));
				if(!check(r,b,g,i))continue;
				if(i==n)ans=MO(ans+dp[r][b][g]);
				dp[i+1][b][g]=MO(dp[i+1][b][g]+dp[r][b][g]);
				dp[r][i+1][g]=MO(dp[r][i+1][g]+dp[r][b][g]);
				dp[r][b][i+1]=MO(dp[r][b][i+1]+dp[r][b][g]);
			}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 110848
A,B,C,D = map(int,input().split())
HP_takahashi = A
HP_aoki = C
while (HP_takahashi>0 and HP_aoki>0):
  HP_aoki =HP_aoki - B
  if (HP_aoki<=0):
    print("Yes")
  else:
    HP_takahashi = HP_takahashi - D
    if (HP_takahashi<=0):
      print("No")

Measured memory_bytes: 9180
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a,b = I()
x = max(a+b,a-b)
print(max(x,a*b))


Measured memory_bytes: 9964
import java.lang.Long.parseLong
import java.util.*

fun main(args:Array<String>) {
    val mod = 1000000007L
    var (N,M) = readLine()!!.split(' ').map(String::toInt)

    val list = Array(N+1){ mutableListOf<Pair<Int, Long>>()}
    val ans = Array(M){""}
    for (m in 0 until M) {
        val (P, Y) = readLine()!!.split(' ').map(String::toLong)
        list[P.toInt()].add(m to Y)
    }
    for ((i0,l) in list.withIndex()) {
        l.sortBy { it.second }
        for ((i1, p) in l.withIndex())
            ans[p.first] = "%06d%06d".format(i0, i1+1)
    }

    println(ans.joinToString("\n"))
}

Measured memory_bytes: 144908