akhauriyash/Code-Regression huggingface dataset:
//	ZapZu's code hohoho
//	#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define dfs_black 1
#define dfs_white -1
#define pr pair
#define vt vector
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef double db;
typedef long long li;
typedef long double ld;

typedef pr<int, int> ii;
typedef pr<ld,ld> dd;

typedef vt<int> vi;
typedef vt<li> vli;
typedef vt<ld> vld;
typedef vt<ii> vii;

typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<int, char> mic;

typedef set<int> s_i;
typedef set<char> s_c;

const int MOD = 1e9+7;
const li INF = 1e18;
const ld PI = 4*atan((ld)1);
int a[100005],c[100005];
signed main()
{
//	freopen(".inp", "r", stdin);
//	freopen(".out", "w", stdout);
	string s;
	cin>>s;
	int n=s.length();
	for(int i=0; i<n; i++)
	{
		if(s[i]!=s[i-1]) c[i]=1;
	}
	int ans=n-1;
	for(int i=1; i<=n; i++)
	{
		if(c[i]) ans=min(ans, max(i-1, n-1-i));
	}
	cout<<ans+1;
}




Measured memory_bytes: 896
package main

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

func main() {
	_ = nextInt()
	s := nextLine()
	r, b := 0, 0
	for _, v := range s {
		if v == 'R' {
			r++
		} else {
			b++
		}
	}
	if r > b {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func lcm(a, b int64) int64 {
	return (a / gcd(a, b)) * b
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

const size = 1000000

var reader = bufio.NewReaderSize(os.Stdin, size)

func nextLine() string {
	var line, buffer []byte
	isPrefix := true
	var err error
	for isPrefix {
		line, isPrefix, err = reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
	}
	return string(buffer)
}
func nextStringArray() []string {
	return strings.Split(nextLine(), " ")
}
func nextInt() int {
	n, _ := strconv.Atoi(nextLine())
	return n
}

func nextIntArray() []int {
	s := strings.Split(nextLine(), " ")
	n := len(s)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(s[i])
	}
	return a
}

func min(i, j int) int {
	if i > j {
		return j
	}
	return i
}

func max(i, j int) int {
	if i < j {
		return j
	}
	return i
}


Measured memory_bytes: 640
/*
約数の数
*/

#include<stdio.h>
int main(void){
  int a,b;/*aからbまでの整数*/
  int c;/*約数*/
  int count=0;/*約数の数*/
  
  scanf("%d %d %d",&a,&b,&c);
  while(b>=a){
    if(c%a == 0)
      count++;
    a++;
  }
  printf("%d\n",count);
  return 0;
}
      
  


Measured memory_bytes: 2760
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define GOAL 2019
#define NUM 105

int N,M;
int loc[NUM];
bool check[GOAL+1];

int main(){

	scanf("%d",&N);

	for(int i = 1; i <= GOAL; i++){

		check[i] = false;
	}

	for(int i = 1; i <= N; i++){

		scanf("%d",&loc[i]);
		check[loc[i]] = true;
	}

	scanf("%d",&M);

	int tmp;

	for(int loop = 0; loop < M; loop++){

		scanf("%d",&tmp);

		if(loc[tmp] == GOAL)continue;
		if(check[loc[tmp]+1])continue;

		check[loc[tmp]] = false;
		loc[tmp]++;
		check[loc[tmp]] = true;
	}

	for(int i = 1; i <= N; i++){

		printf("%d\n",loc[i]);
	}

	return 0;
}



Measured memory_bytes: 3208
#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);

template <class T, class S>
using umap = std::unordered_map<T, S>;
using ll = long long;
using namespace std;

int main() {
    ll a[3][3];
    ll hit[3][3];
    ll n;

    REP(i, 3){
        REP(j, 3){
            cin >> a[i][j];
        }
    }

    cin >> n;

    REP(i, 3){
        REP(j, 3){
            hit[i][j] = 0;
        }
    }

    REP(i, n){
        ll tmp;
        cin >> tmp;
        REP(j, 3){
            REP(k, 3){
                if(a[j][k] == tmp){
                    hit[j][k]++;
                }
            }
        }
    }

    ll ans = 0;
    REP(i, 3){
        if ((hit[i][0]!=0)&&(hit[i][1]!=0)&&(hit[i][2]!=0)){
            ans++;
        }
        if ((hit[0][i]!=0)&&(hit[1][i]!=0)&&(hit[2][i]!=0)){
            ans++;
        }
    }

    if ((hit[0][0]!=0)&&(hit[1][1]!=0)&&(hit[2][2]!=0)){
            ans++;
        }
    if ((hit[2][0]!=0)&&(hit[1][1]!=0)&&(hit[0][2]!=0)){
            ans++;
        }
    if (ans==0){
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }

    return 0;
}

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

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

    int n;
    cin >> n;

    int count = 0;
    for(int i=0;i<n;i++){
        int s,f;
        cin >> s >> f;
        if(s<=a&&f<=a){
            count++;
        }
        if(b<=f&&b<=s){
            count++;
        }      
    }
    if(count==n){
        cout << 0 << endl;
    }
    else{
        cout << 1 << endl;
    }
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const long double PI = acos(-1.0L);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> l(m);
  rep(i, m) {
    int k;
    cin >> k;
    l[i].resize(k);
    rep(j, k) {
      cin >> l[i][j];
      --l[i][j];
    }
  }
  vector<int> p(m);
  rep(i, m)
    cin >> p[i];
  int ans = 0;
  rep(i, 1<<n) {
    bool flag = true;
    rep(j, m) {
      int cnt = 0;
      for (auto e : l[j]) {
        if (i>>e & 1)
          cnt++;
      }
      if (cnt%2 != p[j]) {
        flag = false;
        break;
      }
    }
    if (flag)
      ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188&lang=jp
using namespace std;
int dfs(int &k, const string str);
int dfs2(int &k, const string str);
int get_int(int &k, const string str);

// stage k > 1
int dfs(int&k, const string str) {
	vector<int> val;
	int ans = 0;
	while (k < str.length()) {
		if (str[k] == '[') {
			if (str[k + 1] >= '0' && str[k + 1] <= '9') {
				int x = dfs2(k, str);
				val.push_back(x);
			}
			else {
				k++;
				int x = dfs(k, str);
				val.push_back(x);
				k++;
			}
		}
		if (str[k] == ']') {
			break;
		}
	}
	sort(val.begin(), val.end());
	for (int i = 0; i <= val.size() / 2;i++) {
		ans += val[i];
	}
	return ans;
}
// stage 1
int dfs2(int&k, const string str) {
	vector<int> val;
	int ret = 0;
	while (k < str.length()) {
		if (str[k] == '[') {
			k++;
			val.push_back(get_int(k, str));
		}
		else if (str[k] == ']'){
			sort(val.begin(), val.end());
			for (int i = 0; i <= val.size() / 2;i++) {
				ret += (val[i] + 1) / 2;
			}
			break;
		}
	}
	return ret;
}

int get_int(int &k, const string str) {
	int ret = 0;
	while (k < str.length()) {
		if (str[k] >= '0' && str[k] <= '9') {
			ret = ret * 10 + (str[k] - '0');
			k++;
		}
		else if (str[k] == ']') {
			k++;
			break;
		}
	}
	return ret;
}

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	for (int i = 0; i < n;i++) {
		string str; cin >> str;
		int k= 0;
		cout << dfs(k, str) << endl;
	}
}

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

int main(){
      int A,B,C;cin >> A >> B >> C;
      int ans=0;
      
      ans = (A-B);
      ans = C -ans;

      if(ans <= 0){
            cout << 0 << endl;
      }else{
            cout << ans << endl;
      }
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int L;
	int A;
	int B;
	int C;
	int D;
	int x=0,y=0,z=0;
	scanf("%d %d %d %d %d",&L,&A,&B,&C,&D);
	if(A%C!=0){
		x=A/C+1;
	} else {
		x=A/C;
	}
	if(B%D!=0){
		y=B/D+1;
	} else {
		y=B/D;
	}
	if(x>y){
		z=L-x;
	} else {
		z=L-y;
	}
	printf("%d\n",z);
	return 0;
}

Measured memory_bytes: 596
# jsc2019-qualB - Kleene Inversion
class BIT:  # Binary Indexed Tree (Fenwick Tree)
    def __init__(self, lim):
        self.size = lim
        self.tree = [0] * (lim + 1)  # 1-idx

    def add(self, i, x):  # add x to tree[i], O(logN)
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):  # sum of [1, i], O(logN)
        ret = 0
        while i > 0:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def range_sum(self, l, r):  # range sum of [l, r]
        return self.sum(r) - self.sum(l - 1)


def main():
    N, K, *A = map(int, open(0).read().split())
    tree = BIT(2000)
    x = 0
    for i, a in enumerate(A, 1):  # internal inversion
        tree.add(a, 1)
        x += i - tree.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  # external inversion
        tree.add(a, 1)
        y += i + N - tree.sum(a)
    MOD = 10 ** 9 + 7
    print((x * K + y * K * (K - 1) // 2) % MOD)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<pair<int, int>, int> PP;
const ll INFL = 1LL << 60;
const ll MOD = 1000000007;
const int INF = 1000000000;
const int MAX = 300000;
int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

//------------------------------------------------------------------------------------------------------------------------------

int main(void) {
    string s;
    cin >> s;
    int sz = s.size();
    ll ans = 0;

    for (int i = 0; i < (1 << (sz - 1)); i++) {
        ll num = 0;
        for (int j = 0; j < sz; j++) {
            num *= 1LL * 10;
            num += 1LL * (s[j] - '0');
            if (j == sz - 1 || i & (1 << j)) {
                ans += num;
                num = 0;
            }
        }
    }
    cout << ans << endl;
}

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




int main()
{


     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif*/
   int t;
   cin>>t;
   vector<pair<int,int>>nish;


   for(int i=1;i<=t;i++)
   {
    int first;
    cin>>first;
    nish.push_back({first,i});
   }

   sort(nish.begin(),nish.end());
   for(int i=0;i<t;i++)
   {
    cout<<nish[i].second<<" ";
   }
   cout<<endl;
    return 0;
    
}

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

void count(string s, int p, int &b, int &a) {
    b = a = 0;
    int l = s.size();
    char c = s[p];
    
    for (int i = 0; i < l; i++) {
        if (s[i] == c) {
            if (i < p) {
                b++;
            }
            else if (i > p) {
                a++;
            }
        }
    }
}

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> cp(n+1, 0);
    int b, a;
    int ans = 0;
    
    cp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        count(s, i, b, a);
        cp[i + 1] = cp[i];
        
        if (b && a) {
            // nop
        }
        else if (b && !a) {
            cp[i + 1]--;
        }
        else if (!b && a) {
            cp[i + 1]++;
        }
        else {
            // nop
        }
    }
    
    for (int i = 0; i < (n+1); i++) {
        ans = max(ans, cp[i]);
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    ll x,y;cin>>x>>y;
    ll cnt=0;
    while(x<=y){
        cnt++;
        x*=2;
    }
    co(cnt);
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll MOD = 1000000007;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, ans = 0, w, l;
vl A;
map<ll, ll> insuu;
vl IN;
void insuubunkai(ll n) {
	a = n;
	for (ll i = 2; i * i <= a; i++) {
		if (a % i == 0) {
			insuu[i] = 0;
			IN.push_back(i);
			while (a % i == 0) {
				insuu[i]++;
				a = a / i;
			}
		}
	}

	if (a != 1) {
		insuu[a]++;
		IN.push_back(a);
	}
}
void input() {
	cin >> n;
	insuubunkai(n);
	ans = 0;
	for (ll i=1; i < (1 << IN.size());i++) {
		b = 1;
		k = 0;
		rep(j, IN.size()) {
			if (i & (1 << j)) {
				b *= IN[j];
				k++;
			}
		}
		if(k%2==1)ans += n / b;
		else ans -= n / b;
		//cout << i << " " << ans << endl;
	}

	ans = n - ans;
	cout << ans << endl;
}


void solve() {
	
}

int main() {
	input();
	solve();
}


Measured memory_bytes: 3148
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <stack>
#include <numeric>
using namespace std;
using ll = long long;
const ll mod = 1000000007;

int main(){
	int n; cin >> n;
    int num[1000]={0};
    for(int i=2; i<=n; ++i){
        int arr = i;
        for(int j=2; j<1000; ++j){
            while(true){
                if(arr%j==0){
                    num[j]++;
                    arr/=j;
                }else {
                    break;
                }
            }
        }
    }
    ll ans=1;
    for(int i=2; i<1000; ++i){
        ans = (ans%mod)*(num[i]+1);
    }
    cout << ans << endl;
        return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split( ))
a =  list(map(int, input().split( )))
a.sort()

mod = 10**9 +7

chs = []
tmp = 1
for i in range(k-1):
    tmp *= n-i-1#n,...,n-k+1
    tmp *= pow(i+1,mod-2,mod)#1,...,k
    tmp %= mod
chs.append(tmp)
for i in range(n-k,-1,-1):
    tmp *= i#n-k,...k
    #print(i,pow(i,mod-2,mod),tmp,end = " ")
    tmp *= pow(i+k-1,mod-2,mod)
    #print(tmp,end = " ")
    tmp %= mod
    #print(tmp)
    chs.append(tmp)
mx = 0
for i in range(n-k+1):
    mx += chs[i]*a[-i-1]
    mx %= mod
mn = 0
for i in range(n-k+1):
    mn += chs[i]*a[i]
    mn %=mod

ans = (mx-mn)%mod

print(ans)

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

int main(){
	int16_t N;
	cin >> N;
	vector<int> a(N);
	for(int16_t i = 0; i < N; i++) {
		cin >> a.at(i);
	}
	
	int count = 0;
	for(int16_t i = 0; i < N; i++) {
		bool judge = true;
		while(judge) {
			if(a.at(i) % 2 == 0) {
				a.at(i) /= 2;
				count++;
			} else {
				judge = false;
			}
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 256
import math

N = int(input())

def append_divisor(divisors, num):
    if num not in divisors:
        divisors[num] = 1
    else:
        divisors[num] += 1

def solve(divisors, num):
    limit = int(math.sqrt(num)) + 1
    for i in range(2, limit):
        while num % i == 0:
            append_divisor(divisors, i)
            num //= i
    if num != 1:
        append_divisor(divisors, num)

divisors = {}
for i in range(2, N + 1):
    solve(divisors, i)
# print(divisors)

mod = 10**9 + 7

ans = 1
for d in divisors:
    ans = (ans * (divisors[d] + 1)) % mod
print(ans)


Measured memory_bytes: 39664
/* AOJ 0056 Goldbach's Conjecture */

#include <iostream>

using namespace std;

void sieve_of_eratosthenes();

const int MAX_N = 50000;

bool is_prime[MAX_N + 1];

int
main()
{
    sieve_of_eratosthenes();

    for (;;) {
        int n, max;
        int n_combinations = 0;
        int i;

        cin >> n;
        if (n == 0) break;

        max = n / 2;
        for (i = 2; i <= max; i++) {
            if (is_prime[i] && is_prime[n - i]) n_combinations++;
        }

        cout << n_combinations << endl;
    }

    return 0;
}

// エラトステネスの篩
void
sieve_of_eratosthenes()
{
    int i;

    is_prime[0] = is_prime[1] = false;
    fill(is_prime, is_prime + MAX_N + 1, true);

    for (i = 2; i <= MAX_N; i++) {
        int j;

        if (!is_prime[i]) continue;

        j = 2 * i;
        while (j <= MAX_N) {
            is_prime[j] = false;
            j += i;
        }
    }
}

Measured memory_bytes: 1208
#include<iostream>
using namespace std;	
long long sum;
long long n,a,b,f[100000000];
int main()
{

	cin>>n>>a>>b;
	long long ans=0;
	for(long long i=1;i<=n;i++)
	{
		cin>>f[i];
	}
	for(long long i=2;i<=n;i++)
	{
		sum=0;
		if(((f[i]-f[i-1])*a)>b)
		sum=b;
		else sum=(f[i]-f[i-1])*a;
		ans+=sum;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

struct data{
    int a,b,c;
    bool operator < (data obj) const{
        return ((this->a)-(this->b)) > obj.a-obj.b;
    }
};

signed main(){
    int x,y,z;
    cin>>x>>y>>z;
    int n = x+y+z;
    vector<data> v(n);
    rep(i,n){
        int a,b,c;
        cin>>a>>b>>c;
        v[i] = data{a,b,c};
    }
    
    sort(all(v));
    
    
    rep(i,n){
        v[i].a -= v[i].c;
        v[i].b -= v[i].c;
    }
    
    vector<int> dax(n+1,0), daz(n+1,0), dby(n+1,0), dbz(n+1,0);
    
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    rep(i,n){
        if(i<x){
            pq.push(pii(v[i].a,v[i].c));
            dax[i+1] = dax[i] + v[i].a+v[i].c;
        }else{
            int AC = pq.top().first;
            int C = pq.top().second;
            
            if(AC<v[i].a){
                dax[i+1] = dax[i]-(AC+C)+(v[i].a+v[i].c);
                daz[i+1] = daz[i]+C;
                pq.pop();
                pq.push(pii(v[i].a,v[i].c));
            }else{
                dax[i+1] = dax[i];
                daz[i+1] = daz[i]+v[i].c;
            }
        }
    }
    
    while(pq.size())pq.pop();
    reverse(all(v));
    rep(i,n)swap(v[i].a,v[i].b);
    swap(x,y);
    
    rep(i,n){
        if(i<x){
            pq.push(pii(v[i].a,v[i].c));
            dby[i+1] = dby[i] + v[i].a+v[i].c;
        }else{
            int AC = pq.top().first;
            int C = pq.top().second;
            
            if(AC<v[i].a){
                dby[i+1] = dby[i]-(AC+C)+(v[i].a+v[i].c);
                dbz[i+1] = dbz[i]+C;
                pq.pop();
                pq.push(pii(v[i].a,v[i].c));
            }else{
                dby[i+1] = dby[i];
                dbz[i+1] = dbz[i]+v[i].c;
            }
        }
    }

    swap(x,y);
    int ans = 0;
    for(int i=x;i<=n-y;i++){
//        cout<<i<<" : "<<dax[i]<<" "<<daz[i]<<" "<<dby[n-i]<<" "<<dbz[n-i]<<endl;
        ans = max(ans,dax[i]+daz[i]+dby[n-i]+dbz[n-i]);
    }
    cout<<ans<<endl;
    
    
}

Measured memory_bytes: 7924
#include <bits/stdc++.h>
using namespace std;
int uni[100000],n,m,r[100000];
int find(int a){
	if(a!=uni[a])a=find(uni[a]);
	return a;
}
bool same(int a,int b){
	return find(a)==find(b);
}
void unit(int a,int b){
	int c=find(a),d=find(b);
	if(r[c]>r[d])uni[d]=c;
	else{uni[c]=d;
		if(r[c]==r[d])r[c]++;
	}
}
int main() {
	cin>>n>>m;
	for(int i=0;i<n;i++){uni[i]=i;r[i]=0;}
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>c>>a>>b;
		if(c)cout<<(same(a,b)?1:0)<<endl;
		else unit(a,b);
	}
}

Measured memory_bytes: 3176
import std.stdio;
import std.conv;
import std.string;
import std.algorithm;
import std.math;

void main() {
  long n, k;
  readf("%d %d\n", &n, &k);
  long value = n % k;
  value = k-value < value ? k-value : value;
  writeln(value);
}


Measured memory_bytes: 256
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

K, T, = map(int, input().split())
L = [int(v) for v in input().split()]

for i in range(T):
    L[i] = (-L[i], i)

heapify(L)

m = [None] * K
index = 0
before = None
for _ in range(K):
    if len(L) == 0:
        heappush(L, before)
        before = None

    a, b = heappop(L)
    if before != None:
        heappush(L, before)
        before = None

    m[index] = b
    index += 1
    if a + 1 != 0:
        before = (a + 1, b)

if before != None:
    a, b = before
    m[-1] = b

ans = 0
for i in range(K - 1):
    if m[i] == m[i + 1]:
        ans += 1

print(ans)

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define rep(n) for(ll i = 0 ; i<n ; i++) 
#define repd(n) for(ll i = n-1 ; i>=0 ; i--)
#define MOD 1000000007
#define sz(a) a.size()

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll a,b; cin>>a>>b;
	if(a==1 || b==1) cout <<"1"; else 
	cout << (a*b+1)/2;
	
	return 0;
}

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

int main()
{
    
    /*
    string s1;
    getline( cin, s1 );
    int n1 = s1.size();
    */
    int a, b;
    cin >> a >> b ;
    
    if( 2*a <= 16 && 2*b <= 16 ){
        cout << "Yay!" << endl;
    }
    else {
        cout << ":(" << endl;
    }
      
    return 0;
}


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

int gcd(int a,int b){
  if(a<b){
    int temp=a;
    a=b;
    b=temp;
  }
  while(a%b!=0){
    int temp=a%b;
    a=b;
    b=temp;
  }
  return b;
}

int main(){
  int n;
  cin >> n;
  int *a = new int[n];
  for(int i=0;i<n;i++)
  	cin>>a[i];
  
  int ans=gcd(a[0],a[1]);
  for(int i=2;i<n;i++)
    ans = gcd(ans,a[i]);
  
        
  cout << ans<<"\n";
}

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

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

int main(){
	string s;
	cin >> s;
	
	rep(i, s.size()){
		if(i % 2 == 1){
			if(s[i] == 'R'){
				cout << "No" << endl;
				return 0;
			}
		}
		else{
			if(s[i] == 'L'){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
// #include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
// #include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
*/
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii;
typedef pair<int, ppiipii> pippiipii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> ppiii;
typedef pair<int, ppiii> pippiii;
typedef pair<int, ll> pill;
typedef pair<int, double> pid;
typedef pair<string, string> pss;
// note to self, the below two triggers someone
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef long double ld;

char buf[200005];

int main() {
  scanf("%s", buf);
  int a = 0;
  while(buf[a] != 'A') a++;
  int b = strlen(buf);
  while(buf[b-1] != 'Z') b--;
  printf("%d\n", b-a);
}


Measured memory_bytes: 384
from collections import Counter

dic = Counter()

while True:
  try:
    dic[int(input())] += 1

  except EOFError:
    break

lst = dic.most_common()
max_value = lst[0][1]
mode_values = [t[0] for t in lst if t[1] == max_value]
mode_values.sort()

for v in mode_values:
  print(v)


Measured memory_bytes: 6004
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

ll invNum(vector<int> &A, int l, int r){
    if(r - l == 1) return 0;
    int mid = (l + r) >> 1;
    ll res = invNum(A, l, mid) + invNum(A, mid, r);

    vector<int> L, R;
    for(int i=l;i<r;i++){
        if(i < mid) L.push_back(A[i]);
        else R.push_back(A[i]);
    }
    int N = L.size(), M = R.size();
    int cur = l, j = 0;
    for(int i=0;i<N;i++){
        while(j < M && L[i] > R[j]) A[cur++] = R[j++];
        res += j;
        A[cur++] = L[i];
    }
    for(; j<M;j++) A[cur++] = R[j];
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    ll res = invNum(A, 0, N);
    REP(i,N){
        cout << A[i];
        if(i < N - 1) cout << " ";
    }
    cout << endl;
    cout << res << endl;
}



Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int x,y;
		while(true) {
			int H=scan.nextInt();
			int W=scan.nextInt();
			if(H == 0 && W == 0) break;
			for(x=0;x<H;x++) {
				for(y=0;y<W;y++) {
					System.out.printf("#");
				}
				System.out.printf("\n");
			}
			System.out.printf("\n");
		}
		scan.close();
}
}


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

using namespace std;

const int MAXN = 1010;
const int MOD = 1000000007;
int H, W;
int DP[MAXN][MAXN];

char MAT[MAXN][MAXN];

int main(){

    cin >> H >> W;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> MAT[i][j];
        }
    }
    DP[1][1] = 1;

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (i == 1 && j == 1) continue;
            int up = DP[i - 1][j];
            if (MAT[i - 1][j] == '#') up = 0;
            int left = DP[i][j - 1];
            if (MAT[i][j - 1] == '#') left = 0;
            DP[i][j] = (up % MOD + left % MOD) % MOD;
        }
    }

    cout << DP[H][W];
    return 0;
}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;
// typedef long long int 
typedef long long int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
// typedef pair<ll,ll> pll;
const int modi = 1e9+7;
const int mxn = 1e5+10;
vi adj[mxn];

void dfs(int u ,int p, int* dis, int d = 0){
	dis[u] = d;
	for(auto v:adj[u]){
		if(v==p)continue;

		dfs(v,u,dis,d+1);
	}
}

void solve(){
	int n;
	cin >> n;
	int t,a; // t is going away a is coming near
	cin >> t >> a;
	--t,--a;
	for(int i =0;i<n-1;i++){
		int u ,v;
		cin >> u >> v;
		--u,--v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vector<int> leaves;
	for(int i =0;i<n;i++)
	{
		if(adj[i].size()==1){
			leaves.pb(i);
		}
	}

	int dt[n],da[n];
	dfs(t,-1,dt);
	dfs(a,-1,da);
	int ans =0;
	for(auto e:leaves){
		// cout << e << " " << endl;
		if(dt[e]>da[e])
			continue;
		ans = max(ans,da[e]-1);
	}
	cout << ans << endl;
 }
int main(){
	fast;
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt","r",stdin);
	// 	freopen("output.txt","w",stdout);
	// #endif

	// int t;cin >> t;while(t--)
		solve();
}


Measured memory_bytes: 11904
#include <iostream>
using namespace std;
int main(void){
  int n,k;
  cin >> n >> k;
 
  long long a = n / k;
  
 
  if(k % 2 == 1)
    cout << a * a * a << endl;
  else{
    long long b = n / (k / 2);
  	long long c = b - a;
    cout << a * a * a + c * c * c << endl;
  }
 
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      ans=max(ans,abs(a[i]-a[j]));
    }
  }
  cout<<ans<<endl;
  return 0;
}
  

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

int main()
{
  int N;
  int count = 0;
  vector<int> arr(210);
  cin >> N;
  for (int i = 0; i < N; i++)
    cin >> arr.at(i);
  while(true)
  {
    bool some_odd = false;
    for (int i = 0; i < N; i++)
    {
      if(arr.at(i) % 2 != 0)
        some_odd = true;
    }
    if (some_odd)
      break;
    for (int i = 0; i < N; i++)
    {
      arr.at(i) /= 2;
    }
    count++;
  }  
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define ll long long
#define PI 3.141592653589
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EPS 1e-7
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
const ll MOD = 1e9+7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
ll fast_power(ll x, ll p){
    ll res = 1;
    while(p > 0){
        if(p & 1){
            res = (res * x);
        }
        p = p >> 1;
        x = (x*x);
    }
    return res;
}

int n,k;
int a[105];
int dp[100005][2];

int solve(int left, int turn) {
    if (left == 0) {
        return turn?1:-1;
    }
    if (dp[left][turn])
        return dp[left][turn];
    int ans = turn?1:-1;
    for (int i = 0; i < n; i++) {
        int x = a[i];
        if (left - x < 0) continue;
        if (turn) {
            ans = min(ans, solve(left-x, !turn));
        } else
            ans = max(ans, solve(left-x, !turn));
    }
    cout << left << " " << turn << "\n";
    return dp[left][turn] = ans;
}

int main() {
    IO;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j < 2; j++) {
            if (j)
                dp[i][j] = 1;
            else
                dp[i][j] = -1;
        }
    }

    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < n; k++) {
                if (i - a[k] < 0)   break;
                if (j)
                    dp[i][j] = min(dp[i][j], dp[i - a[k]][!j]);
                else
                    dp[i][j] = max(dp[i][j], dp[i - a[k]][!j]);
            }
        }
    }
    if (dp[k][0] == 1) {
        cout << "First" << "\n";
    } else
        cout << "Second" << "\n";
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MAX_DIGIT = 50;
long long dp[100][2]; // dp[上から i 桁まで][ smaller ]

int main() {
  int N;
  long long K;
  cin >> N >> K;
  vector<long long> A(N);
  for (int i = 0; i < N; ++i) cin >> A[i];
  
  memset(dp, -1, sizeof(dp)); // DP 配列を -1 で初期化
  dp[0][0] = 0; // 初期条件
  rep(i, MAX_DIGIT) {
    ll mask = 1ll<<(MAX_DIGIT - i - 1);
    int num = 0;
    rep(i, N) {
      if(mask & A[i]) num++;
    }

    if(dp[i][1] != -1) {
      chmax(dp[i+1][1], dp[i][1] + mask * max(num, N - num));
    }
    if(dp[i][0] != -1) {
      if(mask & K) {
        chmax(dp[i+1][1], dp[i][0] + mask * num);
        chmax(dp[i+1][0], dp[i][0] + mask * (N - num));
      } else {
        chmax(dp[i+1][0], dp[i][0] + mask * num);
      }
    }
  }

  cout << max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1]) << endl;
}


Measured memory_bytes: 1024
# Problem: https://atcoder.jp/contests/abc080/tasks/abc080_b
# Python 1st Try

import sys
# from collections import defaultdict
# import heapq,copy
# from collections import deque
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solver(inputNum):
    result = "No"
    # algorithm
    strNum = str(inputNum)
    divisorNum = 0
    for j in range(0, len(strNum), +1):
        divisorNum = divisorNum + int(strNum[j])
    if inputNum % divisorNum == 0:
        result = "Yes"
    return result


if __name__ == "__main__":
    print("{}".format(solver(II())))


Measured memory_bytes: 3064
import itertools

N = int(input())
zahyo = [ list(map(int, input().split())) for _ in range(N)]

ans = 0
cnt = 0
for pat in itertools.permutations(zahyo):
    cnt += 1
    for i in range(len(pat)-1):
        distance = ((pat[i][0]-pat[i+1][0])**2 + (pat[i][1]-pat[i+1][1])**2)**(1/2)
        ans += distance
print(ans/cnt)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const int INF = 1e9;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

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

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 1000010; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long mod(long long val, long long m) {
  long long res = val % m;
  if (res < 0) res += m;
  return res;
}
int main() {
    int N,K;
    cin >> N >> K;
    vector<ll> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    sort(vec.begin(),vec.end());
    COMinit();
    ll ret = 0;
    for(int i = 0;i < N;i++) {
        ll a = COM(i,K - 1);
        ll c = COM(N - i - 1,K - 1);
        ret = ret + mod(a - c,MOD) * vec.at(i);
        ret = mod(ret,MOD);
    }
    cout << ret << endl;
}

Measured memory_bytes: 24448
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] c = str.toCharArray();
        
        long sum = 0;
        for (int i = 0; i < c.length; i++) {
            sum += Integer.parseInt(String.valueOf(c[i]));
        }
        
        String ans = "No";
        if (sum % 9 == 0) {
            ans = "Yes";
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 50192
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


class Main {

	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		
		ArrayList<Integer> array = new ArrayList<Integer>();
		
		long sum = 0;
		int n = sc.nextInt();
		int a;
		
		if(0 < n && n <= 10000){
			
			for(int i = 0; i < n; i++){
				
				a = sc.nextInt();
				
				if(-1000000 <= a && a <= 1000000){
					array.add(a);
					sum = sum + a;
				}
				
			}
			
			Collections.sort(array);
			
			int na = array.size() - 1;
			int max = array.get(na);
			int min = array.get(0);
			
			System.out.println(min + " " + max + " " + sum);
		}
		
	}

}

Measured memory_bytes: 42496
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    int n;
    cin >> n;
    ll res = 1;
    while (n--)
    {
        ll t;
        cin >> t;
        res = res / __gcd(res, t) * t;
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 256
// C - Lining Up
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

	map<int,int> A;
	for(int i=1; i<=N; i++){
		int a; cin>>a;
		A[a]++;
	}

	int ans = 1;
	int i,s = (N-1)%2;
	for(i=s; i<N; i+=2){
		if(A.count(i)!=1){
			cout<< '0' <<endl;
			return 0;
		}

		if(A[i]!=2){
			if(s==0 && i==0 && A[i]==1) continue;
			cout<< '0' <<endl;
			return 0;
		}
		ans = ans * 2 % MOD;
	}
	cout<< ans <<endl;
}

Measured memory_bytes: 3200
#include<iostream>
#include<string.h>
using namespace std;
int main(){
	char bun[25] = {};
	int len;
	cin >> bun;
	len=strlen(bun);
	for(int i=len-1;i>=0;i--){
		cout<<bun[i];
	}
	cout<<endl;
	return 0;
}



Measured memory_bytes: 3020
#include<iostream>
#include<list>


using namespace std;

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

    unsigned int ans[n];
    int mid = n/2;
    ans[n/2] = a[0];
    for(unsigned int i=1;i<=n/2;i++){
        ans[mid+i] = a[i*2-1];
        if(i*2!=n)ans[mid-i] = a[i*2];
    }
    if(n%2==0){
        for(unsigned int i=0;i<n/2;i++){
            unsigned int tmp = ans[i];
            ans[i] = ans[n-i];
            ans[n-i] = tmp;
        }
    }
    for(unsigned int i=0;i<n;i++)cout << ans[i] << " ";
    cout << endl;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define cl clear() ;
#define vl vector<ll>
#define sz size()
#define len length()
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define en end()
#define ro return 0
#define br break
#define eb emplace_back
#define con continue
#define ms(x) memset(x , 0, so x)
#define all(x) (x).be , (x).en
#define acc(x) accumulate((x).be , (x).en , 0ll)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
#define trace3(a,b,c) cerr <<"a is " << a << " b is " << b << " c is " << c << el;
#define trace4(a,b,c,d) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << el ;
#define trace5(a,b,c,d,e) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << el;
#define trace6(a,b,c,d,e,f) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << " f is " << f << el ;

int main()
{
    ios;
    ll n , x;
    cin >> n >> x;
    ll res = 0 ;
    vl v ;
    forn(i , 1 , n){
       ll xx;
       cin >> xx;
       v.pb(xx) ;
       if(v[i-1] > x){
        res = res + v[i-1] - x;
        v[i-1] = x;
       }
    }
    forn(i , 1 , n-1){
       ll nsl = v[i] + v[i-1] ;
       if(nsl > x){
        ll diff = nsl - x;
        v[i] = max(0LL , v[i] - diff) ;
        res = res + diff;
       }
    }
    for(ll i = n-2;i>=0;--i){
        ll nsr = v[i] + v[i+1] ;
        if(nsr > x){
            ll diff = nsr -x ;
            v[i] = max(0LL , v[i] - diff) ;
            res = res + diff;
        }
    }
    cout << res<< el ;
    ro ;


}



Measured memory_bytes: 1400
N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(min(K, 50)):
    B = [0 for i in range(N)]
    for j in range(0, N):
        l = max(0, j - A[j])
        r = min(N - 1, j + A[j])
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1

    for j in range(1, N):
        B[j] += B[j - 1]
        
    A = B

[print(i, end=' ') for i in B]
print()


Measured memory_bytes: 170548
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll mod=1e9+7;
const int inf=1<<30;

struct unionfind{
  vector<int> par;
  vector<int> rank;
  unionfind(int n=1){
    init(n);
  }
  void init(int n=1){
      par.resize(n); rank.resize(n);
      for(int i=0;i<n;++i) par[i]=i,rank[i]=0;
  }
  int root(int x){
    if(par[x]==x){
      return x;
    }
    else{
      int r=root(par[x]);
      return par[x]=r;
    }
  }
  bool issame(int x,int y){
    return root(x)==root(y);
  }
  bool merge(int x,int y){
    x=root(x); y=root(y);
    if(x==y) return false;
    if(rank[x]<rank[y]) swap(x,y);
    if(rank[x]==rank[y]) ++rank[x];
    par[y]=x;
    return true;
  }
};

int main(){
  unionfind uf(1e5);
  int n,m; cin >> n >> m;
  rep(i,m){
    int a,b,c;
     cin >> a >> b >> c;
     a--; b--;
    uf.merge(a,b);
  }
  set<int> st;
  rep(i,n){
    st.insert(uf.root(i));
  }
  cout << st.size() << endl;
}

Measured memory_bytes: 5760
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;

int main (void){
	long long int n,i,a[100001],suma=0,sumb=0,ans,ansa,ansb;
	cin >> n;
	for(i=0;i<n;i++) {
		cin >> a[i];
	}
	sort(a,a+n);
	if(n%2==0){
		for(i=1;i<n/2;i++) suma+=a[i-1];
		for(i=n/2+2;i<=n;i++) sumb+=a[i-1];
		ans=2*sumb+a[n/2]-2*suma-a[n/2-1];
	} else {
		for(i=1;i<=(n-3)/2;i++) suma+=a[i-1];
		for(i=(n+3)/2;i<=n;i++) sumb+=a[i-1];
		ansa=2*sumb-2*suma-a[(n-3)/2]-a[(n-1)/2];
		suma=0;
		sumb=0;
		for(i=1;i<=(n-1)/2;i++) suma+=a[i-1];
		for(i=(n+5)/2;i<=n;i++) sumb+=a[i-1];
		ansb=2*sumb-2*suma+a[(n+1)/2]+a[(n-1)/2];
		ans=std::max(ansa,ansb);
	}
	cout << ans << endl;
	return 0;
}

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

const int N = 100009;

int n, a = 1, b = 1, mark[N]={};
bool pass[N]={};
vector<int> adj[N], S;

bool find_route(int u){
    S.push_back(u);
    pass[u] = true;

    if(u == n) return true;

    bool found = false;
    for(int v : adj[u])
        if(!pass[v] && !found) found = find_route(v);

    if(!found) S.pop_back();
    return found;
}

void dfs(int u, int color){
    mark[u] = color; pass[u] = true;
    for(int v : adj[u])
        if(!pass[v] && (!mark[v] || mark[v] == color)){
            if(color == 1 && !mark[v]) a++;
            if(color == 2 && !mark[v]) b++;
            dfs(v,color);
        }
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n-1; i++){
        int x, y; scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    memset(pass, 0, sizeof pass);
    find_route(1);

    // for(int v : S)
    //     fprintf(stderr, "%d ", v);
    // fprintf(stderr, "\n");

    if(S.size() % 2 != 0){
        a = S.size() / 2 + 1;
        b = S.size() / 2;
    }else a = b = S.size() / 2;

    for(int i = 0; i < S.size(); i++)
        if(i < a) mark[S[i]] = 1;
        else mark[S[i]] = 2;

    memset(pass, 0, sizeof pass);
    dfs(1,1);
    dfs(n,2);

    // fprintf(stderr, "%d %d\n", a, b);
    printf("%s\n", a > b? "Fennec":"Snuke");
    return 0;
}


Measured memory_bytes: 11384
#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

constexpr ll mod = 998244353;
int n, s, a[3010];
ll dp[3010];
int main() {
	scanf("%d %d", &n, &s);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int k = 0; k <= s; k++)
			dp[k] *= 2;
		for (int k = s - a[i]; 0 <= k; k--)
			dp[k + a[i]] += dp[k] / 2;
		for (int k = 0; k <= s; k++)
			dp[k] %= mod;
	}
	printf("%lld\n", dp[s]);
}

Measured memory_bytes: 1736
import numpy as np
n, m = map(int,input().split())
l = [list(map(int,input().split()))+ [0] for i in range(m)]
l2 = sorted(l)
p = 0
for i in l2:
    x = 1 if i[0] != p else x + 1
    p = i[0]
    i[2] = x
for i in l:
    print(str(i[0]).zfill(6)+str(i[2]).zfill(6))

Measured memory_bytes: 34344
def ren(a,b,c,d,e,f):
    x = (c*e-f*b)/(a*e-b*d)
    y = (c*d-f*a)/(b*d-e*a)
    print(f'{x+0:.3f} {y+0:.3f}')

while True:
    try:
        a,b,c,d,e,f=map(float,input().split())
    except:
        break
    ren(a,b,c,d,e,f)


Measured memory_bytes: 5604
#include <iostream>
#include <deque>
#include <cstdio>
using namespace std;

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

int mesh[50][50];
int n, m;

struct Point
{
	int x;
	int y;
};

int main()
{
	deque<Point> stack;
	while (true)
	{
		scanf("%d %d", &n, &m);
		if (n == 0 && m == 0) break;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				int a;
				scanf("%d", &a);
				mesh[i][j] = a;
			}
		}
		int count = 0;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (mesh[i][j] == 1)
				{
					Point pt = {j, i};
					stack.push_front(pt);
					mesh[i][j] = 0;
					while (!stack.empty())
					{
						Point point = stack.front();
						stack.pop_front();
						for (int k = 0; k < 8; k++)
						{
							if (0 <= point.y + dy[k] && point.y + dy[k] < m
								&& 0 <= point.x + dx[k] && point.x + dx[k] < n
								&& mesh[point.y + dy[k]][point.x + dx[k]] == 1)
							{
								Point pt = {point.x + dx[k], point.y+dy[k]};
								stack.push_front(pt);
								mesh[point.y + dy[k]][point.x + dx[k]] = 0;
							}
						}
					}
					count++;
				}
			}
		}
		printf("%d\n", count);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    string s;
    cin >> s;
    if(s == "ABC") cout << "ARC" <<endl;
    else cout << "ABC" <<endl;
    
}

Measured memory_bytes: 3628