akhauriyash/Code-Regression huggingface dataset:
#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>;

const int INF = 1001001001;
int dp[1000005][2];

int main() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    s += "0";
    int n = s.size();
    rep(i, n+1) {
        rep(j, 2) dp[i][j] = INF;
    }
    dp[0][0] = 0;
    rep(i, n) rep(j, 2) {
        int x = s[i] - '0';
        x += j;
        if (x < 10) dp[i+1][0] = min(dp[i+1][0], dp[i][j]+x);
        if (x > 0) dp[i+1][1] = min(dp[i+1][1], dp[i][j]+(10-x));
    }
    cout << dp[n][0] << endl;
    return 0;
}

Measured memory_bytes: 9220
#include<iostream>
using namespace std;
 
int main(){
 int a,b;
 cin >> a >> b;
 
 if(a%3==0){
   cout <<"Possible" << endl;
 }
 else if(b%3==0){
   cout << "Possible" << endl;
 }
 else if( (a+b) % 3 == 0){
   cout << "Possible" << endl;
 }
 else{
   cout << "Impossible" << endl;
 }
 return 0;
}

Measured memory_bytes: 384
from collections import Counter

n = int(input())
nums = list(map(int, input().split()))
length = len(nums)
num_dict = Counter(nums)
all_count = 0
for i in num_dict.keys():
    all_count += ((num_dict[i]-1) * num_dict[i]) //2
    
for i in range(length):
    print(all_count - (num_dict[nums[i]]-1))

Measured memory_bytes: 26780
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
		int n;
		n = sc.nextInt();
		int d[] = new int [n];
		int max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
		Long sum = 0l;
		
		for(int i=0;i<n;i++){
			d[i]= sc.nextInt();
			if(d[i]>max){
				max = d[i];
			}
			if(d[i]<min){
				min = d[i];
			}
				sum+=d[i];
		}
		System.out.println(min+" "+max+" "+sum);
		sc.close();
	}

}



Measured memory_bytes: 41168
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    long N = sc.nextLong();
    ArrayList<Integer> first = new ArrayList<>();
    ArrayList<Integer> second = new ArrayList<>();
    for (int i = 1; (1L << i) - 1 <= N; i++) {
      first.add(i);
      second.add(i);
    }
    N -= (1L << first.size()) - 1;
    while (N > 0) {
      int a = first.size() + 1;
      first.add(a);
      for (int i = 0; ; i++) {
        if ((1L << (i + 1)) > N) {
          second.add(i, a);
          N -= (1L << (i));
          break;
        }
      }
    }

    System.out.println(first.size() * 2);
    for (int i = 0; i < first.size(); i++) {
      System.out.print(first.get(i) + " ");
    }
    for (int i = 0; i < first.size(); i++) {
      System.out.print(second.get(i) + (i == first.size() - 1 ? "\n" : " "));
    }
  }

}


Measured memory_bytes: 23892
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a1 = scan.nextInt();
		int a2 = scan.nextInt();
		int a3 = scan.nextInt();

		int sum = a1 + a2 + a3;

		if(sum >=22) {
			System.out.println("bust");
		}else {
			System.out.println("win");
		}
	}

}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--)
#define reprev(i,n) reprrev(i,0,n)
using namespace std;
#define sz(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
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; }
#define pb push_back
#define mp make_pair
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll INF = 1LL<<60;
 
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
struct UnionFind {
    vector<int> par, rank;
 
    UnionFind(int n) : par(n , -1), rank(n, 0) { }
    void init(int n) { par.assign(n, -1), rank.assign(n, 0); }
 
    int root(int x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }
 
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
 
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};
 
int main(){
    ll N;
  	cin >> N;
  	ll ans = 1;
	vector<ll> T(N);
  	rep(i, N) cin >> T[i];
  	rep(i,N){
      ans = ans / gcd(ans,T[i]) * T[i];
    }
  cout << ans << endl;
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
s = S()
L = [0] * n


# 0が狼、1が羊
def main():
    for i, j in [(1, 0), (0, 1), (0, 0), (1, 1)]:
        L[0] = i
        L[1] = j
        for k in range(1, n - 1):
            if (s[k] == 'o' and L[k]) or (s[k] == 'x' and not L[k]):
                L[k + 1] = L[k - 1]
            else:
                L[k + 1] = L[k - 1] ^ 1

        if (s[n - 1] == 'o' and L[n - 1]) or (s[n - 1] == 'x' and not L[n - 1]):
            first = L[n - 2]
        else:
            first = L[n - 2] ^ 1
        if (s[0] == 'o' and L[0]) or (s[0] == 'x' and not L[0]):
            second = L[n - 1]
        else:
            second = L[n - 1] ^ 1
        if first == L[0] and second == L[1]:
            return L


L = main()
if L:
    print(''.join(['S' if i else 'W' for i in L]))
else:
    print(-1)

Measured memory_bytes: 48368
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
n,q=NM()
l=[]
for i in range(n):
    s,t,x=NM()
    l.append((s-x,t-x,x))
l.sort()
INF=float("inf")
l+=[(INF,INF,INF)]
d=LN(q)
q=[]
from heapq import heappush,heappop
j=0
for i in d:
    while l[j][0]<=i:
        s,t,x=l[j]
        heappush(q,(x,t))
        j+=1
    if len(q)==0:
        print(-1)
    else:
        while q:
            x,t=heappop(q)
            if t>i:
                heappush(q,(x,t))
                print(x)
                break
        else:
            print(-1)

Measured memory_bytes: 61976
#include <iostream>
#include <string>

int main() {
    std::string s[3];
    
    for(int i = 0; i < 3; i++) {
        std::cin >> s[i];
    }

    bool flag = false;
    for(int i = 0; i < 3; i++) {
        std::cout << s[i][i];
    }
    std::cout << std::endl;
}

Measured memory_bytes: 256
package main

import (
	"math/rand"
	"time"
	"os"
	"bufio"
	"fmt"
	"strconv"
	"strings"
)

var(
	inf = 10000000071000000
	sc = bufio.NewScanner(os.Stdin)
	stdin = bufio.NewReader(os.Stdin)
	mod = 1000000007
	mod9 = 1000000009
)

func init()  {
	rand.Seed(time.Now().UnixNano())
	buf := make([]byte, 0) //ここのサイズは何でもよさそう
	sc.Buffer(buf, 1000000009)
}


func main() {
	s := gostring()
	count := make([]int,3)
	for _,v:=range s{
		count[int(v)-97] ++
	}
	check := false
	for i:=0;i<3;i++{
		for j:=i+1;j<3;j++{
			if count[i] == count[j]{
				k := 0
				for {
					if k != i && k != j{break}
					k ++
				}
				if abs(count[k] - count[i]) <= 1{
					check = true
				}
			}
		}
	}
	if check {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}

//||||||||||||||||||||||||||入力|||||||||||||||||||||||||||||||||||||||\
//数字一文字入力
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

//文字列を一行入力
func nextLine() string {
	sc.Scan()
	return sc.Text()
}

//空白区切りの文字列の入力
func spaceLine() []string {
	sc.Scan()
	return strings.Split(sc.Text()," ")
}

//数字を一行入力
func intLine() []int {
	str := spaceLine()
	buf := make([]int,len(str))
	for i,s:=range str{
		buf[i],_ = strconv.Atoi(s)
	}
	return buf
}

//次のスペースか改行まで読み込む
func gostring() string {
	byte_ls := make([]byte,0)
	for  {
		b, _ := stdin.ReadByte()
		if b == 32 || b == 10 || b == 0{
			return string(byte_ls)
		} else if b == 13 {
			continue
		} else {
			byte_ls = append(byte_ls,b)
		}
	}
}

//上の関数のintバージョン
func goint() int {
	n,_ := strconv.Atoi(gostring())
	return n
}

//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

func sum(a ...int) int {
	ans := 0
	for i:=0;i<len(a);i++{
		ans += a[i]
	}
	return ans
}

func min(a ...int) int {
	ans := a[0]
	for i:=1;i<len(a);i++{
		if ans > a[i]{
			ans = a[i]
		}
	}
	return ans
}

func abs(n int) int {
	if n >= 0{
		return n
	} else {
		return -n
	}
}

func max(a ...int) int {
	ans := a[0]
	for i:=1;i<len(a);i++{
		if ans < a[i]{
			ans = a[i]
		}
	}
	return ans
}

Measured memory_bytes: 1280
#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    int A, B;

    cin >> A >> B;
    if (1<=A && A<=9 && 1<=B && B<=9){
        cout << A*B << endl;
    }
    else {
        cout << -1 << endl;
    }

    return 0;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  if(A<10&&B<10){
    cout << A*B << endl;
  }else{
    cout << -1 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const int iINF = 0x3f3f3f3f;
const long long INF = 1LL << 60;
using namespace std;

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()
{
  map<int, int> mp;
  int n;
  cin >> n;
  rep(i, n)
  {
    int x;
    cin >> x;
    mp[x]++;
  }

  vector<ll> v;
  for (auto mpi : mp)
  {
    if (mpi.second >= 2)
    {
      v.push_back(mpi.first);
      if (mpi.second >= 4)
      {
        v.push_back(mpi.first);
      }
    }
  }

  if (v.size() <= 1)
    cout << 0 << endl;
  else
    cout << v[v.size() - 1] * v[v.size() - 2] << endl;
  return 0;
}


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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)((n)-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
    for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
    if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
    int l = vv.size();
    if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n  " ) << vv[i] << (i==l-1 ? " ]" : ""); }
    return o;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p){
    return o << "(" << p.first << ", " << p.second << ")";
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

int cnt[100][100];
int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");

    int n; cin >> n;
    vl a(n),two(n),five(n);
    rep(i,n){
        string s; cin >> s;
        auto pos = s.find('.');
        if(pos == string::npos){
            a[i] = stol(s) * pow(10, 9);
        }else{
            s.replace(pos, 1, "");
            int d = 9 - (s.size() - pos);
            a[i] = stol(s) * pow(10, d);
        }
        ll x = a[i];
        while(x % 2 == 0) x /= 2, two[i]++;
        while(x % 5 == 0) x /= 5, five[i]++;
        cnt[two[i]][five[i]]++;
    }

    ll ans = 0;
    rep(i,n){
        int n2 = max(0ll, 18 - two[i]);
        int n5 = max(0ll, 18 - five[i]);
        REP(c2,n2,60) REP(c5,n5,30){
            ans += cnt[c2][c5];
        }
        if(n2 <= two[i] && n5 <= five[i]) ans--;
    }
    ans /= 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8000
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
d = na()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += d[i] * d[j]

print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<math.h>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<time.h>
#include<stdio.h>
using namespace std;
const int N=2*1e5+100;

int main()
{
   int n,k;
   cin>>n>>k;
   long long a[N];
   for(int i=0;i<n;i++){
    cin>>a[i];
   }
   for(int i=0,j=k;j<n;j++,i++){
    if(a[j]>a[i]){
        cout<<"Yes"<<endl;
    }
    else {
        cout<<"No"<<endl;
    }
   }
}

Measured memory_bytes: 5180
#pragma GCC optimize("O2")
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<cmath>
#include<climits>
#include<random>
#include <iomanip>
#include <bitset>
using namespace std;
 
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
 
/////////////////////////////////////////////
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
///////////////////////////////
#define int long long

const int N = 5e5 + 1;
const int mod = 1e9 + 7;
int fact[N];
int power(int a , int n){

	int res = 1;
	while(n){

		if(n&1)
			res*= a , res%=mod;
		a*=a;
		a%=mod;
		n/=2;
	}
	return res;
}
void init(){

	fact[0] = 1;
	for(int i = 1 ; i < N ; ++i)
		fact[i] = fact[i-1]*i%mod;
}

int ncr(int n , int r){

	int ans = fact[n];
	int val = fact[r]*fact[n-r];
	val%=mod;
	val = power(val , mod-2);
	ans*=val;
	ans%=mod;
	return ans;
}

void solve(){

	int n , m;
	cin>>n>>m;

	init();
	int ans = ncr(m , n)*fact[n];
	ans%=mod;
	int x = 0;
	int sign = 1;
	for(int i = 0 ; i <= n ; ++i){

		int k = m - i;
		int r = n - i;

		int val = ncr(k , r)*ncr(n , i);
		val%=mod;
		val*=fact[r];
		val%=mod;
		x+=sign*val; 
		if(x < 0)
			x += mod;
		if(x >= mod)
			x-=mod;
		sign = -sign;
	}
	cout<<x*ans%mod<<endl;
}
 
signed main(){
 
	fast;
	int t = 1;
	//cin>>t;
	for(int i = 1 ; i <= t ; ++i)
		solve();
}


Measured memory_bytes: 7556
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

const int MOD = 1e9+7; //998244353;

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int N = 2e6;
int k;
string _s;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  setF(N);
  cin  >> k >> _s;
  int s = sz(_s);
  ll ans = 0;
  ll a = modPow(26, k), b = 1, ra = modInv(26);
  FOR(i, 0, k+1){
    ans += comb(i+s-1, s-1)*b%MOD*a%MOD;
    a = a*ra%MOD;
    b = b*25%MOD;
  }
  cout << ans%MOD << endl;
}

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

int main(){
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;
  if(n%10==9 || n/10==9){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }  

  return 0;
}


Measured memory_bytes: 256
X = list(map(int, input().split()))
X.sort()
A, B, C = X
a, b, c = [x % 2 for x in X]

cnt = 0
if a == b:
    ope1 = C - B
    cnt += ope1
    B += ope1
    A += ope1
    cnt += (C - A) // 2
else:
    if c == a:
        C += 1
        A += 1
        cnt += 1

        cnt += (C - B) // 2
        cnt += (C - A) // 2
    else:
        C += 1
        B += 1
        cnt += 1

        cnt += (C - B) // 2
        cnt += (C - A) // 2

print(cnt)


Measured memory_bytes: 38384
import numpy as np

MOD = 998244353

N, M = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

def divideArr3(As, numD):
    arrA = np.array(As, dtype=np.int64)
    mask = (1<<numD) - 1
    arrA0 = arrA & mask
    arrA1 = (arrA>>numD) & mask
    arrA2 = arrA>>(2*numD)
    return arrA2, arrA1, arrA0

def convolveArr(arrA, arrB):
    L = len(arrA) + len(arrB) - 1
    lenFFT = 1 << ((L-1).bit_length())
    fA = np.fft.rfft(arrA, n=lenFFT)
    fB = np.fft.rfft(arrB, n=lenFFT)
    arrC = np.rint(np.fft.irfft(fA * fB, n=lenFFT)).astype(np.int64)
    return arrC[:L]

def convolveMOD(As, Bs, MOD):
    numD = 10
    div = 1<<numD
    arrA2, arrA1, arrA0 = divideArr3(As, numD)
    arrB2, arrB1, arrB0 = divideArr3(Bs, numD)

    arrC4 = convolveArr(arrA2, arrB2) % MOD
    arrC2 = convolveArr(arrA1, arrB1) % MOD
    arrC0 = convolveArr(arrA0, arrB0) % MOD
    arrC3 = (convolveArr(arrA2+arrA1, arrB2+arrB1) % MOD - arrC4 - arrC2) % MOD
    arrC1 = (convolveArr(arrA1+arrA0, arrB1+arrB0) % MOD - arrC2 - arrC0) % MOD
    arrC2 += (convolveArr(arrA2+arrA0, arrB2+arrB0) % MOD - arrC4 - arrC0) % MOD
    arrC2 %= MOD

    div2 = div*div%MOD
    div3 = div2*div%MOD
    div4 = div3*div%MOD
    arrAns = ((arrC4*div4)%MOD + (arrC3*div3)%MOD + (arrC2*div2)%MOD + (arrC1*div)%MOD + arrC0) % MOD
    return arrAns.tolist()

anss = convolveMOD(As, Bs, MOD)
print(' '.join(map(str, anss)))


Measured memory_bytes: 268960
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long 
#define REP(i, a, b) for (ll i = a; i < b; i++)
#define REPI(i, a, b) for (ll i = b - 1; i >= a; i--)
#define i_os ios::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);
#define INF (ll)1e18 + 100
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
#define MAX 1e6
/*SOME BITMASK KNOWLEDGE
1)x & (x - 1):sets the last one bit of x to zero
power of two exactly when x & (x − 1) = 0.
2)x & -x:sets all the one bits to zero, except last one bit
3)x | (x - 1):inverts all the bits after the last one bit*/
#define o_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define o_setll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
typedef tree<pair<ll, ll>,null_type,less<pair<ll, ll>>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set

int main() 
{ 
	ll n,k;
	cin>>n>>k;
	set<ll> s;
	REP(i,1,k+1){
		ll d;
		cin>>d;
		REP(j,1,d+1){
			ll l;
			cin>>l;
			s.insert(l);
		}
	}
	ll ct = n;
	for(auto it:s){
		ct--;
	}
	cout<<ct<<endl;
	return 0;	
}  


Measured memory_bytes: 3640
import sys

a = ""
l = []
for input in sys.stdin:
    a += input
l = a.split()
b = int(l[0])
l = l[1:]
for i in range(0,b):
    key = int(l[i])
    j = i - 1
    while(j >= 0 and int(l[j]) > key):
        l[j+1] = l[j]
        j = j - 1
    l[j+1] = key
    if(b > 0):
        for data in l:
            print int(data),
        print
    b = b-1


Measured memory_bytes: 4660
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

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

  int x;
  cin >> x;

  int cur = 0;
  int curI = 0;
  while(x > cur) {
    curI++;
    cur += curI;
  }

  cout << curI << endl;
  return 0;
}


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

int n, m, nn, ans[105][105], a;

int main()
{
    scanf("%d%d%d", &n, &m, &nn);
    int tmpx = 1, tmpy = 1;
    for(int i = 1;i <= nn;i++)
    {
        scanf("%d", &a);
        while(a--)
        {
            if(tmpx&1)
            {
                if(tmpy<=m)
                    ans[tmpx][tmpy] = i, tmpy++;
                else
                    tmpy--, tmpx++, a++;
            }
            else
            {
                if(tmpy >= 1)
                    ans[tmpx][tmpy] = i, tmpy--;
                else
                    tmpy++, tmpx++, a++;
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(j == 1)
                printf("%d", ans[i][j]);
            else
                printf(" %d", ans[i][j]);
        }
        puts("");
    }
    return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define rrep(i,n) for(int (i)=1;i<=(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};

int x, y, z, k;
int a[1010], b[1010], c[1010];

signed main() {
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	
	cin >> x >> y >> z >> k;
	rep(i, x) cin >> a[i];
	rep(i, y) cin >> b[i];
	rep(i, z) cin >> c[i];
	sort(a, a + x, greater<>());
	sort(b, b + y, greater<>());
	sort(c, c + z, greater<>());

	vector<int> sum;
	rep(i, x) {
		rep(j, y) {
			rep(l, z) {
				if((i+1)*(j+1)*(l+1) > k) break;
				sum.push_back(a[i]+b[j]+c[l]);
			}
		}
	}
	sort(all(sum), greater<>());
	rep(i, k) cout << sum[i] << endl;
	return 0;
}

Measured memory_bytes: 4308
#include<stdio.h>

int fibonatch(int);

int rp[50];

int main(){

int i,num;

for(i=0; i<50; i++) rp[i] = -1;

scanf("%d",&num);
printf("%d\n",fibonatch(num));

return 0;
}

int fibonatch(int num){
if(num==0||num==1) return rp[num]=1;
if(rp[num]!=-1) return rp[num];
return rp[num] = fibonatch(num-1)+fibonatch(num-2);
}

Measured memory_bytes: 596
from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0] * N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

for j in range(Q):
    p, x = map(int, input().split())
    count[p-1] += x

que = deque([0])
flag = [False] * N

while que:
    v = que.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e] += count[v]
        que.appendleft(e)

print(*count)


Measured memory_bytes: 56488
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int mod = 1000000007;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Integer v = map.get(s.charAt(i));
            if (v == null) {
                map.put(s.charAt(i), 2);
            } else {
                map.put(s.charAt(i), ++v);
            }
        }
        long ans = 1;
        for (Character key : map.keySet()
             ) {
            ans *= map.get(key);
            ans %= mod;
        }

        System.out.println(--ans);
    }
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, k;
  cin >> n >> k;
  
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a.at(i);
  
  vector<bool> dp(k + 1, false);
  for (int i = 0; i <= k; i++) {
    bool flag = false;
    for (int j = 0; j < n; j++) {
      if (i < a.at(j)) continue;
      else {
        if (dp.at(i - a.at(j)) == false) flag = true;
      }
    }
    dp.at(i) = flag;
  }
  
  if (dp.at(k)) cout << "First\n";
  else cout << "Second\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<=(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 文字変換　
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
// a内でx以上　auto iter = lower_bound(ALL(a), x);
// a内でxより大きい　auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned Euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return Euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int digit_sum(int n) {
  int sum=n%10;
  while(n!=0) {
    n/=10;
    sum+=n%10;
  }
  return sum;
}

vpll PrimeFactorization(ll n) {
  vpll res;
  for (ll i=2; i*i<=n; i++) {
    if(n%i!=0) continue;
    ll ex=0;
    while(n%i==0) {
      ex++;
      n/=i;
    }
    res.push_back(pll(i,ex));
  }
  if(n!=1) res.push_back(pll(n,1));
  return res;
}

int main() {
  int n;
  cin >> n;
  vi a(n+1);
  REP1(i,n) cin >> a[i];
  int s=1;
  vb check(n+1,false);
  int cnt=0;
  while(1) {
    if(check[s]) {
      cout << "-1" << endl;
      break;
    }
    check[s]=true;
    cnt++;
    s=a[s];
    if(s==2) {
      cout << cnt << endl;
      break;
    } 
  }
  return 0;
}


Measured memory_bytes: 3764
n, d = gets.strip.split.map(&:to_i)

arr = []

n.times do |a|
    arr << gets.strip.split.map(&:to_i)
end

# (n * (n - 1) / 2).times do |j|
    # n.times do |k|
    #     p arr[k]
    # end
# end 

ans = 0

(0..(n - 1)).each do |i|
    ((i + 1)..(n - 1)).each do |j|
        norm = 0

        (0..(d - 1)).each do |k|
            diff = arr[i][k] - arr[j][k]
            norm += diff * diff
        end


        (0..norm).each do |k|
            ans += 1 if k * k == norm
        end

    end
end

puts ans

Measured memory_bytes: 14180
#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
#define mod 1000000007
using namespace std;

ll dp[3005][3005];

string getLCS(string& s, string& t, ll len)
{
    string ans;
    ll i=0, j=0;
    
    while(len > 0)
    {
        if(s[i] == t[j])
        {
            ans.push_back(s[i]);
            i++;
            j++;
            len--;
        } else {
            if(dp[i+1][j] > dp[i][j+1])
            {
                i++;
            } else {
                j++;
            }
        }
    }
    return ans;
}

ll lenLCS(string& s, string& t, ll i, ll j)
{
    if(i >= s.length() || j >= t.length())
    {
        return 0;
    }
    if(dp[i][j] != -1)
    {
        return dp[i][j];
    }
    if(s[i]==t[j])
    {
        return dp[i][j] = 1+lenLCS(s, t, i+1, j+1);
    } else {
        return dp[i][j] = max(lenLCS(s, t, i, j+1), lenLCS(s, t, i+1, j));
    }
}

int main()
{
    string s, t;
    cin>>s>>t;
    memset(dp, -1, sizeof dp);
    ll len = lenLCS(s, t, 0, 0);
    //cout<<len<<endl;
    cout<<getLCS(s, t, len)<<endl;
    return 0;
}

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

public class Main {
	int n, m;
	int[] dp;

	int dp(int k) {
		if (0 <= dp[k]) {
			return dp[k];
		}
		if (k == 0) {
			return m;
		}

		int ret = 0;
		ret += dp(k - 1) * (m - 1);
		return dp[k] = ret;
	}

	void run() {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		dp = new int[n];
		Arrays.fill(dp, -1);

		System.out.println(dp(n - 1));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}


Measured memory_bytes: 9044
from math import factorial    #階乗計算
#print(math.factorial(5))   ->   120

N, M = map(int, input().split())
mod = 10**9+7

if abs(N-M)>=2:
    print(0)
    exit()

n = factorial(N)%mod
m = factorial(M)%mod
ans = n*m%mod

if N==M:
    print(ans*2%mod)
else:
    print(ans)

Measured memory_bytes: 4096
#include<stdio.h>
int main(void){
	int n,m;
	
	char str[1000];
	int i, j;
    int ans = 0;

	scanf("%d", &n);
	

	if(n == 3) {
		ans = 180;
	}
	else {
		ans =180+ 180 * (n - 3);
	}

	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;

bool checkStr(string str)
{
	if (str.length() != 6) return false;
	for (int i = 0; i < str.length(); i++) {
		if (islower(str[i]) == false) return false;
	}
	if (str[2] != str[3] || str[4] != str[5]) return false;
	return true;
}

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

	string str;
	cin >> str;
	if (checkStr(str)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int K, c;
    int sum;
    int i;
    
    while (1){
        scanf("%d", &K);
        if (K == 0){
            break;
        }
        
        sum = 0;
        for (i = 0; i < K * (K - 1) / 2; i++){
            scanf("%d", &c);
            sum += c;
        }
        
        printf("%d\n", sum / (K - 1));
    }
    
    return (0);
}

Measured memory_bytes: 600
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 1e18;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<double> P(N);
	REP(i, N)cin >> P[i];
	vector<vector<double> > dp(N + 1, vector<double>(N + 1,0));
	dp[0][0] = 1.0;
	REP(i, N) {
		REP(j, N)dp[i + 1][j] += dp[i][j] * (1-P[i]);
		REP(j, i + 1) {
			dp[i + 1][j + 1] += dp[i][j] * P[i];
		}
	}
	double ans = 0;
	FOR(i, (N + 1) / 2, N + 1) {
		ans += dp[N][i];
	}
	printf("%.10f\n", ans);
	PAU;
	return 0;
}


Measured memory_bytes: 70912
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;

#define int long long

int q,x,y;

bool check(int a)
{
	int i=max(1ll,(a>>1)-2),r=min(a,(a>>1)+2);
	for(;i<=r;++i)
		if((x+i)*(x+a-i)>=x*y)
			return false;
	return true;
}

void test()
{
	x=1;y=4;
	cout<<check(1);
}

signed main()
{
	//test();return 0;
	for(scanf("%lld",&q);q--;)
	{
		scanf("%lld%lld",&x,&y);
		if(x>y)
			swap(x,y);
		int left=0,mid,right=y-x,res=0;
		while(left<=right)
		{
			if(check(mid=(left+right)>>1))
				left=(res=mid)+1;
			else
				right=mid-1;
		}
		printf("%lld\n",((x-1)<<1)+res);
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

int main(){
	int a;
	while(scanf("%d",&a),a){
	int ans=0;
	for(int i=1;i<=sqrt(a*2);i++){
		if(i%2==0){
			if(a*2%i==0&&a%i!=0){
				ans++;
				//printf("%d OK!\n",i);
			}
		}
		else{
			if(a>=i*(i+1)/2&&a%i==0){
				ans++;
				//printf("%d OK!\n",i);
			}
		}
	}
	printf("%d\n",ans-1);
	}
}

Measured memory_bytes: 0
n = int(input())
S = n//3
mod=10**9+7
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res
 
ans = 0
if S>=1:
  for i in range(1,S+1):
    t = n - 3*i
    ans += combination(t+i-1,i-1)
  print(ans%mod)
    
    
else:
  print(0)

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

#define int long long
const int MAX_N = 100000;

int N, A[MAX_N];
vector<int> e[MAX_N];

int Solve(int n)
{
	vector<int> depths;
	for (int i = 0; i < e[n].size(); i++)
	{
		depths.push_back(Solve(e[n][i]));
	}
	sort(depths.begin(), depths.end());
	int res = 0;
	for (int i = 0; i < e[n].size(); i++)
	{
		res = max(res, depths[i] + (int)e[n].size() - i);
	}
	return res;
}

signed main()
{
	A[0] = -1;
	cin >> N;
	for (int i = 1; i < N; i++)
	{
		cin >> A[i]; A[i]--;
		e[A[i]].push_back(i);
	}
	printf("%lld\n", Solve(0));
	return 0;
}

Measured memory_bytes: 15872
n=int(input())
l=[]
for i in range(n):
    s,p=[x for x in input().rstrip().split()]
    l.append([s,int(p),i+1])
l.sort(key=lambda x:x[1],reverse=True)
l.sort(key=lambda x:x[0])


for i,x,z in l:
    print(z)




Measured memory_bytes: 3060
#include<stdio.h>

int main(){
	int i;
	int n;
	int a[100];
	int tmp;
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		a[i]=0;
		scanf("%d",&a[i]);
	}
	
	for(i=0;i<n/2;i++){
		tmp=a[i];
		a[i]=a[n-1-i];
		a[n-1-i]=tmp;
	}
	for(i=0;i<n;i++){
		printf("%d",a[i]);
		if(i!=n-1){
			printf(" ");
		}
	}
	printf("\n");
	
	return 0;
}

Measured memory_bytes: 600
import sys
input = sys.stdin.readline
sys.setrecursionlimit(4100000)

def main():
    N = int(input())
    d = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        d[a].append((b,i))
        d[b].append((a,i))

    ans = [0] * (N - 1) 

    def dfs(v, c, p):
        k = 1
        for i in range(len(d[v])):
            u = d[v][i][0]
            ei = d[v][i][1]
            if u == p:
                continue
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dfs(u,ans[ei],v)
    
    dfs(0,-1,-1)
    print(max(ans))
    for a in ans:
        print(a)

        

if __name__ == "__main__":
    main()

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

typedef long long ll;

const int N = 200005;
int n, p[N], fa[N], cnt[N][2];
ll rev[N];
bool vis[N];

int find(int x) {
	return !fa[x] ? x : fa[x] = find(fa[x]);
}
struct node {
	int x, c0, c1;
	ll r;
};
bool operator<(const node &a, const node &b) {
	return 1ll * a.c1 * b.c0 > 1ll * b.c1 * a.c0;
}
priority_queue<node> q;

int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; ++i)
		scanf("%d", p + i);
	int c[2] = {};
	for (int i = 1, x; i <= n; ++i) {
		scanf("%d", &x);
		++c[x];
		++cnt[i][x];
		q.push((node){i, cnt[i][0], cnt[i][1], 0ll});
	}
	ll ans = 0;
	while (!q.empty()) {
		node t = q.top(); q.pop();
		if (cnt[t.x][0] != t.c0 || cnt[t.x][1] != t.c1 || rev[t.x] != t.r)
			continue;
		if (t.x != 1 && !vis[find(p[t.x])]) {
			fa[t.x] = p[t.x];
			rev[find(t.x)] += 1ll * cnt[find(t.x)][1] * t.c0 + t.r;
			cnt[find(t.x)][0] += t.c0;
			cnt[find(t.x)][1] += t.c1;
			q.push((node){find(t.x), cnt[find(t.x)][0], cnt[find(t.x)][1], rev[find(t.x)]});
			continue;
		}
		vis[t.x] = true;
		c[0] -= t.c0, c[1] -= t.c1;
		ans += t.r + 1ll * t.c1 * c[0];
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main()
{
    int A, B, K;
    cin >> K >> A >> B;

    int i = 0;
    bool flag = false;

    while (K * i <= B)
    {
        if (K * i >= A)
        {
            flag = true;
        }
        i++;
    }

    if (flag)
        cout << "OK" << endl;
    else
        cout << "NG" << endl;
}

Measured memory_bytes: 3556
#include<bits/stdc++.h>
#define EM 100000000
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
LL LINF = 1e18;
int INF = 1e9;
using vint = vector<int>;
using vLL = vector<LL>;

int main(){
    string s;
    cin >> s;
    vector<int> ans(s.size(), 0);
    int l = 0;
    int m = 0;
    for(int i = 0;i < s.size()-1;i++){
        if(s[i] == 'R' && s[i+1] == 'L'){
            m = i;
            if(i == s.size()-2){
                i++;
                if((m-l)&1){ans[m+1] = (i-l+2)/2;ans[m] = i-l+1-ans[m+1];}
                else    {ans[m] = (i-l+2)/2;ans[m+1] = i-l+1-ans[m];}
            }
        }else if((s[i] == 'L' && s[i+1] == 'R') || i == s.size()-2){
            if(i == s.size()-2) i++;
            if((m-l)&1){ans[m+1] = (i-l+2)/2;ans[m] = i-l+1-ans[m+1];}
            else    {ans[m] = (i-l+2)/2;ans[m+1] = i-l+1-ans[m];}
            l = i+1;
            m = i+1;
        }
    }
    for(int i = 0;i < s.size();i++){
        cout << ans[i] << " ";
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  cin >> n;
  vector<i64> a(n + 1), b(n);
  for (i64 i = 0; i < n + 1; i++)
    cin >> a[i];
  for (i64 i = 0; i < n; i++)
    cin >> b[i];
  i64 ans = 0;
  for (i64 i = 0; i < n; i++)
  {
    ans += min(a[i], b[i]);
    b[i] -= min(a[i], b[i]);
    ans += min(a[i + 1], b[i]);
    a[i + 1] -= min(a[i + 1], b[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
int min(int a, int b)
{
  if(a>b) return b;
  else return a;
}
int main()
{
  int A, B, M;
  scanf("%d %d %d", &A, &B, &M);
  int a[A], b[B];
  for(int i=0;i<A;i++) scanf("%d", &a[i]);
  for(int i=0;i<B;i++) scanf("%d", &b[i]);
  int x[M], y[M], c[M];
  for(int i=0;i<M;i++) scanf("%d %d %d", &x[i], &y[i], &c[i]);  
  
  int amin=a[0], bmin=b[0];
  for(int i=0;i<A;i++) amin=min(amin,a[i]);
  for(int i=0;i<B;i++) bmin=min(bmin,b[i]);
  
  int nocou=amin+bmin;
  
  int cou[M];
  for(int i=0;i<M;i++) cou[i]=a[x[i]-1]+b[y[i]-1]-c[i];
  
  int ans = nocou;
  for(int i=0;i<M;i++) ans=min(ans, cou[i]);
  printf("%d", ans);
  return 0;
}
    

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] A = new int[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                A[i][j] = sc.nextInt();
            }
        }
        int[] b = new int[m];
        for(int i=0; i<m; i++){
            b[i] = sc.nextInt();
        }
        int[] c = new int[n];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                c[i] += A[i][j] * b[j];
            }
        }
        for(int i=0; i<n; i++){
            System.out.println(c[i]);
        }
    }
}    


Measured memory_bytes: 40976
#include<cstdio>
#include<algorithm> 
int n,k;
long long ans=0;
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		int x=n/i,r=n%i;
		ans=ans+1ll*x*std::max(0,i-k)+std::max(0,r-k+1);
		if (k==0) --ans;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 1700
#include <iostream>
#include <sstream>
#include <fstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include<iomanip>
#define sqr(x) (x)*(x)
#define ll long long
using namespace std;
ll num[300005],l[300005],r[300005],ans=-1152921504606846976,n,i,j;
priority_queue<ll,vector<ll>,greater<ll>/**/> le;
priority_queue<ll> ri;
int main()
{
	cin>>n;
	for (i=1;i<=n*3;i++)
	{
		cin>>num[i];
		if (i<=n) 
		{
			le.push(num[i]);
			l[n]+=num[i];
		}
		if (i>n*2) 
		{
			ri.push(num[i]);
			r[n+n+1]+=num[i];
		}
	}
	for (i=n+1;i<=n+n;i++)
	{
		l[i]=l[i-1];
		if (le.top()<num[i])
		{
			l[i]=l[i]-le.top()+num[i];
			le.pop();
			le.push(num[i]);
		}
	}
	for (i=n+n;i>n;i--)
	{
		r[i]=r[i+1];
		if (ri.top()>num[i])
		{
			r[i]=r[i]-ri.top()+num[i];
			ri.pop();
			ri.push(num[i]);
		}
	}
	for (i=n;i<=n+n;i++)
	{
		ans=max(ans,l[i]-r[i+1]);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7668
#include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<sstream>
#include<fstream>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
/*freopen{"input.txt","r",stdin};
freopen{"output.txt","w",stdout};*/
#define mp make_pair
#define pb push_back
const int INF=1000*1000*1000;
const int maxn=2e5; 
typedef long long ll;
typedef long double ld;
typedef pair<int,int>PII;
//priority_queue <int,vector<int>,greater<int> > q1;  //从小到大 
//priority_queue <int,vector<int>,less<int> >q2;  //从大到小 

int n;
int a[maxn];
map<int,int>odd,even;
map <int, int>::iterator it;
PII oddfirst,oddsecond,evenfirst,evensecond;

int main(){
	//ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	for(int i=0;i<n;i+=2){
		even[a[i]]++;
	}
	for(int i=1;i<n;i+=2){
		odd[a[i]]++;
	}
	odd[1e9]=0,even[1e9]=0;
	multimap<int,int>odd1,even1;
	for(auto g:odd){
		odd1.emplace(g.second,g.first);
	}
	for(auto g:even){
		even1.emplace(g.second,g.first);
	}
	
	/*for(auto g:odd1){
		cout<<g.first<<' '<<g.second<<endl;
	}
	for(auto g:even1){
		cout<<g.first<<' '<<g.second<<endl;
	}*/
	auto it=odd1.rbegin();
	oddfirst=mp(it->first,it->second);  //次数 大小 
	it++;
	oddsecond=mp(it->first,it->second);
    //cout<<oddfirst.first<<' '<<oddfirst.second<<endl;
    
    //cout<<oddsecond.first<<' '<<oddsecond.second<<endl;
	auto it1=even1.rbegin();
    evenfirst=mp(it1->first,it1->second); 
    it1++;
    evensecond=mp(it1->first,it1->second);
	//cout<<evenfirst.first<<' '<<evenfirst.second<<endl;
    //cout<<evensecond.first<<' '<<evensecond.second<<endl;
	ll ans=0;
	if(oddfirst.second!=evenfirst.second){
		ans=n-oddfirst.first-evenfirst.first;
	}
	else{
		int ans1,ans2;
		ans1=n-oddfirst.first-evensecond.first;
		ans2=n-evenfirst.first-oddsecond.first;
		ans=min(ans1,ans2);
	}
	cout<<ans;
	return 0;
}

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

int main()
{
    int n,a; cin >> n >> a;
    if (n%500 <= a) cout << "Yes" << endl;
    else cout << "No" << endl;
}

/*
Ctrl+@
g++ a.cpp
./a.out
*/

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int yen[]={6000,4000,3000,2000},n,t;
	for(int i=0;i<4;i++){
		int sum=0;
		cin>>t>>n;
		sum=yen[t-1]*n;
		cout<<sum<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160