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

#define pb push_back
#define mp make_pair
#define size(n) ( int( n.size() ) )
#define sqr(n) ( (n) * (n) )
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 5;
int a[N], b[N], c[N], x[N], y[N];

int cmp( int i, int j ){
    return ( a[i] - b[i] < a[j] - b[j] );
}

ll ans = 0, fw[N][4];

ll get( int r, int tp ){
    ll res = 0;
    for ( ; r >= 0; r = ( r & ( r + 1 ) ) - 1 ){
        res += fw[r][tp];
    }
    return res;
}

void add( int i, int val, int tp ){
    for ( ; i < N; i = ( i | ( i + 1 ) ) ){
        fw[i][tp] += val;
    }
}


vector < pair < int, int > > vx, vy;
map < pair < int, int >, int > mx, my;

ll sum( int l, int r, int tp ){
    if ( l > r ){
        return 0;
    }
    ll res = get(r,tp);
    if ( l != 0 ){
        res -= get(l-1,tp);
    }
    return res;
}

ll getsum( int cnt, int tp ){
    int low = 0, high = N, mid;
    while( high - low > 1 ){
        mid = ( high + low ) >> 1;
        if ( sum( mid, N - 1, tp ) >= cnt ){
            low = mid;
        }
        else{
            high = mid;
        }
    }
    return sum( low, N - 1, tp + 1 );
}

int main(){
   // freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int cx, cy, cz;
    scanf("%d %d %d",&cx,&cy,&cz);
    int n = cx + cy + cz;
    ll sumz = 0;
    vector < int > nums;
    for ( int i = 1; i <= n; i++ ){
        scanf("%d %d %d",&a[i],&b[i],&c[i]);
        sumz += c[i];
        nums.pb(i);
    }
    sort( nums.begin(), nums.end(), cmp );
    for ( int i = 0; i < size(nums); i++ ){
        int j = nums[i];
        vx.pb( mp( c[j] - a[j], i ) );
        vy.pb( mp( c[j] - b[j], i ) );
    }
    sort( vx.begin(), vx.end() );
    sort( vy.begin(), vy.end() );
    for ( int i = 0; i < size(vx); i++ ){
        mx[ vx[i] ] = i + 1;
        my[ vy[i] ] = i + 1;
    }
    ll sumx = 0, sumy = 0;
    for ( int i = 0; i < size(nums); i++ ){
        //cout << nums[i] << endl;
        int j = nums[i];
        add( mx[ mp( c[j] - a[j], i ) ], c[j] - a[j], 1 );
        add( mx[ mp( c[j] - a[j], i ) ], 1, 0 );
        sumx += a[j];
    }
    for ( int i = 0; i <= cy - 1; i++ ){
        int j = nums[i];
        sumx -= a[j];
        sumy += b[j];
        add( mx[ mp( c[j] - a[j], i ) ], -( c[j] - a[j] ), 1 );
        add( mx[ mp( c[j] - a[j], i ) ], -1, 0 );
        add( my[ mp( c[j] - b[j], i ) ], ( c[j] - b[j] ), 3 );
        add( my[ mp( c[j] - b[j], i ) ], 1, 2 );
    }
    for ( int i = cy; i <= size(nums) - cx; i++ ){
        ans = max( ans, getsum( size(nums) - i - cx, 0 ) + getsum( i - cy, 2 ) + sumx + sumy );
        int j = nums[i];
        sumx -= a[j];
        sumy += b[j];
        add( mx[ mp( c[j] - a[j], i ) ], -( c[j] - a[j] ), 1 );
        add( mx[ mp( c[j] - a[j], i ) ], -1, 0 );
        add( my[ mp( c[j] - b[j], i ) ], ( c[j] - b[j] ), 3 );
        add( my[ mp( c[j] - b[j], i ) ], 1, 2 );
    }
    cout << ans << endl;
    return 0;
}


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

struct Edge{
	int from, to, cost;
	Edge(int x, int y, int z) : from(x), to(y), cost(z){}
};

vector<long long> d;
vector<Edge> edge;

bool bellmanford(int s, int n){
	d.resize(n, (long long)(-1e18));
	d[s] = 0;

	for(int ix=0; ix<=2*n; ++ix){
		for(auto e : edge){
			if(d[e.from] != (long long)(-1e18) && d[e.from] + e.cost > d[e.to]){
				d[e.to] = d[e.from] + e.cost;
				if(ix > n-1 && e.to == n-1){
					return true;
				}
			}
		}
	}
	return false;
}

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

	for(int i=0; i<m; ++i){
		int a, b, c; cin >> a >> b >> c;
		edge.push_back(Edge(a-1, b-1, c));
	}

	if(bellmanford(0, n)) cout << "inf" << endl;
	else cout << d[n-1] << endl;
}


Measured memory_bytes: 256
n = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

dp_b = [0] * n
j = 0
for i in range(n):
    while j < n:
        if B[i] >= C[j]:
            dp_b[i] = j
            break
        j += 1
    if j == n:
        dp_b[i] = n

for i in range(1, n):
    dp_b[i] = dp_b[i] + dp_b[i - 1]

ans = 0
j = 0
for i in range(n):
    while j < n:
        if A[i] >= B[j]:
            if j == 0:
                break
            else:
                ans += dp_b[j - 1]
                break
        j += 1
    if j == n:
        ans += dp_b[n - 1]

print(ans)

Measured memory_bytes: 24180
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define fr(i,n) for(i=0;i<n;i++)
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 1000000007;
const int nn = 3e5;
#define cc(x) cout << #x << " = " << x << endl
#define dd(x, y) cout << #x << " = " << x << " " << #y << " = " << y << endl
int main(){
        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // int t;
    // cin>>t;
    // while(t--){
    ll i,j,k,l,m,n,x=0,y=0,z=0,w;
    string p,q,s;
    unordered_set<int>sw;
    unordered_map<int,int>mp;
    vi u;
    cin>>n>>w;
  ll a[n],v[n];
  fr(i,n){
      cin>>a[i]>>v[i];
      x+=v[i];
  }
  ll dp[x+1];
  fr(i,x+1){
      dp[i]=1000000000000000000;
  }
 dp[0]=0;
 fr(j,n){
       y=v[j];
for(i=x-y;i>=0;i--){
     dp[i+y]=min(dp[i+y],(dp[i]+a[j]));
 
}
}
 ll ans=0;
 fr(i,x+1){
     if(dp[i]<=w){
         ans=max(ans,i);
     }
 }
 cout<<ans<<"\n";
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
//#define MOD 998244353
#define MOD 1000000007

int main(){
    vector<ll> f;
    rep(i,1,10)f.push_back(i);
    int k;
    cin>>k;k--;
    ll idx=0;
    while(k--){
        ll t=f[idx++];
        if(t%10!=0)f.push_back(t*10+(t%10)-1);
        f.push_back(t*10+(t%10));
        if(t%10!=9)f.push_back(t*10+(t%10)+1);
    }
    rep(i,0,k)cout<<f[i]<<endl;
    
    cout<<f[idx]<<"\n";
}

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

static const double EPS = 1e-10;

// 三角形の外接円の半径
double sol_r(double x1, double y1, double x2, double y2, double x3, double y3) {
  double a = x1 - x2, b = y1 - y2, c = x2 - x3, d = y2 - y3;
  double det = a * d - b * c;
  
  double lx1, lx2, lx3;
  lx1 = pow(x1, 2) + pow(y1, 2);
  lx2 = pow(x2, 2) + pow(y2, 2);
  lx3 = pow(x3, 2) + pow(y3, 2);
  
  double tmp1 = lx1 - lx2, tmp2 = lx2 - lx3;
  
  double xc, yc; // x,y 中心座標
  xc = (1 / (2 * det)) * (d * tmp1 - b * tmp2);
  yc = (1 / (2 * det)) * (-c * tmp1 + a * tmp2);
  
  return sqrt(pow((x1 - xc), 2) + pow((y1 - yc), 2));
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<double> x(n), y(n);
  for (int i = 0; i < n; i++) cin >> x.at(i) >> y.at(i);
  
  double ans = 0;
  if (n == 2) ans = sqrt(pow(x[0] - x[1], 2) + pow(y[0] - y[1], 2)) / 2;
  
  for (int i = 0; i < n - 2; i++) {
    for (int j = i + 1; j < n - 1; j++) {
      for (int k = j + 1; k < n; k++) {
        vector<double> a(3);
        a[0] = pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2);
        a[1] = pow(x[j] - x[k], 2) + pow(y[j] - y[k], 2);
        a[2] = pow(x[k] - x[i], 2) + pow(y[k] - y[i], 2);
        sort(a.begin(), a.end());
        if (a[2] - (a[0] + a[1]) > EPS) ans = max(ans, sqrt(a[2]) / 2);
        else ans = max(ans, sol_r(x[i], y[i], x[j], y[j], x[k], y[k]));
      }
    }
  }
  
  cout << fixed << setprecision(10) << ans << '\n';
}

Measured memory_bytes: 3804
package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	var cap [5]int
	var num int
	{
		tmp, _ := reader.ReadString('\n')
		tmp = strings.Trim(tmp, "\n")
		num, _ = strconv.Atoi(tmp)
	}
	for i := 0; i < 5; i++ {
		tmp, _ := reader.ReadString('\n')
		tmp = strings.Trim(tmp, "\n")
		cap[i], _ = strconv.Atoi(tmp)
	}

	min := checkMin(cap)
	var ans int
	if min > num {
		ans = 5
	} else {
		ans = (num-1)/min + 5
	}

	fmt.Println(ans)

}

func checkMin(cap [5]int) int {
	min := cap[0]

	for i := 1; i < 5; i++ {
		if min > cap[i] {
			min = cap[i]
		}
	}

	return min
}


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

int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int a[1000],q;
int mx=0;
int mi=0;
cin>>q;

for(int f=0;f<q;f++){
cin>>a[f];
if(f>=1){
mx=max((a[f]-a[f-1]),mx);
mi=min((a[f]-a[f-1]),mi);
}}
cout<<mx<<" "<<-1*mi<<endl;
}

return 0;
}


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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define mod (ll)1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n, a[100001];
  cin >> n;
  rep(i, 0, n) cin >> a[i];
  int ans = 1;
  int c = 1, f;
  while(c < n) {
    if(a[c] < a[c - 1]) {
      f = 1;
      break;
    }
    else if(a[c] > a[c - 1]) {
      f = 0;
      break;
    }
    else c++;
  }
  if(f != 1 && f != 0) {
    cout << 1 << endl;
    return 0;
  }
  rep(i, 1, n) {
    if(a[i] < a[i - 1]) {
      if(f == 2) f = 1;
      else if(!f) ans++, f = 2;
    }else if(a[i] > a[i - 1]) {
      if(f == 2) f = 0;
      else if(f) ans++, f = 2;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int n;
int main() 
{
	cin>>n;
	n%=10;
	if(n==3) cout<<"bon"<<endl;
	else if(n==0||n==1||n==6||n==8) cout<<"pon"<<endl;
	else cout<<"hon"<<endl;
	return 0;
}

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

int s[100010], n;

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

    cin>>n;
    for(int i=0; i<n; ++i) {
        int a, b; cin>>a>>b;
        ++s[a];
        --s[b+1];
    }

    int res=0;
    for(int i=0; i<=n; ++i) {
        s[i+1]+=s[i];
        if (s[i+1]>=i) res=i;
    }
    cout<<res<<endl;
}

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

int main() {
	int n; cin >> n;
	int v[100];
	int c[100];

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

	int cost = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] > c[i]) cost += (v[i] - c[i]);
	}

	cout << cost << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define MOD 1000000007
#define EPS (1 >> 30)
#define INF (1 << 30)
//#define INFll (1LL << 60)

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    //---------------------------------------------

    vector<bool> isP(100100, true);
    isP[0] = isP[1] = false;
    for (int i = 2; i < 100100; i++)
    {
        if (isP[i])
        {
            for (int j = i * 2; j < 100100; j += i)
            {
                isP[j] = false;
            }
        }
    }
    int n;
    cin>>n;
    int memo=0;
    for(int i=1;i<=55555;i+=5){
        if(isP[i]){
            cout<<i<<" ";
            memo++;
            if(memo==n){
                cout<<endl;
                break;
            }
        }
    }
    
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<cmath> 
using namespace std;
int main(){
	int a,b;
	while(cin>>a>>b){
		int d=a/b;
		int r=a%b;
		double f=(a*1.0)/(b*1.0);
		cout<<d<<' '<<r<<' ';
		printf("%0.8lf\n",f);
	}
	return 0;
}


Measured memory_bytes: 3232
#include <stdio.h>

int max(int a,int b){
  if(a > b){
    return a;
  }
  return b;
}

int main(void){
  int H,W;
  scanf("%d%d",&H,&W);

  char S[H][W+1];
  for (int i = 0; i < H; i++) {
    scanf("%s",S[i]);
  }

  int sum1[H][W];
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if(S[i][j] == '.'){
        sum1[i][j] = 1;
        if(i-1 >= 0){
          sum1[i][j] += sum1[i-1][j];
        }
      }else sum1[i][j] = 0;
    }
  }
  for (int i = H-2; i >= 0; i--) {
    for (int j = 0; j < W; j++) {
      if(S[i][j] == '.') sum1[i][j] = max(sum1[i][j],sum1[i+1][j]);
    }
  }

  int sum2[H][W];
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if(S[i][j] == '.'){
        sum2[i][j] = 1;
        if(j-1 >= 0){
          sum2[i][j] += sum2[i][j-1];
        }
      }else sum2[i][j] = 0;
    }
  }
  for (int i = 0; i < H; i++) {
    for (int j = W-2; j >= 0; j--) {
      if(S[i][j] == '.') sum2[i][j] = max(sum2[i][j],sum2[i][j+1]);
    }
  }

  int ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      ans = max(ans,sum1[i][j]+sum2[i][j]-1);
    }
  }

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

  return 0;
}

Measured memory_bytes: 35328
#import math.sqrt as sqrt

N, K= list(map(int, input().split()))
#B = list(map(int, input().split()))

S = list(input())


if S[K-1]=="A":
    S[K-1] = 'a'
elif S[K-1] == "B":
    S[K-1] ="b"
else:
    S[K-1] ="c"


for i in range(N):
    print(S[i], end="")


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <iomanip>
#define ll long long
using namespace std;

long long int Calc(ll n, ll x){
    ll co[n+1]; co[0] = 1;
    ll pa[n+1]; pa[0] = 1;
    for(ll i = 1; i <= n; i++){
        co[i] = co[i-1]*2+3;
        pa[i] = pa[i-1]*2+1;
    }
    if(n == 0) return 1;
    else if(x == 1) return  0;
    else if(x > 1 && x < co[n-1]+2) return  Calc(n-1, x-1);
    else if(x == co[n-1]+2) return  pa[n-1]+1;
    else if(x > co[n-1]+2 && x < 2*co[n-1]+3) return  pa[n-1]+1+Calc(n-1, x-co[n-1]-2);
    else return pa[n];
}

int main(void){
    ll n, x;
    cin >> n >> x;
    cout << Calc(n, x) << endl;
    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
    x += y;
    if( x >= m )
        x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
    x -= y;
    if( x < 0 )
        x += m;
}

int main() 
{
    fastio();

    int a,b,c,d;
    cin>>a>>b>>c>>d;

    int turn = 0;
    while( true )
    {
        if( turn == 0 )
        {
            c -= b;
            if( c <= 0 )
            {
                cout<<"Yes";
                return 0;
            }
        }
        else
        {
            a -= d;
            if( a <= 0 )
            {
                cout<<"No";
                return 0;
            }
        }
        turn ^= 1;
    }
    assert(false);


    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 3608
# -*- coding: utf-8 -*-
# from collections import deque
from sys import setrecursionlimit

setrecursionlimit(1000000)


# INF = float("inf")

# d = deque()
# ---Input---#
n = int(input())
# n, k = map(int, input().split())
p = list(map(float, input().split()))
p = [-1] + p

memo = [[-1 for _ in [0] * (n + 1)] for _ in [0] * (n + 1)]
memo[0][0] = 1
for i in range(len(p))[1:]:
    memo[0][i] = 0
    memo[i][0] = memo[i - 1][0] * (1 - p[i])
memo[0][0] = 1


def dp(i, j):
    if memo[i][j] == -1:
        memo[i][j] = dp(i - 1, j) * (1 - p[i]) + dp(i - 1, j - 1) * p[i]
    return memo[i][j]


ans = 0
tar = int(n / 2) + 1
for i in range(n + 1):
    dp(i, i)
    dp(i, n)

for i in range(n + 1)[tar:]:
    ans += dp(n, i)


print("{}".format(ans))


Measured memory_bytes: 218148
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;

int findIndex( int value );

int main(void){
    int X,Y,ans=0;

    cin >> X >> Y;

    ans = X + Y / 2;

    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long prime = 1000000007;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj_list(3*n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        adj_list[u].push_back(n+v);
        adj_list[n+u].push_back(2*n+v);
        adj_list[2*n+u].push_back(v);
    }
    int s, t;
    cin >> s >> t;
    --s;
    --t;
    vector<int> dist(3*n, -1);
    queue<pair<int, int>> q;
    q.push(make_pair(s, 0));
    while (!q.empty()) {
        int u = q.front().first;
        int d = q.front().second;
        q.pop();
        if (dist[u] != -1) {
            continue;
        }
        dist[u] = d;
        for (int j : adj_list[u]) {
            q.push(make_pair(j, d+1));
        }
    }
    cout << (dist[t] == -1 ? -1 : dist[t]/3) << endl;
    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef long double ld;

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

    ll r, ans = 0;
    
    cin >> r;
    
    cout << 3 * r * r << endl;
    
    return 0;
}



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

struct node{
  unsigned int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch(int key){
  NodePointer cur = nil->next;
  while( cur != nil && cur->key != key){
    cur = cur->next;
  }
  return cur;
}

void init(){
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(){
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void deleteNode(NodePointer t){
  if( t == nil)return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
}

void deleteLast(){
  deleteNode(nil->prev);
}

void delete(int key){
  deleteNode(listSearch(key));
}


void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main(){
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) {insert(key); np++; size++;}
    else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
      	if ( com[6] == 'F' ) deleteFirst();
      	else if ( com[6] == 'L' ) deleteLast();
      }
      else {
	         delete(key); nd++;
      }
      size--;
    }
  }

  printList();
  return 0;
}



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

string str;

bool isWin(char c) {
  
  for(int i=0; i<3; i++) {
    int cnt = 0;
    for(int j=0; j<3; j++) {
      if( str[i*3+j] == c ) cnt ++;
    }
    if( cnt == 3 ) return true;
  }
  
  for(int i=0; i<3; i++) {
    int cnt = 0;
    for(int j=0; j<3; j++) {
      if( str[j*3+i] == c ) cnt ++;
    }
    if( cnt == 3 ) return true;
  }

  if( str[0] == c
      && str[4] == c
      && str[8] == c ) return true;

  if( str[2] == c
      && str[4] == c
      && str[6] == c ) return true;
  
  return false;
  
}

int main() {
  while(cin >> str) {
    bool fO = isWin('o');
    bool fX = isWin('x');
    if( !fO && !fX ) cout << "d" << endl;
    else cout << ( fO ? "o" : "x" ) << endl;
  }
  return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
#define SIZE 2000005
#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status Accepted
long long fac[SIZE],finv[SIZE],inv[SIZE];
long long MOD=mod;

void make() {
    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;
    }
}

// 二項係数計算
long long C(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;
}
//status unsolved
int main(){
    int n,m;
    cin>>n>>m;
    make();
    cout<<C(m,2)+C(n,2)<<endl;


    return 0;

}
/*


*/


Measured memory_bytes: 47104
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	int K, X;
	cin >> K >> X;

	if (K * 500 >= X) co("Yes");
	else co("No");


	Would you please return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)

int main() {
  int n,k;
  cin>>n>>k;
  vector<int> a(3);
  rep(i,3) cin >> a[i];
  string s;
  cin>>s;
  vector<int> ctoi(256);
  ctoi['r'] = 2;
  ctoi['c'] = 0;
  ctoi['p'] = 1;
  int ans = 0;
  rep(i,k) {
    vector<int> x;
    for (int j = i; j < n; j += k) {
      x.push_back(ctoi[s[j]]);
    }
    vector<int> dp(2);
    int pre = -1;
    for (int nx : x) {
      vector<int> p(2);
      swap(dp,p);
      dp[0] = max(p[0],p[1]);
      if (pre == nx) {
        dp[1] = p[0]+a[nx];
      } else {
        dp[1] = max(p[0],p[1])+a[nx];
      }
      pre = nx;
    }
    ans += max(dp[0],dp[1]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1020
def main():
    A, B, C = map(int, input().split())
    K = int(input())
    
    while K>0:
        if A < B: break
        else:
            B*=2
            K-=1

    while K>0:
        if B < C: break
        else:
            C*=2
            K-=1


    
    ans = "No"
    if A<B and B<C:
        ans = "Yes"



    return ans

if __name__ == '__main__':
    print(main())

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n; cin >> n;
  vector<double> v(n); cin >> v;
  vector<vector<double>> dp(n+1,vector<double>(n+1,0));
  dp[0][0] = 1;
  for(int i = 1; i <= n; ++i){
    for(int j = 0; j <= n; ++j){
      if(j == 0)dp[i][j] = dp[i-1][j] * (1-v[i-1]);
      else dp[i][j] = dp[i-1][j] * (1-v[i-1]) + dp[i-1][j-1] * (v[i-1]);
    }
  }
  double ans = 0;
  for(int i = (n>>1)+1; i <= n; ++i) ans += dp[n][i];
  cout << fixed << setprecision(10) << ans << endl;
  return 0;  
}


Measured memory_bytes: 70784
<?php
fscanf(STDIN,"%d %d",$n,$k);
for($i=0;$i<$n;$i++){
	$arr[$i]=$i;
}

$cnt=0;
for($s=1;$s<=$n;$s++){
	for($i=$s;$i<=($s+$k-1);$i++){
		if($i>$n){
			break 2;
		}
	}
	$cnt++;
}

echo $cnt;
?>

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N,M;
  cin>>N>>M;
  vector<ll> A0(N,0);
  vector<ll> A1(N,0);
  vector<ll> A2(N,0);
  vector<ll> A3(N,0);
  vector<ll> A4(N,0);
  vector<ll> A5(N,0);
  vector<ll> A6(N,0);
  vector<ll> A7(N,0);
  for(int i=0; i<N; i++){
    ll x,y,z;
    cin>>x>>y>>z;
    A0[i]=x+y+z;
    A1[i]=x+y-z;
    A2[i]=x-y+z;
    A3[i]=x-y-z;
    A4[i]=-x+y+z;
    A5[i]=-x+y-z;
    A6[i]=-x-y+z;
    A7[i]=-x-y-z;
  }
  sort(A0.begin(), A0.end(), greater<ll>());
  sort(A1.begin(), A1.end(), greater<ll>());
  sort(A2.begin(), A2.end(), greater<ll>());
  sort(A3.begin(), A3.end(), greater<ll>());
  sort(A4.begin(), A4.end(), greater<ll>());
  sort(A5.begin(), A5.end(), greater<ll>());
  sort(A6.begin(), A6.end(), greater<ll>());
  sort(A7.begin(), A7.end(), greater<ll>());
  ll ans=0;
  ll tmp0=0;
  ll tmp1=0;
  ll tmp2=0;
  ll tmp3=0;
  ll tmp4=0;
  ll tmp5=0;
  ll tmp6=0;
  ll tmp7=0;
  for(int i=0; i<M; i++)
    tmp0+=A0[i];
  for(int i=0; i<M; i++)
    tmp1+=A1[i];
  ans=max(tmp0, tmp1);
  for(int i=0; i<M; i++)
    tmp2+=A2[i];
  ans=max(ans, tmp2);
  for(int i=0; i<M; i++)
    tmp3+=A3[i];
  ans=max(ans, tmp3);
  for(int i=0; i<M; i++)
    tmp4+=A4[i];
  ans=max(ans, tmp4);
  for(int i=0; i<M; i++)
    tmp5+=A5[i];
  ans=max(ans, tmp5);
  for(int i=0; i<M; i++)
    tmp6+=A6[i];
  ans=max(ans, tmp6);
  for(int i=0; i<M; i++)
    tmp7+=A7[i];
  ans=max(ans, tmp7);
  cout<<ans<<endl;
}


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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

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



void func(std::string s){

    cout<<s.substr(0,5)<<" "<<s.substr(6,7)<<" "<<s.substr(14,5)<<endl;

}

int main(){
    // cout << fixed << setprecision(5);

    std::string s;
    std::cin >> s;
    func(s);
    return 0;
}


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

int L, sz = 0;
struct Edge {
	int u, v, w;
};
vector<Edge> E;

int main() {
	scanf("%d", &L);
	L--;
	if (L == 1) {
		puts("2 2");
		puts("1 2 1");
		puts("1 2 0");
		return 0;
	}
	while ((1 << sz) <= L) sz++;
	int S = 1, T = sz;
	for (int i = 1; i < sz; i++) {
		E.push_back(Edge{ i, i + 1, 1 << (sz - i - 1) });
		E.push_back(Edge{ i, i + 1, 0 });
	}
	int w = 0;
	w = 1 << (sz - 1);
	for (int p = sz - 2, i = 1; p >= 0; p--, i++) {
		if (L >> p & 1) {
			E.push_back(Edge{ S, i + 1, w });
			w += 1 << p;
		}
	}
	E.push_back(Edge{ S, T, L });
	printf("%d %d\n", sz, (int)E.size());
	for (auto& t : E) printf("%d %d %d\n", t.u, t.v, t.w);
	
	return 0;
}

Measured memory_bytes: 256
/*+lmake
 * STD = c++14
 * DEFINE += WAAUTOMATON
 */
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#ifdef WAAUTOMATON
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;

void solve(long long N, vector<long long> d, double x){
	double ans=0;
	double d0=d[0];
	LL n=N;
	do {
		ans+=d0+(n-0.5)*x;
		d0=((2*n+2)*d0+5*x)/(2*n);
		x=(2*n+4)*x/(2*n);
	}while(--n);
	printf("%.9lf\n",ans);
}

int main(){	
#ifdef WAAUTOMATON
	//freopen("in.txt","r",stdin);
#endif
	vector<long long> d(1-1+1);
	long long x;
	long long N;
	scanf("%lld",&N);
	for(int i = 0 ; i <= 1-1 ; i++){
		scanf("%lld",&d[i]);
	}
	scanf("%lld",&x);
	solve(N, d, x);
	return 0;
}



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

using namespace std;

bool blkd[1000][1000];
int dp[1000][1000];
int inf=1000000007;

int pro(int i,int j)
{
    if(blkd[i][j])
    {
        dp[i][j]=0;
        return 0;
    }
    if(i==0 && j==0)
    {
        dp[i][j]=1;
        return 1;
    }
    if(i==0)
    {
        if(dp[i][j-1]==-1)
        {
            dp[i][j-1]=pro(i,j-1)%inf;
        }
        return dp[i][j-1];
    }
    if(j==0)
    {
        if(dp[i-1][j]==-1)
        {
            dp[i-1][j]=pro(i-1,j)%inf;
        }
        return dp[i-1][j];
    }
    if(dp[i-1][j]==-1)
    dp[i-1][j]=pro(i-1,j);
    if(dp[i][j-1]==-1)
    dp[i][j-1]=pro(i,j-1);
    return (dp[i-1][j]+dp[i][j-1])%inf;
}

int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            char c;
            cin>>c;
            if(c=='#')
            blkd[i][j]=true;
            else
            blkd[i][j]=false;
            dp[i][j]=-1;
        }
    }
    int ans=pro(h-1,w-1)%inf;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5248
s = input()
n = int(input())

ans = 0

count = 1
past = ''

for i in s:
    if i == past:
        count += 1
    else:
        ans += count // 2
        count = 1
    past = i

if count == len(s):
    print((len(s)*n)//2)
    exit()

ans += count // 2
ans *= n

if s[0] == s[-1]:
    past = s[0]
    idx = 1
    begin = 1

    while idx < len(s) and past == s[idx] :
        begin += 1
        idx += 1
    past = s[-1]
    idx = -1
    end = 1

    while idx > 0 and past == s[idx] :
        end += 1
        idx -= 1

    if begin %2 != 0 and count %2 != 0:
        ans += n - 1

print(ans)


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

#define pb push_back
#define all(a) (a).begin(), (a).end()

using ll = long long;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    ll n; cin >> n;
    if (n & 1) {
        cout << 0 << '\n';
        return 0;
    }
    ll ans = 0;
    for (ll i = 5; ((n+i) / (2*i)) >= 1; i *= 5) {
        ans += (n / i);
        ans -= ((n+i) / (2 * i));
    }
    cout << ans << '\n';
}

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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

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

///**************************DONE****************************///

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

    int pc = 0, pt = 0;
    for(int i = 0; i < n; i++){
        int t, x, y;
        cin >> t >> x >> y;

        int nc = abs(x + y - pc), nt = t - pt;
        if(nt < nc || nt % 2 != nc % 2)
            return cout << "No\n", 0;

        pc = x + y, pt = t;
    }

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


Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e15;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n,m,x,y; cin>>n>>m>>x>>y;
    vi aa(n),bb(m);
    rep(i,n)cin>>aa[i];
    rep(i,m)cin>>bb[i];
    int a=MAX(aa); int b=MIN(bb);

    for(int i=x+1; i<=y; i++){
        if(a<i && i<=b){
            cout<<"No War"<<endl; return 0;
        }
    }
    cout<<"War"<<endl;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <algorithm>
using namespace std;

int N,H[100100],D[100100];
int main()
{
	scanf ("%d",&N);

	for (int i=1;i<=N;i++) scanf ("%d",&H[i]);
	for (int i=2;i<=N;i++){
		D[i] = D[i-1] + abs(H[i-1]-H[i]);
		if (i > 2 && D[i] > D[i-2] + abs(H[i-2]-H[i]))
			D[i] = D[i-2] + abs(H[i-2]-H[i]);
	}
	printf ("%d\n",D[N]);

	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

string s[3];
queue<char> qu[3];
char c = 'a';

int main()
{
    cin>>s[0]>>s[1]>>s[2];
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < s[i].size(); j++)
        {
            qu[i].push(s[i][j]);
        }
    }
    while(true)
    {
        if(qu[c - 'a'].empty()) break;
        char t = qu[c - 'a'].front();
        qu[c - 'a'].pop();
        c = t;
    }
    printf("%c", c + 'A' - 'a');
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  string s;
  cin >> s;
  for(int i = 0;i + 1 < s.size();i++) {
    set<char> st;
    for(int j = 0;j < 2;j++) st.insert(s[i + j]);
    if(st.size() < 2)  {
      cout << i + 1 << " " << i + 2 << endl;
      return 0;
    }
  }
  for(int i = 0;i + 2 < s.size();i++) {
    set<char> st;
    for(int j = 0;j < 3;j++) st.insert(s[i + j]);
    if(st.size() < 3)  {
      cout << i + 1 << " " << i + 3 << endl;
      return 0;
    }
  }
  cout << -1 << " " << -1 << endl;
}


Measured memory_bytes: 512
use std::io::*;
use std::str::*;
use std::cmp::*;
use std::fmt;



fn main() {
    let mut s:String = read();
    let c = s.chars().collect::<Vec<char>>();
    let mut cnt:Vec<i64> =vec![0;30];
    for i in 0..c.len(){
        cnt[(c[i] as usize)-('a' as usize)] += 1;
    }
    let mut len:i64 = c.len() as i64;
    let mut ans:i64 = len*(len-1)/2;
    for i in 0..26{
        ans -= cnt[i]*(cnt[i]-1)/2;
    }
    println!("{}",ans+1)
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().unwrap_or_else(|_| panic!("Faild to parse {}", s))
}


Measured memory_bytes: 4352
/* << IN THE NAME OF GOD >> */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pob pop_back
#define ft first
#define ftt ft.ft
#define ftc ft.sc
#define sc second
#define err(x) cerr << #x  << " = "<<  x << '\n'
#define out(x) cout << x << '\n'
#define forp(i, r, l) for(int i = int(r); i < int(l); i++)
#define forn(i, r, l) for(int i = int(r); i > int(l); i--)
#define FAST ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
#define ctz __builtin_ctz
typedef pair<int, int> pii;
typedef pair<ll ,ll> pll;
const int maxn = 1e6 + 120;
 


int n ,b[maxn] ,a[maxn] ,x[maxn];
int main(){FAST;
    cin >> n;
    forp(i ,1 ,n + 1)
        cin >> a[i] ,x[i] = a[i];
    sort(x + 1 ,x + n + 1);
    int mid = n >> 1;

    forp(i ,1 ,n + 1){
        if(a[i] > x[mid])
            out(x[mid]);
        else
            out(x[mid + 1]);
    }
    
   return 0;
}
 












Measured memory_bytes: 7040
import java.util.Scanner;
import java.util.Stack;

class Node {
    int id;
    int left;
    int right;
    int parent;
    int sibling;
    int degree;
    int depth;
    int height;
    String type;

    Node(int id, int left, int right) {
        this.id = id;
        this.left = left;
        this.right = right;
        parent = -1;
        sibling = -1;
        degree = 0;
        height = 0;
    }

    static void setInfo(Node[] tree) {
        for(Node node : tree) {
            if(node.left >= 0) {
                tree[node.left].parent = node.id;
                node.degree++;
            }
            if(node.right >= 0) {
                tree[node.right].parent = node.id;
                node.degree++;
            }
            if(node.degree == 2) {
                tree[node.left].sibling = node.right;
                tree[node.right].sibling = node.left;
            }
        }

        int root = -1;
        Stack<Integer> leaves = new Stack<>();
        for(Node node : tree) {
            if(node.degree == 0) {
                leaves.push(node.id);
                node.type = "leaf";
            }
            if(node.parent < 0) {
                root = node.id;
                node.type = "root";
            }
            if(node.type == null) {
                node.type = "internal node";
            }
        }

        while(!leaves.isEmpty()) {
            Node tmp = tree[leaves.pop()];
            if(tmp.parent >= 0 && tree[tmp.parent].height < tmp.height + 1) {
                tree[tmp.parent].height = tmp.height + 1;
                leaves.push(tmp.parent);
            }
        }

        Stack<Integer> task = new Stack<>();
        task.push(root);
        tree[root].depth = 0;
        while(!task.isEmpty()) {
            Node tmp = tree[task.pop()];
            if(tmp.left >= 0) {
                tree[tmp.left].depth = tmp.depth + 1;
                task.push(tmp.left);
            }
            if(tmp.right >= 0) {
                tree[tmp.right].depth = tmp.depth + 1;
                task.push(tmp.right);
            }
        }
    }

    void printInfo() {
        System.out.printf(
            "node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n",
            id, parent, sibling, degree, depth, height, type
        );
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        Node[] tree = new Node[n];
        for(int i = 0; i < n; i++) {
            int id = sc.nextInt();
            int left = sc.nextInt();
            int right = sc.nextInt();
            tree[id] = new Node(id, left, right);
        }

        Node.setInfo(tree);
        for(Node node : tree) {
            node.printInfo();
        }

        sc.close();
    }
}



Measured memory_bytes: 26432
#include <bits/stdc++.h>
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

using namespace std;

const int maxn = 2e5 + 50;

int A , B , C , n , x[maxn] , y[maxn] , z[maxn] , id[maxn];

int cnta[maxn] , cntb[maxn] , cntc[maxn];
priority_queue < pair < int , int > > Az , Ay , Bz;


int main( int argc , char * argv[] ){
	A = read() , B = read() , C = read();
	n = A + B + C;
	for(int i = 1 ; i <= n ; ++ i){
		x[i] = read() , y[i] = read() , z[i] = read();
		id[i] = i;
	}
	sort( id + 1 , id + n + 1 , [] ( const int & f1 , const int & f2 ){
		return -x[f1] + y[f1] < -x[f2] + y[f2];
	});
	for(int i = 1 ; i <= n - B ; ++ i){
		cnta[ id[i] ] = 1;
		int fr = id[i];
		Az.push( make_pair( z[fr] - x[fr] , fr ) );
		Ay.push( make_pair( y[fr] - x[fr] , fr ) );
	}
	for(int i = n - B + 1 ; i <= n ; ++ i){
		cntb[ id[i] ] = 1;
		int fr = id[i];
		Bz.push( make_pair( z[fr] - y[fr]  , fr ) );
	}
	for(int i = 1 ; i <= C ; ++ i){
		long long s1 = -(1LL << 60) , s2 = s1;
		while( !Az.empty() ){
			int g = Az.top().second;
			if( cnta[g] == 0 ){
				Az.pop();
			}else
				break;
		}
		while( !Ay.empty() ){
			int g = Ay.top().second;
			if( cnta[g] == 0 ){
				Ay.pop();
			}else
				break;
		}
		while( !Bz.empty() ){
			int g = Bz.top().second;
			if( cntb[g] == 0 ){
				Bz.pop();
			}else
				break;
		}
		if( !Az.empty() )
			s1 = Az.top().first;
		if( !Ay.empty() && !Bz.empty() )
			s2 = ( long long ) Ay.top().first + ( long long )Bz.top().first;
		if( s1 > s2 ){
			pair < int , int > g = Az.top(); Az.pop();
			cnta[g.second] = 0;
			cntc[g.second] = 1;
		}else{
			pair < int , int > g1 = Ay.top(); Ay.pop();
			pair < int , int > g2 = Bz.top(); Bz.pop();
			cnta[g1.second] = cntb[g2.second] = 0;
			cntb[g1.second] = 1;
			cntc[g2.second] = 1;
			Bz.push( make_pair( z[g1.second] - y[g1.second]  , g1.second ) );
		}
	}
	long long sum = 0;
	for(int i = 1 ; i <= n ; ++ i){
		if( cnta[i] )
			sum += x[i];
		if( cntb[i] )
			sum += y[i];
		if( cntc[i] )
			sum += z[i];
	}
	printf( "%lld\n" , sum );
	return 0;
}

Measured memory_bytes: 5868
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, M, x, y;
	int ans = 0;
	cin >> N >> M;
	vector<int> box(N, 1);
	vector<int> red(N, 0);
	red[0] = 1;

	for (int i = 0;i < M;i++)
	{
		cin >> x >> y;
		x--;
		y--;

		if (red[x] == 1)
		{
			if (box[x] == 1)
				red[x] = 0;
			red[y] = 1;
		}
		
		box[x]--;
		box[y]++;

		cout << endl;
	}
	for (int i = 0;i < N;i++)
		if (red[i] == 1)ans++;

	cout << ans << endl;

	return 0;
}


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

#define pb push_back
#define mp make_pair

using namespace std;

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

int main() {
	double a;
	double b;
	
	cin >> a >> b;
	
	cout << (int) ceil((b-1)/(a-1)) << endl;
  return 0;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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 ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll k; cin>>k;
  
  ll ans=0;
  
  ll mo=0;
  ll maxn=1e8;
  rep(i,maxn){
    mo=(10*mo+7)%k;
    ans++;
    if(mo==0){
      cout<<ans<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
  
}

Measured memory_bytes: 3644
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;

using namespace std;

int main() {
  string s;
  cin >> s;
  rep(i, s.size()) {
    cout << 'x';
  }
}


Measured memory_bytes: 256