akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

template<typename T, typename U>
struct segtree {
	ll n, H;
	
	vector<T> value;
	vector<U> prop;
	vector<bool> dirty;

	segtree<T,U>(vector<T> leaves): n(sz(leaves)) {
		H = 32 - __builtin_clz(2*n-1);

		value.resize(2*n);
		copy(all(leaves),begin(value)+n);
		FORD(i,1,n) value[i] = value[2*i] + value[2*i+1];
		
		dirty.resize(n,false);
		prop.resize(n);
	}

	void apply(ll i, U &upd) {
		value[i] = upd(value[i]);
		if (i < n) prop[i] = prop[i] + upd, dirty[i] = true;
	}

	void rebuild(ll i) {
		for (i /= 2; i; i /= 2) value[i] = prop[i](value[2*i] + value[2*i+1]);
	}

	void propagate(ll i) {
		FORD(h,1,H+1) if (dirty[i >> h]) {
			ll j = i >> h;
			apply(2*j,prop[j]), apply(2*j+1,prop[j]);
			prop[j] = U(), dirty[j] = false;
		}
	}

	void update(ll i, ll j, U upd) {
		if (i == j) return;
		i += n, j += n;
		propagate(i), propagate(j-1);
		for (ll l = i, r = j; l < r; l /= 2, r /= 2) {
			if (l & 1) apply(l++,upd);
			if (r & 1) apply(--r,upd);
		}
		rebuild(i), rebuild(j-1);
	}
	
	T query(ll i, ll j) {
		i += n, j += n;
		propagate(i), propagate(j-1);
		T resl, resr;
		for (; i < j; i /= 2, j /= 2) {
			if (i & 1) resl = resl + value[i++];
			if (j & 1) resr = value[--j] + resr;
		}
		return resl + resr;
	}
};

struct node {
	ll x = oo;
	node operator+(node n) { return {min(x,n.x)}; }
	node operator()(node n) { return {min(x,n.x)}; }
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n, q;
	cin >> n >> q;
	
	segtree<node,node> H(vector<node>(n, {n-1}));
	segtree<node,node> V(vector<node>(n, {n-1}));

	ll res = (n-2)*(n-2);
	while (q--) {
		ll type; cin >> type;
		auto &h = (type == 1 ? H : V);
		auto &v = (type == 1 ? V : H);
		ll x; cin >> x;
		x--;
		ll y = v.query(x,x+1).x;
		h.update(0,y,{x});
		res -= y-1;
//		cerr << x << " " << y << endl;
	}
	cout << res << endl;
}



Measured memory_bytes: 14152
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <cmath>
#include <iomanip>
#include <stdexcept>
#include <utility>
// #include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; i++)
#define rep1(i,h) for(int i = 0; i <= h; i++)
#define rep2(i,n,h) for(int i = n; i < h; i++)
#define rep3(l,n,h) for(int l = n; i <= h; i++)
using namespace std;



int main() {
    int m ,d,n, h;
    cin >> m >> d >> n >>h;
    if(m != n) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <functional>
using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int l = s.size() - 2;
    cout << s[0] << l << s[l+1] << endl;
	return 0;
}

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

int main(){
	int n;
	cin >> n;
	long long hasil=1;
	int yes=0;
	long long res=1;
	while(n--){
		long long inp;
		cin >> inp;
		//cout << LONG_LONG_MAX/res << "\n";
		if((res!=0 && inp>(LONG_LONG_MAX/res)) || (inp!=0 && res>(LONG_LONG_MAX/inp))) {
			yes=1;
			//cout << "ya\n";
		}
		else{
			hasil=res*inp;
			res=hasil;
			if(hasil==0) yes=0;
			//cout << "nggak\n";
		}
	}
	if(yes==1) cout << "-1\n";
	else if(hasil>1000000000000000000) cout << "-1\n";
	else cout << hasil << "\n";
}

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

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniqueV(x)          \
  sort(x.begin(), x.end()); \
  x.erase(unique(x.begin(), x.end()), x.end());
#define debug(x) cerr << #x << ": " << x << '\n'
#define debug2(x, y) cerr << "(" << #x << ", " << #y << ") = " \
                          << "(" << x << ", " << y << ")" << '\n'

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

const long long INF = 3e18 + 12;
const int inf = 1e9;

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

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

  string s;
  cin >> s;

  ll n = s.size();

  ll num = 0;
  ll ans = 0;

  rep(i, n) {
    if (s[i] == 'B') {
      num++;
    } else {
      ans += num;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
int a[N],fa[N],vis[N],mi[N];
typedef pair<int,int> pii;
priority_queue<pii, vector<pii >, greater<pii > >Q;
int find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>a[i],fa[i]=i,mi[i]=INF;
    for(int i=0,u,v; i<m; i++)
    {
        cin>>u>>v,u=find(u),v=find(v);
        if(u!=v)fa[u]=v;
    }
    for(int i=0; i<n; i++)find(i);
    for(int i=0; i<n; i++)
        mi[fa[i]]=min(a[i],mi[fa[i]]),Q.push(make_pair(a[i],fa[i]));
    sort(fa,fa+n);
    int tn=unique(fa,fa+n)-fa;
    if(tn==1)
        cout<<0;
    else if((tn-1)*2>n)
        cout<<"Impossible";
    else
    {
        long long s=0;
        for(int i=0; i<tn; i++)
            s+=mi[fa[i]];
        while(!Q.empty())
        {
            if(tn==2)break;
            pii t=Q.top();
            Q.pop();
            if(!vis[t.second])
            {
                vis[t.second]=1;
                continue;
            }
            s+=t.first,--tn;
        }
        cout<<s;
    }
    return 0;
}


Measured memory_bytes: 2676
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

ll a[18][18];
ll G[(1<<17)];
ll dp[(1<<17)];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=0;i<(1<<n);i++)
	{
		G[i]=0;
		for(int j=0;j<n;j++)
		{
			for(int k=j+1;k<n;k++)
			{
				if(i&(1<<j))
				{
					if(i&(1<<k))
					{
						G[i]+=a[j][k];
					}
				}
			}
		}
	}
	dp[0]=0;
	for(int i=1;i<(1<<n);i++)
	{
		dp[i]=-ll(1e18);
		for(int j=i;;j=(j-1)&i)
		{
			dp[i]=max(dp[i],G[j]+dp[i^j]);
			if(j==0) break;
		}
	}
	cout<<dp[(1<<n)-1]<<'\n';
}


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

using namespace std;



int H, W;
vector<vector<char> > s;

vector<vector<int> > dis;



void move(int x, int y, int d){
  
    
    
    
    
    
    if (x-1 >= 0 && s[y][x-1] == '.' && dis[y][x-1] > d+1) {
        dis[y][x-1] = d+1;
        move(x-1, y, d+1);
    }
    if (x+1 <= W-1 && s[y][x+1] == '.' && dis[y][x+1] > d+1) {
        dis[y][x+1] = d+1;
        move(x+1, y, d+1);
    }
    if (y-1 >= 0 && s[y-1][x] == '.' && dis[y-1][x] > d+1) {
        dis[y-1][x] = d+1;
        move(x, y-1, d+1);
    }
    if (y+1 <= H-1 && s[y+1][x] == '.' && dis[y+1][x] > d+1) {
        dis[y+1][x] = d+1;
        move(x, y+1, d+1);
    }
    
    
    
    
    
    
    
}



int main(){
    
    cin >> H >> W;
    
    s.assign(H, vector<char>(W, '.'));
    dis.assign(H, vector<int>(W, 100000));

    int no = 0;
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> s[i][j];
            if (s[i][j] == '#') {
                no += 1;
            }
        }
    }
    
    
    move(0, 0, 1);
    
    
    if (dis[H-1][W-1] != 100000) {
        cout << H * W - no - dis[H-1][W-1] << endl;
    }else{
        cout << -1 << endl;
    }
    
    
}





Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr double PI = 3.1415926535897932;
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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int N; cin >> N;
	vector<int>vec(N);
	rep(i, 0, N)cin >> vec[i];
	int ans = 1e9;
	rep(i, -110, 110) {
		int cnt = 0;
		rep(j, 0, N) {
			int a = i - vec[j];
			cnt += a * a;
		}
		chmin(ans, cnt);
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 3616
N = int(input())
csf = []
t = 0
for _ in range(N - 1):
    csf.append(list(map(int, input().split())))
# print(csf)
for i in range(N - 1):
    t = 0
    for j in range(i, N - 1):
        if t < csf[j][1]:
            t = csf[j][1]
        if t % csf[j][2] == 0:
            t += csf[j][0]
        else:
            t += csf[j][2] - t % csf[j][2]
            t += csf[j][0]
    print(t)
print(0)


Measured memory_bytes: 3188
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Set<Integer> set = new HashSet<>();
		int cnt = 0;
		int n = 3;
		for (int i = 0; i < n; i++) {
			if (!set.add(sc.nextInt()))
				continue;
			cnt++;
		}
		System.out.println(cnt);
		sc.close();
	}
}


Measured memory_bytes: 19796
#include<cstdio>
using namespace std;
typedef unsigned long long ullong;

//?????°????¨????????????????????????????????????????
ullong pow(ullong x,ullong n, ullong M){
	ullong tmp=1;	//n=0??§tmp=1
	if (n>0) {
	tmp = pow((x*x)%M, n/2, M);
	if (n%2!=0) tmp = (tmp*x)%M;
	}
	
	return tmp;
}

int main(){
	ullong m,n;
	scanf("%lld %lld", &m,&n);

	printf("%lld\n", pow(m,n, 1000000007));
	return 0;
}

Measured memory_bytes: 2728
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define loop(k) rep(author_is_masa,k)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const long long INF = 1e18+10;

/*--------------------------------------------------------------------*/

signed main(){
	string s;cin>>s;
	int ans=0;
	if(s[0]=='R'&&s[1]==s[0]&&s[1]==s[2]) cout<<3<<endl;
	else if(s[1]=='R'&&(s[0]==s[1]||s[1]==s[2])) cout<<2<<endl;
	else if(s[0]=='R'||s[1]=='R'||s[2]=='R') cout<<1<<endl;
	else cout<<0<<endl;

	return 0;
}



Measured memory_bytes: 3624
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	int n, k;
	cin >> n >> k;
	int mini = 0;
	for(int i = 0; i < n; i++){
		int a;
		cin >> a;
		if(a == 1) mini = i;
	}
	int ans = 0;
	int i;
	for(i = 0; i < mini; i += k - 1){
		// cout << i << endl;
		ans++;
	}
	i++;
	for(i = i; i < n; i += k - 1){
		// cout << i << endl;
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
inline int Readin() {
	register int K = 0 , F = 1 ; register char C = getchar() ;
	while( C < '0' or C > '9' ) F = C == '-' ? -1 : 1 , C = getchar() ;
	while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ;
	return F * K ;
}
const int MaxN = 10 + 5 ;
int N , A[MaxN] ;
int main() {
	N = Readin() ;
	for(register int i = 0 ; ++i <= N ; A[i] = Readin() ) ;
	sort( A + 1 , A + 1 + N ) ;
	A[N] >>= 1 ;
	for(register int i = 0 ; ++i <= N ; A[0] += A[i] ) ;
	return not printf( "%d\n" , A[0] ) ;
}

Measured memory_bytes: 256
n=int(input())
xyh=[]
for i in range(n):
    xyh1=[int(i) for i in input().split()]
    xyh.append(xyh1)
xyh.sort(key=lambda x: x[2])
xm,ym,hm=xyh[-1]
for cx in range(101):
    for cy in range(101):
        H=hm+abs(xm-cx)+abs(ym-cy)
        if all(h==max(H-abs(x-cx)-abs(y-cy),0) for x,y,h in xyh):
            print(cx, cy, H)
            exit()

Measured memory_bytes: 3064
package main

import ("fmt"
	    "sort")

func scanNums(len int) (nums []int) {
    var num int
    for i := 0; i < len; i++ {
        fmt.Scan(&num)
        nums = append(nums, num)
    }
    return
}

func main() {
	var N int
	fmt.Scan(&N)

	nums := scanNums(N)

	sort.Ints(nums)
	a := nums[len(nums)/2]
	b := nums[len(nums)/2 - 1]
	fmt.Println(a - b)
}


Measured memory_bytes: 5504
/*
    STARK_BOY
*/
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repe(i,a,b) for(ll i=a;i<=b;i++)
#define bac(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long ll;
typedef vector< ll > vi;
typedef vector<pair<ll,ll> > vpii;
typedef pair<ll,ll> pii;
#define all(c) c.begin(),c.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setbitc(x) __builtin_popcount(x)
#define init(x,a) memset(x,a,sizeof(x))
#define PI           3.14159265358979323846  /* pi */
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());


const int nax=3005;
const int MOD=1e9+7;
int dp[nax][nax];
int n;
string s;

void add_self(int &a, int b)
{
	a=(a+b)%MOD;
}

ll sub(ll a, ll b){return (a-b+MOD)%MOD;}
ll add(ll a, ll b){return (a+b)%MOD;}
ll mul(ll a, ll b){return (a*b)%MOD;}
int main()
{
    ios
    int ti=1;
    //cin>>ti;
    while(ti--)
    {
		cin>>n>>s;

		dp[1][1]=1;

		rep(pos,2,n+1)
		{
			vi pre(pos,0);
			rep(i,1,pos)pre[i]=add(pre[i-1],dp[pos-1][i]);

			rep(last,1,pos+1)
			{
				int L,R;
				if(s[pos-2]=='>')
				{
					L=last,R=pos-1;
				}
				else
				{
					L=1,R=last-1;
				}

				add_self(dp[pos][last],sub(pre[R],pre[L-1]));

			}
		}
		int ans=0;
		rep(i,1,n+1)add_self(ans,dp[n][i]);

		cout<<ans<<endl;
    }
    return 0;
        
}

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

#define fti(i, x, y) for(int i = (x), _y = (y); i <= _y; ++ i)
#define ftd(i, x, y) for(int i = (x), _y = (y); i >= _y; -- i)
#define ll long long

using namespace std;

const int N = 1e5 + 2;
typedef pair <int, int> ii;
int n;
ii a[N];

void inp()
{
    scanf("%d", &n);
    fti(i, 1, n) scanf("%d", &a[i].first), a[i].second = i;
}

void proc()
{
    sort(a + 1, a + n + 1);
    fti(i, 1, n) printf("%d ", a[i].second);
}

int main()
{
    inp();
    proc();
    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; ++i)
using ll = long long;
using P = pair<int,int>;
// auto mod int
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
mint dp[200001];
int main() {
   int n,k;cin>>n>>k;
   vector<P> LR;
   rep(i,k){
      int L,R;cin>>L>>R;
      LR.push_back({L,R});
   }
   dp[1]=mint(1);
   dp[2]=mint(-1);
   for (int i = 1; i <= n; i++){
      for (auto &&j : LR){
         if(i+j.first<=n)dp[i+j.first]+=dp[i];
         if(i+j.second+1<=n)dp[i+j.second+1]-=dp[i];
      }
      dp[i+1]+=dp[i];
   }
   cout<<dp[n]<<endl;
}

Measured memory_bytes: 5180
#include<stdio.h>
int main(void){
	char b;
	scanf("%c",&b);
	switch(b){
		case 'A':
		printf("T");
        break;
		case 'G':
		printf("C");
        break;
		case 'C':
		printf("G");
        break;
		default:
		printf("A");
		break;
	}
	return 0;
}

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

int main() {
  int h, w;
  cin >> h >> w;

  h += 2;

  vector<string> pic(h);

  for (int i = 0; i < h; i++) {
    if ((i == 0) || (i == h - 1)) {
      string s = "";
      for (int j = 0; j < w + 2; j++) {
        s += '#';
      }
      pic.at(i) = s;
    } else {
      string s = "#";
      string input;
      cin >> input;
      s += input + "#";
      pic.at(i) = s;
    }
    cout << pic.at(i) << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
    
#define N 36
    
typedef struct{
  char a;
  int value;
}Card;
    
int main()
{
    
  int i,j,n,min,flag=0;
  Card c[N],b[N],n1,n2;
      
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf(" %c%d",&c[i].a,&c[i].value);
    b[i].a=c[i].a;
    b[i].value=c[i].value;
  }
    
  for(i=0;i<n-1;i++){
    for(j=n-1;j>i;j--){
      if(c[j].value<c[j-1].value){
   
    n1=c[j];
    n2=c[j-1];
      c[j]=n2;
    c[j-1]=n1;
      }
    }
  }
    
        
    
  for(i=0;i<n;i++){
    min=i;
    for(j=i;j<n;j++){
      if(b[j].value<b[min].value){
    min=j;
      }
    }
   
   
    n1=b[i];
    n2=b[min];
    b[i]=n2;
    b[min]=n1;
  }
    
    
  for(i=0;i<n-1;i++){
    printf("%c%d ",c[i].a,c[i].value);
  }
  printf("%c%d\n",c[n-1].a,c[n-1].value);
  printf("Stable\n");
     
  for(i=0;i<n-1;i++){
    printf("%c%d ",b[i].a,b[i].value);
  }
  printf("%c%d\n",b[n-1].a,b[n-1].value);
       
  for(i=0;i<=n-1;i++){
    if(c[i].a!=b[i].a){
      flag=1;
    }
  }
     
  if(flag==1) printf("Not stable\n");
  else printf("Stable\n");
      
  return 0;
}

Measured memory_bytes: 608
package com.example.alds1.two

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val a = IntArray(n)
    for (i in 0 until n) {
        a[i] = sc.nextInt()
    }
    bubbleSort(a)
}

fun bubbleSort(a: IntArray) {
    var c = 0
    for (i in a.size - 1 downTo 0) {
        for (j in 1..i) {
            if (a[j - 1] > a[j]) {
                val tmp = a[j]
                a[j] = a[j - 1]
                a[j - 1] = tmp
                c++
            }
        }
    }
    println(a.joinToString(" "))
    println(c)
}




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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a==b){
        cout << c << endl;
    }else if(b==c){
        cout << a << endl;
    }else {
        cout << b << endl;
    }
    return 0;
}


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

int main() {
  int N, res=0, tmp_max=0;
  cin >> N;
  int H;

  for (int i=0; i<N; i++) {
    cin >> H;
    if(tmp_max<=H) {
      res++;
      tmp_max = H;
    }
  }
  cout << res;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  vector<int> ans(N);
  
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;
    
    ans.at(A-1) = i + 1;
  }
  
  for (int j = 0; j < N; j++) {
    cout << ans.at(j) << " ";
  }
  
  cout << endl;
  
}

Measured memory_bytes: 1152
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;	
	
int main()
{
	int n,s1=0,s2=0,min=10000000;
	
	cin >> n;
	
	vector<int> v(n);
	
	for(int i=0;i<n;i++){
		cin >> v[i];
		s2 += v[i];
	}
	
	for(int i=0;i<n-1;i++){
		s1 += v[i];
		s2 = s2 - v[i];
		if(min >= abs(s2-s1)) min = abs(s2-s1);
	}
	
	cout << min << endl;
	
	
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  int p;
  int ans=m;
  int s=m;
  int a,b;
  bool h=true;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    s += (a-b);
    if(s<0){
      cout << 0 << endl;
      h = false;
      break;
    }
    if(ans<s) ans = s;
  } 
  if(h) cout << ans << endl;
  return 0;
}
 

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define Ans(f, y, n) if(f) cout << y << endl; else cout << n << endl;
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i, v.size()){ cout << v[i] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl;}
#define pb push_back
#define int long long
#define INF 1000000000000000000

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

template<typename T> void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }

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

int mod = 1000000007;
//int mod = 998244353;
#define Add(x, y) x = (x + (y)) % mod
#define Mult(x, y) x = (x * (y)) % mod
#define AddMult(x, y, z) x = (x + (y) * (z)) % mod



signed main(){

    int H, W, h, w; cin >> H >> W >> h >> w;
    cout << H * W - h * W - w * H + h * w << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int n, m, n_c, m_c;
  scanf("%d %d", &n, &m);
  n_c = n * (n-1) / 2;
  m_c = m * (m-1) / 2;
  printf("%d", n_c + m_c); 
}

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

typedef long long ll;

const int MAXW = 1e9 + 5;
const int MAXV = 1e5 + 5;
const int MAXN = 1e2 + 5;
const int INF = 0x3f3f3f3f;

int N, W, w[MAXN], v[MAXN], d[MAXN][MAXV];

int main() {
    cin >> N >> W;
    int V = 0;
    for (int i = 1; i <= N; ++i) {
        cin >> w[i] >> v[i];
        V += v[i];
    }
    memset(d, INF, sizeof(d));
    int ans = 0;
    d[0][0] = 0;
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j <= V; ++j) {
            if (j >= v[i]) d[i][j] = min(d[i - 1][j], d[i - 1][j - v[i]] + w[i]);
            else d[i][j] = d[i - 1][j];
        }
    for (int j = V; j >= 0; --j) if (d[N][j] <= W) {
        ans = j;
        break;
    }
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 41216
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<cctype>
#define ld long double
#define ll long long int
#define ull unsigned long long int
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long INF=1LL<<60;


int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int i,a,b;
	bool ch=true;;
	string s;
	
	cin>>a>>b>>s;
	for(i=0;i<s.length();i++)if(i!=a&&(s[i]<'0'||s[i]>'9'))ch=false;
	if(ch&&s[a]=='-')cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    string s;
    getline(cin, s);  //1行読み込む
        for(int i = 0; i < s.size(); i++){
            char c = s[i];
            if ('A' <= c && c <= 'Z'){
                //c = tolower(c);
                c = c + 32;
            }
            else if('a' <= c && c <= 'z'){
                c = c - 32;
            }
            cout << c ;
    }
    cout << endl;
}


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

using namespace std;

int tab[200007];

int main()
{
    long long int n, i, s=0, w;
    cin >> n;
    for(i=0; i<n; i++){
        cin >> tab[i];
        s=s^tab[i];
    }
    for(i=0; i<n; i++){
        w=s^tab[i];
        cout << w;
        if(i!=n-1){
            cout << ' ';
        }
        else{
            cout << '\n';
        }
    }
    return 0;
}


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

int n;
int lim;
int seg[1 << 20];

int main() {
  scanf("%d", &n);
  lim = 1 << n;
  for (int i=0; i<lim; i++) scanf("%d", &seg[lim-1+i]);
  for (int i=lim-2; i>=0; i--) {
    if (seg[i*2+1] == seg[i*2+2]) seg[i] = seg[i*2+1];
    else seg[i] = abs(seg[i*2+1]-seg[i*2+2]);
  }
  printf("%d\n", seg[0]);
}


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

int main(){
	int n ; cin >> n ;
	vector<int> d(n) ;
	for(int i=0;i<n;i++) cin >> d.at(i) ;
	sort(d.begin(),d.end()) ;
	cout << d.at(n/2)-d.at(n/2-1) << endl ;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
using namespace std;
char s[105];
bool check(int l,int r)
{
    for(int i=l,j=r;i<=j;i++,j--)
        if(s[i]!=s[j]) return 0;
    return 1;
}
int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    if(check(1,(len-1)/2)&&check((len+3)/2,len)&&check(1,len)) printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 128
main = do
  line <- getLine
  let 
    n = read $ head $ words line :: Int
    call i
      | i > n           = []
      | (mod i 3) == 0  = i : call (i+1)
      | otherwise       = include_3 i i
    include_3 x i 
      | x == 0          = call (i+1)
      | (mod x 10) == 3 = i : call (i+1)
      | otherwise       = include_3 (div x 10) i
    in putStrLn $ (++) " " $ unwords $ map show $ call 1



Measured memory_bytes: 4004
n = int(input())
d = input()
r = 0
g = 0
b = 0
for i in range(n):
  if d[i] == 'R':
    r += 1
  elif d[i] == 'G':
    g += 1
  else:
    b += 1
ans = r * g * b
for i in range(n):
  for j in range(i+1,n):
    if (i+j) % 2 == 1:
      continue
    k = (i+j) // 2
    if d[i] != d[j] and d[i] != d[k] and d[j] != d[k]:
      ans -= 1
print(ans)

Measured memory_bytes: 68116
#include <cstdio>
#include <queue>
#include <cctype>
#include <cstring>
#include <cassert>

using namespace std;

struct state {
  int x,y,u,t,c;
  state(){}
  state(int x,int y,int u,int t,int c):x(x),y(y),u(u),t(t),c(c){}
};

int cost[20][20][1<<8][100];
char g[20][20],gt[20][20];
int n,v[8],d[8],s[8],e[8];
int w,h;
int dx[]={0,1,0,-1,0},dy[]={1,0,-1,0,0};

int main(void)
{
  for(;;) {
    scanf("%d%d",&w,&h); if(w+h == 0)break;
    int x,y; x = y = -1;
    for( int i = 0; i < h; i++ ) {
      for( int j = 0; j < w; j++ ) {
        scanf(" %c",g[i]+j);
        if( g[i][j] == 'P' ) {
          g[i][j] = '.';
          x = j;
          y = i;
        }
      }
    }
    memcpy(gt,g,sizeof(gt));
    for( int i = 0; i < h; i++ ) {
      for( int j = 0; j < w; j++ ) {
        if( isdigit(g[i][j]) ) {
          g[i][j] = '#';
        }
      }
    }
    assert(x>=0 && y>=0);
    scanf("%d",&n);
    int id[10],ct=0; memset(id,-1,sizeof(id));
    for( int i = 0; i < n; i++ ) {
      scanf("%d%d%d%d",v+i,d+i,s+i,e+i);
      if( id[v[i]] < 0 ) {
        id[v[i]] = ct;
        for( int j = 0; j < h; j++ ) {
          for( int k = 0; k < w; k++ ) {
            if( gt[j][k] == v[i]+'0' ) g[j][k] = ct+'0';
          }
        }
        ct += 1;
      }
      v[i] = id[v[i]];
    }
    int res = 0;
    queue<state> q;
    q.push(state(x,y,0,0,0));
    memset(cost,-1,sizeof(cost));
    while( !q.empty() ) {
      state p = q.front(); q.pop();
      //printf("%d %d %02x %d %d\n",p.x,p.y,p.u,p.t,p.c);
      if( p.t >= 100 ) continue;
      if( res < p.c ) res = p.c;
      for( int i = 0; i < 4; i++ ) {
        x = p.x+dx[i];
        y = p.y+dy[i];
        if( x < 0 || x >= w || y < 0 || y >= h ) continue;
        if( isdigit(g[y][x]) ) {
          int k = g[y][x]-'0';
          if( !(p.u>>k&1) ) {
            for( int j = 0; j < n; j++ ) {
              if( s[j] <= p.t && p.t < e[j] && v[j] == k ) {
                if( cost[p.y][p.x][p.u|1<<k][p.t] < p.c+d[j] ) {
                  cost[p.y][p.x][p.u|1<<k][p.t] = p.c+d[j];
                  q.push(state(p.x,p.y,p.u|1<<k,p.t,p.c+d[j]));
                }
              }
            }
          }
        }
        if( g[y][x] == '.' && cost[y][x][p.u][p.t+1] < p.c ) {
          cost[y][x][p.u][p.t+1] = p.c;
          q.push(state(x,y,p.u,p.t+1,p.c));
        }
      }
    }
    printf("%d\n",res);
  }
  return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define out(n) cout << n << '\n'
#define rep(i, n) for (ll i = 0; i < (n); i++)
const int inf = 1000000000;
const ll linf = (ll)inf * (ll)inf;
void solve()
{
    ll n;
    in(n);
    string s = "";
    int count = 0;
    while (n > 0)
    {
        n -= 1;
        int k = n % 26;
        char c = 'a' + k;
        s = c + s;
        n /= 26;
    }
    out(s);
}

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

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  int n; cin >> n;
  int i; cin >> i;
  COUT(n-i+1);
  return 0;
}


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

const int maxn = 1e5+10;
int n,m,x,y,ans;
vector<int>G[maxn];
int dp[maxn];

int solve(int a){
    if(dp[a] != -1)
        return dp[a];
    int v = 0;
    for(int b : G[a]){
        v = max(v,solve(b)+1);
    }
    dp[a] = v;
    return dp[a];
}




int32_t main()
{
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i<=m;i++){
        cin >> x >> y;
        G[x].push_back(y);
    }

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



    int ans = 0;
    for(int i = 1;i<=n;i++){
       ans = max(solve(i),ans);
    }


    cout << ans << endl;
}


Measured memory_bytes: 11496
def comb(n, k):
  if n < k:
    return 0
  else:
    res = 1
    _n = n
    for _k in range(1, k+1):
      res *= _n
      res //= _k
      _n -= 1
    
    return res
    

N = input()
n = len(N)
K = int(input())

ans = comb(n-1, K) * (9**K)

if K == 1:
  ans += int(N[0])
elif K == 2:
  ans += comb(n-1, 1) * 9 * (int(N[0])-1)
  N = str(int(N) - int(N[0])*(10**(n-1)))
  n = len(N)
  ans += comb(n-1, 1) * 9
  ans += int(N[0])
else: # K == 3
  ans += comb(n-1, 2) * (9**2) * (int(N[0])-1)
  N = str(int(N) - int(N[0])*(10**(n-1)))
  n = len(N)
  ans += comb(n-1, 2) * (9**2)
  ans += comb(n-1, 1) * 9 * (int(N[0])-1)
  N = str(int(N) - int(N[0])*(10**(n-1)))
  n = len(N)
  ans += comb(n-1, 1) * 9
  ans += int(N[0])

print(ans)

Measured memory_bytes: 3064
//itp1_7-b
#include <iostream>
using namespace std;

int main(){
 int n,x;
 while(true){
  int cnt=0;
  cin>>n>>x;
  if(n==0 && x==0) break;
  for(int i=1;i<n-1;i++)
   for(int j=i+1;j<n;j++)
    for(int k=j+1;k<=n;k++){
     if(i+j+k==x) cnt++;
    }
  cout<<cnt<<endl;
  }
 return 0;
}

Measured memory_bytes: 1160
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>


typedef long double ld;
typedef long long ll;

using namespace std;

#define MAXN (1 << 10)

vector<vector<int> > v;
vector<int> rows;

int ans[MAXN][MAXN];

int h, w, k;

void fillh(int sx, int fx, int y, int color) {
	//cerr << sx << " " << fx << " " << y << " " << color << endl;
	for (int i = sx; i <= fx; i++) {
		ans[y][i] = color;
	}
}

void fillv(int x, int y, int color, int dx) {
	x += dx;
	while ((x >= 1) && (x <= h) && (!ans[x][y])) {
		ans[x][y] = color;
		x += dx;
	}
}

void print() {
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
}

int main() {
	cin >> h >> w >> k;
	for (int i = 1; i <= h; i++) {
		string s;
		cin >> s;
		vector<int> pos;
		pos.push_back(0);
		for (int j = 1; j <= w; j++) {
			if (s[j - 1] == '#') {
				pos.push_back(j);
			}
		}
		pos.push_back(w + 1);
		if (pos.size() > 2) {
			v.push_back(pos);
			rows.push_back(i);
		}
	}

	int color = 0;

	for (int i = 0; i < v.size(); i++) {
		for (int j = 1; j <= (int)v[i].size() - 2; j++) {
			color++;
			if (j < (int)v[i].size() - 2) {
				fillh(v[i][j - 1] + 1, v[i][j], rows[i], color);		
			} else {
				fillh(v[i][j - 1] + 1, v[i][j + 1] - 1, rows[i], color);
			}
		}
	}

	//print();

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (ans[i][j]) {
				fillv(i, j, ans[i][j], -1);
			}
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (ans[i][j]) {
				fillv(i, j, ans[i][j], 1);
			}
		}
	}

	print();
	return 0;
}


Measured memory_bytes: 5112
#include <bits/stdc++.h>
using namespace std;
int main(){
  string a;
  bool b=false;
  cin>>a;
  if(a.size()%2==0){
    for(int i=0;i<a.size();i+=2){
      if(a.at(i)!='h'){
        b=true;
        break;
      }
      if(a.at(i+1)!='i'){
        b=true;
        break;
      }
    }
  }
  else b=true;
  cout<<(b==true? "No":"Yes")<<endl;
}


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

int main(void)
{
    string a, b;
    cin >> a >> b;
    vector<char> num;
    rep(i, a.size()) num.push_back(a[i]);
    rep(i, b.size()) num.push_back(b[i]);
    vector<int> nums;

    rep(i, num.size()) nums.push_back(num[i]-'0');

    int number = 0;
    rep(i, nums.size()) {
        number += nums[i];
        number *= 10;
    }
    number /= 10;
    int answer = 0;
    for (int i = 0;i * i<=number;i++) {
        if (i * i == number) answer = 1; 
    }
    if (answer) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    int n;
    cin >> n;
    bool flg = true;
    for( int i = 0; i < n; ++i ) {
        int a;
        cin >> a;
        if( a % 2 != 0 ) flg = false;

    }

    if( flg ) cout << "second";
    else cout << "first";
    cout << endl;
    return 0;
}


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

int main(){
  int n;
  int s;
  int cnt = 0;

  scanf("%d %d", &n, &s);

  while(n > 0){
    cnt++;
    n -= s;
  }

  printf("%d\n", cnt);

  return 0;
}


Measured memory_bytes: 128
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
bool isprime(int n) { //素数判定
    if(n==1)return false;
    if(n==2)return true;
    for(int i = 2;i<=sqrt(n);i++) {
        if(n%i==0) return false;
    }
    return true;
}
/* ----------------------end----------------------- */
#pragma endregion
signed main() {
    int n;cin >> n;
    vi a(n);
    vi rui(n+3);
    rui[0]=0;
    rep(i, n)cin >> a[i];
    sort(all(a));
    rep(i, n) rui[i+1]=a[i]+rui[i];
    int count=0;
    rep1(i, n) {
        if(rui[i]*2>=rui[i+1]-rui[i]) count++;
        else count=0;
    }
    // rep(i, n+1) cout << rui[i] << (i==n?"\n":" "); 
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 4848
import java.util.*;
class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  char c[]=sc.next().toCharArray();
  int n=c.length;
  boolean b=true;
  for(int i=0;i<n/2;i++){
    if(c[i]!=c[n-1-i])b=false;
  }
  for(int i=0;i<(n/2)/2;i++){
    if(c[i]!=c[n/2-i-1])b=false;
  }
  System.out.println(b?"Yes":"No");
}
}


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

int main(){
  string n;
  cin >> n;
  
  if(n[(n.size() - 1)] == '3')cout << "bon" << endl;
  else if(n[(n.size() - 1)] == '0')cout << "pon" << endl;
  else if(n[(n.size() - 1)] == '1')cout << "pon" << endl;
  else if(n[(n.size() - 1)] == '6')cout << "pon" << endl;
  else if(n[(n.size() - 1)] == '8')cout << "pon" << endl;
  else cout << "hon" << endl;
}

Measured memory_bytes: 3620
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値
#include <functional>//sort第三引数greater<型名>()で降順
#include <map>

using namespace std;
using ll = long long int;

int main(){
    int N;cin>>N;
    vector<int> a(N);
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    int ans = 0;
    for(int i=0;i<N;i++){
        if((i+1)%2==1&&a[i]%2==1) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

string s;
int dp[100001][13], MOD = 1e9 + 7;

int main() {
	cin >> s;
	int n = SI(s);
	
	dp[0][0] = 1;
	inc(i, n) {
		bool f = (s[i] != '?');
		inc(j, 13) {
		inc(k, 10) {
			if(f) { k = s[i] - '0'; }
			(dp[i + 1][(10 * j + k) % 13] += dp[i][j]) %= MOD;
			if(f) { break; }
		}
		}
	}
	
	cout << dp[n][5] << endl;
	
	return 0;
}


Measured memory_bytes: 5504
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define All(v) v.begin(),v.end()
typedef pair<int, int> Pii; typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;

int N, M, Q;
vector<int> graph[100000];
vector<Pip> ope;
int dp[100000][11] = {0};

void dfs( int v, int d, int c )
{
  if( !dp[v][d] ) {
    dp[v][d] = c;
    if( d ) {
      dfs( v, d-1, c );
      for(int i=0; i<graph[v].size(); i++) {
	dfs( graph[v][i], d-1, c );
      }
    }
  }
}

main()
{
  cin >> N >> M;
  Rep(i, M) {
    int a, b; 
    cin >> a >> b;
    a--; b--;
    graph[a].pb( b );
    graph[b].pb( a );
  }

  cin >> Q;
  Rep(i, Q) {
    int v, d, c;
    cin >> v >> d >> c;
    v--;
    ope.pb( Pip(v, Pii(d, c)) );
  }

  for(int i=Q-1; i>=0; i--) {
    Pip p = ope[i];
    int v = p.fr, d = p.sc.fr, c = p.sc.sc;
    dfs( v, d, c );
  }

  for(int i=0; i<N; i++) {
    cout << dp[i][0] << endl;
  }
  
}


Measured memory_bytes: 18540
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

P = 10**9 + 7

S = input()
N = len(S)

psumA = [0] + list(accumulate(c == 'A' for c in S))
psumC = [0] + list(accumulate(c == 'C' for c in S))
psumX = [0] + list(accumulate(c == '?' for c in S))
Q = psumX[N]

ans = 0
for i in range(1, N-1):
  if S[i] == 'B':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q, P) % P
    if Q >= 1:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
  if S[i] == '?':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-2, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
    if Q >= 3:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-3, P) % P

print(ans % P)



Measured memory_bytes: 58036
function main(argString) {
  var split = argString.split('\n');
  var input = split[1].split(' ');
  var number = 0;
  while (input.filter(v => v % 2 === 0).length === input.length) {
    number++;
    input = input.map(v => v / 2);
  }
  console.log(number);
}

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

Measured memory_bytes: 7372