akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<int, ll> pli;
typedef pair<double,double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define TIME(i) Timer i(#i)
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
class Timer {
private:
    string scope_name;
    chrono::high_resolution_clock::time_point start_time;
public:
    Timer (string name) : scope_name(name) {
        start_time = chrono::high_resolution_clock::now();
    }
    ~Timer () {
        auto stop_time = chrono::high_resolution_clock::now();
        auto length = chrono::duration_cast<chrono::microseconds>(stop_time - start_time).count();
        double mlength = double(length) * 0.001;
        debug(scope_name, mlength);
    }
};
#else
#define TIME(i)
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
// const ll MAXN = 

vector<char> stk;
/********** Good Luck :) **********/
int main () {
    TIME(main);
    IOS();

    int n;
    cin >> n;
    REP (i, n) {
        char c;
        cin >> c;
        if (stk.empty() || stk.back() != c) {
            stk.emplace_back(c);
        }
    }

    cout << SZ(stk) << endl;

    return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

std::vector<int> A;
int n;

void print_vector(vector<int> v) {
  for (auto i : v) {
    std::cout << i << " ";
  }
  std::cout << '\n';
}

bool check(int i, int m) {
  if (m == 0) {
    return true;
  }
  if (i >= A.size()) {
    return false;
  }
  bool res = check(i + 1, m) || check(i + 1, m - A[i]);
  return res;
}

int main() {
  cin >> n;
  for (size_t i = 0; i < n; i++) {
    int a;
    cin >> a;
    A.push_back(a);
  }

  int q;
  cin >> q;
  for (size_t i = 0; i < q; i++) {
    int m;
    scanf("%d", &m);

    if (check(0, m)) {
      std::cout << "yes" << '\n';
    } else {
      std::cout << "no" << '\n';
    }
  }

  // print_vector(A);

  return 0;
}



Measured memory_bytes: 3176
#include <bits/stdc++.h>
#include <string>
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define pb push_back
#define ll long long int
#define mod 1000000007
#define f(i,n) for(int i=0;i<n;i++)

using namespace std;
int prime(int n);
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b);
ll gcd(ll a, ll b);

bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int prime(int n){
    int flag=1;
for(int i=2;i<=sqrt(n);i++){
    if(n%i==0){flag=0;break;}
}
  return flag;
}
ll dp[101][100001];

ll ks(ll n,ll w,ll a[],ll val[]){
if(n==-1||w==0) return 0;
else {
    if(dp[n][w]!=-1){

        return dp[n][w];
    }
    else{
        if(a[n]>w){
                dp[n][w]=ks(n-1,w,a,val);
            return ks(n-1,w,a,val);
        }
        else{
            ll temp1=ks(n-1,w,a,val);
            ll temp2=ks(n-1,w-a[n],a,val)+val[n];
            dp[n][w]=max(temp1,temp2);
    return dp[n][w];
        }
    }
}
}

int main(){
       ios_base::sync_with_stdio(false);
    cin.tie(NULL);
ll n,w;
cin>>n>>w;
ll a[n],val[n];
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++){
    cin>>a[i]>>val[i];
}
cout<<ks(n-1,w,a,val);
}


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

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int n; cin >> n;
	string s; cin >> s;

	int cnt = 0;
	REP(i, 10) {
		auto posA = find(s.begin(), s.end(), i + '0');
		if (posA != s.end()) {
			REP(j, 10) {
				auto posB = find(posA+1, s.end(), j + '0');
				if (posB != s.end()) {
					REP(k, 10) {
						auto posC = find(posB+1, s.end(), k + '0');
						if (posC != s.end())
							cnt++;
					}
				}
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}

Measured memory_bytes: 3724
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    n ,k = I2()
    h = Intl()
    dp = [float("inf")]*n
    dp[0] = 0
    for i in range(1,n):
        for j in range(max(0,i-k),i):
            dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
    print(dp[-1])

Measured memory_bytes: 54996
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//BEGIN CUT HERE
template<typename F>
void all_permutations(int n,F f){
  vector<int> vs(n);
  iota(vs.begin(),vs.end(),0);
  do f(vs); while(next_permutation(vs.begin(),vs.end()));
}
//INSERT ABOVE HERE
signed ABC054_C(){
  int n,m;
  cin>>n>>m;
  int es[10][10]={};
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    es[a][b]=es[b][a]=1;
  }
  int ans=0;
  auto f=
    [&](auto &vs){
      if(!es[0][vs[0]+1]) return;
      for(int i=0;i+1<n-1;i++)
        if(!es[vs[i]+1][vs[i+1]+1]) return;
      ans++;
    };
  all_permutations(n-1,f);
  cout<<ans<<endl;
  return 0;
}
/*
  verified on 2019/05/19
  https://atcoder.jp/contests/abc054/tasks/abc054_c
*/
signed main(){
  ABC054_C();
  return 0;
}


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

int main(){
	int i,N,M,X=1,flag=0,debug=0;
	long long int a,ans=0,max=0;
	cin >> N >> M;
	priority_queue<long long int> A;
	for(i=0;i<N;i++){
		cin >> a;
		A.push(a);
	}
	while(M>0){
		i=A.top();
		A.pop();
		A.push(i/=2);
		M--;
	}
	for(i=0;i<N;i++){
		ans+=A.top();
		A.pop();
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef vector< pii > vii;

#define ll          long long
#define ff          first
#define ss          second
#define pb          push_back
#define mkp         make_pair
#define sz          size()

#define forf(a,b,c)    for(int i=a;i<=b;i+=c)
#define forr(a,b,c)    for(int i=a;i>=b;i-=c)
#define all(a)      a.begin(),a.end()
#define mem(a,b)    memset(a,b,sizeof(a))
#define pi          2*acos(0.0)
#define End         return 0;
#define nl endl

#define scan1(a)    scanf("%d",&a)
#define scan2(a,b)  scanf("%d %d",&a,&b)
#define scan3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define scanl(a)    scanf("%lld",&a)
#define scanll(a,b) scanf("%lld %lld",&a,&b)
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define print1(a)    printf("%d",a)
#define print2(a,b)  printf("%d %d",a,b)
#define print3(a,b,c)  printf("%d %d %d",a,b,c)
#define printl(a)    printf("%lld",a)
#define printll(a,b) printf("%lld %lld",a,b)
#define printlll(a,b,c) printf("%lld %lld %lld",a,b,c)

#define MAXN        100000007
#define INF 0x3f3f3f3f
bool mark[100005];vi prime;
void seive(ll N){for(int i=2;i<=N;i++){if(mark[i]==false){prime.pb(i);for(int j=i+i;j<N;j+=i)mark[j]=true;}}}
//freopen("input.txt", "r", stdin);

int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a,b;

    cin>>a>>b;
    if(a==b){
        cout<<a+b<<endl;
        End;
    }
    cout<<max(a,b)+max(a,b)-1<<endl;

}


Measured memory_bytes: 256
<?php
$s = trim(fgets(STDIN));
$t = str_replace('BC','D',$s);
$ans=0;

$a=0;
for($i=0; $i<strlen($t); $i++) {
    if ($t[$i]=='A') $a++;
    elseif ($t[$i]=='D') $ans+=$a;
    else $a=0;
}

echo $ans."\n";


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

signed main() {
    int n, m; cin >> n >> m;
    vector<int> w(n); REP (i, n) cin >> w[i];
    vector<vector<int>> g(n);
    REP (i, m) {
        int u, v; cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> deg(n);
    queue<int> q;
    REP (i, n) {
        deg[i] = g[i].size();
        if (deg[i] == 1) q.push(i);
    }
    vector<bool> core(n, true);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        core[v] = false;
        for (int s : g[v]) {
            if (!core[s]) continue;
            deg[s]--;
            if (deg[s] == 1) q.push(s);
        }
    }

    function<bool(int, int)> dfs1 = [&](int v, int prev) {
        if (core[v]) return true;
        for (int s : g[v]) if (s != prev) {
            if (dfs1(s, v)) {
                core[v] = true;
                return true;
            }
        }
        return false;
    };
    dfs1(0, -1);
    core[0] = true;

    int core_sum = 0;
    REP (i, n) {
        if (core[i]) core_sum += w[i];
    }

    vector<int> from_core;
    REP (i, n) {
        if (core[i]) {
            for (int s : g[i]) from_core.push_back(s);
        }
    }
    function<int(int, int)> dfs2 = [&](int v, int prev) {
        int ma = 0;
        for (int s : (v == 0 ? from_core : g[v])) if (s != prev && !core[s]) {
            ma = max(ma, dfs2(s, v));
        }
        return ma + w[v];
    };
    cout << core_sum + dfs2(0, -1) - w[0] << endl;
}


Measured memory_bytes: 19120
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <cstdlib>
#include <utility>
#include <map>
#include <set>
#include <ios>
#include <iomanip>
#include <functional>
#include <queue>

#define int long long

int inf = (1LL <<  62);
using namespace std;

signed main(){
    int n;
    cin >> n;
    vector<bool> ch_colers(8, false);
    int cntR = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(x <= 399){
            ch_colers[0] = true;
        }
        else if(x <= 799){
            ch_colers[1] = true;
        }
        else if(x <= 1199){
            ch_colers[2] = true;
        }
        else if(x <= 1599){
            ch_colers[3] = true;
        }
        else if(x <= 1999){
            ch_colers[4] = true;
        }
        else if(x <= 2399){
            ch_colers[5] = true;
        }
        else if(x <= 2799){
            ch_colers[6] = true;
        }
        else if(x <= 3199){
            ch_colers[7] = true;
        }
        else{
            cntR++;
        }
    }
    int cnt = 0;
    for(int i = 0; i < 8; i++){
        if(ch_colers[i]){
            cnt++;
        }
    }
    
    if(cntR == 0){
        cout << cnt << " " << cnt;
        exit(0);
    }
    if(cnt == 0){
        cout << 1 << " " << cntR;
        exit(0);
    }
    
    cout << cnt << " " << cnt + cntR;
    
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    try {
        val sc = Scanner(System.`in`)
        val s = sc.nextLine().split(" ")
        val stack = Stack()
        s.forEach {
            when (it) {
                "+" -> stack.push(stack.pop() + stack.pop())
                "-" -> {
                    val a = stack.pop()
                    val b = stack.pop()
                    stack.push(b - a)
                }
                "*" -> stack.push(stack.pop() * stack.pop())
                else -> stack.push(Integer.parseInt(it))
            }
        }
        println(stack.pop())
    } catch (e: Exception) {
        println(e)
    }
}

class Stack {
    private val s = mutableListOf<Int>()

    private var top = s.size - 1

    fun push(x: Int) {
        s.add(x)
        top = s.size - 1
    }

    fun pop(): Int {
        if (isEmpty()) {
            throw Exception("Stack is empty.")
        }
        return s.removeAt(top--)
    }

    fun isEmpty(): Boolean = s.size == 0
}



Measured memory_bytes: 35196
A,B,C = map(int,input().split())
K = int(input())

D = max(A,B,C)
if D == A:
    S = B + C + A*2**K
elif D == B:
    S = A + C + B*2**K
else:
    S = B + A + C*2**K

print(S)


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

#define lli long long int

int main()
{
	lli n,res=0;
	cin>>n;
	vector<lli> v(n);
	for(lli i=0;i<n;i++)
	cin>>v[i];
	sort(v.begin(),v.end(),greater<lli>());
	if(n%2==0)
	{
		for(lli i=0;i<n/2;i++)
		{
			if(i==0) res+=v[i];
			else res=res+2*v[i];
		}
	}
	else
	{
		for(lli i=0;i<(n+1)/2;i++)
		{
			if(i==0||i==(n-1)/2) res+=v[i];
			else res+=2*v[i];
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 4820
n, m = map(int, input().split())

def factorial(n):
    v = 1
    for i in range(1, n + 1):
        v *= i
    return v

def comb(a, b):
    return factorial(a) // (factorial(b) * factorial(a - b))

if (n < 2) & (m < 2):
    print('0')
elif n < 2:
    print(comb(m, 2))
elif m < 2:
    print(comb(n, 2))
else:
    print(comb(n, 2) + comb(m, 2))

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main(){
	
	
	
	long long a,b;
	char op;
	cin>>a>>op>>b;
	if(op=='+'){
	
	cout<<a+b;
}
	else if(op=='-')
	{
	
	cout<<a-b;
}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
x = [0] * N
y = [0] * N
A = [0] * N
for i in range(N):
    A[i] = int(input())
    x[i] = [0] * A[i]
    y[i] = [0] * A[i]
    for j in range(A[i]):
        x[i][j], y[i][j] = map(int, input().split())

x = [[x1-1 for x1 in x0] for x0 in x]

def check_honest():
    flag = True
    for ii in range(len(honest)):
        if int(honest[ii]) == 1:
            for jj in range(A[ii]):
                if int(honest[x[ii][jj]]) != y[ii][jj]:
                    flag = False
    return flag

max_sum = 0
for i in range(2**N):
    honest = bin(2**N | i)[3:]
    if check_honest():
        max_sum = max(max_sum, sum(list(map(int, list(honest)))))

print(max_sum)

Measured memory_bytes: 47068
n,m=map(int,input().split())
##かーどについての初期配列
head =0
tail = n
for i in range(m):
    l,r = map(int,input().split())
    head = max(head,l)
    tail = min(r,tail)
    
if tail < head:
    print(0)
else:
    print(tail-head+1)

Measured memory_bytes: 9060
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<set>
#include<map>
#include<time.h>
#include<stack>
#include<queue>
#include<stdlib.h>
#include<string.h>
#include<vector>
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const LL mod=998244353;
const int inf=1e9;
const double INF=1e9;
int min(int a,int b) {return a<b?a:b;}
int a[15]={0,2,5,5,4,5,6,3,7,6};
string dp[20005];
string max(string a,string b)
{
    int x=a.size();
    int y=b.size();
    if(x>y) return a;
    else if(x<y) return b;
    else{
        return a>b?a:b;
    }
}
int main()
{
    int n,m;
    int d[20];
    int vis[20];
    scanf("%d%d",&n,&m);
    mem(vis,0);
    mem(d,0);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        vis[x]++;
    }
    for(int i=0;i<=n+1;i++) dp[i]="";
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=9;j++)
        {
            if(vis[j]&&(i>=a[j]&&!dp[i-a[j]].empty()||i==a[j]))
            {
                char x=j+'0';
                 dp[i]=max(dp[i],dp[i-a[j]]+x);
            }
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 41600
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007
#define INF (ll)1e18+9
#define N 2000006

using namespace std;

int a, b, c, d, e, f, u[3005], x, y;
double t;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b >> c >> d >> e >> f;
    for (int i = 0; i <= 3000; i++)
        for (int j = 0; j <= 3000; j++)
            if (i * c + j * d <= f)
                u[i * c + j * d] = 1;
    for (int i = 0; i <= 30; i++)
        for (int j = 0; j <= 30; j++)
            if ((i * a * 100 + j * b * 100 <= f)) {
                int k = f - (i * a * 100 + j * b * 100);
                k = min(k, (i * a + j * b) * e);
                while(!u[k]) k--;
                double p = k;
                p /= (i * a * 100 + j * b * 100 + k);
                if (p >= t) t = p, x = i * a * 100 + j * b * 100 + k, y = k;
            }
    cout << x << " " << y << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    int A,B,C,D;cin>>A>>B>>C>>D;
    if(abs(A-C)<=D||(abs(A-B)<=D&&abs(B-C)<=D))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

int main(){
	long n;
	int k;
	
	scanf(" %ld", &n);
	scanf(" %d", &k);
	for(int i=0; i<k; ++i){
		long a, b;
		scanf(" %ld %ld", &a, &b);	
		//対称性を利用して折り返し(1/8サイズになる)
		if(a > (n+1)/2) a=n-a+1;
		if(b > (n+1)/2) b=n-b+1;
		if(a<b) swap(a,b);
		
		long ans=b%3;
		if(ans==0) ans=3;
		printf("%ld\n", ans);
	}
	
	return 0;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

const int mod=1e9+7;

bool isPrime(int N){
    if(N<2) return false;
    for(int i=2;i*i<=N;i++){
        if(N%i==0) return false;
    }
    return true;
}

signed main()
{
    int N; cin>>N;
    int ans=1;
    for(int i=2;i<=N;i++){
        if(isPrime(i)){
            int cnt=0;
            for(int j=i;N/j>0;j*=i) cnt+=N/j;
            ans=ans*(cnt+1)%mod;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef vector<lint> vlint;

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

map<lint, lint> trial_division(lint n){
    map<lint, lint> factor;
    lint tmp = (lint)(sqrt(n)) + 1;
    for (lint i = 2; i < tmp; ++i){
        while (n % i == 0){
            n /= i;
            factor[i] ++;
        }
    }
    if (n != 1) factor[n] ++;
    return factor;
};

int main(){
    lint n; cin >> n;
    lint ans = 0;
    // n-1
    for (lint i = 2; i*i <= n-1; i++){
        if ((n-1) % i == 0){
            ans += 2;
            if (i*i == n-1) ans--;
        }
    }
    
    if (n != 2) ans ++;

    //n
    lint k, j;
    for (lint i = 2; i*i <= n; i++){
        if (n % i == 0){
            k = n;
            while (k % i == 0) k /= i;
            if (k % i == 1) ans ++;

            k = n;
            j = n/i;
            if (i == j) continue;
            while (k % j == 0) k /= j;
            if (k % j == 1) ans ++;
        }
    }
    ans ++;
    cout << ans << endl;
}

Measured memory_bytes: 3608
from sys import stdin
import math


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    R = int(_in[0])  # type:int
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 2*math.pi*R
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Measured memory_bytes: 61976
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
#define vl vector<ll>
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second > b.second; }
ll mod = 1e9+7;

signed main() {
    ll n; cin>>n;
    vector<pair<ll,ll>>r(n),b(n);
    rep(i,n)cin>>r[i].first>>r[i].second;
    rep(i,n)cin>>b[i].first>>b[i].second;
    sort(r.begin(),r.end(),cmp);
    sort(b.begin(),b.end());

    rep(i,n)rep(j,r.size()){
           if(r[j].first<b[i].first&&r[j].second<b[i].second){
               r.erase(r.begin()+j);
               break;
           }
    }
    cout << n-r.size() << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100001
struct edge{ int to,cost; };
typedef pair<int,int> P;

int N,M;
int d[MAX_N];
vector< edge > G[MAX_N];

int main(){
  cin>>N>>M;
  for(int i=0;i<M;i++){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    G[a].push_back((edge){b,c});
  }
  
  int ans=-1;  
  priority_queue< P , vector<P> , greater<P> > Q;

  fill(d,d+MAX_N, (1e9+1) );
  Q.push(P(1,1));
  d[1]=1;
  while(!Q.empty()){
    P p=Q.top();Q.pop();
    int pos=p.second;
    int cost=p.first;
    if(d[pos]<cost)continue;
    for(int i=0;i<(int)G[pos].size();i++){
      edge e=G[pos][i];
      if(e.cost<d[pos])continue;
      if(e.to==N)ans=max(ans,e.cost);
      if(d[e.to]>e.cost){
        d[e.to]=e.cost;
        Q.push(P(d[e.to],e.to));
      }
    }
  }

  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 9580
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	while(n) {
		int dig = n % 10;
		if (dig == 9) return 0 * printf("Yes\n");
	        n /= 10;
	}
	puts("No");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n, m;
  cin >> n >> m;
  vector<string> v(n);
  rep(i, 0, n) cin >> v[i];
  string templ = "";
  rep(i, 0, m) {
    string s;
    cin >> s;
    templ += s;
  }

  rep(i, 0, n - m + 1) {
    rep(j, 0, n - m + 1) {
      string t = "";
      rep(k, i, i + m) rep(l, j, j + m) t += v[k][l];
      if (t == templ) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}


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

int main ( void )
{
	int a, b, c;

	cin >> a >> b >> c;
	if ( ( a < 1 ) || ( a > 9 ) ){
		cout << "ERROR!\n";
		return 0;
	}
	if ( ( b < 1 ) || ( b > 9 ) ){
		cout << "ERROR!\n";
		return 0;
	}
	if ( ( c < 1 ) || ( c > 9 ) ){
		cout << "ERROR!\n";
		return 0;
	}

	if ( ( a == b ) && ( a == c ) && ( b == c ) ){
		cout << "No\n";
		return 0;
	}

	if ( ( a != b ) && ( a != c ) && ( b != c ) ){
		cout << "No\n";
		return 0;
	}

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

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; ++i)
typedef long long ll;
const ll MOD = 1e9+7;


int main(){
    ll n; ll h; cin >> n >> h;
    vector<ll> a(n),b(n);
    rep(i,n) cin >> a[i] >> b[i];
    sort(a.begin(),a.end(), greater<ll>());
    sort(b.begin(),b.end(), greater<ll>());
    ll attack = a[0];
    ll ans = 0;
    rep(i,n){
        if(b[i] > attack){
            h -= b[i];
            ans++;
        }
        if(h<=0){
            cout << ans << endl;
            return 0;
        }
    }
    if(h>0) ans += ((h + attack -1)/attack);
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdlib>
#include <climits>

using namespace std;

int N;
int A[100010];

int main (int argc, char const *argv[])
{
  cin >> N;
  for (size_t i = 0; i < N; i++) cin >> A[i];

  long long ans = 0;
  for (size_t i = 0; i < N; i++) {
    ans += A[i]/2;
    if(A[i]%2 && A[i+1]) A[i+1]+=1;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
from collections import deque
import sys
sys.setrecursionlimit(10++7)

n,k = map(int,input().split())
E = [[] for i in range(n)]
for i in range(n-1):
    
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

mod = 10**9+7

ans = k
q = deque([])
i = 1
for nex in E[0]:
    ans *= k-i
    ans %= mod
    i += 1
    q.append((nex,0))

while q:
    now,bef =  q.popleft()
    i = 2
    for nex in E[now]:
        if nex == bef:
            continue
        ans *= k-i
        ans %= mod
        i += 1
        q.append((nex,now))
print(ans)


Measured memory_bytes: 29456
#include <iostream>
#include <cmath>
#include <stack>
#include <string>
#include <algorithm>

int main() {
    int sum=0, height=0;
    std::string map;
    std::stack<int> backslash;
    std::stack<std::pair<int, int>> water, reversed_water;
    std::cin >> map;
    for (int i=0; i<map.size(); i++) {
        if (map.at(i) == '\\') {
            backslash.push(i);
            height--;
        } else if (map.at(i) == '/') {
            height++;
            if (not backslash.empty()) {
                auto new_water = std::make_pair(i-backslash.top(), backslash.top());
                sum+=(i-backslash.top());
                while (not water.empty()) {
                    if (new_water.second < water.top().second) {
                        new_water.first += water.top().first;
                        water.pop();
                    } else {
                        break;
                    }
                }
                water.push(new_water);
                backslash.pop();
            }
        } else if (map.at(i) == '_') {
            //nothing to do?
        } else {
            std::cout << "invalid input" << std::endl;
        }
    }

    std::cout << sum << std::endl << water.size();
    
    while (not water.empty()) {
        reversed_water.push(water.top());
        water.pop();
    }

    while (not reversed_water.empty()) {
        std::cout << " " << reversed_water.top().first;
        reversed_water.pop();
    }
    std::cout << std::endl;

    return 0;
}


Measured memory_bytes: 3304
using System;

namespace AtCoder.Abc172
{
    class D
    {
        public static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            long ans = 0;
            for (int i = 1; i <= n; i++)
                for (int j = i; j <= n; j += i)
                    ans += j;
            Console.WriteLine(ans);
        }
    }
}


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

int main() {
    //ifstream cin("a.in");

    int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
    
    double opt = -1.0;
    int ans_salt = 0, ans_water = 0;

    for(int aa = 0; aa * a * 100 <= f; ++aa)
        for(int bb = 0; bb * b * 100 <= f; ++bb)
            for(int cc = 0; cc * c <= f; ++cc) {
                int rem = f - aa * a * 100 - bb * b * 100 - cc * c;
                if(rem < 0)
                    continue;
                if((aa * a + bb * b) * e < c * cc)
                    continue;
                int dd = min(rem / d, ((aa * a + bb * b) * e - cc * c) / d);
                int salt = c * cc + d * dd;
                int water = aa * a * 100 + bb * b * 100;

                if(salt / (salt + water + 0.0) > opt) {
                    opt = salt / (salt + water + 0.0);
                    ans_salt = salt;
                    ans_water = water;
                }
            }

    cout << ans_water + ans_salt << " " << ans_salt << "\n";
}

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

int main(){
long N; // 1<=N<=10^10なので以下はlong型にする
  cin>>N;
  
  long best=1;
  for(long i=1; i*i<=N; i++){ // Nの平方根に最も近い整数を求める
   if(N%i==0){best=i;} // bestはNを割り切る最大の平方根i
  }
  
  long num=N/best, ans=0; // numの式はNが素数の場合の対策
  while(num){
    num/=10;
    ans++; // 大きいほうの桁数を算出
  }
  
  cout<<ans;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoderCs
{
    class Program
    {
        static void Main()
        {

            var Num = int.Parse(Console.ReadLine());
            var Comment = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            var Result = 1L;
            var Mod = 1000000007L;
            var Buffer = new int[3] { 0, 0, 0 };

            for (int i = 0; i < Num; i++)
            {

                Result *= Buffer.Count(x => x == Comment[i]);
                if (Buffer[0] == Comment[i]) Buffer[0]++;
                else if (Buffer[1] == Comment[i]) Buffer[1]++;
                else Buffer[2]++;

                if (Result == 0) break;
                while (Mod < Result)
                {
                    Result -= Mod;
                }

            }

            Console.WriteLine(Result);

        }


    }
}


Measured memory_bytes: 27088
N,M,X=map(int,input().split())
A=[]
C=[]
for i in range(N):
    CA=list(map(int,input().split()))
    c=CA[0]
    a=CA[1:]
    A.append(a)
    C.append(c)

import itertools
PRD=list(itertools.product([0,1], repeat=N))

ans=10**15
for i in range(len(PRD)):
    scores=[0 for i in range(M)]
    money=0
    #print(PRD[i])
    for j in range(N):
        for k in range(M):
            scores[k]+=PRD[i][j]*A[j][k]
        money+=PRD[i][j]*C[j]
    #print(scores,money)
    if min(scores)>=X:
        ans=min(ans,money)

if ans==10**15:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 9516
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;


void solve(long long N, long long K){
    cout<< min(N%K, K-N%K)<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.conv, std.string;

void main()
{
  string[] inputs = split(readln());
  int N = to!int(inputs[0]);
  int A = to!int(inputs[1]);
  int B = to!int(inputs[2]);

  int time_charge = A * N;
  writeln(time_charge < B ? time_charge : B);
}


Measured memory_bytes: 256
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy

def j(q):
    if q==1: print("yes")
    else:print("no")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())


#n = ip()                              #入力整数1つ
#n,k= (int(i) for i in input().split())      #入力整数横2つ
#n,x,y = (int(i) for i in input().split())    #入力整数横3つ
#n,a,b,c= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
b = set()
for i in range(len(a)):
    b.add(a[i])
if len(b) == len(a):
    j(1)
j(0)

Measured memory_bytes: 23472
x=int(input())

LIST2=[1]
LIST2X=[-2]

N=1
for i in range(1,30):
    N=N+4**i
    LIST2.append(N)
N=-2
for i in range(1,30):
    N=N-2*4**i
    LIST2X.append(N)



LIST=[0]*60

def nex(N):
    if N>0:
        for i in range(30):
            if N<=LIST2[i]:
                break
        LIST[i*2]+=1
        return N-(-2)**(i*2)

    if N<0:
        for i in range(30):
            if N>=LIST2X[i]:
                break
        LIST[i*2+1]+=1
        return N-(-2)**(i*2+1)

while x!=0:
    x=nex(x)
    #print(x)

for i in range(59,-1,-1):
    if LIST[i]==1:
        break

for j in range(i,-1,-1):
    print(LIST[j],end="")
            

        


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int main2() {
  int A, B; cin >> A >> B;
  int Q; cin >> Q;
  vector<ll> a(A), b(B);
  REP(i, A) cin >> a[i];
  REP(i, B) cin >> b[i];

  vector<int> alb(A, -1), arb(A, -1);
  vector<int> bla(B, -1), bra(B, -1);

  {
    int j = 0;
    for (int i = 0; i < A; i++) {
      while (j < B && b[j] < a[i]) j++;
      arb[i] = j;
    }
    j = B-1;
    for (int i = A-1; i >= 0; i--) {
      while (j >= 0 && a[i] < b[j]) j--;
      alb[i] = j;
    }
    // pv(ALL(arb));
    // pv(ALL(alb));
  }
  {
    int i = 0;
    for (int j = 0; j < B; j++) {
      while (i < A && a[i] < b[j]) i++;
      bra[j] = i;
    }
    i = A - 1;
    for (int j = B-1; j >= 0; j--) {
      while (i >= 0 && b[j] < a[i]) i--;
      bla[j] = i;
    }
    // pv(ALL(bra));
    // pv(ALL(bla));
  }

  REP(_, Q) {
    ll x; cin >> x;
    ll ans = 1LL << 61;

    int pos = distance(a.begin(), lower_bound(ALL(a), x));
    if (0 <= pos && pos < A) {
      if (0 <= alb[pos] && alb[pos] < B) chmin(ans, abs(x - a[pos]) + abs(a[pos] - b[alb[pos]]));
      if (0 <= arb[pos] && arb[pos] < B) chmin(ans, abs(x - a[pos]) + abs(a[pos] - b[arb[pos]]));
    }
    pos--;
    if (0 <= pos && pos < A) {
      if (0 <= alb[pos] && alb[pos] < B) chmin(ans, abs(x - a[pos]) + abs(a[pos] - b[alb[pos]]));
      if (0 <= arb[pos] && arb[pos] < B) chmin(ans, abs(x - a[pos]) + abs(a[pos] - b[arb[pos]]));
    }

    pos = distance(b.begin(), lower_bound(ALL(b), x));
    if (0 <= pos && pos < B) {
      if (0 <= bla[pos] && bla[pos] < A) chmin(ans, abs(x - b[pos]) + abs(b[pos] - a[bla[pos]]));
      if (0 <= bra[pos] && bra[pos] < A) chmin(ans, abs(x - b[pos]) + abs(b[pos] - a[bra[pos]]));
    }
    pos--;
    if (0 <= pos && pos < B) {
      if (0 <= bla[pos] && bla[pos] < A) chmin(ans, abs(x - b[pos]) + abs(b[pos] - a[bla[pos]]));
      if (0 <= bra[pos] && bra[pos] < A) chmin(ans, abs(x - b[pos]) + abs(b[pos] - a[bra[pos]]));
    }
    printf("%lld\n", ans);
  }
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  int S=0,M=0;
  for(int i=0;i<N;i++){
    int P;
    cin>>P;
    S+=P;
    M=max(M,P);
  }
  int ans=S-M/2;
  cout<<ans<<endl;
}

Measured memory_bytes: 3628
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <iostream>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

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

    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    pair<int, int> ans = make_pair(A * 100, 0);
    float con = 0.0;
    int a = 0;
    while (1) {
        int an = A * a * 100;
        if (an > F)
            break;
        int b = 0;
        while (1) {
            int bn = B * b * 100;
            if (an + bn > F)
                break;
            int c = 0;
            while (1) {
                int cn = c * C;
                if (an + bn + cn > F)
                    break;
                int d = 0;
                while (1) {
                    int dn = d * D;
                    if (an + bn + cn + dn > F)
                        break;
                    if (cn + dn <= (an + bn) / 100 * E && con < (float)(cn + dn) / (float)(an+bn+cn+dn)){
                        ans = make_pair(an + bn + cn + dn, cn + dn);
                        con = (float)(cn + dn) / (float)(an + bn + cn + dn);
                    }
                    ++d;
                }
                ++c;
            }
            ++b;
        }
        ++a;
    }
    cout << ans.first << " " << ans.second << "\n";
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] strs = Console.ReadLine().Split(' ');
            int N = int.Parse(strs[0]);
            int K = int.Parse(strs[1]);
            int Q = int.Parse(strs[2]);

            int[] vals = new int[N];
           

            for(int i = 0; i<Q; i++)
            {
                int index = int.Parse(Console.ReadLine()) - 1;
                vals[index]++;

            }

            for(int i = 0; i<N; i++)
            {
                if(K - Q + vals[i] > 0)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }

            //Console.ReadKey();

        }



    }


}


Measured memory_bytes: 17600
import numpy as np
N = int(input())
A = np.array(input().split(), dtype=np.int32)
B = np.array(input().split(), dtype=np.int32)
	
def f(t,A,B):
  power = 1<<t
  mask = (power<<1)-1
  AA = A & mask
  BB = B & mask
  AA.sort()

  x1,x2,x3 = (np.searchsorted(AA, v-BB).sum() for v in [power, 2*power, 3*power])
  zero_cnt = x1 + (x3-x2)
  return (N-zero_cnt)%2
  
answer = 0
for t in range(30):
	x = f(t,A,B)
	if x == 1:
		answer += 1<<t

print(answer)


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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int

int main(){
  int N;
  cin>>N;
  ll A[N],Q;
  cin>>A[0];
  cin>>A[1];
  Q=__gcd(A[0],A[1]);
  for(int i=2;i<N;i++){
    cin>>A[i];
    Q=__gcd(Q,A[i]);
  }
  cout<<Q<<endl;

  return 0;
}


Measured memory_bytes: 1024
/* 
 * Project: AtCoder Beginners Contest 149 B - Greedy Takahashi
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/07/24
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
#include <algorithm>
#include <numeric>
using namespace std;

long a, b;
long k;

void solve() {

    long rest_a;
    long rest_b = b;
    if (k <= a) {
        rest_a = a - k;
    } else if (k <= a + b) {
        rest_a = 0;
        rest_b = b - k + a;
    } else {
        rest_a = 0;
        rest_b = 0;
    }
    printf("%ld %ld\n", rest_a, rest_b);
    return;
}

int main() {

    scanf("%ld", &a);
    scanf("%ld", &b);
    scanf("%ld", &k);

    solve();

}

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

class Doubling{
public:
  const int n, m;
  std::vector<std::vector<int>> table;
  
  // 常に、next[i] >= i を満たすようにする。
  Doubling(const std::vector<int> &next):
    n(next.size()), m(ceil(log2(n))+1), table(m, std::vector<int>(n)){
    for(int i = 0; i < n; ++i) table[0][i] = next[i];
    for(int i = 1; i < m; ++i){
      for(int j = 0; j < n; ++j){
        int k = table[i-1][j];
        if(k >= 0 and k < n){
          table[i][j] = table[i-1][k];
        }
      }
    }
  }

  int distance(int a, int b) const { // aからbに移動する(超える)最小回数 (a<=b)
    int ret = 0;
    int cur = a;

    while(1){
      if(table[0][cur] >= b){
        ++ret;
        break;
      }

      if(table[0][cur] <= cur) return -1;

      int next = -1;
      int diff = 0;
      
      for(int i = 0; i < m; ++i){
        if(table[i][cur] < b and table[i][cur] >= 0){
          next = table[i][cur];
          diff = 1 << i;
        }
      }

      if(next >= cur){
        ret += diff;
        cur = next;
      }else{
        return -1;
      }
    }
    
    return ret;
  }
};



int main(){
  int N; scanf("%d", &N);

  std::vector<int> x(N);
  for(int i = 0; i < N; ++i) scanf("%d", &x[i]);
  
  int L; scanf("%d", &L);

  std::vector<int> next(N);

  for(int i = 0; i < N; ++i){
    next[i] = std::upper_bound(x.begin(), x.end(), x[i]+L) - x.begin() - 1;
  }

  Doubling d(next);

  int Q; scanf("%d", &Q);
  while(Q--){
    int a,b; scanf("%d%d", &a, &b);
    --a, --b;
    if(a > b) std::swap(a,b);

    int ans = d.distance(a,b);
    
    printf("%d\n", ans);
  }
  
  return 0;
}


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

int main() {
	int N;
	cin >> N;
	double a = 1.08;
	for (int i = 0; i <= N; i++) {
		if (floor((double)(i * a)) == N) {
			cout << i << endl;
	        return 0;
		}
	}
	cout << ":(" << endl;
	}

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


int main(){
    ll n,x,m;
    cin >> n >> x >> m;
    ll res=0;
    if(x==0||m==1){
        cout << 0 << endl;
        return 0;
    }
    if(n==1){
        cout << x << endl;
        return 0;
    }
    ll memo1;
    map<ll,ll> mp;
    vector<ll> cal;
    cal.push_back(x);
    mp[x]++;
    res+=x;
    for(ll i=2;i<=min(n,1000000LL);i++){
        ll count=(cal[cal.size()-1]*cal[cal.size()-1])%m;
        cal.push_back(count);
        res+=count;
        mp[count]++;
        if(count==0||i==n){
            cout << res << endl;
            return 0;
        }
        if(mp[count]>=2){
            memo1=i;
            memo1--;
            break;
        }
    }
    ll memo2=cal[memo1];
    ll memo3;
    for(ll i=0;i<ll(cal.size());i++){
        if(cal[i]==memo2){
            memo3=i;
            break;
        }
    }
    ll count1=0,count2=0,count3=0;
    for(ll i=0;i<=memo3;i++){
        count1+=cal[i];
    }
    for(ll i=memo3+1;i<=memo1;i++){
        count2+=cal[i];
    }
    ll memo4=(n-memo3-1)/(memo1-memo3);
    ll memo5=(n-memo3-1)%(memo1-memo3);
    for(ll i=memo3+1;i<memo3+1+memo5;i++){
        count3+=cal[i];
    }
    cout << count1+count2*memo4+count3 << endl;
    return 0;
}  


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

int main() {
	string a;
	cin >> a;
	for (int i = 0; i < 3; i++) {
		if (a.at(i) == '1') {
			a.at(i) += 8;
		}
		else if (a.at(i) == '9') {
			a.at(i) -= 8;
		}
	}
	cout << a << endl;
}

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

int N;
int sum = 0;
string X;
map<string, int> mp;

int main(){
	cin >> N;
	rep(i, N){
		int t;
		cin >> X >> t;
		sum += t;
		mp[X] = sum;
	}
	cin >> X;
	cout << sum - mp[X] << endl;
	return 0;
}

Measured memory_bytes: 256
# abc153_b.py
# https://atcoder.jp/contests/abc153/tasks/abc153_b

# B - Common Raccoon vs Monster /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# アライグマはモンスターと戦っています。
# モンスターの体力は Hです。
# アライグマは N種類の必殺技を使うことができ、i 番目の必殺技を使うとモンスターの体力を Ai減らすことができます。 
# 必殺技を使う以外の方法でモンスターの体力を減らすことはできません。
# モンスターの体力を 0以下にすればアライグマの勝ちです。
# アライグマが同じ必殺技を 2度以上使うことなくモンスターに勝つことができるなら Yes を、できないなら No を出力してください。

# 制約
#     1≤H≤109
#     1≤N≤105
#     1≤Ai≤104
#     入力中のすべての値は整数である。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# H N
# A1 A2 ... AN

# 出力

# アライグマが同じ必殺技を 2度以上使うことなくモンスターに勝つことができるなら Yes を、できないなら No を出力せよ。

# 入力例 1
# 10 3
# 4 5 6

# 出力例 1
# Yes

# 例えば 2番目と 3 番目の必殺技を使うことで、モンスターの体力を 0以下にできます。

# 入力例 2
# 20 3
# 4 5 6

# 出力例 2
# No

# 入力例 3
# 210 5
# 31 41 59 26 53

# 出力例 3
# Yes

# 入力例 4
# 211 5
# 31 41 59 26 53

# 出力例 4
# No


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    H, N = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    if sum(values) < H:
        result = 'No'
    else:
        result = 'Yes'

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['10 3', '4 5 6']
        lines_export = ['Yes']
    if pattern == 2:
        lines_input = ['20 3', '4 5 6']
        lines_export = ['No']
    if pattern == 3:
        lines_input = ['210 5', '31 41 59 26 53']
        lines_export = ['Yes']
    if pattern == 4:
        lines_input = ['211 5', '31 41 59 26 53']
        lines_export = ['No']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


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

int main(){
    int a,b,c;

    cin >> a >> b >> c;

    if(a == b && b == c){
        cout << "1\n";
    }
    else if(a == b){
        if(b != c){
            cout << "2\n";
        }
    }
    else if(a == c){
        if(b != c){
            cout << "2\n";
        }
    }
    else if(b == c){
        if(a != c){
            cout << "2\n";
        }
    }
    else{
        cout << "3\n";
    }

    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
Foods = [0]*(M+1)
for i in range(N):
    K = list(map(int, input().split()))
    for j in range(1, K[0]+1):
        Foods[K[j]] += 1
cnt = 0
for i in range(M+1):
    if Foods[i] == N:
        cnt += 1
print(cnt)

Measured memory_bytes: 3060