akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


class Combination:
    def __init__(self, n, mod):

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

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


@mt
def slv(N, A):
    MOD = 10**9+7
    c = Counter(A)
    k = c.most_common(1)[0][0]
    i = A.index(k)
    j = i + A[i+1:].index(k)

    cmb = Combination(N+1, MOD)
    for k in range(1, N+2):
        ans = cmb(N+1, k) - cmb(i+N-(j+1), k-1)
        ans %= MOD
        print(ans)


def main():
    N = read_int()
    A = read_int_n()

    (slv(N, A))


if __name__ == '__main__':
    main()


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll;  typedef pair<int,ll> pii;
typedef vector<int> VI; typedef vector<ll> VL;
const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

ll prim(int s, const vector<vector<pii>>& G) {
	priority_queue<pii, vector<pii>, greater<pii> > que;
	int n = G.size();
	vector<bool> used(n);
	que.emplace(0, s);
	ll ret = 0;
	while(!que.empty()) {
		int cst = que.top().first, v = que.top().second;
		que.pop();
		if(used[v]) continue;
		used[v] = 1;
		ret += cst;
		for(auto x: G[v]) que.emplace(x.second, x.first);
	}
	return ret;
}
int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	vector<VI> jc(n, VI(3));
	rep(i, n){
		cin >>jc[i][0] >>jc[i][1]; jc[i][2] = i;
	}
	
	vector<vector<pii>> G(n);
	sort(all(jc));
	rep(i, n-1){
		auto z1=jc[i] , z2=jc[i+1];
		G[z1[2]].emplace_back(z2[2], abs(z2[0] - z1[0]));
		G[z2[2]].emplace_back(z1[2], abs(z2[0] - z1[0]));
	}
	sort(all(jc), [](auto& l, auto& r){return l[1] < r[1];});
	rep(i, n-1){
		auto z1=jc[i] , z2=jc[i+1];
		G[z1[2]].emplace_back(z2[2], abs(z2[1] - z1[1]));
		G[z2[2]].emplace_back(z1[2], abs(z2[1] - z1[1]));
	}
	cout << prim(0, G) <<endl;
	return 0;
}

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

int main()
{
    char str[15], ans[15];
    scanf("%s", str);

    int cnt = 0, len = strlen(str);

    for(int i=0; i<len; i++){
        if(str[i]=='B'){
            if(cnt!=0) cnt--;
            continue;
        }
        ans[cnt++] = str[i];
    }
    ans[cnt] = '\0';
    printf("%s\n", ans);

    return 0;
}


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

typedef long long int lli;

int main()
{
  lli n, ans = 0;
  cin >> n;
  if(n % 2)
    cout << "0" << endl;
  else
  {
    n /= 2;
    while(n)
    {
      ans += n / 5;
      n /= 5;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 256
let rec iter a b f = if a >= b then () else (f a; iter (a+1) b f)
let () =
  Scanf.scanf "%d" @@ fun x ->
  let a = Array.make (x+1) false in
  a.(1) <- true;
  iter 2 (x+1) (fun b ->
    let rec loop v =
      if v > x then ()
      else (a.(v) <- true; loop (v*b))
    in loop (b*b));
  Array.mapi (fun i e -> i,e) a
  |> Array.fold_left (fun v (i,t) -> if t then i else v) 1
  |> Printf.printf "%d\n"

Measured memory_bytes: 640
package main

import "fmt"

var n, m, cnt uint
var k, p []int
var s [][]int

func dfs(step, sw uint) { // 2^nのスイッチのパターンを全列挙する
	if n == step { // スイッチのパターン確定
		var i, j uint
		ok := true
		for i = 0; i < uint(len(s)); i++ { // i-1番目のスイッチ群の条件をチェックする
			var tsw uint
			for j = 0; j < uint(len(s[i])); j++ {
				tsw |= 1 << (uint(s[i][j]) - 1) // i-1番目のスイッチ群をビット列にする
			}
			tsw &= sw // スイッチのパターンとビットANDを取る
			tcnt := 0
			for j = 0; j < 64; j++ { // 立っているbitの数を確認する (64bit前提)
				if (tsw & (1 << j)) != 0 {
					tcnt++
				}
			}
			if tcnt%2 != p[i] { // 立っているbitの数を2で割った余りがp[i]でなければこの電球は点いていない
				ok = false
				break
			}
		}
		if ok {
			cnt++
		}
		return
	}
	dfs(step+1, sw)

	sw |= 1 << step
	dfs(step+1, sw)
}

func main() {
	fmt.Scan(&n, &m)
	k = make([]int, m)
	s = make([][]int, m)
	p = make([]int, m)
	for i := range k {
		fmt.Scan(&k[i])
		s[i] = make([]int, k[i])
		for j := range s[i] {
			fmt.Scan(&s[i][j])
		}
	}
	for i := range p {
		fmt.Scan(&p[i])
	}
	dfs(0, 0)
	fmt.Println(cnt)
}


Measured memory_bytes: 512
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B = MAP()

ans = 0
for i in range(A, B + 1):
    if str(i)[0] == str(i)[4] and str(i)[1] == str(i)[3]:
        ans += 1
print(ans)


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

int main(){
  int A,B;
  cin >> A >> B;
  
  int ans = 0;
  if(A>=B){
    ans += A;
    A--;
  }else if(B>=A){
    ans += B;
    B--;
  }
  
  if(A>=B){
    ans += A;
    A--;
  }else if(B>=A){
    ans += B;
    B--;
  }
  
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
using namespace std;

const int maxn = 1e7 + 10;
bool dp[maxn];


int main()
{
	int n;
    while(cin>>n)
    {
    	int i;
    	for(i=1; i<=n; i++)
    	{
    		if(i * (i + 1) / 2 >= n) break;
    	}
    	int sum = i * (i+1) / 2;

    	vector<bool> vis(i+1, false);
    	int k = 30;

    	while(sum > n)
    	{
    		if( (1 << k) < sum && sum - (1 << k) >= n)
    		{
    			sum -= (1 << k);
    			vis[(1 << k)] = true;
    		}
    		--k;
    	}
    	for(int j=1; j<=i; j++) if(!vis[j]) cout<<j<<endl;
    }
}








Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let w: usize = read();
    // (weight, value)
    let mut vec: Vec<(i64, i64)> = vec![];
    for _ in 0..n {
        vec.push((read(), read()));
    }
    let mut dp: Vec<Vec<i64>> = vec![vec![0; w + 1]; n + 1];
    for i in 0..n {
        for j in 0..w + 1 {
            if j < vec[i].0 as usize {
                dp[i + 1][j] = dp[i][j];
                continue;
            }
            dp[i + 1][j] = std::cmp::max(dp[i][j - vec[i].0 as usize] + vec[i].1, dp[i][j])
        }
    }
    println!("{}", dp[n][w]);
}


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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	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 { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= a; }
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint& operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
	int n;
	vector<T> d;
	BIT(int n = 0) :n(n), d(n + 1) {}
	void add(int i, T x = 1) {
		for (i++; i <= n; i += i & -i) {
			d[i] += x;
		}
	}
	T sum(int i) {
		T x = 0;
		for (i++; i; i -= i & -i) {
			x += d[i];
		}
		return x;
	}
	T sum(int l, int r) {
		return sum(r - 1) - sum(l - 1);
	}
};
int main() {
	int N;
	cin >> N;
	vector<pair<int, int>>X(N);
	map<int, int>sx;
	map<int, int>sy;
	for (int i = 0; i < N; ++i) {
		cin >> X[i].first >> X[i].second;
		sx[X[i].first] = 0;
		sy[X[i].second] = 0;
	}
	int count = 0;
	for (auto s : sx) {
		sx[s.first] = count;
		count++;
	}
	count = 0;
	for (auto s : sy) {
		sy[s.first] = count;
		count++;
	}
	for (int i = 0; i < N; ++i) {
		X[i].first = sx[X[i].first];
		X[i].second = sy[X[i].second];
	}

	mint ans = 0;
	sort(X.begin(),X.end());
	BIT<int> bit_bef(N), bit_aft(N);
	for (int i = 0; i < N; i++) bit_aft.add(i, 1);
	for (int i = 0; i < N; i++) {
		bit_aft.add(X[i].second, -1);
		mint m0 = ((mint)2).pow(bit_bef.sum(X[i].second));
		mint m1 = ((mint)2).pow(i - bit_bef.sum(X[i].second));
		mint m2 = ((mint)2).pow(bit_aft.sum(X[i].second));
		mint m3 = ((mint)2).pow(N - i - 1 - bit_aft.sum(X[i].second));
		ans += (m0 - 1)*(m3 - 1)*m1*m2;
		ans += (m1 - 1)*(m2 - 1)*m0*m3;
		ans -= (m0 - 1)*(m3 - 1)*(m1 - 1)*(m2 - 1);
		ans += ((mint)2).pow(N - 1);
		bit_bef.add(X[i].second, 1);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 25168
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    A, B = map(int, read().split())

    if A > B:
        print('GREATER')
    elif A < B:
        print('LESS')
    else:
        print('EQUAL')

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9116
// 最大公約数
#include<bits/stdc++.h>
using  namespace std;
int gcd(int a, int b);
int main(){
    int x,y;
    cin >> x >> y;
    // a >= b
    if(x < y){
        int w = x; x = y; y = w;
    }
    cout << gcd(x,y) << endl;
}
int gcd(int m, int n){
    while(n != 0){
        int w = n;
        n = m % n;
        m = w;
    }
    return m;
}


Measured memory_bytes: 3120
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;
int N, M, a[100000];
int main()
{
	bool b[100000] = { false };
	long long an[100010] = { 0 };
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d", &a[i]);
		b[a[i]] = true;
	}
	an[1] = 1;
	if (b[1]) {
		an[1] = 0;
	}
	if (b[2]) {
		an[2] = 0;
	}
	else if (an[1] == 0) {
		an[2] = 1;
	}
	else {
		an[2] = 2;
	}
	for (int i = 3; i <= N; i++) {
		if (b[i]) {
			an[i] = 0;
		}
		else {
			an[i] = (an[i - 1] + an[i - 2]) % mod;
		}
	}
	printf("%lld", an[N] % mod);
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,k;
  cin >> a >> b >> k;
  vector<int> list;
  for(int i=min(a,b); i>=1; i--) {
    if(a%i == 0 && b%i == 0) {
      list.push_back(i);
    }
  }
  cout << list.at(k-1) << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n;
string s,t,q;
int max(int a,int b){
    return a>b?a:b;
    
}
void solve(){
    int s1=s.size(),s2=t.size(),dp[s1+1][s2+1],i,j;
    for(i=0;i<=s1;i++){
         for(j=0;j<=s2;j++){
            dp[i][j]=0;}}
        for(i=0;i<s1;i++){
              for(j=0;j<s2;j++){
              if(s[i]==t[j])
              dp[i+1][j+1]=dp[i][j]+1;
             else
             dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
        }
    } i=s1;j=s2;
    vector<char> a;
       while(i>0&&j>0){
       if(dp[i][j]>max(dp[i-1][j],dp[i][j-1])){
              a.pb(s[i-1]);
              i--;j--;}
             else{
                 if(dp[i-1][j]==dp[i][j])
                 i--;
                 else
                 j--;
             }
           
       }
       reverse(a.begin(),a.end());
       for(i=0;i<a.size();i++)
       cout<<a[i];
    
     a.clear();
}
    int main() {
        int i,x;
        cin>>s>>t;
     solve();
     return 0;
}

Measured memory_bytes: 35456
# AGC024B


n = int(input())
a = [None] * n
for i in range(n):
    num = int(input())
    a[i] = num-1

seen = [False] * n
counts =[1] * n
for num in a:
    seen[num] = True
    if num>=1 and seen[num-1]:
        counts[num] = counts[num-1] + 1
print(n - max(counts))

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

int main()
{
	double A, B, H, M;
	cin >> A >> B >> H >> M;
	
	double Hdo = H * 30;
	double Mdo = M * 0.5;
	double HMdo = Hdo + Mdo;
	double Mdo2 = M*6;
	double N;
	
	if(HMdo - Mdo2 >= 180)
	{
		N = 360 - (HMdo - Mdo2);
	}
	else
	{
		N = Mdo2 - HMdo;
	}
	
	double ans = pow(A,2) + pow(B,2) - 2*A*B * cos(N * (acos(-1.0)/180.0));
	
	cout << fixed << setprecision(10) << sqrt(ans) << endl;
	
	return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
/* kmjpさん */

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long

typedef pair<ll, ll> P;

int n, m;
set<int> e[100010];
set<int> re[100010];
int ans[100010];

int main(){
    cin >> n >> m;
    REP(i, n+m-1) {
        int a, b;
        cin >> a >> b;
        e[a].insert(b);
        re[b].insert(a);
    }

    /* 入次数が0の頂点を探す */
    REPN(i, 1, n+1) if(re[i].empty()) {
        e[0].insert(i);
        re[i].insert(0);
        break;
    }

    /* トポロジカルソート */
    queue<int> Q;
    Q.push(0);
    while(Q.size()) {
        int x = Q.front();
        Q.pop();
        for(auto y: e[x]) {
            /* つながっている先を見て、つぶしていく */
            re[y].erase(x);
            /* 最後のやつは、一番近いやつのはず */
            if(re[y].empty()) {
                ans[y] = x;
                Q.push(y);
            }
        }
    }

    REPN(i, 1, n+1) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 20352
N = int(input())
rewards = [None] * N
for i in range(N):
    a, b, c = map(int, input().split())
    rewards[i] = (a, b, c)

dp = [[0] * 3 for _ in range(N + 1)]

for i in range(1, N + 1):
    dp[i][0] = max(dp[i - 1][1] + rewards[i - 1][0], dp[i - 1][2] + rewards[i - 1][0])
    dp[i][1] = max(dp[i - 1][0] + rewards[i - 1][1], dp[i - 1][2] + rewards[i - 1][1])
    dp[i][2] = max(dp[i - 1][0] + rewards[i - 1][2], dp[i - 1][1] + rewards[i - 1][2])
print(max(dp[N]))


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

struct Edge {
  /*
    dst -> destination
    weight -> weight
   */
  int dst,weight;
};

struct Data {

  int place,min;

  bool operator < (const Data& data)const{
    //if( min < data.min ) => true;
    if(data.min != min)return min > data.min;
    return data.place > place;
  }

};

//int cost[100001][100001];
vector<Edge> cost[10001];
int n;
int mindist[10001];
bool used[10001];

void dijkstra(){

  for(int i=0 ; i < 10001 ; i++){
    mindist[i]=1e9;
  }
  
  mindist[0]=0;

  priority_queue<Data> PQ;

  PQ.push((Data){0,0});

  while(!PQ.empty()){
    Data a=PQ.top();
    PQ.pop();
    if( mindist[a.place] < a.min ) continue;
    for(int i=0 ; i < (int)cost[a.place].size() ; i++){
      if(mindist[cost[a.place][i].dst] > cost[a.place][i].weight+mindist[a.place]){
	mindist[cost[a.place][i].dst] = cost[a.place][i].weight+mindist[a.place];
	PQ.push((Data){cost[a.place][i].dst,mindist[cost[a.place][i].dst]});
      }
      //cost[a.place].pop_back();
    } 
  }
  
  for(int i=0 ; i < n ; i++){
    cout <<i<<" "<<mindist[i]<<endl;
  }
  
}
int main(){
  
  int u,k,v,c;
  
  // 0 -> 1 weight : 3
  /*  
      cost[0].push_back((Edge){1,3});
      cost[0].push_back((Edge){0,4});
      cost[2].push_back((Edge){0,3});
  */
  
  cin >>n;
  
  for(int i=0 ; i < n ; i++){
    cin >>u>>k;
    for(int j=0 ; j < k ; j++){
      cin >>v>>c;
      cost[u].push_back((Edge){v,c});
    }
  }

  dijkstra();

  return 0;
}


/*
1sec => 10^8


 */

Measured memory_bytes: 6352
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

/*
 * 初期状態のピースでSccを可能な限り作って損をすることはない.
 * cが2未満しか余らなかった場合、終了.
 * cが2以上余っているということはSが枯渇したので、ccccをいくつ作れるかに帰着される.
 */
int main() {
  ll S, c; cin >> S >> c;
  ll ans = 0;
  ll d = min(S, c/2);
  S -= d;
  c -= d*2;
  ans += d;
  if (c < 2) {
    cout << ans << endl;
    return 0;
  }
  
  ans += c/ 4;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;

using namespace std;
using Graph = vector<vector<int>>;
Graph G;
const int AMAX = 100000;
/*int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}

int n;
vll a;

ll solve(bool isp)
{
	ll sum = 0ll;
	ll ret = 0ll;

	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (isp and sum <= 0)
		{
			ret += -sum + 1;
			sum = 1ll;
		}
		if (not isp and sum >= 0)
		{
			ret += sum + 1;
			sum = -1ll;
		}
		isp ^= 1;
	}
	return ret;
}

*/
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N;
	cin >> N;
	vector<int> data(N);
	vector<int> rank(8);
	for (int i = 0; i < N; i++)
	{
		cin >> data[i];
		if (1 <= data[i] && data[i] < 400)
		{
			rank[0]++;
		}
		if (400 <= data[i] && data[i] < 800)
		{
			rank[1]++;
		}
		if (800 <= data[i] && data[i] < 1200)
		{
			rank[2]++;
		}
		if (1200 <= data[i] && data[i] < 1600)
		{
			rank[3]++;
		}
		if (1600 <= data[i] && data[i] < 2000)
		{
			rank[4]++;
		}
		if (2000 <= data[i] && data[i] < 2400)
		{
			rank[5]++;
		}
		if (2400 <= data[i] && data[i] < 2800)
		{
			rank[6]++;
		}
		if (2800 <= data[i] && data[i] < 3200)
		{
			rank[7]++;
		}
		if (3200 <= data[i])
		{
			rank[8]++;
		}


	}

	int ans = 0;
	for (int i = 0; i < 8; i++)
	{
		if (rank[i] > 0)
		{
			ans++;
		}
	}
	int max, min = 0;

	
	max = ans + rank[8];
	

	if (ans>=1)
	{
		min = ans;
	}
	else if (ans == 0)
	{
		min = 1;
	}

	cout << min << " " <<max << endl;


	return 0;

}

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

int main() {
 UL N; scanf("%u",&N);
 UL A[100000]; rep(i,N) scanf("%u",&A[i]);
 UL Q; scanf("%u",&Q);
 rep(q,Q){
  UL k; scanf("%u",&k);
  UL l=0,r=N+1;
  while(l+1!=r){
   UL m=(l+r)>>1;
   if(A[m-1]<k) l=m;
   else r=m;
  }
  printf("%u ",l);
  l=0,r=N+1;
  while(l+1!=r){
   UL m=(l+r)>>1;
   if(A[m-1]<=k) l=m;
   else r=m;
  }
  printf("%u\n",l);
 }
 return 0;
}




Measured memory_bytes: 3572
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<set>
 
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define INF 1<<25
 
typedef long long ll;

int dy[8]={1,1,1,0,0,-1,-1,-1};
int dx[8]={-1,0,1,-1,1,-1,0,1};
struct S{
	int a,b,c;
};
bool asc(const S& left,const S& right){
	return left.c > right.c;
}


int main(){
	ll H,W;
	cin>>H>>W;
	ll mn=10e10;
	rep(i,2){
		REP(j,1,H){
			ll a=j*W;
			ll b=(H-j)*(W/2);
			ll c=H*W-a-b;
			mn=min(mn,max({a,b,c})-min({a,b,c}));
		}
		REP(j,1,H){
			ll a=j*W;
			ll b=(H-j)/2*W;
			ll c=H*W-a-b;
			mn=min(mn,max({a,b,c})-min({a,b,c}));
		}
		swap(H,W);
	}
	cout<<mn<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

#include <math.h>
#define PI 3.14159265358979323846264338327950L


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

Measured memory_bytes: 3576
fun main(args: Array<String>) {
    val (N,X) = readLine()!!.split(" ").map{it.toInt()}
    val xs = readLine()!!.split(" ").map{it.toInt()} + X
    val min = xs.min()!!
    val ys = xs.map { it-min }.sorted()
    var z=ys[1]
    for(i in 2..N){
        z=gcd(z,ys[i]-ys[i-1])
    }
    println(z)
}

tailrec fun gcd(a:Int, b:Int):Int = if(b==0) a else gcd(b,a%b)

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

int main() {
  int W, a, b, Ans;
  cin >> W >> a >> b;
  if(min(a,b)+W>=max(a,b)) Ans=0;
  else Ans=max(a,b)-(min(a,b)+W);
  cout << Ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int d, score;
vector<int> c(26);
vector<vector<int>> s(400, vector<int>(26)), pos(26);

int get_score(vector<int> t){
    vector<int> pos(26, 0);
    int ans = 0;
    rep(i, t.size()){
        int l = i + 1 - pos[t[i]];
        ans -= (l * (l-1) / 2) * c[t[i]];
        ans += s[i][t[i]];
        pos[t[i]] = i+1;
    }
    rep(i, 26){
        int l = t.size() + 1 - pos[i];
        ans -= (l * (l-1) / 2)* c[i];
    }
    return ans;
}

int main() {
    cin >> d;
    rep(i, 26)cin >> c[i];
    rep(i, d)rep(j, 26)cin >> s[i][j];
    //-----code------// 
    vector<int> t, pos(26, 0);
    rep(i, d){
        int max_score = -mod;
        int best_j = -1;
        rep(j, 26){
            t.push_back(j);
            int score = get_score(t);
            if(max_score < score){
                best_j = j;
                max_score = score;
            }
            t.pop_back();
        }
        t.push_back(best_j);
    }
    vector<int> ans = t;
    double start_temp = 100, end_temp = 10;
    int current_max_score = get_score(t);
    while(clock() < 1.95 * CLOCKS_PER_SEC){
        if(rand() % 2 == 0){
            int D = rand() % d, q = rand() % 26;
            int old = t[D];
            int olds = get_score(t);
            t[D] = q;
            int score = get_score(t);
            double temp = start_temp + (end_temp - start_temp) * clock() / (1.95 * CLOCKS_PER_SEC);
            double prob = exp((olds - score)/temp);

            if(chmax(current_max_score, score)){
                ans = t;
            }else{
                if(prob <= (double)(rand() % 10000) / 10000){
                    t[D] = old;
                }
            }

            if(prob >= ((rand()%inf)/(double)inf))t[D] = old;
        }else{
            int a = 5 + rand() % (d-10), b = 1 + rand() % 4;
            int olds = get_score(t);
            swap(t[a], t[b]);
            int score = get_score(t);
            if(score < olds){
                swap(t[a], t[b]);
            }
        }
    }
    rep(i, d)cout << ans[i]+1 << endl;
}


Measured memory_bytes: 3840
#!/usr/bin/env python3
#ABC139 B

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a,b = LI()
n = 1
if b == 1:
    print(0)
    quit()
while 1:
    if a + (n-1)*(a-1) >= b:
        print(n)
        quit()
    n += 1


Measured memory_bytes: 38384
import sys

(N, K) = map(int, input().split(" "))
S = input()

nowOn = S[0]
count = 0
serialList = []

for i in S:

    if(nowOn == i):
        count += 1

    else:
        serialList.append(count)
        count = 1
        nowOn = i

serialList.append(count)

T = 2 * K + 1
A = 0

#serialList -> ["1", "0", "1", "0", ...]
if S[0] == "0":
    serialList.insert(0, 0)
    
#exception
if int(len(serialList) / 2) < K:
    print(len(S))
    sys.exit()

maxA = 0
for i in range(T):
    A += serialList[i]
    maxA = A
    
for i in range(T, len(serialList), 2):
    A -= serialList[i - T]
    A -= serialList[i - T + 1]
    A += serialList[i]

    if(i+1 < len(serialList)):
        A += serialList[i + 1]

    if maxA < A:
        maxA = A
        
print(maxA)



Measured memory_bytes: 45680
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>
#include <unordered_map>

#define mod 1000000007

using namespace std;
using ll = long long;

void solve(){
    string s;
    cin >> s;
    int res = (int)s.length();
    for(int i = 0; i < s.length(); i++){
        if(s[i] != s[i+1]){
            res = min(res, max(i+1, (int)s.length()-i-1));
        }
    }
    cout << res << endl;
}

int main(){
    solve();
    return 0;
}

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

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

    int max1, max2;
    max1 = max2 = 0;
    int id;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        max2 = max(max2, a);
        if (max1 < max2) {
            id = i;
            swap(max1, max2);
        }
    }

    for (int i = 0; i < n; i++) {
        int out = i == id ? max2 : max1;
        cout << out << endl;
    }

    return 0;
}


Measured memory_bytes: 1664
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <fcntl.h>

int main()
{
	int i = 0;
	int ans = 0;
	char n[10000000];

	scanf("%s", n);
	while (n[i])
	{
		ans += n[i] - 48;
		i++;
	}
	printf("%s\n", (ans % 9 == 0 ? "Yes" : "No"));

	return (0);
}


Measured memory_bytes: 1796
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i++)
 
int main(){
  long long N,co=0,d=1,i=0;
  cin >> N;
  
  vector <long long> p(N);
  vector <long long> c(0);
  
  rep(i,N){
    cin >> p.at(i);
    if(i+1==p.at(i))
      c.push_back(i);
     }
  
  while(i<(long long)c.size()-1){
    if(c.at(i+1)-c.at(i)==1){
      i++;
      if(i+1!=c.size() && c.at(i+1)-c.at(i)==1){
      	while(i+1!=c.size() && c.at(i+1)-c.at(i)==1){
        d++;
        i++;
      }
        d++;

        d/=2;
      
      co+=d;
      
      }
      
      else{
        co++;
      }
    }
      
    d=1;
    i++;
  }
  
     cout << (long long)c.size()-co << endl; 
}

Measured memory_bytes: 2168
// -*- coding:utf-8-unix -*-

use num_traits::{pow, One};
use proconio::{fastout, input};
use std::ops::{Add, Div, Mul, Sub};

const MODULUS: usize = 998244353;

#[fastout]
fn main() {
    input! {
        a: usize,
        b: usize,
        c: usize,
        d: usize,
    }
    let mut yarikata: Vec<Vec<ModP>> = vec![vec![ModP(0); d + 1 - b]; c + 1 - a];
    for i in 0..=c - a {
        for j in 0..=d - b {
            if i == 0 && j == 0 {
                yarikata[i][j] = ModP(1);
            } else if i == 0 {
                yarikata[i][j] = yarikata[i][j - 1] * ModP(a);
            } else if j == 0 {
                yarikata[i][j] = yarikata[i - 1][j] * ModP(b);
            } else {
                yarikata[i][j] = yarikata[i][j - 1] * ModP(a + i)
                    + yarikata[i - 1][j] * ModP(b + j)
                    - yarikata[i - 1][j - 1] * ModP(a + i - 1) * ModP(b + j - 1);
            }
        }
    }
    println!("{}", yarikata[c - a][d - b].0);
}

#[derive(Clone, Copy, PartialEq, Debug)]
struct ModP(usize);

impl One for ModP {
    fn one() -> Self {
        return ModP(1);
    }
}
impl Add for ModP {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        return ModP((self.0 + rhs.0) % MODULUS);
    }
}
impl Sub for ModP {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        return ModP((self.0 + MODULUS - rhs.0) % MODULUS);
    }
}
impl Mul for ModP {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        return ModP((self.0 * rhs.0) % MODULUS);
    }
}
impl Div for ModP {
    type Output = Self;
    fn div(self, rhs: Self) -> Self {
        if rhs.0 == 0 {
            panic!("Tried to divide by ModP(0)!");
        }
        let rhs_inv = pow(rhs, MODULUS - 2);
        return self * rhs_inv;
    }
}


Measured memory_bytes: 72412
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define st(vvv) sort(vvv.begin(),vvv.end())
#define rvs(vvv) reverse(vvv.begin(),vvv.end())
int inf = 1000000007;

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int gg = n - m;
	gg = gg * gg;
	if (gg > 1) {
		cout << 0 << endl;
		return 0;
	}
	i64 ans = 1;
	ff(i, 1, m+1) {
		ans *= i;
		ans %= inf;
	}
	ff(i, 1, n+1) {
		ans *= i;
		ans %= inf;
	}
	if (n == m)ans *= 2;
	ans %= inf;
	cout << ans << endl;
	return 0;
}

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


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

class CKnotPuzzle {
public:
	void solve(std::istream& in, std::ostream& out) {
        ll n,l;
        in >> n >> l;
        vector<ll> a(n);
        rep(i,n){
            in >> a[i];
        }
        ll t=-1L;
        rep(i,n-1){
            if(a[i]+a[i+1]>=l){
                t=i;
                break;
            }
        }
        if(t==-1){
            out << "Impossible" << endl;
            return ;
        }
        out << "Possible" << endl;
        rep(i,t){
            out << i+1 << endl;
        }
        for(int i=n-1;i>t;i--){
            out << i << endl;
        }
	}
};


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


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int main(){
    int N; cin>>N;
    vector<int> B(N+1,INT_MAX);
    rep(n,1,N) cin>>B.at(n);

    vector<int> A(N,0);
    rep(n,0,N) A.at(n)=min(B.at(n),B.at(n+1));

    cout<<accumulate(ToEnd(A),0)<<endl;
}

Measured memory_bytes: 256
// B - Digit Sums
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	string S; cin>>S;
	int s = 0;
	rp(i, 0, S.size()) s += S[i]-'0';
	cout<< (stoi(S)%s? "No":"Yes") <<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
const int N=360;
int mod;
inline void Add(int &x,int y) { x+=y; if(x>=mod) x-=mod;  }
int solve0(int n,int k) { // you can't choose k consecutive integers
	static int f[N];
	f[0]=1;
	for(int i=1;i<=n+1;++i) {
		f[i]=0;
		for(int j=i-1;i-j-1<k&&j>=0;--j)
			f[i]=(f[i]+f[j])%mod;
	}
	return f[n+1];
}
int solve1(int n,int k) { // k is odd, k!=1
	static int f[N][N][N];
	f[1][0][0]=1;
	f[1][1][0]=1;
	for(int i=2;i*2-k<=n;++i) {
		int a=2*i,b=2*i-k;
		for(int j=0;j<=i-1;++j) // go down
			for(int l=0;l<=i-1;++l) if(f[i-1][j][l]) { // go down - left - down
			//	cout<<i-1<<' '<<j<<' '<<l<<':'<<f[i-1][j][l]<<endl;
				if(b<0) {
					Add(f[i][0][0],f[i-1][j][l]);
					Add(f[i][j+1][0],f[i-1][j][l]);
				}
				else if(a>n) {
					Add(f[i][0][0],f[i-1][j][l]);
					if(l) { if(l<k) Add(f[i][0][l+1],f[i-1][j][l]); }
					else Add(f[i][0][0],f[i-1][j][l]);
				}
				else {
					for(int s=0;s<4;++s) {
						int x=s&1,y=s&2;
						int j1=x?j+1:0;
						int l1=(y&&l)?l+1:0;
						if(x&&y) l1=max(l1,j+1);
						if(l1>=k+1) continue; 
						Add(f[i][j1][l1],f[i-1][j][l]);
					}
				}
			}
	}
	int ans=0;
	for(int j=0;j<=(n+k)/2;++j)
		for(int l=0;l<=k;++l) if(f[(n+k)/2][j][l])
			ans=(ans+f[(n+k)/2][j][l])%mod;//,cout<<(n+k)/2<<' '<<j<<' '<<l<<':'<<f[(n+k)/2][j][l]<<endl;
	return ans;
}
int main() { 
	int n,k;
	scanf("%d%d%d",&n,&k,&mod);
	if(k==1) { printf("%d\n",solve0(n,3)); return 0; }
	if(k%2==0) {
		k/=2;
		printf("%d\n",(int)(solve0(n/2,k+1)*1ll*solve0((n+1)/2,k+1)%mod));
		return 0;
	}
	printf("%d\n",solve1(n,k));
	return 0;
}

Measured memory_bytes: 73984
N=int(input())
keta=0
n=N
ketakari=0
while(1):
    keta+=1
    ketakari+=26**keta
    if N<=ketakari:
        break
for j in range(1,keta):
    N-=26**j
ans=""
#print(keta)
#print(ans)
#print(N)
N-=1
for i in range(keta):
    kari=N%26
    ans=chr(ord("a")+kari)+ans
    N//=26
print(ans)

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

using namespace std;

#define int long long
long long m, s, ans = 1e12;

long long f(long long b, long long n){
    if(b == 1) return 0;
    if(n < b) return n;
    else return f(b, n / b) + n % b;
}

signed main(){
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> m >> s;
    if(m == s){
        cout << m + 1;
        return 0;
    }
    for(int i = 2; i*i <= m; i++){
        if(f(i, m) == s)
            ans = min (ans,i);
    }
    for(int i = 2; i*i <= s; i++){
        if(f(i, m) == s)
            ans = min (ans,i);
    }
    if(m > s){
        for(int i = 1; i*i <= m - s; i++){
            int pointer = (m - s)/i + 1;
            if(f(i, m) == s)
                ans = min(ans,i);
            if(f(pointer, m) == s)
                ans = min(ans,pointer);
        }
    }
    if(ans != 1e12) {cout << ans; exit(0);}
    cout << "-1\n";
}


Measured memory_bytes: 256
// Problem : D - Coloring Edges on Tree
// Contest : AtCoder - AtCoder Beginner Contest 146
// URL : https://atcoder.jp/contests/abc146/tasks/abc146_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
const ll MOD = 1e9 + 7;
#define fir first
#define sec second
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(c,a,b) for(ll c=a;c<b;c++)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define min_heap priority_queue<pll,vector<pll>,greater<pll> >
ll dx4[]={-1,1,0,0};
ll dy4[]={0,0,-1,1};
ll dx8[]={-1,-1,-1,0,1,1,1,0};
ll dy8[]={-1,0,1,1,1,0,-1,-1};
bool isvalid(ll x,ll y,ll n,ll m)
{
    return (x>=0 and y>=0 and x<n and y<m);
}
ll isprime[1000];
vector<ll> prime;
void sievetoprime(ll n)
{
    mem(isprime,true);
    for(ll p=2;p*p<=n;p++)
    {
        if(isprime[p]==true)
        {
            for(ll i=p*p;i<=n;i+=p)
                isprime[i]=false;
        }
    }
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
void solve()
{
    ll n;
    cin>>n;
    vector<ll> adj[n+1];
    vector<pll> v;
    map<pll,ll> ma;
    ll a,b;
    rep(i,0,n-1)
    {
    	cin>>a>>b;
    	adj[a].pb(b);
    	adj[b].pb(a);
    	v.pb(mp(a,b));
    	ma[{a,b}]=0;
    	ma[{b,a}]=0;
    }
    ll mx=-INF;
    for(ll i=1;i<=n;i++)
    {
    	a=adj[i].size();
    	mx=max(mx,a);
    }
    cout<<mx<<"\n";
    for(ll i=1;i<=n;i++)
    {
    	ll curr=0;
    	vector<ll> col(adj[i].size());
    	iota(all(col),1);
    	for(auto j:adj[i])
    	{
    		if(ma[{i,j}])
    		{
    			auto x=remove(all(col),ma[{i,j}]);
    		}
    	}
    	for(auto j:adj[i])
    	{
    		if(ma[{i,j}]==0 and ma[{j,i}]==0)
    		{
    			ma[{i,j}]=col[curr];
    			ma[{j,i}]=col[curr];
    			curr++;
    		}
    	}
    }
    for(auto i:v)
    {
    	cout<<ma[{i.fir,i.sec}]<<endl;
    }
}
int main()
{
    ll inpoup = 0;
    if(inpoup==1)
    {
        #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
        #endif
    }
    IOS
    ll t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 20592
#include <cstring>
#include <cstring>
#include <vector>
#include <queue>
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <cstring>
#include <unordered_set>
#include <algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9;
 
typedef long long ll;
 
int main()
{
	int arr[3];
	for (int i = 0; i < 3; i++)
		cin >> arr[i];
	sort(arr, arr + 3);
	cout << arr[0] * arr[1]/2;
}

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

#define watch(x) cerr << (#x) << ": " << (x) << endl

int h, w, a, b;

int32_t main() {

    cin >> h >> w >> a >> b;

    vector<vector<int>> ans(h, vector<int>(w, 0));

    for(int row = 0; row < b; ++row) {
        for(int col = 0; col < a; ++col) {
            ans[row][col] = 1;
        }
    }

    for(int row = b; row < h; ++row) {
        for(int col = a; col < w; ++col) {
            ans[row][col] = 1;
        }
    }

    for(auto v : ans) {
        for(auto i : v) cout << i;
        cout << '\n';
    }
    
    return 0;
}


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

typedef long long ll;
const long long LINF = 1LL << 60;
const long long LMINF = 1LL << 63;
const int INF = 1 << 30;

#define REP(i,n) for(int i = 0;i < n;++i)
#define REPS(i,x) for(int i = 1;i <= (int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i >= 0;i--)
#define RREPS(i,x) for(int i=((int)(x));i > 0;i--)
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << ": " << x << "\n"

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



int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int l,r,d;
    cin >> l>> r>> d;
    int ans = 0;
    for(int i = l;i <= r;i++){
        if(i % d == 0)ans++;
    }

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

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

void solve(){
    int n,m;cin>>n>>m;n++;
    vector<bool>a(n,0);REP(i,m){int x;cin>>x;a[x]=1;}
    int dp[n];dp[0]=1;dp[1]=a[1]?0:1;
    rep(i,2,n)(dp[i]=a[i]?0:dp[i-1]+dp[i-2])%=mod;
    cout<<dp[n-1]<<endl;
}
int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(void){
 
    int N;
    int ans = 0;
    cin >> N;
    
    for(int i = 1; i <= N; i+=2){
        
        int count = 0;
        int num = i;
        
        for(int j = 1; j <= N; j++){
            if(num % j == 0) count++;
        }
        
        if(count == 8) ans++;
    }
    
    cout << ans << endl;
}


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

long long int Ism(long long int n, int a)
{
    if(a==1)
    {
        return n;
    }
    long long int num = 1;
    while(a > 0)
    {
        if(a%2!=0)
        {
            num = num*n%MOD;
        }
        n = n*n%MOD;
        a /= 2;
    }
    return num;
}

long long int func(int n, int a)
{
    long long int x=1,y=1;
    for(int i = 0; i < a; ++i)
    {
        x = (x*(n-i))%MOD;
        y = (y*(i+1))%MOD;
    }
    return (x*Ism(y,MOD-2))%MOD;
}

int main()
{
    long long int n, a, b;
    cin >> n >> a >> b;
    long long int bouquet = Ism(2,n);
    cout << (bouquet-1-func(n,a)+MOD+-func(n,b)+MOD)%MOD << endl;
}

Measured memory_bytes: 256
n,a,b = map(int,input().split())
mod = (10**9)+7
max_cate = pow(2, n, mod) - 1
def cmb_mod(n, r, mod):
  numerator = 1
  denominator = 1
  for i in range(r):
    numerator = (numerator * (n - i)) % mod
    denominator = (denominator * (i + 1)) % mod
  return (numerator * pow(denominator,mod-2,mod)) % mod

a_num = cmb_mod(n,a,mod)
b_num = cmb_mod(n,b,mod)
print((max_cate - a_num - b_num)%mod)


Measured memory_bytes: 3064
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N):
    res = 0
    while N != 0:
        b = format(N, "b").count("1")
        N %= b
        res += 1
    return res


def main():
    N = int(input())
    X = input().strip()
    K = X.count("1")

    A = [(1, 1)]
    for i in range(N):
        a, b = A[-1]
        A.append(((a * 2) % (K - 1) if K != 1 else 0, (b * 2) % (K + 1)))

    B = [0, 0]
    for i, b in enumerate(X[::-1]):
        if b == "0":
            continue
        if K != 1:
            B[0] += A[i][0]
            B[0] %= K - 1
        B[1] += A[i][1]
        B[1] %= K + 1

    res = [0] * N
    for i, b in enumerate(X[::-1]):
        if b == "0":
            res[i] = (B[1] + A[i][1]) % (K + 1)
        else:
            if K == 1:
                res[i] = 0
                continue
            res[i] = (B[0] - A[i][0]) % (K - 1)
        res[i] = f(res[i]) + 1

    for r in res[::-1]:
        print(r)


if __name__ == "__main__":
    main()


Measured memory_bytes: 40336
#include<stdio.h>
#include <string.h>
const int M=1046527,NIL=-1,L=14;
char H[1046527][14];
int getChar(char ch){
    if(ch=='A') return 1;
    if(ch=='C') return 2;
    if(ch=='G') return 3;
    if(ch=='T') return 4;
    return 0;
}
long long getKey(char str[]){
    long long sum=0,p=1,i;
    for ( i = 0; str[i] ; ++i) {
        sum+=p*(getChar(str[i]));
        p*=5;
    }
    return sum;
}
int h1(int k){return k%M;}
int h2(int k){return 1+(k%(M-1));}
int find(char str[]){
    long long k,i,h;
    k=getKey(str);
    for ( i = 0;  ; ++i) {
        h=(h1(k)+i*h2(k))%M;
        if(strcmp(H[h],str)==0) return 1;
        else if(strlen(H[h])==0) return 0;
    }
    return 0;
}
int insert(char str[]){
    long long key,i,h;
    key=getKey(str);
    for ( i = 0;  ; ++i) {
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0) return 1;
        else if(strlen(H[h])==0) {
            strcpy(H[h],str);
            return 0;
        }
    }
    return 0;
}
int main(){
    int i,n,h;
    char str[L],com[9];
    for ( i = 0; i < M; ++i) H[i][0]='\0';
    scanf("%d",&n);
    for ( i = 0; i < n; ++i) {
        scanf("%s %s",com,str);
        if(com[0]=='i') insert(str);
        else {
            if(find(str)) printf("yes\n");
            else printf("no\n");
        }
    }
    return 0;
}


Measured memory_bytes: 16040
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include <vector>
#include <algorithm>

using namespace std;


int main()
{

	int N;
	cin >> N;
	int count = 0;
	for(int a = 1; a <= N; a++) {
		// bの範囲
		int bmax = (N % a == 0) ? N / a - 1 : N / a;
		count += bmax;
		//cout << bmax << endl;
	}
	
	cout << count << endl;
	
	return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
    #include<string.h>
    int main()
    {
        int i,j,k;
        char S[201];
        scanf("%s",S);
        k = strlen(S);
        for(i=k-2;0<i;i-=2){
          if(strncmp(S,S+i/2,i/2) ==0){
          printf("%d\n",i);
          return 0;
          }
        }
        return 0;
    }

Measured memory_bytes: 128