akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<queue>
using namespace std;

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

int main(){
    int t, n;
    while(cin >> t >> n, t+n){
        bool visit[121][121] = {};
        int x, y;
        for(int i = 0; i < n; i++){
            cin >> x >> y;
            visit[x+60][y+60] = true;
        }
        cin >> x >> y;
        queue<pair<pair<int,int>, int>> s;
        s.push({{x,y},0});
        int cnt = 0;
        while(!s.empty()){
            pair<pair<int,int>,int> p = s.front(); s.pop();
            if(p.second > t)    break;
            x = p.first.first, y = p.first.second;
            if(visit[x+60][y+60]) continue;
            cnt++;
            visit[x+60][y+60] = true;
            for(int k = 0; k < 6; k++){
                int nx = x + dx[k], ny = y + dy[k];
                if(!visit[nx+60][ny+60]){
                    s.push({{nx,ny},p.second+1});
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vll vector<ll>
#define vi vector<int>
#define vvll vector<vll>
#define wh(t) while(t--)
#define fi(n) for(ll i = 0; i < n; i++)
#define fj(n) for(ll j = 0; j < n; j++)
#define fu(i,s,e) for(ll i = s; i <=e; i++)
#define fd(i,s,e) for(ll i = s; i >=e; i--)
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define fr first
#define se second
#define sll stack<ll>
#define qll queue<ll>
using namespace std;
const ll M = 1e9+7;
//const ll M = 998244353;

ll pmp(ll x,ll n){ll a = 1;while(n > 0){if(n & 1) a = (a * x)%M;x = (x * x)%M;n = n>>1;}return a;}

void solve(){
	ll n;
	cin >> n;
	vll a(1e5+1,0);
	ll sum = 0;
	fi(n){ll x;cin >>x;a[x]++;sum+=x;}
	ll q;
	cin >> q;
	fi(q){
		ll b,c;
		cin >> b >> c;
		ll f = a[b];
		a[c]+=f;
		a[b]=0;
		sum-=f*b;
		sum+=f*c;
		cout << sum << endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif
	ll t;
	t = 1;
	// cin >> t;
	wh(t){
		solve();
	}
	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
	return 0;
}

Measured memory_bytes: 3988
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vl;
typedef vector<int> vi;
#define pb push_back
#define en "\n"
#define forn(i,e) for(ll i=0; i<e; i++)
#define forsn(i,s,e) for(ll i=s; i<e; i++)
#define rforn(i,e) for(ll i=e; i>=0; i--)
#define rforsn(i,s,e) for(ll i=e; i>=s; i--)
#define asort(arr,n) sort(arr,arr+n)
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(),greater<int>())
#define ff first
#define ss second
#define aout(a) for (auto u:a) {cout<<u<<" ";}cout<<en;

 
#define out(x1) cout << x1 << en
#define out2(x1,x2) cout << x1 << " " << x2 << en
#define out3(x1,x2,x3) cout << x1 << " " << x2 << " " << x3 << en

 
#define in(x1) cin >> x1
#define in2(x1,x2) cin >> x1 >> x2
#define in3(x1,x2,x3) cin >> x1 >> x2 >> x3
 
#define arrin(a,n) forn(i,n) cin >> a[i];
#define arrout(a,n) forn(i,n) {cout << a[i] << " ";} cout << en;
 

int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

ios_base::sync_with_stdio(false);
    cin.tie(NULL);

ll n;
in(n);
ll arr[n][3];
for (ll i = 0; i < n; i++)
{
    for (ll j = 0; j < 3; j++)
    {in(arr[i][j]);
        
    }
    
}
ll dp[n][3];
// maximum happiness if last turn is j and only i days are there
for (ll i = 0; i < 3; i++)
{dp[0][i]=arr[0][i];
    
}
for (ll i = 1; i < n; i++)
{
for (ll j = 0; j < 3; j++)
{
    ll sum=0;
    ll mina=0;
    for (ll k = 0; k < 3; k++)
    {if (j!=k){mina=max(mina,dp[i-1][k]);
        // out2(mina,dp[i-1][k]);
    }
    }
    // out3(mina,i,j);
    dp[i][j]=mina+arr[i][j];
    
}
    
}
ll maxa=0;
for (ll i = 0; i < 3; i++)
{maxa=max(maxa,dp[n-1][i]);
    
}
out(maxa);


// for (ll i = 0; i < n; i++)
// {for (ll j = 0; j < 3; j++)
// {cout<<dp[i][j]<<" ";
    
// }cout<<en;
    
// }




    return 0;
}


Measured memory_bytes: 8256
#include<iostream>
using namespace std;
#include<queue>
struct QUE {
	int y;
	int x;
	int count;
	QUE(int a, int b, int c) { y = a, x = b, count = c; }
};

int map[1024][1024];
queue<QUE> q;
int y_move[] = { -1, -1, -1, 0, 0, +1, +1, +1 }, x_move[] = { -1, 0, +1, -1, +1, -1, 0, +1 };
int main() {
	int h, w;
	cin >> h >> w;

	for (int i = 1; i <= h; ++i) {
		for (int i2 = 1; i2 <= w; ++i2) {
			char str;
			cin >> str;
			if (str == '.') { map[i][i2] = 0; q.push(QUE(i, i2, 1)); }
			else map[i][i2] = str - '0';
		}
	}

	int ans;
	while (!q.empty()) {
		int y = q.front().y, x = q.front().x; ans = q.front().count;
		q.pop();
		for (int k = 0; k < 8; ++k) {
			if (map[y + y_move[k]][x + x_move[k]] > 0) {
				map[y + y_move[k]][x + x_move[k]]--;
				if (map[y + y_move[k]][x + x_move[k]] == 0) { q.push(QUE(y + y_move[k], x + x_move[k], ans + 1)); }
			}
		}
	}
	cout << ans-1 << endl;
}

Measured memory_bytes: 7204
// C.

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

using namespace std;

int main(int argc, char* argv[]) {
	int n, a = 0, b = 0, c = 0;
	cin >> n;
	int seq[8] = { 1,2,3,4,5,6,7,8 }, p[8], q[8];
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> q[i];
	}
	do {
		++c;
		int i;
		for (i = 0; i < n; ++i) {
			if (seq[i] != p[i]) {
				break;
			}
		}
		if (i >= n) {
			a = c;
		}
		for (i = 0; i < n; ++i) {
			if (seq[i] != q[i]) {
				break;
			}
		}
		if (i >= n) {
			b = c;
		}
	} while (next_permutation(seq, seq + n));
	cout << abs(b - a) << endl;
	return 0;
}


Measured memory_bytes: 256
def myAnswer(S:list) -> int:
   ans = 0
   for i in range(len(S)):
      S.pop() # 末尾消去
      if(len(S) % 2 == 1):
         continue
      middle = len(S) // 2
      if(S[middle:] == S[:middle]):
         ans = len(S)
         break
   return ans





def modelAnswer():
   tmp=1
def main():
   S = list(input())
   print(myAnswer(S[:]))
if __name__ == '__main__':
   main()

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

int h[101010];
int dp[101010];

void chmin(int &x, int y){
    if(x > y)x = y;
}
int abs(int x){
    if(x < 0)return -x;
    return x;
}
int main(void){
    // Your code here!
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
        dp[i] = 1145141919;
    }
    dp[1] = 0;
    for(int i = 1; i <= n; i++){
        chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 1024
<?php
/**
 * ABC130
 * B - Bounding
 */

// $s = trim(fgets(STDIN));
// fscanf(STDIN, "%d %d", $a, $b);
// $n = array_map('intval', explode(' ', trim(fgets(STDIN))));

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

$X = 0;
$count = 1;
for ($i = 0; $i < $n; $i++) {
    $X += $l[$i];
    if ($X > $x) {
        break;
    }
    $count++;
}

echo $count, PHP_EOL;


Measured memory_bytes: 4856
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> P;
int main(){
  int n;
  while(cin>>n,n){
  vector <P> ans;
  while(n--){
    int ID,sum=0,cnt=0,ste[2]={},cnt2=0,pre=0,a,cnt3=0;
    cin>>ID;
    while(cnt<10){
      cin>>a;
      cnt3=!cnt3;
      cnt2++;
      while(ste[cnt3])sum+=a,ste[cnt3]--;
      if(cnt2==1&&a==10) ste[cnt3]++,ste[!cnt3]++,cnt2=2;
      else if(cnt2==2&&a+pre==10) ste[!cnt3]++;
      pre=a;
      if(cnt2==2) cnt++,cnt2=0,pre=0;
      sum+=a;
    }

    if(ste[!cnt3]) cin>>a;
    while(ste[!cnt3]--)sum+=a;
    if(ste[cnt3]) cin>>a;
    while(ste[cnt3]--)sum+=a;
    ans.push_back(P(sum,-ID));
  }

  sort(ans.begin(),ans.end());
  for(int i=(int)ans.size()-1;i>=0;i--) cout << -ans[i].second<<" "<<ans[i].first<<endl;
  }
  return 0;
}

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

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


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


def solve(X: int):
    def is_prime(n):
        for i in range(2, n + 1):
            if i * i > n:
                break
            if n % i == 0:
                return False
        return n != 1


    while True:
        if is_prime(X):
            break
        X += 1
    print(X)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <cstdio>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>

int main()
{
    std::string n;
    std::cin >> n;

    for (int i = 0; i < n.size(); ++i) {
        if (n[i] == '1') {
            std::cout << '9';
        } else {
            std::cout << '1';
        }
    }

    std::cout << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
    int N, K;
    std::cin >> N >> K;

    int result = 1;
    for (int i = 0; i < N; ++i) {
        if (result < K) {
            result *= 2;
        } else {
            result += K;
        }
    }
    std::cout << result << std::endl;
    return 0;
}


Measured memory_bytes: 256
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
L = list(map(int,list(input().strip())))
N = len(L)
A = []
for i in range(N):
    if L[i]==1:
        A.append(i)
cnt = 0
for i in range(len(A)):
    j = A[i]
    k = i
    n = N-1-j
    cnt = (cnt+pow(2,k)*pow(3,n))%p
cnt = (cnt+pow(2,len(A)))%p
print(cnt)

Measured memory_bytes: 89084
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <queue>
#include <sstream>
#include <climits>
#include <cmath>
#include <list>
#include <functional>
#include <map>
#include <stack>
using namespace std;
#define M_PI 3.141592
#define FOR(i,n) for(int i=0;i<(int)n;i++)
#define FORI(i,k,n) for(int i=k;i<(int)n;i++)
#define toRad 2.0*M_PI/360.0
#define inin(x) int x;cin>>x;
#define all(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" :"<<x<<endl;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define EPS 1e-12
#define pri_max 60000
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

/*
bool memo[pri_max] = {};
vector<int> pri;
void calc()
{
	for (int i = 2; i < pri_max; i++)
	{
		if (memo[i] == false)
		{
			pri.push_back(i);
			for (int l = i; l < pri_max; l += i)
			{
				memo[l] = true;
			}
		}
	}
}*/
double len(pdd a, pdd b)
{
	return sqrt((b.first - a.first)*(b.first - a.first) + (b.second - a.second)*(b.second - a.second));
}

int main()
{
	int n;
	while (cin >> n&&n)
	{
		vector<pdd> v;
		int ans = 1;
		for (int i = 0; i < n; i++)
		{
			pdd p;
			scanf("%lf,%lf", &p.first, &p.second);
			v.push_back(p);
		}
		for (int i = 0; i < n; i++)
		{
			for (int l = 0; l < n; l++)
			{
				if (i == l)continue;
				if (!(len(v[i], v[l])>2.0))
				{
					pdd p;
					p.first = v[i].first + cos(atan2(v[l].second - v[i].second, v[l].first - v[i].first));
					p.second = v[i].second + sin(atan2(v[l].second - v[i].second, v[l].first - v[i].first));
					int temp = 0;
					for (int k = 0; k < n; k++)
					{
						if (!(len(v[k], p)>1.0))temp++;
					}
					ans = max(temp, ans);
				}
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1404
// C.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[])
{
	LL n, m;
	cin >> n >> m;
	LL ans = min(n, m / 2);
	ans += (m - ans * 2) / 4;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def PrimeDecomposition(N):
        ret = {}
        n = int(N ** 0.5)
        for d in range(2, n + 1):
            while N % d == 0:
                if d not in ret:
                    ret[d] = 1
                else:
                    ret[d] += 1
                N //= d
            if N == 1:
                break
        if N != 1:
            ret[N] = 1
        return ret

    N = int(input())
    P = PrimeDecomposition(N)
    ans = 0
    for d in P:
        a = P[d]
        for i in range(1, 100):
            if a >= i:
                a -= i
                ans += 1
            else:
                break
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 63400
#include <stdio.h>

int main () {
    
  int h,w;
  while (1) {
    scanf ("%d %d",&h,&w);
    int n,i;
    if (h == 0 && w == 0) break;
    for (i=0;i<h;i++) {
      for (n=0;n<w;n++) {
	printf ("#");
      }
      printf ("\n");
    }
     

    printf ("\n");
  }
  return 0;
}

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

int main() {
  ll n, p;
  cin >> n >> p;
  vector<pair<ll, ll>> res;
  for (ll i = 2; i * i <= p; i++) {
    if (p % i != 0) continue;
    int num = 0;
    while (p % i == 0) {
      p /= i;
      num++;
    }
    res.push_back(make_pair(i, num));
  }
  if (p != 1) res.push_back(make_pair(p, 1));
  ll ans = 1;
  for (auto p : res) rep(i, p.second / n) ans *= p.first;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {
	private Scanner sc;
	
	public static void main(String[] args) {
		new Main();
	}
	
	public Main() {
		sc = new Scanner(System.in);

		while (sc.hasNextLine()) {
			String[] param = sc.nextLine().split(",");
			
			int d = 0;
			int[] ds = new int[10];
			for (int j = 0; j < 10; j++) {
				ds[j] = Integer.parseInt(param[j]);
				d = d + ds[j];
			}

			int l = Integer.parseInt(param[10]);
			int r = Integer.parseInt(param[11]);
			
			double point = (double)d / (r + l) * l;
			
			int j = 0;
			while (point > 0.0) {
				point = point - ds[j];
				j++;
			};
			
			System.out.println(j);
		}
		
	}
}

Measured memory_bytes: 26260
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N,K,Q;
LL A[2001];
typedef pair<LL,int> P;
vector<P>s;
bool used[2001];
int main(){
	cin>>N>>K>>Q;
	REP(i,N){
		cin>>A[i];
		s.push_back(P(A[i],i));
		used[i]=false;
	}
	sort(s.begin(),s.end());
	LL ans=1e18;
	REP(i,N){
		//			cout<<"i回目"<<endl;
		vector<LL>q;
		vector<LL>v;
		REP(j,N){
			if(used[j]==true){
				if(v.size()>=K){
					sort(v.begin(),v.end());
					reverse(v.begin(),v.end());
					for(int k=K-1;k<v.size();k++){
					//	cout<<v.size()<<"pat1 "<<k<<" "<<v[k]<<endl;
						q.push_back(v[k]);
					}
				}
				v.clear();
			}else{
				v.push_back(A[j]);
			}
		}
		if(v.size()>=K){
			sort(v.begin(),v.end());
			reverse(v.begin(),v.end());
			for(int k=K-1;k<v.size();k++){
			//	cout<<v.size()<<"pat2 "<<k<<" "<<v[k]<<endl;
				q.push_back(v[k]);
			}
			v.clear();
		}
		
		
		if(q.size()>=Q){
			//cout<<"Qsize"<<q.size()<<endl;
			sort(q.begin(),q.end());
			ans=min(ans,q[Q-1]-q[0]);
			//cout<<i<<" "<<q[Q-1]<<" "<<q[0]<<endl;
		}
		used[s[i].second]=true;
	}
	cout<<ans<<endl;
	
	return(0);
}

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

int main() {

  // 文字列
  string s,t;
  int cnt = 0;
  cin >> s >> t;
  
  for (int i = 0; i < 3; i++) {
    if (s.at(i) == t.at(i)) cnt++;
  }
  
  cout << cnt;
}


Measured memory_bytes: 384
from collections import defaultdict

def main():
    X, Y, A, B, C = map(int, input().split())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    R = list(map(int, input().split()))
    d_p = defaultdict(int)
    d_q = defaultdict(int)
    d_r = defaultdict(int)
    for p in P:
        d_p[p] += 1
    for q in Q:
        d_q[q] += 1
    for r in R:
        d_r[r] += 1
    D = P + Q + R
    D.sort(reverse=True)
    ans = 0
    x = 0
    y = 0
    c = 0
    for i in range(A + B + C):
        if x + y + c >= X + Y:
            break

        if x < X and d_p[D[i]]:
            ans += D[i]
            x += 1
            d_p[D[i]] -= 1
        elif y < Y and d_q[D[i]]:
            ans += D[i]
            y += 1
            d_q[D[i]] -= 1
        elif d_r[D[i]]:
            ans += D[i]
            c += 1
            d_r[D[i]] -= 1

    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 120872
import sys,bisect
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for e in a:
    for w in b:
        ab.append(e+w)
ab.sort()

ok = -1
ng = 10**12
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    cnt = 0
    for e in c:
        cnt += len(ab)-bisect.bisect_left(ab,mid-e)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

res = []
for e in c:
    ind = bisect.bisect_left(ab,ok-e)
    for i in range(ind,len(ab)):
        res.append(e+ab[i])
res.sort()
for i in range(1,k+1):
    print(res[-i])
        



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

using namespace std;
//typedef long long ll;
//typedef vector<int> VI;

#define FOR(i, a, n) for (long long i = (long long)a; i < (long long)n; ++i)
#define REP(i, n) FOR(i, 0, n)

//グラフの隣接リスト
//VI g[100010];
vector<int> G[100010];
//頂点の入次数を管理
//int h[100010];
int indeg[100010];

signed main()
{
    //頂点数v、辺の数e
    int n, m;
    cin >> n >> m;
    vector<int> revG[n];
    REP(i, n+m-1) {
        int s, t;
        cin >> s >> t;
        s--;t--;
        //頂点sから頂点tへの有向辺
        G[s].push_back(t);
        revG[t].push_back(s);
        indeg[t]++;
    }
    
    //入次数が0の頂点の集合を格納するスタック
    stack<int> st;
    
    //入次数が0の頂点であればstに追加
    REP(i, n) if(indeg[i] == 0) st.push(i);
    
    //ソートされた後のグラフの頂点の列
    vector<int> seq;
    //stがなくなるまでループ
    while(st.size()) {
        //stの集合のから一つ取り出す
        int i = st.top(); st.pop();
        seq.push_back(i);
        for(auto& j: G[i]) {
            //隣接する頂点の入次数をマイナス1
            indeg[j]--;
            //これによって入次数が0になればstに追加
            if(indeg[j] == 0) st.push(j);
        }
    }
    
    vector<int> order(n);//頂点iがseq内で何番目か
    REP(i,n){
      order[seq[i]] = i;
    }
    vector<int> ans(n);
    int temp;
    int par;
    REP(i,n){
      temp = -1;
      for(auto& j:revG[i]){
        if(temp<order[j]){
          temp = order[j];
          par = j;
        }
      }
      if(temp==-1){
        ans[i] = 0;
      }else{
        ans[i] = par+1;
      }
    }
    
    REP(i,n){
      cout<<ans[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 13436
package main

import "fmt"

func pow(n, x int64) int64 {
	if n == 1 {
		return 1
	}
	if x == 0 {
		return 1
	}
	r := n * pow(n, x-1)
	// fmt.Printf("[pow(%d,%d) -> %d\n", n, x, r)
	return r
}
func main() {
	var i, j, X int64
	fmt.Scan(&X)
	var max int64 = 1
	for i = 1; i <= 40; i++ {
		// fmt.Printf("[d01] i %d\n", i)
		for j = 2; j < 1024; j++ {
			s := pow(i, j)
			if s > X {
				break
			}
			if s > max {
				max = s
			}
		}
	}
	fmt.Println(max)
}


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    set<int> s;
    s.insert(a);
    s.insert(b);
    s.insert(c);
    if(s.size()==2) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;


typedef long long i64;
const int inf = (int)1.05e9;


int main()
{
	char s[100004];

	scanf("%s", s);
	int count[3] = {0, 0, 0};

	for(int i = 0; s[i] != '\0'; ++i) {
		int idx = s[i] - 'a';
		count[idx] += 1;
	}

	int maxi = count[0], mini = count[0];
	for(int i = 1; i < 3; ++i) {
		mini = min(mini, count[i]);
		maxi = max(maxi, count[i]);
	}

	bool ok = (maxi - mini <= 1);

	printf("%s\n", ok ? "YES" : "NO");

	return 0;
}

/* waffle */


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

#define debug(x) cout << #x << " = " << x << endl;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;
const ll mod = 998244353;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

ll exp(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}

const int maxn = 2e5 + 10;

int a[maxn];

map<int,int>mapa;

int main()
{
  ios::sync_with_stdio(0);
  ll n;

  cin >> n;
  
  ll ans = 0;
  
  for(int i = 1; i <= n; i++)
  {
    cin >> a[i];
    mapa[i - a[i]]++;
  }


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

  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 21320
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }


int main() {
    ll n; cin >> n;
    vector<ll> avec(n, 0);
    for(int i = 0; i < n; ++i) {
        cin >> avec[i];
    }
    ll now = avec[0];
    ll sum = 0;
    for(int i = 0; i < n; ++i) {
        ll ch = avec[i]-now;
        if(ch >= 0) {
            now = avec[i];
        }else {
            sum += abs(ch);
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 4784
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int count = 0;
    while(true) {
      count++;
      int a = sc.nextInt();
      if(a == 0) {
        break;
      } else {
        System.out.println("Case " + count + ": " + a);
      }
    }
  }
}



Measured memory_bytes: 44860
# -*- coding: utf-8 -*-
"""
C - AB Substrings
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c

"""
import sys


def solve(N, words):
    eA, sB, both = 0, 0, 0
    ans = 0
    for w in words:
        ans += w.count('AB')
        if w[-1] == 'A':
            if w[0] == 'B':
                both += 1
            else:
                eA += 1
        elif w[0] == 'B':
            sB += 1

    if both == 0:
        ans += min(eA, sB)
    elif eA == 0 and sB == 0:
        ans += (both - 1)
    else:
        ans += min(eA, sB) + both
    return ans


def main(args):
    N = int(input())
    words = [input() for _ in range(N)]
    ans = solve(N, words)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3700
n, p = map(int, input().split())
s = list(map(int, list(input())))

u = [ 0 for i in range(n+1)]

d = 1
for i in range(n):
    u[n-(i+1)] = (u[n-i] + s[n-1-i] * d) % p
    d = 10 * d % p

# print(u, d)

def solve(u, s):
    if p == 2 or p == 5:
        return solve1(s)
    else:
        return solve2(u)


def solve1(s):
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    return ans

def solve2(u):
    ans = 0
    cnt = [0 for i in range(p)]
    for i in range(n+1):
        cnt[u[i]] += 1
    for i in range(p):
        q = cnt[i]
        ans += (q * (q-1)) // 2
    return ans

print(solve(u, s))



Measured memory_bytes: 12404
#include<iostream>
#include<vector>
using namespace std;
int main() {

	int N, M, ans = 0;
	cin >> N >> M;
	vector<int> A(M,0);

	for (int i = 0; i < N; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int a;
			cin >> a;
			A[a - 1]++;
		}
	}

	for (int i = 0; i < M; i++) {
		if (A[i] == N)ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int a[3][3];
int n, e;
int b[10];
int main() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", a[i] + j);
		}
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", b + i);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (a[j][k] == b[i])a[j][k] = 0;
			}
		}
	}
	for (int i = 0; i < 3; i++) {
		if (a[i][0] == 0 && a[i][1] == 0 && a[i][2] == 0)e = 1;
		if (a[0][i] == 0 && a[1][i] == 0 && a[2][i] == 0)e = 1;
	}
	if (a[0][0] == 0 && a[1][1] == 0 && a[2][2] == 0)e = 1;
	if (a[0][2] == 0 && a[1][1] == 0 && a[2][0] == 0)e = 1;
	if (e)printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include<iomanip>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60

int H[200009];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) cin >> H[i];

	int ans = 0;
	int cnt = 0;
	int h = H[0];

	for (int nxt = 1; nxt < N; nxt++) {
		if (H[nxt] <= h) {
			cnt++;
			h = H[nxt];
		}
		else {
			ans = max(ans, cnt);
			cnt = 0;
			h = H[nxt];
		}
	}
	ans = max(ans, cnt);
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 640
n = gets.chomp.to_i
llist = gets.chomp.split.collect{ |item| item.to_i}

llist.sort!
ldata = [0]
be = 0
n.times do |ni|
  nowl = llist[ni]
  if be == nowl
    ldata[nowl] += 1
  else
    (be+1).upto(nowl) do |nii|
      ldata[nii] = ldata[be]
    end
    ldata[nowl] += 1
  end
  be = nowl
end

result = 0
a = 0
b = 0
c = 0
0.upto(n-3) do |ai|
  a = llist[ai]
  (ai+1).upto(n-2) do |bi|
    b = llist[bi]
    cmin = b-a
    cmax = a+b
    maxC = ldata[cmax-1] ? ldata[cmax-1] : ldata[-1]
    maxC -= (bi+1)
    result += maxC 
  end
end
puts result


Measured memory_bytes: 1912
#include<algorithm>
#include<iostream>
#include<vector>

typedef long long i64;

using namespace std;

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

    int ans = 0;

    for(int i=0;i<N;i++){
            for(int j=1;;j++){
                if((a[i] % (1<<j)) != 0){
                    ans += (j-1);
                    break;
                }
            }
    }

    cout<<ans<<endl;

}

Measured memory_bytes: 892
#include <iostream>
#include<string>
using namespace std;
int main(){
  int a,b,c,d,e,k;
  cin>>a>>b>>c>>d>>e>>k;
  if(e-a<=k){
      cout<<"Yay!"<<endl;
    
  }
  else {
      cout<<":("<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N;
 
  cin >> N;
 
  vector<int> A(N);
 
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }//入力終了

  if(A.size()==1){
    cout << 1 << endl;
    return 0;
  }//項が一つしかないとき
 
  int cut=0;//分割回数
 
  for(int i=0;i<N-1;){

    if(A.at(i)==A.at(i+1)) {
      i++;
      continue;
    }
 
    else if(A.at(i)>A.at(i+1)){//減少傾向の場合
      while(A.at(i)>=A.at(i+1)){//減少する限り次に進める
        i++;
        if(i==N-1) break;
      }
      cut++;   //分割回数
      i++;     //次の部分列の先頭へ  
 
    }
 
    else {//増加傾向の場合
      while(A.at(i)<=A.at(i+1)){//増加する限り次に進める
        i++;
        if(i==N-1) break;
      }
      cut++;   //分割回数
      i++;     //次の部分列の先頭へ
    }

  if(i==N-1) {
    cut++;
    break;
  }//この時点でi==N-1を満たす場合、増加傾向または減少傾向の場合は最終項だけが仲間外れだった。→ 切り取り+1回
 
 
  }
 
  cout << cut << endl;
 
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int a[SIZE];
int main(){
    DRI(N);
    REP(i,N)RI(a[i]);
    int t=0,an=1;
    REPP(i,1,N){
        if(a[i]>a[i-1]){
            if(t&1){
                an++;
                t=0;
            }
            else t|=2;
        }
        else if(a[i]<a[i-1]){
            if(t&2){
                an++;
                t=0;
            }
            else t|=1;
        }
    }
    cout<<an<<endl;
    return 0;
}


Measured memory_bytes: 764
import sys
import numpy as np
from itertools import product 
input = sys.stdin.readline
N,M,X= map(int,input().split())
CA = [list(map(int,input().split())) for i in range(N)]
C,*A = zip(*CA)
C = np.array(C)
A = np.array(A)

inf = 10**8
ans = inf

l = [1,0]
for c in product(l,repeat=N):
    Y = c * A
    Y = np.sum(Y,axis=1)
    if np.all((Y-X) >= 0):
        ans = min(ans, np.sum(c*C))

if ans == inf:
    print(-1)
else:
    print(ans)










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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;

const ll mod = 1000000007;

class Primes {
private:
	vector<int> Prime_Number;
	vector<bool> is_prime_;
public:
	Primes(int N) {
		is_prime_.resize(N + 1, true);
		is_prime_[0] = is_prime_[1] = false;
		for (int i = 0; i < N + 1; i++) {
			if (is_prime_[i]) {
				Prime_Number.push_back(i);
				for (int j = 2 * i; j <= N; j += i) is_prime_[j] = false;
			}
		}
	}
	int operator[](int i) { return Prime_Number[i]; }
	int size() { return Prime_Number.size(); }
	int back() { return Prime_Number.back(); }
	bool isPrime(int q) { return is_prime_[q]; }
};

int main() {
	ll n;
	cin >> n;
	vector<ll> table(n + 1, 0);
	for (ll i= 1; i <= n; i++) {
		for (ll j = 1; i * j <= n; j++) {
			table[i * j]++;
		}
	}
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += i * table[i];
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 81312
#include<stdio.h>

int main(void) {

	long int number = 0;	scanf("%d", &number);
	long long int date[10001] = {0};

	long long int max = -1000000;
	long long int min = 1000000;
	long long int total = 0;
	
	for (int i = 0; i < number; i++) {

		scanf("%lld", &date[i]);

		if (max < date[i]) {
			max = date[i];
		}
		if (min > date[i]) {
			min = date[i];
		}

		total += date[i];
	}

	printf("%lld %lld %lld\n", min, max, total);

	return 0;
}


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

int main() {
    int N, K;
    cin >> N >> K;
    vector<long long> h(N);
    for (int i = 0; i < N; i++) {
        cin >> h[i];
    }

    const long long INF = 1e16;
    long long dp[N];
    fill(dp, dp + N, INF);
    dp[0] = 0;

    for (int i = 1; i < N; i++) {
        for (int j = i - K; j < i; j++) {
            if (j >= 0) {
                dp[i] = min({dp[i], dp[j] + abs(h[i] - h[j])});
            }
        }
    }

    cout << dp[N - 1] << endl;
}

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

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

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}
 
int n, a, b;
string s;
int are[100];
int main(){
    cin >> s;
    for(int i = 0; i < s.length(); i++){
        are[s[i]-'a']++;
    }
    for(int i = 0; i < 3; i++){
        if(are[i] != 1){
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}

Measured memory_bytes: 256
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int A = sc.nextInt();
        int B = sc.nextInt();
        out.println(Math.max(A * B, Math.max(A + B, A - B)));
        out.close();
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        FastScanner(FileReader s) {
            br = new BufferedReader(s);
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        String nextLine() throws IOException { return br.readLine(); }

        double nextDouble() throws IOException { return Double.parseDouble(next()); }

        int nextInt() throws IOException { return Integer.parseInt(next()); }

        long nextLong() throws IOException { return Long.parseLong(next()); }
    }
}

Measured memory_bytes: 22100
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef long long int Int;
typedef pair<Int, Int> P;
typedef pair<P, Int> PP;


Int H, W, L;
int my[] = {-1, 0, 1, 0};
int mx[] = {0, 1, 0, -1};

void turn(PP &now, vector< vector<bool> > &v){
  Int y = now.first.first, x = now.first.second, d = now.second;
  while(!(y + my[d] >= 0 && x + mx[d] >= 0 && y + my[d] < H && x + mx[d] < W && v[y + my[d]][x + mx[d]] == 0)) d = (d + 1) % 4;
  now.second = d;
}

PP solve(vector< vector<bool> > &G, PP &now, Int &L){
  vector<PP> v;
  map<PP, Int> M;
  Int cnt = 0;
  turn(now, G);
  while(L-- > 0){
    turn(now, G);
    Int &y = now.first.first, &x = now.first.second, &d = now.second;
    y = (y + my[d]); x = (x + mx[d]);
    if(L <= 0) return now;
    else if(M.find(now) != M.end()) break;
    v.push_back(now);
    M[now] = cnt++;
  }
  Int t = L % ((int)v.size() - M[now]);
  return v[t + M[now]];
}


int main() {
  map<char, Int> D;
  D['N'] = 0; D['E'] = 1; D['S'] = 2; D['W'] = 3;
  string RD = "NESW";
  while(cin >>H >>W >>L && (H || W || L)){
    vector< vector<bool> > v(H, vector<bool>(W));
    PP now;
    REP(i, H){
      REP(j, W){
        char c; cin >>c;
        if(c == '.') v[i][j] = 0;
        else if(c == '#') v[i][j] = 1;
        else{
          v[i][j] = 0;
          now.first.second = j; now.first.first = i;
          now.second = D[c];
        }
      }
    }
    PP ans = solve(v, now, L);
    cout <<ans.first.first + 1 <<" " <<ans.first.second + 1 <<" " <<RD[ans.second] <<endl;
  }
  return 0;
}

Measured memory_bytes: 1652
#include <iostream>
#include <algorithm>
#include <string>
#include <functional> 
#include <vector>
#include <numeric>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <cstdlib>

using namespace std;

int main(){


    int n;
    cin >> n;
    vector<pair<int,int>> red(n),blue(n);

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

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

    sort(red.begin(),red.end());
    sort(blue.begin(),blue.end());

    int cnt = 0;

    for(int i=n-1;i>=0;i--){
        int kouho;
        for(int k=0;k<n;k++){
            if(red[i].first < blue[k].second && red[i].second < blue[k].first){
                cnt++;
                blue[k].first = 0;
                blue[k].second = 0;
                break;
            }
        }
    }

    cout << cnt;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

const ll INF = 1LL << 60;

int main(){
  int H,W; cin >> H >> W;
  int c[10][10];
  rep(i, 10) rep(j, 10) cin >> c[i][j];
  int a[H][W];
  rep(i, H) rep(j, W) cin >> a[i][j];

  // わーしゃるふろいど
  rep(k, 10) rep(i, 10) rep(j, 10) chmin(c[i][j],c[i][k]+c[k][j]);

  ll ans = 0;
  rep(i, H) rep(j, W){
    if(a[i][j] == -1) continue;
    ans += c[a[i][j]][1];
  }

  std::cout << ans << '\n';
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin>>n;
  vector<int>city(n);
  rep(i,n)cin>>city[i];
  int l,q;
  cin>>l>>q;
  int nl=n,c=0;
  while(nl>0){c++;nl/=2;}
  vector<vector<int>>db(n,vector<int>(c,n));
  int r=0;
  rep(i,n)
  {
    while(r+1<n&&city[r+1]<=city[i]+l)r++;
    db[i][0]=r;
  }
  rep(i,c-1)
  {
    rep(j,n)
    {
      db[j][i+1]=db[db[j][i]][i];
    }
  }
  auto check=[&](int s,int t,int day){
    rep(i,c)
    {
      if(day&(1<<i))
      {
        s=db[s][i];
      }
    }
    return s>=t;
  };
  rep(i,q)
  {
    int a,b;
    cin>>a>>b;
    a--;b--;
    if(a>b)swap(a,b);
    int ok=n,ng=0;
    while(ok-ng>1)
    {
      int mid=(ok+ng)/2;
      if(check(a,b,mid))ok=mid;
      else ng=mid;
    }
    cout<<ok<<"\n";

  }
  cout<<flush;


  return 0;

}


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



int main()
{
    long long r;
    long long c;
    
    cin>>r>>c;
    
    char x;
    long long a[r][c];
    
    for(long long i=0;i<r;i++)
    {
        for(long long j=0;j<c;j++)
        {
            cin>>x;
            if(x=='.')a[i][j]=0;
            else
            a[i][j]=-1;
        }
    }
    
    a[0][0]=1;
   
   for(long long i=0;i<r;i++)
    {
        for(long long j=0;j<c;j++)
        {
            if(i==0 && j==0)continue;
            if(a[i][j]==-1)continue;
            
            if(i==0&&j>0)
            {
                if(a[i][j-1]==1)a[i][j]=1;
                else
                a[i][j]=0;
                //cout<<"abc";
                continue;
            }
            
            if(j==0&&i>0)
            {
                if(a[i-1][j]==1)a[i][j]=1;
                else
                a[i][j]=0;
                //cout<<"gffcg";
                continue;
            }
            
            
            
            if(a[i-1][j]>=0 && a[i][j-1]>=0)
            {
                a[i][j]=(a[i-1][j]+ a[i][j-1])%1000000007;
            }
            if(a[i-1][j]==-1 && a[i][j-1]>=0)
            {
                a[i][j]= a[i][j-1]%1000000007;
            }
            if(a[i-1][j]>=0 && a[i][j-1]==-1)
            {
                a[i][j]=a[i-1][j]%1000000007;
            }
        }
    }
    // for(long long i=0;i<r;i++)
    // {
    //     for(long long j=0;j<c;j++)
    //     {cout<<a[i][j]<<" ";}
    //     cout<<endl;
    // }
    cout<<a[r-1][c-1];
   
    return 0;
}


Measured memory_bytes: 8064
/**
 *COYG, 14 FA Cups we are back baby
 */
#include <bits/stdc++.h>
using namespace std;
#define mod 		1000000007
#define ll 		long long
#define mp 		make_pair
#define pb 		push_back
#define forn(i,n) 	for(int i=0;i<n;i++)
#define for1(i,n) 	for(int i=1;i<n;i++)
#define ford(i,n) 	for(int i=n-1;i>=0;i--)
#define vi 		vector<int>
#define vl 		vector<ll>
#define pii 		pair<int,int>
#define pll 		pair<ll,ll>
#define vpi 		vector<pair<int,int> >
#define vpl		vector<pair<ll,ll> >
#define vvi 		vector<vector<int> >
#define vvl 		vector<vector<ll> >
#define ull 		unsigned long long
#define IOS 		ios_base::sync_with_stdio(false);
#define PI 		3.1415926535897932384626
#define ff 		first
#define ss 		second
#define char2Int(c) 	(c-'0')
#define FOREACH(i,t) 	for (auto i=t.begin(); i!=t.end(); i++)
#define clr(a,x) 	memset(a,x,sizeof(a)) //set elements of array to some value
#define all(x)		(x).begin(),(x).end()//cout<<"Case #"<<zzz<<": ";
#define plll pair<ll,pll >
ll n;
void add_self(ll&a,ll b)
{
   a+=b;
   if(a>=mod)
   {
       a-=mod;
   }
}
struct mat
{
    vector<vector<ll> > a;
    mat(){
        a.resize(n,vector<ll>(n));
    }
    mat operator*(mat& s)
    {
        mat ret;
        forn(i,n)
        {
            forn(j,n)
            {
                forn(k,n)
                {
                    ll temp=(a[i][j]*s.a[j][k])%mod;
                    add_self(ret.a[i][k],temp);
                }
            }
        }
        return ret;
    }
};
mat power(mat m, ll p)
{
    mat ret;forn(i,n)ret.a[i][i]=1;
    while(p>0)
    {
        if(p%2==1)
        {
            ret=ret*m;
        }
        m=m*m;
        p/=2;
    }
    return ret;
}
void solve()
{
    cin>>n;ll k;cin>>k;
    vector<vector<ll> > adj;
    adj.resize(n,vector<ll>(n));
    forn(i,n)forn(j,n)cin>>adj[i][j];
    mat topass;topass.a=adj;
    mat ans=power(topass,k);
    ll ret=0;
    forn(i,n)
    {
        forn(j,n)
        {
            add_self(ret,ans.a[i][j]);
        }
    }
    cout<<ret<<endl;
}
int main()
{
    IOS;cin.tie(NULL);
    ll zz;zz=1;
    //cin>>zz;
    for(int zzz=1;zzz<=zz;zzz++)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3740
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main()
{
  int N, M;
  cin >> N >> M;
  vector<int> P(M), Y(M);
  REP(i, M)
  cin >> P[i] >> Y[i];
  vector<int> vc[100001];
  REP(i, M)
  vc[P[i]].push_back(Y[i]);
  REP1(i, N)
  sort(ALL(vc[i]));
  REP(i, M)
  printf("%06d%06d\n", P[i], lower_bound(ALL(vc[P[i]]), Y[i]) - vc[P[i]].begin() + 1);
  return 0;
}

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

int main() {
    int N, K;
    int l[50];
    cin >> N >> K;
    for (int i = 0; i < N; ++i) cin >> l[i];

    sort(l, l + N, greater<int>());
    int total = 0;
    for (int i = 0; i < K; ++i) total += l[i];
    
    cout << total << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll INF=1e18;
//const int INF=1001001001;
// Sieve of Eratosthenes
// https://youtu.be/UTVg7wzMWQc?t=2774

map<ll,ll> mp;


struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  void factorMap(int x) {
  //  vector<int> res;
    while (x != 1) {
      mp[f[x]]++;
      ll temp=f[x];
    while (x%temp==0)
      x /= temp;
    }

  }
    //auto f=factor(n)で vector< pair<素因数、個数>>
  vector<P> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<P> res(1, P(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
};


int main() {
  ll n;
  cin>>n;
  Sieve s(1000005);
  rep(i,n){
    ll a1;
    cin>>a1;
    s.factorMap(a1);

  }
  ll Mi=INF;
  ll Ma=0;
  if (mp.size()==0){
    cout<<"pairwise coprime";
    return 0;
  }
  for(auto i:mp){
    Mi=min(i.second, Mi);
    Ma=max(i.second,Ma);
  //  cout<<"i"<<i.first<<Mi<<" "<<Ma<<endl;
    }
  if (Ma==1)cout<<"pairwise coprime";
  else if (Ma==n)cout<<"not coprime";
  else cout<<"setwise coprime";
}


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

int main(){
    map<int,int> m1;
    int ans=0;
    int n,a;
    cin >> n;

    for (int i = 0; i < n; i++){
        cin >>a;
        if(m1.find(a) != m1.end())m1[a]++;
        else m1[a]=1;
    }

    for (auto p = m1.begin(); p != m1.end(); p++){
        if(p->first > p->second)ans+= p->second;
        else ans += (p->second)-(p->first);
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 4736
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use itertools::Itertools;
use std::process::exit;
use std::cmp::*;
use num::*;
use num::integer::Roots;

fn main() {
    input! {
    mut a:usize,
    mut b:usize,
    m:usize,
    }
    let mut z=0;
    for i in 0.. {
        if z>=m {println!("{}",i);exit(0)}
        if a>=b {z+=a;b-=1}
        else {z+=b;a-=1}
    }
}

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

int main() {
    int N, M; cin >> N >> M;
    priority_queue<int> pq;
    for(int i = 0; i < N; i++) {
        int A; cin >> A;
        pq.push(A);
    }
    for(int i = 0; i < M; i++) {
        int n = pq.top(); pq.pop();
        pq.push(n / 2);
    }
    long long sum = 0;
    while(!pq.empty()) {
        sum += pq.top();
        pq.pop();
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3812