akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <math.h>

double SD(int n){
    int i,y;
    double average = 0,sum = 0;
    int point[1000] = {0};
    double squared,sigma = 0,sd;
    
    for(i = 0;i < n;i++){
        scanf("%d",&y);
        point[i] = y;
        sum += y;
    }
    
    average = sum/n;
    
    for(i = 0;i < n;i++){
        squared = (point[i]-average)*(point[i]-average);
        sigma += squared;
    }
    
    sd = sigma/n;
    
    return(sd);
}

int main(void){
    // Your code here!
   int n;
   double x;
    
    while(1){
        scanf("%d",&n);
        if(n == 0) break;
        x = sqrt(SD(n));
        
        printf("%lf\n",x);
    }
    
}



Measured memory_bytes: 1800
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vint a(n);
    int s=0;
    int si=0;
    REP(i,n){
        cin >> a[i];
        if(abs(a[i])>abs(s)){
            s=a[i];
            si=i;
        }
    }
    cout << 2*n-2 << endl;
    REP(i,n){
        if(i!=si){
            cout << si+1 << " " << i+1 << endl;
        }
    }
    if(s>=0){
        REP(i,n-1){
            cout << i+1 << " " << i+2 << endl;
        }
    }else{
        for(int i=n-1;i>0;i--){
            cout << i+1 << " " << i << endl;
        }
    }


    return 0;
}

Measured memory_bytes: 256
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
# a[0] == 0 のケース、要検証

n = int(input())
a = list(map(int, input().split()))
count_p = 0  # 操作回数(正)
count_m = 0  # 操作回数(負)
s = 0  # 現時点の和


def counter(a, s):
    if s * (s + a) < 0:
        return 0
    else:
        if s < 0:
            return 1 - (s + a)
        else:
            return -1 - (s + a)


# a[0]を+にする場合
if a[0] <= 0:
    count_p = 1 - a[0]
    s = 1
else:
    s = a[0]

for i in range(n-1):
    tmp = counter(a[i + 1], s)
    s = s + a[i+1]+tmp
    count_p = count_p + abs(tmp)

# a[0]を-にする場合
if a[0] >= 0:
    count_m = 1 + a[0]
    s = -1
else:
    s = a[0]


for i in range(n-1):
    tmp = counter(a[i + 1], s)
    s = s + a[i+1]+tmp
    count_m = count_m + abs(tmp)

print(str(min(count_p, count_m)))


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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  int N,M;cin>>N>>M;
  UnionFind uni(N);
  for(int i=0;i<M;i++){
    int a,b;cin>>a>>b;
    uni.unite(a,b);
  }
  vector<int> z(N,0);
  for(int i=0;i<N;i++)z[uni.root(i)]++;
  int m=0;
  for(int i=0;i<N;i++){
    m=max(m,z[i]); 
  }
  cout<<m<<endl;
}


Measured memory_bytes: 11172
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, L = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    tot=0
    ma=100000
    for i in range(N):
        tot+=L+i
        if abs(L+i)<abs(ma):
            ma=L+i
    print(tot-ma)




if __name__ == "__main__":
    main()

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

int main(){
  int n; cin >> n;
  ll ans = 0;
  for(int i = 1; i < n; i++){
    int x = n / i;
    if(n % i == 0) x--;
    ans += x;
  }
  cout << ans << endl;
  return 0;
}


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

int N;

typedef long long ll;

ll T = 0,AO = 0,ans = 0;

struct Data {
  ll  A,B,C;
  
};

bool operator>(const Data&left, const Data&right) {
  return left.C > right.C;
}

int main() {
  cin >> N;
  vector<Data> data(N);
  for ( int i = 0; i < N; i++ ) {
    cin >> data[i].A >> data[i].B;
    data[i].C = data[i].A + data[i].B;
  }

  sort(data.begin(),data.end(),greater<Data>());

  //  for ( int i = 0; i < N; i++ ) cout << data[i].C << endl;
  
 bool f = true;
 for ( int i = 0; i < N; i++ ) {
    if (f)  {
      T += data[i].A;
       f = false;
    }
    else {
      AO += data[i].B;
       f = true;
    }
  }
  ans = T - AO;
    cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 2560
#!/usr/bin/env python3

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

for i in range(N):
    A[i] -= 1

tele = [0]
#tele = [0,A[0]-1]
z = 0
s = 0
#B = {0:0,A[0]-1:1}
B = {0:0}
for i in range(N):
    if A[tele[-1]] in B and len(B) != 1:
        s = B[A[tele[-1]]]
        break
    B[A[tele[-1]]] = i+1
    tele.append(A[tele[-1]])
    z = tele[-1]

if K <= s:
    print(tele[K]+1)
else:
    K -= s
    amari = K%(len(tele[s:len(tele)]))
    tele = tele[s:len(tele)]*2
    print(tele[amari]+1)


Measured memory_bytes: 39212
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = double.Parse(line[0]);
        var m =double.Parse(line[1]);
        var d = double.Parse(line[2]);
        var ans = (m - 1) *(n -d) * 2d / (n * n);
        if (d == 0) ans /= 2;
        Console.WriteLine(ans);
    }
}

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

using namespace std;

using ll = long long;

#define ALL(A) A.begin(),A.end()

int main()
{
    ll A,B,C,K;
    cin >> A >> B >> C >> K;

    if(K<A) cout << K << endl;
    else if(K>=A && K<=A+B) cout << A << endl;
    else cout << A - (K - A - B) << endl;

    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;

int main() {
    ll A, B , C;
    cin >> A >> B >> C;
    if (C >= A && C <= B)cout <<"Yes";
    else cout<<"No";
    return 0;
}

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

const int MAX = 1000;
const int dy[4]={0,1,0,-1}, dx[4]={1,0,-1,0}; // 4近傍の移動
int H,W;
int goal_y, goal_x;
bool g[MAX][MAX]; // 通れるマスならtrue
bool visited[MAX][MAX];

int bfs(int warp_count, vector<P> prev_warped) {
  vector<P> reached_by_walking; // 今回新しく到達したマス
  // 前の階層でワープして到達したマスから四近傍移動で到達できる点を探索
  for(auto& start_pair : prev_warped) {
    queue<P> que;
    P current_p = start_pair;
    visited[current_p.first][current_p.second] = true;
    reached_by_walking.push_back(P(current_p.first, current_p.second));
    que.push(current_p);
    while(!que.empty()) {
      current_p = que.front();
      que.pop();
      for(int i = 0; i < 4; ++i) {
        int next_y = current_p.first + dy[i];
        int next_x = current_p.second + dx[i];
        // 範囲外
        if(next_y < 0 || next_y >= H) continue;
        if(next_x < 0 || next_x >= W) continue;

        if(next_y == goal_y && next_x == goal_x) return warp_count; // 目的のマスについた

        // 通れないまたはすでに到達済み
        if(!g[next_y][next_x]) continue;
        if(visited[next_y][next_x]) continue;
        reached_by_walking.push_back(P(next_y, next_x));
        que.push(P(next_y, next_x));
        // que.push(make_tuple(next_y, next_x, curr_d+1));
        visited[next_y][next_x] = true;
      }
    }
  }
  if(reached_by_walking.empty()) return -1; // 歩きで新しいマスに到達できない場合これ以上探索しても意味ない
  vector<P> warped; // この階層でワープしたマス
  // 新しく到達したマスからワープする
  for(auto& reached : reached_by_walking) {
    int current_y = reached.first, current_x = reached.second;
    for(int dy = -2; dy <= 2; ++dy) {
      for(int dx = -2; dx <= 2; ++dx) {
        if(!dy && !dx) continue;
        int next_y = current_y + dy;
        int next_x = current_x + dx;
        if(next_y < 0 || next_y >= H) continue;
        if(next_x < 0 || next_x >= W) continue;
        if(next_y == goal_y && next_x == goal_x) return warp_count+1; // 目的のマスについた

        // 通れないまたはすでに到達済み
        if(!g[next_y][next_x]) continue;
        if(visited[next_y][next_x]) continue;
        warped.push_back(P(next_y, next_x));
        visited[next_y][next_x] = true;
      }
    }
  }
  if(warped.empty()) return -1; // 歩きで到達できる範囲にも答えがなく、ワープを使っても到達点を拡大できない
  return bfs(warp_count+1, warped);
}

signed main() {
  cin >> H >> W;
  int start_y, start_x;
  cin >> start_y >> start_x; --start_y; --start_x;
  cin >> goal_y >> goal_x; --goal_y; --goal_x;
  REP(h, H) {
    REP(w, W) {
      char c;
      cin >> c;
      g[h][w] = (c == '.');
    }
  }
  cout << bfs(0, vector<P>{P(start_y, start_x)});
  cout << "\n";
  return 0;
}


Measured memory_bytes: 70648
def mi(): return map(int,input().split())
def lmi(): return list(map(int,input().split()))
def ii(): return int(input())
def isp(): return input().split()
 
n=ii()
a=lmi()
suma=sum(a)
counter=[0]*(10**5+1)
for i in a:
  counter[i]+=1
#print(counter)
q=ii()
 
for i in range(q):
  b,c=mi()
  suma+=(c-b)*counter[b]
  
  counter[c]+=counter[b]
  counter[b]=0
  #print(counter)
  print(suma)

Measured memory_bytes: 84412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll N;
vector<ll> T;
vector<ll> A;
vector<long double> LogSum;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    T.resize(N + 1);
    A.resize(N + 1);
    LogSum.resize(N + 1);
    for(int i = 0; i < N; i++) {
        cin >> T[i] >> A[i];
        LogSum[i+1] = LogSum[i];
        LogSum[i+1] += log(1 - 0.1 * A[i]);
        //cerr << i << " "<< LogSum[i+1] << " " << log(1 - 0.1 * A[i]) << endl;
    }
    T.back() = 2e9;
    ll Q;
    cin >> Q;
    while(Q--) {
        ll l, r;
        cin >> l >> r;
        long double LOG = 0;
        auto itr = lower_bound(T.begin(), T.end(), r);
        int index = distance(T.begin(), itr);
        LOG = LogSum[index];
        itr = lower_bound(T.begin(), T.end(), l);
        index = distance(T.begin(), itr);
        LOG -= LogSum[index];
        cout << fixed << setprecision(20) << 1e9 * exp(LOG) << endl;
    }
    return 0;
}



Measured memory_bytes: 6012
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <sstream>
#include <cmath>
#include <climits>
#include <set>
#include <iostream>
#include <map>
#include <functional>
#include <cstdlib>
#include <numeric>
#include <queue>
#include <complex>
#include <sstream>
#include <stack>

using namespace std;

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef complex<double> Point;

int main()
{
	for(;;){
		int length[3];
		rep(i, 3)
			scanf("%d", &length[i]);
		if(length[0]+length[1]+length[2] == 0)
			break;
		sort(length, length+3);
		int l = length[0]*length[0] + length[1]*length[1];

		int n;
		scanf("%d", &n);
		rep(i, n){
			int r;
			scanf("%d", &r);
			puts(r*r*4>l ? "OK" : "NA");
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9 + 7;
const int inf = 1e8;

int main() {
	int N,pmax = 0,sump= 0;
	cin>>N;
	vector<int> p(N);
	rep(i,N){
		cin>>p[i];
		pmax = max(pmax,p[i]);
		sump +=p[i];
	}

	int ans= sump-pmax/2;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

const int INF = 1000000000;

int main(){
    int n;
    while(cin >> n){
        vector<int> x(n);
        vector<int> y(n);
        REP(i, n) cin >> x[i] >> y[i];

        int dp[1001][1001] = {};
        REP(i, n) REP(j, n + 1) dp[i][j] = (i + 1 == j ? 0 : INF);

        for(int len = 2; len <= n; len++) {
            for(int i = 0; i + len <= n; i++) {
                int j = i + len;
                for(int k = i + 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + x[k] - x[i] + y[k - 1] - y[j - 1]);
                }
            }
        }
        
        cout << dp[0][n] << endl;
    }

    return 0;
}

Measured memory_bytes: 5124
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  ll A, B, C; cin >> A >> B >> C;
  if ( C <= A + B + 1 ) cout << C + B << '\n';
  else cout << A + 2 * B + 1 << '\n';
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
 
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VB;
 
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
 
const LD eps=1e-10;
const long long INFLL=(LL)(1e9)*(LL)(1e9);
const int INF=1e9;
 
template<class T>
void chmin(T& a, const T b)
{
	if(a>b)
		a=b;
}
template<class T>
void chmax(T& a, const T b)
{
	if(a<b)
		a=b;
}
 
const LL pow(const LL p, const LL q)
{
	LL t=1;
	for(int i=0;i<q;i++)
		t*=p;
	return t;
}

template <typename T>
struct has_iter
{
	private:
		template <typename U>
		static constexpr true_type check(typename U::iterator*);
		template <typename U>
		static constexpr false_type check(...);

	public:
		static constexpr bool value = decltype(check<T>(nullptr))::value;
};


template<typename T, typename U = typename T::iterator>
void print(const T& container)
{
		auto&& first=begin(container), last=end(container);
		auto&& back=prev(last);
		for(auto e=first; e!=last; e=next(e))
			cout<<*e<<" \n"[e==back];
}


extern void* enabler;
template<typename Head, typename enable_if<!has_iter<Head>::value>::type*& = enabler>
void print(const Head& head)
{
	cout<<head<<endl;
}

template<> void print<string>(const string& container)
{
	cout<<container<<endl;
}

template<typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail)
{
	cout<<head<<" ";
	print(tail...);
}

void io_speedup()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec)
{
	for(T& x: vec) is >> x;
	return is;
}

template<typename T>
vector<T> read(int n)
{
	vector<T> t(n);
	cin>>t;
	return t;
}

template<typename T>
T read()
{
	T t;
	cin>>t;
	return t;
}



int main()
{
	vector<int> a(3);
	cin>>a;
	sort(ALL(a));
	int ans=0;
	ans+=a[2]-a[1];
	a[0]+=a[2]-a[1];
	a[1]=a[2];
	ans+=(a[1]-a[0])/2;
	if((a[1]-a[0])%2==1) ans+=2;
	print(ans);
}


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

#define ll long long int

int dp[5004][5004];
int main(){
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(s[i-1]==s[j-1]){
        dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]);
      }
      else{
        dp[i][j]=0;
      }
      dp[i][j] = min(dp[i][j],j-i);
      ans=max(ans,dp[i][j]);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 98048
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
/*
int main() {
    // 前処理
    COMinit();

    // 計算例
    cout << COM(100000, 50000) << endl;
}*/

//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
*/
int main(){
    ll N;
    cin >> N;
    vector<ll> num(N);
    rep(i,N)cin >> num[i];
    vector<ll> n = num;
    sort(all(n));
    ll left = n[N / 2 - 1];
    ll right = n[N / 2];
    if(left == right){
        rep(i,N)cout << left << endl;
    }
    else{
    rep(i,N){
        if(num[i] == left){
            cout << right << endl;
        }
        else if(num[i] == right){
            cout << left << endl;
        }
        else{
            if(num[i] <=left)cout << right << endl;
            else cout << left << endl;
        }
    }
    }
}

Measured memory_bytes: 5376
N = int(input())
SP = [input().split() for i in range(N)]

for i in range(N):
  SP[i].append(i+1)
  SP[i][1] = int(SP[i][1])
  SP[i][1] = -SP[i][1]

SP.sort()

for i in range(N):
  print(SP[i][2])

Measured memory_bytes: 3060
ar = []                                            
raw = raw_input().split()                          
#ar.append(int(raw))                               
#raw = raw_input()                                 
#raw = raw_input()                                 
#ar.append(int(raw))                               
#raw = raw_input()                                 
#ar.append(int(raw))                               
#raw = raw_input()                                 
#ar.append(int(raw))                               
#raw = raw_input()                                 
#ar.append(int(raw))                               




#n = ar[0]                                         
a = int(raw[0])                                    
b = int(raw[1])
#c = ar[3]
#d = ar[4]
#e = ar[5]                                         

first = max(a,b)                                   

if ( a > b):                                       
    a -= 1                                         
else:
    b -= 1                                         


second = max(a,b)                                  

print first + second 

Measured memory_bytes: 2568
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

long long cnt = 0;
vector<int> g;

int shell(int n) {
	int m = 0;
	for (int i = 1;; i = i*2  + 1, m++) {
		if (i > n)break;
		g.push_back(i);
	}
	return m;
}

void insertionSort(int a[], int n, int g) {
	int i, j;
	for (i = g; i < n; i++) {
		j = i;
		int v = a[i];
		while (j-g >= 0 && a[j - g] > v) {
			a[j] = a[j - g];
			j -= g;
			cnt++;
		}
		a[j] = v;
	}

}


int main()
{
	int a[1000001];
	int m;
	int n, i, j;
	cin >> n;
	m = shell(n);
	for (i = 0; i < n; i++)
		cin>>a[i];

		cout << m << endl;
		for (i = m-1; i >=0; i--) {
			insertionSort(a, n, g[i]);
			cout << g[i];
			if(i)cout<< ' ';
		}
		cout << "\n" << cnt << endl;
		for (i = 0; i < n; i++)
			cout << a[i] << endl;
    return 0;
}




Measured memory_bytes: 7064
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define mod 1000000007
#define vi vector<int>
#define vll vector<ll>
#define pb push_back

ll power(int x, unsigned int y){
    ll res = 1;
    while(y > 0){
        if(y & 1) res = res * x;
        y >>= 1;
        x *= x;
    }
    return res;
}


// Check for number of Cases!!
void solve() {
    int num;

    cin >> num;

    ll arr[num];

    for(int i = 0; i < num; i++)
        cin >> arr[i];

    ll ans=0;

    ll suf[num+2];
    
    suf[num]=0;
    
    for(int i = num - 1; i >= 0 ;i--){
        suf[i]=(suf[i+1]+arr[i])%mod;
    }
    
    for(int i = 0; i < num-1; i++){
        ans=(ans+(arr[i]*suf[i+1])%mod)%mod;
    }
    cout<<ans<<"\n";
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1;
    // cin >> t;
    while(t--) {
      solve();
    }
}

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

int main(){
    int H, N;
    int *A;
    cin >> H >> N;
    A = new int[N];
    
    int i, sum = 0;
    for (i=0;i<N;i++){
        cin >> A[i];
        sum += A[i];
    }

    if (sum >= H){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long w,h,v,t,x,y,p,q;
main()
{
	cin>>w>>h>>v>>t>>x>>y>>p>>q;
	vector<long>Y;
	for(long i=-v*t;i<=v*t;i++)
	{
		long yy;
		if(i%2==0)yy=i*h+q;
		else yy=i*h+h-q;
		if(-1e7<=yy&&yy<=1e7)Y.push_back((yy-y)*(yy-y));
	}
	sort(Y.begin(),Y.end());
	long ans=0;
	for(long i=-v*t;i<=v*t;i++)
	{
		long xx;
		if(i%2==0)xx=i*w+p;
		else xx=i*w+w-p;
		if(xx<-1e7||1e7<xx)continue;
		long LIM=(long)v*t*v*t-(xx-x)*(xx-x);
		ans+=upper_bound(Y.begin(),Y.end(),LIM)-Y.begin();
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 19352
//#pragma GCC optimize(2)
//南京市第三区OI委提醒您：
//代码千万条，-O2第一条。
//-O2不规范，超时两行泪。
// Happy TLE and WA every day!
// by: zxb
#include<bits/stdc++.h>
#define mp              make_pair
#define rep(i,n)        for(int i = 0; i < n; i++)
#define foreach(i,c)    for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define BINF            0x7fffffff
#define INF             0x3f3f3f3f
#define LINF            4557430888798830399
#define pb              push_back
#define F               first
#define S               second
#define Time            clock()/CLOCKS_PER_SEC
#define read            ZXBs_fast_input
#define write           ZXBs_fast_output
#define int             long long
//#define usingFiles
using namespace std;

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

inline bool read(int& x){
	x = 0;
	int c;
	int sign = 1;
	while( (c = getchar()) < '0' || c > '9' ) if(c == '-') sign = -1;
	x = c ^ '0';
	while( (c = getchar()) >= '0' && c <= '9' ) x = (x<<3) + (x<<1) + (c ^ '0');
	x *= sign;
	return 1;
}

inline bool write(int x){
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
	return 1;
}

const int rp = 666666;
const bool debug = 1;
const bool I_good_vegetable_a = 1;

int n;
int x[55], y[55];
int cnt = 0;
map<pii, int> num;
int hi[3000];

signed main(){
	ios::sync_with_stdio(false);
	#ifdef usingFiles
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	cin >> n;
	rep(i, n) cin >> x[i] >> y[i];
	rep(i, n){
		rep(j, n){
			if(i == j) continue;
			pii now = mp(x[j] - x[i], y[j] - y[i]);
			if(num.find(now) == num.end()) num[now] = cnt++;
			hi[num[now]]++;
		}
	}
	int mx = 0;
	rep(i, cnt) mx = max(mx, hi[i]);
	cout << n-mx << endl;
	return 0;
}

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

#include <vector>
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define PI 3.14159265359
using namespace std;

int main() {
  int R;
  cin >> R;
  cout << R * PI*2 << endl;
}

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

int main(){
  int N;
  int counter = 0;
  cin >> N;
  vector<int> L(N);
  rep(i,N) cin >> L.at(i);

  sort(L.rbegin(),L.rend());

  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++){
       if(L.at(k) + L.at(j) > L.at(i))counter++;
      }
    }
  }
  cout << counter << endl;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    uf.union(a-1, b-1)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

w = [0] * (n+1)

for i in range(1, n+1):
    w[i] = uf.size(i-1) - friend[i] - block[i] - 1

print(*w[1:])

Measured memory_bytes: 14980
#include <cstdio>
using namespace std;

int main()
{
    int n;
    while(~scanf("%d",&n)){
        int a;
        scanf("%d",&a);
        int tmp = n%500;
        if(tmp <= a)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9
 
typedef long long ll;
 
using namespace std;
 
const ll inf = 1e18;
const ll mod = 1e9+7;
const int N = 2e5+5;
//int a[N];

int main()
 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 	
 	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif

    ll a, b, c, d;

    cin >> a >> b >> c >> d;

    ll ans = max(max(b*d, max(b*c, a*c)), a*d);

    cout << ans;

    return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long int
int32_t main()
{
    IOS;
    ll a,b,c,d,e;cin>>a>>b>>c>>d>>e;
     ll p1=a*60+b;
     ll p2=c*60+d;
     ll di=p2-p1;
     cout<<di-e;
} 


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int H, W, count = 0;
    cin >> H >> W;
    for (int i = 0; i < H * W; i++) {
        char A;
        cin >> A;
        if (A == '#') {
            count++;
        }
    }
    if (count == H + W - 1) {
        cout << "Possible" << endl;
    }
    else {
        cout << "Impossible" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll inf=1000000000000000000;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(int i=n;i>=m;i--)
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
pll f(vector<pll> v,ll n){
    ll sum=0;
    rep(i,0,v.size())sum+=v[i].first+v[i].second;
    ll u=v.size();
    set<ll> now;
    if(v[0].first<=n)now.insert(v[0].first);
    if(v[0].second<=n)now.insert(v[0].second);
    rep(i,1,u){
        set<ll> w;
        for(auto itr=now.begin();itr!=now.end();itr++){
            ll k=*itr;
            if(k+v[i].first<=n)w.insert(k+v[i].first);
            if(k+v[i].second<=n)w.insert(k+v[i].second);
        }
        now=w;
    }
    ll ret=-1;
    for(auto itr=now.begin();itr!=now.end();itr++){
        ret=max(ret,*itr);
    }
    return make_pair(ret,sum-ret);
}
int main(){
    ll n;cin>>n;
    ll p[n+1];
    vector<ll> v[n+1];
    rep(i,2,n+1){
        cin>>p[i];
        v[p[i]].push_back(i);
    }
    ll x[n+1];
    rep(i,1,n+1)cin>>x[i];
  if(n==1){
    cout<<"POSSIBLE"<<endl;
  return 0;
  }
    ll cnt[n+1];
    fill(cnt,cnt+n+1,0);
    pll sco[n+1];
    queue<ll> q;
    rep(i,1,n+1){
        if(v[i].size()==0){
            sco[i]=make_pair(x[i],0);
            cnt[p[i]]++;
            if(cnt[p[i]]==v[p[i]].size())q.push(p[i]);
        }
    }
    while(q.size()>0){
        ll now=q.front();q.pop();
        vector<pll> w;
        rep(i,0,v[now].size())w.push_back(sco[v[now][i]]);
        //rep(i,0,w.size())cout<<w[i].first<<" "<<w[i].second<<endl;
        pll e=f(w,x[now]);
        if(e.first==-1){
            cout<<"IMPOSSIBLE"<<endl;
            return 0;
        }
        if(now==1){
            cout<<"POSSIBLE"<<endl;
            return 0;
        }
        sco[now]=make_pair(x[now],e.second);
        cnt[p[now]]++;
        if(cnt[p[now]]==v[p[now]].size())q.push(p[now]);
    }
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
#define lowbit(x) ((x)&(-x))
#define randome_generate srand(std::chrono::high_resolution_clock::now().time_since_epoch().count())
using namespace std;
int r1,r2,c1,c2;
long long inv[2000100],fac[2000100],finv[2000100],mod=1000000007;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>r1>>c1>>r2>>c2;
	inv[1]=1LL;
	for(int i=2;i<=2000010;i++)//递推逆元 
		inv[i]=mod-((mod/i)*inv[mod%i])%mod;
	fac[0]=1LL;
	for(int i=1;i<=2000010;i++)
		fac[i]=(fac[i-1]*i)%mod;
	finv[0]=1LL;
	for(int i=1;i<=2000010;i++)
		finv[i]=(finv[i-1]*inv[i])%mod;
	long long ans=0LL;
	for(int i=c1;i<=c2;i++){
		ans+=((fac[r2+i+1]*finv[i+1])%mod*finv[r2])%mod;
		ans-=((fac[r1-1+i+1]*finv[i+1])%mod*finv[r1-1])%mod;
		ans%=mod;
		ans+=mod;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
    string s;
    cin >> s;
    for (int i = 2; i <= s.length(); i += 2) {
        string sub_s = s.substr(0, s.length() - i);
        bool is_correct = true;
        for (int j = 0; j < sub_s.length() / 2; j++) {
            if (sub_s[j] != sub_s[sub_s.length() / 2 + j]) is_correct = false;
        }
        if (is_correct) {
            cout << sub_s.length() << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define PI 3.1415926535897931
#define MAXN ((int)2e5+5)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

double a,b,x;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	
	cin >> a >> b >> x;

	double h,tang;

	h = ((2*x)/(a*a)) - b;

	if(2*x >= a*a*b)
	{
		tang = (a) / (b-h);
		cout << fixed << setprecision(12) << 90 - (atan(tang) * 180) / PI << endl;
	}
	else
	{
		tang = ((a*b*b) / (2*x));
		cout << fixed << setprecision(12) << (atan(tang) * 180) / PI << endl;
	}

	// TRACE2(h,tang);




}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mx = 1e5+10,INF=INT_MAX;
ll n,m;
int main()
{
    cin>>n>>m;
    ll H[n];
    for(int i=0; i<n; i++)
    {
        cin>>H[i];
    }
    ll dp[n];
    fill(dp,dp+n,INF);
    dp[0]=0;
    for(int i=0; i<n-1; i++)
    {
        for(int j=1; j<=min(m,n-i-1); j++)
            dp[i+j] = min(dp[i+j],abs(H[i]-H[i+j])+dp[i]);
    }
    cout<<dp[n-1]<<endl;
}



Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
"""
Created on Sun Apr  5 22:11:18 2020

@author: Kanaru Sato
"""

n,k,c = list(map(int, input().split()))
s = list(input())

early = []
late = []

i = 0
count = 0
while i < n and count < k:
    if s[i] == "o":
        early.append(i)
        i = i+c+1
        count = count+1
    else:
        i = i+1


i = n-1
count = 0
while i > -1 and count < k:
    if s[i] == "o":
        late.append(i)
        i = i-c-1
        count = count+1
    else:
        i = i-1

for i in range(len(early)):
    if early[i] == late[k-i-1]:
        print(early[i]+1)

Measured memory_bytes: 22104
using System;
class _0046
{
    public static void Main()
    {
        double max, min, n;
        string str = Console.ReadLine();
        n = double.Parse(str);
        max = min = n;
        while ((str = Console.ReadLine()) != null)
        {
            n = double.Parse(str);
            if (n > max) max = n;
            if (n < min) min = n;
        }
        Console.WriteLine((max - min).ToString("0.0"));
    }
}

Measured memory_bytes: 5760
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
//#include <intrin.h>

#define fore(i,a,b) for(int i = a; i < (b); i++)
#define fr(i,a,b) for(int i = a - 1; i >= b; i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define N 300005
#define inf (ll)2e18
#define EPS 1e-12
#define mod 1000000007LL
#define __builtin_popcount(x) __popcnt(x)

using namespace std;

typedef long long ll;

inline void solve()
{
	int n, k;
	cin >> n >> k;
	set<int> s;
	for (int i = 0; i < k; i++) {
		int d;
		cin >> d;
		for (int j = 0; j < d; j++) {
			int a;
			cin >> a;
			s.insert(a);
		}
	}
	cout << n - s.size();
}

int main()
{
	fast;
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	fore(t, 0, q)
	{
		solve();
		cout << '\n';
	}
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;
using ll = long long;
using Mat = array<array<ll, 2>, 2>;
constexpr ll MOD = (ll)(1e9 + 7);

Mat operator*(const Mat& m1, const Mat& m2)
{
    Mat ans{{{0, 0}, {0, 0}}};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                ans[i][j] += m1[i][k] * m2[k][j];
                ans[i][j] %= MOD;
            }
        }
    }
    return ans;
}

Mat power(const Mat& m, const ll n)
{
    if (n == 0) {
        return Mat{{{1, 0}, {0, 1}}};
    }
    if (n % 2 == 1) {
        return power(m, n - 1) * m;
    } else {
        const Mat mm = power(m, n / 2);
        return mm * mm;
    }
}

ll fib(const ll n)
{
    return power(Mat{{{0, 1}, {1, 1}}}, n + 2)[0][1];
}

ll calc(const ll n)
{
    if (n % 2 == 0) {
        return (n / 2 + 1) * (n / 2 + 1);
    } else {
        return (n / 2 + 1) * (n / 2 + 2);
    }
}

ll root(const ll k)
{
    ll inf = 0;
    ll sup = 1LL << 33;
    while (inf < sup) {
        const ll mid = (inf + sup) / 2;
        const ll c = calc(mid);
        if (c > k) {
            sup = mid;
        } else if (c == k) {
            return mid;
        } else {
            if (inf == mid) {
                break;
            }
            inf = mid;
        }
    }
    return inf;
}

int main()
{
    ll K;
    cin >> K;
    if (K == 1) {
        cout << 1 << endl;
        return 0;
    }
    const ll rt = root(K - 1);
    const ll pos = K - calc(rt) - 1;
    const ll rest = (rt + 1) / 2 - pos;
    if (pos <= (rt + 1) / 4) {
        cout << (fib(2 * pos) * fib(rt - 2 * pos + 1)) % MOD << endl;
    } else {
        cout << (fib(2 * rest + 1) * fib(rt - 2 * rest)) % MOD << endl;
    }


    return 0;
}

Measured memory_bytes: 3100
n, h = gets.split.map(&:to_i)
ab = []
n.times do
  ab.push gets.split.map(&:to_i)
end
sab = ab.sort_by {|e| e.first }
nab = ab.sort_by {|e| -e.last }
nsum = 0
ncount = 0
nab.each do |e|
  if e.last > sab[-1].first
    nsum += e.last
    ncount += 1
  end
end
count = 0
if h <= nsum
  nab.each do |e|
    count += 1
    h -= e.last
    break if h <= 0
  end
else
  h -= nsum
  count = ncount
  count += h / sab[-1].first
  count += 1 unless (h % sab[-1].first).zero?
end
puts count


Measured memory_bytes: 13404
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n];
    int ans=0;
    for(int i=0;i<n;i++){
      cin>>a[i];  
    }
    for(int i=0;i<n;i++){
        while(true){
          if(a[i]%2==0){
            ans++;
            a[i]=a[i]/2;
          }
          else{
            break; 
          }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

int main(void){
    int N;
    cin >> N;
    cout << (N+1)/2 << endl;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(long i=0; i<(long)(n);i++)
#define REP(i,s,t) for(long i=s; i<t; i++)
#define RNG(i,s,t,u) for(long i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()
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; }

int main(){
  long n,x,m;
  cin >> n >> x >> m;
  vl div(100001);
  for(long i=0; i<100001; i++){
    div.at(i) = i * i % m;
  }
  set<long> st;
  vl list;
  long tmp = x;
  rep(i,n){
    if(i==0){
      st.insert(x);
      list.push_back(x);
      continue;
    }else{
      tmp = div.at(tmp);
      if(st.count(tmp)){
        break;
      }else{
        st.insert(tmp);
        list.push_back(tmp);
      }
    }
  }
  if(n == list.size()){
    long sum = 0;
    rep(i,n) sum += list.at(i);
    cout << sum << endl;
    return 0;
  }else{
    long len;
    long sum = 0;
    rep(i,list.size()){
      if(list.at(i) != tmp){
        sum += list.at(i);
      }else{
        len = list.size() - i;
        long sub = 0;
        REP(j,i,list.size()){
          sub += list.at(j);
        }
        long r = n - i;
        sum += (r/len)*sub;
        r %= len;
        REP(j,i,i+r){
          sum += list.at(j);
        }
        cout << sum << endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 6772
use std::io::Read;

fn main() {
    let mut buf = String::new();
    let stdin = std::io::stdin();
    stdin.lock().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n = iter.next().unwrap().parse::<usize>().unwrap();
    let k = iter.next().unwrap().parse::<usize>().unwrap();
    if k >= n {
        println!("0");
        std::process::exit(0);
    }

    let mut a_vec: Vec<usize> = Vec::with_capacity(n);
    for a in iter {
        a_vec.push(a.parse::<usize>().unwrap());
    }
    a_vec.sort();

    let mut ans = 0_usize;
    let mut cnt = n;
    for a in a_vec {
        ans += a;
        cnt -= 1;
        if cnt == k { break; }
    }

    println!("{}", ans);
}


Measured memory_bytes: 9464
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
int ask(ll a,ll b,ll c,ll d){
	cout<<"? "<<a<<" "<<b<<" "<<c<<" "<<d<<"\n"<<flush;
	int res;
	cin>>res;
	return res;
}
int main(){
	int h,w,n,K;
	cin>>h>>w>>n>>K;
	int ans[55][55];
	rep(i,h)rep(j,w)ans[i][j]=0;
	rep(i,h)for(int j=0;j<w;j+=4){
		int l=j,r=min(w-1,j+3);
		int allsum=ask(i,l,i,r);
		if(allsum==0)continue;
		if(r-l+1==2){
			int x=ask(i,l,i,l);
			ans[i][l]=x,ans[i][r]=allsum-x;
			continue;
		}
		else{
			int x=ask(i,l,i,l+1);
			int y=allsum-x;
			if(x>0){
				int s=ask(i,l,i,l);
				int t=x-s;
				ans[i][l]=s,ans[i][l+1]=t;
			}
			if(y>0){
				int s=ask(i,l+2,i,l+2);
				int t=y-s;
				ans[i][l+2]=s,ans[i][l+3]=t;
			}
		}
	}
	ll fans=0,po2=1;
	rep(i,h)rep(j,w){
		fans=(fans+po2*ans[i][j])%K;
		po2=po2*2%K;
	}
	cout<<"! "<<fans<<"\n"<<flush;
}


Measured memory_bytes: 720
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1},{0,0}};
//typedef pair<int, int> P;
//priority_queue<int, vector<int>, greater<int> > q;
int main()
{
   IOS;
   double l;
   cin >> l;
   cout<<fixed<<setprecision(12)<<(l/3.0)*(l/3.0)*(l/3.0);
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yarrr
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <vector>
#include <algorithm>

class TreeRestoring {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n;
		in >> n;
		std::vector<int> heights(n);
		for (int i = 0; i < n; i++)
			in >> heights[i];
		int min_height = *std::min_element(heights.begin(), heights.end());
		int max_height = *std::max_element(heights.begin(), heights.end());
		int min_count = 0, max_count = 0;
		for (int v : heights) {
			if (v == min_height)
				++min_count;
			if (v == max_height)
				++max_count;
		}
		bool ok = true;
		ok &= min_height == (max_height + 1) / 2;
		if (max_height % 2 == 0)
			ok &= (min_count == 1);
		else
			ok &= (min_count == 2);
		ok &= (max_count >= 2);
		for (int height = min_height; height <= max_height; height++) {
			bool found = false;
			for (int v : heights)
				found |= (v == height);
			ok &= found;
		}
		if (ok)
			out << "Possible" << "\n";
		else
			out << "Impossible" << "\n";
	}
};


int main() {
	TreeRestoring solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 384
s = input()
n = len(s)

mod = {}

_s = 0
for i in range(n):
  _s = (_s + int(s[-(i + 1)]) * pow(10, i, 2019)) % 2019
  if _s in mod:
    mod[_s] = mod[_s] + 1
  else:
    mod[_s] = 1

ans = 0
for x in mod.keys():
  if x == 0:
    ans += mod[x] * (mod[x] + 1) // 2
  else:
    ans += mod[x] * (mod[x] - 1) // 2

print(ans)

Measured memory_bytes: 9292