akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    long double x, y;
    cin >> x >> y;
    y/=x;
    cout << (unsigned long long)std::log2(y)+1 << endl;
}


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

int main()
{
 int a,b,c,d,e,x,y;
 cin>>a>>b>>c>>d>>e;

 if(a<=b&&a<=c)x=a;
 if(b<=a&&b<=c)x=b;
 if(c<=a&&c<=b)x=c;

 if(d<e)y=d;
  else y=e;

 cout<<x+y-50<<'\n';

  return 0;
}

Measured memory_bytes: 1160
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      n: usize,
      k: usize,
      aa: [usize; n],
    }
    let mut dp = vec![false; k+1];
    dp[0] = false;

    for i in 1..k+1 {
        let mut ok = false;
        for j in 0..n {
            if i < aa[j] {
                continue;
            }
            if dp[i-aa[j]] == false {
                ok = true;
                break;
            }
        }
        dp[i] = ok;
    }
    if dp[k] {
        println!("{}", "First");
    } else {
        println!("{}", "Second");
    }
}


Measured memory_bytes: 4352
#include<stdio.h>
 
int main(void){
    double a,b,c,d,e,f,g,x,y;
 
    while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)!=EOF){
        y=(f-c*d/a)/(e-b*d/a);
        x=(f-c*e/b)/(d-a*e/b);
 
        if(-0.0005<x&&x<=0)x=0;
        if(-0.0005<y&&y<=0)y=0;
 
        printf("%.3f %.3f\n",x,y);
     
    }
 
    return 0;
 
}

Measured memory_bytes: 652
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define setDP(arr) memset(arr,-1,sizeof arr)
#define Clear(arr) memset(arr,0,sizeof arr)
#define oo 1000000000
#define inf 1000000000000000000
#define M 998244353
using namespace std;
typedef long long ll;
const int N = 1e6+300;
const int SQRTN = 320;
const int LOGN = 20;
const double PI = acos(-1);
const double TAU = 2*PI;

int a,b,c;

inline void solve(){
  cin >> a;
  int ans=0;
  for(int i = 1,x ; i <= a ; i++){
    cin >> x;
    if(!(i&1))continue;
    ans+=(x%2);
  }
  cout << ans << endl;
}

signed main() {
    int t=1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}


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

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n, r;
	cin >> n;

	r = n % 1000;
	if (r == 0)
		cout << 0;
	else
		cout << 1000 - r;

	return 0;
}

Measured memory_bytes: 3640
#include <string>
#include <iostream>
using namespace std;
int main(){
    string S;
    cin >> S;
    int year = stoi(S.substr(0, 4));
    int month = stoi(S.substr(5, 2));
    int day = stoi(S.substr(8, 2));
    int data = year*10000 + month*100 + day;
    if(data <= 20190430) cout << "Heisei";
    else cout << "TBD";
    return 0;
}

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

const int N = 1e5 + 9;

int ar[ N ], dp[ N ];

int main(){
    int n;
    ios::sync_with_stdio( false );

    cin >> n;
    for( int i = 1; i <= n; i++ ){
        cin >> ar[ i ];
    }


    dp[ 1 ] = 0;
    dp[ 2 ] = abs( ar[ 2 ] - ar[ 1 ] );

    for( int i = 3; i <= n; i++ )
        dp[ i ] = min ( dp[ i - 1 ] + abs( ar[ i ] - ar[ i - 1 ] ), dp[ i - 2 ] + abs( ar[ i ] - ar[ i - 2 ] ) );


    cout << dp[ n ] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

using R = long double;

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

    R p, q;
    int n, m; cin >> n >> m >> p;
    p /= 100.; q = 1 - p;

    vi as(m), bs(m);
    rep(i, m){
        int a, b; cin >> a >> b; a--, b--;
        as[i] = a, bs[i] = b;
    }

    vector<R> dp(1 << n, (R)0);

    rep(sup, 1, 1 << n){
        int l = 0;
        while(not ((sup >> l) & 1)) l++;
        
        R& cur = dp[sup] = (R)1;
        
        for(int sub = ((sup - 1) & sup); sub != sup; sub = ((sub - 1) & sup)){
            if(not ((sub >> l) & 1)) continue;

            int subc = (~sub) & sup;
            R diff = dp[sub];
            rep(i, m){
                int a = as[i], b = bs[i];
                if((((sub >> a) & 1) and ((subc >> b) & 1)) or
                   (((sub >> b) & 1) and ((subc >> a) & 1))){
                    diff *= p;
                }
            }
            cur -= diff;
        }
    }

    cout.precision(20);
    cout << fixed << dp.back() << endl;

    return 0;
}

Measured memory_bytes: 3368
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
#define maxn 100010
#define maxm 200010
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
int ne[maxn], tot;
bool vis[maxn];
LL dist1[maxn], dist2[maxn], ways1[maxn], ways2[maxn];
struct Edge { int from, to, ne; LL w; }edge[maxm << 1];
void add(int u, int v, LL w) {
	edge[tot] = { u, v, ne[u], w };
	ne[u] = tot++;
}
struct node {
	int v; LL c;
	bool operator < (const node nd) const { return c > nd.c; }
};
int n;
void dfs(int src, LL* dist, LL* ways) {
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= n; ++i) dist[i] = inf;
	vis[src] = true; dist[src] = 0; ways[src] = 1;
	priority_queue<node> q;
	while (!q.empty()) q.pop();
	while (true) {
		for (int j = ne[src]; ~j; j = edge[j].ne) {
			int v = edge[j].to;
			if (vis[v]) continue;
			LL now = edge[j].w + dist[src];
			if (now == dist[v]) (ways[v] += ways[src]) %= mod;
			else if (now < dist[v]) {
				dist[v] = now; ways[v] = ways[src];
				q.push({ v, now });
			}
		}
		while (!q.empty() && vis[q.top().v]) q.pop();
		if (q.empty()) break;
		vis[src = q.top().v] = true;
	}
}
int main() {
	memset(ne, -1, sizeof ne);
	int m, s, t;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 0; i < m; ++i) {
		int u, v; LL w;
		scanf("%d%d%lld", &u, &v, &w);
		add(u, v, w), add(v, u, w);
	}
	dfs(s, dist1, ways1);
	dfs(t, dist2, ways2);
	LL ww = ways1[t];
	LL ans = ww * (ww - 1) % mod;
	LL dis = dist1[t];
	if (!(dis & 1)) {
		LL half = dis >> 1;
		for (int i = 1; i <= n; ++i) if (dist1[i] == half && dist2[i] == half) {
			LL temp = ways1[i] * ways2[i] % mod;
			ans = (ans - (temp * (temp - 1)) % mod + mod) % mod;
		}
	}
	for (int i = 0; i < m; ++i) {
		int id = i << 1,
			u = edge[id].from, v = edge[id].to;
		if (dist1[u] > dist1[v]) swap(u, v);
		if (dist1[u] + edge[id].w + dist2[v] == dis && (dist1[u] << 1) < dis && (dist2[v] << 1) < dis) {
			LL temp = ways1[u] * ways2[v] % mod;
			ans = (ans - (temp * (temp - 1)) % mod + mod) % mod;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 16852
import std.stdio, std.string, std.array, std.conv, std.algorithm, std.typecons, std.range, std.container, std.math, std.algorithm.searching, std.functional,std.mathspecial, std.numeric;

void main(){
    auto abc=readln.split.map!(to!int).array;
    auto gcd=gcd(abc[0],abc[1]);
    writeln(abc[2]%gcd==0?"YES":"NO");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long

int const maxi = 4*200005;
ll t[maxi];
vector<ll> dp(200005);

void build(int idx , int l ,int r){
	if(l==r){
		t[idx] = dp[l]; 
		return;
	}
	int mid = (l+r)>>1;

	build(2*idx+1 , l , mid);
	build(2*idx+2 , mid+1 ,r);

	t[idx] = max(t[2*idx+1], t[2*idx+2]);
}

void update(int v, int l , int r, int idx , ll val){
	if(l==r && idx==l){
		t[v] = dp[idx];
		return;
	}
	int mid = (l+r)>>1;
	if(idx<=mid) update(2*v+1, l,mid , idx , val);
	else update(2*v+2 , mid+1, r , idx,val);
	t[v] = max(t[2*v+1] , t[2*v+2]);

}

ll query(int v, int l, int r , int ql , int qh){
	if(r<ql || l > qh) return -1e18;
	if(l==ql && r==qh)return t[v];
	int mid = (l+r) >> 1;
	return max(query(2*v+1, l, mid, ql , min(mid, qh)) , query(2*v+2 , mid+1 , r , max(mid+1,ql) , qh));
}

int main(){
	IOS;
	int n;
	cin >> n;
	ll h[n];
	ll b[n];
	for(int i=0 ; i < n ; ++i){
		cin >> h[i];
	} 
	for(int i=0;i<n ; ++i){
		cin >> b[i];
	}
	//build(0,0,n);

	for(int flower = 0 ; flower<n ; ++flower){
		ll base = query(0,0,n , 0,h[flower] - 1 );
		dp[h[flower]] = b[flower] + base;
		update(0,0,n,h[flower], dp[h[flower]]);
	}

	ll ans = 0;
	for(int i=0; i <= n ; ++i){
		ans = max(dp[i], ans);
	}
	cout << ans << endl;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string A;
    string B;
    cin >> A >> B;
    char C[A.length()];
    char D[B.length()];
    A.copy(C, A.length());
    B.copy(D, B.length());
    sort(C, C+A.length());
    sort(D, D+B.length(), greater<int>());
    rep(i, A.length()) {
        //cout << C[i];
    }
    cout << endl;
    rep(i, A.length()) {
        if (C[i] < D[i]) {
            cout << "Yes" << endl;
            return 0;
        } else if (C[i] > D[i]) {
            cout << "No" << endl;
            return 0;
        }
        
    }
    if (A == B ) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }


    return 0;
}


Measured memory_bytes: 256
import itertools

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

seq = list(range(2, n+1))
ptr = list(itertools.permutations(seq, n-1))

ans = 0
for i in ptr:
    flag2 = True
    for j in range(n-1):
        flag = False
        if j == 0:
            for a,b in ab:
                if (a,b) == (1,i[j]) or (a,b) == (i[j],1):
                    flag = True
                    break
        else:
            for a,b in ab:
                if (a,b) == (i[j], i[j-1]) or (a,b) == (i[j-1], i[j]):
                    flag = True
                    break
        if not flag:
            flag2 = False
            break
    if flag2:
        ans += 1

print(ans)


Measured memory_bytes: 75032
n = int(input())
a = list(map(int, input().split()))

cnt, t = 0, 0
for i in range(1,n):
    if a[i] == a[i - 1] and t == 0:
        continue
    elif a[i] >= a[i - 1] and t >= 0:
        t = 1
    elif a[i] <= a[i - 1] and t <= 0:
        t = -1
    else:
        cnt += 1
        t = 0
else:
    cnt += 1
print(cnt)


Measured memory_bytes: 14252
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;


namespace tes
{
	class contest
	{
		static void Main(string[] args)
		{
			 
            var num = int.Parse(Console.ReadLine());
            var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            int max = input.Max();
            int midCount = input.Length - input.Count(c => c == max);
            Array.Sort(input);
            Array.Reverse(input);
            var tmp = new int[max+1];
            tmp[0] =  max ;
            tmp[tmp.Length - 1] =  max ;

            bool check = true;
            if (input.Count(c => c == max) < 2) check = false; 
            
			int mid = (max + 1) / 2;
            if(max %2 == 1)
            {
                if (input.Count(c => c == mid) > 2) check = false;
            }
            else
            {
                if (input.Count(c => c == mid) > 1) check = false;
            }
           
            
            for (int i = 0; i < input.Length; i++)
            {
               
                int current = input[i];
                if (current == max) continue;
                if (current < (max + 1) / 2)
                {
                    check = false;
                    break;
                }

                if (tmp[current]==0)tmp[current] = current ;
                else if(tmp[max - current]== 0) tmp[max-current] =  current;
                else
                {
					if (tmp.Contains(current)) continue;
					
                    for (int j = 0; j < tmp.Length; j++)
                    {
                        
                        if((tmp[j] != 0 && (tmp[j] + 1 == current)))
                        {
                            break;
                        }

                        if (j == tmp.Length - 1) check = false;
                    }
                }
            }


            if (tmp.Contains(0)) check = false;

            if (!check ) Console.WriteLine("Impossible");
            else Console.WriteLine("Possible");

		}				 
	}
}

Measured memory_bytes: 2904
//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
    int m1, d1, m2, d2;
    cin >> m1 >> d1 >> m2 >> d2;
    if(m1 != m2 && d2 == 1){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	while(true){
		int n; cin>>n;
		if(n==0)break;
		vector<int>s(n); for(auto&&i:s)cin>>i;
		sort(s.begin(),s.end());
		cout<<accumulate(s.begin()+1,s.end()-1,0)/(n-2)<<"\n"s;
	}
}


Measured memory_bytes: 3044
s = input()
t = input()

S, T = len(s), len(t)

dp = [[0] * (T+1) for i in range(S+1)]

for i, SS in enumerate(s):
    for j, TT in enumerate(t):
        if SS == TT:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
while i+1 and j+1:
    if dp[i+1][j+1] == dp[i][j+1]:
        i -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        ans = s[i] + ans
        i -= 1
        j -= 1
print(ans)

Measured memory_bytes: 112476
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;

ll C[2005][2005];
ll dp[100005][13];


int main(){
    int N;
    string S,T;
    cin >> N >> S >> T;
    for(int i=0; i< N; i++){
        cout << S[i] << T[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
#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>
#include "bits/stdc++.h"
#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)
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;
const int MAX = 200001;
const int MOD = 1e+9+7;
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; 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;
}
int main(){
	COMinit();
	ll N,M,K;
	scan(N>>M>>K);
	prin((N+M)*inv[6]%MOD*K%MOD*(K-1)%MOD*COM(N*M,K)%MOD);
	return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
    using namespace std;
     
     
     
    int main(){
    	int n,k;
    	cin >> n >> k;
    	
    	vector<int> v(k);
    	for(int i=0;i<k;i++){
    		cin >> v[i];
    	}
    	if(v.size()==1){
    		cout << v[0]-1 << endl;
    		return 0;
    	}
    	
    	sort(v.begin(),v.end());
    	for(int i=0;i<1000;i++){
    		v[v.size()-1]-=v[v.size()-2];
    		v[v.size()-2]=0;
    		sort(v.begin(),v.end());
    	}
    	
    	cout << max(0,v[v.size()-1]-1) << endl;
    	return 0;
    }

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef array<int,3> A;
vector<A> vs;
int R,C,N;
void push(int x,int y,int i){
	if(x==0){
		vs.push_back(A{{0,y,i}});
	}
	else if(y==C){
		vs.push_back(A{{1,x,i}});
	}
	else if(x==R){
		vs.push_back(A{{2,-y,i}});
	}
	else{
		vs.push_back(A{{3,-x,i}});
	}
}
int main() {
	cin >> R >> C >> N;
	for(int i=0;i<N;i++){
		int x,y,z,w;
		cin >> x >> y >> z >> w;
		if((x==0||x==R||y==0||y==C)&&
			(z==0||z==R||w==0||w==C)){
			push(x,y,i);
			push(z,w,i);
		}
	}
	sort(vs.begin(),vs.end());
	stack<int> st;
	for(int i=0;i<vs.size();i++){
		if(st.size()&&st.top()==vs[i][2]){
			st.pop();
		}
		else{
			st.push(vs[i][2]);
		}
	}
	if(st.size()){
		cout << "NO" << endl;
	}
	else{
		cout << "YES" << endl;
	}

	return 0;
}



Measured memory_bytes: 4852
import java.util.*;

public class Main{
	
	Scanner sc = new Scanner(System.in);
	
	final int N = 3;
	int[][] board;
	String ans = "123456780";
    int count = 0;
    int[] dy = {1, 0, -1, 0};
    int[] dx = {0, 1, 0, -1};
    
	
	Queue<Pazzle> Q = new LinkedList<Pazzle>();
    HashSet<String> H = new HashSet<String>();
	
	class Pazzle{
		int y, x;
		int[][] board;
		Pazzle(int y, int x, int[][] board){
			this.y = y;
			this.x = x;
			this.board = new int[N][N];
			for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { this.board[i][j] = board[i][j]; } }
		}
		
		Pazzle(Pazzle p){
			this.y = p.y;
			this.x = p.x;
			board = new int[N][N];
			for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { board[i][j] = p.board[i][j]; } }
		}
		
		public String getString() {
			String str = "";
			for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { str += Integer.toString(board[i][j]); } }
			return str;
		}
		
		public void swap(int ny, int nx) {
			int tmp = board[y][x];
			board[y][x] = board[ny][nx];
			board[ny][nx] = tmp;
			y = ny;
			x = nx;
		}
		
		public void printBoard() {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) { System.out.print(board[i][j]+" "); }
				System.out.println();
			}
			System.out.println();
		}
	}
	
	public void solve() {
		board = new int[N][N];
		int y = 0, x = 0;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				board[i][j] = sc.nextInt();
				if(board[i][j] == 0) { y = i; x = j; }
			}
		}
		
        Q.add(new Pazzle(y,x,board));
        
        while( !Q.isEmpty() ) {
        		int length = Q.size();
        		for(int i=0; i<length; i++) {
        			Pazzle p = Q.poll();
        			String str = p.getString();
        			if( str.equals(ans) ) { System.out.println(count); return; }
        			H.add(str);
        			
        			for(int j=0; j<4; j++) {
        				int ny = p.y + dy[j];
        				int nx = p.x + dx[j];
        				if(ny>=0 && nx>=0 && ny<N && nx<N) {
        					Pazzle np = new Pazzle(p);
        					np.swap(ny, nx);
        					if( H.contains( np.getString() ) ) { continue; }
        					Q.add(np);
        				}
        			}
        		}
        		count++;
        }
	}
	
	public static void main(String[] args) {
		Main obj = new Main();
		obj.solve();
	}
}


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

int main() {
  int N, A, B, ans = 0, nsum, n;
  cin >> N >> A >> B;
  for(int i = 1; i <= N; i++) {
    n = i;
    nsum = 0;
    while(n > 0) {
      nsum += (n % 10);
      n /= 10;
    }
    if((A <= nsum) && (nsum <= B)){
      ans += i;
    }
  }
  cout << ans << endl;
}


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


int main()
{
	//freopen("input16.txt","r",stdin);freopen("output16.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	int h,w,i;
	string a;
	cin>>h>>w;
	for (i=0;i<h;i++){
		cin>>a;
		cout<<a<<"\n"<<a<<"\n";
	}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace abc171_b
{
  class Program
  {
    static void Main(string[] args)
    {
      var N = CIn.ReadInt();
      var K = CIn.ReadInt();
      var p = CIn.ReadIntArray(N);

      Array.Sort(p);

      var ans = 0;

      for (int i = 0; i < K; i++)
      {
        ans += p[i];
      }

      Console.WriteLine(ans);
    }
  }

  static class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(int n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(int n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(int n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(int n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }

    public static char[,] ReadCharMatrix(int h, int w)
    {
      var array = new char[h, w];
      for (var i = 0; i < h; i++)
      {
        var l = Console.ReadLine().ToCharArray();
        for (var j = 0; j < w; j++)
        {
          array[i, j] = l[j];
        }
      }
      return array;
    }
  }
}


Measured memory_bytes: 28292
// B - Around Square
#include<iostream>
using namespace std;
int main()
{
	int input;
	cin >> input;

	int cnt = -1;
	int result, result2;
	while(result <= input)
	{
		result2 = result;
		
		++cnt;
		result = cnt * cnt;
	}
	cout << result2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
#define Max(a) (*max_element(ALL(a)))
#define Min(a) (*min_element(ALL(a)))
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;cin>>s;
  for(auto c:s){
    if(c == '?')cout<<'D';
    else cout<<c;
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 3788
/**
 *   author: malviyanshiv
 *   created: 27 July 2019  17:18:12
**/

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for(int i = a; i < b; i++)
#define RREP(i, a, b) for(int i = a-1; i >= b; i--)
#define FORE(a) for(auto ele : a )
#define ALL(a) begin(a), end(a)
#define RPB(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define PB push_back
#define MP make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define LINF 2000000000000000007
#define F first
#define S second
#define TC int t; cin >> t; while(t--)
#define SET(a,b) memset(a,b,sizeof(a))

#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif

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


void optimizeIO(){
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
}

int main(){
	optimizeIO();

	int a, b;
	cin >> a >> b;
	int c = abs(a+b);
	if( c&1 )
		cout << "IMPOSSIBLE" << endl;
	else
		cout << c/2 << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int a[N];
int n;

int main() {
   // freopen("rd.txt", "r", stdin);
   // freopen("ans.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    ll ans = 0;
    int temp = INT_MAX;
    for (int i = 1; i <= n-1; i++) {
        if (a[i] < 0) {
            a[i+1] = -1 * a[i+1];
            a[i] = -1 * a[i];
        }
        ans = ans + 1LL * abs(a[i]);
       //temp = min(temp, abs(a[i]));
    }
   // cout << ans << " " << temp << endl;
   // temp = min(temp, abs(a[n]));
    temp = *min_element(a+1, a+n);
    if (a[n] < 0) {
       if (abs(a[n]) < temp) ans = ans + 1LL * a[n];
       else ans = ans - 1LL * a[n] - 2LL * temp;
    }
    else ans = ans + 1LL * a[n];
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 640
// She is Pretty pretty!
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 1e6 + 100;
struct Node {
    ll w, s, v;
} a[N];
int dp[N];
bool cmp(Node a, Node b) { return a.w + a.s < b.w + b.s; }
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].w >> a[i].s >> a[i].v;
    }
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        for (int j = 3e4; j >= a[i].w; j--) {
            if (a[i].s + a[i].w >= j) {
                dp[j] = max(dp[j], dp[j - a[i].w] + a[i].v);
            }
        }
    }
    cout << *max_element(dp + 1, dp + 30000) << endl;
    return 0;
}

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

#define PI 3.14159265359
#define eps 1e-8
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORN(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,n) FOR(i,0,n)
typedef long long int ll;
const int INF = 1<<29;
typedef long long ll;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

double tick() { 
	static clock_t oldticks;
	clock_t newticks = clock();
	double diff = 1.0 * (newticks - oldticks) / CLOCKS_PER_SEC; 
	oldticks = newticks;
	return diff;
}

inline int toInt(string s){
	return atoi(s.c_str());
}

inline int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

inline int lcm(int a,int b){
	return a*(b/gcd(a,b));
}

inline bool isPrime(int n){
	ll j;
	j=sqrt(n);

	if(n<2)
		return 0;
	for(int i=2;i<=j;i++){
		if(n%i==0)
			return false;
	}
	return true;
}

inline long long nCr(long long n,long long m){
    ll res=1;
    if(n-m < m) m=n-m;

    for(ll i=1;i<=m;i++,n--){
        res=res*n;
        res=res/i;
    }
    return res;
}

string s;
int n;

int main(){
	ios_base::sync_with_stdio(false); //Fast I/O
	cin.tie(NULL);
	//freopen("in.txt","r",stdin);
	//freopen("output.txt","w",stdout);	

	cin >> s;
	cin >> n;

	for(int i=0;i<(int)s.length();i+=n){
		cout << s[i];
	}

    //cerr << tick();

	return 0;
	
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back 
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long
int rd()
{
    int sum = 0;char c = getchar();bool flag = true;
    while(c < '0' || c > '9') {if(c == '-') flag = false;c = getchar();}
    while(c >= '0' && c <= '9') sum = sum * 10 + c - 48,c = getchar();
    if(flag) return sum;
    else return -sum;
}
int n,l;
int a[101000];
int main()
{
	n = rd();l = rd();
	rep(i,1,n) a[i] = rd();
	int k1,k2;
	bool ck = false;
	rep(i,1,n) if(a[i]>=l) {ck = true;k1 = i;break;}
    if(ck)
    {
    	printf("Possible\n");
    	repp(i,n-1,k1) printf("%d\n",i);
    	rep(i,1,k1-1) printf("%d\n",i);
    	return 0;
    }
    rep(i,1,n-1) if(a[i]+a[i+1]>= l){ck = true;k1 = i;k2 = i+1;break;}
    if(ck)
    {
    	printf("Possible\n");
    	repp(i,n-1,k2) printf("%d\n",i);
    	rep(i,1,k1-1) printf("%d\n",i);
    	printf("%d\n",k1);
    	return 0;
    }
    else printf("Impossible");
}

Measured memory_bytes: 1152
#include<iostream>


int main() {

	int K, S;
	std::cin >> K >> S;

	int ans = 0;

	for (int x = 0; x <= K; x++) {
		for (int y = 0; y <= K; y++) {
			if (S - x - y >= 0 && S - x - y <= K) ans += 1;
			}
		}
	
		std::cout << ans << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define all(a)  a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define mod 1000000007
#define _for(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

using namespace std;

int main(){
   int N, M;
   cin >> N >> M;
   vector<string> s;
   string t;
   for(int n = 1; n <= N; ++n){
      cin >> t;
      s.pb(t);
   }
   sort(all(s));
   for(int n = 0; n < s.sz; ++n){
      cout << s[n];
   }
   cout << endl;
   return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n;
  cin>>n;
  if(n%2==0) cout<<n/2;
  else cout<<n/2+1;
  return 0;
}

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

int main(){
	while(1){
		int W, H;
		char s[100];
		char map[50][50];
		int i;
		int count = 0;

		scanf("%d %d\n", &W, &H);
		// printf("%d,%d\n", W, H);
		if((W | H) == 0) break;

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

			for(j = 0; j < W + 2; j++){
				map[i][j] = -1;
			}
		}

		for(i = 0; i < H; i++){
			int j;

			/* fgets(s, 100, stdin); */
			for(j = 0;j < W; j++){
				int end = 0;
				char c;

				c = getchar();

				switch(c){
				case '.':
					map[i + 1][j + 1] = 0;
					break;
				case '#':
					map[i + 1][j + 1] = -1;
					break;
				case '@':
					map[i + 1][j + 1] = 1;
					break;
				default:
					end = 1;
					break;
				}

				if(end) break;
			}
			getchar();
		}

		while(1){
			int end = 0;

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

				for(j = 0; j < W + 2; j++){
					if(map[i][j] == 1){
						if(map[i + 1][j] == 0) map[i + 1][j] = end = 1;
						if(map[i - 1][j] == 0) map[i - 1][j] = end = 1;
						if(map[i][j + 1] == 0) map[i][j + 1] = end = 1;
						if(map[i][j - 1] == 0) map[i][j - 1] = end = 1;
					}
				}
			}

			if(end == 0) break;
		}

		for(i = 1; i < H + 1; i++){
			int j;

			for(j = 1; j < W + 1; j++){
				if(map[i][j] == 1) count++;
			}
		}

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

	exit(EXIT_SUCCESS);
}

Measured memory_bytes: 608
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;

}

ll n;
vector<vector<vector<double>>> dp(301, vector<vector<double>>(301, vector<double>(301, -1.0)));

double solve(ll i, ll j, ll k) {
	if (dp[i][j][k] >= 0.0) {
		return dp[i][j][k];
	}

	if (i == 0 && j == 0 && k == 0) {
		return 0.0;
	}

	double res = 0.0;

	if (i > 0) {
		res += solve(i - 1, j, k) * i;
	}
	if (j > 0) {
		res += solve(i + 1, j - 1, k) * j;
	}
	if (k > 0) {
		res += solve(i, j + 1, k - 1) * k;
	}
	res += n;
	res = res / (double)(i + j + k);
	dp[i][j][k] = res;

	return res;
}

signed main() {
	ll a;

	cin >> n;

	vector<ll> x(4, 0);

	REP(i, n) {
		cin >> a;
		x[a]++;
	}

	cout << setprecision(10) << scientific << solve(x[1], x[2], x[3]) << endl;
}

Measured memory_bytes: 216960
#include<bits/stdc++.h>
#define st first
#define nd second

using ll = long long ;
using namespace std;
using pii = pair<int,int>;
int dp[150][12];
pii rec(int k, int lev){
	dp[lev][0] = dp[lev - 1][0] + dp[lev - 1][1];
	for(int i = 1; i <= 9; i++){
		for(int j = -1; j <= 1; j++){
			if(k <= dp[lev - 1][i + j]){
				printf("%d",i);
				return {i +j, k};
			}
			k -= dp[lev - 1][i + j];
			dp[lev][i] += dp[lev - 1][i + j];
		}
	}
	pii ret = rec(k, lev + 1);
	printf("%d", ret.st);
	for(int i = ret.st - 1; i <= ret.st + 1; i++){
		if(ret.nd <= dp[lev - 1][i]){
			return {i, ret.nd};
		}
		ret.nd -= dp[lev - 1][i];
	}


}
int main(){
	int k;
	scanf("%d", &k);
	if(k <= 9) return !printf("%d",k);
	for(int i = 0; i < 10; i++) dp[1][i] = 1;
	k -= 9;
	pii p = rec(k, 2);

	printf("%d",p.st);

}

Measured memory_bytes: 256
var i : integer;
    s : char;
begin
  for i := 1 to 5 do begin
    read(s)
  end;
  read(s);
  if s = '1' then writeln('TBD')
  else begin
    read(s);
    i := Ord(s) - 48;
    if i < 5 then writeln('Heisei') else writeln('TBD')
  end
end.

Measured memory_bytes: 128
# Author: cr4zjh0bp
# Created: Tue Mar 24 00:01:43 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import Counter

n = ni()
a = na()
c = Counter(a)
m = list(c.items())
m.sort(reverse=True)
xy = [0] * 2
i = 0
flag = False
for k, v in m:
    if v >= 4:
        if i != 0:
            print(xy[0] * k)
        else:
            print(k * k)
        flag = True
        break
    elif v >= 2:
        xy[i] = k
        i += 1
        if i == 2:
            print(xy[0] * xy[1])
            flag = True
            break
if not flag:
    print(0)

Measured memory_bytes: 21540
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

class UnionFindTree():
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
        self.huben = N*(N-1)//2
  
    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i]) 
            self.parent[i] = group
        return group
      
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]: # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px
                
            self.parent[py] = px
            self.huben -= self.size[px] * self.size[py]
            self.size[px] += self.size[py]

    def getsize(self, x):
        return self.size[self.find(x)]
    
    def groups(self, index1=True):
        return set([self.find(i) for i in range(0+index1, N+index1)])

N, M = inpl()
A, B = [0]*M, [0]*M

for i in range(M):
    A[i], B[i] = inpl()

ans = []
UFT = UnionFindTree(N)

for i in range(M-1, -1, -1):
    ans.append(UFT.huben)
    UFT.unite(A[i], B[i])

print(*ans[::-1], sep="\n")

Measured memory_bytes: 85080
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[303][303][303];
ll mod = 1e9 + 7;
int main() {
  int n, m;
  while(cin >> n >> m) {
    memset(dp, 0, sizeof(dp));
    dp[0][1][1] = 1;
    for(int i = 0; i < m; ++i) {
      for(int j = 1; j <= n; ++j) {
        for(int k = 1; k <= j; ++k) {
          (dp[i+1][j][j] += dp[i][j][k]*k%mod) %= mod; // 頂点1と強連結な頂点に移動
          (dp[i+1][j][k] += dp[i][j][k]*(j-k)) %= mod; // 頂点1から片方向連結な頂点に移動
          (dp[i+1][j+1][k] += dp[i][j][k]*(n-j)) %= mod; // 頂点1と非連結な頂点に移動
        }
      }
    }
    cout << dp[m][n][n] << endl;
  }

  return 0;
}


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

int main() {
    int N;  
    cin >> N;
    int t[114514], x[114514], y[114514]; 
    for(int i = 1; i <= N; ++i){
    cin >> t[i] >> x[i] >> y[i];
    }
    string ans = "Yes"; 
    for(int i = 1; i <= N; ++i){
    if (abs(x[i] + y[i] - x[i-1] - y[i-1]) % 2 
        != (t[i] - t[i-1]) % 2 ||
         abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]) > t[i] - t[i-1])
    {ans = "No"; 
     break; 
     }
    }
     cout << ans << endl;
}


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

typedef long long ll;
const ll inf = 1e15;

int main() {
    ll n;
    cin>>n;
    ll minv = inf;
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ll tmp;
        cin>>tmp;
        if (tmp <= minv) minv = tmp,ans++;
    } 
    cout<<ans<<"\n";
}

Measured memory_bytes: 256
use v5.18; # strict say state
use warnings;
use List::Util qw(reduce first max min sum0);

chomp (my $s = <STDIN>);
if (substr($s,2,1) eq substr($s,3,1) && substr($s,4,1) eq substr($s,5,1)) {
  say "Yes";
} else {
  say "No";
}

Measured memory_bytes: 768
N = int(input())
P = list(map(int, input().split()))

sort = [i for i in range(1, N+1)]
t = 0
for i, n in enumerate(sort):
  if  P[i] != n and t < 2:
    t +=1
    continue
  elif P[i] != n and t > 1:
    print("NO")
    quit()
print("YES")


Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

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

    cout << min({abs(a / 2 * b * c - (a - a / 2) * b * c),
                 abs(b / 2 * a * c - (b - b / 2) * a * c),
                 abs(c / 2 * b * a - (c - c / 2) * b * a)})
         << endl;
    ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int INF=1e9+7;
int main(){
  int N;cin>>N;
  vector<long long>A(60);
  for(int i=0;i<N;i++){
    long long a;cin>>a;
    for(int j=0;j<60;j++)
      if(a&(1ll<<j))A[j]++;
  }
  long long ans=0;long long count=1;
  for(int i=0;i<60;i++){
    ans+=(A[i]*(N-A[i]))%INF*count;
    ans%=INF;
    count=count*2%INF;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3628
#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 n;
  cin >> n;
  vector<int> x(n);
  vector<int> y(n);
  vector<int> a(n);
  vector<int> b(n);
  rep(i,n){
    cin >> x[i] >> y[i];
    a[i]=x[i]+y[i];
    b[i]=x[i]-y[i];
  }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  int res = a[a.size()-1]-a[0];
  res = max(res,b[b.size()-1]-b[0]);
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 6384
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <map>

int main() {
  int A, B, C, X, Y;
  scanf("%d %d %d %d %d", &A, &B, &C, &X, &Y);

  int res=A*X+B*Y;
  res = std::min(res, std::max(X, Y)*2*C);
  if (X < Y) {
    res = std::min(res, X*2*C+(Y-X)*B);
  } else {
    res = std::min(res, Y*2*C+(X-Y)*A);
  }
  printf("%d\n", res);
}


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

int main()
{
	int n,i,s=0;
	cin>>n;
	int a[n],b[n-1];
	for(i=0;i<n-1;i++) cin>>b[i];
	for(i=0;i<n-1;i++)
	{
		a[i]=(i==0 ? b[i] : min(a[i],b[i]));
		s+=a[i];
		a[i+1]=b[i];
	}
	s+=a[n-1];
	
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
import sys
read = sys.stdin.read


D = int(input())
CS = np.array(read().split(), np.int32)
C = CS[:26]
S = CS[26:].reshape((-1, 26))
del CS

last = np.zeros((26, ))
ans = []

def getContestType_at_d(d):
    s = -10000000
    for i in range(26):
        mask = np.ones((26, ))
        mask[i] = 0
        tmp = S[d][i] - np.sum(C * (d + 1 - last) * mask)
        if s < tmp:
            s = tmp
            t = i

    last[t] = d + 1

    return t + 1, s
#score = 0
for d in range(D):
    t, _ = getContestType_at_d(d)
    ans.append(t)
    #score += s
    #print('score:', score)


print('\n'.join(map(str, ans)))

Measured memory_bytes: 27512
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll a,v,b,w,t;
    cin>>a>>v>>b>>w>>t;
   // bool f=false;
    int dis=abs(a-b);
    int par=(v-w);
    if(par*t>=dis){
        cout<<"YES";
    }
    else
        cout<<"NO";
}



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

using std::pair;
using std::vector;
using std::string;

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

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

string procStatus() {
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int N = 100000;

int n, k;
int a[N + 5];

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    read(n), read(k);
    for(int i = 1; i <= n; ++i) read(a[i]);

    if(a[1] >= 0) return printf("%d\n", a[k]), 0;
    if(a[n] <= 0) return printf("%d\n", -a[n-k+1]), 0;

    int ans = INT_MAX;
    for(int i = 1; i + k - 1 <= n; ++i) if(a[i] <= 0 && a[i + k - 1] >= 0) {
        chkmin(ans, -a[i] + a[i + k - 1] - a[i]);
        chkmin(ans, a[i + k - 1] * 2 - a[i]);
    }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 640