akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = 1234567;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	int H,W;
	cin>>H>>W;
	int h,w;
	cin>>h>>w;
	cout<<(H-h)*(W-w)<<endl;
	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(now, par):
    global ans
    h = 0
    for child in g[now]:
        if child == par: continue
        h = max(h, dfs(child, now) + 1)
    if h == k - 1 and par != 0:
        ans += 1
        h = -1
    return h

n, k = map(int, raw_input().split())
a = map(int, raw_input().split())
g = [[] for _ in xrange(n)]
ans = 0
if a[0] != 1:
    a[0] = 1
    ans += 1
for i in xrange(n):
    g[a[i] - 1].append(i)
dfs(0, 0)
print ans


Measured memory_bytes: 152856
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        if (s.charAt(2) == s.charAt(3) && s.charAt(4) == s.charAt(5)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    int ab[2010] = {0};
    int ad[4010] = {0};

    for(int a = 0;a <= 1000;a++){
        for(int b = 0;b <= 1000;b++){
            ab[a+b]++;
        }
    }


    for(int a = 0;a <= 2000;a++){
        for(int b = 0;b <= 2000;b++){
            ad[a+b]+=ab[a]*ab[b];
        }
    }
     while(cin>>n){
        cout<<ad[n]<<endl;
     }
    return 0;
}

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define reps(i,s,e) for(int i=s; i<(int)e; i++)
#define coutd(i) cout << std::fixed << std::setprecision(i)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Set = std::set<T>;
template<class T, class U>
using Map = std::map<T, U>;

template<class T>
using Graph = vector<vector<T>>;

const int INT_BIG = 1<<28;
const int MOD = 1000000007;


// #include <iostream>

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr std::ostream& operator << (std::ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

int main() {
    // ooxxooxxxooo
    // oooooo
    // k-1Ci-1 * n-k+1Ci

    int N, K;
    cin >> N >> K;

    vector<Fp<MOD>> factorial(N+2);
    factorial[0] = 1;
    rep(i, N+1) {
        factorial[i+1] = factorial[i] * Fp<MOD>(i+1);
    }

    reps(i, 1, K+1) {
        if ( N-K+1-i >= 0) {
            cout << (factorial[K-1]/factorial[K-i]/factorial[i-1]) * (factorial[N-K+1]/factorial[N-K+1-i]/factorial[i]) << endl;
        } else {
            cout << 0 << endl;
        }
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<stdlib.h>
using namespace std;
int main(){
   int x[4];
   for(int i=0;i<3;i++)cin>>x[i];
   for(int i=0;i<3;i++){
       for(int j=0;j<2;j++){
           if(x[j]<x[j+1]){
               int hoge=x[j];
               x[j]=x[j+1];
               x[j+1]=hoge;
           }
       }
   }
  int ans=10*x[0]+x[1]+x[2];
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void) {
  int N, Y;
  cin >> N >> Y;
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= (N - i); j++) {
      if (10000 * i + 5000 * j + 1000 * (N - i - j) == Y) {
        cout << i << ' ' << j << ' ' << (N - i - j) << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
#define pb      push_back
#define all(v)  v.begin(),v.end()
#define see(x)  cout<<#x<<" : "<<(x)<<endl;
#define ya      cout<<"Yes"<<endl;
#define no      cout<<"No"<<endl;
#define ff      first
#define sc      second
typedef long long ll;
typedef pair<ll,ll> pii;

int main()
{

    ll n;
    double dis,a,b,c;
    cin>>n>>c;
    ll ans=0;
    while(n--)
    {
        cin>>a>>b;
        if(sqrt(a*a+b*b)<=c)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3844
unittest
{
	assert( [ "2 7" ].parse.expand.solve == 4 );
	assert( [ "1 1" ].parse.expand.solve == 0 );
	assert( [ "50 4321098765432109" ].parse.expand.solve == 2160549382716056 );
}



import std.algorithm;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nx = input.front.split.to!( long[] );
	return tuple( nx[ 0 ], nx[ 1 ] );
}

long solve( long n, long x )
{
	auto ans = 0L;
	
	// レベルnのときの全層数と全パティ数を計算
	auto tl = memoize!calcTotalLayer( n );
	auto tp = memoize!calcTotalPatty( n );

	// xが全層数以上の場合、食べたパティ数は全パティ数になる。
	if( tl <= x ) return tp;
	
	// xが全層数の半分と等しい場合、食べたパティ数は全パティ数の半分になる。
	auto hl = cast( long ) ceil( tl / 2f );
	if( x == hl ) return cast( long ) ceil( tp / 2f );
	
	// xが全層数の半分より大きい場合、上の層から数えて、全層数から数えた分を引く
	// （こうすると最大でも全層数の半分まで数えれば済むようになる）
	if( hl < x ) return tp - memoize!solve( n, tl - x );
	
	// xが全層数の半分より小さい場合、下の層から数える
	auto l = 0L;
	auto p = 0L;
	
	// バンズ1枚
	l++;
	if( x <= l ) return p;
	
	// レベルn-1バーガー
	p += memoize!solve( n - 1, x - l );
	l += memoize!calcTotalLayer( n - 1 );
	if( x <= l ) return p;
	
	// パティ1枚
	p++;
	l++;
	if( x <= l ) return p;
	
	// レベルn-1バーガー
	p += memoize!solve( n - 1, x - l );
	l += memoize!calcTotalLayer( n - 1 );
	if( x <= l ) return p;
	
	// バンズ1枚
	l++;
	return p;
}

long calcTotalLayer( long n )
{
	if( n == 0 ) return 1;
	else         return memoize!calcTotalLayer( n - 1 ) * 2 + 3;
}

long calcTotalPatty( long n )
{
	if( n == 0 ) return 1;
	else         return memoize!calcTotalPatty( n - 1 ) * 2 + 1;
}


Measured memory_bytes: 256
import sys
import collections as col
import bisect
import numpy as np


def main():
    n = int(input())
    aarray = [int(e) for e in input().split()]
    aarray.sort()
    record = []
    endpoint = max(1, bisect.bisect(aarray, 0))
    aqueue = col.deque(aarray)
    while len(aqueue) > endpoint + 1:
        amax = aqueue.pop()
        amin = aqueue.popleft()
        record.append((amin, amax))
        aqueue.appendleft(amin - amax)
    amax = aqueue.pop()
    while len(aqueue) > 0:
        amin = aqueue.popleft()
        record.append((amax, amin))
        amax -= amin
    print(amax)
    for r in record:
        print(r[0], r[1])


main()


Measured memory_bytes: 28768
#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l),i##R=(r);i<=i##R;i++)
#define DOR(i,r,l) for(int i=(r),i##L=(l);i>=i##L;i--)
#define loop(i,n) for(int i=0,i##R=(n);i<i##R;i++)
#define sf scanf
#define pf printf
#define mms(a,x) memset(a,x,sizeof a)
using namespace std;
typedef long long ll;
template<typename A,typename B>inline void chkmax(A &x,const B y){if(x<y)x=y;}
template<typename A,typename B>inline void chkmin(A &x,const B y){if(x>y)x=y;}
const int N=25;
int main(){
	int L,R;
	sf("%d%d",&L,&R);
	if(R-L>2019)puts("0");
	else {
		int ans=1e9;
		FOR(i,L,R)FOR(j,i+1,R)
			chkmin(ans,(int)(1ll*i*j%2019));
		pf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define ub upper_bound
#define lb lower_bound
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;


signed main(){
  int n;
  int M[12][12];
  while(cin>>n,n){
    rep(i,n)rep(j,n)cin>>M[i][j];
    rep(i,n){
      int tmp=0;
      rep(j,n)tmp+=M[i][j];
      M[i][n]=tmp;
    }
    rep(i,n){
      int tmp=0;
      rep(j,n)tmp+=M[j][i];
      M[n][i]=tmp;
    }
    int tmp=0;
    rep(i,n)tmp+=M[n][i];
    M[n][n]=tmp;
    rep(i,n+1){
      rep(j,n+1)cout<<setw(5)<<M[i][j];
      cout<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3164
// D - XXOR

// 一致しない桁を全探索する解法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

// 常に50桁で考える（実際は40ビットで十分）
ll A[100000];
ll B[51]; // S[i][j]: Kの左からi桁目がjのときのfの各Aのi桁目が1の数
ll S[51][2]; // S[i][j]: Kの左からi桁目がjのときのfの各Aのi桁目が表す数の和
ll k[51]; // Kのi桁目のビット

int main() {
	ll N, K;
	cin >> N >> K;

	for (int i=0; i<N; i++) {
		ll A;
		cin >> A;
		for (int i=50; i>=1; i--) {
			B[i] += A % 2;
			A /= 2;
		}
	}

	/*
	// **** debug ****
	for (int i=0; i<=50; i++) {
		cout << "B[" << i << "] = " << B[i] << endl;
	}
	*/

	for (int i=1; i<=50; i++) {
		S[i][0] = B[i] * pow(2, 50-i);
		S[i][1] = (N - B[i]) * pow(2, 50-i);
	}

	/*
	// **** debug ****
	for (int i=0; i<=50; i++) {
		cout << "S[" << i << "][0] = " << S[i][0] << endl;
		cout << "S[" << i << "][1] = " << S[i][1] << endl;
	}
	*/

	for (int i=50; i>=1; i--) {
		k[i] = K % 2;
		K /= 2;
	}

	ll ans = 0;
	// X = K（すべて一致）の場合
	for (int i=1; i<=50; i++) {
		ans += S[i][k[i]];
	}

	//cout << "X=K: " << ans << endl; // **** debug ****

	// X と K が 左からi桁目でX[i] < K[i] の場合
	bool ignore = true;
	for (int i=1; i<=50; i++) {
		if (k[i]) ignore = false;
		if (ignore) continue; // X > K は対象外
		if (k[i] == 0) continue;

		ll candidate = 0;

		// iより左
		for (int j=1; j<i; j++) {
			candidate += S[j][k[j]]; // 一致
		}

		// i
		candidate += S[i][0]; // X[i] < K[i]

		// iより右
		for (int j=i+1; j<=50; j++) {
			candidate += max(S[j][0], S[j][1]); // どちらでも
		}

		//cout << "i=" << i << " " << candidate << endl; // **** debug ****

		ans = max(ans, candidate);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4108
from math import log2
import time
import sys

MOD = 10 ** 9 + 7

def lca(u, v):
    if level[u] < level[v]: u, v = v, u

    up = int(log2(level[u]))
    while up >= 0:
    	if level[u] - (1 << up) >= level[v]:
    		u = par[u][up]
    	up -= 1

    if u == v: return v

    up = int(log2(level[u]))
    while up >= 0:
    	if par[u][up] and par[v][up] != par[u][up]:
    		u, v = par[u][up], par[v][up]
    	up -= 1

    return par[u][0]

n = int(input())

adj = {}
u = 0
for _ in range(n):
    c, *v_list = [int(item) for item in sys.stdin.readline().strip().split()]
    adj[u] = []
    for v in v_list:
        adj[u].append(v)
    u += 1

start = 0

Q = [start]
done = [0] * (n + 1)
par = [[0] * (int(log2(n)) + 1) for _ in range(n + 1)]
level = [0] * (n + 1)
level[start] = 1

while Q:
    current = Q.pop()
    for nxt in adj[current]:
        if done[nxt]: continue
        done[current] = 1
        level[nxt] = level[current] + 1
        par[nxt][0] = current
        Q.append(nxt)

lvl = 1
while (1 << lvl) < n:
	for i in range(0, n):
		if par[i][lvl - 1]: par[i][lvl] = par[par[i][lvl - 1]][lvl - 1]
	lvl += 1

q = int(input())
for _ in range(q):
	u, v = [int(item) for item in sys.stdin.readline().strip().split()]
	_lca = lca(u, v)
	print(_lca)



Measured memory_bytes: 53472
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int mod = 1e9 + 7;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll N, M;
	cin >> N >> M;
	ll factN = 1, factM = 1;
	for (ll i = 1; i <= N; i++)
		factN = factN * i % mod;
	for (ll i = 1; i <= M; i++)
		factM = factM * i % mod;
	if (N + 1 == M || M + 1 == N)
		cout << (ll) factN * factM % mod << endl;
	else if (N == M)
		cout << (ll) 2 * factM * factN % mod;
	else
		cout << 0 << endl;

}



Measured memory_bytes: 3620
import sys
import heapq, functools, collections, itertools
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(grid,k):  # fix inputs here
    console(grid)
    grid = [[1 if x == "#" else 0 for x in row] for row in grid]
    console("----- solving ------")
    console(grid)

    res = 0

    for arr in itertools.product([0,1], repeat=len(grid)+len(grid[0])):
        cnt = 0
        for i,row in enumerate(grid):
            for j,cell in enumerate(row):
                if arr[i] == 0 and arr[-j-1] == 0 and cell == 1:
                    cnt += 1
        if cnt == k:
            res += 1
        # print(arr, res, cnt)
    
    return res


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    nrows,_,k = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for _ in range(nrows):
        grid.append(input())

    res = solve(grid,k)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)


Measured memory_bytes: 77904
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD = 10 ** 9 + 7


W, H, N = MI()
m = [0, 0, W, 0, H]
for _ in range(N):
    x, y, a = MI()
    if a == 1:
        m[a] = max(m[a], x)
    elif a == 2:
        m[a] = min(m[a], x)
    elif a == 3:
        m[a] = max(m[a], y)
    else:
        m[a] = min(m[a], y)
print(max(0, m[2] - m[1]) * max(0, m[4] - m[3]))

Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            int x = sc.nextInt();
            int w = 0;
            if(n==0&&x==0) break;
            for(int i=1;i<=n-2;i++){
                for(int j=i+1;j<=n-1;j++){
                    for(int k=j+1;k<=n;k++){
                        if(i+j+k==x) w++;
                    }
                }    
            }
            System.out.println(w);
        }
        sc.close();
    }
}


Measured memory_bytes: 26316
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <climits>
#include <iomanip>
#define endl "\n"
#define debug(x) cout << #x << " : " << x << endl;
#define debug2(x, y) cout << #x << " : " << x  << ", " << #y << " : " << y << endl;
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0);
typedef long long ll;
using namespace std;

int main()
{
	FASTIO

	ll n;
	cin >> n;

	ll maxm = 0;
	ll ans = 0;
	for(ll i = 0; i < n; i ++)
	{
		ll val;
		cin >> val;

		if(val > maxm)
			maxm = val;
		else
			ans += (maxm - val);
	}	

	cout << ans << endl;
}

Measured memory_bytes: 3652
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        親が同じか判別する
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        yをxの根に繋ぐ
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n, m = map(int, input().split())
    edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    uf = UnionFind(n)
    res = [(n - 1) * n // 2]
    for i in reversed(range(1, m)):
        a, b = edge[i]
        if not uf.same(a, b):
            res.append(res[-1] - uf.size(a) * uf.size(b))
            uf.union(a, b)
        else:
            res.append(res[-1])
    print(*res[::-1], sep="\n")


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 33620
import java.util.*;


public class Main {
    public static void call(int n){
        int i = 1;
        do {
            int x = i;
            if ( x % 3 != 0 ){
                while( x != 0 ){
                    if ( x % 10 == 3 ){
                        System.out.printf(" %d", i);
                        break;
                    }
                    x /= 10;
                }
    
            } else {
                System.out.printf(" %d", i);
            }
        } while(++i <= n);
        System.out.println();
    }
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        call(n);
    }
}



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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
const ll INF = 1001001001;

const int mod = 1000000007;

struct mint {
    ll x;

    mint(ll x = 0) : x(x % mod) {}

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
};


mint dp0[2005][2005];
mint dp1[2005][2005];

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

    vector<int> s(n + 1), t(m + 1);
    rep(i, n)scanf("%d", &s[i]);
    rep(i, m)scanf("%d", &t[i]);
    dp0[0][0] = 1;

    rep(i, n + 1)
        rep(j, m + 1) {
            dp0[i + 1][j] += dp0[i][j];
            dp1[i][j] += dp0[i][j];
            dp1[i][j + 1] += dp1[i][j];
            if (s[i] == t[j]) {
                dp0[i + 1][j + 1] += dp1[i][j];
            }
        }
    mint ans = dp1[n][m];
    cout << ans.x << endl;
}


Measured memory_bytes: 63104
#include <algorithm>
#include <stdio.h>

int main(){
    int input_P[20];
    int input_N;
    int output_numP = 0;
    
    scanf("%d", &input_N);
    for(int count = 0; count < input_N; count++){
        scanf("%d", &input_P[count]);
    }

    for(int count = 1; count < input_N - 1; count++){
        // printf("\n%d ", input_P[count]);

        if( std::min( input_P[count - 1], std::min( input_P[count] , input_P[count+1]) ) < input_P[count] 
            && std::max( input_P[count - 1], std::max( input_P[count] , input_P[count+1]) ) > input_P[count]){
            
            // printf("%d ", input_P[count]);
            output_numP++;
        }
    }

    printf("%d", output_numP);

    return(0);
}

Measured memory_bytes: 128
fn main() {
    let (n, k, v) = read();
    let ans = solve(n, k, v);
    write(ans);
}

fn read() -> (i32, i32, Vec<i32>) {
    let mut l1 = String::new();
    std::io::stdin().read_line(&mut l1).ok();
    let mut iter = l1.trim().split_whitespace();
    let n: i32 = iter.next().unwrap().parse().unwrap();
    let k: i32 = iter.next().unwrap().parse().unwrap();

    let mut l1 = String::new();
    std::io::stdin().read_line(&mut l1).ok();
    let iter = l1.trim().split_whitespace();
    let mut v = Vec::<i32>::new();
    for i in iter {
        v.push(i.parse().unwrap());
    }

    (n, k, v)
}

fn write(s: i32) {
    println!("{}", s);
}

fn solve<'a>(n: i32, k: i32, mut v: Vec<i32>) -> i32 {
    v.sort();
    let s = v.iter().take(k as usize).sum();
    s
}

Measured memory_bytes: 2116
#include<stdio.h>
int R=1,C=1,H[2000010],N[2000010];
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
int main(){
  int n,m,i,j,d[300010];
  long long max=-1e18,a[300010],b[300010];
  scanf("%d",&n);
  m=3*n-1;
  for(i=0;i<3*n;i++)scanf("%d",&d[i]);
  for(i=0;i<3*n;i++)a[i]=b[i]=0;
  //kimeuti
  //for(i=0;i<3*n;i++)printf("%4lld %4lld\n",a[i],b[i]);printf("\n");
  for(i=0;i<n;i++){
    hin(d[i]);
    a[i]+=d[i];
    a[i+1]+=a[i];
  }
  //for(i=0;i<3*n;i++)printf("%4lld %4lld\n",a[i],b[i]);printf("\n");
  for(i=n;i<2*n;i++){
    hin(d[i]);
    a[i]+=d[i];
    a[i]-=N[hout()];
    a[i+1]+=a[i];
  }
  R=C=1;
  for(i=0;i<n;i++){
    hin(-d[m-i]);
    b[m-i]+=d[m-i];
    b[m-i-1]+=b[m-i];
  }
  for(i=n;i<2*n;i++){
    hin(-d[m-i]);
    b[m-i]+=d[m-i];
    b[m-i]+=N[hout()];
    b[m-i-1]+=b[m-i];
  }
  //for(i=0;i<3*n;i++)printf("%4lld %4lld\n",a[i],b[i]);
  for(i=0;i<=n;i++){
    if(max<a[i+n-1]-b[i+n])max=a[i+n-1]-b[i+n];
  }
  printf("%lld\n",max);
  return 0;
}
    
    


Measured memory_bytes: 10880
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(),(v).end())
#define RSORT(v) sort((v).rbegin(),(v).rend())
const ll MOD = 1000000007;

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}


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

void solve(std::string A, std::string B, std::string C){
    if(A[A.size()-1] == B[0] && B[B.size()-1] == C[0]){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
}

int main(){
    std::string A;
    std::cin >> A;
    std::string B;
    std::cin >> B;
    std::string C;
    std::cin >> C;
    solve(A, B, C);
    return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

struct node {ll x, y;} A[53], B[53];

int n, m;

ll dis(int xx, int yy) {return abs(A[xx].x - B[yy].x) + abs(A[xx].y - B[yy].y);}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> A[i].x >> A[i].y;
	for (int i = 1; i <= m; ++i) cin >> B[i].x >> B[i].y;
	for (int i = 1; i <= n; ++i) {
		ll di = dis(i, 1); int id = 1;
		for (int j = 2; j <= m; ++j)
			if (dis(i, j) < di) {
				di = dis(i, j);
				id = j;
			}
		printf("%d\n", id);
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner seer = new Scanner(System.in);
		int n = seer.nextInt();
		int k = seer.nextInt();
		for(int i = 0; i < n; i++){
			seer.nextInt();
		}
		System.out.println((int)Math.ceil((n-1)*1.0/(k-1)));
	}
}


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

using namespace std;

const int maxn = 101;
short f[maxn][maxn][maxn][maxn],sum1[maxn][maxn],sum2[maxn][maxn];
char s[maxn][maxn];
int n,m,sx,sy;

short Max(short a,short b)
{
    if (a > b)
        return a;
    return b;
}

void solve()
{
    int l1 = sx - 1,r1 = n - sx,l2 = sy - 1,r2 = m - sy; //上下左右
    for (int i = 0; i <= l1; i++)
        for (int j = 0; j <= r1; j++)
            for (int p = 0; p <= l2; p++)
                for (int q = 0; q <= r2; q++)
                {
                    int L = max(q + 1,sy - p),R = min(m - p,sy + q);
                    if (L <= R)
                    {
                        f[i + 1][j][p][q] = Max(f[i + 1][j][p][q],f[i][j][p][q] + (sx - i - 1 >= j + 1 ? sum1[sx - i - 1][R] - sum1[sx - i - 1][L - 1] : 0));
                        f[i][j + 1][p][q] = Max(f[i][j + 1][p][q],f[i][j][p][q] + (sx + j + 1 <= n - i ? sum1[sx + j + 1][R] - sum1[sx + j + 1][L - 1] : 0));
                    }
                    L = max(j + 1,sx - i),R = min(n - i,sx + j);
                    if (L <= R)
                    {
                        f[i][j][p + 1][q] = Max(f[i][j][p + 1][q],f[i][j][p][q] + (sy - p - 1 >= q + 1 ? sum2[R][sy - p - 1] - sum2[L - 1][sy - p - 1] : 0));
                        f[i][j][p][q + 1] = Max(f[i][j][p][q + 1],f[i][j][p][q] + (sy + q + 1 <= m - p ? sum2[R][sy + q + 1] - sum2[L - 1][sy + q + 1] : 0));
                    }
                }
    /*
    for (int i = 0; i <= l1; i++)
        for (int j = 0; j <= r1; j++)
            for (int p = 0; p <= l2; p++)
                for (int q = 0; q <= r2; q++)
                    cout << i << " " << j << " " << p << " " << q << " " << f[i][j][p][q] << endl;
                */
    cout << f[l1][r1][l2][r2] << endl;
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s",s[i] + 1);
        for (int j = 1; j <= m; j++)
            if (s[i][j] == 'E')
            {
                sx = i;
                sy = j;
            }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            sum1[i][j] = sum1[i][j - 1];
            sum2[i][j] = sum2[i - 1][j];
            if (s[i][j] == 'o')
                sum1[i][j]++,sum2[i][j]++;
        }
    solve();

    return 0;
}


Measured memory_bytes: 201088
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long int n;cin>>n;
  long long int ans =0 ;
  for(long long int j=1;j<=n;j++){
    long long int k = n /j;
    ans+=(j*(k)*(k+1))/2;
  }
  cout<<ans<<endl;
}
    


Measured memory_bytes: 3604
#include <iostream>
#include <iomanip>
/*cout <<setprecision(11)<<ret<<endl;で、数字部分を計11桁表示*/
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//Shift+Command+bでデバッグ
//その後ターミナルで./a.outを実行
//入力を貼り付ける

//////////////////
//  A
/*int main(void){
    vector<int> a(3);
    cin>>a[0]>>a[1]>>a[2];

    sort(a.begin(),a.end());

    cout<<a[0]+a[1]<<endl;
    return 0;
}*/
//////////////////
//  B
int main(void){
    int n,sum=0;cin>>n;
    vector<int> a(n);

    rep(i,n){
        cin>>a[i];
        sum+=a[i];
    }
    int tmpsum=0,mini=sum;
    rep(i,n){
        tmpsum+=a[i];
        mini=min( mini, abs(tmpsum-(sum-tmpsum)) );
    }
    cout<<mini<<endl;
    return 0;
}
//////////////////
//  C
/*int main(void){

    return 0;
}*/
//////////////////
//  D
/*int main(void){

    return 0;
}*/
//////////////////
//  E
/*int main(void){

    return 0;
}*/
//////////////////
//  F
/*int main(void){

    return 0;
}*/


Measured memory_bytes: 3556
#include<stdio.h>
int main()
{
    int A,B,c,K;
    scanf("%d %d",&A,&B);
    c=A+B;
    if(c%2==0)
    {
        K=c/2;
        printf("%d\n",K);
    }
    else
    {
        printf("IMPOSSIBLE\n");
    }

   return 0;
}


Measured memory_bytes: 1736
import numpy as np

n=int(input())
if n==1:
  print(0)
else:
  def factorization(n):
      arr = []
      temp = n
      for i in range(2, int(-(-n**0.5//1))+1):
          if temp%i==0:
              cnt=0
              while temp%i==0:
                  cnt+=1
                  temp //= i
              arr.append([i, cnt])
 
      if temp!=1:
          arr.append([temp, 1])
 
      if arr==[]:
          arr.append([n, 1])
 
      return arr
 
  y=factorization(n)
  def judge(y):
    i=1
    while np.arange(i+2).sum()<=y:
      i+=1
    return i
  ans=0
  for i in range(len(y)):
    ans+=judge(y[i][1])
  print(ans)


Measured memory_bytes: 27200
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


int main()
{
	ll x;
	cin >> x;

	ll y = 100;
	ll res = 0;
	while (y < x)
	{
		y = y + y * 0.01;
		res++;
	}

	println(res);
}

Measured memory_bytes: 3584
h ,w = map(int,input().split())
p = []
cou = 0

for i in range(h):
    s = list(input())
    if s.count("#") != 0:
        p.append(s)
        cou += 1

q = {i for i in range(w)}

for i in range(cou):
    kar = set()
    for j in range(w):
        if p[i][j] == ".":
            kar.add(j)
    q = q & kar
    
s = {i for i in range(w)}
s = s - q
    
for i in range(cou):
    for j in s:
        print(p[i][j],end="")
    print()

Measured memory_bytes: 4596
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll ac(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
int D;
vector<int> c(26);
vector<int> last(26, 0);
vector<vector<int>> s(365, vector<int>(26));
void input();
int score;
int next_num;
const int Way = 20;
const int Nest = 3;
/*void dfs(int nest, int d) {
	int M = 0, temp = score;
	int prev, n;
	vector<pair<int, int>> kouho(26);
	rep(j, 0, 26) {
		score = temp;
		score += s[d - 1][j];
		prev = last[j];
		last[j] = d;
		rep(k, 0, 26)score -= c[k] * (d - last[k]);
		kouho[j].first = score;
		kouho[j].second = j;
		last[j] = prev;
	}
	//sort(all(kouho), greater<pair<int, int>>());
	rep(j, 0, Way) {
		//prev = last[kouho[j].second];
		//last[kouho[j].second] = d;
		score = kouho[j].first;
		if (nest && d < D)dfs(nest - 1, d + 1);
		if (M < score)M = score, n = kouho[j].second;
		printf("j:%2d score:%d\n", j, score);
		//last[kouho[j].second] = prev;
	}
	score = M;
	next_num = n;
}*/
int dfs(int nest, int i) {
	ll M = -1 << 30, temp = score;
	int prev, p;
	vector<pair<int, int>> kouho(26);
	rep(j, 0, 26) {
		score = temp + s[i - 1][j];
		rep(k, 0, 26)if (j != k)score -= c[k] * (i - last[k]);
		kouho[j].first = score;
		kouho[j].second = j;
	}
	sort(all(kouho), greater<pair<int, int>>());
	rep(j, 0, Way){
		score = kouho[j].first;
		prev = last[kouho[j].second];
		last[kouho[j].second] = i;
		if (nest && i < D)dfs(nest - 1, i + 1);
		last[kouho[j].second] = prev;
		if (M < score)M = score, p = kouho[j].second;
	}
	score = M;
	return p;
}
int main()
{
	input();
	/*rep(i, 1, D + 1) {
		//score = 0;
		dfs(Nest, i);
		printf("%d\n", next_num + 1);
		last[next_num] = i;
		printf("%d\n", score);
	}*/
	rep(i, 1, D + 1) {
		score = 0;
		int p = dfs(Nest, i);
		last[p] = i;
		printf("%d\n", p + 1);
		//printf("%d\n", score);
	}
	return 0;
}
void input() {
	cin >> D;
	rep(i, 0, 26)cin >> c[i];
	rep(i, 0, D) {
		rep(i2, 0, 26)cin >> s[i][i2];
	}
}

Measured memory_bytes: 3788
a, b, c, x, y = map(int, input().split())
prc = 10**10
for i in range(max(x, y) * 2 + 1):
    prc = min(max(x - i // 2, 0) * a + max(y - i // 2, 0) * b + i * c, prc)
print(prc)

Measured memory_bytes: 8908
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;
void f(){
 int n;
 LL ans = 0;
 cin >> n;
 vector<int> in(n);

 forn(i,n){
     cin >> in.at(i);
     ans += in.at(i) - 1;
 }
 cout << ans << endl;
}
   
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    
  f();
 return 0;
}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;


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

  return 0;
}

Measured memory_bytes: 256
from operator import itemgetter
n, m = map(int, input().split())
lis = []
for i in range(n):
    lis.append(list(map(int, input().split())))

lis = sorted(lis, key = itemgetter(0))
#print(lis)
money = 0
cnt = 0
for i in range(n):
    money += lis[i][0] * lis[i][1]
    cnt += lis[i][1]
    #print(money)
    if cnt >= m:
        money -= (cnt-m) * lis[i][0]
        break
print(money)

Measured memory_bytes: 29740
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 510000;
const int MOD = 1000000007;

        signed main() {
        int n,j,ans=0;
        cin>>n;
        int m[100]={};
       for(int i=1;i<=n;i++){
           j=i;
           while(j>=10)j/=10;
           m[i%10+j*10]++;
       }
       for(int i=1;i<10;i++){
           for(int j=1;j<10;j++){
               ans+=m[i*10+j]*m[j*10+i];
           }
       }
       cout<<ans;
         return 0;

        }


Measured memory_bytes: 256
import std.stdio,std.conv, std.algorithm, std.container,std.array,std.range,std.string,std.typecons;
const dx = [1,0,-1,0];
const dy = [0,1,0,-1];
void read(T...)(auto ref T args){ 
	auto line = readln().split(); 
	foreach(i,ref arg; args) arg = line[i].to!(typeof(arg));
}
int sum(int n){return n * (n + 1)/ 2;}
int tax(int per,int yen) {return cast(int)(yen * (100 +per) / 100);}
void main(){
	int x,y,s;
	while(read(x,y,s),x|y|s){
		int ans ;
		foreach(i;1..s){
			foreach(j;i..s){
				if (tax(x,i) + tax (x,j) == s ){
					ans = max(ans,tax(y,i) + tax(y,j));
				}	
			}
		}
		ans.writeln;
	}
}

Measured memory_bytes: 2448
#include <stdio.h>
int main(){
  int a, b, c, d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  if	 ( a+b > c+d ){ printf("Left\n");     }
  else if( a+b < c+d ){ printf("Right\n");    }
  else				  { printf("Balanced\n"); }
  return 0;
}

Measured memory_bytes: 1648
#include <bits/stdc++.h>
#define FOR(i, n) for (long long i = 0; i < (n); ++i)
#define pb push_back
#define int long long
#define debug(x) std::cout << #x << ": " << x << '\n';
typedef long long ll;
const int N = 2e5 + 10;
int a[N];

signed main() {
    std::ios::sync_with_stdio(false);
    int n;
    std::cin >> n;
    std::unordered_map<int,int> cnt;
    FOR(i, n) {
    	std::cin >> a[i];
    	cnt[a[i]]++;
    }
    int answ = 0;
    FOR(lg, 31) {
    	ll x = (1ll << (31 - lg));
    	FOR(i, n) {
    		if (cnt[a[i]] != 0 && cnt.find(x - a[i]) != cnt.end()) {
    			if (x - a[i] == a[i]) {
    				if (cnt[x - a[i]] >= 2) {
    					cnt[x - a[i]] -= 2;
    					answ++;
    				}
    			}
    			else if (cnt[x - a[i]] >= 1){
    				cnt[a[i]]--;
    				cnt[x - a[i]]--;
    				answ++;
    			}
    		}
    	}
    }
    std::cout << answ;
}

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

vector<int> G[200010];
const ll MOD = ll(1e9 + 7);

ll modpow(ll x, ll y, ll m){
	if(y == 0) return 1;
	ll res = modpow(x, y / 2, m);
	return res * res % m * (y & 1 ? x : 1) % m;
}

int cnt[200010];

struct S{
	ll none, one, over;
	S() : none(1), one(1), over(0){}
};

deque<S> dp[200010];

deque<S>* g(int v, int d){
	cnt[d]++;

	if(G[v].size() == 0){
		dp[v].push_back(S());
		return &dp[v];
	}

	deque<S>* ret = nullptr;
	for(auto c : G[v]){
		auto res = g(c, d + 1);
		if(ret == nullptr) ret = res;
		else{
			if(ret->size() < res->size()) swap(ret, res);

			for(int i = 0; i < res->size(); i++){
				S s, s1 = (*ret)[i], s2 = (*res)[i];
				ll sum1 = 0, sum2 = 0;
				sum1 = (s1.none + s1.one + s1.over) % MOD;
				sum2 = (s2.none + s2.one + s2.over) % MOD;
				s.none = s1.none * s2.none % MOD;
				s.one = (s1.one * s2.none % MOD + s1.none * s2.one % MOD) % MOD;
				s.over = (sum1 * sum2 % MOD - s.none - s.one + 2 * MOD) % MOD;
				(*ret)[i] = s;
			}
			res->clear();
		}
	}
	for(int i = 0; i < ret->size(); i++){
		if((*ret)[i].over == 0) break;
		(*ret)[i].none += (*ret)[i].over;
		(*ret)[i].none %= MOD;
		(*ret)[i].over = 0;
	}
	ret->push_front(S());
	return ret;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N;
	cin >> N;
	for(int i = 1; i <= N; i++){
		int p;
		cin >> p;
		G[p].push_back(i);
	}

	deque<S>* res = g(0, 0);
	ll ans = 0;
	for(int i = 0; i < res->size(); i++){
		if(cnt[i] == 0) continue;
		ans += (*res)[i].one * modpow(2, N + 1 - cnt[i], MOD) % MOD;
		ans %= MOD;
	}
	cout << ans << endl;
}


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

int main() {
    int N; cin >> N;
    set<int> s;
    for (int i = 0; i < N; i++)
    {
        int x; cin >> x;
        s.insert(x);
    }
    cout << s.size()<< endl;    
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-7;
const double PI = acos(-1.0);
int sgn(double x){
	return x<-eps?-1:x>eps;
}
struct Point{
	double x,y;
	Point(double a = 0.0,double b = 0.0):
		x(a),y(b){}
	bool operator == (const Point &p) const{
		return sgn(x - p.x) == 0 && sgn(y - p.y) == 0;
	}
	bool operator < (const Point &p) const{
		return y + eps < p.y || (y < p.y + eps && x + eps < p.x);
	}
	Point operator + (const Point &p) const{
		return Point(x + p.x, y + p.y);
	}
	Point operator - (const Point &p) const{
		return Point(x - p.x, y - p.y);
	}
	double operator * (const Point &p) const{
		return x*p.y - y*p.x;
	}
	double operator / (const Point &p) const{
		return x*p.x + y*p.y;
	}
	Point operator * (const double &k) const{
		return Point(x*k, y*k);
	}
	Point operator / (const double &k) const{
		return Point(x/k, y/k);
	}
	double len2()const{
		return x*x + y*y;
	}
	double len()const{
		return sqrt(len2());
	}
	Point scale(double k = 1.0)const{
		double tmp = len();
		return sgn(tmp)?(*this)*(k/tmp):(*this);
	}
	Point turnLeft()const{
		return Point(-y,x);
	}
	Point spin(Point &p,double angle){
		Point vec = (*this) - p;
		double Cos(cos(angle)), Sin(sin(angle));
		return p + Point(vec.x * Cos - vec.y * Sin, vec.x * Sin + vec.y * Cos);
	}
	void output()const{
		printf("%.10lf\n%.10lf\n",x,y);
	}
}a,b;
int n;
double d,l,r,t;
int main() {
	//freopen("in.txt", "r", stdin);
	while(scanf("%d%lf",&n,&d),n){
		a = Point(-d,0);
		b = Point(d,0);
		while(n--){
			scanf("%lf%lf%lf",&l,&r,&t);
			l = l/180*PI;
			r = r/180*PI;
			if(sgn(l - r) == 0){
				Point v = b-a;
				l *= t;
				v = v.turnLeft().scale(l);
				a = a+v;
				b = b+v;
			}
			else if(sgn(l) == 0){
				b = b.spin(a,r*t/(d*2));
			}
			else if(sgn(r) == 0){
				a = a.spin(b,-l*t/(d*2));
			}
			else{
				Point p;
				double lr,rr;
				if(sgn(l) == sgn(r)){
					if(sgn(fabs(l) - fabs(r)) == -1){
						p = a + (a-b).scale(2*d/(r/l - 1.0));
						lr = 2*d/(r/l - 1.0);
						rr = lr + d*2;
					}
					else{
						p = b + (b-a).scale(2*d/(l/r - 1.0));
						rr = 2*d/(l/r - 1.0);
						lr = rr + d*2;
					}
					if(sgn(l) == sgn(l - r)){
						l *= -1;
						r *= -1;
					}
				}
				else{
					p = b + (a - b).scale(2*d/(fabs(l/r) + 1.0));
					rr = 2*d/(fabs(l/r) + 1.0);
					lr = 2*d - rr;
					l *= -1;
				}
				a = a.spin(p,l*t/lr);
				b = b.spin(p,r*t/rr);
			}
		}
		((a+b)/2).output();
	}
	return 0;
}

Measured memory_bytes: 1260
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

int cv(char c){
    if(isdigit(c)) return c-'0';
    if('A'<=c && c<='Z') return c-'A'+10;
    return c-'a'+36;
}

ll READ(){
    ll p;
    string s;
    cin >>p >>s;

    ll ret = 0;
    rep(i,s.size()){
        ret = p*ret + cv(s[i]);
    }
    return ret;
}

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

    vector<ll> x(n);
    rep(i,n) x[i] = READ();

    // rep(i,n) printf(" %lld\n", x[i]);
    ll res = 0;
    rep(i,n){
        res ^= __builtin_popcount(x[i]);
    }

    string ans = "lose";
    if(res != 0) ans = "win";
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3696
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
using namespace std;
bool enough(vector<ll>h,ll T,ll a,ll b){
  ll d=a-b;
  ll t=0;
  rep(i,h.size()){
    if (h[i]-b*T>0){
      t+=(h[i]-b*T+d-1)/d;
    }
  }
  return t<=T;
}
int main(){
  ll n,a,b;
  cin>>n>>a>>b;
  vector<ll>h;
  rep(i,n){
    ll t;
    cin>>t;
    h.push_back(t);
  }
  ll upper=(1<<30)/b+1,lower=0;
  while (upper!=lower+1){
  //  cout<<upper<<","<<lower<<endl;
    ll T=(upper+lower)/2;
    if(enough(h,T,a,b)){
      upper = T;
    }else lower=T;
  }
  cout<<upper<<endl;
}


Measured memory_bytes: 1908
#include<iostream>


int main() {


	int n, m;

	int sec = 0;

	std::cin >> n >> m;

	sec = n * 100 + m * 1800;

	for (int i = 0; i < m; i++) {
		sec *= 2;
	}


	
	std::cout << sec;




	return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define INF 1<<31-1
#define LLINF 1<<63-1
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define MOD 1000000007
void swap(int* x,int* y){
  int tmp=*x;*x=*y;*y=tmp;
}

int main(){
  int N[5],i,ans=0,m=10;
  scanf("%d%d%d",&N[0],&N[1],&N[2]);
  scanf("%d%d",&N[3],&N[4]);
  for(i=0;i<5;i++){
    if(m>N[i]%10&&N[i]%10!=0)m=N[i]%10;
    if(N[i]%10!=0)N[i]=(N[i]/10+1)*10;
    ans+=N[i];
  }
  m=m-10;
  ans+=m;

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


Measured memory_bytes: 128
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,*A = map(int,read().split())

# まず、重複を除外
B = [A[0]] + [y for x,y in zip(A,A[1:]) if x != y]

seq = []
answer = 0
for x in B:
    if not seq:
        answer += 1
        seq.append(x)
        continue
    if len(seq) == 1:
        seq.append(x)
        continue
    a,b = seq[-2:]
    if a < b < x or a > b > x:
        seq.append(x)
        continue
    # xを追加すると破綻
    answer += 1
    seq = [x]

print(answer)

Measured memory_bytes: 13020