akhauriyash/Code-Regression huggingface dataset:
from bisect import bisect_left, bisect_right, insort_left
from typing import Dict, List


if __name__ == "__main__":
    num_query = int(input())
    d: Dict[str, List[int]] = {}
    keys: List[str] = []

    for _ in range(num_query):
        op, *v = input().split()
        if ("0" == op):
            if v[0] not in d:
                insort_left(keys, v[0])
                d[v[0]] = []
            d[v[0]].append(int(v[1]))
        elif ("1" == op):
            if v[0] in d:
                for elem in d[v[0]]:
                    print(elem)
        elif ("2" == op):
            if v[0] in d:
                d[v[0]] = []
        else:
            left_key = bisect_left(keys, v[0])
            right_key = bisect_right(keys, v[1], left_key)
            for k in range(left_key, right_key):
                for elem in d[keys[k]]:
                    print(keys[k], elem)



Measured memory_bytes: 41172
#include <iostream>
#include <cmath>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
  int n, a, b, p1, p2;
  cin >> n >> a >> b;
  p1 = a * n;
  p2 = b;
  cout << min(p1, p2) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

#define MEALP 800 // meal price in yen
#define PAIDA 200 // amount given back per 15 meals

int main()
{
    int N;
    long total_given, paid_back;
    scanf("%d", &N);
    total_given = MEALP * N;
    paid_back   = N/15 * PAIDA;
    total_given -= paid_back;
    printf("%ld\n", total_given);
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  vector<int> cnt(N, 0);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    cnt[a]++, cnt[b]++;
  }
  for (int i = 0; i < N; i++) {
    if (cnt[i] % 2 == 1) {
      cout << "NO" << '\n';
      return 0;
    }
  }
  cout << "YES" << '\n';
  return 0;
}


Measured memory_bytes: 640
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

bool query(long long num) {
    cout << "? " << num << endl;
    
    string s; cin >> s;
    return s[0] == 'Y';
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    if (!query(1000000000000000000LL)) {
        for (long long i = 1; ; i *= 10) {
            if (!query(i)) {
                long long st = i/10, ed = i-1;
                while (st < ed) {
                    long long md = (st+ed)/2;
                    if (query(md*10)) ed = md;
                    else st = md+1;
                }

                cout << "! " << st << endl;
                return 0;
            }
        }
    }

    else {
        for (long long i = 9; ; i *= 10) {
            if (query(i)) {
                cout << "! " << i/9 << endl;
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 624
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws FileNotFoundException {

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);

    int n = cin.nextInt();
    long[] a = new long[n];
    for (int i=0;i<n;i++) {
      long in = cin.nextLong();
      if (in%2==1) {
        System.out.println("first");
        return;
      }
    }

    System.out.println("second");

  }

}

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

using namespace std;

int main() {
		int N, M;
		cin >> N >> M;
		vector<int> sw(N);
		for (int i = 0; i < M; i++) {
				int K;
				cin >> K;
				for (int j = 0; j < K; j++) {
						int s;
						cin >> s;
						s--;
						sw[s] |= 1<<i;
				}
		}

		int p = 0;
		for (int i = 0; i < M; i++) {
				int x;
				cin >> x;
				p |= x<<i;
		}

		int ans = 0;
		for (int s = 0; s < (1<<N); s++) {
				int t = 0;
				for (int i = 0; i < N; i++) {
						if (s>>i & 1) t ^= sw[i];
				}
				if (t == p) ans++;
		}

		cout << ans << endl;

		return 0;
}


Measured memory_bytes: 384
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))

def prime_factorize(num):
	x = 1
	fcts = []
	while x * x <= num:
	    if num % x == 0:
	        fcts.append(x)
	        fcts.append(num // x)
	    x += 1
	fcts.sort(reverse = True)
	return fcts

def num_operation(l):
	# lでAの要素を割り切るために必要な操作の回数
	nums_div1 = sorted([x % l for x in nums])
	nums_div2 = [(l - x) % l for x in nums_div1]
	min_op = 10 ** 10

	lf = 0
	rg = sum(nums_div2)
	if rg % l == 0:
		min_op = rg

	for i in range(n):
		lf += nums_div1[i]
		rg -= nums_div2[i]
		if (lf - rg) % l == 0:
			min_op = min(min_op, max(lf, rg))
	return min_op

sum_nums = sum(nums)
fcts = prime_factorize(sum_nums)

for fct in fcts:
	if num_operation(fct) <= k:
		print(fct)
		break


Measured memory_bytes: 3064
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

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

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


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    que = queue.Queue()
    que.put((0, -1))

    while que.qsize() > 0:
        node, used_color = que.get()
        current_color = 0 if used_color != 0 else 1
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            edge_dic[(ai, bi)] = current_color
            que.put((k, current_color))
            current_color = current_color + 1 if used_color != current_color + 1 else current_color + 2

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


if __name__ == '__main__':
    main()


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) {
    int x;
    cin >> x;
    a[x-1]++;
  }
  sort(a.begin(),a.end());
  vector<int> s(n+1); // sum of [0,i)
  rep(i,n) s[i+1] = s[i]+a[i];
  int ans = n;
  for (int k = 1; k <= n; ++k) {
    while (1) {
      bool ok = [&](int c) {
        int i = lower_bound(a.begin(), a.end(), c) - a.begin();
        int sum = c*(n-i) + s[i];
        return (sum >= c*k);
      }(ans);
      if (ok) break;
      --ans;
    }
    printf("%d\n", ans);
  }
  return 0;
}

Measured memory_bytes: 3200
#include<stdio.h>

int main(){
  int x,y,a;

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

Measured memory_bytes: 592
#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define all(x) (x).begin(),(x).end()

int main() {
    int h,w;
    cin >> h >> w;
    vector<string> a(h);
    vector<bool> disw(w,false);

    for (int i=0; i<h; i++) cin >> a[i];
    for (int i=h-1; i>=0; i--) {
        if (all_of(all(a[i]), [](char& c){return c=='.';})) {
            a.erase(a.begin()+i);
        }
    }

    h = a.size();

    for (int i=0; i<w; i++) {
        bool f = true;
        for (int j=0; j<h; j++) {
            if (a[j][i] == '#') f = false;
        }
        disw[i] = f;
    }

    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            if (!disw[j])
                cout << a[i][j];
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(a, b) << " " << max(a+b-n, 0) << endl;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

int main()
{
    ll n, k;
    cin >> n >> k;
    map<ll, ll> m; 
    rep(i, n) {
        ll a, b;
        cin >> a >> b;
        m[a] += b;
    }

    ll cnt = 0;
    int ans = 0;
    for(auto x : m) {
        cnt += x.second;
        if(cnt >= k) {
            ans = x.first;
            break;
        } 
    }

    cout << ans << endl;

    return 0;
}


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

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

using namespace std;


int main()
{

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

	int b=0;
	int c=N;
	do{
		
		int a=c%10;
		b=b+a;
		c=c/10;
	}while(c>0);
	
	if(N%b==0) printf("Yes\n");
	else{printf("No\n");}
	
	
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<string>
#include<iomanip>
#include<set>
#include<algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<pair<int,int> > ab(n);
	for(int i=0;i<n;i++)
	{
		int a,b;
		cin >> a >> b;
		ab[i]=make_pair(b,a);
	}
	sort(ab.begin(),ab.end());

	bool flag=true;
	long long count=0;
	for(int i=0;i<n;i++)
	{
		count+=ab[i].second;
		if(count>ab[i].first)
			flag=false;
	}

	cout << (flag ? "Yes" : "No") << endl;






}

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) for(int i = 0 ; i < n ; ++i)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int main(){
    int n;
    while(cin >> n, n){
        vector< P > train(n);
        rep(i, n){
            int h, m, s;
            scanf("%d:%d:%d", &h, &m, &s);
            train[i].first = h * 10000 + m * 100 + s;
            scanf("%d:%d:%d", &h, &m, &s);
            train[i].second = h * 10000 + m * 100 + s;
        }
        SORT(train);
        vector<bool> done(n);
        int ans = 0;
        rep(i, n){
            if(!done[i]){
                ++ans;
                done[i] = true;
                int tmp = train[i].second;
                REP(j, i + 1, n){
                    if(tmp <= train[j].first && !done[j]){
                        done[j] = true;
                        tmp = train[j].second;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3196
import java.util.Scanner;

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

        long A = sc.nextLong();
        long B = sc.nextLong();
        long K = sc.nextLong();

        if (A >= K)
            System.out.println((A - K) + " " + B);
        else if (A + B >= K)
            System.out.println(0 + " " + (B - (K - A)));
        else
            System.out.println(0 + " " + 0);
    }

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1;} return 0;}
struct init{init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}}init_;

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
struct UnionFind {
private:
    vector<int> par;
    vector<int> count;
    vector<int> rank;
public:
    UnionFind(int N) {
        count.assign(N, 1);
        rank.assign(N, 0);
        par.assign(N, 0);
        rep(i, N) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x)
            return x;
        else {
            par[x] = root(par[x]);
            return par[x];
        }
    }

    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return;
        if (rank[x] < rank[y])
            swap(x, y);
        else if (rank[x] == rank[y])
            rank[y]++;
        par[y] = x;
        count[x] += count[y];
        return;
    }

    int size(int x) {
        return count[root(x)];
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }
};
using UF = struct UnionFind;

int main() {
    ll N, M;
    cin >> N >> M;
    UF uf(N);
    
    rep(i, M) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        uf.unite(a, b);
    }

    ll ans = 0;
    rep(i, N) chmax(ans, (ll)uf.size(i));

    cout << ans << endl;
}

Measured memory_bytes: 5716
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
	int N; 
	cin >> N; 
	int T[110] = {}; 
	int V[110] = {}; 
	int S[110] = {}; 
	for(int i = 1; i <= N; i++){
		cin >> T[i];
		S[i] = S[i-1] + T[i] * 2; 
	}
	for(int i = 1; i <= N; i++){
		cin >> V[i]; 
	}
	int A[40010] = {}; // N+1個の関数の最小値を各点について考える．0.5の整数倍で切り替わることがあるので，あらかじめVもTも2倍しておいて，あとで積分値を4で割る．
	for(int t = 0; t <= S[N]; t++){
		A[t] = min(t, S[N] - t); 
	}
	for(int i = 1; i <= N; i++){
		for(int t = 0; t <= S[N]; t++){
			if(t < S[i-1]){A[t] = min(A[t], V[i] * 2 - t + S[i-1]);}
			else if(t >= S[i-1] && t <= S[i]){A[t] = min(A[t], V[i] * 2);}		
			else if(t > S[i]){A[t] = min(A[t], V[i] * 2 + t - S[i]);}
		}
	}
	int ans = 0; 
	for(int i = 1; i < S[N]; i++){
		ans += A[i]; 
	}
	cout.precision(10); 
	cout << (double) ans * 0.25 << endl; 
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;


vector<string> split(const string &s, char delim) {
    vector<string> elems;
    string item;
    for (char ch: s) {
        if (ch == delim) {
            if (!item.empty())
                elems.push_back(item);
            item.clear();
        }
        else {
            item += ch;
        }
    }
    if (!item.empty())
        elems.push_back(item);
    return elems;
}

bool compare_by_b(tuple<int, string, int> a, tuple<int, string, int> b) {
    if(get<2>(a) != get<2>(b)){
        return get<2>(a) > get<2>(b);
    }
}

bool compare_by_string(tuple<int, string, int> a, tuple<int, string, int> b) {
    if(get<1>(a) != get<1>(b)){
        return get<1>(a) < get<1>(b);
    }else{
      	return get<2>(a) > get<2>(b);
    }
}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
  	cin >> n;
  	list<long> S;
  	int idx=0;
  	long s;
  	while(cin >> s)
    {
      S.push_back(s);
      idx++;
      if(idx == n) break;
    }
  	int q;
  	cin >> q;
  	vector<long> T(q);
  	idx=0;
  	while(cin >> T[idx])
    {
      idx++;
      if(idx == q) break;
    }
  	
  	int count = 0;
  	for(int i=0;i<q;i++)
    {
		for(auto itr = S.begin(); itr != S.end(); ++itr) {
        	if( *itr == T[i] ) 
            {
              count++;
              S.erase(itr);
              break;
            }
        }
    }
  	cout << count << endl;
  	return 0;
}



Measured memory_bytes: 3376
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {

	long long int sz, prv=0, cont=0, ans=0;
	string s;
	vector<long long int> v;

	cin >> s;
	sz = s.size();

	for (int i = 0;i < sz;i++) {
		if (s[i] == '>') {
			if (prv == -1) {
				cont++;
			}
			else if (prv == 1) {
				v.emplace_back(cont);
				cont = 1;
				prv = -1;
			}
			else {
				cont++;
				prv = -1;
			}
		}
		else if (s[i] == '<') {

			if (prv == -1) {
				v.emplace_back(cont);
				cont = 1;
				prv = 1;
			}
			else if (prv == 1) {
				cont++;
			}
			else {
				cont++;
				prv = 1;
			}
		}
		//cout << prv << endl;
	}

	v.emplace_back(cont);

	if (s[0] == '<') {
		for (int i = 0;i < v.size();i++) {
			ans += v[i] * (v[i] + 1) / 2;
			if (i % 2 == 1) {
				ans -= min(v[i], v[i - 1]);
			}
		}
	}
	else {
		for (int i = 0;i < v.size();i++) {
			ans += v[i] * (v[i] + 1) / 2;
			if (i % 2 == 0 && i>1) {
				ans -= min(v[i], v[i - 1]);
			}
		}

	}
	//for (int i = 0;i<v.size();i++) cout << v[i] << " d" << endl;

	cout << ans << endl;


}


Measured memory_bytes: 3068
#include <stdio.h>
int main() {
    int RB[6]={0,0,0,0,0,0},i,N,j,T[5]={1650,1700,1750,1800,1850};while (scanf("%d",&N)!=EOF) {
    while (N--) {scanf("%d.%d",&i,&j);i=i*10+j;if (i<T[0]) RB[0]++; else if (i>=T[4]) RB[5]++; else {for (j=1;j<5;j++) if (T[j-1]<=i && T[j]>i) RB[j]++;}}
    for (i=0;i<6;i++) {printf("%d:",i+1);while (RB[i]) RB[i]--,putchar('*');puts("");}} return 0;}

Measured memory_bytes: 1044
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main () {
    ios_base::sync_with_stdio(false);
    int K;
    cin>>K;
    queue<ll> q;
    for(ll i=1;i<10;i++) {
        q.push(i);
    }
    ll x;
    for(int k=0;k<K;k++) {
        x = q.front();
        q.pop();
        if(x%10 > 0) {
            q.push(10*x+x%10-1);
        }
        q.push(10*x+x%10);
        if(x%10 < 9) {
            q.push(10*x+x%10+1);
        }
    }
    cout<<x<<"\n";
    return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define LEN(x) (int)x.size()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;

signed main()
{
  i64 a, b; cin >> a >> b;
  if (a <= 0 && 0 <= b) {
    puts("Zero");
  } else if (a < 0 && b < 0 && (abs(b-a)+1) % 2 == 1) {
    puts("Negative");
  } else {
    puts("Positive");
  }

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if (b >= a*c) {
    cout << c << endl;
  } else if (b < a) {
    cout << 0 << endl;
  } else {
    cout << b/a << endl;
  }
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append(i+(l-1)*10**6+(r-1)*10**12)

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort()
last = [None]*n
ans = [None]*q
nr = -1
for i in query:
    r = i//10**12
    l = i%10**12//10**6
    idx = i%10**6
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
print(*ans)

Measured memory_bytes: 172832
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
// const int MOD = 1e9 + 7;

int main() {
    long long N;
    cin >> N;
    vector<long long> A(100);
    A[0] = 2;
    A[1] = 1;
    for (int i = 2; i < 100; i++) {
        A[i] = A[i - 1] + A[i - 2];
    }
    cout << A[N];
}


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

#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

int gcd(int a, int b) {
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}
//#define MULTIPLE_TEST_CASE
void solution() {
  int n, k;
  cin >> n >> k;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  while (k--) {
    bool nada = 1;
    for (int i = 0; i < n; i++)
      if (a[i] != n) nada = 0;
    if (nada) break;
    vector<int> v(n + 1, 0);
    for (int i = 0; i < n; i++) {
      int l = max(0, i - a[i]);
      int r = min(n - 1, i + a[i]);
      v[l]++;
      v[r + 1]--;
    }
    for (int i = 1; i <= n; i++) v[i] += v[i - 1];
    for (int i = 0; i < n; i++) a[i] = v[i];
  }
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  cout << endl;
}

int32_t main() {
  DESYNC;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int t = 1;
#ifdef MULTIPLE_TEST_CASE
  cin >> t;
#endif
  while (t--) solution();
}


Measured memory_bytes: 5184
import java.util.*;
import static java.lang.Math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		ArrayList<Integer> res = new ArrayList<Integer>();
		int k;
		for (k = 40; k >= 0; k--) {
			if (n >= (1L << k) - 1) break;
		}
		for (int i = 1; i <= k; i++) res.add(i);
		n -= (1L << k) - 1;
		for (int i = k - 1; i >= 0; i--) {
			if (n < (1L << i)) continue;
			k++;
			res.add(i, k);
			n -= 1L << i;
		}
		System.out.println(2 * res.size());
		for (int x : res) System.out.print(x + " ");
		for (int i = 1; i <= res.size(); i++) System.out.print(i + " ");
		System.out.println();
	}
}



Measured memory_bytes: 23764
# https://atcoder.jp/contests/agc021/tasks/agc021_a

import itertools
import collections
import bisect

def main():
    N = list(map(int, input()))
    if N[1:].count(9) == len(N) - 1:
        print(sum(N))
    else:
        print(N[0] - 1 + (len(N) - 1) * 9)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> D(N);
  for (int i = 0; i < N; i++) cin >> D[i];
  int M;
  cin >> M;
  vector<int> T(M);
  for (int i = 0; i < M; i++) cin >> T[i];

  map<int, int> d, t;
  for (int i = 0; i < N; i++) d[D[i]]++;
  for (int i = 0; i < M; i++) t[T[i]]++;

  bool flag = true;
  for (auto i : t) if (i.second > d[i.first]) flag = false;

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

Measured memory_bytes: 20608
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(){
    int a,b;
    cin>>a>>b;
    string game;
    game=game+to_string(a);
    game=game+to_string(b);
    int num=stoi(game);
    int n=sqrt(num); 
    if(n*n==num)cout<<"Yes";
    else cout<<"No";
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int a,b,c,d,e=0;
scanf ("%d%d%d%d",&a,&b,&c,&d);
if (a>b){
e=e+b;
}
 else{
 e=e+a;
 }
if(c>d){
e=e+d;
}
  else{
  e=e+c;
  }
 printf ("%d",e);
return 0;
}

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

typedef long long ll;
vector<ll> A;

int main(void) {
	int N;
	const double INF_DB = 2.0e+18;
	const ll INF_LL = (ll)(1e+18);

	cin >> N;
	A.resize(N);
	bool z_flag = false;
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
		if (A[i] == 0)
			z_flag = true;
	}

	if (z_flag) {
		cout << "0\n";
		return 0;
	}

	ll mul_ll = 1;
	double mul_db = 1.0;
	for (int i = 0; i < N; ++i) {
		mul_db *= (double)A[i];
		if (mul_db >= INF_DB) {
			mul_ll = -1;
			break;
		}
		mul_ll *= A[i];
		if (mul_ll > INF_LL) {
			mul_ll = -1;
			break;
		}
	}
	cout << mul_ll << '\n';
	return 0;
}


Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int N;
    cin >> N;
    long long int a[N],ans[N],tmpp=1e9;
    pair<long long int,long long int> tmp[N];
    map<long long int,long long int> m;
    
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        ans[i] = 0;
        tmp[i] = make_pair(a[i],i);
        m[a[i]]++;
    }
    sort(tmp,tmp+N);
    for(int i = N-1; i >= 0; i--) {
        tmpp = min(tmp[i].second,tmpp);
        if(i == 0) {
            ans[tmpp] += tmp[i].first * N;
        }else {
            ans[tmpp] += (tmp[i].first - tmp[i-1].first) * (N-i);
        }
    }
    for(int i = 0; i < N; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 10496
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

int main() {
  int n, k;
  string s;
  cin >> n >> k >> s;
  --k;
  s[k] = s[k] + 32;
  cout << s <<  endl;
}


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

int main() {
    int N; cin >> N;
    int C[10][10] = {0};

    for (int i = 1; i <= N; i++) {
        int a = i % 10;
        int b = i / pow(10, (int)log10(i));
        C[b][a]++;
    }
    ll sum = 0;
    rep(i,10) rep(j,10) sum += C[i][j] * C[j][i];
    cout << sum << endl;
}


Measured memory_bytes: 4000
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    if (A >= 13) {
        cout << B << endl;
    } else if (A >= 6) {
        cout << B / 2 << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=10100100100100100;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
mint choose(int n,int a){
    mint denominator=1,numerator=1;
    for(int i=0; i<a; i++){
        denominator*=i+1;
        numerator*=n-i;
    }
    return numerator/denominator;
}
int main(){
    int n,a,b;cin >> n >> a >> b;
    mint ans=mint(2).pow(n);
    ans-=1;
    ans-=choose(n,a);
    ans-=choose(n,b);
    cout << ans.x << endl;
}

Measured memory_bytes: 256
#![allow(unused_mut)]
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(unused_imports)]
#![allow(dead_code)]
use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
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)*}
    };
}
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, 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!{
        N: usize,
        h: [isize; N],
    }
    let mut dp = vec![0; N+1];
    dp[0] = 0;
    for i in 1..N {
        if i == 1 {
            dp[i] = dp[i-1] + (h[i-1]-h[i]).abs();
        } else {
            dp[i] = min(dp[i-1] + (h[i-1]-h[i]).abs(), dp[i-2] + (h[i-2]-h[i]).abs());
        }
    }
    println!("{:?}", dp[N-1]);
}



Measured memory_bytes: 6396
#include <bits/stdc++.h>
 
using namespace std;
 
#define f0r(a, b) for (long long a = 0; a < (b); a++)
#define f1r(a, b, c) for (long long a = (b); a < (c); a++)
#define f0rd(a, b) for (long long a = (b); a >= 0; a--)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define mp make_pair
#define f first
#define s second
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
 
void fio() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 

 
const long double pi = 3.14159265358979323846;

using lld = long double;

vl edges[200005];
bool vis[200005];
ll par[200005];

void solve() {
  ll n, m; cin >> n >> m;
  f0r(i, m) {
    ll x, y; cin >> x >> y;
    edges[--x].pb(--y);
    edges[y].pb(x);
  }

  ms(vis, 0);
  
  queue<pll> q;
  q.push(mp(0, -1));
  while (!q.empty()) {
    pll x = q.front();
    
    q.pop();

    if (vis[x.f]) continue;
    vis[x.f] = 1;
    par[x.f] = x.s + 1;

    for (ll y: edges[x.f]) {
      if (!vis[y]) {
        q.push(mp(y, x.f));
      }
    }
  }

  cout << "Yes\n";
  f1r(i, 1, n) cout << par[i] << '\n';
}
 
int main() {
  fio();
  
  int T = 1;
  // cin >> T;
  while (T--) solve();
} 

Measured memory_bytes: 16788
import java.util.Scanner;
import java.util.Arrays;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int[] a = new int[3];
    
    for(int i = 0; i < 3; i++){
      a[i] = scan.nextInt();
    }
    
    Arrays.sort(a);
    
    if((a[0] + a[1]) == a[2]){
      System.out.println("Yes");
    }
    else{
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 21972
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;
typedef long long ll;
const int MAXN = 305;
struct { int v, next; ll w; } e[MAXN * MAXN];
int head[MAXN], cnt_edge;
inline void add_edge(int u, int v, ll w) {
    e[cnt_edge] = { v, head[u], w };
    head[u] = cnt_edge++;
}
int n;
struct Item {
    ll val;
    int u, v;
    bool operator > (const Item &item) const {
        return val > item.val;
    }
};
ll dis[MAXN];
bool inque[MAXN];
void spfa(int s) {
    queue<int> que;
    dis[s] = 0;
    inque[s] = true;
    que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        inque[u] = false;
        for(int i = head[u]; i != -1; i = e[i].next) {
            if(dis[e[i].v] > dis[u] + e[i].w) {
                dis[e[i].v] = dis[u] + e[i].w;
                if(!inque[e[i].v]) {
                    inque[e[i].v] = true;
                    que.push(e[i].v);
                }
            }
        }
    }
}
priority_queue<Item, vector<Item>, greater<Item>> que;
int main() {
    memset(head, 0xff, sizeof(head));
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
        ll val; scanf("%lld", &val);
        if(i < j) {
            que.push((Item){val, i, j});
        }
    }
    ll ans = 0;
    while(!que.empty()) {
        Item item = que.top(); que.pop();
        for(int i = 1; i <= n; i++) dis[i] = 2e9;
        spfa(item.u);
        if(dis[item.v] < item.val) {
            printf("-1\n");
            return 0;
        }
        else if(dis[item.v] > item.val) {
            add_edge(item.u, item.v, item.val);
            add_edge(item.v, item.u, item.val);
            ans += item.val;
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL -1
using namespace std;
const int64_t MOD = 1e9 + 7;

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

	vector<int64_t> v(n);
	for (int64_t i = 0; i < n; i++) {
		cin >> v.at(i);
	}

	int64_t a, b;
	a = 0;
	b = 0;

	int64_t sum = 0;
	for (int64_t i = 0; i < n; i++) { //plus first
		if (!i) {
			if (v.at(i) >= 0) {
				if (!v.at(0)) {
					a++;
					sum = 1;
				}
				else {
					sum = v.at(i);
				}
			}
			else {
				sum = 1;
				a += abs(v.at(i)) + 1;
			}
		}
		else {
			int64_t n = sum + v.at(i);
			//cout << "n:" << n << endl;

			if (i % 2) {
				if (n > 0) {
					a += abs(n) + 1;
					sum = -1;
				}
				else {
					if (!n) {
						a++;
						sum = -1;
					} else {
						sum = n;
					}
				}
			}
			else {
				if (n < 0) {
					a += abs(n) + 1;
					sum = 1;
				}
				else {
					if (!n) {
						a++;
						sum = 1;
					}
					else {
						sum = n;
					}
				}
			}
		}
	}

	for (int64_t i = 0; i < n; i++) { //minus first
		if (!i) {
			if (v.at(i) <= 0) {
				if (!v.at(0)) {
					b++;
					sum = -1;
				}
				else {
					sum = v.at(i);
				}
			}
			else {
				sum = -1;
				b += abs(v.at(i)) + 1;
			}
		}
		else {
			int64_t n = sum + v.at(i);

			if (i % 2) {
				if (n < 0) {
					b += abs(n) + 1;
					sum = 1;
				}
				else {
					if (!n) {
						b++;
						sum = 1;
					}
					else {
						sum = n;
					}
				}
			}
			else {
				int64_t n = sum + v.at(i);
				if (n > 0) {
					b += abs(n) + 1;
					sum = -1;
				}
				else {
					if (!n) {
						b++;
						sum = -1;
					}
					else {
						sum = n;
					}
				}
			}
		}
	}

	//cout << "a:" << a << endl;
	//cout << "b:" << b << endl;

	cout << min(a, b) << endl;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

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

	ll n, k;
	cin >> n >> k;

	vl a(n);
	FOR(i,0,n) cin >> a[i];
	
	ll xmin = 0, xmax = 1e9;
	while (xmax-xmin > 1) {
		ll x = (xmin+xmax)/2;

		ll need = 0;
		FOR(i,0,n) {
			need += (a[i]-1)/x;
		}
		
		if (need <= k) xmax = x;
		else xmin = x;
	}
	cout << xmax << endl;
}



Measured memory_bytes: 4680
N = int(input())
A = [int(_) for _ in input().split()]
C = [0 for i in range(N + 1)]

for a in A:
    C[a] += 1

sum_comb = sum([c * (c-1) // 2 for c in C])
for a in A:
    print(sum_comb - (C[a] - 1))


Measured memory_bytes: 25768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int n,k;cin>>n>>k;
	string s;cin>>s;
	vector<int>ans;
	for(int i=s.size()-1;i>0;i--){
		int low=i;
		for(int j=i;j>=max(0,i-k);j--){
			if(s[j]=='0'){
				low=j;
			}
		}
		if(low==i){
			cout<<-1<<endl;
			return 0;
		}else{
			ans.push_back(i-low);
			i=low+1;
		}
	}
	reverse(ans.begin(),ans.end());
	for(auto u:ans){
		cout<<u<<' ';
	}cout<<endl;
	return 0;
}

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

int main(){
	string s,t;
	cin >> s >> t;
	int sum = 0;
	for(int i=0;i<3;i++){
		if(s[i] == t[i]) sum++;
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
import math
import collections
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
N, M = map(int, input().split())
prime = primes(10**5)
m = math.sqrt(M)
dic = collections.defaultdict(int)
mod = 10**9 + 7
for p in prime:
    if p <= m:
        while M % p == 0:
            dic[p] += 1
            M = M//p
if M > 1:
    dic[M] += 1
def comb(n, k):
    ans = 1
    for i in range(1, k+1):
        ans = ans*(n+1-i)//i
    return ans
ans = 1
for i in dic.values():
    ans *= comb(N+i-1, i)
    ans %= mod
print(ans)

Measured memory_bytes: 7284
#include <stdio.h>

int main(){
  int N,i,ANS;
  ANS=0;
  scanf("%d", &N);
  int A[N];
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  for(i=0;i<N;i++){
    ANS=ANS+A[i]-1;
  }
  printf("%d",ANS);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#define llint long long
#define inf 1e9

using namespace std;

string s;
int succ[200005][26];
int dp[200005];
int nx[26];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	int n = s.size();
	s = "#" + s;
	
	for(int i = 0; i < 26; i++) nx[i] = n+1; 
	for(int i = n; i >= 1; i--){
		for(int j = 0; j < 26; j++) succ[i][j] = nx[j];
		nx[s[i]-'a'] = i;
	}
	for(int i = 0; i < 26; i++) succ[0][i] = nx[i];
	
	for(int i = 0; i <= n+1; i++) dp[i] = inf;
	dp[n+1] = 0;
	
	for(int i = n; i >= 0; i--){
		for(int j = 0; j < 26; j++){
			dp[i] = min(dp[i], dp[succ[i][j]]+1);
		}
	}
	
	int p = 0; string ans;
	while(p < n+1){
		for(int j = 0; j < 26; j++){
			if(dp[p] == dp[succ[p][j]]+1){
				p = succ[p][j];
				ans += j+'a';
				break;
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 21712
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> void read(T &x){
	int f=0; x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	if(f) x=-x;
}



int main(){
	int x;

	cin>>x;
	cout<<360/__gcd(360,x)<<endl;

	return 0;
}

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

int main(){
  int n,ans=0;cin>>n;
  for(int i=1;i<=n;++i){
    int cnt=0;
    for(int j=1;j<=i;++j){
      if(j%2==0) continue;
      if (i%j==0) ++cnt;
    }
    if(cnt==8) ++ans;
  }
  cout<<ans<<endl;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N, Q; cin >> N >> Q;
  vector<vector<int>> G(N);
  rep(i, N-1) {
    int a, b; cin >> a >> b; a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<ll> val(N);
  rep(i, Q) {
    int p, x; cin >> p >> x; p--;
    val[p] += x;
  }
  auto dfs = [&](auto dfs, int u, int p) -> void {
    for (int v : G[u]) if (v != p) {
      val[v] += val[u];
      dfs(dfs, v, u);
    }
  };
  dfs(dfs, 0, -1);
  rep(i, N) cout << val[i] << (i == N - 1 ? '\n' : ' ');
}


Measured memory_bytes: 21888
#include <iostream>

using namespace std;

int main() {
  int k, s;
  cin >> k >> s;
  
  int ans0 = 0;
  int ans1 = 0;
  int ans2 = 0;
  int ans3 = 0;
  int ans4 = 0;
  int ans5 = 0;
  int ans6 = 0;
  int ans7 = 0;
 
  for (int x = 0; x <= k; x++) {
    int y = 0;
    for (; y <= k - 1; y += 2) {
      int z = 0;
      for (; z <= k - 3; z += 4) {
        ans0 += x+y+z == s-0; 
        ans1 += x+y+z == s-1; 
        ans2 += x+y+z == s-2; 
        ans3 += x+y+z == s-3; 
        ans4 += x+y+z == s-1; 
        ans5 += x+y+z == s-2; 
        ans6 += x+y+z == s-3; 
        ans7 += x+y+z == s-4; 
      }

      for (; z <= k; z++) {
        ans0 += x+y+z == s;
        ans1 += x+y+z == s-1;
      }
    }
    
    for (; y <= k; y++) {
      int z = 0;
      for (; z <= k - 3; z += 4) {
        ans0 += x+y+z == s-0; 
        ans1 += x+y+z == s-1; 
        ans2 += x+y+z == s-2; 
        ans3 += x+y+z == s-3;
      }

      for (; z <= k; z++) {
        ans0 += x+y+z == s;
      }
    }
  }

  int ans = ans0+ans1+ans2+ans3+ans4+ans5+ans6+ans7;

  cout << ans << endl;
}


Measured memory_bytes: 256
import sys

n = int( sys.stdin.readline() )
output = []
for i in range( 1, n+1 ):
	x = i
	if x%3 == 0:
		output.append( " {:d}".format( i ) )
	else:
		while x != 0:
			if x%10 == 3:
				output.append( " {:d}".format( i ) )
				break
			x = x//10
print( "".join( output ) )

Measured memory_bytes: 7232
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

using namespace std;

typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "{";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "}";

    return os;
}

ll pow_mod(ll a, ll p) {
    ll res = 1;
    while(p) {
        if (p & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        p >>= 1;
    }

    return res;
}


ll mod_inv(ll a, ll m) {
    ll b = m, u = 0, v = 1;
    while(a) {
        ll t = b / a;
        swap(b -= t * a, a);
        swap(u -= t * v, v);
    }

    return (u % m + m) % m;
}

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

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}


#ifdef LOCAL
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int H, W, K;
    cin >> H >> W >> K;
    --K;

    int c[W];
    c[0] = 1;
    c[1] = 2;
    FOR(i, 2, W) {
        c[i] = c[i-1] + c[i-2];
    }

    ll s[H+1][W];
    REP(i, H+1) REP(j, W) s[i][j] = 0;
    s[0][0] = 1;

    REP(i, H) {
        REP(j, W) {
            ll a1=0, a2=0, a3=0;
            if (j > 0) a1 = (s[i][j-1] * c[max(j-2, 0)] * c[max(W-j-2, 0)]) % MOD;
            a2 = (s[i][j] * c[max(j-1, 0)] * c[max(W-j-2, 0)]) % MOD;
            if (j < W-1) a3 = (s[i][j+1] * c[max(j-1, 0)] * c[max(W-j-3, 0)]) % MOD;

            s[i+1][j] = (a1 + a2 + a3) % MOD;
        }
    }

    cout << fixed << setprecision(20);
    cout << s[H][K] % MOD << endl;

}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

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

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

ll modpow(ll a, ll b){
    if(b == 0) return 1;
    else if(b % 2 == 0){
        ll d = modpow(a, b/2) % MOD;
        return (d * d) % MOD;
    }
    else{
        return (a * modpow(a, b-1)) % MOD;
    }
}

const int MAX_N = 400010;

ll fact[MAX_N], finv[MAX_N];
ll comb(int n, int r){
    if(n < r || r < 0) return 0;
    return fact[n] * finv[n-r] % MOD * finv[r] % MOD;
}

void calc(int n){
    fact[0] = finv[0] = 1;
    for(int i=1; i<=n; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        finv[i] = modpow(fact[i], MOD-2);
    }
}

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

    calc(400005);
    ll n, k; cin>>n>>k;

    ll ans = comb(n - 1 + n, n);

    if(k >= n - 1){
        cout << ans << endl;
        return 0;
    }

    if(k == 1){
        ll ans = comb(n, 2) * 2;
        cout << ans % MOD << endl;
        return 0;
    }

    // k < n - 1
    for(int i=1; i<n-k; i++){
        // i 箇所に集中する
        ll cur = comb(n, i);
        ll k = i;
        cur *= comb(n - 1, k - 1);
        cur %= MOD;
        ans -= cur;
        ans += MOD;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6528