akhauriyash/Code-Regression huggingface dataset:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque, defaultdict

    n, m = map(int, readline().split())
    graph = [defaultdict(set) for _ in range(n + 1)]
    for _ in range(m):
        p, q, c = map(int, readline().split())
        graph[p][c].add(q)
        graph[q][c].add(p)
    q = deque([(1, 0, -1)])
    vis = set()
    while q:
        now, v, c = q.popleft()
        if now == n:
            print(v)
            exit()
        if (now, c) in vis:
            continue
        vis.add((now, c))
        if c == 0:
            for cc in graph[now]:
                for next in graph[now][cc]:
                    if (next, cc) not in vis:
                        q.append((next, v + 1, cc))
        else:
            for next in graph[now][c]:
                if (next, c) not in vis:
                    q.appendleft((next, v, c))
            if (now, 0) not in vis:
                q.appendleft((now, v, 0))
    print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 207364
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    x = II()
    if x == 0:
        print(1)
    else:
        print(0)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9112
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
struct points
{
    double x,y;
}a[10];
double d(points A,points B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double fac[10];

int main()
{
    fac[0]=1;
    for(int i=1;i<=9;++i)fac[i]=fac[i-1]*1.0*i;
    cin>>n;
    double ans=0;
    for(int i=1;i<=n;++i)cin>>a[i].x>>a[i].y;
    double fenmu=1.0;
    for(int i=1;i<=n;++i)fenmu*=i;
    for(int i=1;i<=n;++i)
    {
        for(int j=i+1;j<=n;++j)
        {
            double t=d(a[i],a[j]);
            ans+=t*fac[2]*fac[n-1]/fenmu;
        }
    }
    printf("%.12lf\n",ans);
    return 0;
}


Measured memory_bytes: 256
//08-3 ??????????????????
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
using namespace std;
int main(){
    bool flg = true;
    while(flg){
        int n;
        cin >> n;

        if(n == 0){
            flg = false;
        }
        else{
            int card[202] = {};
            card[2*n+1] = -1;
    
            for(int i=0; i<n; i++){
                int tmp;
                cin >> tmp;
                card[tmp] = 1;
            }
    
            bool flg2 = true;
            int ba = 0;
            int A = n;
            int B = n;
            while(flg2){
                int i = ba+1;
                bool flg3 = true;
                while(flg3){//???????????????????????¢???
                    if(card[i]==1){
                        card[i] = -1;
                        ba = i;
                        A--;
                        flg3 = false;
                    }
                    else if(i >= 2*n){//???????????????????????????
                        if(ba != 0){//??????
                            ba = 0;
                            flg3 = false;
                        }
                        else{//??????
                            flg3 = false;
                            flg2 = false;
                        }
                        
                    }
                    i++;
                }
                if(flg2){
                    i = ba+1;
                    flg3 = true;
                    while(flg3){//???????????????????????¢???
                        if(card[i]==0){
                            card[i] = -1;
                            ba = i;
                            B--;
                            flg3 = false;
                        }
                        else if(i >= 2*n){//???????????????????????????
                            if(ba != 0){//??????
                                ba = 0;
                                flg3 = false;
                            }
                            else{//??????
                                flg3 = false;
                                flg2 = false;
                            }
                            
                        }
                        i++;
                    }
                }
            }
            cout << B << endl << A << endl;    
        }
    }
    return 0;
}


Measured memory_bytes: 3096
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**16
    n=II()
    aa=LI()
    if n%2:
        dp=[[-inf]*3 for _ in range(n)]
        dp[0][2]=0
        dp[0][0]=aa[0]
        dp[1][1]=aa[1]
        for i,a in enumerate(aa[2:],1):
            if i-1>=0:dp[i+1][0]=dp[i-1][0]+a
            if i-2>=0:dp[i+1][1]=max(dp[i-2][0],dp[i-1][1])+a
            elif i-1>=0:dp[i+1][1]=dp[i-1][1]+a
            if i-3>=0:dp[i+1][2]=max(dp[i-3][0],dp[i-2][1],dp[i-1][2])+a
            elif i - 2 >= 0: dp[i + 1][2] = max(dp[i - 2][1], dp[i - 1][2]) + a
            elif i - 1 >= 0: dp[i + 1][2] = dp[i - 1][2] + a
        ans=max(dp[-1][2],dp[-2][1])
        if n>2:ans=max(ans,dp[-3][0])
    else:
        dp=[[-inf]*2 for _ in range(n)]
        dp[0][0]=aa[0]
        dp[1][1]=aa[1]
        for i,a in enumerate(aa[2:],1):
            dp[i+1][0]=dp[i-1][0]+a
            if i-2>=0:dp[i+1][1]=max(dp[i-2][0],dp[i-1][1])+a
            elif i - 1 >= 0: dp[i + 1][1] = dp[i - 1][1] + a
        ans=max(dp[-1][1],dp[-2][0])
    print(ans)

main()

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

const int N = 1e5 + 5;
typedef long long ll;
vector<int> adj[N];
bool visited[N]={};
int nodesNum;
int dp[N];
void dfs(int node){
    if(visited[node])
        return;
visited[node]=1;
for(int i=0;i<adj[node].size();i++){
        int child=adj[node][i];
    if(!visited[child])
    dfs(child);
    dp[node]=max(1+dp[child],dp[node]);
}
}



int main()
{
   int edges;
   cin >> nodesNum >> edges;
   while (edges--)
   {
       int x, y;
       cin >> x >> y;
       adj[x].push_back(y);
   }
   for(int i=1;i<=nodesNum;i++){
        if(!visited[i])
      dfs(i);
   }
   int ans=0;
   for(int i=1;i<=nodesNum;i++){
    ans=max(ans,dp[i]);
   }
 cout<<ans;
   return 0;
}


Measured memory_bytes: 8192
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main(){
		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
		int M,D;
		cin>>M>>D;
		int tot=0;
		for(int i=1;i<=M;i++){
			for(int d=22;d<=D;d++){
				if((d/10)>=2 && (d%10)>=2 && (d/10)*(d%10)==i){
            tot++;
				}
			}
		}
		cout<<tot;
		return 0;
}


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

using LL = long long;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
 
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
// clang-format on

void solve(long long N) {
  // solver code

  cout << (int)(N / 2.0 + 0.5) << endl;
}

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


Measured memory_bytes: 256
import sys
#Nは整数並んでいる整数の数
N = int(input())
H = list(map(int, input().split()))

#リストの中身が単調非減少にできるかどうかを考える
for i in range(N-1):
    #H[i]<H[i+1]の時、すでに単調非減少を満たす。とりあえず右のやつを引いておくと便利
    if(H[i]<H[i+1]):
        
        H[i+1] = H[i+1]-1
        continue
    #H[i]=H[i+1]のときは何もしない
    elif(H[i] == H[i+1]):
        continue
    #左右の数字を比較した時、左のほうが1大きい場合は、左の数を1減らすことによって、単調非減少を実現可能である
    #elif(H[i] - H[i+1] == 1):
        #H[i] = H[i]-1 
        #continue
    
    
    

for j in range(N-1):
    if(H[j]>H[j+1]):
        print('No')
        sys.exit()
print("Yes")
    
        

Measured memory_bytes: 14252
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){ 
  char a;cin>>a;
  if(a=='A')cout<<"T";
  if(a=='T')cout<<"A";
  if(a=='C')cout<<"G";
  if(a=='G')cout<<"C";
  }


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        // input
        int red = scan.nextInt();
        int green = scan.nextInt();
        int blue = scan.nextInt();
        int border = scan.nextInt();

        // search
        int count = 0;
        for(int r = 0; r <= border; r++){
            for(int g = 0; g <= border; g++){
                if((border - red * r - green * g) % blue == 0 && (border - red * r - green * g) >= 0){
                    count++;
                }
            }
        }

        // answer
        System.out.println(count);


    }
}

Measured memory_bytes: 21844
A, B, C, D = map(int, input().split())

# 高橋君のモンスターは体力が A で攻撃力が B です。
# 青木君のモンスターは体力が C で攻撃力が D です。
# 高橋君が勝つなら Yes、負けるなら No を出力してください。

while A > 0 and C > 0:
    C -= B
    if C <= 0:
        print('Yes')
        break
    A -= D
    if A <= 0:
        print('No')
        break

Measured memory_bytes: 9040
from collections import Counter,defaultdict
n = int(input())

dic = {}
dicjudge = {}
for i in range(n):
    C = Counter(input())
    for j in C:
        if not j in dic:
            dic[j] = C[j]
        elif dic[j] > C[j]:
            dic[j] = C[j]

        if j in dicjudge:
            dicjudge[j] += 1
        else:
            dicjudge[j] = 1

anslst = sorted(dic.items())
#print(anslst)

ans = ''
for i in anslst:
    if dicjudge[i[0]] >= n:
        ans += i[0] * i[1]
print(ans)



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

int main(){
	ll n, a, b;
  cin >> n >> a >> b;
  ll ans = 0;
  if(a == 0) cout << ans << endl;
  else{
    if(n % (a + b) <= a) {
      ans = n / (a + b) * a + n % (a + b);
      cout << ans << endl;
    }
    else{
      ans = n / (a + b) * a + a;
      cout << ans << endl;
    }
  }
}

Measured memory_bytes: 256
#include <cstdio>
char M[100][100];
int main()
{
	int h,w;
	scanf("%d%d",&h,&w);
	for (int i = 0; i < h; i++)
		scanf("%s",M[i]);
	for (int i = 0; i < h; i++)
	for (int j = 0; j < w; j++)
	{
		if (M[i][j] != '#')
		{
			int cnt = 0;
			for (int x = -1; x <= 1; x++)
			for (int y = -1; y <= 1; y++)
			{
				if (i + x >= 0 && i + x < h && j + y >= 0 && j + y < w && M[x + i][y + j] == '#')
					cnt++;
			}
			M[i][j] = '0' + cnt;
		}
	}
	for (int i = 0; i < h; i++)
		printf("%s\n",M[i]);
} 

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

int N, M;
const int MAX_N = 50 + 10;
int a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N];

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> a[i] >> b[i];
    for (int i = 0; i < M; i++) cin >> c[i] >> d[i];

    vector<int> ans;
    for (int i = 0; i < N; i++) {
        int D = 1.0e9;
        int num;
        for (int j = M-1; j >= 0; j--) {
            if (D >= abs(c[j] - a[i]) + abs(d[j] - b[i])) {
                D = abs(c[j] - a[i]) + abs(d[j] - b[i]);
                num = j+1;
            }
        }

        ans.push_back(num);
    }

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
import math

a, b, h, m = list(map(int, input().split()))

theta = ( 360/(12*60) * (h*60 + m) ) - (360/60 * m)

x2 = a**2 + b**2 - 2*a*b*math.cos(math.radians(theta))
print(math.sqrt(x2))

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

using namespace std;

int main() {
    string S;
    cin >> S;
    int count = 0;
    for(int i = 0; i < S.size() / 2; i++) {
        if(S.at(i) != S.at(S.size() - 1 - i))
            count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
<?php
// 桁数が増えてもOK！$valueと$sumを任意で変更する
$value = fgets(STDIN);
// 計算後の値
$sum = 7;
// 桁数(なぜか入力に改行(?)があるのでtrimする)
$length = strlen(trim($value));
// +,-の数
$signCount = $length - 1;
// 左から順番に1桁ずつ配列に格納
$array = array();
for ($i = 0; $i < $length; $i ++) {
    $array[] = (int) substr($value, $i, 1);
}

// 全探索(記号種類2(+,-)を計算回数分べき乗する)
// 1ならプラス、0ならマイナス
for ($i = 0; $i < pow(2, $signCount); $i ++) {
    $result = $array[0];
    $resultStr = $array[0];
    // 桁の左から比較する
    for ($j = $signCount - 1; $j >= 0; $j --) {
        // 左シフトした値と比べる
        if (($i & (1 << $j)) === (1 << $j)) {
            $result += $array[$signCount - $j];
            $resultStr .= "+" . $array[$signCount - $j];
        } else {
            $result -= $array[$signCount - $j];
            $resultStr .= "-" . $array[$signCount - $j];
        }
    }
    if ($result === $sum) {
        echo $resultStr . "=" . $sum;
        exit(0);
    }
}


Measured memory_bytes: 3576
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[10001];

signed main(){
    int n,p;
    memset(dp, 0, sizeof(dp));
    cin>>n>>p;
    string s;
    cin>>s;
    int count=0;
    dp[0] = 1;
    int curr=0;
    int tn=1;
    if(p==2 || p==5){
        for(int i=(n-1); i>=0; i--){
            if((s[i]-'0')%p==0){
                count += i+1;
            }
        }
        cout<<count<<endl;
        return 0;
    }
    for(int i=(n-1); i>=0; i--){
        curr = curr +(((s[i]-'0')*tn)%p);
        curr %= p;
        dp[curr]++;
        tn = tn*10;
        tn %= p;
    }
    for(int i=0; i<p; i++){
        count += ((dp[i]*(dp[i]-1))/2);
    }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 644
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


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

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)







int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    cout << min(c, b / a) << endl;
}


Measured memory_bytes: 256
s = input()
l = len(s)

if len(s) == 2:
    if s[0] == s[1]:
        print(1, 2)
    else:
        print(-1, -1)
    exit()

for i in range(l - 2):
    p = s[i:i+3]
    p_set = set(p)
    if len(p_set) != 3:
        print(i + 1, i + 3)
        exit()

print(-1, -1)


Measured memory_bytes: 3188
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int ans;
  if(n<10) ans=n;
  else if(n<100) ans=9;
  else if(n<1000) ans=n-90;
  else if(n<10000) ans=909;
  else if(n<100000) ans=909+n-9999;
  else ans=90909;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input().rstrip()
ret = 0
me = []
for i, rival in enumerate(t):
    if rival == 'r':
        if i - k >= 0 and me[i - k] == 'p':
            if i + k < n:
                if t[i + k] == 'p':
                    me.append('r')
                elif t[i + k] == 's':
                    me.append('s')
                elif t[i + k] == 'r':
                    me.append('s')
        else:
            me.append('p')
            ret += p
    elif rival == 's':
        if i - k >= 0 and me[i - k] == 'r':
            if i + k < n:
                if t[i + k] == 'r':
                    me.append('s')
                elif t[i + k] == 'p':
                    me.append('p')
                elif t[i + k] == 's':
                    me.append('s')
        else:
            me.append('r')
            ret += r
    elif rival == 'p':
        if i - k >= 0 and me[i - k] == 's':
            if i + k < n:
                if t[i + k] == 'r':
                    me.append('r')
                elif t[i + k] == 's':
                    me.append('p')
                elif t[i + k] == 'p':
                    me.append('r')
        else:
            me.append('s')
            ret += s
print(ret)


Measured memory_bytes: 4212
#include<stdio.h>
#include<vector>
using namespace std;
vector<int> e[100];
bool used[100];
int max(int a,int b){return a>b?a:b;}
int dfs(int f,int t){
	int i;
	int m=0;
	for(i=0;i<e[t].size();i++){
		if(e[t][i]==f)continue;
		if(!used[e[t][i]]){
			used[t]=true;
			m=max(m,dfs(t,e[t][i]));
			used[t]=false;
		}
	}
	return m+1;
}
int main(){
	int n;
	int i,j;
	while(1){
	scanf("%d",&n);
	if(n==0)return 0;
	for(i=0;i<100;i++)e[i].clear();
	for(i=0;i<n;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;b--;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	int ans=0;
	for(i=0;i<100;i++)used[i]=false;
	for(i=0;i<100;i++){
		for(j=0;j<e[i].size();j++){
			used[i]=true;
			ans=max(ans,dfs(i,e[i][j])+1);
			used[i]=false;
		}
	}
	printf("%d\n",ans);
	}
}

Measured memory_bytes: 1056
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <array>
#include <bitset>
using namespace std;

typedef long long ll;
const ll mod=1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<n+1;i++)
int main(){
    string S;
    cin>>S;
    int a=stoi(S);
    int b=a/100;
    int c=a%100;
    if(0<b && b<13 && 0<c && c<13) cout<<"AMBIGUOUS"<<endl;
    else if(0<b && b<13) cout<<"MMYY"<<endl;
    else if(0<c && c<13) cout<<"YYMM"<<endl;
    else cout<<"NA"<<endl;

    return 0;
}

Measured memory_bytes: 256
# 1行目の入力を空白で分割された数値として扱う
A, B, K = map(int, input().split())

#
if A >= K:
    A = A - K
else:
    if A + B >= K:
        B = B - (K - A)
        A = 0
    else:
        B = 0
        A = 0

# 答えの出力
print(str(A) + " " + str(B))

Measured memory_bytes: 2940
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, Y) for (int(X) = 0; (X) < (Y); ++(X))
#define rrep(X, Y) for (int(X) = (Y)-1; (X) >= 0; --(X))
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const string YES = "YES";
const string NO = "NO";

void solve(std::string S) {
  const string akiba = "AKIHABARA";
  if (S.size() > akiba.size()) {
    print(NO);
    return;
  }

  int i = 0;
  int j = 0;
  int aAdd = 0;
  bool ok = true;
  while (j < akiba.size()) {
    if (S[i] == akiba[j]) {
      i++;
      j++;
      continue;
    }

    if (S[i] != akiba[j] && akiba[j] == 'A') {
      aAdd++;
      j++;
      continue;
    }

    ok = false;
    break;
  }

  if (ok && akiba.size() - S.size() == aAdd) {
    print(YES);
  } else {
    print(NO);
  }
}

int main() {
  std::string S;
  std::cin >> S;
  solve(S);
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int k,tot,n,m,p[500001],q[500001],l[2000001],r[2000001],f[2000001],lz[2000001],dbd,fir[500001],nex[500001],sto[500001],ru[500001];
void addbian(int aa,int bb)
{
	tot++;
	nex[tot]=fir[aa];
	fir[aa]=tot;
	sto[tot]=bb;
} 
int getmin(int aa,int bb)
{
	if(aa<bb) return(aa);
	else return(bb);
}
void update(int num,int hh)
{
	lz[num]=hh;
	f[num]=hh;
}
void built(int num,int x,int y)
{
	l[num]=x;
	r[num]=y;
	f[num]=dbd;
	lz[num]=0;
	if(x==y) return;
	int mid=(x+y)/2;
	built(num*2,x,mid);
	built(num*2+1,mid+1,y);
}
int ask(int num,int x)
{
	if(l[num]==r[num])return(f[num]);
	int mid=(l[num]+r[num])/2;
	if(lz[num]>0)
	{
		update(num*2,lz[num]);
		update(num*2+1,lz[num]);
		lz[num]=0;
	}
	if(x<=mid)return(ask(num*2,x));
	else return(ask(num*2+1,x));
	f[num]=getmin(f[num*2],f[num*2+1]);
}
void gai(int num,int x,int y)
{
	if((x==l[num])&&(y==r[num]))
	{
		update(num,dbd);
		return;
	}
	int mid=(l[num]+r[num])/2;
	if(lz[num]>0)
	{
		update(num*2,lz[num]);
		update(num*2+1,lz[num]);
		lz[num]=0;
	}
	if(y<=mid)gai(num*2,x,y);
	else
	{
		if(x>mid) gai(num*2+1,x,y);
		else
		{
			gai(num*2,x,mid);
			gai(num*2+1,mid+1,y); 
		}
	}
	f[num]=getmin(f[num*2],f[num*2+1]);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		q[p[i]]=i;	
	}
	dbd=0;
	built(1,1,n); 
	for(int i=1;i<=n;i++)
	{
		int bb=ask(1,q[i]);
		if(bb!=0)
		{
			addbian(bb,q[i]);
			ru[q[i]]++;
		}
		int li=1,ri=q[i];
		if(q[i]-k+1>1) li=q[i]-k+1;
		dbd=q[i];
		gai(1,li,ri);
	}
	dbd=n+1;
	built(1,1,n);
	for(int i=1;i<=n;i++)if(ru[i]==0)
	{
		dbd=i;
		gai(1,i,i);
	} 
	for(int i=1;i<=n;i++)
	{
		int bb=fir[f[1]],cc=f[1];
		while(bb!=0)
		{
			ru[sto[bb]]--;
			if(ru[sto[bb]]==0)
			{
				dbd=sto[bb];
				gai(1,dbd,dbd);
			}
			bb=nex[bb];
		}
		p[cc]=i;
		dbd=n+1;
		gai(1,cc,cc);
	}
	for(int i=1;i<=n;i++)printf("%d\n",p[i]);
}

Measured memory_bytes: 38272
#include <bits/stdc++.h>
using namespace std;
 #define MAX 1000000000005
 #define ll long long int
 int main()
 {    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

        long long int m,sum=0,k=0,i,d=MAX,j,sum1=0,sum2=0,sum3=0,l,kk,sum4=0,sum5=0,sum6=0,c=MAX,x,y,q;
         ll n;
           cin>>x>>n;
          ll a[n],b[1000]={0};
           for(i=0;i<n;i++)
             {cin>>a[i];
              b[a[i]]++;
             }
             for(i=x;i>=0;i--)
               {  if(b[i]==0)
                     {  c=i;
                         break;
                     }
               }
               for(i=x+1;i<=1000;i++)
               { if(b[i]==0)
                  { d=i;
                   break;
                  }
               }
               ll e=abs(c-x);
               ll f=abs(d-x);

                if(e<f)
                 cout<<c;
                else if(f<e)
                 cout<<d;
                 else
                    cout<<min(c,d)<<endl;
 }








Measured memory_bytes: 3652
#include<cstdio>
#include<algorithm>
#define MN 100001
using namespace std;

int read_p,read_ca;
inline int read(){
    read_p=0;read_ca=getchar();
    while(read_ca<'0'||read_ca>'9') read_ca=getchar();
    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();
    return read_p;
}
int n,m,i,j,dis[101][101],x[MN],y[MN],z[MN],mmh=0;
int main(){
	int i,j,k;
	n=read();m=read();
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++) dis[i][j]=1e9;
	for (i=1;i<=n;i++) dis[i][i]=0;
	for (i=1;i<=m;i++) x[i]=read(),y[i]=read(),z[i]=read(),dis[x[i]][y[i]]=z[i],dis[y[i]][x[i]]=z[i];
	for (k=1;k<=n;k++)
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
	if (i!=j&&i!=k&&j!=k&&dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];
	
	for (i=1;i<=m;i++) if (dis[x[i]][y[i]]<z[i]) mmh++;
	printf("%d\n",mmh);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main(){
    string s,t;
    char temp; //イントする！！
    cin >> s >> t;
    for(int i=0;i<s.size();i++){
        if(s!=t){
            temp = s[s.size()-1];
            
            s = temp +s.substr(0,s.size()-1);
           }
        if(s==t){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout <<"No"<< endl;
    
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = Integer.parseInt(scanner.next());
        int b = Integer.parseInt(scanner.next());
        scanner.close();

        System.out.println((int) Math.ceil((a + b) / 2.0));
    }
}


Measured memory_bytes: 22996
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

struct Edge {
    ll to;
    ll cost;
    Edge (ll t, ll c) {
        to = t;
        cost = c;
    }
};

struct Node {
    int cost;
    int gas;
    int from;
    Node (int c, int g, int f) {
        cost = c;
        gas = g;
        from = f;
    }
    bool operator < (const Node &a) const {
        return cost == a.cost ? gas < a.gas : cost > a.cost;
    }
};

ll N,M,L;
ll INF = 1e18;
ll dist[1010][1010];
ll lg[1010][1010];
int s[100010];
int t[100010];
vector < Edge > G[310];

void dijkstra (int start)
{
    // cost, left, idx
    priority_queue < Node > que;
    que.emplace(Node(0, L, start));

    while (!que.empty()) {
        ll cost = que.top().cost;
        ll gas = que.top().gas;
        ll from = que.top().from;
        que.pop();
        if (dist[start][from] > cost) {
            dist[start][from] = cost;
            lg[start][from] = gas;
        } else if (lg[start][from] < gas && dist[start][from] == cost) {
            lg[start][from] = gas;
        } else {
            continue;
        }
        REP(i,G[from].size()) {
            ll to = G[from][i].to;
            ll ct = G[from][i].cost;
            if (gas >= ct) {
                ll ng = gas - ct;
                ll nc = cost;
                ll ni = to;
                if (dist[start][ni] < nc) continue;
                if (dist[start][ni] == nc && lg[start][ni] >= ng) continue;
                que.emplace(Node(nc, ng, ni));
            } else {
                ll ng = L - ct;
                ll nc = cost + 1;
                ll ni = to;
                if (dist[start][ni] < nc) continue;
                if (dist[start][ni] == nc && lg[start][ni] >= ng) continue;
                que.emplace(Node(nc, ng, ni));
            }
        }
    }
}

int main ()
{
    cin >> N >> M >> L;
    REP(i,1010)REP(j,1010) {
        dist[i][j] = INF;
        lg[i][j] = 0;
    }

    REP(i,M) {
        int A,B,C;
        scanf("%d%d%d", &A, &B, &C);
        if (C > L) continue;
        G[A].push_back(Edge(B, C));
        G[B].push_back(Edge(A, C));
    }

    REP(i,N) {
        dijkstra(i + 1);
    }

    int Q; cin >> Q;
    REP(i,Q) {
        scanf("%d%d", s + i, t + i);
    }

    REP(i,Q) {
        ll dt = dist[s[i]][t[i]];
        if (dt == INF) {
            cout << -1 << endl;
        } else {
            cout << dt << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 19960
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;
int main(){
 	int N;
 	cin >> N;
 	ll a[3*N];

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

 	sort(a, a+3*N);

 	ll ans = 0;

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

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

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

using namespace std;

typedef long long ll;
const int N=200000;
int n,v[N+5];
ll s[N+5];

ll f2(ll x,ll y) {
    return max(x,y)-min(x,y);
}

ll f4(ll a,ll b,ll c,ll d) {
    return max(max(a,b),max(c,d))-min(min(a,b),min(c,d));
}

ll sum(int st,int dr) {
    return s[dr]-s[st-1];
}

int main() {
  ///  ios_base::sync_with_stdio(false);
  ///  cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>v[i];
        s[i]=s[i-1]+v[i];
    }
    ll ans=(1LL<<60);
   /** for(int p=1;p<=n;p++) {
        ll mi=(1LL<<60);
        for(int p1=1;p1<p;p1++)
            for(int p2=p+1;p2<n;p2++) {
                ll val=f4(sum(1,p1),sum(1,p)-sum(1,p1),sum(p2,n),sum(p+1,n)-sum(p2,n));mi=min(mi,val);
            }
        for(int p1=1;p1<p;p1++)
            for(int p2=p+1;p2<n;p2++) {
                ll val=f4(sum(1,p1),sum(1,p)-sum(1,p1),sum(p2,n),sum(p+1,n)-sum(p2,n));
                if(val==mi)
                    cout<<p<<" : "<<p1<<" , "<<p2<<" : "<<val<<"\n";
            }
    }**/
    int p1=0,p2=3;
    for(int p=2;p<=n-2;p++) {
        ll total1=sum(1,p);
        while(p1+1!=p && f2(sum(1,p1),total1-sum(1,p1))>=f2(sum(1,p1+1),total1-sum(1,p1+1)))
            p1++;
        ll total2=sum(p+1,n);
        while(p2!=n && f2(sum(p2,n),total2-sum(p2,n))>=f2(sum(p2+1,n),total2-sum(p2+1,n)))
            p2++;
        ans=min(ans,f4(sum(1,p1),total1-sum(1,p1),sum(p2,n),total2-sum(p2,n)));
       /// cout<<p<<" : "<<p1<<" , "<<p2<<" ---------- > "<<min(ans,f4(sum(1,p1),total1-sum(1,p1),sum(p2,n),total2-sum(p2,n)))<<"\n";
        /// cout<<"\n\n";
     ///   cout<<ans<<"\n";
    }
    cout<<ans<<"\n";
    return 0;
}
/**

**/


Measured memory_bytes: 2688
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

long long int f(long long int m, const vector<long long int>& v) {
    long long int c = 0;
    for (int i = 0; i < (int)v.size() - 1; i++) {
        if (v[i] * v[i + 1] > m) {
            c += 0;
        } else {
            int b = i + 1, e = (int)v.size() - 1;
            while (b < e) {
                int mm = (b + e) / 2 + 1;
                if (v[i] * v[mm] > m) {
                    e = mm - 1;
                } else {
                    b = mm;
                }
            }
            c += b - i;
        }
    }
    return c;
}


int main() { 
    long long int n, k;
    cin >> n >> k;
    vector<long long int> pos, neg, zero;
    for (int i = 0; i < n; i++) {
        long long int t;
        cin >> t;
        if (t > 0) {
            pos.push_back(t);
        } else if (t < 0) {
            neg.push_back(-t);
        } else {
            zero.push_back(t);
        }
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    long long int neg_count = (long long int)1 * neg.size() * pos.size();
    long long int neg_size = neg.size(), pos_size = pos.size(), zero_size = zero.size();
    long long int zero_count = zero_size * (pos_size + neg_size) + (zero_size - 1) * zero_size / 2;
    long long int b, e, m, c;
    if (k <= neg_count) {
        b = -1e18, e = -1;
        while (b < e) {
            m = (b + e) / 2 - 1;
            c = 0;
            for (auto neg_num : neg) {
                if (neg_num * pos.back() < -m) {
                    c += 0;
                } else {
                    int bb = 0, ee = pos.size() - 1;
                    while (bb < ee) {
                        int mm = (bb + ee) / 2;
                        if (neg_num * pos[mm] < -m) {
                            bb = mm + 1;
                        } else {
                            ee = mm;
                        }
                    }
                    c += pos.size() - bb;
                }
            }
            if (c >= k) {
                e = m;
            } else {
                b = m + 1;
            } 
        }
        cout << b << endl;
    } else if (k <= neg_count + zero_count) {
        cout << 0 << endl;
    } else {
        b = 1, e = 1e18;
        while (b < e) {
            m = (b + e) / 2;
            c = 0;
            c += f(m, pos);
            c += f(m, neg);
            if (c + neg_count + zero_count >= k) {
                e = m;
            } else {
                b = m + 1;
            }
        }
        cout << b << endl;
    }
}




Measured memory_bytes: 5416
import itertools

a_L = []

for i in range(5):
    a_L.append(int(input()))

def hosei(x):
    """int:x"""
    x = -(x // -10)
    return x*10

a_L = list(itertools.permutations(a_L))

ans_L = []

for c in a_L:
    times = 0
    counter = 0
    for i in c:
        if counter != 4:
            times += hosei(i)
        else:
            #print(aaa)
            times += i
        counter += 1
    ans_L.append(times)

print(min(ans_L))

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
const int INF = 1e9;
const long long LINF = 1e18;
const double EPS = 1e-8;
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); ++i)
#define rep(i,j) reps(i,0,j)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef vector<int> vi;
typedef pair<string, int> Psi;
typedef pair<ll, ll> Pll;
int main(){
	int a[3];
	rep(i,3){
		cin >> a[i];
	}
	sort(a,a+3);
	int prev = -1;
	int ans = 0;
	rep(i,3){
		if(prev != a[i]){
			prev = a[i];
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class TAskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int a = 0;
            out.println(a);
            out.flush();
            String sa = in.next();
            if (sa.equals("Vacant")) return;
            int b = n / 2;
            out.println(b);
            out.flush();
            String sb = in.next();
            if (sb.equals("Vacant")) return;
            if (((b - a) % 2 == 0) ^ (sa.equals(sb))) {
                // do nothing
            } else {
                a = b;
                b = n;
                String t = sa;
                sa = sb;
                sb = t;
            }
            while (true) {
                int c = (a + b) / 2;
                out.println(c);
                out.flush();
                String sc = in.next();
                if (sc.equals("Vacant")) return;
                if (((c - a) % 2 == 0) ^ (sa.equals(sc))) {
                    b = c;
                    sb = sc;
                } else {
                    a = c;
                    sa = sc;
                }
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}



Measured memory_bytes: 23716
use io::*;
use std::*;

const YES: &'static str = "Yes";
const NO: &'static str = "No";
fn solve(a: i64, b: i64, c: i64) {
    if c-a-b <= 0 {
        println!("{}",NO);
    }else {
        if (c-a-b)*(c-a-b) > 4 * a * b {
            println!("{}",YES);
        }else {
            println!("{}",NO);
        }
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
fn main() {
    let con = read_string();
    let mut scanner = Scanner::new(&con);
    let mut a: i64;
    a = scanner.next();
    let mut b: i64;
    b = scanner.next();
    let mut c: i64;
    c = scanner.next();
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(move || solve(a, b, c)).unwrap().join().unwrap();
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


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

int main() {
    int n,m;
    cin >> n >> m;
    vector<int> w,v;
    for(int i=0; i<n; i++){
        int a,b;
        cin >> a >> b;
        w.push_back(a);
        v.push_back(b);
    }
    long long dp[n+1][m+1];
    
    for(int i=0; i<n+1; i++){
        for(int j=0; j<m+1; j++){
            if(i==0||j==0){
                dp[i][j]=0;
            }else{
                if(j<w[i-1]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=max(v[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
                }
            }
        }
    }
    cout << dp[n][m] << endl;
    
}

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

int main(){
    int n; cin >> n;
    vector<int> l(n); rep(i,n) cin >> l[i];
    sort(l.begin(),l.end());
    int ans = 0;
    rep(i,n-2){
        for(int j = i+1; j < n-1; j++){
            int dist = (lower_bound(l.begin(), l.end(), l[i]+l[j])-l.begin())-j-1;
            if(dist > 0) ans += dist;
        }
    }
    cout << ans << endl;
}

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

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<ld, ld> pld;
typedef pair<string, string> pss;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define set_random                  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline ll input() {
    ll n;
    cin >> n;
    return n;
}

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

set_random;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7;
const ll MOD1 = 998244353;
const ll MOD2 = 1e9 + 7;
const ll MOD3 = 1e9 + 9;

ll n , ans , p[MAXN] , gcdl[MAXN] , gcdr[MAXN];

int main() {
    fast_io;

    cin >> n;
    for(ll i = 1 ; i <= n ; i++)    cin >> p[i];

    for(ll i = 1 ; i <= n ; i++)    gcdl[i] = __gcd(gcdl[i - 1] , p[i]);
    for(ll i = n ; i >= 1 ; i--)    gcdr[i] = __gcd(gcdr[i + 1] , p[i]);

    for(ll i = 1 ; i <= n ; i++)    ans = max(ans , __gcd(gcdl[i - 1] , gcdr[i + 1]));
    cout << ans << endl;

    return 0;
}
/*
todo :
    1- set constants
    2- check TimeLimit and MemoryLimit
    3- check special test cases
    4- don't forget BS can help you that is good idea(use for loop for floats)
    5- don't forget printf and scanf can help you in your code speed
*/


Measured memory_bytes: 9216
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        q: usize,
        v: [(usize, usize, usize); q]
    }
    let m = 1000003;
    let mut stair: Vec<usize> = vec![0; m];
    stair[0] = 1;
    for i in 1..m {
        stair[i] = stair[i - 1] * i % m;
    }
    let stair_i: Vec<usize> = stair.iter().map(|x| inv_m(*x, m)).collect();
    for (x, d, n) in v {
        if d == 0 {
            println!("{}", pow_m(x, n, m));
            continue;
        }
        let k = x * inv_m(d, m) % m;
        if k == 0 || k + n - 1 >= m {
            println!("0");
        } else {
            println!("{}", stair[k + n - 1] * stair_i[k - 1] % m * pow_m(d, n, m) % m);
        }
    }
}

fn pow_m(n: usize, mut p: usize, d: usize) -> usize {
    let mut r = n;
    let mut ret = 1;
    while p > 0 {
        if p % 2 == 0 {
            r = r * r % d;
            p /= 2;
        } else {
            ret = ret * r % d;
            p -= 1;
        }
    }
    ret
}

fn inv_m(n: usize, d: usize) -> usize {
    pow_m(n, d - 2, d)
}


Measured memory_bytes: 25468
#include <iostream>
#include <vector>

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

int main() {
  int N;
  int W;
  std::cin >> N >> W;

  std::vector<int> w(N);
  std::vector<long long> v(N);
  for (int i = 0; i < N; ++i)
    std::cin >> w[i] >> v[i];

  // dp[i][j] = i 個までで重さ j 以下の場合の価値の最大値
  std::vector<std::vector<long long>> dp(
      N + 7, std::vector<long long>(2 * W + 7, 0LL));

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= W; ++j) {
      chmax(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
      chmax(dp[i + 1][j], dp[i][j]);
    }
  }

  std::cout << dp[N][W] << std::endl;
}


Measured memory_bytes: 169088
out = []

def plus(i,j,k):
    out.append(' '.join(['+',str(i),str(j),str(k)]))

def comp(i,j,k):
    out.append(' '.join(['<',str(i),str(j),str(k)]))

comp(2,0,100)
comp(2,1,99)
plus(99,100,100)
comp(500,100,100)
for i in range(62):
    plus(100 + i, 100 + i, 101 + i)


#Convert A to Binary
    
#Reference 297
#Have so far 298
#Test 299
plus(0, 100, 297)
for i in range(30, -1, -1):
    plus(298, 100 + i, 299)
    comp(299, 297, 300 + i)
    plus(5000, 300 + i, 296)
    for _ in range(i):
        plus(296, 296, 296)
    plus(296, 298, 298)


#Convert B to Binary
plus(1, 100, 397)
for i in range(30, -1, -1):
    plus(398, 100 + i, 399)
    comp(399, 397, 400 + i)
    plus(5000, 400 + i, 396)
    for _ in range(i):
        plus(396, 396, 396)
    plus(396, 398, 398)

for i in range(31):
    for j in range(31):
        plus(300 + i, 400 + j, 500)
        comp(100, 500, 501)
        for _ in range(i + j):
            plus(501,501,501)
        plus(501, 2, 2)

print(len(out))
print('\n'.join(out))


Measured memory_bytes: 71124
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(K: int, X: int):
    ans = [i for i in range(max(-1000000, X-K+1),min(1000000, X+K))]

    print(' '.join(map(str, ans)))
    return



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

if __name__ == '__main__':
    main()


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

int Mygcd(int x, int y);

int main()
{
	int a, b, temp;
	cin >> a >> b;
	if (a < b) {
		temp = b;
		b = a;
		a = temp;
	}
	cout << Mygcd(a, b) << "\n";
	return 0;
}

int Mygcd(int x, int y)
{
	if (y == 0) return x;
	else return Mygcd(y, x%y);
}

Measured memory_bytes: 1168
s = list(input())
if s[0] == '?':
    s[0] = 'D'
if s[-1] == '?':
    s[-1] = 'D'
    
for i in range(1, len(s)):
    if s[i] == '?':
        if s[i-1] == 'P':
            s[i] = 'D'
        elif s[i-1] == 'D':
            if s[i+1] == 'P':
                s[i] = 'D'
            else:
                s[i] = 'P'
            
print(''.join(s))

Measured memory_bytes: 73888