akhauriyash/Code-Regression huggingface dataset:
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };

    // G(T')
    // G(0) = 0
    // G(1) = 1
    // G(S1) .. G(S N-1)
    // G(S1) + 1 = G(S1')
    // T => S1, S2, ...
    // {G(S1), G(S2), ...} = {0, 1, ..., G(T)-1}
    // T' => S1', S2', ..., 0
    // {G(S1') ,G(S2'), ..., 0 } = {G(S1)+1, G(S2)+1, ..., 0 } = {1, 2, ..., G(T), 0 }
    // G(T') = G(T) + 1

    let n: usize = sc.read();
    let mut graph = vec![vec![]; n];
    for _ in 1..n {
        let x = sc.read::<usize>() - 1;
        let y = sc.read::<usize>() - 1;
        graph[x].push(y);
        graph[y].push(x);
    }

    if grundy_dfs(0, 0, &graph) == 0 {
        println!("Bob");
    } else {
        println!("Alice");
    }
}

fn grundy_dfs(v: usize, p: usize, graph: &Vec<Vec<usize>>) -> usize {
    let mut grundy = 0;
    for &next in graph[v].iter() {
        if next == p {
            continue;
        }
        grundy ^= grundy_dfs(next, v, graph) + 1;
    }
    grundy
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 16636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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; }

template<class T> inline auto __lcm(T& a, T& b) 
{ return a * b / __gcd(a, b); }

template<typename T> void remove(std::vector<T>& vector, unsigned int index)
{ vector.erase(vector.begin() + index); }


int main() {

  int M1, D1, M2, D2;
  cin >> M1 >> D1 >> M2 >> D2;

  if (M1 != M2) print(1);
  else print(0);

  return 0;
}


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

int main(){
	int i, j, n, a;
	int count=0, flag;

	scanf("%d",&n);

	for(i = 0;i < n; i++){
		flag=0;
		scanf("%d",&a);

		for(j = 2;j <= sqrt(a); j++){
			if(a%j == 0) {//素数じゃなかったらブレイク
				flag=1;
				break;
			}
		}
		if(flag == 0){
			count++;
		}
	}	
	printf("%d\n", count);
	return 0;
}



Measured memory_bytes: 2100
#include "bits/stdc++.h"
#include <chrono>
#include <tuple>
#include <string>
#include <random>
#include <cstdio>
#define ll long long int
// #define endl '\n'
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define pll pair<ll, ll>
#define pint pair<int, int>
#define S second
#define F first
#define all(c) (c).begin(),(c).end()
using namespace std; 
ll max(ll a, ll b){ if(a>b)return a;return b;}
ll min(ll a, ll b){ if(a < b) return a;return b;}
const int N = 100001;
vector<pair<ll, ll> > adj[N];
ll mod = 1000000007;

void solve() 
{
    int n, m;
    cin>>n>>m;

    vi x(n), y(m);

    rep(i, n) cin>>x[i];

    rep(i, m) cin>>y[i];

    sort(all(x)), sort(all(y));

    ll a = 0, b = 0;

    rep(i, n)
    {
        a += (i*x[i] - (n - i - 1)*x[i]);
        a += mod;
        a = a%mod;
    }

    // cout<<a<<endl;

    rep(i, m)
    {
        b += (i*y[i] - (m - i - 1)*y[i]);
        b+=mod;
        b = b%mod;
    }

    ll ans = (a*b)%mod;
    cout<<ans<<endl;




}

int main()
{
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    // cin>>T;
    int t=0;
    while(t++<T)
    {
        // cout<<"Case #"<<t<<":"<<' ';
        solve();
        // cout<<'\n';
    }

    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


Measured memory_bytes: 6356
import os, sys, re, math

N = int(input())
XY = []

for i in range(N):
    XY.append([int(n) for n in input().split()])

V = 0
for i in range(N):
    for j in range(N):
        if i != j:
            V += math.sqrt((XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2)

S = [0, 0, 1, 3, 6, 10, 15, 21, 28]
T = math.factorial(N)
m = T * (N - 1) // S[N] // 2

print(m * V / T)


Measured memory_bytes: 9848
import sys
input = sys.stdin.readline
def print_ans(ar):
    """Test Case
    >>> print_ans([1, 3, 4])
    4
    >>> print_ans([3, 2, 3])
    5
    """
    print(sum(ar) - max(ar))

if __name__ == '__main__':
    ar = list(map(int, input().rstrip().split()))
    print_ans(ar)




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

int main() {
	int ans = 0;
	int n;
	cin >> n;
	int l[210];
	for (int i = 0; i < 2 * n; i++)cin >> l[i];
	sort(l, l + 2 * n);
	for (int i = 0; i < n; i++) {
		ans += min(l[2 * i], l[2 * i + 1]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int  a, b, c,d,e,k;
  cin >>a>>b>>c>>d>>e>>k;
  if((e-a)>k){cout<<":("<<endl;
  }else{
  cout <<"Yay!"<< endl;}
}


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

using P = pair<int, int>;
vector<int> D = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main()
{
  int n, m;
  vector<int> A;

  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int t;
    cin >> t;
    A.push_back(t);
  }

  vector<P> M;

  for (int i = 0; i <= n; ++i) {
    P answer = make_pair(-1, -1);

    for (auto a: A) {
      if (i > D[a]) {
        auto rest = M[i - D[a]];
        if (rest.first >= 0) {
          answer = max(answer, make_pair(rest.first + 1, max(rest.second, a)));
        }
      } else if (i == D[a]) {
        answer = max(answer, make_pair(1, a));
      }
    }

    M.push_back(answer);
  }

  while (n > 0) {
    cout << M[n].second;
    n -= D[M[n].second];
  }
  cout << endl;

  return 0;
}


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

using namespace std;
using ll = long long;

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "YES"
#define FALSE__ "NO"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);

#define MOD 1000000007

void init();
void solve();

signed main()
{
	init();
	solve();
}

ll x, y;

void init()
{
	cin >> x >> y;
}

void solve()
{
	ll res = x;
	int cnt = 0;
	while (res <= y) {
		res *= 2;
		cnt++;
	}
	cout << cnt << endl;
}




Measured memory_bytes: 256
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

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

#define MAX 100000
#define NIL -1

typedef int _loop_int;
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

ll N,K,Q;

ll member[MAX];

int main() {
    cin >> N >> K >> Q;

    REP(i,N) {
        member[i] = K;
    }

    multiset<ll> A;

    REP(i, Q) {
        ll a;
        cin >> a;
        A.insert(a);
    }
    auto temp = A.begin();
    REP(i, N) {
        ll acounter = 0; 
        
        for(auto it = temp;it!=A.end();it++) {
            if ((i+1)==*it) {
                acounter++;
            } else {
                temp = it;
                break;
            }
        }
        
        if ((K-Q+acounter)>0) {
            print("Yes");
        } else{
            print("No");
        }
    }
    return 0;
}


Measured memory_bytes: 6016
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const ld TAU=2*acos(-1);
const ld eps=1e-7;
const int inf=1e9+99;
const ll linf=1e18+88;
const int P=1e9+7;



const int N=500<<10;
char s[N];
int dp[N][32];
int n;

int nx[N][32];

int32_t main() {
	scanf("%s",s);
	n=(int)strlen(s);
	s[n]='$';
	s[n+1]='\0';
	for(int i=n;--i>=0;) {
		int me=s[i]-'a';
		dp[i][me]=i+1;
		int L=i+1;
		for(int c=me;c<26;c++) {
			if(!dp[L][c]) break;
			dp[i][c+1]=dp[L][c];
			L=dp[L][c];
		}
		if(dp[i][26]) for(int c=0;c<26;c++) if(!dp[i][c]) dp[i][c]=dp[L][c];
	}

	for(int i=0;i<n;i++) nx[i][0]=dp[i][26];
	for(int i=0;i<=n;i++) if(!nx[i][0]) nx[i][0]=-1;
	for(int l=1;l<=20;l++) {
		for(int i=0;i<=n;i++) {
			if(~nx[i][l-1]) nx[i][l]=nx[nx[i][l-1]][l-1];
			else nx[i][l]=-1;
		}
	}

	int Q; scanf("%d",&Q);
	for(;Q--;) {
		int L,R; scanf("%d%d",&L,&R);
		--L;
		for(int l=20;l>=0;--l) {
			// cerr<<nx[L][l]<<endl;
			if(~nx[L][l] && nx[L][l]<=R) L=nx[L][l];
			// cerr<<L<<","<<R<<endl;
		}
		if(L==R) printf("Yes\n");
		else printf("No\n");
	}


}




Measured memory_bytes: 128128
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());

            var list = new List<int>();
            list.Add(n);

            while (true)
            {
                if (n % 2 == 0)
                    n = n / 2;
                else
                    n = 3 * n + 1;

                if (list.Contains(n)) break;
                list.Add(n);

            }

            Console.WriteLine(list.Count + 1);
        }
    }
}


Measured memory_bytes: 13024
import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a[] = new int[4];
    for(int i=0;i<3;i++)  a[i] = sc.nextInt();
    for(int i=0;i<3-1;i++){
      for(int j=0;j<3-i;j++){
        if(a[j]>a[j+1]){
          a[3] = a[j];
          a[j] = a[j+1];
          a[j+1] = a[3] ;
        }
      }
    }
    System.out.println(a[0]+" "+a[1]+" "+a[2]);
  }
}



Measured memory_bytes: 26108
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    // stringstream ss("12300 99");
    // ss >> a >> b;
    cout << fixed << setprecision(8);
    cout << a / b << " " << a % b << " " << (double)a / (double)b << endl;
    return 0;
}



Measured memory_bytes: 3288
#include<cstdio>
#include<cmath>
int main(){
  double x1,y1,x2,y2;
  scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
  printf("%.7f\n",sqrt(pow(x2-x1,2)+pow(y2-y1,2)));
}


Measured memory_bytes: 2740
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using ll = long long;
#define rep(inc, bgn, end) for (int inc = bgn; inc < end; ++inc)
#define repe(inc, bgn, end) for (int inc = bgn; inc <= end; ++inc)

using namespace std;

#define PI 3.141592
int main() {
    int n, m;
    cin >> n >> m;
    if (n >= m) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> pos(m);
    // O:m
    rep(i, 0, m) {
        cin >> pos[i];
    }

    // O;mlog(m)
    sort(pos.begin(), pos.end());

    vector<int> lenList(m - 1);
    // O:m-1
    rep(i, 0, m - 1) {
        lenList[i] = abs(pos[i] - pos[i + 1]);
    }

    // O:mlog(m)
    sort(lenList.begin(), lenList.end());

    // O:m-1
    long sum = 0;
    rep(i, 0, lenList.size() - (n - 1)) {
        sum += lenList[i];
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 1024
import itertools

target=input()
n = len(target)-1
#bit_list = [list(f"{i:0{n}b}") for i in range(2**n)]
status = [['0', '1'] for _ in range(n)]
bit_list = list(itertools.product(*status)) 


answer = 0

for bits in bit_list:
    one_number_indexes=[i for i, x in enumerate(bits) if x == '1']
    
    # ここで1がある場所を取得
    start=0    
    # 街灯の箇所で文字を区切る関数を実装
    for index in one_number_indexes:
        answer=answer+int(target[start:index+1])
        start=index+1
    answer=answer+int(target[start:n+1])

print(answer)

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

int main() {
  int a,b,c;
  cin >>a >>b >> c;
  
  int tmp;
  tmp=a;
  a=b;
  b=tmp;
  
  tmp=a;
  a=c;
  c=tmp;
  
  cout <<a <<" "<<b<<" "<<c<<endl;
    
}


Measured memory_bytes: 256
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}

void main()
{
    auto dp = new long[][](1000 + 2, 1000 + 2);
    long H, W;
    scan(H, W);
    // if (H != 3)
    //     return;
    dp[0][] = 0;
    foreach (row; dp)
        row[0] = 0;

    dp[1][1] = 1;

    foreach (i; 1 .. H + 1)
    {
        auto s = sread();
        foreach (j; 1 .. W + 1)
            if (s[j - 1] == '.')
            {
                // writefln("(%d %d): %d + %d", i, j, dp[i - 1][j], dp[i][j - 1]);
                dp[i][j].maxAssign((dp[i - 1][j] + dp[i][j - 1]) % (10 ^^ 9 + 7));
            }
            else
            {
                dp[i][j] = 0;
            }
    }
    dp[H][W].writeln();
}


Measured memory_bytes: 11004
n = int(input())
base = [["aabc", "ddbc", "bcaa", "bcdd"], ["aabba", "bcc.a", "b..cb", "a..cb", "abbaa"], ["aabc..", "ddbc..", "..aabc", "..ddbc", "bc..aa", "bc..dd"], ["aabbcc.", "dd.dd.a", "..d..da", "..d..db", "dd.dd.b", "..d..dc", "..d..dc"]]
if n == 2:
    print(-1)
elif n == 3:
    print(".aa")
    print("a..")
    print("a..")
else:
    div, mod = n // 4 - 1, n % 4 + 4
    for i in range(div):
        for j in base[0]:
            print("." * i * 4 + j + "." * ((div - i - 1) * 4 + mod))
    for i in base[mod - 4]:
        print("." * div * 4 + i)

Measured memory_bytes: 9096
import java.math.BigDecimal;

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

		var a=new BigDecimal[5];
		for(int i=0;i<5;i++) {
			a[i]=sc.nextBigDecimal();
		}
		for(int i=0;i<5;i++) {
			if(BigDecimal.ZERO.equals(a[i])) {
				System.out.println((i+1));
				break;
			}
		}
	}
}


Measured memory_bytes: 37400
N = int(input())
S = input()

from collections import Counter
c = Counter()

for si in S:
    c[si] += 1

# print(c.values())

ans = 1
for n in c.values():
    ans *= n + 1
    ans = ans % (10 ** 9 + 7)

ans -= 1
print(ans)

Measured memory_bytes: 3444
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
ll n;
ll u,v;
vvi E(111111);
/*
int root=0;
int parent[20][111111];
int depth[111111];

void dfs(int v,int p,int d){
  parent[0][v] = 0;
  depth[v] = d;
  for(int i=0;i<E[v].size();i++){
    if(E[v][i] != p)dfs(E[v][i],v,d+1);
  }
}

void init(int V){
  dfs(root,-1,0);
  for(int k=0;k+1<20;k++){
    for(int v=0;v<V;v++){
      if(parent[k][v] < 0)parent[k+1][v]=-1;
      else parent[k+1][v] = parent[k][parent[k][v]];
    }
  }
}

int lca(int u,int v){
  if(depth[u]>depth[v])swap(u,v);
  for(int k=0;k<20;k++){
    if((depth[v]-depth[u])>>k&1){
      v=parent[k][v];
    }
  }
  if(u==v)return u;
  for(int k=19;k>=0;k--){
    if(parent[k][u] != parent[k][v]){
      u = parent[k][u];
      v = parent[k][v];
    }
  }
  return parent[0][u];
}
*/
ll node;
vi ho(111111);
void bfs(){
  queue<int>tak,ao;
  tak.push(u);
  ao.push(v);
  ho[u]=1;ho[v]=2;
  while(true){
    if(tak.empty()&&ao.empty())break;
    ll num=tak.size();
    for(int i=0;i<tak.size();i++){
      ll now=tak.front();tak.pop();
      for(auto e:E[now]){
	if(ho[e]==2)node=now;
	if(ho[e]==0){
	  ho[e]=1;
	  tak.push(e);
	}
      }
    }
    num=ao.size();
    for(int i=0;i<ao.size();i++){
      ll now=ao.front();ao.pop();
      for(auto e:E[now]){
	if(ho[e]==0){
	  ho[e]=2;
	  ao.push(e);
	}
      }
    }


  }
}

vi vis(111111);
void dfs2(int now,int di,int par){
  vis[now]=di;
  for(auto a:E[now]){
    if(a==par||a==node)continue;
    dfs2(a,di+1,now);
  }
}
vi vis2(111111);
void dfs3(int now,int di,int par){
  vis2[now]=di;
  for(auto a:E[now]){
    if(a==par||vis[a]||a==v)continue;
    dfs3(a,di+1,now);
  }
}
vi vis3(111111);
void dfs4(int now,int di,int par){
  vis3[now]=di;
  for(auto a:E[now]){
    if(a==par)continue;
    dfs4(a,di+1,now);
  }
}
vi vis4(111111);
void dfs5(int now,int di,int par){
  if(ho[now]==2)vis4[now]=0;
  else
    vis4[now]=di;
  for(auto a:E[now]){
    if(a==par)continue;
    dfs5(a,di+1,now);
  }
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  cin>>u>>v;
  u--;v--;
  for(int i=0;i<n-1;i++){
    ll a,b;cin>>a>>b;
    E[--a].pb(--b);
    E[b].pb(a);
  }
  //init(n);
  //node = lca(u,v);
  //dfs2(v,0,-1);
  bfs();
  dfs3(node,0,-1);
  dfs4(u,0,-1);
  dfs5(v,0,-1);
  ll ma=0,ma2=0;
  ll po=-1,po2=-1;
  for(int i=0;i<n;i++){
    if(vis4[i]){
      ma=max(vis4[i],ma);
    }
  }
  // cout<<node<<endl;
  cout<<ma-1<<endl;
  return 0;
}


Measured memory_bytes: 14336
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    a,b,k=map(int,input().split())
    from fractions import gcd
    g=gcd(a,b)
    A=divisors(g)
    print(A[-k])
resolve()

Measured memory_bytes: 64364
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int N;
    cin>>N;
    vector<long> arr(N);
    for(int i=0;i<N;++i){
        cin>>arr[i];
    }
    reverse(arr.begin(), arr.end());
    long DP[N];
    for(int i=0;i<N;++i){
        DP[i] = 1e9+7;
    }
    int l, r, m;
    for(int i=0;i<N;++i){
        l = 0;
        r = N-1;
        while(l<r){
            m = (l+r)/2;
            if(DP[m]>arr[i]){
                r = m;
            }
            else{
                l = m+1;
            }
        }
        DP[l] = arr[i];
    }
    int ans = 0;
    l = 0;
    r = N-1;
    while(l<r){
        m = (l+r)/2;
        if(DP[m]==1e9+7){
            r = m;
        }
        else{
            l = m + 1;
        }
    }
    if(DP[l]==1e9+7)cout<<l<<endl;
    else cout<<l+1<<endl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n;
  std::cin >> n;
  std::vector<int> v(n+1);
  std::vector<int> ball(n+1,0);


  for (int i = 1; i <= n; i++) {
    std::cin >> v[i];
  }

  for (int i = n; i > 0; i--) {

      int sum=0;
      for (int j = 2*i; j <= n; j+=i) {
        sum+=ball[j];
      }
      sum%=2;
      if(sum!=v[i]){
        ball[i]++;
      }

  }

  vector<int> ans;
  for (int i = 1; i <= n; i++) {
    if (ball[i]) ans.push_back(i);
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) {
      printf("%d%c", ans[i], i+1==ans.size()?'\n':' ');
  }

  return 0;
}


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

#define PI acos(-1)
#define pb push_back
#define int long long int
#define mp make_pair
#define pi pair<int, int>
#define pii pair<pi, int>
#define fir first
#define sec second
#define MAXN 200001
#define MAXL 20
#define mod 1000000007

signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  vector<int> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  for (int i = k; i < n; i++)
  {
    if (v[i] > v[i - k])
      cout << "Yes\n";
    else
      cout << "No\n";
  }
  return 0;
}

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

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double EPS = 1e-6;
const int MAX_N = 105;
const int MAX_W = 1e5 + 5;

int N, W;
ll dp[MAX_W];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> N >> W;
	for (int i = 0; i < N; ++i) {
		int w, v; cin >> w >> v;
		for (int j = W; j >= 0; --j) {
			if (j - w >= 0) {
				dp[j] = max(dp[j], dp[j - w] + v);
			}
		}
	}

	cout << *max_element(dp, dp + W + 1) << '\n';

	return 0;
}

Measured memory_bytes: 1024
use std::io::{self, BufRead};

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let _ = lines.next().unwrap().unwrap();
  let line = lines.next().unwrap().unwrap();
  let mut vs: Vec<i32> = line.split(' ').map(|x| x.parse().unwrap()).collect();
  vs.sort();
  for i in 0..(vs.len()-1) {
    if vs[i] == vs[i+1] {
      println!("NO");
      return;
    }
  }
  println!("YES");
}

Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;

int main(){
    int n,m,q;
    cin>>n>>m>>q;
    vvi vec(n+1,vi(n+1));
    REP(i,m){
        int l,r;
        cin>>l>>r;
        vec[l][r]++;
    }
    REP(i,n+1){
        REP(j,n+1){
            if(i+1<=n)vec[i+1][j]+=vec[i][j];
        }
    }
    REP(i,n+1){
        REP(j,n+1){
            if(j+1<=n)vec[i][j+1]+=vec[i][j];
        }
    }
    REP(i,q){
        int l,r;
        cin>>l>>r;
        cout<<vec[r][r]-vec[l-1][r]-vec[r][l-1]+vec[l-1][l-1]<<endl;
    }
    return 0;
}

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

int main() {
    string S;
    cin >> S;
    for (int i = 1; i <= S.size(); i++) {
        if (i % 2 == 0) {
            if (S.at(i - 1) == 'R') {
                cout << "No" << endl;
                return 0;
            }
        } else {
            if (S.at(i - 1) == 'L') {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define i int
#define ch char
#define f float
#define uns unsigned
#define input(x) cin >>x
#define output(x) cout <<x
#define space() cout <<endl
#define vi(x) vector<x>
#define loop(I,N) for(lli I=0;I<N;I++)
#pragma GCC optimize("Ofast") 
#define you -> Noob
#define max 1000001
lli dp[max];
//written by Aden Frost
void fastaf(void)
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
}
lli frog(lli A[],lli N)
{
    if(N<=1)
        return 0;
    if(dp[N]!=-1)
        return dp[N];
    else
        return dp[N]=min(abs(A[N-1]-A[N-2])+frog(A,N-1),abs(A[N-1]-A[N-3])+frog(A,N-2));
}
void solve(void)
{
    lli N;
    input(N);
    lli A[N];
    loop(I,N)
        input(A[I]);
    reverse(A,A+N);
    output(frog(A,N));
}
int main()
{
    for(i I=0;I<max;I++)
        dp[I]=-1;
    fastaf();
    solve();
    space();
    return 0;
}


Measured memory_bytes: 16112
using System;

class Print_a_Rectangle
{
  public static void Main()
  {
    while(true)
    {
      string number_str = Console.ReadLine();
      string[] number_tmp = number_str.Split();
      int H = int.Parse(number_tmp[0]);
      int W = int.Parse(number_tmp[1]);
      
      if(H==0&&W==0) break;
      
      for(int i=1;i<=H;i++)
      {
        for(int j=1;j<=W;j++)
        {
          if((i+j)%2==0)
          {
            Console.Write("#");
          }else{
            Console.Write(".");
          }
        }
        Console.WriteLine();
      }
      
      Console.WriteLine();
      }
   }
}

Measured memory_bytes: 8876
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	int num[100];
	int i, j;
	int ans = 0;
	
	cin >> n;
	
	for (i = 0; i < n; i++){
		cin >> num[i];
	}
	
	for (i = 0; i < n; i++){
		for (j = n - 1; j > i; j--){
			if (num[j - 1] > num[j]){
				swap(num[j-1],num[j]);
				ans++;
			}
		}
	}
	
	for (i = 0; i < n; i++){
		cout << num[i];
		if (i == n - 1){
			cout << "\n";
		}
		else {
			cout << " ";
		}
	}
	
	cout << ans << "\n";
	
	return (0);
}



Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (1e9)
#define INFL (1e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>using arr=vector<vector<T>>;
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);}
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; }
ll ans;
void dfs(vector<int> a, int n, int x){
    // prvec(a);
    if(a.size()==4){
        int s = 0;
        rep(i, 3) s += a[i+1];
        // pr(s);
        if(s==x) ans++;
        return;
    }
    int b = a.back();
    vector<int> aa = a;
    FOR(i, b+1, n+1){
        a.push_back(i);
        dfs(a, n, x);
        a = aa;
    }
}

ll solve(int n, int x){
    vector<int> a;
    a.push_back(0);
    ans = 0;
    dfs(a, n, x);
    return ans;
}

int main()
{
    int n, x; 
    while(cin >> n >> x){
        if(n==0 && x==0) break;
        pr(solve(n, x));        
    }
    return 0;}


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;

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

    int n, y;
    cin >> n >> y;

    rep(i, n+1){
        rep(j, n-i+1){
            ll tmp = i * 10000 + j * 5000 + (n-i-j) * 1000;
            if(tmp == y) {
                cout << i << " " << j << " " << n-i-j << endl;
                return 0;
            }
        }
    }

    cout << -1 << " " << -1 << " " << -1 << endl;


    return 0;
}

Measured memory_bytes: 256
fn main() {
    let mut b = String::new();
    let _ = std::io::stdin().read_line(&mut b);
    let c = b.split_whitespace().map(|i| i.parse().unwrap()).collect::<Vec<i32>>();
    if c[0] <= c[2] && c[2] <= c[1] {
        println!("Yes");
    } else {
        println!("No");
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define min(a, b) ((a<b)?a:b)
#define max(a, b) ((a<b)?b:a)
#define pb push_back
#define endl "\n"
typedef long long ll;

#define max_element mmmmm
#define min_element nnnnn

template<class T>
class BIT {
	public:
		int BIT_size;
		vector<T> BIT_array;
		BIT(int BIT_size) {
			this->BIT_size = BIT_size;
			BIT_array = vector<T>(BIT_size+1);
			fill(BIT_array.begin(), BIT_array.end(), 0);
		}
		void BIT_update(int i, T d) {
			for(; i<=BIT_size; i+=(i&-i)) {
				BIT_array[i] += d;
			}
		}
		T BIT_sum(int i) {
			T BIT_sum_result = 0;
			for(; i>0; i-=(i&-i)) {
				BIT_sum_result += BIT_array[i];
			}
			return BIT_sum_result;
		}				
};

ll pow(ll a, ll b, ll m) {
	a %= m;
	ll result = 1;
	while(b > 0) {
		if(b & 1) {
			result = result*a%m;
		}
		a = a*a%m;
		b /= 2;		
	}
	return result;
}

ll m = 1000000007;

int main() {
	ll n, k; cin >> n >> k;
	ll v[n+2];
	v[0] = 0;
	ll solution = 0;
	for(int i=1; i<=n+1; i++) v[i] = i-1;
	for(int i=1; i<=n+1; i++) v[i] += v[i-1];
	for(int i=k; i<=n+1; i++) {
		ll low = v[i];
		ll hi = v[n+1] - v[n+1-i];
		solution = (solution+hi-low+1)%m;
	}
	cout << solution << endl;
}







































































Measured memory_bytes: 5136
#include<bits/stdc++.h>
using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	char s[10];
	cin>>s;
	int a[26];
	memset(a,0,sizeof(a));
	for(int i=0;i<4;i++)
	{
		a[s[i]-'A']++;
	}
	int count=0;
	for(int i=0;i<26;i++)
	{
		if(a[i]==2)count++;
	}
	if(count==2)cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template <class T> 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() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S, T;
    cin >> S >> T;

    map<char, int> sc, tc;
    if (S.size() != T.size()) {
        cout << "No" << endl;
        return 0;
    }

    REP(i, S.size()) {
        auto itr = sc.find(S[i]);
        if (itr != sc.end()) {
            itr->second++;
        } else {
            sc[S[i]] = 1;
        }
    }
    REP(i, T.size()) {
        auto itr = tc.find(T[i]);
        if (itr != tc.end()) {
            itr->second++;
        } else {
            tc[T[i]] = 1;
        }
    }

    REP(i, S.size()) {
        if (sc[S[i]] != tc[T[i]]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


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

using namespace std;

#define ll long long int
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 998244353
const int N = 2e5 + 5;
int dp[N];
int pref[N] , l[N] , r[N];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n , k;
    cin>>n>>k;
    for(int i = 0; i < k; i++){
        cin>>l[i]>>r[i];
    }
    dp[1] = 1;
    pref[1] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 0; j < k; j++){
            if(i <= l[j]){
                continue;
            }
            int left = l[j];
            int right = min(r[j] , i - 1);
            int add = (pref[i - left] - pref[i - right - 1] + MOD) % MOD;
            dp[i] = (dp[i] + add) % MOD;
        }
        pref[i] = pref[i - 1] + dp[i];
        pref[i] %= MOD; 
    }
    cout<<dp[n]<<"\n";
    
}

Measured memory_bytes: 5108
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()
#define allg(v) v.begin(), v.end(), greater<int>()



signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s;
  int n;
  cin >> n;
  
  //vector<int> a(n);  rep(i, 0, n) cin >> a[i];
  
  cout << n*n*n << "\n";
  
  //cout << (  ?"Yes" :"No") << "\n";
  
  //cout << fixed << setprecision(15) << n << "\n";

}

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

#define repi(i, s, n) for (ll i {s}, i##_len{n}; i < i##_len; ++i)
#define rep(i, n) repi(i, 0, n)
#define all(x) std::begin(x), std::end(x)

namespace forno
{
template<typename T, typename... Args>
T get_value(std::basic_istream<Args...>& is);
template<typename C, typename... Args>
C get_container(std::basic_istream<Args...>& is, typename C::size_type length = std::numeric_limits<typename C::size_type>::max());
template<typename C>
ll llsize(const C& c);
template<typename C, size_t N>
ll llsize(const C(&)[N]);

ll llgcd(ll a, ll b);
ll lllcm(ll a, ll b);
ll lllog2(ll x);
}
using namespace forno;

int main()
{
  const auto c {get_value<char>(cin)};
  cout << static_cast<char>(c + 1) << '\n';
  return 0;
}

class initalization
{
  class custom_numpunct: public std::numpunct<char>
  {
  public:
    using numpunct::numpunct;
  protected:
    std::string do_truename() const override { return "Yes"; }
    std::string do_falsename() const override { return "No"; }
  };

public:
  initalization()
  {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.imbue(std::locale(std::cout.getloc(), new custom_numpunct{}));
    std::cout << std::boolalpha;
  }
} initalize;

namespace forno
{

template<typename T, typename... Args>
T get_value(std::basic_istream<Args...>& is)
{
  T v {};
  is >> v;
  return v;
}

template<typename C, typename... Args>
C get_container(std::basic_istream<Args...>& is, typename C::size_type length)
{
  C v {};
  if (length != std::numeric_limits<typename C::size_type>::max())
    v.reserve(length);
  typename C::value_type e {};
  for (auto i {length}; i != 0 && is >> e; --i)
    v.push_back(std::move_if_noexcept(e));
  return v;
}

template<typename C>
ll llsize(const C& c)
{
  return static_cast<ll>(c.size());
}

template<typename C, size_t N>
ll llsize(const C(&)[N])
{
  return static_cast<ll>(N);
}

ll llgcd(ll a, ll b)
{
  return b ? llgcd(b, a%b) : a;
}

ll lllcm(ll a, ll b)
{
  return a / llgcd(a, b) * b;
}

ll lllog2(ll x)
{
  ll res {0};
  for (;!(x % 2); ++res)
    x >>= 1;
  return res;
}

}


Measured memory_bytes: 256
def main():
    n = int(input())
    A = list(map(int, input().split()))
    
    total_high = 0
    for i in range(n-1):
        if A[i] > A[i+1]:
            delta_high = A[i] - A[i+1]
            A[i+1] += delta_high
            total_high += delta_high
    return print(total_high)

main()

Measured memory_bytes: 32376
long_and_wide = []
previous = nil

gets
A = gets.split.map(&:to_i).sort

A.reverse_each do |a|
  if previous && a == previous
    long_and_wide << a
    break if long_and_wide.size == 2

    previous = nil
  else
    previous = a
  end
end

if long_and_wide.size == 2
  puts long_and_wide.inject(&:*)
else
  puts 0
end


Measured memory_bytes: 10112
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define INF 2000000000
typedef long long ll;

int main(){
    int N,M;
    cin >> N >> M;
    vector<ll> H;
    ll h;
    REP(i,N){
        cin >> h;
        H.push_back(h);
    }
    vector<vector<int>> E(N);
    int A,B;
    REP(i,M){
        cin >> A >> B;
        A--;
        B--;
        E.at(A).push_back(B);
        E.at(B).push_back(A);
    }
    bool f;
    int count = 0;
    REP(i,N){
        f = true;
        for(auto j : E.at(i)){
            if(H.at(i)<=H.at(j)) f=false;
        }
        if(f) count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 8852
#include<stdio.h>
#include<stdlib.h>

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int main(void){
    char S[101];
    long K;
    scanf("%s %ld",S,&K);

    int one_num=0;
    for(int i=0;i<=100;i++){
        if(S[i]=='1') one_num++;
        else break;
    }

    char ans;
    if(one_num>=K) ans='1';
    else ans=S[one_num];
    printf("%c\n",ans);

    return 0;
}

Measured memory_bytes: 128
integer(8) N,M,i
integer(8),allocatable,dimension(:)::A,B
integer(8) ans
read*,N,M
allocate(A(N),B(N))
do i=1,N
  read*,A(i),B(i)
end do
call heapsortPair(N,A,B)
ans=0
do i=1,N
  if(B(i)<M)then
    ans=ans+A(i)*B(i)
    M=M-B(i)
  else
    ans=ans+A(i)*M
    exit
  endif
end do

print"(i0)",ans

contains
subroutine HeapsortPair(n,array,array2)
  implicit none
!ここの入力は状況に応じて変更すること
  integer(8),intent(in) :: n
  integer(8),intent(inout) :: array(1:n),array2(1:n)
  integer(8)::i,k,j,l
  integer(8):: t,t2

  l=n/2+1
  k=n
  do while(k /= 1)
     if(l > 1)then
        l=l-1
        t=array(L)
        t2=array2(L)
     else
        t=array(k)
        t2=array2(k)
        array(k)=array(1)
        array2(k)=array2(1)
        k=k-1
        if(k == 1) then
           array(1)=t
           array2(1)=t2
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j<=k)
        if(j < k)then
           if(array(j) < array(j+1))j=j+1
        endif
        if (t < array(j))then
           array(i)=array(j)
           array2(i)=array2(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
     array2(i)=t2
  enddo
  return
end subroutine HeapsortPair
end

Measured memory_bytes: 1792
from math import floor, ceil, log2

def getNums(As, N):
    nums = [0] * N
    accNum = 0
    stack = [(N-1, float('inf'))]
    dNow = 0
    for i in reversed(range(N - 1)):
        if As[i] <= As[i+1]:
            dd = floor( log2( As[i+1] / As[i] ) / 2 )
            if dd > 0: stack.append((i, dNow))
            dNow -= dd
        else:
            dTgt = dNow + ceil( log2( As[i] / As[i+1] ) / 2 )
            while dNow < dTgt:
                pos, d = stack[-1]
                if dTgt > d:
                    accNum += (d - dNow) * (pos - i)
                    dNow = d
                    stack.pop()
                else:
                    accNum += (dTgt - dNow) * (pos - i)
                    if dTgt == d: stack.pop()
                    dNow = dTgt
                    break
        nums[i] = accNum
    return nums

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

numPstvs = getNums(As, N)
numNgtvs = getNums(As[::-1], N)[::-1]

ans = float('inf')
for i, (p, m) in enumerate(zip(numPstvs + [0], [0] + numNgtvs)):
    ans = min(ans, 2 * p + 2 * m + i)
print(ans)


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

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'
#define         pii        pair<int,int>
#define         mapii      map<int,int>
#define         mapll      map<ll,ll>
#define         mapci      map<char,int>
#define         mapcl      map<char,ll>
#define         mapsi      map<string,int>
#define         mapsl      map<string,ll>
#define         pll        pair<ll,ll>
#define         vi         vector<int>
#define         vl         vector<ll>
#define         vd         vector<double,double>
#define         all(c)     c.begin(),c.end()
#define         F          first
#define         S          second
#define         mp         make_pair
#define        ftc(x)      cerr << #x << ": " << x << " " << endl;
#define         PI         acos(-1)
#define         lcm(a,b)   ((a*b)/__gcd(a,b))
#define        optimize    ios_base::sync_with_stdio(false);cin.tie(NULL);
#define        sqr(a)       ((a)*(a))

int main()
{
    ll n,i,j,k,l=1ll,m,cnt,ans=0;

    cin >> n;

   for(i=2;i*i<=n;i++)
   {
       cnt = 0;

       while(n>1 && n%i == 0)
       {
           n = n/i;

           cnt++;
       }
       if(cnt){
       // cout << i << " " << cnt << endl;
       m = (ll)sqrt(1+(8*cnt)) - 1;
       m /= 2;
       ans += m;
       }

   }
   if(n>2)ans++;

   cout << ans << endl;

}



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

const double eps = 1e-9;
double n;

int main(void){
  cin >> n;
  for(int i = 1; i <= 50000; i++){
    if(abs(floor(1.08*i) - n) < eps){
      cout << i << endl;
      return 0;
    }
  }
  cout << ":(" << endl;
  return 0;
}


Measured memory_bytes: 3708
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;

namespace mine
{
    typedef long long ll;
    const int MAX_N=110;
    int mymax(int x,int y) {return x>y?x:y;}
    int mymin(int x,int y) {return x<y?x:y;}
    int myabs(int x) {return x>0?x:-x;}

    int a[110000];
    void main()
    {
        int n,k;scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int ans=0x3f3f3f3f;

        for(int l=1;l<=n-k+1;l++)
        {
            int r=l+k-1;
            if(l+k-1<=n)
            {
                ans=mymin(ans,myabs(a[l])+myabs(a[r]-a[l]));
                ans=mymin(ans,myabs(a[r])+myabs(a[l]-a[r]));
            }
        }
        printf("%d",ans);
    }
};

int main()
{
    mine::main();
}


Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
int main(){
	int n,num,ans = 0;
	map<int,int> m;
	map<int,int>::iterator iter;
	cin >> n;
	for(int i = 0;i<n;i++){
		cin >> num;
		m[num]++;
	}
	for(iter = m.begin();iter!=m.end();iter++){
		int a = iter->first,b = iter->second;
		if(a<=b){
			ans += b-a;
			continue;
		}
		if(a>b){
			ans += b;
			continue;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
    ll n, m;
    cin >> n >> m;
    vector<ll> s(m);
    vector <char> c(m);
    rep(i, m){
        cin >> s[i] >> c[i];
    }

    rep(i, powl(10, n)){
        string str = to_string(i);
        ll str_size = str.size();
        bool flg=true;
        if (str_size != n){
            continue;
        }
        rep(j, m){
            if ((s[j]-1) < str_size && str[s[j]-1] == c[j]){
                continue;
            }
            flg = false;
        }
        if (flg){
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}


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

int n, k;
string s;
vector<int> v;

int solve();

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

  cout << solve() << endl;
  return 0;
}

int solve() {
  int ans = 0;
  if(s[0] == '0') v.push_back(0);
  for(int i = 0; i < n; ++i) {
    int now = 0;
    bool ch = s[i] - '0';
    while(i < n && s[i] - '0' == ch) ++now, ++i;
    v.push_back(now);
    if(i == n) break;
    --i;
  }
  if(s[n - 1] == '0') v.push_back(0);
  assert(v.size() % 2 == 1);
  for(int l = 0, r = 0, cnt = 0; l < v.size(); ++l) {
    while(r < v.size() && r - l <= 2 * k) cnt += v[r++];
    ans = max(ans, cnt);
    cnt -= v[l++];
    if(l < v.size()) cnt -= v[l];
  }
  return ans;
}

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
struct Node;
vector<Node> V;
struct Node {
  int idx;
  vector<int> nbr;
  bool vst = false;
  int ans = -1;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    lint N, M;
    cin >> N >> M;
    REP(i, N) V.emplace_back();
    REP(i, M) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        V[u].nbr.push_back(v);
        V[v].nbr.push_back(u);
    }
    deque<int> que;
    que.push_back(0);
    V[0].vst = true;
    while(!que.empty()) {
        int x = que.front();
        que.pop_front();
        //cout << x << endl;
        for(int y : V[x].nbr) {
            if(!V[y].vst) {
                V[y].ans = x;
                que.push_back(y);
                V[y].vst = true;
            }
        }
    }
    cout << "Yes" << endl;
    FOR(i, 1, N) {
        cout << V[i].ans+1 << "\n";
    }
}

Measured memory_bytes: 11224
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int x, y;
	cin >> x >> y;
	int ans = 2100000000;
	if (x < y) ans = y-x;
	if (-x <= y) ans = min(ans, 1 + y + x);
	if (x <= -y) ans = min(ans, 1 - y - x);
	if (x > y) ans = min(ans, 2 - y + x);
	cout << ans << endl;
}


Measured memory_bytes: 256