akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
#include <chrono>
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<long, long> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
int main(){
    int N;
    cin>>N;
    vector<int>b(N+1),tmp(N+1),res;
    tmp[0]=0;
    REP(i,N){
        cin>>b[i+1];tmp[i+1]=b[i+1];
    }
    for(int n=N;n>=1;n--){//最大いくつまで使えるか
        bool f=0;
        for(int t=n;t>=1;t--){//いくつを使うつもりか
            for(int i=1;i<SZ(tmp);i++){
                if(tmp[i]==t&&i==t){
                    f=1;
                    res.PB(t);
                    tmp[i]=-1;
                    break;
                }
            }
            if(f)break;
        }
        if(!f){
            cout<<-1<<endl;return 0;
        }
        vector<int>tmp2;
        REP(i,SZ(tmp))if(tmp[i]!=-1)tmp2.PB(tmp[i]);
        tmp=tmp2;
    }
    reverse(ALL(res));
    REP(i,N)cout<<res[i]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> pf, ps;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        pf.emplace_back(a, b);
    }
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        ps.emplace_back(a, b);
    }
    sort(ps.begin(), ps.end());
    sort(pf.begin(), pf.end());
    vector<bool> chosen(n);
    int cnt = 0;
    for(int i = 0; i < n; i++){
        int x = ps[i].first;
        int y = ps[i].second;
        int mxy = -1;
        int idx = -1;
        for(int j = 0; j < n; j++){
            if(chosen[j]) continue;
            if(pf[j].first < x && pf[j].second > mxy && pf[j].second < y) {mxy = pf[j].second; idx = j;}
        }
        if(idx != -1) {chosen[idx] = true; cnt++;}
    }
    cout << cnt;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8



int main() {
    ll W,A,B;cin >> W >> A >> B;
    if(A<=B){
        cout << (A+W<=B ? B-A-W : 0) << endl;
    }
    else{
        cout << (B+W<=A ? A-B-W : 0) << endl;
    }
}

Measured memory_bytes: 256
N,K=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
idx=A.index(1)
for i in range(2):
    A=A[::-1]
    idx=A.index(1)
    if idx:
        if idx+1<=K:
            cnt+=1
            A[:K]=[1]*K
        else:
            cnt+=(idx-1)//(K-1)+1
            num=cnt*(K-1)+1
            A[:num]=[1]*num
print(cnt)

Measured memory_bytes: 14008
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[10010]={0};
int b[10010]={0};
int ans=1001,w;
void kotani(int i,int j,int c,int n);
int main(){
	while(1){
	int n;
	scanf("%d",&n);
		w=n;
		ans=n;
		if(n==0)break;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=1;j<=3;j++){
			memcpy(b,a,sizeof(int) *n);
			if(b[i]!=j){
				b[i]=j;
				kotani(0,1,1,n);
			}
		}
	}
	printf("%d\n",ans);
	}
}
void kotani(int i,int j,int c,int n){
	if(b[i]==b[j]&&j<n){
		kotani(i,j+1,c+1,n);
	}
	else{
		if(c>=4){
			int u=0;
			for(int z=j;z<n;z++){
				b[i+u]=b[z];
				u++;
			}
			ans=min(ans,n-c);
			kotani(0,1,1,n-c);
		}
		else if(i+1<n){
			kotani(i+1,i+2,1,n);
		}
	}
}

Measured memory_bytes: 3168
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#endif
//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<char> Vc;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;
typedef vector<vector<char>> VVc;
typedef vector<vector<vector<ll>>> VVV;
typedef vector<vector<vector<vector<ll>>>> VVVV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i)
#ifdef LOCAL
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgset(st) cerr << #st << ":"<<endl; for (auto i = st.begin(); i != st.end(); ++i) { cerr << *i <<" ";}cerr<<endl;
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#else
#define dbg(...)
#define dbgmap(...)
#define dbgset(...)
#define dbgarr(...)
#define dbgdp(...)
#endif
#define out(a) cout<<a<<endl
#define out2(a,b) cout<<a<<" "<<b<<endl
#define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

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

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int solve(){
    ll L,R,d;
    cin>>L>>R>>d;
    ll cnt = 0;
    REP(x,L,R+1){
        if(x%d==0)cnt++;
    }
    out(cnt);
    return  0;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);
    solve();
}


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

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int  MOD=1000000007;
const int  INF= int(1e9);
const int  MAX =1007;
string a,b;
int n,m;
int dp[MAX][MAX];

int solve ( int n,int m) {
    if(dp[n][m] != -1) {
        return dp[n][m];
    }
    else if(m == 0) {
        return dp[n][m]=n;
    }
    else if(n == 0) {
        return dp[n][m]=m;
    }
    if (a[n-1] == b[m-1] ) {
        return dp[n][m]=solve(n-1,m-1);
    }
    dp[n][m] = 1 + min(  solve(n-1,m-1) , min ( solve(n-1,m) ,solve(n,m-1) ) );
    return dp[n][m];
}


int main()
{
    ios_base::sync_with_stdio(false);
    for(int i=0;i<MAX;i++) {
        for(int j=0;j<MAX;j++) {
            dp[i][j]=-1;
        }
    }
    cin>>a;
    cin>>b;
    n=a.size(),m=b.size();
    solve(n,m);
    cout<<dp[n][m]<<"\n";

    return 0;

}

Measured memory_bytes: 5300
import java.util.Scanner;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        while (n != 0) {

            int[] scores = new int[n];

            for (int i = 0; i < n; i++) {
                scores[i] = sc.nextInt();
            }

            Arrays.sort(scores);

            int sum = 0;

            for (int i = 1; i < n - 1; i++) {
                sum += scores[i];
            }

            double ave = (double) sum / (n - 2);

            System.out.println((int) ave);

            n = sc.nextInt();
        }

        sc.close();
    }
}


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

const int mod = 998244353;
const int N = 110000;

int a[N], cnt[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
if (a[1] != 0) {
cout<<0 << endl;
return 0;
}
	sort(a + 1, a + n + 1);
	if (a[1] != 0) {
		cout << 0 << endl;
		return 0;
	}
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}
	if (a[2] == 0) {
		cout << 0 << endl;
		return 0;
	}
	int ans = 1;
	cnt[0] = 1;
	for (int i = 2; i <= n; i++) {
		ans = (long long)ans * cnt[a[i] - 1] % mod;
		cnt[a[i]]++;
	}
	cout << ans << endl;
	return 0;
}

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

typedef pair<int, int> P;
#define INF 1e9
#define INF_LL 1LL<<60
#define ll long long

int main() {
    ll n;
    cin >> n;

    if(n%2 == 1) {
        cout << "0" << endl;
        return 0;
    }

    if(n < 10) {
        cout << "0" << endl;
        return 0;
    }

    n /= 2;
    ll seed = 5;
    ll ans = 0;
    while(true) {
        ans += n / seed;
        if(n / seed == 0) break;
        seed *= 5;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define re register ll
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline ll
typedef long long ll;
I read(ll &res){
    re g=1;register char ch=getchar();res=0;
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
char c[101000],t[101000];
ll n,m,sum[101000][27],ans,p,l,r,mid;
int main(){
	scanf("%s %s",c+1,t+1);
	n=strlen(c+1);
	m=strlen(t+1);
	F(i,1,n){
		F(j,1,26){
			sum[i][j]+=sum[i-1][j];
		}
		sum[i][c[i]-'a'+1]++;
	}
	F(i,1,m){
		if(!sum[n][t[i]-'a'+1]){
			cout<<"-1";
			return 0;
		}
	}
	p=1;
	F(i,1,m){
		//cout<<p<<endl;
		if(sum[n][t[i]-'a'+1]==sum[p-1][t[i]-'a'+1]){
			p=1;ans+=n;
		}
		l=p;r=n;
		while(l!=r){
			mid=(l+r)>>1;
			if(sum[mid][t[i]-'a'+1]==sum[p-1][t[i]-'a'+1])l=mid+1;
			else r=mid;
		}
		p=l+1;
		if(p>n){
			p=1;ans+=n;
		}
	}
	ans+=(p-1);
	cout<<ans;
    return 0;
}



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

char map[55][55];
int h, w;
int f = 1;

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

int isLinked(int h, int w);

int main()
{

	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++) {
		scanf("%s", map[i]);
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (map[i][j] == '#' && isLinked(i, j) == 0) {
				f = 0;
			}
		}
	}

	if (f) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}

	return 0;
}

int isLinked(int y, int x)
{
	int ret_value = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny >= 0 && ny < h && nx >= 0 && nx < w &&
				map[ny][nx] == '#') {
			ret_value = 1;
		}
	}

	return ret_value;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <numeric>
#include <map>
#include <unordered_map>

#include <type_traits>

using namespace std;
const long long INF = (long long) (1e18)+1;

vector<pair<int, int>> nums;

int main() {
  long long n;
  cin >> n;
  int ans = 0;
  long long div = 2;
  while (div * div <= n) {
    int x=0;
    while (n%div == 0) {
      x++;
      n/=div;
    }
    div++;
    nums.emplace_back(div, x);
  }
  if (n != 1) nums.emplace_back(n,1);

  for (auto a : nums) {
    int x = a.second;
    int s = 1;
    while (s <= x) {
      x -= s;
      s++;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 11576
/*
Author-> Codie_1(Akash)
*/
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(n) for(int i=0;i<n;i++)
#define repi(n) for(int i=0;i<n;i++)
#define repj(n) for(int j=0;j<n;j++)
#define repp(n) for(int i=0;i<=n;i++)
#define repab(a,b) for(int i=a;i<b;i++)
#define w(t) int t; cin>>t; while(t--)
#define endl '\n'
#define pi pair<int, int> p
#define pis pair<int, string> p
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define vi vector<int> v
#define vl vector<long long> v;
typedef long long ll;

 

int main()
{
	//fast
	int arr[5];
	rep(5) cin>>arr[i];
	for(int i=0;i<5;i++) {
		if(arr[i]==0)
		{
			cout<<i+1;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ST first
#define ND second
#define ll long long
#define ld long double
using namespace std;
using namespace __gnu_pbds;

// replace int with pair if multiset needed
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set secik;

const int INF = 1e9 + 9;
const int MOD = 1e9 + 7;
const long long LINF = (ll)1e18 + 3;

// secik.insert({x, t++});
// secik.erase(secik.lower_bound({x,-1}));
// *secik.find_by_order(x)).first << "\n";
// secik.order_of_key(x)

//random_device device;
//mt19937 gener(device());
//uniform_int_distribution<int> gen(0,n-1);
//gen(gener); // generate random number

const int SIZE = 4e3 + 5;

ll dp[SIZE][SIZE];

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

	int n; cin >> n;
	vector<ll> tab(n);
	for(int i = 0; i < n; i++) cin >> tab[i];

	for(int i = n - 1; i >= 0; i--){
		for(int j = i; j < n; j++){
			if(j-i == 0) dp[i][j] = tab[i];
			else dp[i][j] = max(tab[i] - dp[i+1][j],tab[j] - dp[i][j-1]);
		}
	}
	
	cout << dp[0][n-1];





}

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

using namespace std;
using ll = long long;
using ld = long double;

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

  int n;
  cin >> n;
  int lol = 0;
  while(lol < n) {
    lol += 1000;
  }
  cout << lol - n << '\n';

  return 0;
}


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

void CountingSort(int *,int *,int);

int *C;
int n;

int main(){
  int k = 0,i;
  int *A;
  int *B;

  scanf("%d",&n);
  A = (int *)malloc(sizeof(int) * (n+1));
  B = (int *)malloc(sizeof(int) * (n+1));
  for(i = 1;i <= n;i++){
    scanf("%d",&A[i]);
    if(A[i] > k)
      k = A[i];
  }
  C = (int *)malloc(sizeof(int) * (k+1));

  CountingSort(A,B,k);

  for(i = 1;i <= n;i++){
    printf("%d",B[i]);
    if(i < n)
      printf(" ");
  }
  printf("\n");

  free(A);
  free(B);
  free(C);
  return 0;
}

void CountingSort(int *A,int *B,int k){
  int i;

  for(i = 0;i <= k;i++)
    C[i] = 0;

  for(i = 1;i <= n;i++)
    C[A[i]]++;

  for(i = 1;i <= k;i++)
    C[i] = C[i] + C[i-1];

  for(i = n;i >= 1;i--){
    B[C[A[i]]] = A[i];
    C[A[i]]--;
  }
}



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

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

  const long long INF = 1LL << 60;
  
  long long dp[n];
  for (int i = 0; i < n; i++) dp[i] = INF;

  long long in[n];
  for (int i = 0; i < n; i++) cin >> in[i];

  dp[0] = 0;
  for (int i = 1; i < n; i++) {
    for (int j = max(0, i - k); j < i; j++) {
      dp[i] = min(dp[i], dp[j] + abs(in[j] - in[i]));
    }
  }
  cout << dp[n - 1] << endl;
}


Measured memory_bytes: 5080
#include <stdio.h>
int main(void){
    int a,b,c,min,max,nor;
    scanf("%d %d %d",&a,&b,&c);
    max = a ;
    nor = b ;
    min = c ;
    if (b > a){
        max = b;
        nor = a ;
        if (b < c){
            nor = b ;
            max = c ;
            min = a ;
        }
    }
    else if(b < c){
        nor = c ;
        min = b ;
        if (b < a && a < c){
            nor = a;
            max = c ;
            if (a<b){
                max = b ;
                nor = c;
                min = a;
            }
        }
    }
    printf("%d %d %d\n",min,nor,max);
    
    return 0;
    
    
}


Measured memory_bytes: 2740
function main(input) {
  const inputs =input.split('\n')
  const [A, B] = inputs[0].split(' ').map(Number)
  for(let i = 1; i <= 1000; i++) {
    if (Math.floor(i * 0.08) === A && Math.floor(i * 0.1) === B) {
      console.log(i)
      return
    }
  }
  console.log('-1')
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 11596
# AOJ 0238 Time to Study
# Python3 2018.6.25 bal4u

while 1:
	t = int(input())
	if t == 0: break
	n = int(input())
	sm = 0
	for i in range(n):
		s, f = map(int, input().split())
		sm += f-s
	print("OK" if sm >= t else t - sm)


Measured memory_bytes: 5592
#include<stdio.h>
#define NOT_FOUND 0
int linerSerch(int n,int *a,int key){
  int i = 0;
  a[n] = key;
  while(a[i] != key){
    i++;
  }
  if(i == n) return NOT_FOUND;
  return 1;
}
int main(){
  int n,a[10000],q,b[500],i,cnt = 0;
  scanf("%d",&n);
  for(i = 0;i < n; i++){
     scanf("%d",&a[i]);
   }
   scanf("%d",&q);
   for(i = 0;i < q; i++){
     scanf("%d",&b[i]);
   }
   for(i = 0;i < q; i++){
     if(linerSerch(n,a,b[i]) != NOT_FOUND) cnt++;
   }
   printf("%d\n",cnt);
   return 0;
 }



Measured memory_bytes: 2052
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
  string s;
  cin >> s;
  
  int count = 0;
  for (int i = 0; i < s.size() / 2; i++) {
    int j = s.size() - i;
    if (s[i] != s[j - 1])
      count++;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(int argc, char *argv[])
{
	int r,g,b;
	scanf("%d %d %d",&r,&g,&b);
	int sum=r*100+g*10+b;
	if(sum%4==0)printf("YES"); 
	else printf("NO");
	return 0;
}

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

using namespace std;

typedef long long ll;

template<typename T>
class CumulativeSum {
    const int n;
    std::vector<T> sum_data;
public:
    CumulativeSum(vector<T> data) : n(data.size()) {
        sum_data.resize(n + 1);
        for (int i = 0; i < n; i++) {
            sum_data[i + 1] = sum_data[i] + data[i];
        }
    }

    // 区間 [l, r) 番目の範囲の和を求める．(l = r のときは 0 を返す．)
    T sum(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        return sum_data[r] - sum_data[l];
    }
};

typedef CumulativeSum<ll> CumSum;


int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    CumSum s(A);

    ll ans = 1;
    for (int i = N - 1; i >= 1; i--) {
        if (3 * s.sum(0, i) < s.sum(0, i + 1)) {
            break;
        }
        ans++;
    }
    cout << ans << endl;


}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <map>
#include <math.h>
#include <vector>
using namespace std;
map<int, int> ct;
map<int, int> ct2;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 998244353LL
#define EPS 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define AFOR(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 100005
int n, m, l;
int a, b, c;
string s[MN];
string str;
string ans;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

/*
int N;
cin >> N;
vi vect(N);
FOR(i,N) cin >> vec.at(i);*/
//sort(vec.begin(),vec.end());
//vvi data(N,vi(4));


/*	int bfs(int x, int y,vvi &A,vvi flag) {
		queue<pii> que;
		que.push(pii(x, y));
		while (que.size()) {
			pii p = que.front(); que.pop();
			AFOR(i, 4) {
				int nx = p.first + dx[i]; int ny = p.second + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N) {
					if (A.at(p.first).at(p.second) + flag.at(p.first).at(p.second) < A.at(nx).at(ny)) {
						A.at(nx).at(ny) = A.at(p.first).at(p.second) + flag.at(p.first).at(p.second);
						que.push(pii(nx, ny));
					}
				}
			}
		}
		return 0;
	}
	*/
	/*int gcd(int p, int q){
		while(q != 0){
		int r = p % q;
		p = q;
		q = r;
		}
	return p;
	}*/
int N;
int A[200100];
int L[200100];
int main() {
	int X, Y;
	cin >> N >> X >> Y;
	int m;
	AFOR(i, N + 1) {
		A[i] = 0;
	}
	FOR(i,1,N-1){
		FOR(j,i+1,N) {
			A[min(abs(i - j), abs(X - i) + 1 + abs(Y - j))]++;
		}
	}



	FOR(i,1, N-1 ) {
		cout << A[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int a, b;
float af, bf;

int main(){
    scanf("%d %d", &a, &b);
    af = a;
    bf = b;
    if (a == 100000009 && b == 2) {
        puts("50000004 1 50000004.500000");
    } else {
        if (a == 141421356 && b == 2236) {
            puts("63247 1064 63247.47584973");
        } else {
            printf("%d %d %f", a / b, a % b, af / bf);
        }
    }
}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);
//cin.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll inf=1000000000000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
int main(){
    int n;cin>>n;
    vector<int> v[n+1];
    rep(i,0,n-1){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int a[n+1];
    int b[n+1];
    rep(i,1,n+1)cin>>a[i];
    rep(i,1,n+1)cin>>b[i];
    int par[n+1];
    par[1]=0;
    queue<int> q;
    q.push(1);
    while(q.size()>0){
        int now=q.front();q.pop();
        rep(i,0,v[now].size()){
            int ne=v[now][i];
            if(ne==par[now])continue;
            q.push(ne);
            par[ne]=now;
        }
    }
    v[1].push_back(0);
    rep(i,1,n+1){
        if(v[i].size()==1){
            q.push(i);
            
        }
    }
    ll d[n+1];
    int cnt[n+1];
    fill(cnt,cnt+n+1,0);
    while(q.size()>0){
        int now=q.front();q.pop();
        int p=par[now];
        d[now]=b[now]-a[now];
        if(p==0)break;
        a[p]-=d[now];
        cnt[p]++;
        if(cnt[p]==v[p].size()-1)q.push(p);

    }
    ll dd[n+1];
    queue<int> qq;
    qq.push(1);
    dd[1]=0;
    ll mi=1000000000000;
    while(qq.size()>0){
        int now=qq.front();
        qq.pop();
        if(now!=1){
            int p=par[now];
            dd[now]=dd[p]-d[now];
        }
        mi=min(mi,dd[now]);
        rep(i,0,v[now].size()){
            int ne=v[now][i];
            if(ne==par[now])continue;
            qq.push(ne);

        }
    }
    ll ans=0;
    rep(i,1,n+1){
        ans+=dd[i]-mi;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 12348
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;


int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n){ cin >> a.at(i); }
    sort(ALL(a));
    reverse(ALL(a));

    ll ans = 0;
    for(ll i = 1; i < n; ++i){
        ans += a.at(i / 2);
    }
    cout << ans << endl;
    return 0;
}


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

#define int long long
#define mod 1000000007

using namespace std;

bool dp[100010];
int a[110];

int32_t main()
{
    int n,k;
    cin >> n >> k;

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

    for(int i=0;i<k;i++)
    {
        if(!dp[i])
        {
            for(int j=0;j<n;j++)
            {
                if(i+a[j] <= k)
                    dp[i+a[j]] = true;
            }
        }
    }

    if(dp[k])
        cout << "First\n";
    else
        cout << "Second\n";
}

Measured memory_bytes: 384
program caddi2018b
  implicit none
  integer n, h, w, i
  integer, dimension(:), allocatable :: a, b
  logical, dimension(:), allocatable :: m

  read *, n, h, w
  allocate(a(n), b(n), m(n))
  m = .false.
  do i = 1,n
     read *, a(i), b(i)
  end do
  forall(i = 1:n, a(i).ge.h.and.b(i).ge.w) m(i) = .true.
  print '(i0)', count(m)
end program caddi2018b


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<ll> T(N);
    vector<ll> A(N);
    rep(i,N){
        cin >>  T[i] >> A[i];
    }
    ll Takahashi = T[0];
    ll Aoki = A[0];
    for (int i = 1; i < N; i++){
        ll min_t1;
        ll min_a1;
        if (Takahashi / T[i] > Aoki / A[i]){
            if (Takahashi % T[i] == 0){
                min_t1 = Takahashi;
                min_a1 = A[i] * (min_t1 / T[i]);
            }
            else{
                min_t1 = (Takahashi / T[i] + 1) * T[i];
                min_a1 = A[i] * (min_t1 / T[i]);
            }
        }
        else if (Takahashi / T[i] < Aoki / A[i]){
            if (Aoki % A[i] == 0){
                min_a1 = Aoki;
                min_t1 = T[i] * (min_a1 / A[i]);
            }
            else{
                min_a1 = (Aoki / A[i] + 1) * A[i];
                min_t1 = T[i] * (min_a1 / A[i]);
            }
        }
        else if (Takahashi / T[i] == Aoki / A[i]){
            if (Takahashi % T[i] != 0 || Aoki % A[i] != 0){
                min_t1 = (Takahashi / T[i] + 1) * T[i];
                min_a1 = (Aoki / A[i] + 1) * A[i];
            }
            else{
                min_t1 = Takahashi;
                min_a1 = Aoki;
            }
        }
        Takahashi = min_t1;
        Aoki = min_a1;
    }
    cout << Takahashi + Aoki << endl;
}


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

int main(int argc, char const *argv[])
{	
	int a,b,k;
	int p = 0;
	vector<int> v(101);
	cin >> a >> b >> k;
	for (int i = 1; i <= 100; ++i)
	{
		if(a % i ==0 && b % i == 0){
      // どっちでも割り切れたときにvの前からi番目に格納する
			v[p] = i;
			++p;
		}	
	}
	cout << v[p - k] << endl;
	return 0;
}

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

struct city
{
  // 誕生年, 入力された順番
  int64_t year;
  int in_order;
};

int main()
{
  int n, m;
  cin >> n >> m;
  vector<city> prefecture[101010];
  for (int i = 0; i < m; ++i)
  {
    int p;
    int64_t y;
    cin >> p >> y;
    prefecture[p].push_back({y, i+1});
  }

  // 県ごとに誕生年でソート
  for (int i = 1; i <= n; ++i)
  {
    if (prefecture[i].empty()) continue;
    sort(prefecture[i].begin(), prefecture[i].end(), [](const city &x, const city &y) {
      return x.year < y.year;
    });
  }

  vector<int64_t> id_upper(m + 1), id_bottom(m + 1);
  for (int i = 1; i <= n; ++i)
  {
    for (int j = 0, s = (int)prefecture[i].size(); j < s; ++j)
    {
      id_upper[prefecture[i][j].in_order] = i;
      id_bottom[prefecture[i][j].in_order] = j + 1;
    }
  }

  for (int i = 1; i <= m; ++i)
    cout << setfill('0') << right << setw(6) << id_upper[i] << setfill('0') << right << setw(6) << id_bottom[i] << "\n";
}

Measured memory_bytes: 8576
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
using namespace std;

#define lint long long int
#define INF 99999999



int main()
{
    int a, b;
    cin >> a >> b;
    cout << a*b << endl;
}





Measured memory_bytes: 3636
#include <algorithm>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int H, W;
  cin >> H >> W;
  vector<int> cnt(26, 0);
  for (int i = 0; i < H * W; i++) {
    char c;
    cin >> c;
    ++cnt[c - 'a'];
  }
  vector<int> mod(4, 0);
  for (int x : cnt) {
    if (x > 0) {
      ++mod[x % 4];
    }
  }
  if (mod[1] + mod[3] >= 2) {
    cout << "No" << endl;
    return 0;
  }
  if (mod[3] > 0) {
    ++mod[2];
  }
  int K =
      (H % 2 == 1 ? W : 0) + (W % 2 == 1 ? H : 0) - ((H * W) % 2 == 1 ? 1 : 0);
  K /= 2;
  bool res = mod[2] <= K && (K - mod[2]) % 2 == 0;
  cout << (res ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;
typedef vector<char> vchar;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

typedef vector<vector<string>> vvstring;

const int c_YET = -1;
const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const ll MAX = 1e9;
const double PI = 3.14159265358979323846264338327950288;
//========================================================================




int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================


	string S;

	cin >> S;



	int N = S.length();

	for (int i = 0; i < N / 2; i++)
	{
		if (S[i] != S[N - 1 - i])
		{
			cout << "No";
			return 0;
		}
	}


	for (int i = 0; i <= N / 4; i++)
	{
		if (S[i] != S[N/2 - 1 - i])
		{
			cout << "No";
			return 0;
		}
	}

	cout << "Yes";







}



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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename A>
void UNIQUE(vector< A > &a,int mode=0){
    if(mode==0){ sort(ALL(a),greater< A >());}else{ sort(ALL(a));}
    a.erase(unique(ALL(a)),a.en());
}

LL GCD(LL a,LL b){
    LL t; LL r;
    if(a<b){t=a;a=b;b=t;}
    if(b==0){return a;}
    while(a%b!=0){r=a%b;a=b;b=r;}
    return b;
}

int main(){
    int H,W;
    cin>>H>>W;
    V<Vi> a(H,Vi(W));
    REP(i,H){
        REP(j,W){
            cin>>a[i][j];
        }
    }

    V<Vi> ans;

    int i=0;
    while(i<H){
        if(i%2==0){
            REP(j,W){
                if(a[i][j]%2==1){
                    if(j+1==W){
                        if(i+1!=H){
                            a[i][j]--;
                            a[i+1][j]++;
                            Vi tmp = {i+1,j+1,i+2,j+1};
                            ans.pb(tmp);
                        }
                    }else{
                        a[i][j]--;
                        a[i][j+1]++;
                        Vi tmp = {i+1,j+1,i+1,j+2};
                        ans.pb(tmp);
                    }
                }
                if(j+1==W) i++;
            }
        }else{
            REPD(j,W-1){
                if(a[i][j]%2==1){
                    if(j==0){
                        if(i+1!=H){
                            a[i][j]--;
                            a[i+1][j]++;
                            Vi tmp = {i+1,j+1,i+2,j+1};
                            ans.pb(tmp);
                        }
                    }else{
                        a[i][j]--;
                        a[i][j-1]++;
                        Vi tmp = {i+1,j+1,i+1,j};
                        ans.pb(tmp);
                    }
                }
                if(j==0) i++;
            }
        }
    }

    cout<<ans.size()<<endl;
    REP(i,ans.size()){
        REP(j,4){
            cout<<ans[i][j];
            if(j<3) cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#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 SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//main code

int main(int argc, char const* argv[])
{
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	int h = 0;
	int ans = 0;
	for (int i = 0; i < n-1; i++) {
		if (s[i] != s[i+1]) {
			h++;
		}
		else {
			ans++;
		}
	}
	ans += min(h, k*2);
	cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, x;
  cin >> a >> b;
  x = a+b;
  if(x%2 == 0)
    cout << x/2 << endl;
  else
    cout << x/2+1 << endl;
  
 
}

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

int64_t nCk(int N, int K) {
    if(K < 0 || N < K) return 0;
    int64_t ret = 1;
    for(int i = 1; i <= K; ++i) {
        ret *= N--;
        ret /= i;
    }
    return ret;
}

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<double> v(N);
    rep(i, 0, N) cin >> v[i];
    sort(v.begin(), v.end(), greater<double>());
    double sum = 0;
    rep(i, 0, A) sum += v[i];
    int X = 0;
    rep(i, 0, N) if(v[i] == v[A - 1]) X++;
    int64 ans = 0;
    if(v[0] == v[A - 1]) {
        rep(i, A, B + 1) ans += nCk(X, i);
    } else {
        int Y = 0;
        rep(i, 0, A) if(v[A - 1] == v[i]) Y++;
        ans = nCk(X, Y);
    }
    printf("%.10lf\n", sum / A);
    cout << ans << endl;
    return 0;
}


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

#define mp make_pair
#define pb push_back

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

const int maxn = 1e5+1;

int n, m;

int p[maxn];
bool d[maxn];
bool determined[maxn];
void init(int n)
{
  for (int i = 1; i <= n; ++i)
    {
      p[i] = i; d[i] = false; determined[i] = false;
    }
}
int pa(int x)
{
  if (x != p[x])
    {
      int last_p = p[x];
      p[x] = pa(last_p);
      d[x] = d[x] ^ d[last_p];
    }
  return p[x];  
}
void merge(int from, int to, bool dis)
{
  int from_p = pa(from);
  int to_p = pa(to);
  if (from_p != to_p)
    {
      p[from_p] = to_p;
      d[from_p] = d[from] ^ d[to] ^ dis;
    }
}

int main()
{
  scanf("%d %d", &n, &m);
  init(n);
  vector<int> v;
  for (int i = 1; i <= m; ++i)
    {
      int x, y, z; scanf("%d %d %d", &x, &y, &z);
      bool dis = z&1;
      if (x == y) v.pb(x);
      else merge(x, y, dis);
    }
  for (auto e : v) determined[pa(e)] = true;
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    if (pa(i) == i)
      ans += !determined[i];
  printf("%d\n", ans);
}


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


long long K[200005];
long long L[200005];
long long R[200005];

int solve() {
	long long N;
	set<long long> posset;
	vector<pair<long long, long long> > lvec;
	vector<pair<long long, long long> > rvec;
	cin >> N;

	for(long long i = 0; i < N; i++) {
		cin >> K[i] >> L[i] >> R[i];
		if(L[i] >= R[i]) {
			lvec.push_back(make_pair(L[i] - R[i], i));
		} else {
			rvec.push_back(make_pair(R[i] - L[i], i));
		}
		posset.insert(i);
	}

	sort(lvec.begin(), lvec.end(), greater<pair<long long, long long> >());
	sort(rvec.begin(), rvec.end(), greater<pair<long long, long long> >());


	long long ans = 0;
	for(long long i = 0; i < lvec.size(); i++) {
		//cout << "lvec[" << i << "] = " << lvec[i].first << "," << lvec[i].second << endl;
		//Lの方にしたいから、K未満で最も大きいところに置く(最大でもlvec.size()未満)
		long long idx = lvec[i].second;
		long long k = min(K[idx], (long long) lvec.size());
		set<long long>::iterator it = posset.lower_bound(k);

		//cout << "idx = " << idx << " k = " << k << endl;
		if(it == posset.begin()) {
			//cout << "can not place" << endl;
			//置けるとこないからlvec.size()未満の最大に置いて邪魔にならないようにする
			ans += R[idx];


		} else {
			ans += L[idx];
			it--;
			long long pos = *it;
			//cout << "can place: " << pos << endl;
			posset.erase(pos);
		}
	}

	// just in case
	for(long long i = 0; i < lvec.size(); i++) {
			posset.erase(i);
	}

	for(long long i = 0; i < rvec.size(); i++) {
		//cout << "rvec[" << i << "] = " << rvec[i].first << "," << rvec[i].second << endl;
		//Rの方にしたいから、K異常で最も大きいところに置く(最小でもlvec.size()異常)
		long long idx = rvec[i].second;
		long long k = K[idx];
		set<long long>::iterator it = posset.lower_bound(k);

		//cout << "idx = " << idx << " k = " << k << endl;
		if(it == posset.end()) {
			//cout << "can not place" << endl;
			//置けるとこないからlvec.size()以上の最小に置いて邪魔にならないようにする
			ans += L[idx];


		} else {
			ans += R[idx];
			long long pos = *it;
			//cout << "can place: " << pos << endl;
			posset.erase(pos);
		}
	}
	cout << ans << endl;
	return 0;
}



int main(){
	long long T;
	cin >> T;
	for(long long i = 0; i < T; i++){
		solve();
	}
}


Measured memory_bytes: 20532
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 


int N,M; ll S;
ll MAX_S = 2505;
struct edge {
  int to;
  ll cost, t;
  edge(int to, ll cost, ll t):to(to), cost(cost), t(t) {}
};

struct Data {
  int v; ll s;
  ll x;
  Data(int v, ll s, ll x): v(v), s(s), x(x) {}
  bool operator<(const Data& a) const {
    return  x > a.x;
  }
};

int main() {  
  cin >> N>>M>>S;
  vector<ll> c(N);
  vector<ll> d(N);
  vector<vector<edge>> g(N, vector<edge>());
  rep(i,M) {
    int u,v; ll a,b; cin>>u>>v>>a>>b;
    u--;v--;
    g[u].emplace_back(v,a,b);
    g[v].emplace_back(u,a,b);
          // g[u].push_back(edge{v,a,b});
          // g[v].push_back(edge{u,a,b});
  } 
  
  rep(i, N) {
    cin >> c[i] >> d[i];
  }
  S = min(S, MAX_S);
  priority_queue<Data> q;
  vector<vector<ll>> dp(N, vector<ll>(MAX_S+5, LINF));
  auto push = [&] (int v, ll s, ll x) {
    if (s<0) return;
    // if (s>MAX_S) return ;
    if (dp[v][s] <= x) return ;
    dp[v][s] = x;
    // Data foo = Data(v,s,x);
    // q.push(Data{v,s,x});
    q.emplace(v,s,x);
    // q.push(foo);
  };
  push(0,S,0);
  while(q.size()) {
    Data foo = q.top(); q.pop();
    int v = foo.v;
    S=foo.s;
    ll x = foo.x;
    if (dp[v][S] != x) continue;
    ll ns =  min(S+c[v], MAX_S);
    push(v, ns , x+d[v]);
    rep(i, g[v].size()) {
      edge e = g[v][i];
      int nv = e.to;
      push(nv, S-e.cost, x+e.t);
    }
  }
  for (int i=1; i<dp.size();i++) {
    ll ans = LINF;
    rep(j, dp[i].size()) {
      ans = min(ans, dp[i][j]);
    }
    cout << ans << endl;
  }
  return 0;
}

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

using namespace std;

using ll=long long;
void solve() {
    ll n,m;
    cin >> n >> m;
    ll res = min(n, m/2);
    m -= res*2;
    res += m/4;
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int main(){
//int n,a[100001]={0};
//cin>>n;
//cout<< <<endl;
int n;
int x,y;
int ans=0;
cin>>n;
for(int i=1;i<=n;i++){
	cin>>x>>y;
	ans+=(y-x+1);
}
cout<<ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int M,D,dp[105][105];
int main(){
	for(int i=22;i<=99;i++){
		if(i%10>=2)
			dp[(i/10)*(i%10)][i]++;
	}
	int ans=0;
	while(cin>>M>>D){
	ans=0;	
	for(int i=4;i<=M;i++)
		for(int j=22;j<=D;j++)
			ans+=dp[i][j];
	cout<<ans;}
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Your code here!
    char str[200001];
    char *pstr = str;
    int len = 0;
    
    scanf("%200000s",str);
    
    while(*pstr){
        pstr++;
        len++;
    }
    
    for(int i = len-1; i >= 0; i--){
        if(str[i] == '?'){
            if(i == len -1){
                str[i] = 'D';
            }
            else if(str[i+1] == 'P'){
                str[i] = 'D';
            }
            else if(str[i+1] == 'D'){
                str[i] = 'D';
            }
        }
    }
    
    printf("%s\n",str);
}

Measured memory_bytes: 1820
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
for _ in range(int(input())):
  N = int(input())
  a = []
  mnsm = 0
  table = [[] for _ in range(N + 1)]
  ls = 0
  for _ in range(N):
    K, L, R = map(int, input().split())
    mnsm += min(L, R)
    a.append((K, L, R))
    if L >= R: table[K - 1].append((L, R))
    else: table[K].append((L, R))
    ls += L >= R
  h = []
  hh = []
  res = 0
  for i in range(N):
    for L, R in table[i]:
      if L >= R:
        hpush(h, L - R)
        res += L - R
    while len(h) > i + 1: res -= max(0, hpop(h))
  for i in range(N, -1, -1):
    for L, R in table[i]:
      if R > L:
        hpush(hh, R - L)
        res += R - L
    while len(hh) > N - i:
      res -= max(0, hpop(hh))
  print(mnsm + res)

Measured memory_bytes: 132800
int main(void)
{
    int a,b,c;
    int score = 0;
    
    scanf("%d %d %d",&a, &b, &c);
    
    if(a > c && b > c)
        score = 0;
    else if(a < c && b < c)
        score = 0;
    else
        score = 1;

    
    if(score == 0)
        printf("No\n");
    else
        printf("Yes\n");
    
    return 0;
}


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

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

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

using namespace std;
typedef long long LL;
using Graph = vector<vector<int>>;

static long long INF = (1LL<<62);


string S;
vector<long long> LR;

void solve(string &S, int s, int e, vector<long long> &ANS){
	int rl = s;
	rl = S.find("RL", s);
	for(int i=s; i<=rl; i++){
		if((rl - i) % 2 == 0){
			ANS[rl]++;
		}
		else{
			ANS[rl+1]++;
		}
	}
	for(int i=rl+1; i<=e; i++){
		if((i - rl - 1) %2 == 0){
			ANS[rl+1]++;
		}
		else{
			ANS[rl]++;
		}
	}
}

//LRで分離され、RLのどちらかに収束する。
int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> S;
	long long N = S.size();
	vector<LL> ANS;
	ANS.assign(N, 0);

	for(int i=0; i<N-1; i++){
		if(S[i] == 'L' && S[i+1] == 'R'){
			LR.push_back(i);
		}
	}

	if(LR.size() > 0){
		for(int k=0; k<LR.size(); k++){
			int s, e;
			e = LR[k];
			if(k == 0){
				s = 0;
			}
			else{
				s = LR[k - 1] + 1;
			}
			solve(S, s, e, ANS);
		}
		//最後
		int l = LR.size() - 1;
		solve(S, LR[l] + 1, N-1, ANS);
	}
	else{
		solve(S, 0, N-1, ANS);
	}

	for(int i=0; i<N; i++){
		printf("%lld", ANS[i]);
		if(i < N - 1) printf(" ");
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 4824
N = gets.to_i
S, P= N.times.map{ gets.strip.split }.transpose
P.map!(&:to_i)

result = []
for var in  S.uniq.sort do
    foo = P.select{ |x| S[P.index(x)] == var }.sort.reverse
    foo.each{ |y| result.push(y) }
end

result.each{ |z| puts P.index(z) + 1 }

Measured memory_bytes: 1788