akhauriyash/Code-Regression huggingface dataset:
# coding=utf-8
def counting_sort(input_list: list, upper: int) -> list:
    number = len(input_list)

    # noinspection PyUnusedLocal
    b = [0 for i in range(number+1)]
    # noinspection PyUnusedLocal
    counter_list = [0 for i in range(upper+1)]

    for j in input_list:
        counter_list[j] += 1

    for i in range(k+1):
        counter_list[i] += counter_list[i-1]

    for j in range(number):
        b[counter_list[input_list[j]]] = input_list[j]
        counter_list[input_list[j]] -= 1

    return b


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    k = 2000000
    a = counting_sort(a, k)
    a.pop(0)

    print(' '.join(map(str, a)))

Measured memory_bytes: 226292
import java.io.*;
import java.util.*;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		String s;
		StringTokenizer st;
		int i,a,b,c;
		try {
			s = r.readLine();
			int number = Integer.parseInt(s);
			for(i=0;i<number;i++){
				s = r.readLine();
				st = new StringTokenizer(s," ");
				a = Integer.parseInt(st.nextToken().toString());
				b = Integer.parseInt(st.nextToken().toString());
				c = Integer.parseInt(st.nextToken().toString());
				if((a*a+b*b==c*c)||(b*b+c*c==a*a)||(c*c+a*a==b*b)){
					System.out.println("YES");
				} else {
					System.out.println("NO");
				}
			}
		} catch (NoSuchElementException e) {
			System.exit(0);
		}
	}
}

Measured memory_bytes: 9872
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return map(int, input_tuple)


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


###############################################################################


def main():
    n, m, c = intin()
    blist = intina()
    alistlist = []
    for i in range(n):
        alistlist.append(intina())

    count = 0
    for alist in alistlist:
        csum = 0
        for i, a in enumerate(alist):
            csum += a * blist[i]
        csum += c
        if csum > 0:
            count += 1

    print(count)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
// D


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<ll> vll;

int main() {

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

    ll ans = a[0]-1;
    ll l = 1;
    for(int i=1; i<N; i++) {
	ll plus = 0;
	if(a[i] > l+1) { // 足せる
	    plus = a[i]/(l+1) - (a[i]%(l+1) == 0 ? 1 : 0); // 売れる個数の最大値
	    ans += plus;
	}
	else {
	    l = max(l,a[i]);
	}
    }
    cout << ans << endl;
    


    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;
#define endl '\n'

template<typename T>
inline bool chmin(T& x, T a) {
	if (x >= a) { x = a; return true; }
	return false;
}

template<typename T>
inline bool chmax(T& x, T a) {
	if (x <= a) { x = a; return true; }
	return false;
}

int score;
int stone[10][5];
bool flag[10][5];

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

	while (1) {
		string S; cin >> S;
		if (S == "#") { break; }
		int n = S.size();
		int N = 1 << n;

		int count = 0;
		set<string, greater<string>> small;
		set<string> big;

		string T0, T;
		vector<bool> hit(26, false);

		for (int _i = 0; _i < N; _i++) {
			T0 = S;
			int j = 0;
			bool result = true;
			for (int k = 1; k < N; k *= 2) {
				if (_i & k) {
					if (T0[j] == 'z') {
						result = false;
						break;
					}
					T0[j] += 1;
				}
				j++;
			}
			if (result == false) {
				continue;
			}
			T = T0; // 候補
			
			std::fill(hit.begin(), hit.end(), false);
			hit[0] = true;

			
			for (int i = 0; i < n; i++) {// 愚直シミュレーション
				int c = T[i] - 'a';
				if (hit[c] == false) {
					T[i]--;
					hit[c] = true;
				}
				if (T[i] != S[i]) {
					result = false;
					break;
				}
			}
			if (result) {
				count++;
				small.insert(T0);
				big.insert(T0);
				if (small.size() > 5) {
					small.erase(small.begin());
				}
				if (big.size() > 5) {
					big.erase(big.begin());
				}
			}
		}

		cout << count << endl;
		if (count > 10) {
			set<string> small2;
			for (auto itr = small.begin(); itr != small.end(); itr++) {
				small2.insert(*itr);
			}

			for (auto itr = small2.begin(); itr != small2.end(); itr++) {
				cout << *itr << endl;
			}
			for (auto itr = big.begin(); itr != big.end(); itr++) {
				cout << *itr << endl;
			}
		}
		else {
			for (auto itr = small.begin(); itr != small.end(); itr++) {
				big.insert(*itr);
			}
			for (auto itr = big.begin(); itr != big.end(); itr++) {
				cout << *itr << endl;
			}
		}
	}

	return 0;
}


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

int main()
{
  int N,K;
  cin >> N >> K;
  int ans = 1;
  rep(i, N) {
    ans = min(2*ans, ans+K);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
 

//result = Math.pow(num1, num3)
//StringBuffer str = new StringBuffer(hoge1);
//String hoge2 = str.reverse().toString();
//map.containsKey(A)

//Map<String, Integer> map = new HashMap<String, Integer>(n);
/*for ( キーのデータ型 key : マップの名前.keySet() ) {
	データのデータ型 data = マップの名前.get( key );
	
	// keyやdataを使った処理;
}*/
//int i = Integer.parseInt(s);
//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek
//Deque<String> qq=new ArrayDeque<>();//push,pop,peek
//ArrayList<String> cc = new ArrayList<>(n);
//Collections.sort(list);
//Array.sort(list);
//Arrays.asList(c).contains("a")
//list.set(1,"walk");
public class Main {
	static int a1[]= {0,-1,0,1};
	static int b1[]= {-1,0,1,0};
	private static Scanner sc = new Scanner(System.in);
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
	static int K;
	public static void main(String[] args) {
		int a=sc.nextInt();
		int b=sc.nextInt();
		if(b==1) {
			p(0);
		}else {
		p((int)Math.ceil((double)(b-1)/(a-1)));
		}
		}	
}


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

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

ll n,a;
vector<ll> x;

ll dp[64][64][3001];
// dp[i][j][k]:=x[0]...x[j-1]からi枚選んで総和をkにするカードの選び方の数

int main(){
    cin>>n>>a;
//    debug2(n,a);
    rep(i,n){
        ll xx;cin>>xx;
        x.push_back(xx);
    }

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

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=3000;k>=0;k--){
                dp[i][j][k] += dp[i][j-1][k];
                if(k-x[j-1]>=0){
                    dp[i][j][k] += dp[i-1][j-1][k-x[j-1]];
                }
            }
        }
    }

//    for(int i=0;i<=n;i++){
//        cout << i << endl;
//        cout << "xi ";
//        for(ll j=0;j<35;j++){
//            printf("%2lld ",j);
//        }
//        cout << endl;
//        for(int j=0;j<=n;j++){
//            if(j==0) cout << ".." << " ";
//            else printf("%2lld ",x[j-1]);
//            for(int k=0;k<35;k++){
////                cout << dp[i][j][k] << " ";
//                printf("%2lld ",dp[i][j][k]);
//            }
//            cout << endl;
//        }
//        cout << endl;
//    }

    ll ans=0;
    for(int i=1;i<=n;i++) ans += dp[i][n][a*i];

    cout << ans << endl;
}


Measured memory_bytes: 59264
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N,M;
  cin>>N>>M;
  
  vector<int> A(M);
for (int i = 0; i < M; i++) {
  cin >> A.at(i);
}
  
  int sw=0;
  for (int i = 0; i < M; i++) {
  sw=sw+A.at(i);
}
  
  if(N-sw<0){
    cout<<-1<<endl;
  }else{
    cout<<N-sw<<endl;
  }
  
}




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

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

    int x[n];
    int max = -1;
    for(int i = 0; i < n; i++){
        cin >> x[i];
        if(max < x[i]){
            max = x[i];
        }
    }

    ll ans = 10e9;
    ll now = 0;
    for(int i = 1; i <= max; i++){
        now = 0;
        for(int j = 0; j < n; j++){
            now += pow(x[j] - i,2);
        }
        if(ans > now){
            ans = now;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
if __name__ =='__main__':
    S = input()
    st = 0
    ed = 0
    cnt = 0
    flag = True
    for i, s in enumerate(S):
        if s=='A' and flag:
            st = i
            flag = False
        if s=='Z':
            ed = i
            cnt = max(cnt, ed-st)
    
    print(cnt+1)

Measured memory_bytes: 9168
N = input()
suma = 0
for i in N:
    suma += int(i)

c = False
for i in range(9):
    if str(i) in N[1:]:
        c = True
if c:
    print(9*(len(N)-1) + (int(N[0])-1))
else:
    print(9*(len(N)-1) + int(N[0]))


Measured memory_bytes: 38256
#include <bits/stdc++.h>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const ll Lmax=ll(1e18);
const ll INF=1e6;
const int Nmax=2e5+1;
const int Nd=61;


int main(){
  int a,b;
  cin>>a>>b;
  if(a>b){
    rep(i,a){
      cout<<b;
    }
    return 0;

  }else{
    rep(i,b){
      cout<<a;
    }

    return 0;
  }


}


Measured memory_bytes: 3604
import numpy as np
 
mod = 10**9 + 7
max_digit = 60
N = int(input())
A = np.array(list(map(int, input().split())))

result = 0
base = 1
for _ in range(max_digit + 1):
  a = A % 2
  c = np.count_nonzero(a == 0)
  result = (result + (base*(N - c)*c) % mod) % mod
  A = A >> 1
  base = base*2 % mod

print(result)


Measured memory_bytes: 48800
#include <iostream>
#include <climits>
#include <cmath>

using namespace std;

int main(void) {
  int n, *w, s1, s2;
  int min, tmp;
  
  cin >> n;
  w = new int[n];
  min = INT_MAX;
  s1 = s2 = 0;
  for (int i = 0; i < n; i++) {
    cin >> w[i];
    s2 += w[i];
  }
  
  for (int i = 0; i < n; i++) {
    s1 += w[i]; s2 -= w[i];
    //cout << s1 <<',' << s2 << ',' << abs(s1 - s2) << endl;
    min = min < abs(s1 - s2) ? min : abs(s1 - s2);
    
  }
  
  cout << min << endl;
  
  return 0;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#pragma GCC optimize "-O3"
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned short us;
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll infll=(1ull<<63)-1;
const int inf=(1ull<<31)-1;
vector<vector<int>> g(200001);
bool vis[200001];
ll a[200001];
int n,m;

void dfs(int v){
	vis[v]=true;
	for (int j=0;j<g[v].size();j++){
		if (!vis[g[v][j]]){
			a[g[v][j]]+=a[v];
			dfs(g[v][j]);
		}
	}
}

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(18);
	cin>>n>>m;
	for (int i=0,f,t;i+1<n;i++){
		cin>>f>>t;
		f--,t--;
		g[f].push_back(t);
		g[t].push_back(f);
	}
	for (int i=0,f,v;i<m;i++){
		cin>>f>>v;
		a[--f]+=v;
	}
	fill(vis,vis+200001,false);
	dfs(0);
	for (int i=0;i<n;i++)
		cout<<a[i]<<" ";
	return 0;
}

Measured memory_bytes: 21376
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdio>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 1000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}
map<string,int> mp;
void solve(){
	string s;
	cin>>s;
	mp["SSS"]=0;
	mp["SSR"]=1;
	mp["SRS"]=1;
	mp["SRR"]=2;
	mp["RSS"]=1;
	mp["RSR"]=1;
	mp["RRS"]=2;
	mp["RRR"]=3;
	cout<<mp[s];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 3652
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
p_list=[]
score=0
for i in range(len(t)):
    if i<k:
        if t[i]=='r':
            p_list.append('p')
            score+=p
        elif t[i]=='s':
            p_list.append('r')
            score+=r
        else:
            p_list.append('s')
            score+=s
    else:
        if t[i]=='r':
            if p_list[i-k]=='p':
                if i+k>=len(t):
                    p_list.append('a')
                else:
                    p_list.append(t[i+k])
            else:
                p_list.append('p')
                score+=p
        elif t[i]=='s':
            if p_list[i-k]=='r':
                if i+k>=len(t):
                    p_list.append('a')
                else:
                    p_list.append(t[i+k])
            else:
                p_list.append('r')
                score+=r
        else:
            if p_list[i-k]=='s':
                if i+k>=len(t):
                    p_list.append('a')
                else:
                    p_list.append(t[i+k])
            else:
                p_list.append('s')
                score+=s
print(score)


Measured memory_bytes: 4212
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 5e5 + 10;
int N;
LL A[500], S, X, D, Y;
int main()
{
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
    {
        scanf("%lld", &A[i]);
        if(i <= 2)
            S += A[i];
        else
            X ^= A[i];
    }
    if(S - X < 0 || (S - X) % 2 != 0)
    {
        printf("-1\n");
        return 0;
    }
    else
        D = (S - X) / 2;
    if((D & X) || D > A[1])
    {
        printf("-1\n");
        return 0;
    }
    for(int i = 60; i >= 0; i--)
    {
        if((X & (1LL << i)) && (D ^ (Y | (1LL << i))) <= A[1])
            Y |= (1LL << i);
    }
    if(D ^ Y)
        printf("%lld\n", A[1] - (D ^ Y));
    else
        printf("-1\n");
    return 0;
}


Measured memory_bytes: 3808
import scala.annotation.tailrec

object Main extends App {

  import scala.io.StdIn._
  import scala.math._

  val Array(n, q) = readLine.trim.split(' ').map(_.toInt)
  var orient: Int = 0
  for (_ ← 0 until q){
    readLine.trim.split(' ').map(_.toInt) match {
      case Array(0, k) ⇒ println((orient + k - 1) % n + 1)
      case Array(1, k) ⇒ orient = (orient + k) % n
    }
  }
  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}


Measured memory_bytes: 160092
import math
a,b,h,m=map(int,input().split())
h=h*30+m*0.5
m*=6
d=abs(h-m)
d=360-abs(h-m) if d>360-d else d
print(math.sqrt(a**2+b**2-2*a*b*math.cos(math.radians(d))))

Measured memory_bytes: 9516
//C - One-stroke Path: 
//Assunto: 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define loop(i, a, b) for(int i = a; i < b; i++)
#define loopBack(i, a, b) for(int i = a; i >= b; i--)
#define INF INT_MAX
#define LINF LLONG_MAX
#define DINF DBL_MAX
#define MAX 100050
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

int n, m, x, y;
int ans = 0;

void dfs(int no, vector<bool> vis, int total, vector<int> adj[]) {
    if(vis[no]) return;
    total++;
    if(total == n) ans++;
    vis[no] = true;
    for(auto x: adj[no]) {
        dfs(x, vis, total, adj);
    }
} 

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n >> m;
    vector<int> adj[n+1];
    loop(i, 0, m) {
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    vector<bool> vis(n+1, false);
    dfs(1, vis, 0, adj);
    cout << ans << '\n';
}

Measured memory_bytes: 256
#include <stdio.h>

int partition(int*, int, int);

int main(){
  int i,n,A[100000],q;

  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&A[i]);

  q=partition(A,0,n-1);

  for(i=0;i<n;i++){
    if(i)printf(" ");
    if(i==q)printf("[");
    printf("%d",A[i]);
    if(i==q)printf("]");
  }
  printf("\n");
  
  return 0;
}

int partition(int* A, int p, int r){
  int x,i,j,tmp1,tmp2;
  x=A[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(A[j]<=x){
      i+=1;
      tmp1=A[i];
      A[i]=A[j];
      A[j]=tmp1;
    }
  }
  
  tmp2=A[i+1];
  A[i+1]=A[r];
  A[r]=tmp2;
  return i+1;
}



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

int main(){
    ll n; cin>>n;
    vector<ll> a(n),b(n);
    for(int i=0; i<n; i++) cin>>a[i]>>b[i];
    ll ans=0,sum=0,res;
    for(int i=n-1; i>=0; i--) {
        res = b[i] - (a[i]+sum) % b[i];
        res %= b[i];
        ans += res;
        sum += res;
    }
    cout<<ans;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;


int main(){
    int x,y,z;cin>>x>>y>>z;
    x-=z;
    int ans=x/(y+z);
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 3512
N = int(input())
A = list(map(int,input().split()))
cnt = 1
flag = ""
for i in range(1,N):
	if A[i - 1] > A[i] and flag == "":
		flag = "+"
	elif A[i - 1] < A[i] and flag == "":
		flag = "-"
	elif flag == "+" and (A[i - 1] < A[i]):
		cnt += 1
		flag = ""
	elif flag == "-" and (A[i - 1] > A[i]):
		cnt += 1
		flag = ""
print(cnt)

Measured memory_bytes: 14224
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

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

	int n;
	cin>>n;
	vi in(n);
	rep(i,n)cin>>in[i];
	sort(all(in));
	cout<<in[n/2]-in[n/2-1]<<endl;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            int a = scanner.nextInt();
            if(a%2==1 && i%2==1) ans++;
        }

        System.out.println(ans);

    }



}


Measured memory_bytes: 35852
from collections import defaultdict
d = defaultdict(int)
ans=0
S=input()
T=input()
for i in range(len(S)):
 if d[S[i]]==0 or d[S[i]]==T[i]:
  d[S[i]]=T[i]
 else:
  ans+=1
  break
d = defaultdict(int)
for i in range(len(S)):
 if d[T[i]]==0 or d[T[i]]==S[i]:
  d[T[i]]=S[i]
 else:
  ans+=1
  break
if ans>0:
 print("No")
else:
 print("Yes")

Measured memory_bytes: 9660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
const ll INF=1e9+7;
const ll N = 1002;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a,b;
	cin>>a>>b;
	if(a<=8&&b<=8)cout<<"Yay!"<<endl;
	else cout<<":("<<endl;
	return 0;
}


Measured memory_bytes: 256
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():
    _ = int(sys.stdin.readline().rstrip())
    Arr = [int(x) for x in sys.stdin.readline().rstrip().split()]

    K = 43

    #
    A = Arr[0]
    B = Arr[1]

    S = A + B
    X = 0
    for i in range(2, len(Arr)):
        X ^= Arr[i]

    # print(S, X)

    # 次を満たすa, b が見つかるか？
    #  a+b=S, a^b=X, a<=A

    # 桁DP : 桁を一つずつ決めていくようなDP
    # dp[今の桁数 = 0:42][繰り上がりがあるか = 0,1][今までがA以下かどうか 0=以下、1=より大きい] = 最大値
    # 値は最大値。満たすものがなければ -1
    dp = [[[-1 for x in [0, 1]] for _ in [0, 1]] for _ in range(K)]

    dp[0][0][0] = 0  # 最初

    v = 1
    for i in range(K - 1):  # 桁数
        cx = X & 1  # current X
        cs = S & 1  # current S
        ca = A & 1  # current A
        for j in range(2):  # 繰り上がりある／ない
            for k in range(2):  # 今までの範囲が A 以下かどうか
                if dp[i][j][k] == -1:  #
                    continue

                for na in range(2):
                    for nb in range(2):
                        ni = i + 1
                        nj = 0
                        nk = k
                        if na ^ nb != cx:  # a ^ b = A か？
                            continue

                        ns = na + nb + j
                        if ns % 2 != cs:  # a + b = S か？
                            continue

                        # ここで遷移は確定

                        if ns >= 2:  # 繰り上がり処理
                            nj = 1

                        if ca < na:
                            nk = 1
                        elif ca == na:
                            nk = k
                        else:
                            nk = 0

                        dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] | (v * na))

        X >>= 1
        S >>= 1
        A >>= 1
        v <<= 1
        # print(v)

    a = dp[K - 1][0][0]
    if a == -1 or a == 0:
        print(-1)
    else:
        print(Arr[0] - a)


main()


Measured memory_bytes: 9348
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
using namespace std;
long long MOD = 1e9 + 7;

int A, B;

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

Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

const int mod = (int) 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (long long) x * y % mod;
}

int myPower(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}

void precalc() {
}


const int maxn = (int) 1e5 + 10;
int a[maxn];
int n, minl;

int read() {
  if (scanf("%d%d", &n, &minl) < 2) {
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
  }
  return 1;
}

void solve() {
  for (int i = 0; i < n - 1; ++i) {
    if (a[i] + a[i + 1] >= minl) {
      printf("Possible\n");
      for (int j = 0; j < i; ++j) {
        printf("%d\n", j + 1);
      }
      for (int j = n - 2; j >= i; --j) {
        printf("%d\n", j + 1);
      }
      return;
    }
  }
  printf("Impossible\n");
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 1152
#include <iostream>
 
using namespace std;
 
typedef long long int ll;
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,ans=0;
    cin >> n;
 
   // ans = (n*(n+1))/2;
 
    for(int i=1 ; i<=n ; i++)
    {
        if(i%3==0 || i%5==0)
           {
 
           }
           else
            ans+=i;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3652
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <functional>
#include <numeric>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(void) {
	char s;
	cin >> s;
	if (isupper(s)) cout << "A" << endl;
	else cout << "a" << endl;
	return 0;
}

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

using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;

int n, k;
vector<int> G[N];
int num[N];

int mx[N], mi[N], dep[N];
int l[N], r[N];

bool ok = 1;

void dfs(int u, int fa)
{
	if (num[u] != -1)
	{
		mx[u] = num[u] - dep[u];
		mi[u] = num[u] + dep[u];
	}
	else
	{
		mx[u] = -inf;
		mi[u] = inf;
	}
	for (int i = 0; i < (int) G[u].size(); i++)
	{
		int v = G[u][i];
		if (v == fa) continue;
		dep[v] = dep[u] + 1;
		dfs(v, u);
		mx[u] = max(mx[u], mx[v]);
		mi[u] = min(mi[u], mi[v]);
	}
}
void dfs2(int u, int fa)
{
	if (num[u] == -1)
	{
		if (fa == 0)
		{
			num[u] = l[u];
		}
		else if(l[u] <= num[fa] - 1 && num[fa] - 1 <= r[u])
		{
			num[u] = num[fa] - 1;
		}
		else if(l[u] <= num[fa] + 1 && num[fa] + 1 <= r[u])
		{
			num[u] = num[fa] + 1;
		}
		else
		{
			ok = 0;
			return;
		}
	}
	else
	{
		if (fa != 0 && abs(num[u] - num[fa]) != 1)
		{
			ok = 0;
			return;
		}
	}
	//printf("%d %d\n", u, num[u]);
	for (int i = 0; i < (int) G[u].size(); i++)
	{
		int v = G[u][i];
		if (v == fa) continue;
		dfs2(v, u);
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		num[i] = -1;
	}
	scanf("%d", &k);
	for (int i = 1; i <= k; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		num[x] = y;
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++)
	{
		l[i] = mx[i] + dep[i];
		r[i] = mi[i] - dep[i];
		//printf("%d %d %d %d\n", i, l[i], r[i], num[i]);
	}
	dfs2(1, 0);
	
	if (ok == 0)
	{
		puts("No");
	}
	else
	{
		puts("Yes");
		for (int i = 1; i <= n; i++) printf("%d\n", num[i]);
	}
	return 0;
}

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

int main() {
  int64_t N;
  cin >> N;
  if(N==1)
  {
    cout << 1;
  	return 0;
  }
  int64_t Ln=0;
  int64_t Ln_1=1;
  int64_t Ln_2=2;
  for (int i=0; i<N-1; i++)
  {
    if(i!=0)
    {
    Ln_2=Ln_1;
    Ln_1=Ln;
    }
    Ln=Ln_1+Ln_2;
  }
  cout << Ln <<endl; 
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define pb push_back
using namespace std;
typedef pair<int,int> pii;

int main(){
  int n;
  double t,a;
  
  cin>>n;
  cin>>t>>a;
  
  double tmp,tmp2;
  int res=0;

  cin>>tmp;
  tmp=t-0.006*tmp;
  tmp2=tmp;
  
  for(int i=1;i<n;i++){
    cin>>tmp;
    tmp=t-0.006*tmp;
    if(fabs(tmp2-a)>fabs(tmp-a)){
      res=i;
      tmp2=tmp;
    }
  }
  cout<<res+1<<endl;
  
  return 0;
}


Measured memory_bytes: 256
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = na()

    a.insert(0, 0)
    a.append(0)

    total = 0
    for i in range(1, len(a)):
        total += abs(a[i] - a[i - 1])

    for i in range(1, len(a) - 1):
        smaller = min(a[i - 1], a[i + 1])
        current = a[i]
        larger = max(a[i - 1], a[i + 1])

        if smaller <= current <= larger:
            print(total)
        elif current < smaller:
            print(total - abs(current - smaller) * 2)
        elif current > larger:
            print(total - abs(current - larger) * 2)


if __name__ == '__main__':
    main()


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


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

  ll a,b,c;
  cin >> a >> b >> c;

  bool f = false;
  REP1(i, b){
    if((a%b*i)%b == c)
      f = true;
  }

  if(f)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


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

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pair<int,int>> a(n + 1);
	for (int i = 1;i <= n;++i) {
		int x;
		cin >> x;
		a[i] = {x,-i};
	}
	sort(a.begin() + 1,a.end());
	reverse(a.begin() + 1,a.end());
	vector<long long> cnt(n + 1);
	a.emplace_back(0,0);
	int mx = -1e9;
	int count = 0;
	for (int i = 1;i <= n;++i) {
		int j = i + 1;
		while (j <= n && a[i].first == a[j].first) ++j;
		mx = max(mx,a[i].second);
		count += j-i;
		cnt[-mx] += 1ll * count * (a[i].first - a[j].first);
		i = j-1;
	}
	for (int i = 1;i <= n;++i) cout << cnt[i] <<"\n";
}

Measured memory_bytes: 2672
#include <iostream>

using namespace std;

int main(){
	int r, g, b;
	cin >> r >> g >> b;
	
	if((r*100+g*10+b)%4 == 0){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
	
	return 0;
}

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

int main(){
    int N, K;
    std::cin >> N >> K;
    std::vector< int > P(N);
    std::vector< int > C(N);
    for(int i=0; i<N; i++){
        std::cin >> P[i];
        P[i]--;
    }
    for(int i=0; i<N; i++){
        std::cin >> C[i];
    }
    
    std::vector< long long > loop_score(N);
    std::vector< int > loop_cnt(N, 0);
    long long max = -1e18;
    
    for(int i=0; i<N; i++){
        if(loop_cnt[i] == 0){
            int cnt = 1;
            int index = P[i];
            long long score = C[i];
            long long max_score = C[i];
            std::vector< int > root(1, i);
            while(i != index && cnt < K){
                score += C[index];
                if(max_score < score){
                    max_score = score;
                }
                index = P[index];
                root.push_back(index);
                cnt++;
            }
            if(i == index){
                for(int j=0; j<root.size(); j++){
                    loop_score[root[j]] = score;
                    loop_cnt[root[j]] = cnt;
                }
                
                if(score > 0){
                    int loop_N = K / cnt - (K % cnt == 0) - 1;
                    if(loop_N > 0){
                        score = score * loop_N;
                        cnt = cnt * loop_N;
                        if(max_score < score){
                            max_score = score;
                        }
                    }
                    while(cnt < K){
                        score += C[index];
                        if(max_score < score){
                            max_score = score;
                        }
                        index = P[index];
                        cnt++;
                    }
                }
            }
            
            if(max < max_score){
                max = max_score;
            }
        }else{
            int cnt = 1;
            int index = P[i];
            long long score = C[i];
            long long max_score = C[i];
            if(loop_score[i] > 0){
                int loop_N = K / loop_cnt[i] - (K % loop_cnt[i] == 0) - 1;
                if(loop_N > 0){
                    score += loop_score[i] * loop_N;
                    cnt += loop_cnt[i] * loop_N;
                    if(max_score < score){
                        max_score = score;
                    }
                }
            }else{
                int loop_N = K / loop_cnt[i] - (K % loop_cnt[i] == 0) - 1;
                if(loop_N > 0){
                    cnt += loop_cnt[i] * loop_N;
                }
            }
            while(cnt < K){
                score += C[index];
                if(max_score < score){
                    max_score = score;
                }
                index = P[index];
                cnt++;
            }
            if(max < max_score){
                max = max_score;
            }
        }
    }
    
    
    std::cout << max << std::endl;
    
    
    return 0;
    
}


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

int main(){
	int a[100], i = 0;
	while (true){
		cin >> a[i];
		if (cin.eof()) { break; }
		if (a[i] == 0 ){
			cout << a[i - 1] << endl;
			i--;
		}
		else { i++; }
	}
	return 0;
}

Measured memory_bytes: 2996
package main

import (
	"fmt"
)

func main() {
	var n, k, q int

	var a, user []int

	n = scanInt()
	k = scanInt()
	q = scanInt()

	for i := 0; i < n; i++ {
		user = append(user, 0)
	}

	for i := 0; i < q; i++ {
		a = append(a, scanInt())
	}

	for _, u := range a {
		i := u - 1
		user[i] = user[i] + 1
	}

	for _, point := range user {
		end := k - q + point
		if end > 0 {
			fmt.Println("Yes")
		} else {
			fmt.Println("No")
		}
	}

}

func scanStr() string {
	var s string
	fmt.Scan(&s)
	return s
}

func scanInt() int {
	var i int
	fmt.Scan(&i)
	return i
}


Measured memory_bytes: 6784
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll t,p,q,x,c1,c2,c3,d,e,f;
    ll n,m,z;
    vector<ll>v;
    cin>>n;
    m=((n-1)*n)/2;
    cout<<m<<endl;
}









Measured memory_bytes: 256
n = int(input())
as_list = input().split(" ")
a_list = [ int(astr) for astr in as_list ]

x = 0

for a in a_list:
    x ^= a
for i in range(n):
    a_list[i] &= ~x
pos = 0

for b in range(59,-1,-1):

    for i in range(pos,n):
        a = a_list[i]
        if a & (1 << b):
            if i > pos:
                
                # i番目とpos番目を入れ替える
                a_list[i] = a_list[pos]
                a_list[pos] = a

            for j in range(n):
                if j == pos:
                    continue
                if a_list[j] & (1 << b):
                    a_list[j] ^= a
            pos += 1
            break
    
y = 0

for a in a_list:
    y ^= a

print(x + 2 * y)


Measured memory_bytes: 16116
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int N = in.nextInt(); // > 0, odd, up to 3000

            double[] dp = new double[(N / 2) + 1];
            // dp[i] = probability of having i heads
            dp[0] = 1;
            for (int coin = 0; coin < N; coin++)
            { // coins
                double p_tails = 1 - in.nextDouble();
                for (int i = (N / 2); i >= 0; i--)
                {
                    if (i - 1 >= 0)
                    {
                        dp[i] = dp[i - 1] * p_tails + dp[i] * (1 - p_tails);
                    } else
                    {
                        dp[i] = +dp[i] * (1 - p_tails);
                    }
                }
            }
            double sum = 0;
            for (int tails = 0; tails <= N / 2; tails++)
            {
                sum += dp[tails];
            }
            out.print(sum);
        }

    }
}



Measured memory_bytes: 36116
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int n,point[500007],pat[500007] = { 0 };
	int sum = 0,i = 1;
	scanf("%d",&n);
	for (i = 1; (i <= n && sum < n); ++i)
	{
		sum += i;
		point[i] = i;
		pat[i] = 1;
	}
	if(sum == n){
		for (int k = 1; k < i; ++k)
		{
			if(pat[k])	printf("%d\n",point[k]);
		}
	}
	else{
		pat[abs(sum - n)] = 0;
		for (int k = 1; k < i; ++k)
		{
			if(pat[k])	printf("%d\n",point[k]);
		}
	}
	return 0;
}


Measured memory_bytes: 4096
#include "bits/stdc++.h"
#define all(x) x.begin(),x.end()
#define rep(i,N) for(int i=0;i<(int)N;++i)
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using vll2 = vector<vector<ll>>;
const ll INF = (1LL << 30);
const ll LINF = (1LL << 60);
const ll MOD = 1e9 + 7;

struct Data {
   int y;
   int x;
   ll cost;
   bool operator<(const Data& r) const {
      return cost < r.cost;
   }
   bool operator>(const Data& r) const {
      return cost > r.cost;
   }
};

int main() {
   cin.tie(0);
   ios::sync_with_stdio(false);
   using P = pair<int, int>;
   int dy[] = { 0, 1, 0, -1 };
   int dx[] = { -1, 0, 1, 0 };

   while (true) {
      int R; cin >> R;
      if (R == 0) break;
      vll2 v(2, vll(R + 1, INF));
      v[0][0] = v[1][0] = 0;
      rep(k, 2) {
         int W, H, X, Y;
         cin >> W >> H >> X >> Y, X--, Y--;
         vll2 L(H, vll(W));
         rep(i, H) rep(j, W) cin >> L[i][j];

         priority_queue<Data, vector<Data>, greater<Data>> que;
         que.emplace(Data{ Y, X, 1 });
         int cnt = 1;
         ll res = 1;
         while (cnt <= R && !que.empty()) {
            Data dat = que.top(); que.pop();
            if (L[dat.y][dat.x] == INF) continue;
            res = max(res, dat.cost);
            v[k][cnt++] = res;
            L[dat.y][dat.x] = INF;
            rep(i, 4) {
               int ny = dy[i] + dat.y, nx = dx[i] + dat.x;
               if (ny < 0 || ny >= H || nx < 0 || nx >= W || L[ny][nx] == INF) continue;
               que.emplace(Data{ ny, nx, L[ny][nx] });
            }
         }
      }

      ll ans = LINF;
      for (int i = 0; i <= R; ++i) {
         ans = min(ans, v[0][i] + v[1][R - i]);
      }
      cout << ans << endl;
   }
}



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

int main() {
	int h,w,x,y;
	cin >> w >> h >> x >> y;
	double s=(double)h*w/2;
	char p='0';
	if(x*2==w&&y*2==h)
	{
		p='1';
	}
	cout << fixed << setprecision(15) << s << ' ' << p << endl;
	return 0;
}


Measured memory_bytes: 3740
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            a[i]+=1

    for i in range(3,10**5+1):
        a[i]+=a[i-1]

    for i in range(q):
        l,r=map(int,input().split())
        print(a[r]-a[l-1])

main()

Measured memory_bytes: 7268
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};

int main(){
    int H,W;
    cin >> H >> W;
    vector<string> graph(H);
    vector<vector<int>> reached(H,vector<int>(W,0));
    for(int i=0;i<H;i++) cin >> graph[i];

    queue<pair<int,int>> que;
    que.push(make_pair(0,0));
    reached[0][0] = 1;
    while(!que.empty()){
        int x = que.front().second,y = que.front().first;
        que.pop();
        for(int i=0;i<4;i++){
            int d_x = x+dx[i],d_y = y+dy[i];
            if(d_x<0 || d_x>=W || d_y<0 || d_y>=H) continue;
            if(reached[d_y][d_x]>0 || graph[d_y][d_x]=='#') continue;
            que.push(make_pair(d_y,d_x));
            reached[d_y][d_x] = reached[y][x]+1;
        }
    }
    int cnt=0;
    for(int y=0;y<H;y++){
        for(int x=0;x<W;x++){
            if(graph[y][x] == '.') cnt++;
        }
    }
    int ans = reached[H-1][W-1]>0 ? cnt-reached[H-1][W-1] : -1;

    cout << ans << endl;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int dp[20][20];
int main(){
    int a,b;
    int n;
    int x[40],y[40];
    while(true){
    cin>>a>>b;
    if(a==0&&b==0)
        break;
    cin>>n;
    for(int i=0;i<20;i++)
        for(int j=0;j<20;j++)
            dp[i][j]=0;
    for(int i=1;i<n+1;i++){
        cin>>x[i]>>y[i];
        dp[y[i]][x[i]]=-1;
    }
    dp[1][1]=1;
    for(int i=1;i<b+1;i++){
        for(int j=1;j<a+1;j++){
            if(dp[i][j]!=-1){
            if(dp[i-1][j]>0)
                dp[i][j]+=dp[i-1][j];
            if(dp[i][j-1]>0)
                dp[i][j]+=dp[i][j-1];
            }
            else
                dp[i][j]=0;
        }
    }
    cout<<dp[b][a]<<endl;
    }
    return 0;
}
 

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=1; i<=(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int X;
    cin>>X;
    int sum=0;
    for(int i=1; ; i++) {
        if(sum>=X) {
            cout<<i-1<<endl;
            break;
        }
        sum+=i;
    }
}

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

int main(void) {

  char s[51];
  scanf("%s", s);
  char akiba[10] = "AKIHABARA";
  int current = 0;
  for (int i = 0; i < strlen(s); i++) {
    if (current > 8) {
      printf("NO\n");
      return 0;
    }
    if (s[i] != akiba[current]) {
      if (akiba[current] == 'A') {
        current++;
        if (current > 8) {
          printf("NO\n");
          return 0;
        }
        if (s[i] != akiba[current]) {
          printf("NO\n");
          return 0;
        } else {
          current++;
        }
      } else {
        printf("NO\n");
        return 0;
      }
    } else {
      current++;
    }
  }
  if (current < 8) {
    printf("NO\n");
    return 0;
  }
  printf("YES\n");

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n, m; cin >> n >> m;
  long long ans = n * m;
  if(n % 3) ans = min(ans, m);
  else ans = 0;
  if(m % 3) ans = min(ans, n);
  else ans = 0;
  auto f = [&](long long i, long long j){
    long long p1 = i * j;
    long long p2 = (n - i) * j;
    long long p3 = n * (m - j);
    return max({p1, p2, p3}) - min({p1, p2, p3});
  };
  for(int rot = 0; rot < 2; rot++){
    swap(n, m);
    for(int i = 0; i <= n; i++){
      int lo = 0, hi = m;
      while(hi - lo >= 5){
      	int mid = (lo+hi)>>1;
        if(f(i, mid) > f(i, mid + 1)) lo = mid + 1;
        else hi = mid;
      }
      while(lo <= hi){
        ans = min(ans, f(i, lo));
        lo++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256