akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef list<int> LISTINT;
int main(){
    int n;
    int m;
    while(scanf("%d",&n)!=EOF){
    LISTINT l;
    LISTINT::iterator i;
        int time=1;
        for(int j=0;j<n;j++){
            scanf("%d",&m);
            time=!time;
            if(time) l.push_back(m);
            else l.push_front(m);
        }
        if(!(n&1)) l.reverse();
        for(i=l.begin();i!=l.end();++i)
            printf("%d ",*i);
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 8448
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
    ArrayList<Integer> list = new ArrayList<Integer>();
    String line = sc.nextLine();
    int n = Integer.parseInt(line);
    String line1 = sc.nextLine();
    String[] linesp1 = line1.split(" ");
    for(int i = 0; i < n; i++) {
        list.add(Integer.parseInt(linesp1[i]));
    }
    int max = list.get(0);
    int min = list.get(0);
    long sum = 0;
    for(int i = 0; i < list.size(); i++) {
        int num = list.get(i);
        if(num > max) {
            max = num;
        }
        if(num < min) {
            min = num;
        }
        sum += num;
    }
    System.out.println(min + " " + max + " " + sum);
  }
}


Measured memory_bytes: 33168
def main():
    n, k = map(int, input().split())
    while True:
        if n % k == 0:
            n = 0
            break
        else:
            if n // k == 0:
                if n > abs(n - k):
                    n = abs(n - k)
                break
            else:
                n = n % k
    print(n)


if __name__ == "__main__":
    main()


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

ll parallel(ll H, ll W){
    ll ret;
    if(H%3==0){
        ret = 0;
    }else{
        ll Smax = (H/3 + 1)*W;
        ll Smin = (H/3)*W;
        ret = Smax - Smin;
    }
    return ret;
}

ll composite(ll H, ll W){
    ll ret = 1e18;
    for(int h=1; h<H; h++){
        vector<ll> S(3, 0);
        S[0] = h*W;
        if(W%2==0){
            S[1] = (H-h)*(W/2);
            S[2] = (H-h)*(W/2);
        }else{
            S[1] = (H-h)*(W/2);
            S[2] = (H-h)*(W/2+1);
        }
        sort(S.begin(), S.end());
        ret = min(ret, S[2] - S[0]);
    }
    return ret;
}

int main(){
    ll H, W;  cin >> H >> W;
    ll ans = 1e18;

    ans = min(ans, parallel(H, W));
    ans = min(ans, parallel(W, H));
    ans = min(ans, composite(H, W));
    ans = min(ans, composite(W, H));
    cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
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; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> D(N); rep(i, 0, N) { cin >> D[i]; }
	int M; cin >> M;
	vector<int> T(M); rep(i, 0, M) { cin >> T[i]; }
	map<int, int>m;
	rep(i, 0, N) {
		m[D[i]]++;
	}
	bool f(true);

	rep(i, 0, M) {
		if (m[T[i]])m[T[i]]--;
		else f = false;
	}

	cout << (f ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 12288
#include<iostream>
#include<math.h>
#include<string.h>
#include<vector>
using namespace std;

int main(){
	int a,b;
	cin >> a >> b;
	int ans;
	
	if(b/10==0){
		ans=10*a+b;
	}else if(b/100==0){
		ans=100*a+b;
	}else if(b/1000==0){
		ans=1000*a+b;
	}
	
	for(int i=0;i*i<=ans;i++){
		if(i*i==ans){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        input_inner!{$s, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($exp_input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                let start = std::time::Instant::now();
                let input = solve($exp_input);
                let end = start.elapsed();
                assert_eq!(input, $output, "{}.{:03}", end.as_secs(), end.subsec_millis());
                assert!(end.as_secs() <= 2, "expected_sec: {}sec, actual_sec: {}sec", 2, end.as_secs());
                assert!(end.as_secs() <= 1, "expected_sec: {}sec, actual_sec: {}sec", 1, end.as_secs());
                assert!(end.subsec_millis() <= 10, "expected_ms: {}ms, actual_ms: {}ms", 10, end.subsec_millis());
                assert!(end.subsec_millis() <= 2, "expected_ms: {}ms, actual_ms: {}ms", 2, end.subsec_millis());
            )*
        }
    };
}

test! {
r#"10 3
4 5 6"# => r#"Yes"#,

r#"20 3
4 5 6"# => r#"No"#,

r#"210 5
31 41 59 26 53"# => r#"Yes"#,

r#"211 5
31 41 59 26 53"# => r#"No"#,
}

fn solve(src: &str) -> String {
    let mut src_iter = src.split_whitespace();
    input! {
        source = src_iter,
        h: usize,
        n: usize,
        a: [usize; n]
    }

    let a_sum = a.iter().sum::<usize>();

    if h <= a_sum {
        "Yes"
    } else {
        "No"
    }.to_string()
}

Measured memory_bytes: 6396
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */


vector<vector<ll>> calc(vector<ll>& A){
    vector<vector<ll>> dp(A.size()+1,vector<ll>(16));
    ll N = A.size();
    for(ll i = N-2; i >= 0;i--){
        for(ll j = 0; j <= 15;j++){
            ll add = LLONG_MAX;
            
            ll nowA = A[i] * (1LL << (2*j)); // 4^jを乗じた値
            if(nowA <= A[i+1]){
                add = dp[i+1][0]; // 操作の必要がない
            }else{
                // 何回操作したら超えるか
                ll cnt = 0;
                ll mul = (A[i+1] + nowA-1)/A[i+1];
                while(!(mul <= 1LL<<(cnt*2))) cnt++;
                if(cnt > 15){
                    ll diff = cnt - 15;
                    add = (N-1-i)*2*diff + 15*2 + dp[i+1][15];
                }else{
                    add = cnt*2 + dp[i+1][cnt];
                }
            }
            
            dp[i][j] = add;
        }
    }
    return dp;
}
template<class Type>
Type solve(Type res = Type()){
    int N; cin >> N;
    vector<ll> A(N);for(auto& in:A) cin >> in;
    auto dp1 = calc(A); // pos
    reverse(A.begin(),A.end());
    auto dp2 = calc(A); // neg
    
    res = min(dp1[0][0],dp2[0][0]+N);
    for(ll i = 1; i < N;i++){
        res = min(res,dp1[i][0] + dp2[N-i-1][0] + i);
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 67456
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))


k,s = map(int,input().split())

cnt = 0

for i in range(min(k,s)+1):
    for j in range(min(k,s)+1):
        memo = s-i-j

        if 0<=memo and memo<=k:
            cnt += 1
            

print(cnt)

Measured memory_bytes: 2940
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

n = int(input())
A = list(map(int, input().split()))

index = partition(A, 0, n - 1)
A[index] = "[" + str(A[index]) + "]"
A = map(str, A)
print(" ".join(A))


Measured memory_bytes: 16388
#include<iostream>
#include<algorithm>
using namespace std;
long long a[10001],b[10001];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
		a[i] -= b[i];
	}
	long long sum = 0; long long  need = 0; long long can;
	if (sum > 0){
		cout << "No" << endl;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (a[i] < 0) {
			need += (-a[i] + 1) / 2;
		}
	}
	can = -sum;
	if (need <= can) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int>PAIR;
const int maxn = 200005;
map<int,int>mp;

int a[maxn];
int cmp(const PAIR& x,const PAIR& y)
{
    return x.second<y.second;
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);

    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        mp[a[i]]++;
    }
    vector<PAIR>ve(mp.begin(),mp.end());
    sort(ve.begin(),ve.end(),cmp);

    /*for( vector<PAIR>::iterator i = ve.begin();i!=ve.end();i++)
        cout<<i->first<<' '<<i->second<<endl;*/

    int num = mp.size();
    int ans=0;


    if(k<num)
    {
        vector<PAIR>::iterator i = ve.begin();
        for(int j=1; i!=ve.end(),j<=num-k; i++,j++)
        {
            ans+=i->second;
            //cout<<"j== "<<j<<endl;
        }
    }
    else ans=0;

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


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

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
// const int mod = 1e9 + 7;

#define mem(a, b) memset(a, b, sizeof(a))
#define REP(i, a) for (int i = 0; i < a; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(a) a.begin(), a.end()

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

inline void print_vector(vector<int> &A){
    for (auto&& x : A){
        cout << x << " ";
    }
    cout << endl;
}

inline void print_array(const int A[], int n) {
    REP(i, n) {
        cout << A[i] << " ";
    }
    cout << endl;
}

inline void solve() {
    int n, k;
    cin >> n >> k;
    set<int> s;
    for (int i = 1; i <= n; i++) {
        s.insert(i);
    }

    for (int i = 0; i < k; i++) {
        int nxt;
        cin >> nxt;
        for (int i = 0; i < nxt; i++) {
            int t;
            cin >> t;
            s.erase(t);
        }
    }

    cout << s.size() << endl;
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    int t = 1;
    // cin >> t;

    for (int _ = 0; _ < t; _++) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
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; }

string ans;

void dfs(string f, int sum, string s, int i){
    if (i == 4){
        if (sum == 7){
            ans = f + "=7";
        }
        return;
    }
    dfs(f + "+" + s[i], sum+(s[i]-'0'), s, i+1);
    dfs(f + "-" + s[i], sum-(s[i]-'0'), s, i+1);
}

int main(){
    string s;
    cin >> s;
    dfs({s[0]}, s[0]-'0', s, 1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3576
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

void Pr(bool f){
  cout << (f ? "Yes" : "No") << "\n";
  exit(0);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  vs ans={"pon", "pon", "hon", "bon", "hon", "hon", "pon", "hon", "pon", "hon"};
  ll n;
  cin >> n;
  print(ans[n%10]);
}


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;

const int limit=50;
int N,M;
int a[limit]={0},b[limit]={0};

bool graph[limit][limit];
bool visited[limit];

void dfs(int x){
  visited[x]=true;
  for(int i=0;i<N;i++){
    if(graph[x][i]==false) continue;
    if(visited[i]==true) continue;
    dfs(i);
  }
}

int main(){

  cin >> N >> M;
  for(int i=0;i<M;i++){
    cin >> a[i] >> b[i];
    a[i]--,b[i]--;
    graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;
  }

  int ans=0;
  for(int i=0;i<M;i++){
    graph[a[i]][b[i]]=graph[b[i]][a[i]]=false;
    for(int j=0;j<N;j++) visited[j]=false;
    dfs(0);
    bool bridge=false;
    for(int j=0;j<N;j++) if(visited[j]==false) bridge=true;
    if(bridge) ans+=1;
    graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;
  }

  cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

char s[200];

int main()
{
	int lev=0, ml=0;
	scanf("%*d%s", s);
	for(int i=0; s[i]; ++i){
		if(s[i] == '('){
			++lev;
		} else --lev;
		ml=min(ml, lev);
	}
	for(int i=ml+1; i<=0; ++i) putchar('(');
	printf("%s", s);
	for(int i=lev-ml-1; 0<=i; --i) putchar(')');
	return 0;
}


Measured memory_bytes: 256
#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,t,n2=1,a[200010],sum[200010],dat[800010],ans=0;
vector <LL> v;
map <LL,LL> mp;

void upd(LL k)
{
	dat[k]++;
	while(k>0)
	{
		k=(k-1)/2;
		dat[k]++;
	}
}

LL query(LL k,LL lb,LL ub,LL tlb,LL tub)
{
	if(ub<tlb||tub<lb) return 0;
	if(tlb<=lb&&ub<=tub) return dat[k];
	return query(k*2+1,lb,(lb+ub)/2,tlb,tub)+query(k*2+2,(lb+ub)/2+1,ub,tlb,tub);
}

int main()
{
	cin>>n>>t;
	rep(i,n)
	{
		scanf("%lld",&a[i]);
		a[i]-=t;
	}
	v.pb(0);
	repn(i,n)
	{
		sum[i]=sum[i-1]+a[i-1];
		v.pb(sum[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	rep(i,v.size()) mp[v[i]]=i;
	while(n2<v.size()+1) n2*=2;
	upd(mp[0]+n2-1);
	repn(i,n)
	{
		ans+=query(0,0,n2-1,0,mp[sum[i]]);
		upd(mp[sum[i]]+n2-1);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 22256
//agc014_a.cpp
//Sat Oct 27 12:49:43 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int x,y,z;
	cin >> x >> y >> z;
	int a = x+y;
	int b = y+z;
	int c = x+z;

	int aeven = 0;
	while (a%2==0){
		aeven++;
		a = a/2;
	}

	int beven = 0;
	while (b%2==0){
		beven++;
		b = b/2;
	}

	int ceven = 0;
	while (c%2==0){
		ceven++;
		c = c/2;
	}

	int ans = aeven;
	if (beven < ans){
		ans = beven;
	}
	if (ceven < ans){
		ans = ceven;
	}

	if (x%2 ==1 || y%2 == 1 || z%2 == 1){
		ans = 0;
	}else if (a == b && b == c && c== a){
		ans = -1;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <sstream>
#include <iostream>
#include <array>
#include <algorithm>

int main(){
    int line_num = 0;
    std :: string sentence, replaced = "Hoshino", replacing = "Hoshina";
    std :: cin >> line_num;
    std :: getline(std :: cin, sentence);
    for(int i = 0;i < line_num;i++){
        std :: getline(std :: cin, sentence);
        std::string::size_type pos = 0;
        while ((pos = sentence.find(replaced, pos)) != std::string::npos) {
            sentence.replace(pos, replaced.length(), replacing);
            pos += replaced.length();
        }
        std :: cout << sentence << std :: endl;
    }
}


Measured memory_bytes: 3140
#include<bits/stdc++.h>                                                                                               
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;

int sum[6000050];
signed main(){
    int n;
    cin >> n;
    if(n == 1){ 
        cout << 1 << '\n';
        return 0;
    }   
    reps(i,n / 2 + 1){ 
        sum[i] = sum[i - 1] + i;
    }   

    int low = 0;
    int high = n+1;
    while(high - low > 1){ 
        int mid = (high + low) / 2;
        if(sum[mid] >= n){ 
            high = mid;
        }
        else{
            low = mid;
        }
    }   
    
    int err = sum[high] - n;
    reps(i,high){
        if(i == err) continue;
        cout << i << '\n';
    }   
    return 0;
}


Measured memory_bytes: 41216
#include <stdio.h>

int main(void) {
    int N,a[100000],b1 = 0,b2 = 0,i;
    scanf("%d",&N);
    for (i = 0; i < N; i++) {
        scanf("%d",&a[i]);
    }
    for (i = 0; i < N; i++) {
        if (a[i] % 4 == 0) {
            b1++;
        } else if (a[i] % 2 == 0) {
            b2++;
        }
    }
    if (b2 != 0) b2--;
    if (b1 * 2 + b2 > N - 2) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 512
#define ll long long int
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const ll y = 1000;
const ll INF = y*y*y*y*y*y;
int main() {
	ll n, k;
	cin >> n >> k;
	vector <ll> h(n);
	for (int i = 0; i < n; i++) cin >> h[i];
	vector <ll> dp(n, INF);
	dp[0] = 0; dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			if (i-j>=0) dp[i] = min(dp[i - j] + abs(h[i - j] - h[i]), dp[i]);
		}
	}
	cout << dp[n - 1];
}

Measured memory_bytes: 1792
#インクルード
import math
#ロジック
N = int(input())
kirisage = math.floor(N / 1.08)
kiriage = math.ceil(N / 1.08)
if N == math.floor(kirisage * 1.08):
  print(kirisage)
elif N == math.floor(kiriage * 1.08):
  print(kiriage)
else:
  print(":(")



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

#define MOD 1000000007

int main()
{
    int N, M;
    cin >> N >> M;

    string A[N];
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    string B[M];
    for (int i = 0; i < M; i++)
    {
        cin >> B[i];
    }

    for (int i = 0; i < N - M + 1; i++)
    {
        for (int j = 0; j < N - M + 1; j++)
        {
            bool is_valid = true;
            for (int k = 0; k < M; k++)
            {
                if (A[i + k].substr(j, M) != B[k])
                {
                    is_valid = false;
                }
            }
            if (is_valid)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
#include<fstream>
#include<array>

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
using namespace std;

const LL MOD = 1000000007;// 10^9+7
const int INF = (1 << 30);

//変数
constexpr int H = 19;
constexpr int W = 15;
int ans = INF;


bool out(const int& count, const pair<int,int>& next)
{
	int y = next.first;
	int x = next.second;

	if (x < 0)return true;
	if (y < 0)return true;
	if (14 < x)return true;
	if (18 < y) {
		ans = min(ans, count);
		return true;
	}
	return false;
}

int gap(pair<int, int> l, pair<int, int> r)
{
	int a = abs(l.first - r.first);
	int b = abs(l.second - r.second);
	return max(a, b);
}

bool goal(const pair<int, int> now)
{
	if (now.first == H)return true;
	if (now.first == H - 1
		&& 0 <= now.second
		&& now.second < W)return true;
	return false;
}

void step(
	const array<array<bool,W>,H>& goban,
	const pair<int,int>& now,
	const int& count)
{
	constexpr int dirSiz = 8;
	constexpr int dh[] = { -1,0,1,1,1,0,-1,-1 };
	constexpr int dw[] = { 1,1,1,0,-1,-1,-1,0 };
	if (ans <= count)return;

	//visualize(goban, now);

	REP(i, dirSiz) {
		auto nextGoban = goban;
		auto next = now;

		while (true) {
			next.first += dh[i];
			next.second += dw[i];
			if (out(count, next))break;

			if (nextGoban[next.first][next.second]) {
				nextGoban[next.first][next.second] = false;
			}
			else {
				break;
			}
		}
		if (gap(now, next) <= 1) {
			continue;
		}
		else {
			if (goal(next)) {
				ans = min(ans, count);
			}
			else {
				if (!out(count, next)) {
					//visualize(goban, now);
					step(nextGoban, next, count + 1);
				}
			}
		}
	}
}


//デバッグ
void debug()
{
	int N;
	cin >> N;
}


//メイン関数
int main()
{
	pair<int, int> start;
	array<array<bool, W>, H> goban;
	REP(i, H) {
		string tmp;
		array<bool,W> row;
		cin >> tmp;
		REP(j,W){
			char c = tmp[j];
			row[j] = (c == 'X');
			if (c == 'O')start = { i,j };
		}
		goban[i] = row;
	}

	step(goban, start, 1);
	if (ans == INF)ans = -1;
	cout << ans << endl;

	debug();
	return 0;
}



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

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

	int A[N];

	for(int i = 0; i < N; i++){
		cin >> A[i];
	}

	int max_num, min_num;
	max_num = A[0];
	min_num = A[0];
	for(int i = 0; i < N; i++){
		if(max_num < A[i]){
			max_num = A[i];
		}
		if(min_num > A[i]){
			min_num = A[i];
		}
	}

	cout << max_num - min_num << endl;
}


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

using namespace std;


#define ff				first
#define ss				second
#define int				long long
#define pb				push_back
#define mp				make_pair
#define pii				pair<int,int>
#define vi				vector<int>
#define mii 			map<int,int>
#define	pqb				priority_queue<int>
#define pqs				priority_queue<int,vi,greater<int> >
#define setbits(x)		__builtin_popcountll(x)
#define zrobits(x)		__builtin_ctzll(x)
#define mod				1000000007
#define inf 			1e18
#define ps(x,y)			fixed<<setprecision(y)<<x
#define mk(arr,n,type)	type *arr = new type[n]
#define w(x)			int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)


void c_p_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

}


bool isPrime(int n)
{
	if (n <= 1)
		return false;
	if (n <= 3)
		return true;
	if (n % 2 == 0 || n % 3 == 0)
		return false;
	for (int i = 5; i * i <= n; i += 6)
	{
		if (n % i == 0 || n % (i + 2) == 0)
			return false;

	}
	return true;
}

vector<int> Sieve(int n)
{
	bool prime[n + 1];
	memset(prime, true, sizeof(prime));
	for (int i = 2; i * i <= n; i++)
	{
		if (prime[i])
		{
			for (int j = i * i; j <= n; j += i)
			{
				prime[j] = false;
			}
		}
	}
	vi primes;
	for (int i = 2; i <= n; i++)
	{
		if (prime[i])
			primes.pb(i);
	}
	return primes;
}


bool cmp(pair<string, int> a, pair<string, int> b)
{
	return a.ss < b.ss;
}
int lengthOfLongestIncreasingSubsequence(int arr[], int n)
{
	int max = 1, len = 1;
	for (int i = 1; i < n; i++)
	{
		if (arr[i] > arr[i - 1])
			len++;
		else
		{
			if (max < len)
				max = len;

			len = 1;
		}
	}
	if (max < len)
		max = len;

	return max;
}

set<int> primeFactors(int  n)
{
	set<int> factors;
	while (n % 2 == 0)
	{
		n /= 2;
		factors.insert(2);

	}
	for (int i = 3; i <= sqrt(n); i += 2)
	{
		while (n % i == 0)
		{
			factors.insert(i);
			n /= i;
		}
	}
	if (n > 2)
		factors.insert(n);
	return factors;
}

void print(vi j)
{
	for (int i = 0; i < j.size(); i++)
	{
		cout << j[i] << " ";
	}
	cout << endl;
}

int dp[102][100002];

int32_t main()
{
	 FIO;
//	c_p_c();
//--------------------------------------------------
	int n, W;
	cin >> n >> W;
	mk(wt, n, int);
	mk(val, n, int);
	for (int i = 0; i < n; i++)
	{
		cin >> wt[i] >> val[i];
	}


	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			if (i == 0 || j == 0)
				dp[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= W; j++)
		{
			if (wt[i - 1] <= j)
				dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
			else
				dp[i][j] = dp[i - 1][j];
		}
	}
	cout << dp[n][W] << endl;

}

Measured memory_bytes: 79232
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string d[10];
char n[10000];
int main(){
	string nsd;
	int k;
	int ns;
	cin>>nsd>>k;
	for(int i=0;i<k;i++)cin>>d[i];
	ns=nsd.size();
	for(int i=0;i<nsd.size();i++)n[i]=nsd[ns-1-i];
	while(true){
		bool ok=true;
		for(int i=0;i<k;i++){
			for(int f=0;f+d[i].size()<=ns;f++){
				bool sam=true;
				for(int g=0;g<d[i].size();g++){
					if(n[f+g]!=d[i][d[i].size()-g-1])sam=false;
				}
				if(sam)ok=false;
			}
		}
		if(ok)break;
		n[0]++;
		for(int i=0;i<ns;i++){
			if(n[i]>'9'){
				if(i==ns-1)n[ns]='1',ns++;
				else n[i+1]++;
				n[i]-=10;
			}
		}
	}
	for(int i=0;i<ns;i++)cout<<n[ns-i-1];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

typedef double lf;
const lf pai = 3.141592653589793238462643383279;
class point{
public:
  lf x, y;
  point(){}
  point(lf X, lf Y){x = X; y = Y;}
};

point operator + (point x, point y){return point(x.x + y.x, x.y + y.y);}
point operator - (point x, point y){return point(x.x - y.x, x.y - y.y);}
point operator * (point x, lf y){return point(x.x * y, x.y * y);}
point operator * (lf x, point y){return point(x * y.x, x * y.y);}

lf dot(point a, point b){return a.x * b.x + a.y * b.y;}
lf det(point a, point b){return a.x * b.y - a.y * b.x;}
lf len2(point a){return a.x * a.x + a.y * a.y;}
lf len(point a){return sqrt(a.x * a.x + a.y * a.y);}
lf sqr(lf x){return x * x;}

class circle{
public:
  point a; lf r;
  circle(){}
  circle(point A, lf R){a = A; r = R;}
};

void MOD(lf &x){while (x > pai) x -= (pai + pai); while (x < -pai) x += (pai + pai);}
int cross(circle a, circle b, lf &r1, lf &r2){
  lf D = len2(a.a - b.a);
  if (D > sqr(a.r + b.r)) return 0;
  else if (D < sqr(a.r - b.r)) return 0;
  lf t1 = atan2(b.a.y - a.a.y, b.a.x - a.a.x);
  lf t2 = acos((D + sqr(a.r) - sqr(b.r)) / (2 * sqrt(D) * a.r));
  r1 = t1 - t2; r2 = t1 + t2; MOD(r1); MOD(r2);
  return 1;
}

point P[2333];
int n, M;

pair <lf, int> d[2333];
int l;
void add(lf L, lf R){d[++l] = make_pair(L, 1); d[++l] = make_pair(R, -1);}
bool check(int p, lf r){
  int i, j; lf _l, _r;
  circle cb(P[p], r);
  l = 0;
  for (i = 1; i <= n; i++)
    if (i != p){
      circle cr(P[i], r);
      if (cross(cb, cr, _l, _r)){
	if (_l > _r) add(_l, pai), add(-pai, _r);
	else add(_l, _r);
      }
    }
  sort(d + 1, d + l + 1);
  j = 0;
  for (i = 1; i <= l; i++){
    j += d[i].second; if (j >= M - 1) return 1;
  }
  return 0;
}

#define m (l + r) / 2
int p[2333];
int main(){
  int i, j;
  lf ans = 1e10, l, r;
  scanf("%d", &n);
  M = n;
  for (i = 1; i <= n; i++) scanf("%lf %lf", &P[i].x, &P[i].y), p[i] = i;
  random_shuffle(p + 1, p + n + 1);
  for (i = 1; i <= n; i++)
    if (check(p[i], ans)){
      for (l = 0, r = ans; r - l > 1e-8; )
	if (check(p[i], m)) r = m; else l = m;
      ans = r;
    }
  printf("%.9lf", ans);
  return 0;
}
// soln copied from https://www.codechef.com/viewsolution/12412231

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

#define REP(i,n) for(int (i)=0;(i)<(n);++(i))
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define ALL(obj) (obj).begin(),(obj).end()
#define space <<" "<<
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
#define FIX <<fixed<<setprecision(10)<<
using namespace std;

using ll = long long; using ull = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using pii = pair<int,int>; using pll = pair<ll,ll>;

const ll MOD = 1e9+7;
int sw;

class dice{
private:

public:
    int face[6];
    void operate(char order);
};

void dice::operate(char order){
if(order=='E'){
    sw=face[5];
    face[5]=face[2];
    face[2]=face[0];
    face[0]=face[3];
    face[3]=sw;
}else if(order=='W'){
    sw=face[5];
    face[5]=face[3];
    face[3]=face[0];
    face[0]=face[2];
    face[2]=sw;
}else if(order=='N'){
    sw=face[5];
    face[5]=face[4];
    face[4]=face[0];
    face[0]=face[1];
    face[1]=sw;
}else if(order=='S'){
    sw=face[5];
    face[5]=face[1];
    face[1]=face[0];
    face[0]=face[4];
    face[4]=sw;
}else if(order=='R'){
    sw=face[1];
    face[1]=face[2];
    face[2]=face[4];
    face[4]=face[3];
    face[3]=sw;
}
}

int main(){

dice dice1;
dice dice2;
int times=0;

REP(i,6){
    cin>>dice1.face[i];
}
REP(i,6){
    cin>>dice2.face[i];
}
REP(i,4){
    if(dice1.face[0]==dice2.face[0]&&dice1.face[5]==dice2.face[5])break;
    dice2.operate('N');
}
if(!(dice1.face[0]==dice2.face[0]&&dice1.face[0]==dice2.face[0]))dice2.operate('W');
REP(i,4){
    if(dice1.face[0]==dice2.face[0]&&dice1.face[5]==dice2.face[5])break;
    dice2.operate('N');
}
REP(i,4){
    if(dice1.face[1]==dice2.face[1]&&dice1.face[4]==dice2.face[4])break;
    dice2.operate('R');
}
if(dice1.face[0]==dice2.face[0]&&dice1.face[1]==dice2.face[1]&&dice1.face[2]==dice2.face[2]
&&dice1.face[3]==dice2.face[3]&&dice1.face[4]==dice2.face[4]&&dice1.face[5]==dice2.face[5])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}


Measured memory_bytes: 3104
my $n=<STDIN>-0;
my $k=0;
my $t=$n;
for(my $i=1;$i<=$n;$i++){
    my $p=$i;
    my $c=0;
    while($p%2==0){
        $p=$p/2;
        $c++;
    }
    if($c>$k){
        $k=$c;
        $t=$i;
    }
}
print $t;

Measured memory_bytes: 384
# coding: utf-8
# Your code here!
n=int(input())
tmp=0
count=0
ans=0
wer=0
if n==1:
    print(1)
else:
    for i in range(1,n+1):
    #print(count,ans,wer)
        tmp=i
        for j in range(n):
            if tmp%2==0:
                count+=1
                tmp=tmp//2
            else:
                if count>ans:
                    ans=count
                    wer=i
                count=0
                break
    print(wer)

Measured memory_bytes: 3064
n = int(input())
m = 0
a = 0
r = 0
c = 0
h = 0
for _ in range(n):
    s = str(input())
    if s[0] == "M":
        m += 1
    elif s[0] == "A":
        a += 1
    elif s[0] == "R":
        r += 1
    elif s[0] == "C":
        c += 1
    elif s[0] == "H":
        h += 1

#print(m,a,r,c,h)
ans = m*(a*r+a*c+a*h+r*c+r*h+c*h)+a*(r*c+r*h+c*h)+r*c*h
print(ans)


Measured memory_bytes: 9080
from collections import deque


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
tree = [[] for i in range(n)]

for i in range(n-1):
    tree[info[i][0] - 1].append([info[i][1] - 1, info[i][2]])
    tree[info[i][1] - 1].append([info[i][0] - 1, info[i][2]])
    
q = deque()
q.append(0)
visited = [False]*n
visited[0] = True
color = [0]*n

while q:
    pos = q.pop()
    for i, cost in tree[pos]:
        if not visited[i]:
            visited[i] = True
            if cost % 2 == 0:
                color[i] = color[pos]
            else:
                color[i] = color[pos]^1
            q.append(i)
for i in range(n):
    print(color[i])

Measured memory_bytes: 66776
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int h,w,k;
string s[6];
bool h1[6],h2[6];
int main(){
	ios::sync_with_stdio(0);
	cin>>h>>w>>k;
	rep(i,h)
	cin>>s[i];
	int ans=0;
	rep(i,1<<h){
		rep(j,1<<w){
			rep(k1,h){
				h1[k1]=false;
				if((i&1<<k1))
				h1[k1]=true;
			}
			rep(k1,w){
				h2[k1]=false;
				if((j&1<<k1))
				h2[k1]=true;
			}
			int ans1=0;
			rep(k1,h)
			rep(i1,w){
				if(!h1[k1]&&!h2[i1]&&s[k1][i1]=='#')
				ans1++;
			}
			if(ans1==k)
			ans++;
		}
	}
	cout<<ans;
	re 0;
}

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

int main(){
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> w(n);
    for(int i=0; i < n; i ++){
        w[i] = 0;
    }
    for(int i=0; i < q; i ++){
        int winner;
        cin >> winner;
        w[winner-1] +=1;
    }
    for(int i=0; i < n; i ++){
        if(q-w[i] >= k){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

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

vi lis,a,ans;
stack<int> st;
vector<vi> g;
void dfs(int now, int par){
    int ind = lower_bound(all(lis),a[now]) - lis.begin();
    st.push(lis[ind]);
    lis[ind] = a[now];
    ans[now] = lower_bound(all(lis),INF) - lis.begin();
    for(auto ne: g[now])if(ne != par){
        dfs(ne,now);
    }
    lis[ind] = st.top();
    st.pop();
}

signed main(void) {
    int n;
    cin >> n;
    a = vi(n);
    rep(i,n)cin >> a[i];
    g = vector<vi> (n);
    rep(i,n-1){
        int u,v;
        cin >> u >> v;
        u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    lis = vi(n+1, LINF);
    ans = vi(n);
    dfs(0,-1);
    rep(i,n)cout << ans[i] << endl;
}


Measured memory_bytes: 28496
#include "bits/stdc++.h"

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>istream &operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
//template <typename T, typename S>ostream &operator<<(ostream &os, pair<T, S> &p) {os << p.first << " " << p.second;return os;}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T, class U>bool chmin(T& a, U b) { if (a > b) { a = b; return true; }return false; }
template <class T, class U>bool chmax(T& a, U b) { if (a < b) { a = b; return true; }return false; }

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int H, W; cin >> H >> W;
	vector<string>s(H); rep(i, 0, H) { cin >> s[i]; }
	int ans = 0;

	auto f = [&](vector<string>v) {
		int a = 0;
		while (count(all(v[a]), 'B') == 0)a++;
		int b = v.size() - 1;
		while (count(all(v[b]), 'B') == 0)b--;
		rep(i, 0, v[0].size()) {
			rep(j, 0, v[0].size()) {
				if (a == b and i == j)continue;
				if (v[a][i] == 'B' and v[b][j] == 'B') {
					int d = abs(a - b) + abs(i - j);
					chmax(ans, d);
				}
			}
		}
	};
	f(s);
	vector<string>t(W, string(H, '.'));
	rep(i, 0, H) {
		rep(j, 0, W) {
			t[j][i] = s[i][j];
		}
	}
	f(t);
	
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 5196
#include <iostream>



int main () {
  int n, i;
  int left, right;
  int sum_a, sum_b;
  while (std::cin >> n) {
    if (n == 0) {
      break;
    }
    sum_a = 0;
    sum_b = 0;
    for (i = 0; i < n; i ++) {
      std::cin >> left >> right;

      if (left > right) sum_a += (left + right); 
      else if (left < right) sum_b += (left + right);
      else {
        sum_a += left;
        sum_b += right;
      }
    }
    std::cout << sum_a << " " << sum_b << std::endl;
  }
  return 0;
}

Measured memory_bytes: 2952
#include <iostream>
#include <cmath>
#include <map>
#include <set>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    map<pair<int, int>, set<int>> pair_index;
    for(int i=0; i<n; i++){
        double x;
        int pow2=0, pow5=0;
        unsigned long long val;
        scanf("%lf", &x);
        val=llround(x*1e9);
        while(val%2==0){
            pow2++;
            val/=2;
        }
        while(val%5==0){
            pow5++;
            val/=5;
        }
        pair_index[*new pair(pow2, pow5)].insert(i);
    }
    unsigned long long counter=0;
    for(auto i=pair_index.begin(); i!=pair_index.end(); i++){
        for(auto j=pair_index.begin(); j!=pair_index.end(); j++){
            if(min(i->first.first+j->first.first, i->first.second+j->first.second)>=18){
                if(i==j){
                    counter+=i->second.size()*(j->second.size()-1)/2;
                }else if(*i<*j){
                    counter+=(i->second.size()*j->second.size());
                }
            }
        }
    }
    printf("%llu\n", counter);
    return 0;
}


Measured memory_bytes: 19224
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;

int main() {
    int L, R, d;
    cin >> L >> R >> d;
    cout << R / d - (L - 1) / d << endl;
}

Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int N=2000005;
const int MOD=200003;
const double Pi=acos(-1);
struct Complex
{
	double x,y;
	Complex(double xx=0,double yy=0)
	{
		x=xx,y=yy;
		return;
	}
	Complex operator+(Complex const &b)const
	{
		return (Complex){x+b.x,y+b.y};
	}
	Complex operator-(Complex const &b)const
	{
		return (Complex){x-b.x,y-b.y};
	}
	Complex operator*(Complex const &b)const
	{
		return (Complex){x*b.x-y*b.y,x*b.y+y*b.x};
	}
};
Complex W[N<<1];
void dft(vector<Complex> &f,int len)
{
	if(len==1) return;
	vector<Complex> fl,fr;
	fl.resize(len/2),fr.resize(len/2);
	for(int k=0;k<len/2;k++)
		fl[k]=f[k*2],fr[k]=f[k*2+1];
	dft(fl,len/2);
	dft(fr,len/2);
	Complex w=W[len],buf=(Complex){1,0};
	for(int k=0;k<len/2;k++)
	{
		f[k]=fl[k]+buf*fr[k];
		f[k+len/2]=fl[k]-buf*fr[k];
		buf=buf*w;
	}
	return;
}
void idft(vector<Complex> &f,int len)
{
	if(len==1) return;
	vector<Complex> fl,fr;
	fl.resize(len/2),fr.resize(len/2);
	for(int k=0;k<len/2;k++)
		fl[k]=f[k*2],fr[k]=f[k*2+1];
	idft(fl,len/2);
	idft(fr,len/2);
	Complex w=(Complex){W[len].x,-W[len].y},buf=(Complex){1,0};
	for(int k=0;k<len/2;k++)
	{
		f[k]=fl[k]+buf*fr[k];
		f[k+len/2]=fl[k]-buf*fr[k];
		buf=buf*w;
	}
	return;
}
typedef vector<int> poly;
poly fft(const poly &F,const poly &G)
{
	vector<Complex> f,g;
	int n=F.size()-1,m=G.size()-1;
	f.resize(n+1),g.resize(m+1);
	for(int i=0;i<=n;i++)
		f[i].x=F[i];
	for(int i=0;i<=m;i++)
		g[i].x=G[i];
	for(m+=n,n=1;n<=m;n<<=1);
	for(int i=1;i<=n;i++)
		W[i]=(Complex){cos(2*Pi/i),sin(2*Pi/i)};
	f.resize(n);
	g.resize(n);
	dft(f,n);
	dft(g,n);
	for(int i=0;i<n;i++)
		f[i]=f[i]*g[i];
	idft(f,n);
	poly res;
	res.resize(m+1);
	for(int i=0;i<=m;i++)
		res[i]=(int)(f[i].x/n+0.5);
	return res;
}
const int G=2;
int n;
int a[N];
long long powG[N],logG[N];
void init()
{
	powG[0]=1;
	logG[1]=0;
	for(int i=1;i<=MOD-2;i++)
	{
		powG[i]=powG[i-1]*G%MOD;
		logG[powG[i]]=i;
	}
	return;
}
int cnt[N];
signed main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]) cnt[logG[a[i]]]++;
	}
	poly f;
	f.resize(MOD-1);
	for(int i=0;i<=MOD-2;i++)
		f[i]=cnt[i];
	f=fft(f,f);
	long long ans=0;
	for(int i=0;i<f.size();i++)
		ans+=f[i]*powG[i%(MOD-1)];
	for(int i=0;i<=MOD-2;i++)
		ans-=cnt[i]*(powG[i]*powG[i]%MOD);
	printf("%lld",ans/2);
	return 0;
}

Measured memory_bytes: 106924
#include<bits/stdc++.h>
using namespace std;
#define PI 3.1415926
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int sum=0;
    for(int i=0;i<k;i++){
        int s;
        scanf("%d",&s);
        sum+=s;
    }

    printf("%d",sum>n?-1:n-sum);
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> mochi(N);
    for(int i = 0; i<N; i++) cin >> mochi.at(i);
    sort(mochi.begin(), mochi.end(), [](int a, int b){return a > b;});
    int cur = mochi.at(0), ans = 1;
    for(int i = 1; i<N; i++){
        if(mochi.at(i) < cur){
            cur = mochi.at(i);
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256