akhauriyash/Code-Regression huggingface dataset:
/*********************
*  Author: xuziyuan  * 
*********************/

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL n,num[2][70],x,ans=0;

int main()
{
	cin>>n;
	rep(i,n)
	{
		scanf("%lld",&x);
		rep(j,64)
		{
			num[x&1][j]++;
			x/=2;
		}
	}
	LL res=1;
	rep(j,64)
	{
		ans=(ans+num[0][j]*num[1][j]%MOD*res%MOD)%MOD;
		res=res*2%MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int n, s[100001], q, t, cnt=0;
int binsearch(){
  int  left = 0, right = n;
  while(left < right){
    int mid = (left + right) / 2;
    if(s[mid] == t) return mid;
    else if(t < s[mid]) right = mid;
    else left = mid + 1;
  }
  return -1;
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++)scanf("%d",&s[i]);
  cin>>q;
  for(int i=0;i<q;i++){
    scanf("%d",&t);
    if(binsearch()!=-1)cnt++;
  }
  cout<<cnt<<endl;


  return 0;
}



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

#define Max 200005
#define sentinel 2000000000 

typedef long long ll;
int n;
ll coun = 0;

int L[Max/2+2],R[Max/2+2];

ll merge(int A[],int left,int mid,int right)
{
	ll cnt = 0;
	int i,j;
	int n1 = mid - left ;
	int n2 = right - mid;
	for(i=0;i<n1;i++) L[i] = A[left+i];
	for(j=0;j<n2;j++) R[j] = A[mid+j];
	L[n1]=R[n2]=sentinel;
	i = j = 0;
	for(int k=left;k<right;k++)
	{
		if(L[i]<=R[j])
		{
			A[k] = L[i++];
			coun =coun+ j; 
			cnt += j;
		}
		else
		{
			A[k] = R[j++];
			//cnt+=n1-i;
		}
	}
	return cnt;
}

ll mergeSort(int A[],int left,int right)
{
	ll c1,c2,c3;
	if(left+1<right)
	{
		int mid = (left+right)/2; 
		c1 = mergeSort(A,left,mid);
		c2 = mergeSort(A,mid,right);
		c3 = merge(A,left,mid,right);
		return c1 + c2 + c3;
	}
	else return 0;	
}

int main()
{
	int A[Max];
	ll cnt;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>A[i];	
	}
	cnt = mergeSort(A,0,n);
	//cout<<cnt<<endl;
	cout<<coun<<endl;
	return 0;
	
}



Measured memory_bytes: 4644
#include <iostream>

using namespace std;

int t,n,i,j,m,k,q[200005],sum,a,b,c,nr;
string s,x;

int main() 
{
    cin>>s>>x;
    for (int i=0; i<s.size(); i++){
        if (s[i]!=x[i]) nr++;
    }
    cout<<nr;

}

Measured memory_bytes: 3848
#include <queue>
#include <cstdio>
#include <iostream>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <time.h>
#include <functional>
using namespace std;
typedef long long int ll;

#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(int i=0;i<n;i++)

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

ll beki(ll a, ll b) {
    ll tmp = 1;
    REP(i, b) tmp *= a;
    return tmp;
}

ll K;
queue<ll> que;
ll ans[100010];
ll num = 0;
ll nowNum = 0;

int main() {



    cin >> K;
    if (K <= 9)
    {
        cout << K << endl;
        return 0;
    }
    //queに1の桁をつめる
    for (ll i = 1; i <= 9; i++)
    {
        que.push(i);
        ans[num] = i;
        num++;
        nowNum++;
    }

    //queにつまってるやつまでのをやるまでやる
    while (true) {
        //n回めはn桁のものをn+1桁にする
        for (ll i = 0; i < nowNum; i++) {
            for (ll j = -1; j <= 1; j++) {
                //ここで0、1、2とかを後ろにつける
                ll a = que.front();
                ll b = a % 10;

                if (b == 0 && j == -1) continue;
                if (b == 9 && j == 1) continue;
                que.push(a * 10 + b + j);
                ans[num] = a * 10 + b + j;
                num++;
                if (num == K) {
                    cout << ans[K - 1] << endl;
                    //REP(i, K) {
                    //    cout << ans[i] << endl;
                    //}
                    return 0;
                }
            }
            que.pop();
        }

        //最後にもどす
        nowNum = num - nowNum;
    }


}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int N,K,X,Y ;
  cin >> N >> K >> X >>Y;
  if(N <= K){
   cout << N*X << endl;
  }else{
   cout << K*X + (N-K)*Y << endl;
  }
  
 
}

Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w; cin >> h >> w;
    V< V<char> > s(h, V<char>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) cin >> s[i][j];
    }

    V< V<int> > dist(h, V<int>(w, INF));
    dist[0][0] = (s[0][0] == '#' ? 1 : 0);
    for (int i = 1; i < w; i++) {
        if (s[0][i - 1] == s[0][i] || s[0][i] == '.') dist[0][i] = dist[0][i - 1];
        else dist[0][i] = dist[0][i - 1] + 1;
    }
    for (int i = 1; i < h; i++) {
        if (s[i - 1][0] == s[i][0] || s[i][0] == '.') dist[i][0] = dist[i - 1][0];
        else dist[i][0] = dist[i - 1][0] + 1;
    }
    for (int i = 1; i < h; i++) {
        for(int j = 1; j < w; j++) {
            chmin(dist[i][j], dist[i - 1][j] + (s[i - 1][j] == s[i][j] || s[i][j] == '.' ? 0 : 1));
            chmin(dist[i][j], dist[i][j - 1] + (s[i][j - 1] == s[i][j] || s[i][j] == '.' ? 0 : 1));
        }
    }

    cout << dist[h - 1][w - 1] << '\n';
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
unordered_set<string> ans;


int main(){
    int n; cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    for(int i = 0; i<=999; i++){
        int c[3] = {i / 100, (i / 10) % 10, i % 10 };
        int f = 0;
        for(int j = 0; j<n; j++){
            if(s[j] == ('0' + c[f]))f++;
            if(f == 3)break;
        }
        if(f == 3) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

using namespace std;
#define INF 1000007
#define MOD 1000000007
#define maxn 101
#define maxh 1001
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
const int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};
typedef std::pair<int, int> P;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *) array, (T *) (array + N), val);
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) { return a / gcd(a, b) * b; }

bool IsPrime(int num) //素数判定
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

vector<int> divisor(int n) //約数列挙
{
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i - 1);
            if (i * i != n) {
                ret.push_back((n / i) - 1);
            }
        }
    }
    sort(ret.begin(), ret.end());
    return (ret);
}

int a, b;

void f(int x) {
    while (x) {
        a++;
        b = x;
        x /= 10;
    }
}

signed main() {
    int A, B, T, ans;
    ans = 0;
    cin >> A >> B >> T;
    for (int i = A; i <= T; i = i + A) {
        ans += B;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from copy import deepcopy

def binary(x, n):
  l = []
  for i in range(n):
    l.append(x%2==1)
    x //= 2
  return l

def main():
  h, w, k = map(int, input().strip().split())
  mat = numpy.array([[1 if c=='#' else 0 for c in input().strip()] for _ in range(h)])
  
  def f(mat, i, j):
    mat[binary(i, h)] = 0
    mat[:, binary(j, w)] = 0
    return mat.sum() == k
  
  cnt = 0
  for i in range(2 ** h):
    for j in range(2 ** w):
      if f(deepcopy(mat), i, j):
        cnt += 1
  print(cnt)
      
if __name__=='__main__':
  main()


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

#define in cin
#define out cout

#define REP(i,n) for(int i=0; i<n; i++)
#define REP2(i,s,e) for(int i=s; i<e; i++)
#define REPE(i,s,e) for(int i=s; i<=e; i++)
#define REPR(i,s,e) for(int i=s; i>=e; i--)

#define all(v) v.begin(), v.end()
#define pb push_back

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rd(n) scanf("%d", &n)

#define x first
#define y second
#define intINF 2147483647
#define llINF 9223372036854775807LL
#define MOD 1000000007

int main()
{
    string deck[3];
    in >> deck[0] >> deck[1] >> deck[2];

    int turn = 0;
    int pos[3] = {0, 0, 0};
    while(pos[0] <= deck[0].size() && pos[1] <= deck[1].size() && pos[2] <= deck[2].size())
    {
        if(pos[turn] == deck[turn].size()) break;

        turn = deck[turn][pos[turn]++] - 'a';
        //out << pos[0] << " " << pos[1] << " " << pos[2] << "\n";
    } out << char(turn+'A') << "\n";

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

signed main(){
    int a,b,c,d,e,k;
    cin >> a >> b >> c >> d >> e >> k;
    if(e-a <= k){
        cout << "Yay!" << endl;
    }else cout << ":(" << endl;
    
    
    return 0; 
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc123.contest.atcoder.jp/tasks/abc123_a

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const ll mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int h, n;
    cin >> h >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i)  cin >> a[i];
    int sum = accumulate(a.begin(), a.end(), 0);
    if(sum >= h)    cout << "Yes\n";
    else    cout << "No\n";
}

Measured memory_bytes: 640
S = list(input())
ACGT = ['A','C','G','T']
 
tans = 0
ans = 0
 
for i in range(len(S)):
  if S[i] in ACGT:
    tans += 1 
    if ans < tans:
        ans = tans
  else:
    tans = 0


print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;



string t="ACGT";

int main(){
    int n,q;cin >> n >> q;
    string s;cin >> s;
    vector<int> a(n,0),sum(n+1,0);
    for (int i = 0; i < n-1; i++) {
        if(s[i]=='A'&&s[i+1]=='C'){
            a[i]++;
            a[i+1]++;
        }
    }
    for (int i = 0; i < n; i++) {
        sum[i+1] = sum[i] + a[i];
    }
    for (int i = 0; i < q; i++) {
        int l,r;cin >> l >> r;
        l--;
        int ans = sum[r] - sum[l];
        if(s[l]=='C') ans-=a[l];
        if(s[r-1]=='A') ans-=a[r-1];
        cout << ans/2 << endl;
    }
    return 0;
}



Measured memory_bytes: 1792
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

// vectorの重複削除
// std::sort(test.begin(), test.end());
// test.erase(std::unique(test.begin(), test.end()), test.end());

using namespace std;
using ll = long long;
using P = pair<int, int>; // vector<P> ba(n); みたいな感じですぐ使える ba[i] = P(a, b); make_pairをしなくてもいい
// typedef vector<int> v;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
#define rep(i, c) for(int i = 0; i < int(c); i++)
#define ALL(x) (x).begin(), (x).end() //sort(ALL(obj))みたいな
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値
#define pb push_back
#define pf push_front //dequeの時に使うはず
// const int MOD = 1000000007;


int main() {
  deque<char>deq;
  string s;
  char c;
  int n;
  int t,f;
  cin >> s >> n;
  rep(i, s.size()) deq.pb(s[i]);
  
  bool flag = true;
  rep(i,n) {
    cin >> t;
    if (t == 1) flag = !flag;
    else {
      cin >> f >> c;
      if (f == 1) {
        if (flag) deq.pf(c);
        else deq.pb(c);

      } else {
        if (flag) deq.pb(c);
        else deq.pf(c);
      }
    }
  }
  if (flag) {
    for_each(deq.begin(), deq.end(), [](char x) {
      cout << x;
    });
  } else {
    for_each(deq.rbegin(), deq.rend(), [](char x) {
      cout << x;
    });
  }
  cout << endl;
}


Measured memory_bytes: 960
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import math
import string


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  res = input()
  letters = string.ascii_letters.lower()
  ans = letters[letters.index(res)+1 % 27]

  return ans


if __name__ == "__main__":
  print(main())


Measured memory_bytes: 4084
import re
  
  
def solve(s, t):
    s = s.replace('?', '.')
    ls, lt = len(s), len(t)
    if ls < lt:
        return 'UNRESTORABLE'
    ans = []
    for i in range(ls - lt + 1):
        m = re.match(s[i:i + lt], t)
        if m is None:
            continue
        ans.append((s[:i] + t + s[i + lt:]).replace('.', 'a'))
    if not ans:
        return 'UNRESTORABLE'
    return min(ans)
  
  
s = input().strip()
t = input().strip()
  
print(solve(s, t))

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

typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cout.tie(0);
    ll a,b,n;
    cin>>a>>b>>n;
    ll x=min(n,b-1);
    double ans=(1.0*(a/(1.0*b))*x);
    ll res=ans;
    ll t=(x/b);
    res-=(a*t);
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 3612
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=3e3+5;
char s1[N],s2[N];
int dp[N][N],pre[N][N];
char s[N];
int main(){
    scanf("%s%s",s1+1,s2+1);
    int len1=strlen(s1+1),len2=strlen(s2+1);
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1,pre[i][j]=-1;
            else{
                if(dp[i-1][j]>dp[i][j-1]){
                    dp[i][j]=dp[i-1][j];
                    pre[i][j]=0;
                }else{
                    dp[i][j]=dp[i][j-1];
                    pre[i][j]=1;
                }
            }
        }
    }
    int top=0;
    for(int i=len1,j=len2;i&&j;){
        if(pre[i][j]==-1){
            s[++top]=s1[i];
            i--,j--;
        }else if(pre[i][j]==0){
            i--;
        }else j--;
    }
    for(int i=top;i;i--) putchar(s[i]);
}


Measured memory_bytes: 70784
#1indexed
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

n = int(input())
s = input()
q = int(input())

bit = [BIT(n+1) for i in range(26)]
for i in range(n):
    bit[ord(s[i])-97].add(i+1, 1)


s = list(s)
for _ in range(q):
    query, a, b = input().split()
    if query == "1":
        i = int(a)
        c = ord(b)-97
        bit[c].add(i, 1)

        bit[ord(s[i-1])-97].add(i, -1)
        s[i-1] = b
    else:
        ans = 0
        for k in range(26):
            if bit[k].sum(int(b))-bit[k].sum(int(a)-1) >= 1:
                ans += 1
        print(ans)


Measured memory_bytes: 171620
#include <iostream>
#include <string>
using namespace  std;

const int cnMaxAry = 1000033;

long long fnStrToLL(string sKey)
{
  int iElm;
  int iBase = 1;
  long long llKey = 0;
  for (int i = sKey.size() - 1; i >= 0; i--)
  {
    switch (sKey[i])
    {
      case  'A': iElm = 1;
                 break;
      case  'C': iElm = 2;
                 break;
      case  'G': iElm = 3;
                 break;
      case  'T': iElm = 4;
                 break;
      default:   iElm = 0;
    }
    llKey += iBase * iElm;
    iBase *= 5;
  }
  return llKey;
}

int fnHash1(long long a_llKey) { return (a_llKey % cnMaxAry); }
int fnHash2(long long a_llKey) { return (1 + (a_llKey % (cnMaxAry - 1))); }

void fnDic(string stasDic[])
{
  int iCmdCnt;
  cin >> iCmdCnt;

  for (int i = 0; i < iCmdCnt; i++)
  {
    string sCmd;
    string sKey;
    cin >> sCmd >> sKey;

    long long llKey = fnStrToLL(sKey);
    int iCnt = 0;
    for (iCnt = 0; ;iCnt++)
    {
      int ix = (fnHash1(llKey) + iCnt * fnHash2(llKey)) % cnMaxAry;
      if (stasDic[ix] == sKey)
      {
        if (sCmd[0] == 'i')
          break;
        else if (sCmd[0] == 'f')
        {
          cout << "yes" << endl;
          break;
        }
      }
      else if (stasDic[ix].size() == 0)
      {
        if (sCmd[0] == 'i')
        {
          stasDic[ix] = sKey;
          break;
        }
        else if (sCmd[0] == 'f')
        {
          cout << "no" << endl;
          break;
        }
      }
    }
  }
}

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

  static string stasDic[cnMaxAry];
  fnDic(stasDic);
  
  return 0;
}

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

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,n,m) for(ll i=n; i>(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define VEC2(x,a,b) vector<vector<ll>> x = vector<vector<ll>>(a,vector<ll>(b,0))
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "; cout<<endl
#define cout(n) cout<<fixed<<setprecision(n)

template<typename T>
vector<T> Divisors(T n)
{
    vector<T> result;

    T boundary = sqrt(n);

    for (T i = 1; i <= boundary; i++) {
        if (n % i == 0) {
            result.push_back(i);
            if(i != (n / i) && i * i != n)
                result.push_back(n/i);
        }
    }
    sort(result.begin(),result.end());
    return result;
}

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

  ll N,M;
  cin>>N>>M;

  vector<ll> v;
  v=Divisors<ll>(M);
  ll res=1;
  FOR(i,0,v.size()){
    if(v[i]>=N) res=max(res,M/v[i]);
  }


  cout<<res<<endl;
}


Measured memory_bytes: 256
/* Atcoder abc147a
 * See tasks at: https://atcoder.jp/contests/abc147/tasks/abc147_a
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
int main()
{
    uint32_t a1, a2, a3;
    cin >> a1 >> a2 >> a3;

    if (a1 + a2 + a3 < 22)
        cout << "win";
    else
        cout << "bust";
    
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Text;

namespace FindPrime
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] arr = new int[N];

            for (int l = 0; l < N; l++)
            {
                arr[l] = int.Parse(Console.ReadLine());
            }

            int count = 0;

            for(int i=0;i<arr.Length;i++)
            {
                bool prime = true;
                int half = (int) Math.Sqrt(arr[i]);
                for(int j = 2; j <= half; j++)
                {
                    if ((arr[i] % j) == 0)
                    {
                        prime = false;
                        break;
                    }
                }

                if (prime == true)
                {
                    count++;
                }
            }

            Console.WriteLine(count);
        }
    }
}

Measured memory_bytes: 5756
<?php

$n = trim(fgets(STDIN));
$first = 0;
$firstKey = 0;
$second = 0;

for($x = 1;$x <= $n ; $x++){
  $a = trim(fgets(STDIN));
  if($a >= $first){
    $second = $first;
    $first = $a;
    $firstKey = $x;
  }else if($a > $second){
    $second = $a;
  }
}


$nums = array_fill(1,$n,$first);
$nums[$firstKey] = $second;
print implode("\n",$nums);

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

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

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
  read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
  match n {
    0 => a,
    _ => {
      a.push(read::<T>());
      read_n_logic(n - 1, a)
    }
  }
}

use std::cmp::{max, min};
use std::collections::BinaryHeap;

fn main() {
  let n: usize = read();
  let mut a: Vec<f64> = read_n(n);
  let a_len = a.len();

  for i in 0..a_len - 1 {
    a.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let min = a.remove(0);
    let second_min = a.remove(0);
    a.push((min + second_min) / 2.0);
  }


  println!("{:?}", a[0]);
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define arep(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> B(N - 1);
    rep(i, 0, N - 1) cin >> B[i];
    int ans = B[0] + B[N - 2];
    rep(i, 1, N - 1) {
        ans += min(B[i - 1], B[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cfloat>
#include <climits>
#include <iomanip>

using namespace std;

int main() {
	int n, m, p, a, b;

	while(true) {
		cin >> n >> m >> p >> a >> b;

		if( !m && !n && !p && !a && !b ) {
			break;
		}

		vector< vector< double > > dp(1 << n, vector< double >(m + 1,INT_MAX / 4));
		vector< int > t(n);
		vector< vector< int > > map(m + 1, vector< int >(m + 1, INT_MAX / 4));

		for(int i = 0; i < n; i++) {
			cin >> t[i];
		}
		for(int i = 0; i < p; i++) {
			int x, y, z;
			cin >> x >> y >> z;

			map[x][y] = z;
			map[y][x] = z;
		}

		dp[0][a] = 0;

		for(int s = 0; s < (1 << n); s++) {
			for(int i = 0; i < n; i++) {
				for(int j = 1; j <= m; j++) {
					for(int k = 1; k <= m; k++) {
						if(map[j][k] == INT_MAX / 4) {
							continue;
						}
						if(!(s >> i & 1)) {
							int next = s | (1 << i);
							dp[next][k] = min(dp[next][k], dp[s][j] + ((double)map[j][k] / t[i]));
						}
					}
				}
			}
		}

		double ans = INT_MAX / 4;
		for(int s = 0; s < (1 << n); s++) {
			ans = min(ans, dp[s][b]);
		}


		cout << setprecision(3) << fixed;

		if(ans == INT_MAX / 4) {
			cout << "Impossible" << endl;
		} else {
			cout  << ans << endl;
		}
	}
}

Measured memory_bytes: 1364
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        sc.nextLine();
        String[] y = sc.nextLine().split(" ");
        int[] x = new int[y.length];
        int min = Integer.MAX_VALUE;
        int count = 0;
        for(int i = 0;i<x.length;i++){
            x[i] = Integer.parseInt(y[i]);
            if(min>x[i]){
                min = x[i];
                count = 1;
            }else if(min==x[i]){
                count++;
            }
        }
        int answer = (n-count+k-2)/(k-1);
        System.out.println(answer);
    }
}

Measured memory_bytes: 48856
n,m=map(int,input().split())

if n>=2 and m>=2:
    print(n*(n-1)//2+m*(m-1)//2)
elif n<=1 and m>=2:
    print(m*(m-1)//2)
elif n>=2 and m<=1:
    print(n*(n-1)//2)
else:
    print(0)

Measured memory_bytes: 3060
program main
  implicit none
  integer :: n, i, mi
  integer, allocatable :: a(:)
  read(*, *) n
  allocate(a(n))
  read(*, *) (a(i), i = 1, n)
  mi = 999999
  do i = 1, n
    mi = min(mi, fact_of_two(a(i)))
  end do
  write(*, "(i0)"), mi
  deallocate(a)

  contains

  function fact_of_two(i)
    implicit none
    integer :: i, j, fact_of_two
    do j = 0, 100
      if (mod(i, 2 ** j) /= 0) then
        exit
      end if
    end do
    if (j < 1) stop 1
    fact_of_two = j - 1
  end function fact_of_two
end


Measured memory_bytes: 768
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

x = s()
print(x[:4]+" "+x[4:])


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

int main() {
	int n; 
	string s;
	unordered_map<string, int> _map;
	
	cin >> n;
	
	while(n--) {
		cin >> s;
		if(_map.find(s) != _map.end())
			_map[s]++;
		else _map[s] = 1;
	}
		
	for(auto str: {"AC", "WA", "TLE", "RE"})
		cout << str << " x " << _map[str] << endl;
		
	return 0;
}

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

// n回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii;  // 2次元配列
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> PII;

template<typename T>
using vec = vector<T>;
template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int _StartTime_ = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    // cout << fixed << setprecision(15);

    string s;
    int a,b,c;
    cin >> a >> b;


    cout <<             a*(a-1)/2 + b*(b-1)/2               << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-_StartTime_)/CLOCKS_PER_SEC));
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <map>
#include <queue>
#include <bitset>
#include <sstream>
#include <iomanip>

using namespace std;
typedef long long ll;


int main(){
        ll X, t;
        cin >> X >> t;
        cout << max(X-t, 0LL);

}


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

using namespace std;

#define int long long

void solve() {
    int k, n;
    cin >> k >> n;
    int a[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    int ans = k - (a[0] + k - a[n - 1]);
    for (int i = 1; i < n; ++i) ans = min(ans, k - a[i] + a[i - 1]);
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 1792
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

N,K=map(int,input().split())
P=list(map(int,input().split()))
P.sort()
print(sum(P[:K]))


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

const int N = 1e6+1;

char ch[N];
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll int n; 
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> ch[i];
	}
	
		
		
		ll int cnt = 0;
		for(int i = 0; i < n; ++i)
		{
			if(ch[i] == 'W')
			{
				cnt++;
			}
		}
		
		ll int ans = cnt;
		for(int i = (n); i > n-cnt; --i)
		{
			if(ch[i] == 'W')
			{
				ans--;
			}
		}
		
		cout << ans << "\n";
		
		
	
}

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

long long digits(long long N) { return to_string(N).length(); }
void solve(long long N) {
    long long ans = 20;
    for (long long i = 1; i <= sqrt(N); i++) {
        long long A = i;
        if (N % i != 0) continue;
        long long B = N / i;
        long long f = max(digits(A), digits(B));
        ans = min(ans, f);
    }
    cout << ans << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can
// remove this line by using your custom template)
int main() {
    long long N;
    scanf("%lld", &N);
    solve(N);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 100000000
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(g);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()


typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;

#ifdef TESTING
#define DEBUG fprintf(stderr,"====TESTING====\n")
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define DEBUG 
#define VALUE(x)
#define debug(...)
#endif
/*
inline string IntToString(ll a) {
	char x[100];
	sprintf_s(x, "%lld", a); string s = x;
	return s;
}

inline ll StringToInt(string a) {
	char x[100]; ll res;
	strcpy_s(x, a.c_str()); sscanf_s(x, "%lld", &res);
	return res;
}
*/

inline string uppercase(string s) {
	int n = SIZE(s);
	rep(i, n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
	return s;
}

inline string lowercase(string s) {
	int n = SIZE(s);
	rep(i, n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
	return s;
}

int main()
{
	ll a, b, ans = 0;
	cin >> a >> b;
	if (a == 0 || b == 0) {
		cout << "0" << endl;
	}
	else if (a == 1 && b == 1)
		puts("1");
	else if (a == 1 || b == 1) {
		cout << a*b - 2 << endl;
	}
	
	else
		cout << (a-2) * (b-2) << endl;
	return 0;
}


Measured memory_bytes: 256
/*
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
typedef mp::cpp_int mint; //*/
#include <bits/stdc++.h>
#define  re(i,j,n) for(li i=(j);i<(n);i++)
#define  rep(i,n) re(i,0,(n))
#define  red(i,n) for(li i=n;i>0;i--)
#define  all(a) begin(a),end(a)
#define  pb(a) push_back(a)
using namespace std;
typedef long int li;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<string> vs;


int main()
{
    li x=0,m;
    string s;
    cin>>m>>s;
    m=0;
    for(char c:s){
        if(c=='I') x++;
        if(c=='D') x--;
        if(m<x)m=x;
    }
    cout<<m<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>
#include<queue>

using namespace std;

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

int main(){
    int n, m;
    cin >> n >> m;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        q.push(a);
    }
    vector<pair<int, int>> d(m);
    for(int i = 0; i < m; i++){
        int b, c;
        cin >> b >> c;
        d[i] = make_pair(c, b);
    }
    sort(rbegin(d), rend(d));
    for(int i = 0; i < m; i++){
        auto p = d[i];
        for(int j = 0; j < p.second; j++){
            int t = q.top();
            if(t >= p.first){
                i = m;
                break;
            }
            q.pop();
            q.push(p.first);
        }
    }
    ll ans = 0;
    while(!q.empty()){
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1528
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<utility>
#include<functional>
#include<stack>
#include<queue>
#include<cmath>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
# define MOD 1000000000+7
# define INF 1000000000
typedef long long ll;
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int main() {

	/*
	int n, m, a, b;
	int ans = 0, r = 0;
	vector<int> v;
	bool list[100][100] = { false };
	
	cin >> n >> m;

	rep(i, m) {
		cin >> a >> b;
		list[a - 1][b - 1] = true;
		list[b - 1][a - 1] = true;
	}
	rep(i, n) {
		v.push_back(i);
	}

	do {

		rep(i, n - 1) {

			if (list[v[i]][v[i + 1]] == true || list[v[i + 1]][v[i]] == true) {
				r++;
			}
		}

		if (r == n - 1 && v[0] == 0) ans++;

		r = 0;

	} while (next_permutation(v.begin(), v.end()));
	
	cout << ans << endl;

	*/

	int n = 0;
	int h[100000] = {};
	int dp[100010] = {};
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[i] = INF;
	}
	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		if (i == 2) {
			dp[i] = abs(h[i - 1] - h[i]);
		}
		else {
			dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]));
		}
	}

	cout << dp[n] << endl;


}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7,INF=1e18;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t=1;
    // cin>>t;
    while(t--)
    {
        string s,t;
        cin>>s;
        cin>>t;
        int n=s.size(),m=t.size();
        vector<vector<int> > a(n);
        for(int i=0;i<n;i++)
        {
            a[i].resize(m,0);
            for(int j=0;j<m;j++)
            {
                if(s[i]==t[j])
                {
                    if(i!=0&&j!=0)
                    {
                        a[i][j]=1+a[i-1][j-1];
                    }
                    else
                    {
                        a[i][j]=1;
                    }
                }
                else
                {
                    if(i!=0)
                    a[i][j]=max(a[i-1][j],a[i][j]);
                    if(j!=0)
                    a[i][j]=max(a[i][j-1],a[i][j]);
                }
            }
        }
        string s1="";
        int i=n-1,j=m-1;
        while(a[i][j])
        {
            if(i==0)
            {
                s1.push_back(s[i]);
                break;
            }
            if(j==0)
            {
                s1.push_back(t[j]);
                break;
            }
            if(a[i-1][j]==a[i][j])
            {
                i--;
            }
            else if(a[i][j-1]==a[i][j])
            {
                j--;
            }
            else
            {
                s1.push_back(s[i]);
                i--,j--;
            }
        }
        reverse(s1.begin(),s1.end());
        cout<<s1<<"\n";
    }
    return 0;
}

Measured memory_bytes: 38824
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
const ll INF = 1e17;

// a*x - b*y = return value = GCD(a,b). x,y >= 0
ll egcd(ll a, ll b, ll &x, ll &y) { // MINUS B*Y
	if (b == 0) {
		x = 1; y = 0;
		return a;
	}

	ll d = egcd(b, a%b, y, x);
	y = a - x * (a / b) - y;
	x = b - x;
	return d;
}
// modular inverse; works for any mod p (coprime with a)
ll inverse(ll a, ll p=mod) {
	ll x, y;
	egcd(a%p + p, p, x, y);
	return x % p;
}

ll fact[(int)2e5 + 1];
void fillFact() {
	fact[0] = 1;
	for (int i = 1; i < 2e5 + 1; i++) {
		fact[i] = fact[i - 1] * i;
		fact[i] %= mod;
	}
}

//Be sure to fillFact() before using this
//nCk with mod, uses mult inverse
//here assumes mod is prime, otherwise use egcd
ll choose(ll n, ll k) {
	if (k > n) { return 0; }
	ll num = fact[n], denom = fact[k];
	denom *= fact[n - k]; denom %= mod;

	ll multInv = inverse(denom);
	num *= multInv; num %= mod;
	return num;
}

struct edge {
	int u, v; ll w;
	edge() {}
	edge(int _u, int _v, ll _w) :
		u(_u), v(_v), w(_w) {}
};

struct node { vector<edge> edges; };
vector<ll> ans;
//Everything is 0-indexed
struct tree {
	vector<node> nodes;
	vector<int> parent, subtreeSize;
	vector<ll> ways;
	int root, n;

	tree(int _n, int _r = 0) : n(_n), root(_r) { nodes.resize(n); parent.resize(n, -1); subtreeSize.resize(n, 1); ways.resize(n, 1); }

	void add_edge(int u, int v, ll w = 1ll) {
		edge e1(u, v, w); edge e2(v, u, w);
		nodes[u].edges.push_back(e1);
		nodes[v].edges.push_back(e2);
	}

	void dfs(int u, int p) {
		ll res = 1;
		vector<ll> childSubtree;
		for (auto &e : nodes[u].edges) {
			if (e.v == p) { continue; }
			parent[e.v] = u;
			dfs(e.v, u);
			subtreeSize[u] += subtreeSize[e.v];
			res *= ways[e.v]; res %= mod;
			childSubtree.push_back(subtreeSize[e.v]);
		}
		if (childSubtree.empty()) { return; }

		ll prefix = childSubtree[0];
		for (int i = 1; i < childSubtree.size(); i++) {
			ll cur = childSubtree[i]; prefix += cur;
			res *= choose(prefix, cur); res %= mod;
		}

		ways[u] = res;
	}

	void reroot(int u, int p) {
		ans[u] = ways[u];

		for (auto &e : nodes[u].edges) {
			if (e.v == p) { continue; }

			ll prevWaysU = ways[u], prevWaysV = ways[e.v];

			ways[u] *= inverse(ways[e.v]); ways[u] %= mod;
			ways[u] *= inverse(choose(n-1, subtreeSize[e.v])); ways[u] %= mod;
	
			subtreeSize[u] -= subtreeSize[e.v];
			subtreeSize[e.v] += subtreeSize[u];

			ways[e.v] *= ways[u]; ways[e.v] %= mod;
			ways[e.v] *= choose(n-1, subtreeSize[u]); ways[e.v] %= mod;

			reroot(e.v, u);

			ways[u] = prevWaysU; ways[e.v] = prevWaysV;

			subtreeSize[e.v] -= subtreeSize[u];
			subtreeSize[u] += subtreeSize[e.v];
		}
	}
};

int main() {
	fillFact();
	int n; cin >> n;
	tree t(n);
	for (int i = 0; i < n-1; i++) {
		int u, v; cin >> u >> v; u--; v--;
		t.add_edge(u, v);
	}
	ans.resize(n);
	t.dfs(0, -1);
	t.reroot(0, -1);

	for (auto &x : ans) { cout << x << endl; }
}

Measured memory_bytes: 24172
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Vec2(T, n, m, xs, x0) vector<vector<T>> xs(n, vector<T>(m, x0))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n, ap);
    bool isUp = true, isDown = true;
    int ans = 1;
    For(i, n-1){
        Cin(int, a);
        if(a > ap) isDown = false;
        if(a < ap) isUp = false;
        ap = a;
        if(isUp || isDown) continue;
        ans ++;
        isUp = isDown = true;
    }
    Cout(ans);
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader br = new BufferedReader(new FileReader("in1.txt"));
		// BufferedReader br = new BufferedReader(new FileReader("in2.txt"));
		int n = Integer.parseInt(br.readLine());
		List<Integer> A = new ArrayList<Integer>();
		for (int i = 0; i < n; i++)
			A.add(Integer.parseInt(br.readLine()));
		
		// G?????¨?????????
		List<Integer> G = new ArrayList<Integer>();
		G.add(1);
		int m = 1;
		while (true) {
			int G_m = 2 * (G.get(m - 1) + 1) - 1;
			if (G_m > n)
				break;
			G.add(G_m);
			m++;
		}
		Collections.reverse(G);
		
		// ?????§????????????
		int cnt = 0;
		for (int k = 0; k < m; k++) {
			int g = G.get(k);
			for (int i = g; i < n; i++) {
				int v = A.get(i);
				int j = i - g;
				while (j >= 0 && A.get(j) > v) {
					A.set(j + g, A.get(j));
					j = j - g;
					cnt++;
				}
				A.set(j + g, v);
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(m);
		sb.append('\n');
		for (int g : G) {
			sb.append(g);
			sb.append(' ');
		}		
		sb.deleteCharAt(sb.length() - 1);
		sb.append('\n');
		sb.append(cnt);
		sb.append('\n');		
		for (int a : A) {
			sb.append(a);
			sb.append('\n');
		}
		System.out.println(sb.toString());
	}
}

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

using namespace std;

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.length();
    bool is_rotation = false;
    for (int i = 0; i < n; ++i) {
        bool is_rotation_i = true;
        for (int j = i, cnt = 0; cnt < n; j = (j + 1) % n, cnt++) {
            if (s[j] != t[cnt]) {
                is_rotation_i = false;
                break;
            } 
        }
        if (is_rotation_i) {
            is_rotation = true;
            break;
        }
    }
    if (is_rotation) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    vector<vector<ll>> ind(100);
    rep(i,len(s)){
      ind[s[i]-'0'].push_back(i);
    }
    ll num=0;
    ll now;
    char now2;
    rep(i,len(t)){
      if(len(ind[t[i]-'0'])==0){
        cout<<-1<<endl;
        return 0;
      }
      if(i==0){
        now=ind[t[i]-'0'][0];
        now2=t[i];
        continue;
      }
      auto itr=upper_bound(begin(ind[t[i]-'0']),end(ind[t[i]-'0']),now);//-begin(ind[t[i]-'0']);
      if(itr==end(ind[t[i]-'0'])){
        num++;
        now=ind[t[i]-'0'][0];
      }else{
        now=*itr;
      }
      //cout<<t[i]<<' '<<num<<endl;
    }
    //cout<<num<<endl;
    ll ans=num*len(s)+now+1;
    cout<<ans<<endl;
}

Measured memory_bytes: 1736