akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 9999999999
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define p(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
//#define int long long


using namespace std;


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };




ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

ll pow2(ll a, ll n) {//aのn乗を計算します。
	ll x = 1;
	while (n > 0) {//全てのbitが捨てられるまで。
		if (n & 1) {//1番右のbitが1のとき。
			x = x * a;
		}
		a = a * a;
		n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
	}
	return x;
}

long long nCr(int n, int r) {
	if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
	long long ans = 1;
	int i;

	for (i = 1; i <= r; i++) {
		ans *= n - r + i;
		ans /= i;
	}

	return ans;
}


const int MOD = 1000000007;

bool arr[1050000];
int sosuu[100010];
void Eratosthenes() {
	ll N = 1050000;
	int c = 0;
	for (int i = 0; i < N; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i < sqrt(N); i++) {
		if (arr[i]) {
			for (int j = 0; i * (j + 2) < N; j++) {
				arr[i *(j + 2)] = 0;
			}
		}
	}

	for (int i = 2; i < N; i++) {
		if (arr[i]) {
			sosuu[c] = i;
			//cout << sosuu[c] << " ";
			c++;
		}
	}
	//cout << endl;
	//cout << c << endl;
}

bool A[100010];
int B[100010];
vector<int>graph[100010];
int main() {
	m0(A);m0(B);
	int N,M;
	cin >> N>>M;
	bool exist=0;
	REP(i,M){
		int a,b;
		cin >> a>>b;
		a--;b--;
		A[a]=true;
		graph[a].pb(b);
	}
	REP(i,N){
		if(A[i]){
			VSORT(graph[i]);
			B[graph[i][0]]++;
		}
	}
	ll ans = 0 ;
	ll cnt =0;
	REP(i,N){
		if(exist){
			if(B[i]>0){
				for(int j=cnt;j<i;j++)if(A[j])B[graph[j][0]]--;
				ans++;
				exist=false;
				cnt=i;
			}
		}
		if(A[i])exist=true;
	}
	p(ans);
}

//もじゃさんのしゃきょう


Measured memory_bytes: 7424
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin >> n >> m;
	if((n+m)==15){
		cout << "+" << endl;
		return 0;
	}else{
		if((n*m)==15){
			cout << "*" << endl;
			return 0;	
		}
	}
	cout << "x" << endl;
	system("pause");
	return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n;
    cin >> n;
    vector<lint> a(n + 1), b(n);
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    lint ret = 0;
    for (int i = 0; i < n; ++i) {
        lint t = min(a[i], b[i]);
        b[i] -= t;
        ret += t;
        lint u = min(a[i + 1], b[i]);
        a[i + 1] -= u;
        ret += u;
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,m,q; LL a[N],b[N],ans[N];
int main()
{
	int i,l,r,mid; LL x;
	scanf("%d %d",&n,&q),a[m=1]=n;
	for(i=1;i<=q;i++){
		scanf("%lld",&x);
		while(m&&a[m]>=x) m--;
		a[++m]=x;
	  }
	b[m]=1;
	for(i=m;i>=2;i--){
		for(x=a[i];;){
			l=0,r=i;
			while(r-l>1){
				mid=(l+r)>>1;
				if(x>=a[mid]) l=mid;
				else r=mid;
			  }
			if(!l){ ans[x]+=b[i]; break;}
			b[l]+=b[i]*(x/a[l]),x%=a[l];
		  }
		b[i]=0;
	  }
	ans[a[1]]+=b[1];
	for(i=n;i>=1;i--) ans[i]+=ans[i+1];
	for(i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}


Measured memory_bytes: 4096
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	as := map[int]int{}
	var a int
	for i := 0; i < n; i++ {
		fmt.Scan(&a)
		as[a]++
	}

	var max int
	for x := 0; x < 100000; x++ {
		cnt := as[x] + as[x-1] + as[x+1]
		if cnt > max {
			max = cnt
		}
	}

	fmt.Println(max)
}


Measured memory_bytes: 8064
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>

using namespace std;

typedef pair<int, int> P;
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define _1 first
#define _2 second
#define pb push_back
#define mod 1000000007
#define INF 1050000000

const int maxn = 1e5 + 10;
int a,s[10005];

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

	string s; cin >> s;

	cout << "ABC" << s << endl;


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6 + 69;

ll n,m,k,x,y,ans;

ll A[N],fix[N];

vector< ll > v;

string s;

int main(){

    ios::sync_with_stdio(0);

    cin>>n>>k;

    for(int i=1;i<=n;i++)
        fix[i] = 1e18;

    fix[0] = 0;

    for(int i=1;i<=k;i++){
        cin>>x>>y;
        for(int j=0;j<=n;j++)
        if(fix[j]!=1e18){
            fix[min(j+x,n)] = min(fix[min(n,j+x)],fix[j] + y);
        }
    }

    cout<<fix[n]<<endl;



}


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

int main() {
    int n, a, b;
    cin >> n;
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> a >> b;
        v[i] = make_pair(-b, a);
    }
    sort(v.begin(), v.end());
    int time = 1000000010;
    for(int i = 0; i < n; ++i) {
        int shimekiri = -v[i].first, t = v[i].second;
        time = min(shimekiri, time) - t;
        if(time < 0) {
            cout << "No" << '\n';
            return 0;
        }

    }
    cout << "Yes" << '\n';
    
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if((A+B)>(C+D))cout << "Left" << endl;
  else if((A+B)<(C+D))cout << "Right" << endl;
  else cout << "Balanced" << endl;
}


Measured memory_bytes: 256
#![allow(non_snake_case,unused_imports,dead_code)]
use std::io::Read;
use std::cmp::max;
use std::cmp::min;
use std::str::FromStr;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::BinaryHeap;
use std::cmp::Ordering;

use proconio::input;
use proconio::marker::{Chars,Usize1,Isize1};

fn comp_f64(a: &f64, b: &f64) -> Ordering {
    if a < b {
        return Ordering::Less;
    } else if a > b {
        return Ordering::Greater;
    }
    Ordering::Equal
}

fn main() {

    input!{
        N:usize,
        T:[isize;N],
        A:[isize;N]
    }

    let MOD = 1_000_000_007;
    let mut ans = 1;

    if N==1{
        println!("{}",if A[0]==T[0] {1} else {0});
        return;
    }

    if A[0]>A[1] && A[0]!=T[0] {ans = 0;}
    if A[0]<T[0] {ans = 0;}
    if T[N-1]>T[N-2] && A[N-1]!=T[N-1] {ans = 0;}
    if T[N-1]<A[N-1] {ans = 0;}

    for i in 1..N-1{
        let mut tmp = 1;
        if T[i]>T[i-1] && A[i]>A[i+1]{
            if T[i]!=A[i] {tmp = 0;}
        } else if T[i]>T[i-1]{
            if T[i] > A[i] {tmp = 0;}
        } else if A[i]>A[i+1]{
            if A[i] > T[i] {tmp = 0;}
        } else {
            tmp = min(T[i],A[i]);
        }
        ans *= tmp;
        ans %= MOD;
    }

    ans %= MOD;
    println!("{}",ans);
}

Measured memory_bytes: 5560
n,a,b = map(int,input().split())
ans = 10**20
if abs(a-b)%2==0:
    ans = abs(a-b)//2
else:
    #右でパリティを変えて近づく
    tmp = (abs(a-b)-1)//2+min(n-a,n-b)+1
    ans = min(ans,tmp)
    #左でパリティを変えて近づく
    tmp = (abs(a-b)-1)//2+min(a-1,b-1)+1
    ans =min(ans,tmp)
print(ans)


Measured memory_bytes: 3060
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
      	int b = sc.nextInt();
		int sho = 0;
      	int amrS = 0;
	    int ans = 0;
      
      for(int i = 1 ; i < n+1 ; i++){
        sho = i;
        amrS= 0;
      	while(sho != 0){
          amrS += sho%10;
          sho /= 10;
        }  
        if(amrS >= a && amrS <= b){
        	ans += i; 
        }  
      }
                  System.out.println(ans);
    }
}


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

const int N=2e5+100;
const int mod=1e9+7;
typedef long long ll;


typedef pair<int,int> pa;

int fa[200],p[200][200],vis[200];

vector<int>ve[200];

int a[200],b[200],c[200],d[200];

int dfs(int x)
{
    for (auto v:ve[x]){
        if(!vis[v]){
            vis[v]=1;
            if(fa[v]==-1 || dfs(fa[v])){
               fa[v]=x;
               return 1;
            }
        }
    }
    return 0;
}
int n;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    memset(fa,-1,sizeof fa);
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=n;i++) {
        cin>>c[i]>>d[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(c[j]>a[i] && d[j]>b[i]) {
                ve[i].push_back(j);
              //  ve[j].push_back(i);
            }
        }
    }
    int ans=0;

    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        if(dfs(i)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}


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

int main(void){
	int n;
	cin >> n;
	vector<int> a(n, 0);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	std::sort(a.begin(), a.end() );
	
	int counter = 0;
	int temp;
	int j = -1;
	for(int i = 0; i < n; i++){
		if(j == a[i]){
			temp++;
		}else{
			if(temp % 2 == 1)  counter++;
			temp = 1;
			j = a[i];
		}
		if(i == n-1){
			if(temp % 2 == 1)  counter++;
		}
	}
	cout << counter << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define endl			"\n"
#define ll				long long
#define all(v)			((v).begin()), ((v).end())
#define sz(v)			((int)((v).size()))
#define clr(v, d)		memset(v, d, sizeof(v))
#define rep(i, v)		for(int i=0;i<sz(v);++i)
#define lp(i, n)		for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)	for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)	for(int i=(j);i>=(int)(n);--i)
#define vi				vector <int>
#define vl				vector <ll>
#define ii				pair <ll,ll>
#define vii				vector <ii>
#define ull				unsigned long long
const double PI = 2 * acos(0.0);
void run() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
}

int main() {
	run();
	string s;
	cin >> s;
	int n = s.size();
	int cntCap = 0, cntC = 0;
	lp(i,n)
		cntCap += (s[i] >= 97);
	for (int i = 2; i < n - 1; i++) {
		cntC += (s[i] == 'C');
	}
	//cout << cntCap << ' ' << cntC << endl;
	if (s[0] == 'A' && cntCap == n - 2 && cntC == 1)
		cout << "AC";
	else
		cout << "WA";
}



Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint inf=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}


int main(void){
	int n,i,ans=0;cin>>n;
	multiset<llint>h;
	for(i=0;i<n;i++){llint x;cin>>x;h.ins(x);}
	while(h.size()){
		auto aaa=prev(h.end());
		h.erase(aaa);
		llint ter=1,u=(*aaa);
		while(ter<=u){ter*=2;}
		ter-=u;
		auto p=h.lower_bound(ter);
		if(p==h.end()){continue;}
		if((*p)!=ter){continue;}
		ans++;
		h.erase(p);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 12564
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
using namespace std;

int main() {

    vector<vector<char> > root (9, vector<char>(5));

    char c;
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 4 + (i % 2); j++) {
            cin >> c;
            root[i][j] = c;
        }
    }

    cout << "R";

    int x = 1;
    int y = 0;
    int d = 2;
    char dirs [] = { 'L', 'U', 'R', 'D', 'L', 'U', 'R', 'D' }; 

    while ( x || y ) {
        bool gone = false;
        for (int i = -1; i < 3; i++) {
            switch(dirs[d + i]) {
                case 'L':
                    if (x > 0 && root[2 * y][x - 1] == '1') {
                        x -= 1;
                        d = 4;
                        cout << 'L';
                        gone = true;
                    }
                    break;
                case 'U':
                    if (y > 0 && root[2 * y - 1][x] == '1') {
                        y -= 1;
                        d = 1;
                        cout << 'U';
                        gone = true;
                    }
                    break;
                case 'R':
                    if (x < 4 && root[2 * y][x] == '1') {
                        x += 1;
                        d = 2;
                        cout << 'R';
                        gone = true;
                    }
                    break;
                case 'D':
                    if (y < 4 && root[2 * y + 1][x] == '1') {
                        y += 1;
                        d = 3;
                        cout << 'D';
                        gone = true;
                    }
                    break;
            }
            if (gone) break;
        }
    }
    cout << endl;
     
    return 0;
}

Measured memory_bytes: 0
// Copyright 2017 Parallelc
#include <bits/stdc++.h>
using namespace std;  // NOLINT

using LL = int64_t;
const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string a, b, c;
    cin >> a >> b >> c;
    if (b.front() == a.back() && b.back() == c.front()) cout << "YES\n";
    else cout << "NO\n";
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int a[18];

long long dfs(int x, int y, int p, int q) {
    int i;
    long long ans = 1e18;
    
    if (x + 1 == y) return 0;
    
    for (i = x + 1; i < y; i++) ans = min(ans, dfs(x, i, p, p + q) + dfs(i, y, p + q, q) + (long long)(p + q) * a[i]);
    
    return ans;
}

int main() {
    int n, i;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    
    printf("%lld\n", dfs(0, n - 1, 1, 1) + a[0] + a[n - 1]);
    
    return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		--A;
		--B;
		int[] x = new int[Q];
		for (int i = 0; i < Q; ++i) {
			x[i] = sc.nextInt();
			--x[i];
		}
		solve(N, Q, A, B, x);

	}

	void solve(int N, int Q, int A, int B, int[] x) {
		long[] f = new long[N];
		Arrays.fill(f, Long.MAX_VALUE / 16);
		Seg sAdd = new Seg(N);
		Seg sSub = new Seg(N);
		f[B] = Math.abs(A - x[0]);
		f[A] = Math.abs(B - x[0]);
		sAdd.setVal(A, f[A] + A);
		sAdd.setVal(B, f[B] + B);
		sSub.setVal(A, f[A] - A);
		sSub.setVal(B, f[B] - B);
		long pending = 0;
		for (int i = 1; i < Q; ++i) {
			long add = Math.abs(x[i] - x[i - 1]);
			pending += add;
			long cur = f[x[i]];// pending分は除く
			cur = Math.min(cur, -x[i] + sAdd.query(x[i], N) - add);
			cur = Math.min(cur, x[i] + sSub.query(0, x[i]) - add);
			f[x[i - 1]] = cur;
			sAdd.setVal(x[i - 1], f[x[i - 1]] + x[i - 1]);
			sSub.setVal(x[i - 1], f[x[i - 1]] - x[i - 1]);
		}
		long ans = Long.MAX_VALUE / 16;
		for (int i = 0; i < N; ++i) {
			ans = Math.min(ans, f[i] + pending);
		}
		System.out.println(ans);
	}

	class Seg {
		int n;
		long[] v;

		public Seg(int n_) {
			n = 1;
			while (n < n_)
				n *= 2;
			v = new long[2 * n - 1];
			Arrays.fill(v, Long.MAX_VALUE / 16);
		}

		void setVal(int k, long val) {
			k += n - 1;
			v[k] = val;
			while (k > 0) {
				k = (k - 1) / 2;
				v[k] = Math.min(v[2 * k + 1], v[2 * k + 2]);
			}
		}

		long query(int a, int b) {
			return query(0, n, a, b, 0);
		}

		long query(int l, int r, int a, int b, int k) {
			if (r <= a || b <= l) {
				return Long.MAX_VALUE / 16;
			} else if (a <= l && r <= b) {
				return v[k];
			} else {
				long vl = query(l, (l + r) / 2, a, b, 2 * k + 1);
				long vr = query((l + r) / 2, r, a, b, 2 * k + 2);
				return Math.min(vl, vr);
			}
		}

	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 90508
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


bool input() {
  return true;
}

void solve(){
}

int main() {
  string s; cin >>s;
  int q; cin >>q;
  rep(qq, q){
    string com; cin >>com;
    int a,b; cin >>a >>b;
    if (com == "print"){
      for (int i=a; i<=b; i++) cout <<s[i];
      cout <<endl;
    }else if (com == "reverse"){
      reverse(s.begin()+a, s.begin()+b+1);
    }else if (com == "replace"){
      string t; cin >>t;
      for (int i=0; i<t.size(); i++){
        s[i+a] = t[i];
      }
    }
  }
}


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

const int INF = 1e9;
using lint = long long;
const lint LINF = 1e18;
const lint MOD = 1e9 + 7;
// const lint MOD = 998244353;

template <typename T>
T gcd(T m, T n) {
    if (n == 0) {
        return m;
    } else {
        return gcd(n, m % n);
    }
}

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

    int n;
    cin >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> lef(n + 2), rig(n + 2);
    for (int i = 1; i <= n; i++) {
        lef[i] = gcd(lef[i - 1], a[i]);
    }
    for (int i = n; i > 0; i--) {
        rig[i] = gcd(rig[i + 1], a[i]);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, gcd(lef[i - 1], rig[i + 1]));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1408
import numpy as np
n = int(input())
a = list(map(int, input().split()))
a = np.array(a)
mod = 10**9 + 7
ans = 0
for i in range(60):
  # a要素のi番目のデータが1であるデータの数
  b = np.count_nonzero(a >> i & 1)
  # 2進数 -> 10進数 (b*(N-b)は(1の個数)*(0の個数))
  ans += 2 ** i * (b*(n-b))
  # 和算のたびにmodで割ってあげる
  ans %= mod
print(ans)

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

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

  vector<int> p(n);
  REP(i,n) {
    cin >> p[i];
  }
  
  int ans = 0;
  int a, b;
  REP(i,n-2) {
    a = max({p[i],p[i+1],p[i+2]});
    b = min({p[i],p[i+1],p[i+2]});
    if (p[i+1] != a && p[i+1] != b) ans++;
  }
  
  cout << ans << endl;
  
}

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

typedef long long ll;

const int inf = (1 << 30);
int H[100002], n;
int dp[100002][4];

int go(int p, int last) {
    if(p == n - 1) {
        return abs(H[p] - H[p - last]);
    }
    if(dp[p][last] != -1) return dp[p][last];
    int op1 = inf, op2 = inf;
    op1 = go(p + 1, 1);
    if(p + 2 <= n - 1) op2 = go(p + 2, 2);
    return dp[p][last] = abs(H[p] - H[p - last]) + min(op1, op2);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    memset(dp, -1, sizeof dp);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> H[i];
    }
    cout << go(0, 0) << endl;
}




Measured memory_bytes: 8448
#include "bits/stdc++.h"
using namespace std;

int main() {
  int N;
  cin >> N;
  switch(N%10) {
  case 2:
  case 5:
  case 4:
  case 7:
  case 9:
    cout << "hon";
    break;
  case 0:
  case 1:
  case 6:
  case 8:
    cout << "pon";
    break;
  case 3:
    cout << "bon";
    break;
  }
}

Measured memory_bytes: 3608
arr = Array.new
while line = $stdin.gets
arr << line.chomp.split(" ").map(&:to_i)
end
peak = arr[1]
maps=Array.new(arr[0][0]).fill(0)
(arr[2..-1]).each{|i|
    if peak[i[0]-1] == peak[i[1]-1] then
        maps[i[0]-1] = -1
        maps[i[1]-1] = -1
    elsif peak[i[0]-1] > peak[i[1]-1]
        maps[i[1]-1] = -1
    else
        maps[i[0]-1] = -1
    end
}
puts maps.count(0)

Measured memory_bytes: 23556
#!/usr/bin/env python3
import sys
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int):

    ans = []
    for i in range(1, 10):
        for j in range(1, 10):
            ans.append(i*j)
    if N in ans:
        yes()
    else:
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <iostream>
using namespace std;
typedef long long ll;
const long long mod = 1e9 + 7;
int main() {
    ll n,m;
    cin >> n >> m;
    if (n%2==1){
        for (ll i = 1; i <= m; i++) {
            cout << i << " " << n - i << endl;;
        }
    }
    else {
        for (ll i = 1; i <= m; i++) {
            if (i < (n+4)/4) {
                cout << i << " " << n - i + 1 << endl;
            }
            else {
                cout << i  << " " << n - i  << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3600
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

int n;
ll a[20];

ll dp(int ,int ,int ,int);

int main(){
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	cout << dp(1, n, 1, 1) << endl;
	return 0;
}

ll dp(int l, int r, int x, int y){
	if(r - l + 1 == 2) return a[l] * x + a[r] * y;
	ll ans = 999999999999999;
	for(int i = l + 1; i < r; ++i)
		ans = min(ans, dp(l, i, x, x + y) + dp(i, r, x + y, y) - a[i] * (x + y));
	return ans;
}

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

using namespace std;

int main(void){

    int n,k;
    cin >> n >> k;
    
    unsigned long long result = k;
    for(int i=1; i<n; i++) {
        result *= (k-1);
    }

    cout << result << endl;

    return 0;
    
}


Measured memory_bytes: 256
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;
int n;
long long m;
vector<vector<int>> p;
vector<vector<long long>> bmemo, amemo;
vector<map<int, long long>> cmemo;
vector<int> parent;

long long dfs(int i, int from) {
  parent[i] = from;
  vector<long long> v;
  for (auto &j : p[i]) {
    if (j == from)
      v.push_back(1);
    else
      v.push_back((dfs(j, i) + 1) % m);
  }
  long long ret = 1;
  bmemo[i].push_back(ret);
  for (int j = 0; j < p[i].size(); j++) {
    ret *= v[j];
    ret %= m;
    bmemo[i].push_back(ret);
  }
  long long back = 1;
  amemo[i].push_back(back);
  for (int j = (int)p[i].size() - 1; j >= 0; j--) {
    back *= v[j];
    back %= m;
    amemo[i].push_back(back);
  }
  reverse(amemo[i].begin(), amemo[i].end());
  return ret;
}

long long dfs2(int i, int from) {
  if (cmemo[i].find(from) != cmemo[i].end())
    return cmemo[i][from];
  auto it = lower_bound(p[i].begin(), p[i].end(), from);
  cmemo[i][from] = 1;
  if (parent[i] >= 0)
    cmemo[i][from] *= (dfs2(parent[i], i) + 1) % m;
  cmemo[i][from] *= bmemo[i][it - p[i].begin()];
  cmemo[i][from] %= m;
  cmemo[i][from] *= amemo[i][it - p[i].begin() + 1];
  cmemo[i][from] %= m;
  return cmemo[i][from];
}

long long dfs3(int i) {
  if (parent[i] < 0) {
    return amemo[i][0];
  }
  return (amemo[i][0] * (dfs2(parent[i], i) + 1)) % m;
}

int main() {
  cin >> n >> m;
  bmemo.resize(n);
  amemo.resize(n);
  cmemo.resize(n);
  parent.resize(n);
  p.resize(n);
  for (int i = 0; i < n - 1; i++) {
    int a, s;
    cin >> a >> s;
    a--;
    s--;
    p[a].push_back(s);
    p[s].push_back(a);
  }
  for (int i = 0; i < n; i++)
    sort(p[i].begin(), p[i].end());
  dfs(0, -1);
  for (int i = 0; i < n; i++) {
    cout << dfs3(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 38144
import numpy as np
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(len(s)):
    for j in range(len(s[0])):
        if s[i][j] == '#':
            continue
        pre = 0
        p = np.full((h, w), -1)
        p[i][j] = 0
        check = deque([((i, j), 0)])#(from,now, dist)
        while check:
            now, d = check.popleft()
            pre = max(pre, d)
            for k, l in [(1,0), (-1,0),(0,1), (0,-1)]:
                b = now[0] + k
                c = now[1] + l
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                elif p[b][c] == -1 and s[b][c] != '#':
                    check.append(((b, c), d + 1))
                    p[b][c] = d + 1
        ans = max(ans, pre)

print(ans)

Measured memory_bytes: 27160
import numpy as np

n = int(input())
v = [int(_) for _ in input().split()]

m = int(n / 2)
p = max(v)

evens = np.array([0] * p)
odds = np.array([0] * p)

for i in range(0, m):
    evens[v[2 * i] - 1] += 1
    odds[v[2 * i + 1] - 1] += 1

if len(evens) == 1 and len(odds) == 1:
    if evens.argsort()[-1] == odds.argsort()[-1]:
        print(m)
    else:
        print(0)
elif len(evens) ==1:
    mode_e1 = evens.argsort()[-1]
    mode_o2, mode_o1 = odds.argsort()[-2:]
    if mode_e1 == mode_o1:
        print(m - odds[mode_o2])
    else:
        print(m - odds[mode_o1])
elif len(odds) == 1:
    mode_e2, mode_e1 = evens.argsort()[-2:]
    mode_o1 = odds.argsort()[-1]
    if mode_e1 == mode_o1:
        print(m - evens[mode_e2])
    else:
        print(m - evens[mode_e1])
else:
    mode_e2, mode_e1 = evens.argsort()[-2:]
    mode_o2, mode_o1 = odds.argsort()[-2:]

    if mode_e1 == mode_o1:
        print(min(n - evens[mode_e1] - odds[mode_o2], n - evens[mode_e2] - odds[mode_o1]))
    else:
        print(n - evens[mode_e1] - odds[mode_o1])


Measured memory_bytes: 33036
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i <= n; i++)
template<class T> inline int chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline int chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<30;
const ll LINF = 1LL<<58;
const int mod = 1000000007;

ll dp[10101][2][110];

int main(){
    string s; int d;
    cin >> s >> d;
    int n = s.size();
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        int x = s[i] - '0';
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < d; k++) {
                for (int l = 0; l <= (j ? 9 : x); l++) {
                    dp[i + 1][j || l < x][(k + l) % d] += dp[i][j][k];
                    dp[i + 1][j || l < x][(k + l) % d] %= mod;
                }
            }
        }
    }
    cout << ((dp[n][0][0] + dp[n][1][0] - 1) % mod + mod) % mod<< endl;
    return 0;
}


Measured memory_bytes: 17408
#include <iostream>

using namespace std;

int result500=0,result1000=0;

void time500m(double time){
    if(time < 35.50){
        result500=0;
    }
    else if(time >= 35.50 && time < 37.50 ){
        result500=1;
    }
    else if(time >= 37.50 && time < 40 ){
        result500=2;
    }
    else if(time >= 40 && time < 43 ){
        result500=3;
    }
    else if(time >= 43 && time < 50 ){
        result500=4;
    }
    else if(time >= 50 && time < 55 ){
        result500=5;
    }
    else if(time >= 55 && time < 70 ){
        result500=6;
    }
    else if(time >= 70 ){
        result500=7;
    }
}

void time1000m(double time){
    if(time < 71){
        result1000=0;
    }
    else if(time >= 71 && time < 77 ){
        result1000=1;
    }
    else if(time >= 77 && time < 83 ){
        result1000=2;
    }
    else if(time >= 83 && time < 89 ){
        result1000=3;
    }
    else if(time >= 89 && time < 105 ){
        result1000=4;
    }
    else if(time >= 105 && time < 116 ){
        result1000=5;
    }
    else if(time >= 116 && time < 148 ){
        result1000=6;
    }
    else if(time >= 148){
        result1000=7;
    }
}

int main() {

    int result;
    double time500,time1000;

    while(cin >> time500 >> time1000){
        
        time500m(time500);
        time1000m(time1000);

        if(result500>result1000){
            result=result500;
        }
        else{
            result=result1000;
        }

        switch(result){
        case 0 : cout << "AAA" << endl; break;
        case 1 : cout << "AA" << endl; break;
        case 2 : cout << "A" << endl; break;
        case 3 : cout << "B" << endl; break;
        case 4 : cout << "C" << endl; break;
        case 5 : cout << "D" << endl; break;
        case 6 : cout << "E" << endl; break;
        case 7 : cout << "NA" << endl; break;
        }
        
    }

    return 0;
}

Measured memory_bytes: 1220
#include<stdio.h>
 
int main(void){
 
int s=0,x=0,y=0;
  
scanf("%d",&s);
  
x=s/100;
y=s%100;
  
if(x>=1 && x<=12){
	if(y>=1 && y<=12){
    	printf("AMBIGUOUS");
    }else {
      printf("MMYY");
    	}
	}
  else if(y>=1 && y<=12)
  	{
	printf("YYMM");
	}
  else{
printf("NA");
	}
  
return 0; 
}


Measured memory_bytes: 128
#include <iostream>

int gcd(int, int);
int main()
{
    int n, x, y, ans;
    std::cin >> n >> x >> y;
    ans = abs(x-y);

    while (--n)
    {
        std::cin >> y;
        ans = gcd(ans, abs(x-y));
    }

    std::cout << ans << std::endl;
}

int gcd(int x, int y)
{
    while (y)
    {
        int temp = y;
        y = x % y;
        x = temp;
    }

    return x;
}

Measured memory_bytes: 256
#include<iostream>
#define int long long
using namespace std;
int n,a[101],ans;
void dfs(int x)
{
	if(x==n+1)
	{
		int s=0;
		for(int i=1;i<=n;i++)s+=a[i];
		ans=max(ans,s);
		return;
	}
	if(a[x]<0){
		int b[101]={0};
		for(int i=1;i<=n;i++)b[i]=a[i];
		for(int i=x;i<=n;i+=x)a[i]=0;
		dfs(x+1);
		for(int i=1;i<=n;i++)a[i]=b[i];
	}
	dfs(x+1);
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>n/6;i--)
	{
		int s=0;
		for(int j=i;j<=n;j+=i)s+=a[j];
		if(s>0)continue;
		for(int j=i;j<=n;j+=i)a[j]=0;
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}


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

int main(){
    int a,b;
    char op;
    while(1){
        cin >> a >> op >> b;
        if(op == '?')break;
        
        if(op == '+')cout << a + b << endl;
        else if (op == '-')cout << a - b << endl;
        else if (op == '*')cout << a * b << endl;
        else if(op == '/')cout << a / b << endl;
    }
return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
const long long MOD = 1e9+7;
using namespace std;
#define ll long long
#define ar array

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

	int A,B;
	cin >> A >> B;
	cout << (A-1)*(B-1) << endl;
	return 0;
}


Measured memory_bytes: 3608
n=int(input())
p=list(map(int,input().split()))
x=[i+1 for i in range(n)]
if p==x:print("YES");exit()
for i in range(n):
  for j in range(n):
    if i==j:continue
    p[i],p[j]=p[j],p[i]
    if p==x:print("YES");exit()
    p[i],p[j]=p[j],p[i]
print("NO")

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

const int MAX_N = (int)(1e5 + 5);

using ll = long long int;

int n;
ll a[MAX_N];

int over2;
int just1;
int just0;

int main(void){
  // Here your code !
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld\n", &(a[i]));
  }

  for (int i = 0; i < n; ++i) {
    int cnt = 0;
    while (true) {
      if (a[i] % 2 == 0) {
        a[i] /= 2;
        cnt += 1;
      }
      else {
        if (cnt >= 2) {
          over2 += 1;
        }
        else if (cnt == 1) {
          just1 += 1;
        }
        else {
          just0 += 1;
        }

        break;
      }
    }
  }

  int threshold = (n % 2 == 0) ? n / 2 : (n - 1) / 2;

  if ((just1 > 0 && (just1 + over2 + over2) >= n) || over2 >= threshold) {
    printf("Yes\n");
  }
  else printf("No\n");

  return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <assert.h>
#include <sstream>
#include <string>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater <>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
using namespace std;
using ll = long long;
typedef std::pair<ll,ll> P;
//#include <boost/multiprecision/cpp_int.hpp>
//using bint = boost::multiprecision::cpp_int;



void dfs(int n, string s, char m){
    if (s.size() == n) cout << s << endl;
    else{
        for(char c = 'a';c<=m;c++){
            if (c!=m) dfs(n,s+c,m);
            else dfs(n,s+c,(char) (m+1));
        }
    }
}

int main(){
    int n;
    cin >> n;
    dfs(n,"",'a');
}


Measured memory_bytes: 1536
// abc109_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#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))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int R;
    cin >> R;

    if (R < 1200){
        print("ABC");
    } else if (R < 2800){
        print("ARC");
    } else {
        print("AGC");
    }

    return 0;
}


Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let N: usize = sc.get();
    let mut A: Vec<usize> = sc.vec(N);
    A.sort();
    let mut cum = vec![0; N+1];
    for i in 0..N {
        cum[i+1] = cum[i] + A[i];
    }
    let mut ans = 1usize;
    for i in (0..N).rev() {
        if cum[i] * 2 >= A[i] {
            ans += 1;
        } else {
            break;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 6396
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    const int MAX = 1<<15;
    vector<vector<int> > num(MAX+1, vector<int>(5, 0));
    num[0][0] = 1;
    for(int i=1; i*i<=MAX; ++i){
        for(int j=i*i; j<=MAX; ++j){
            for(int k=1; k<=4; ++k){
                num[j][k] += num[j-i*i][k-1];
            }
        }
    }

    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        int ret = 0;
        for(int i=1; i<=4; ++i)
            ret += num[n][i];
        cout << ret << endl;
    }
}

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

using namespace std;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) (int)a.size()
#define fi first
#define se second
#define ar array
#define forn(i, n) for(int i = 0; i < n ; ++i)


typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int > pii;
typedef vector<pii> vpi;
const ll MOD =1e9+7;

void solve(){
	int n; cin >> n;
	vi a(n); forn(i, n) cin >> a[i];
	map<int,int> mp1 , mp2;
	int ans=n;
	for(int i=0, j = 1; i < n-1 && j < n; i+=2, j+=2){
		mp1[a[i]]++;
		mp2[a[j]]++;
	}
	set<ar<int,2>> s, t;
	for(auto x: mp1)
		s.insert({x.se,x.fi});
	for(auto x: mp2)
		t.insert({x.se,x.fi});
	
	int od = (*s.rbegin())[1],od1=0,ev1=0;
	if(sz(s)>1)
		od1 = (*++s.rbegin())[1];
	int ev = (*t.rbegin())[1];
	if(sz(t) > 1)
		ev1 = (*++t.rbegin())[1];
	if(od != ev){
		ans = n - mp1[od]-mp2[ev];
		cout<<ans;return;
	}
	if(od == ev && sz(s) < 2 && sz(t) < 2){
		cout << n/2;return;
	}
	ans = min(n - mp1[od]-mp2[ev1], n-mp1[od1]-mp2[ev]);
	cout << ans;
}
int main(){
	int t=1;
	//cin >> t;
	while(t--){
		solve();
		cout <<'\n';
	}
}


Measured memory_bytes: 12852
#include <iostream>

int main(){
  int N,p[50];
  int flag=0;
  	scanf("%d",&N);
	for(int i=1;i<=N;i++){
    	scanf("%d",&p[i]);
      if(p[i]!=i){
      	flag++;
      }
    }
  	if(flag>=3){
    	printf("NO");
    }
  else{
  	printf("YES");
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  int ab = a * b;
  
  if (ab % 2 == 0){
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 3648
#include<stdio.h>
#define MAX 100
#define INFTY 10000001

int main(){
  int i, j, n;
  int M[MAX][MAX];
  int k, c, u, v;
  int minv;
  int d[MAX];
  int vis[MAX];

  scanf("%d", &n);
  
  for (i = 0; i< n; i++){
    for (j = 0; j < n; j++){
      M[i][j] = INFTY;
    }
  }

  for (i = 0; i < n; i++){
    scanf("%d %d", &u, &k);
    for (j = 0; j < k; j++){
      scanf("%d %d", &v, &c);
      M[u][v] = c;
    }
  }

  for (i = 0; i < n; i++){
    d[i] = INFTY;
    vis[i] = 0;
  }

  d[0] = 0;

  while(1){
    minv = INFTY;
    u = -1;
    for (i = 0; i < n; i++){
      if (minv > d[i] && !vis[i]){
        u = i;
        minv = d[i];
      }
    }
    if (u == -1) break;
    vis[u] = 1;
    for (v = 0; v < n; v++){
      if (!vis[v] && M[u][v] != INFTY){
        if (d[v] > d[u] + M[u][v]){
          d[v] = d[u] + M[u][v];
        }
      }
    }
  }

  for (i = 0; i < n; i++){
    printf("%d %d\n", i, (d[i]==INFTY?-1:d[i]));
  }

  return 0;
}



Measured memory_bytes: 2088
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define int ll
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a*b/gcd(a,b);
}

int f(string s){
    int ret = 0;
    rep(i,s.size()){
        ret *= 10;
        ret += s[i]-'0';
    }
    return ret;
}

signed main(void) {
    int i,j;
    string s;
    cin >> s;
    int n = s.size();
    int num = f(s);
    vi v(10);
    rep(i,10)v[i] = i;
    string ans;
    int diff = 0;
    int MAX = 1;
    rep(i,n)MAX *= 10;
    do{
        string t = "";
        rep(i,n)t += v[i]+'0';
        int p = abs(num-f(t));
        int tmp = min(p, MAX-p);
        if(tmp > diff){
            diff = tmp;
            ans = t;
        }
    }while(next_permutation(all(v)));
    cout << ans << endl;
}



Measured memory_bytes: 3196
#include<stdio.h>
#include<string.h>
int main()
{
    char s[100000];
    scanf("%s", s);
    int l,p=0;
    l=strlen(s);
    for(int i=0;i<l-1;i++)
    {
        if(s[i]!=s[i+1])
        {
            p++;
        }
    }
    printf("%d\n", p);
    return 0;
}


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = 1e9+7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

vector<VI> r;
VI ks;

void rec(int s, int p, int& d){
	if(ks[s] !=-1) return;
	ks[s] = d++; 
	for(auto x: r[s]) if(x != s){
		rec(x, s, d);
	}

}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	r.resize(n);
	rep(i, n-1){
		int a,b;
		cin >>a >>b;
		r[a-1].emplace_back(b-1);
		r[b-1].emplace_back(a-1);
	}
	VI c(n);
	rep(i, n) cin >>c[i];
	sort(c.rbegin(), c.rend());
	ks.assign(n, -1);
	int d = 0;
	rec(0,-1, d);
	ll ans=0;
	rep(i,n) for(auto x: r[i]) if(i>x)ans += min(c[ks[i]], c[ks[x]]);
	cout << ans<<"\n";
	for(auto x : ks) cout<<c[x] <<" ";
	cout<<endl;
	return 0;
}


Measured memory_bytes: 1408
#agc027a
import sys

n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
b=[]
b.append(a[0])
for i in xrange(1,n):
 b.append(b[i-1]+a[i])
for i in xrange(n):
 if b[i]==x:
  print i+1
  sys.exit()
 elif b[i]>x:
  print i
  sys.exit()
print n-1


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

int main()
{
	int H = 0, A = 0, ans = 0;
	
	std::cin >> H >> A;

	int i = 0;
	while (H - i * A > 0)
	{
		i++;
	}
	
	ans = i;

	std::cout << ans << std::endl;

	return 0;
}

Measured memory_bytes: 384
import itertools
n,m=map(int,input().split())
KS=[]
for i in range(m):
  ks=[int(i) for i in input().split()]
  KS.append(ks)
P=[int(i) for i in input().split()]
ans=0
for Key in itertools.product(range(2),repeat=n):
  Key=list(Key)
  chk=True
  for i in range(m):
    on=0
    for j in range(KS[i][0]):
      on+=Key[KS[i][j+1]-1]
    if on%2!=P[i]:
      chk=False
  if chk==True:
    ans+=1
print(ans)

Measured memory_bytes: 3064