akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
// TLEの場合はbit shiftに変える
using namespace std;
int N, M;
bool same_check(vector <string>A, vector <string>B, int strow, int stcol)
{
  if ((strow+M) > N) return false;
  if ((stcol+M) > N) return false;
  for (int Brow = 0;  Brow < M; Brow++) {
    for (int Bcol = 0; Bcol < M; Bcol++) {
      if ((B[Brow][Bcol])!=(A[Brow+strow][Bcol+stcol])) {
        return false;
      }
    }
  }
  return true;
}
int main()
{
  cin >> N >> M;
  vector <string> A(N), B(M);
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < M; i++) cin >> B[i];
  
  bool ans = false;
  for (int row = 0; row < N-M+1; row++) {
    for (int col = 0; col < N-M+1; col++) {
      if (same_check(A, B, row, col)) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}


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

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

	vector<int> H(N);
	rep(i, N) cin >> H.at(i);
	// rep(i, N) cout << H.at(i) << " ";
	int cnt = 0;
	int ans = 0;
	rep2(i, N, 1, 1){
		if (H.at(i - 1) >= H.at(i)) cnt++;
		else {
			ans = max(ans, cnt);
			cnt = 0;
			// cout << H.at(i - 1) << " " << H.at(i) << endl;
		}
	}
	ans = max(ans, cnt);
	cout << ans << endl;
}

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

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
#define se cout << "test ok" << endl;
#define sp << " " <<
#define enl "\n";
using namespace std;
using ll=long long;
using ld=long double;
ll mod = ll(1e9)+7;
ll inf = ll(1e18);
void bl(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void bl2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b){a=b; return true;} return false; }
template<typename T> inline bool chmin(T &a, T b){ if(a>b){a=b; return true;} return false; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ fill((T*)array, (T*)(array+N), val); }
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

#include <iostream>
#include <vector>
#include <map>
using namespace std;

namespace dbg {
    using ll = long long;

    class Debug {
    public:
        Debug(){}
        template<typename T>
        void vd(vector<T> vec);
        template<typename T>
        void vd2(vector<vector<T>> vec);
        template<typename T>
        void ad(T *arr, ll n);
        template<typename T, size_t N>
        void ad2(T (&arr)[N], ll n);
        template<typename T>
        void md(T mp);
    };

    template<typename T>
    void Debug::vd(vector<T> vec) {
        for (auto vv : vec) cout << vv << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::vd2(vector<vector<T>> vec) {
        for (auto vv : vec) for (auto vvv : vv) cout << vvv << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::ad(T *arr, ll n) {
        for (int i = 0; i <= n; i++) cout << arr[i] << " ";
        cout << endl;
    }

    template<typename T, size_t N>
    void Debug::ad2(T (&arr)[N], ll n) {
        for (int i = 0; i <= N; i++) for (int j = 0; j <= n; j++) cout << arr[i][j] << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::md(T mp) {
        cout << "key : value" << endl;
        for (auto const &m : mp) cout << m.first << " : " << m.second << endl;
        cout << endl;
    }

}

#endif //INCLUDE_DEBUG_HPP

using dbg::Debug;
Debug debug;

class ALucky7 {
public:
	void solve(std::istream& in, std::ostream& out) {
	    string n;
	    in >> n;

	    bool flg = false;
	    for(int i=0; i<n.length(); i++){
            if(n[i] == '7') flg = true;
	    }

	    bl(flg, out);
	}
};


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


Measured memory_bytes: 3628
<?php

fscanf(STDIN, "%d", $n);
$A = array_map('intval', explode(' ', trim(fgets(STDIN))));

$sum = array_sum($A);
$odd_sum = 0;
for ($i = 0; $i < $n; ++$i) {
    $A[$i] = $A[$i] * 2;

    if (($i + 1) % 2 === 1) {
        $odd_sum += $A[$i];
    }
}

$m = [];
$m[0] = $odd_sum - $sum;
for ($i = 0; $i < $n - 1; ++$i) {
    $m[$i + 1] = $A[$i] - $m[$i];
}

echo implode(' ', $m);


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

#define NREP for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(),(x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;
const static ll MOD = 1e9+7;

int main(int argc, char *argv[]) {
    ll n, x;
    cin >> n >> x;

    vector<ll> a(n);
    NREP {
        cin >> a[i];
    }

    sort(ALL(a));

    ll ans = 0;
    NREP {
        if (i == n-1) {
            if (x == a[i]) ans++;
            break;
        }

        if (x >= a[i]) {
            x -= a[i];
            ans++;
        } else {
            break;
        }
    }

    MSG(ans)
}


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

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n,ans=0,sum=0; cin>>n;
    vector<ll> a(n);
    rep(i,n){
        cin>>a[i];
        sum+=a[i];
      	sum%=mod;
    }
    
    rep(i,n-1){
        sum-=a[i];
        if(sum<0) sum+=mod;
        ans += a[i]*sum;
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4844
N=int(input())
S=list(input())
K=int(input())

ans = []
a = S[K-1]

for i in range(N):
    if S[i] == S[K-1]:
       ans.append(a)
    else:
       ans.append('*')

mojiretu = ' '

for x in ans:
    mojiretu += x
    
print(mojiretu)
    

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  __MAKE_TIME__  Problem: __PROBLEM__ / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */



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

	LL N; cin >> N;
	LL M; cin >> M;
	LL ans = 0;
	VL f(1e5 + 10);
	f[0] = 1;
	FOR(i, 1, 1e5 + 5) {
		f[i] = i * f[i - 1];
		f[i] %= MOD;
	}
	if (abs(N - M) <= 1) {
		ans = f[N] * f[M];
		if (N == M)ans *= 2;
		ans %= MOD;

	}
	else ans = 0;
	cout << ans << endl;

	return 0;
}


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

using namespace std;
using ll = long long;

#define sz(a) (int)a.size()

const int N = 5e5 + 2;
const ll MOD = 1e9 + 7;

struct IT {
    struct Node {
        int lf, rg;
        int lz = 0;
    };
    vector<Node> a;

    void init(int n) { a.resize(n * 4 + 2); }

#define md ((l + r) >> 1)
#define nx (i << 1)
    void down(int i) {
        if (a[i].lf == a[i].rg) return;
        a[nx].lz += a[i].lz;
        a[nx + 1].lz += a[i].lz;
        a[i].lz = 0;
    }

    void build(int l, int r, int i = 1) {
        if (l > r) return;
        a[i].lf = l;
        a[i].rg = r;
        if (l == r) return;
        build(l, md, nx);
        build(md + 1, r, nx + 1);
    }

    void inc(int l, int r, int x, int i = 1) {
        if (l > r) return;
        if (a[i].lf > r || a[i].rg < l) return;
        if (l <= a[i].lf && a[i].rg <= r) {
            a[i].lz += x;
            return;
        }
        down(i);
        inc(l, r, x, nx);
        inc(l, r, x, nx + 1);
    }

    void update(int p, int x, int i = 1) {
        if (a[i].lf > p || a[i].rg < p) return;
        if (a[i].lf == p && a[i].rg == p) {
            a[i].lz = 0;
            return;
        }
        down(i);
        update(p, x, nx);
        update(p, x, nx + 1);
    }

    int get(int p, int i = 1) {
        if (a[i].lf > p || a[i].rg < p) return INT_MIN;
        if (a[i].lf == p && a[i].rg == p) return a[i].lz;
        down(i);
        return max(get(p, nx), get(p, nx + 1));
    }
#undef md
#undef nx
} stree;

int n, a[N];
vector<int> va;
ll f[N][2], tmp[N];

inline int idx(int x) {
    return (lower_bound(va.begin(), va.end(), x) - va.begin()) + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] ^= a[i - 1];
        if (a[i]) va.push_back(a[i]);
    }
    sort(va.begin(), va.end());
    va.erase(unique(va.begin(), va.end()), va.end());
    if (a[n] == 0) {
        stree.init(sz(va));
        stree.build(1, sz(va));
        for (int i = 0; i <= sz(va); ++i) f[i][0] = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] == 0) {
                (f[0][0] *= 2) %= MOD;
                stree.inc(1, sz(va), 1);
            } else {
                int ps = idx(a[i]);
                int tp = stree.get(ps);
                stree.update(ps, 0);
                (f[ps][0] += f[ps][1] * tp % MOD) %= MOD;
                (f[ps][1] += f[ps][0]) %= MOD;
            }
        }
        for (int i = 1; i <= sz(va); ++i) (f[0][0] += f[i][1]) %= MOD;
    } else {
        f[0][0] = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] == 0) (f[0][0] += f[0][1]) %= MOD;
            else if (a[i] == a[n]) (f[0][1] += f[0][0]) %= MOD;
        }
    }
    cout << f[0][0] << "\n";
    return 0;
}

Measured memory_bytes: 26864
S = input()
N = len(S)

dic = {}
for i, s in enumerate(S):
    if not s in dic.keys():
        dic[s] = [i]
    else:
        dic[s].append(i)

all = True
for i in range(N-1):
    if S[i] != S[i+1]:
        all = False


ans = N

for m in dic.keys():
    if all:
        ans = 0
        break
    q = list(S)
    c = 0
    allm = False
    while not allm:
        n = len(q)
        qq = []
        allm = True
        for i in range(n-1):
            if q[i] == m or q[i+1] == m:
                qq.append(m)
            else:
                allm = False
                qq.append(q[i])
        c += 1
        q = qq
    ans = min(ans, c)

print(ans)


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

int times;
vector<vector<int> > lists;
vector<int> stampA;
vector<int> stampB;

void dfs(int point){
    times++;
    stampA.at(point-1)=times;
    for(int i=0;i<(int)lists.at(point-1).size();i++){
        if(stampA.at(lists.at(point-1).at(i)-1)==0) dfs(lists.at(point-1).at(i));
    }
    times++;
    stampB.at(point-1)=times;
    
}

int main(){
    times=0;
    int n;
    cin >> n;
    lists.resize(n,vector<int>());
    stampA.resize(n,0);
    stampB.resize(n,0);
    for(int i=0;i<n;i++){
        int u,k;
        cin >> u >> k;
        for(int j=0;j<k;j++){
            int v;
            cin >> v;
            lists.at(u-1).push_back(v);
        }
    }
    
    for(int i=0;i<n;i++){
        if(stampA.at(i)==0) dfs(i+1);
    }
    
    for(int i=0;i<n;i++){
        cout << i+1 << " " << stampA.at(i) << " " << stampB.at(i) << endl;
    }
}


Measured memory_bytes: 3156
H,W = map(int,input().split())
s=[input() for _ in range(H)]

ok = True
def check(i,j,H,W,s):
    flag = False
    if (i+1) <= (H-1):
        if s[i+1][j] == "#":
            flag = True
    if (i-1) >= 0:
        if s[i-1][j] == "#":
            flag = True
    if (j+1) <= (W-1):
        if s[i][j+1] == "#":
            flag = True
    if (j-1) >= 0:
        if s[i][j-1] == "#":
            flag = True
    return flag

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            ch = check(i,j,H,W,s)
            if not ch:
                ok = False
                break
    if not ok:
        break



if ok:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,m;

int main(){
  ll ans=0;
  cin >> n >> m;
  string s;cin>>s;

  //反対向きに考える
  vi dp(n+1,-1);
  dp[0]=0;
  int nowi=0;
  ll te=0;

  for(int j=0;j<n+1;j++){
    int flag=0;
    REP(i,m){
      int nexti=min((int)n,nowi+(int)(m-i));
      if (s[n-nexti]=='1')continue;
      dp[nexti]=te*100001LL*0+(ll)(nexti-nowi);
      te++;
      nowi=nexti;
      flag=1;
      break;
    }
    if (flag==0){cout<<-1<<endl;return 0;}
    if (nowi==n)break;
  }


  
  REP(i,te)
  {
    cout<<dp[nowi]<<" ";
    nowi-=dp[nowi];
  }
  cout<<endl;
/*
  REP(i,n+1){
    cout<<dp[i]<<" "<<endl;
  }
  */
  return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>

int main() {
  int x, y;
  while (1) {
    scanf("%d %d", &x, &y);
    if (x == 0 && y == 0) {
      break;
    }
    if (x < y) {
      printf("%d %d\n", x, y);
    } else {
      printf("%d %d\n", y, x);
    }
  }
  return 0;
}



Measured memory_bytes: 2032
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

MOD = 10**9+7

N = int(input())
S = []
for _ in range(2):
    s = input()
    S.append(s)

i = 0
if S[0][i] == S[1][i]:
    ans = 3
    i += 1
else:
    ans = 6
    i += 2

while i < N:
    if S[0][i] == S[1][i]:
        if S[0][i-1] == S[1][i-1]: ans *= 2
        else: ans *= 1
        ans %= MOD
        i += 1
    else:
        if S[0][i-1] == S[1][i-1]: ans *= 2
        else: ans *= 3
        ans %= MOD
        i += 2

print(ans)        

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

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

const int N = 30001;
int used[N];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a;
    int cur = 1;
    ll s = 0;
    for (int i = 1; i < n; ++i) {
        while (cur % 2 && cur % 3) {
            ++cur;
        }
        a.push_back(cur);
        used[cur] = 1;
        s += cur;
        ++cur;
    }
    for (int i = 4; i < N; ++i) {
        if (used[i] || gcd(s, i) == 1 || (s + i) % 2 || (s + i) % 3) {
            continue;
        }
        cur = i;
        break;
    }
    for (int i : a) {
        cout << i << ' ';
    }
    cout << cur;
    return 0;
}

Measured memory_bytes: 640
#!/usr/bin/env python3
# input
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
m, n = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x.sort()
y.sort()
fx = [0]
fy = [0]
mod = 10 ** 9 + 7
x_sum = 0
y_sum = 0
for i in range(m - 2, -1, -1):
    fx.append((fx[-1] + (x[i + 1] - x[i]) * (m - 1 - i)) % mod)
    x_sum += fx[-1]
    x_sum %= mod
for i in range(n - 2, -1, -1):
    fy.append((fy[-1] + (y[i + 1] - y[i]) * (n - 1 - i)) % mod)
    y_sum += fy[-1]

    y_sum %= mod
print(x_sum * y_sum % mod)


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

vector<int> l;

int binary_search(vector<int> &a, int left, int right, int key) { // a[i]<keyを満たすiの個数
    int ok = left - 1; // 常にtrue
    int ng = right + 1; // 常にfalse
    while (ok + 1 < ng) {
        int mid = (ok + ng) / 2;
        if (a[mid] < key) ok = mid;
        else ng = mid;
    }
    return ok - left + 1;
}

int main() {
    int n;
    cin >> n;
    l.resize(n);
    rep(i, n) {
        cin >> l[i];
    }
    sort(l.begin(), l.end());
    long sum = 0;
    for (int i = 0; i < n-2; i++) {
        for (int j = i+1; j < n-1; j++) {
            sum += binary_search(l, j+1, n-1, l[i]+l[j]) - binary_search(l, j+1, n-1, l[j]-l[i]+1);
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main(void)
{
	int n;
	int i,h,w;
	int j;
	double best;
	double bmi,sa;
	int a;
	
	scanf("%d",&n);
	best=22.0;
	while(n!=0){
		sa=99999.0;
		for(j=0;j<n;j++){
			scanf("%d %d %d",&i,&h,&w);
			bmi=(double)w/(((double)h/100)*((double)h/100));
			if(best<bmi){
				bmi=bmi-best;
			}
			else {
				bmi=best-bmi;
			}
//			printf("%lf\n",bmi);
			if(sa>bmi){
				a=i;
				sa=bmi;
			}
			else if(sa==bmi && a>i){
				a=i;
			}	
		}
		printf("%d\n",a);
		scanf("%d",&n);

	}
	return 0;
}

Measured memory_bytes: 1028
IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  indata PIC X(100).
       PROCEDURE DIVISION.
        ACCEPT indata.
        
         IF indata = "Sunny" THEN
           DISPLAY "Cloudy"
         END-IF
         IF indata = "Cloudy" THEN
           DISPLAY "Rainy"
         END-IF
         IF indata = "Rainy" THEN
           DISPLAY "Sunny"
         END-IF


       STOP RUN.


Measured memory_bytes: 636
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        String s = sc.next();
        
        if(s.equals("ABC")){
            System.out.println("ARC");
        }else{
            System.out.println("ABC");
        }
    }
}

Measured memory_bytes: 35676
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (ll i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n, k;
  cin >> n >> k;
  vector<pair<ll, ll>> p(n);
  rep(i, n) cin >> p[i].first >> p[i].second;

  vector<ll> vk;
  vk.push_back(k);
  ll tmp = 0;
  FORR(i, 35, 1) {
    if (!(k >> i & 1LL)) continue;
    vk.push_back(tmp + (1LL << i) - 1);
    tmp += (1LL << i);
  }
  ll ans = 0;
  rep(i, vk.size()) {
    ll res = 0;
    rep(j, n) {
      if ((vk[i] | p[j].first) == vk[i]) res += p[j].second;
    }
    chmax(ans, res);
  }
  cout << ans << '\n';


  


  

  
  return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int arrayCnt = new Integer(s.nextLine()).intValue();
		int[] array = new int[arrayCnt];
		String[] tmpArray = s.nextLine().split(" ");
		for(int i=0 ; i<array.length ; i++) {
			array[i] = new Integer(tmpArray[i]).intValue();
		}
		String result = partition(array);
		System.out.println(result);
	}

	public static String partition(int[] array) {
		int index = 0;
		for(int i=0 ; i<array.length-1 ; i++) {
			if(array[i] <= array[array.length-1]) {
				int tmp = array[index];
				array[index] = array[i];
				array[i] = tmp;
				index++;
			}else {

			}
		}
		int tmp = array[index];
		array[index] = array[array.length - 1];
		array[array.length - 1] = tmp;
		StringBuilder b = new StringBuilder();
		for(int i=0 ; i<array.length ; i++) {
			if(index == i)
				b.append("[").append(array[i]).append("] ");
			else
				b.append(array[i]).append(" ");
		}
		return b.toString().trim();
	}
}

Measured memory_bytes: 42928
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int A, B;

  cin >> A >> B;

  cout << (A - 1) * (B - 1);
}

Measured memory_bytes: 3568
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include  <vector>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 100001;
int mod = 1e9 + 7;
typedef long long ll;

int rec[N];
int r9[6] = {1,9,81,729,6561,59049};
int r6[7] = {1,6,36,216,1296,7776,46656};
int main()  
{
  //  freopen("in.txt", "r", stdin); 
    int n;
    while (~scanf("%d", &n))
    {
      memset(rec, -1, sizeof(rec));
      rec[1] = 1;
      rec[0] = 0;
      for (int i = 2; i <= n; i++)
      {
        int tmp = rec[i-1] + 1;
        if (i >= 9)
        {
            for (int j = 0; j < 6; j++)
                if (i >= r9[j] && rec[i-r9[j]] != -1)
                    tmp = min(tmp, 1 + rec[i-r9[j]]);
        }

        if (i >= 6)
        {
            for (int j = 0; j < 7; j++)
            {
                if (i >= r6[j] && rec[i-r6[j]] != -1)
                    tmp = min(tmp, 1 + rec[i-r6[j]]);
            }
        }

        if (i >= 1)
            tmp = min(tmp, i);
        rec[i] = tmp;
      }
      printf("%d\n", rec[n]);
    }
    return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}





void _main() {
        int n; cin >> n;
        vector<int> a(n), b(n), c(n); cin >> a >> b >> c;
        sort(all(a));
        sort(all(b));
        sort(all(c));

        ll ans = 0;
        for (int j = 0; j < n; j++) {
                auto i = lower_bound(all(a), b[j]) - a.begin() - 1;
                auto k = upper_bound(all(c), b[j]) - c.begin();
                ans += (i + 1) * (n - k);
        }

        cout << ans;
}




signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


Measured memory_bytes: 4520
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int a;
int solve(int p,int q,int n,int seki,int l){
  if(p==0) return 1;
  if(n<=0 || p<0) return 0;
  int ret = 0;
  for(int i=l;seki*i<=a;++i){
    int bunsi = p*i-q;
    int bunbo = q*i;
    ret+=solve(bunsi,bunbo,n-1,seki*i,i);
  }
  return ret;
}
 
int main(){
  int p,q,n;
  while(cin>>p>>q>>a>>n,p){
    //memset(memo,0,sizeof(memo));
    cout << solve(p,q,n,1,1) << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;


int main(void) {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) {
    cin >> a[i];
  }

  int count4 = 0;
  int count2 = 0;
  rep(i, n) {
    if (a[i] % 4 == 0) {
      count4++;
    } else if (a[i] % 2 == 0) {
      count2++;
    }
  }
  int countNot = n - count4 - count2;
  countNot += count2 == 0? 0 : 1;

  if (count4 + 1 >= countNot) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3952
/*等价于求比s/2大的最小的数
为什么呢？我们假定有一个值x<s/2
那么它一定会对应一组s-x>s/2(原来选的都不选，原来不选的都选)
然后全部都选没有对应的，所以求的就是比s/2大的最小的那个
然后就变成了一个背包问题*/ 
#include<bits/stdc++.h>
#define N 4000005
using namespace std;
bitset<N>v;
int n,a[N],m;
int main()
{
	scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	v[0]=1; for (int i=1;i<=n;i++) m+=a[i],v|=v<<a[i];
	for (int i=m/2;i>=0;i--)
		if (v[i]){printf("%d\n",m-i);return 0;}
	return 0;
}

Measured memory_bytes: 1664
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
map<long long, int> zip;
vector<long long> unzip;
template <typename T> void compress(vector<T>& v) {
  for (int i = 0; i < (int) v.size(); i++) unzip.push_back(v[i]);
  sort(unzip.begin(), unzip.end());
  unzip.erase(unique(unzip.begin(), unzip.end()), unzip.end());
  for (int i = 0; i < (int) unzip.size(); i++) zip[unzip[i]] = i + 1;
}
template<typename T>
class Fenwick {
private:
  int n;
  vector<T> bit;
public:
  Fenwick() : n(-1) {}
  Fenwick(int n_, T d = T()) : n(n_), bit(n + 1, d) {}

  inline void add(int i, T val) {
    if (i == 0) return;
    for (int x = i; x <= n; x += (x & -x)) bit[x] += val;
  }

  // [1, i);
  inline T get(int i) {
    T res = T();
    for (int x = i; x > 0; x -= (x & - x)) res += bit[x];
    return res;
  }

  // return [i, j);
  inline T get(int i, int j) {
    return get(j - 1) - get(i - 1);
  }

  inline int lower_bound(int val) {
    if (val <= 0) return 0;
    int x = 0, r = 1;
    while (r < n) r <<= 1;
    for (int k = r; k > 0; k >>= 1) {
      if (x + k <= n && bit[x + k] < val) {
        val -= bit[x + k];
        val += k;
      }
    }
    return x + 1;
  }

  const T& operator[](const int &i) const {
    return bit[i];
  }
};
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector <long long> sum(n + 1);
  for (int i = 0; i < n; i++) {
    sum[i + 1] = sum[i] + a[i] - k;
  }
  compress(sum);
  Fenwick<int> bit(n + 100);
  long long ans = 0;
  for (int i = 0; i <= n; i++) {
    ans += bit.get(zip[sum[i]]);
    bit.add(zip[sum[i]], 1);
  }
  cout << ans << '\n';
  return 0;
}

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

int main()
{
  int k,n,ma=0;
  cin >> k >>n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  rep(i,n-1){
    ma =max(a[i+1]-a[i],ma);
  }
  ma=max(ma,a[0]+(k-a[n-1]));
  cout << k-ma << endl;
}

Measured memory_bytes: 1024
mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys

sys.setrecursionlimit(10**4)

N=int(input())
edge=[[] for i in range(N)]
parent=[0]*N
deg=[1]*N
deg[0]=0
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


def prv(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            parent[nv]=v
            prv(nv,v)

prv(0,-1)

for i in range(N):
    new=[]
    for v in edge[i]:
        if v!=parent[i]:
            new.append(v)
    edge[i]=new


from collections import deque
ans = list(v for v in range(N) if deg[v]==0)
deq = deque(ans)
used = [0]*N

while deq:
    v = deq.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)


dp=[[] for i in range(N)]
sz=[0 for i in range(N)]

for v in ans[::-1]:
    sz[v]=1
    dp[v]=[0]*(sz[v]+1)
    dp[v][1]=1
    for nv in edge[v]:
        merged=[0]*(sz[v]+sz[nv]+1)
        for i in range(sz[v]+1):
            for j in range(sz[nv]+1):
                merged[i+j]=(merged[i+j]+dp[v][i]*dp[nv][j])%mod
        sz[v]+=sz[nv]
        dp[v] =merged
    for k in range(1,sz[v]+1):
        dp[v][0]=(dp[v][0]-(g1[k]*g2[k//2])%mod*((k+1)%2)*dp[v][k])%mod

print((-dp[0][0]*pow(inverse[2],N//2,mod))%mod)

Measured memory_bytes: 143284
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int maxn=2e5+5;
char a[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll x;
	cin>>x;
    ll ans=0;
    ans+=(x/500)*1000;
    x%=500;
    ans+=x/5*5;
    cout<<ans<<'\n';



}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod =1e9+7;

int main()
{
    string s;
    cin>>s;
    string t;
    cin>>t;
    int sn=s.length();
    int tn=t.length();
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    bool flag=true;

    if(sn<tn)
    {
        cout<<"UNRESTORABLE";
        return 0;
    }
    rep(i,sn-tn+1)
    {
        flag=true;
        rep(j,tn)
        {
            if(s[i+j]!='?' && s[i+j]!=t[j])flag=false;
        }
        if(flag)
        {
            rep(j,tn)
            {
                s[i+j]=t[j];
            }
            break;
        }
    }
    if(flag)
    {
        rep(i,sn)
        {
            if(s[i]=='?')s[i]='a';
        }
        reverse(s.begin(),s.end());
        cout<<s;
    }
    else
    {
        cout<<"UNRESTORABLE";
    }
    
    

}

Measured memory_bytes: 256
n, q = map(int, input().split())
s = list(input())
tmp = [0] * n
ans = []
for i in range(1, n):
    if s[i - 1] == "A" and s[i] == "C":
        tmp[i] += tmp[i - 1] + 1
    else:
        tmp[i] = tmp[i - 1]
for i in range(q):
    l, r = map(int, input().split())
    ans.append(tmp[r - 1] - tmp[l - 1])

for i in range(len(ans)):
    print(ans[i])


Measured memory_bytes: 62328
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int A = 1e6+5;
int a[A], c[A]; 
int main() {
	int n;
	cin >> n;
	
	rep(i,n) {
		cin >> a[i];
		c[a[i]]++;
	}

	int g = 0;
	rep(i,n) g = __gcd(g, a[i]);

	if (g > 1) {
		cout << "not coprime" << endl;
		return 0;
	}
	
	for (int i = 2; i < A; i++)
	{
		int cnt = 0;
		if (c[i] == -1) continue;
		for (int j = i; j < A; j += i) cnt += c[j];
		
		if (cnt > 1) {
			cout << "setwise coprime" << endl;
			return 0;
		}
	}
	cout << "pairwise coprime" << endl;
	return 0;
}


Measured memory_bytes: 11376
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
 
using namespace std;

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

	if(B/A<C){
		cout << B/A << endl;
	}
	else{
		cout << C << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
   int x;
   cin>>x;
   if(x%7==1){
       cout<<"fri"<<endl;
   }
   else if(x%7==2){
       cout<<"sat"<<endl;
   }
   else if(x%7==3){
       cout<<"sun"<<endl;
   }
   else if(x%7==4){
       cout<<"mon"<<endl;
   }
   else if(x%7==5){
       cout<<"tue"<<endl;
   }
    else if(x%7==6){
        cout<<"wed"<<endl;
    }
    else if(x%7==0){
        cout<<"thu"<<endl;
    }
}


Measured memory_bytes: 3116
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map> 
#define INF 0x3f3f3f3f
#define int __int128
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn=2e5+6;
const int mod=1e9+7;
const double pi=acos(-1.0);
const int cnt=1e18;
int n,m;
int a[maxn];
int read(){        
    int s = 0, f = 1;        
    char ch = getchar();        
    while(!isdigit(ch)) {        
        if(ch == '-') f = -1;        
        ch = getchar();        
    }        
    while(isdigit(ch)) {        
        s = s * 10 + ch - '0';        
        ch = getchar();        
    }        
    return s * f;        
}  
void write(int x){        
    if(x < 0) {        
        putchar('-');        
        x = -x;        
    }        
    if(x > 9)        
        write(x/10);        
    putchar(x % 10 + '0');        
    return;        
}         
signed main(){
	n=read();
	int ans=1;
	int flag=1;
	for(int i=1;i<=n;i++)
		a[i]=read();
    for(int i=1;i<=n;i++){
    	if(a[i]==0){
    		printf("0\n");
    		return 0;
		}
	}
	for(int i=1;i<=n;i++){
    	ans*=a[i];
    	if(ans>cnt){
    		flag=0;
    		break;
		}
	}
	if(flag==0)  cout<<"-1"<<endl;
	else write(ans);
	return 0; 
}

Measured memory_bytes: 5196
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    int sum=0;
    for(int i=0;i<k;i++)
    {
        sum+=arr[i];
    }
    cout<<sum;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
long long n,a,b;
int main()
{
	cin>>n>>a>>b;
	n=abs(n);
	int k=n/b;
	if(a<=n/b)
	{
		cout<<n-b*a<<endl;
		return 0;
	}
	if((n-b*k)>(b*(k+1)-n))
		k++;
	else if((n-b*k)==(b*(k+1)-n))
	{
		cout<<abs(n-b*k)<<endl;
		return 0;
	}
	if((a-k)%2==0)
	{
		cout<<abs(n-b*k)<<endl;
		return 0;
	}
	if((n-b*k)<0)
	{
		cout<<n-b*(k-1)<<endl;
		return 0;
	}
	cout<<abs(n-b*(k+1))<<endl;
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <stdio.h>
#include <math.h>

#define EPS 1e-3
#define INF (1<<29)
#define equals(a, b) (fabs(a - b) < EPS)

struct Country {
    int f, a, x, y, i;
    Country(){}
    Country(int f, int a, int x, int y, int i) :
        f(f), a(a), x(x), y(y), i(i) {}
};

double get_distance(double x1, double y1, double x2, double y2)
{
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main()
{
    int N, f, a, t, x, y;    
    std::cin >> N;
    std::vector<Country> country[2];
    for (int i = 0; i < N; i++) {
        std::cin >> f >> a >> t >> x >> y;
        country[t].push_back(Country(f, a, x, y, i));
    }
    
    double max_dist[2], min_time[2];
    for (int i = 0; i < 2; i++) {
        size_t size = country[i].size();
        max_dist[i] = -1;
        min_time[i] = INF;
        if (size > 1) {         
            for (size_t j = 0; j < size-1; j++) {            
                Country c1 = country[i][j], c2 = country[i][j+1];
                if (c1.a == c2.a || c2.i - c1.i != 1) {
                    continue;
                }                
                double ndist = get_distance(c1.x, c1.y, c2.x, c2.y);
                double ntime = (c2.f - c1.f) / 60.0;
                if (ndist > max_dist[i]) {
                    max_dist[i] = ndist;                    
                    min_time[i] = ntime;
                } else if (equals(ndist, max_dist[i])) {
                    if (ntime < min_time[i]) {
                        min_time[i] = ntime;
                    }
                }
            }
        }
        if (max_dist[i] == -1) {
            std::cout << -1 << " " << -1 << std::endl;
        } else {
            printf("%.10f %.10f\n", max_dist[i], min_time[i]);
        }
    }
    return 0;
}

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

using namespace std;

typedef long long ll;

ll MOD = 1000000007;

int main(int, char**) {
	int n; cin >> n;
	vector<int> value;
	
	for (int i=0; i<n; i++) {
		int v; cin >> v;
		value.push_back(v);
	}
	
	sort(value.begin(), value.end(), greater<int>());

	double ans = 0;
	double c = 1;
	for (int i=0; i<n; i++) {
		if (i != n-1) c *= 0.5;
		ans += value[i] * c;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long x = sc.nextInt();
		int[][] arr = new int[n][n];
		long[] totals = new long[n];
		for (int i = 0; i < n; i++) {
		    arr[0][i] = sc.nextInt();
		    totals[0] += arr[0][i];
		}
		for (int i = 1; i < n; i++) {
		    for (int j = 0; j < n; j++) {
		        arr[i][j] = Math.min(arr[i - 1][j], arr[i - 1][(j - 1 + n) % n]);
		        totals[i] += arr[i][j];
		    }
		    totals[i] += x * i;
		}
		Arrays.sort(totals);
		System.out.println(totals[0]);
   }
}




Measured memory_bytes: 52880
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>

using namespace std;
using ll=long long int;

int main() {
    string s, t;
    cin >> s >> t;
    vector<int> a[26];
    for (int i = 0; i < s.size(); ++i) {
        int idx = s[i] - 'a';
        a[idx].push_back(i);
    }
    ll i = 0;
    ll rep = 0;
    for (auto c: t) {
        int ci = c - 'a';
        if (a[ci].empty()) {
            cout << -1 << endl;
            return 0;
        }
        auto it = lower_bound(a[ci].begin(), a[ci].end(), i);
        if (it == a[ci].end()) {
            ++rep;
            it = a[ci].begin();
        }
        i = *it + 1;
        if (i == s.size()) {
            ++rep;
            i = 0;
        }
    }

    ll ans = rep * s.size() + i;
    cout << ans << endl;

    return 0;
}


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

int main(){
  int64_t MOD = 1000000007;
  int64_t N;
  cin >> N;
  int64_t ans = 1;
  rep(i, N){
    ans *= i;
    ans %= MOD;
  }
  
  cout << ans << endl;
  
}

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

int main() {
    ll n;
    cin >> n;
    vector<ll> even, odd;
    for(ll i = 0; i < n; i++){
        ll a;
        cin >> a;
        if(i%2==0)
            even.emplace_back(a);
        else
            odd.emplace_back(a);
    }
    sort(even.begin(), even.end());
    sort(odd.begin(), odd.end());
    even.emplace_back(-1); odd.emplace_back(-1);
    ll ce = 1, co = 1;
    vector<pair<ll, ll>> check1, check2;
    for(ll i = 0; i < even.size()-1; i++){
        if(even[i]!=even[i+1]){
            check1.emplace_back(ce, even[i]);
            ce = 0;
        }
        if(odd[i]!=odd[i+1]){
            check2.emplace_back(co, odd[i]);
            co = 0;
        }
        ce++; co++;
    }
    //cout << check1.size() << " " << check2.size() << endl;
    sort(check1.begin(), check1.end());
    sort(check2.begin(), check2.end());
    /*for(ll i = 0; i < check1.size(); i++)
        cout << check1[i].first << " " << check1[i].second << endl;
    for(ll i = 0; i < check2.size(); i++)
        cout << check2[i].first << " " << check2[i].second << endl;*/
    if(check1.size()==1 && check2.size()==1 && check1[0].second == check2[0].second)
        cout << n/2 << endl;
    else{
        ll MIN = -1;
        for(ll i = check2.size()-1; i >= 0; i--){
            if(check1[check1.size()-1].second!=check2[i].second){
                MIN = n - check1[check1.size()-1].first - check2[i].first;
                //cout << check1[check1.size()-1].first << " " << check2[i].first << endl;
                break;
            }
        }
        for(ll i = check1.size()-1; i >= 0; i--){
            if(check2[check2.size()-1].second!=check1[i].second){
                MIN = min(MIN, n - check2[check2.size()-1].first - check1[i].first);
                break;
            }
        }
        cout << MIN << endl;
    }
    return 0;
}


Measured memory_bytes: 3440
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())

    def isOK(mid):
        if N <= (mid * (mid + 1)) // 2:
            return True
        else:
            return False

    ok = 10 ** 7
    ng = 0

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    while N > 0:
        if N >= ok:
            print(ok)
            N -= ok
            ok -= 1
        else:
            ok -= 1


if __name__ == '__main__':
    main()


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

int main() {

	int n;
	cin >> n;
	vector<int> nums(n);

	int start = 1, ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
		if (nums[i] == start) 
			++start;
		else 
			++ans;

	}

	cout << (ans == n ? -1 : ans);
}

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

int main()
{
	int n;
	cin>>n;
	if(n>=400&&n<=599)
		cout<<8<<endl;
	if(n>=600&&n<=799)
		cout<<7<<endl;
	if(n>=800&&n<=999)
		cout<<6<<endl;
	if(n>=1000&&n<=1199)
		cout<<5<<endl;
	if(n>=1200&&n<=1399)
		cout<<4<<endl;
	if(n>=1400&&n<=1599)
		cout<<3<<endl;
	if(n>=1600&&n<=1799)
		cout<<2<<endl;
	if(n>=1800&&n<=1999)
		cout<<1<<endl;
	return 0;
}

Measured memory_bytes: 3632
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

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

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n1,n2,n3,n4;cin>>n1>>n2>>n3>>n4;
    map<int,int>m;
    m[n1]++;m[n2]++;m[n3]++;m[n4]++;
    if(m[1]==1&&m[9]==1&&m[7]==1&&m[4]==1)
        cout<<"YES"<<Endl;
    else cout<<"NO"<<Endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------









Measured memory_bytes: 256
n = int(input())
llist = list(map(int, input().split()))

llist.sort()
res = 0
for i in range(n-2):
    prev = n-1
    for j in range(n-2,i,-1):
        for k in range(prev, j, -1):
            if llist[k] < llist[i] + llist[j]:
                res += k - j
                prev = k
                break            
print(res)

Measured memory_bytes: 3188
d=int(input())
c=list(map(int,input().split())) #scoreを減らす
s=[] #scoreを増やす
for i in range(d):
    t=list(map(int,input().split()))
    s.append(t)
last=[0]*26 #それぞれのコンテストが最後に行われたのは何日目か
for i in range(1,d+1): #365日、1日目ならi=1
    temp_best=-100000000
    for j in range(26): #それぞれの日において、26個のコンテストを順番にピックアップ
        temp=s[i-1][j]
        for k in range(26): #ピックアップされていないコンテストは、スコアを減らす
            if j!=k:
                temp-=(c[k]*(i-last[k]))
        if temp>temp_best:
            temp_best=temp
            rem=j
    print(rem+1)
    last[rem]=i

Measured memory_bytes: 9296
N = int(input())
S = str(input())
count = S.count('R')*S.count('G')*S.count('B')
for i in range(N):
  for l in range(N):
    j = i + l
    k = j + l
    if k >= N:
      break
    if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
      count -= 1

print(count)

Measured memory_bytes: 73492
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#include<vector>

int main(){
	int n,m;
	cin >> n >> m;
	int c[n],s,ct;
	bool f=true;
	if(n==1){
		c[0]=0;
		rep(i,m){
			cin >> s >> ct;
			if(c[0]==0||c[0]==ct)c[0]=ct;
			else f=false;
		}
	}
	// n=2,3
	else{
		c[0]=1;
		rep(i,n-1)c[i+1]=0;
		rep(i,m){
			cin >> s >> ct;
			if(s==1){
				if(ct==0)f=false;
				else if(c[0]==1||c[0]==ct)c[0]=ct;
				else f=false;
			}
			//s=2,3
			else{
				if(c[s-1]==0||c[s-1]==ct)c[s-1]=ct;
				else f=false;
			}
		}
	}
	if(f)rep(i,n)cout << c[i];
	else cout << -1;

	return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <cmath>
#include <vector>
#include <string>
#include <iostream>

int Hash(const std::string& Text)
{
    int Hash = 0;
    for(std::size_t i = 0; i < Text.size(); ++i){
        if(i){
            Hash *= 5;
        }
        switch(Text[i]){
        case 'A':
            Hash += 1; break;
        case 'C':
            Hash += 2; break;
        case 'G':
            Hash += 3; break;
        case 'T':
            Hash += 4; break;
        default:
            assert(false);
        }
    }
    return Hash;
}
int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::vector<bool> dic(std::pow(5,12), false);
    int n;
    std::cin >> n;
    std::string command, str;
    for(int i = 0; i < n; ++i){
        std::cin >> command >> str;
        if(command[0] == 'i'){
            dic[Hash(str)] = true;
        }else
        if(command[0] == 'f'){
            std::cout << (dic[Hash(str)] ? "yes" : "no") << std::endl;
        }
    }
    return 0;
 }

Measured memory_bytes: 31008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const long long INF = 1LL << 60;
const int MOD = 1000000007;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    ll N = a.size();
    vector<ll> b(n);

    if(true){
      b[N / 2] = a[0];
      ll idx = 0;
      for (int i = N - 1; i > 0; i -= 2) {
        b[idx] = a[i];
        idx++;
      }
      idx = N / 2 + 1;
      ll j = 0;
      if (N % 2 == 1)
        j = 1;
      else j = 2;
      for (; j < N; j += 2) {
        b[idx] = a[j];
        idx++;
      }
    }
    for (int i = 0; i < N; i++){
      cout << b[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 6320
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in))) {

			String in = br.readLine();
			String[] day = {"SAT","FRI","THU","WED","TUE","MON","SUN"};
			for(int i = 0; i < day.length; i++) {
				if(in.equals(day[i])) {
					System.out.println(i+1);
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 25388
while True:
    h, w = map(int, raw_input().split())
    if (h == 0) & (w == 0):
        break
    line0 = ""
    line1 = ""
    for i in range(w):
        if i == 0 or i == w - 1:
            line0 += "#"
        else:
            line0 += "."
        line1 += "#"
    for j in range(h):
        if j == 0 or j == h - 1:
            print line1
        else:
            print line0
    print ""

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

int main() {
    int N;
    cin >> N;
    set<int> s;
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        s.insert(a);
    }

    cout << s.size() << endl;

    return 0;
}

Measured memory_bytes: 256