akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
#![allow(clippy::many_single_char_names)]

// language: Rust(1.42.0)
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"
// My Library Repositry is at "https://github.com/Loptall/prcn_lib"

/*
    青perfほしいよ〜！
*/

// from std...
use std::cmp::{
    max, min, Ordering,
    Ordering::{Equal, Greater, Less},
    Reverse,
};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::convert::TryInto;
use std::mem::swap;
use std::num::{NonZeroU32, ParseIntError};
use std::ops::{
    Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
    Index, IndexMut, Mul, MulAssign, Neg, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
    SubAssign,
};
use std::process::exit;
use std::{f32, f64, i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

// Dep' crates are...
use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_complex::Complex;
use num_integer::{binomial, gcd, lcm, multinomial, Integer};
use num_rational::Rational;
use num_traits::{clamp, one, pow, zero, Num, NumAssignOps, NumOps, One, Pow, Zero};
use permutohedron::Heap;
use proconio::{
    fastout, input, is_stdin_empty,
    marker::{Bytes, Chars, Isize1, Usize1},
};
use rand::random;

pub const MOD10E9_7: usize = 1000000007;
pub const MOD99_: usize = 998244353;
pub const MAX: usize = std::usize::MAX;
pub const PI: f64 = f64::consts::PI;
pub const ASCII_A: u8 = 65;

// code...
// #[fastout]
fn main() {
    input! {
        t: usize
    }

    for _testcase in 0..t {
        solve();
    }
}

fn solve() {
    input! {
        n: usize,
        camel: [(usize, usize, usize); n]
    }

    let mut l = Vec::new();
    let mut r = Vec::new();

    let mut ans = 0usize;

    for (i, a, b) in camel {
        ans += min(a, b);
        if a >= b {
            l.push((i, a - min(a, b)));
        } else {
            r.push((n - i, b - min(a, b)));
        }
    }

    ans += f(l);
    ans += f(r);

    println!("{}", ans);
}

fn f(mut cs: Vec<(usize, usize)>) -> usize {
    let n = cs.len();
    for (m, _) in cs.iter_mut() {
        *m = min(*m, n);
    }

    let mut s = vec![Vec::new(); n + 1];
    for i in 0..n {
        s[cs[i].0].push(cs[i].1);
    }

    let mut res = 0usize;
    let mut q = BinaryHeap::new();

    for i in (1..=n).rev() {
        for x in s[i].iter() {
            q.push(*x);
        }

        if q.len() > 0 {
            res += q.peek().unwrap();
            q.pop();
        }
    }

    res
}


Measured memory_bytes: 13808
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
vector<int>res;
int ma,cnt;

void dfs(int s,const int t,const string n,vector<int>&v){
	if(s>t)return;
	if(n.empty()){
		if(ma<s)ma=s,cnt=0;
		if(ma==s)res=v,cnt++;
	}else{
		int add=0;
		for(int i=0;i<n.size();i++){
			add=add*10+n[i]-'0';
			v.push_back(add);
			dfs(s+add,t,n.substr(i+1),v);
			v.pop_back();
		}
	}
}

int main(){
	int t;
	string n;
	for(;cin>>t>>n,t;){
		vector<int>v;
		ma=0,cnt=0;
		dfs(0,t,n,v);
		if(cnt>1)puts("rejected");
		else if(!ma)puts("error");
		else{
			printf("%d",ma);
			for(int i=0;i<res.size();i++)printf(" %d",res[i]);
			puts("");
		}
	}
}

Measured memory_bytes: 1232
N, M, X = map(int, input().split())
A = list(map(int, input().split()))
to_zero = sum([1 for a in A if a < X])
to_n = sum([1 for a in A if a > X])
if to_zero >= to_n:
    print(to_n)
else:
    print(to_zero)


Measured memory_bytes: 2940
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        String S = scan.next();
        String T = scan.next();
        boolean answer = solve(S, T);
        System.out.println(answer ? "Yes" : "No");
    }
    private static boolean solve(String S, String T) {
        char[] data_S = S.toCharArray();
        char[] data_T = T.toCharArray();
        boolean answer = false;
        int N = data_S.length;
        for (int m = 0; m < N; m++) {
            boolean same = true;
            for (int i = 0; i < N; i++) {
                if (i+m < N) {
                    if (data_S[i + m] != data_T[i]) {
                        same = false;
                        break;
                    }
                    continue;
                }
                if (data_S[i + m - N] != data_T[i]) {
                    same = false;
                    break;
                }
            }
            if (same) {
                return true;
            }
        }
        return false;
    }
}


Measured memory_bytes: 21972
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr int MOD = 1000000000 + 7;
//?¶????????????????????????????????????§??????????????????????¢????????????????
constexpr int INF = 2000000000;
const double PI = acos(-1);

int maze[51][51];
int w, h;

void dfs(int hpos, int wpos) {
	maze[hpos][wpos] = 0;
	for (int x = -1; x <= 1; x++) {
		for (int y = -1; y <= 1; y++) {
			int nx = wpos + x;
			int ny = hpos + y;
			if (0 <= nx&&nx < w && 0 <= ny&&ny < h&&maze[ny][nx] == 1)dfs(ny, nx);
		}
	}
}

int main() {
	while (cin >> w >> h&&w&&h) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> maze[i][j];
			}
		}
		int ans = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (maze[i][j] == 1) {
					ans++;
					dfs(i, j);
				}
			}
		}
		cout << ans << endl;
	}

}

Measured memory_bytes: 3236
/*
	Author: Luis Manuel D�az Bar�n (LUISMO)
	Problem:
	Online Judge:
	Idea:
*/
#include<bits/stdc++.h>
// Types
#define ll long long
#define ull unsigned long long
// IO
#define sf scanf
#define pf printf
#define mkp make_pair
#define fi first
#define se second
#define endl "\n"

using namespace std;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll inf = 1e16 + 3;
const int mod = 1e9 + 7;
const int lim = 2e3 + 2;

int H, W;
string str;
int mt[lim][lim];
ll paths[lim][lim];

void solve()
{
    cin >> H >> W;
    for(int i = 0; i < H; i++)
    {
        cin >> str;
        for(int j = 0; j < W; j++)
        {
            if(str[j] == '#')
                mt[i][j] = 1;
        }
    }

    paths[0][0] = 1;

    for(int i = 0; i < H; i++)
    {
        for(int j = 0; j < W; j++)
        {
            paths[i][j] %= mod;
            if(mt[i][j] == 0)
            {
                paths[i][j+1] += paths[i][j];
                paths[i+1][j] += paths[i][j];
            }
        }
    }

    cout << paths[H-1][W-1] << endl;
}


void fastIO()
{
	cin.sync_with_stdio(false);
	cin.tie(0);
}

void IO()
{
	if(fopen("d:\\lmo.in","r") != NULL)
	{
		freopen("d:\\lmo.in","r",stdin);
	}
	else if(fopen("/media/Beijing/lmo.in","r") != NULL)
	{
		freopen("/media/Beijing/lmo.in", "r", stdin);
	}
}

int main()
{
	IO();

	fastIO();

	solve();
}


Measured memory_bytes: 26368
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	ll ret=1900*m+100*(n-m);
	ret*=(1<<m);
	cout<<ret<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, c) for(long long i=0; i<(long long)c; i++)
const ll INF=1000000000000001;
int main() {
	int n,ans;
	string s,s2;
	ans=0;
	cin >>n>>s;
	s2=s;
	int j=n-1;
	int i=0;
	while(i<j){
		while(s[i]=='R')i++;
		if (i>=n)break;
		while(s[j]=='W')j--;

		if (i<j){
			s[i]='R';
			s[j]='W';
			ans++;
		}
	}
	j=0;
	for(i=0;i<n;i++){
		if (s[i]=='W' && j==0){
			j=i;
		}
		if (j!=0 && s[i]=='R'){
//			cout <<"i2="<<i<<endl;
			ans++;
		}
	}
	cout <<ans<<endl;
	return 0;
}


Measured memory_bytes: 3816
#include <stdio.h>

int n;
int a[110][110][10];
int b[110];
int maxx;
int cc[110];

void tf(int hm, int s)
{
	if(hm == n + 1)
	{
		int ff = 0;
		
		for(int i = 1 ; i <= n ; i++)
		{
			if(ff == 1)
				break;
			
			if(cc[i] == 1)
			{
				for(int j = 0 ; j < b[i] ; j++)
				{
					if(cc[a[i][j][0]] != a[i][j][1])
					{
						ff = 1;
						break;
					}
				}
			}
		}
		
		if(ff == 1)
			return;
		
		else
		{
			if(maxx < s)
				maxx = s;
			return;
		}
	}
	
	cc[hm] = 0;
	tf(hm + 1, s);
	cc[hm] = 1;
	tf(hm + 1, s + 1);
}

int main(void)
{
	scanf("%d", &n);
	
	for(int i = 1 ; i <= n ; i++)
	{
		int all;
		
		scanf("%d", &all);
		
		b[i] = all;
		
		for(int j = 0 ; j < all ; j++)
		{
			scanf("%d %d", &a[i][j][0], &a[i][j][1]);
		}
	}
	
	tf(1, 0);
	
	printf("%d", maxx);
	return 0;
}

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

int main(){
  int N, L, sum, max;
  
  cin >> N;
  max = sum = 0;
  for(int i = 0; i < N; ++i){
    cin >> L;
    if(max < L) max = L;
    sum += L;
  }
  
  if(sum - max > max){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    long t = 0;
    int n, i;

    n = sc.nextInt();
    for(i = 0;i < n;i++)t += sc.nextLong();
    out.println(t / n);

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 41424
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll ans = LLONG_MAX;
  ll s = 0;
  rep(i, n){
    s += a[i];
  }
  ll x = 0;
  for(int i = 0; i < n - 1; i++){
    x += a[i];
    ans = min(abs(s - 2*x), ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
using System;
class Program{
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		int a=0,b=1;
		for(int i=1;a<n;i++,b++){a+=i;}
		a-=n;
		for(int i=1;i<b;i++){
			if(a!=i){Console.WriteLine("{0}",i);}
		}
	}
}

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

int main(int argc, char const *argv[])
{
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }

    int oorCnt = 0;
    vector<int> colors(8, 0);

    for (int i = 0; i < N; i++)
    {
        int rate = a[i];
        if (rate < 400)
        {
            colors[0]++;
        }
        else if (rate < 800)
        {
            colors[1]++;
        }
        else if (rate < 1200)
        {
            colors[2]++;
        }
        else if (rate < 1600)
        {
            colors[3]++;
        }
        else if (rate < 2000)
        {
            colors[4]++;
        }
        else if (rate < 2400)
        {
            colors[5]++;
        }
        else if (rate < 2800)
        {
            colors[6]++;
        }
        else if (rate < 3200)
        {
            colors[7]++;
        }
        else
        {
            oorCnt++;
        }
    }

    int count = 0;
    for (int i = 0; i < 8; i++)
    {
        if (colors[i] > 0)
            count++;
    }

    int result = 0;

    if(count == 0 & oorCnt > 0){
        cout << 1 << ' ' << oorCnt << endl;
    } else {
        cout << count << ' ' << count + oorCnt << endl;
    }

    return 0;
}


Measured memory_bytes: 3600
#include<stdio.h>

int main(void){
  int a,b,i,temp[5],val,ans;
  scanf("%d %d",&a,&b);
  for(i=a;i<=b;i++){
    val = i;
    temp[0] = val % 10;
    val = val / 10;
    temp[1] = val % 10;
    val = val / 10;
    temp[2] = val % 10;
    val = val / 10;
    temp[3] = val % 10;
    temp[4] = val / 10;
    if(temp[0] == temp[4] && temp[1] == temp[3]){
      ans++;
    }
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,char> P;

bool ok(P a,P b,P c){
    return a.second == b.second && b.second == c.second && ((a.first-b.first == 1 && b.first-c.first == 1) || (a.first == b.first && b.first == c.first));
}

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

    int T;

    cin >> T;

    for(int i=0; i<T; i++){
        vector<P> v(9);

        for(auto &t:v) cin>>t.first;

        for(auto &t:v) cin>>t.second;

        bool flag=false;

        do{
            flag = (ok(v[0],v[1],v[2]) && ok(v[3],v[4],v[5]) && ok(v[6],v[7],v[8]));
        }while(!flag && next_permutation(v.begin(),v.end()));

        cout << (flag ? 1 : 0) << endl;
    }
}

Measured memory_bytes: 1196
#include<stdio.h>
#include<string.h>
main(){
  char str[11],stn[11];
  int N,i,j,l,f,ans=0,n1,n2;

  scanf("%s",&str);
  n1=strlen(str);

  scanf("%d",&N);

  for(i=0;i<N;i++){
    scanf("%s",stn);

    for(j=0;j<10;j++){



      for(l=0;l<n1;l++){
	if(stn[(j+l)%10]==str[l]){
	  f=1;
	}
	else{
	  f=0;
	  break;
	}
      }




      if(f==1){
	ans++;
	break;
      }
    }
  }

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

  return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define INF 1000000
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class edge{
public:
	int to,cap,cost,rev;
	edge(){}
	edge(int tt,int cc,int co,int rr){
		to=tt;
		cap=cc;
		cost=co;
		rev=rr;
	}
};

int V;
vector<edge> G[1000];
int dist[1000];
int h[1000];
int prevv[1000],preve[1000];

void add_edge(int from,int to,int cap,int cost){
	G[from].push_back(edge(to,cap,cost,G[to].size()));
	G[to].push_back(edge(from,0,-cost,G[from].size()-1));
}

int min_cost_flow(int s,int t,int f){
	int res=0;
	fill(h,h+V,0);
	while(f>0){
		priority_queue<P,vector<P>,greater<P> > que;
		fill(dist,dist+V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(que.size()){
			P p=que.top();
			que.pop();
			int v=p.second;
			if(dist[v]<p.first)continue;
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					prevv[e.to]=v;
					preve[e.to]=i;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF){
			return -1;
		}
		for(int v=0;v<V;v++){
			h[v]+=dist[v];
		}
		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}

int n,m,k;
int a[101];
int b[101][101];
int T[101];

int main(void){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<m;i++){
		scanf("%d",&T[i]);
	}
	int s=n+m+1,t=s+1;
	V=t+1;
	for(int i=0;i<n;i++){
		add_edge(s,i,1,0);
		add_edge(i,t,1,100-a[i]);
		for(int j=0;j<m;j++){
			add_edge(i,n+j,1,100-b[j][i]);
		}
	}
	for(int i=0;i<m;i++){
		add_edge(n+i,n+m,T[i],0);
	}
	if(m>0)add_edge(n+m,t,n-k,0);
	printf("%d\n",n*100-min_cost_flow(s,t,n));
	return 0;
}

Measured memory_bytes: 3516
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INF = 1e9+1000;

int dp_s[100100], dp_a[100100];
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, M;
  while(cin>>N,N){
	VI HP(N); REP(i,N) cin >> HP[i];
	cin >> M;

	fill(dp_s, dp_s+100100, INF);
	fill(dp_a, dp_a+100100, INF);
	dp_s[0] = dp_a[0] = 0;
	REP(i,M){
	  int mp, dam;
	  string s1, s2;
	  cin >> s1 >> mp >> s2 >> dam;
	  if(s2 == "Single"){
		FOR(hp,1,100001)
		  dp_s[hp] = min(dp_s[hp], dp_s[max(0,hp-dam)]+mp);
	  }
	  else
		FOR(hp,1,100001)
		  dp_a[hp] = min(dp_a[hp], dp_a[max(0,hp-dam)]+mp);
	}

	LL ans = INF;
	REP(a,100001){
	  LL sum = dp_a[a];
	  REP(i,N) sum += dp_s[max(0,HP[i]-a)];
	  ans = min(ans, sum);
	}
	cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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 all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;
int d[210][210];
int V;

void warshall_floyd(){
    for(int k=0;k<V;k++){
        for(int i=0;i<V;i++){
            for(int j=0;j<V;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        }
    }
}

int main() {
    cin >> V;
    rep(i,V){
        rep(j,V){
            char c;
            cin >> c;
            if(i==j)d[i][j]=0;
            else if(c=='0')d[i][j]=mod;
            else d[i][j]=1;
        }
    }
    warshall_floyd();
    int mx=0;
    rep(i,V){
        rep(j,V){
            if(d[0][i]==d[0][j] && d[i][j]==1){
                cout << -1;
                return 0;
            }
            else chmax(mx,d[i][j]);
        }
    }
    cout << mx+1;
    


}

/*

蟻本ありがとうございます

 */



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define PI 3.1415926535897
#define EPS (1e-10)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using namespace std;


signed main(){
	string N;
	cin >> N;

	cout << count(ALL(N), '2') << endl;

	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define faster ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ld long double
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i,a,b) for(ll i = a; i < b; i++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define bins(v, x) binary_search(v.begin(), v.end(), x)
const double pi = 2*acos(0.0);
const int INF = 1e9+1;
const int mod = 1e9+7;
const int mod1 = 998244353;
 
ll modExp(ll base, ll exp, ll mod) {
   ll res = 1;
   while (exp > 0) {
    	if (exp % 2 == 1) {
        	res= (res * base) % mod;
		}
      exp = exp >> 1;
      base = (base * base) % mod;
   }
   return res;
}

ll inverse(ll base, ll exp, ll mod) {
   return modExp(base, exp - 2, mod);
}

bool compare(const pair<int, int>&i, const pair<int, int>&j) {
    return (i.S > j.S || (i.S == j.S && i.F > j.F));
}

void test() {
   ll n;
   cin >> n;

   vector<ll> a(n);
   ll sum = 0;
   vector<int> cnt(100001, 0);
   REP(i,0,n) {
      cin >> a[i];
      cnt[a[i]]++;
      sum += a[i];
   }

   ll q, b, c;
   cin >> q;

   while(q--) {
      cin >> b >> c;
      sum -= (cnt[b]*b + cnt[c]*c);
      cnt[c] += cnt[b];
      cnt[b] = 0;
      sum += cnt[c]*c;
      cout << sum << endl;
   }

}

int main() {
   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);
   faster;
   cout.precision(10);
   cout << fixed;

   int t = 1;
   //cin >> t;
   while(t--)
      test();

   return 0;
}

Measured memory_bytes: 4524
#include<bits/stdc++.h>
using namespace std;
#define ioS            ios::sync_with_stdio(false);cin.tie(0);
#define li             long int
#define ll            long li
#define ull            unsigned ll
#define pi             pair<int,int>
#define vi             vector<int>
#define vli            vector<li>
#define vll           vector<ll>
#define vvi            vector<vector<int>>
#define pb             push_back
#define mp             make_pair
#define forn(i,s,n)    for(auto i=s;i<n;++i)               
#define forr(i,s,n)    for(auto i=s;i>=n;--i) 
const li mx = 1e6;
void solve() 
{
    int n;
    double x,y;
    double d,e;
    cin>>n>>d;
    int count = 0;
    while(n--)
    {
        cin>>x>>y;
        e = sqrt(x*x + y*y);
        if(e <= d)  count++;
    }
    cout<<count<<endl;
}
int main() {
    ioS
    int t;
    // cin>>t;
    // while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 3864
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


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

#　制約を考えないの組み合わせ数は重複組み合わせでわかる
# そこから、移動がk回のことを考え、0人の部屋が何個あるかで場合分け、全事象から引く。
#　全事象考える必要ない?

m, a, b = LI()
n = 2 * 10 ** 5
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


a_ret = 1
for i in range(m, m - a, -1):
    a_ret = a_ret * i % mod

a_ret = a_ret * inv[a] % mod


b_ret = 1
for i in range(m, m - b, -1):
    b_ret = b_ret * i % mod

b_ret = b_ret * inv[b] % mod

print((pow(2, m, mod) - a_ret - b_ret - 1) % mod)

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

const int N = 10;

int n, L, ALL;
int a[N];
int f[32][324];

inline int min(const int x, const int y) {return x < y ? x : y;}
inline int max(const int x, const int y) {return x < y ? y : x;}

long double solve() {
	int i, j, k, c, to, len = n * L + L;
	memset(f, 0, sizeof f), f[0][(n + 1) * a[n]] = 1;
	for (i = 1; i < len; ++i) if (i % (n + 1)) {
		c = i % (n + 1) - 1, to = min(i + (n + 1) * a[c], len);
		for (j = 0; j <= ALL; ++j) if (!(j >> c & 1))
			for (k = i; k <= len; ++k)
				f[j | 1 << c][max(k, to)] += f[j][k];
	}
	return f[ALL][i];
}

int main() {
	int i, cc = 0; long double ans = 0.;
	scanf("%d%d", &n, &L), ALL = ~(-1 << --n);
	for (i = 0; i <= n; ++i) scanf("%d", a + i);
	std::sort(a, a + (n + 1));
	do ans += solve(), ++cc; while (std::next_permutation(a, a + n));
	printf("%.12Lg\n", ans / (cc * powl(L, n)));
	return 0;
}

Measured memory_bytes: 384
import math

n = []
score = []
scores = []

while True:
    input_n = int(input())
    if input_n == 0:
        break
    n.append(input_n)
    input_score = [int(i) for i in input().split()]
    score.append(input_score)


def total(scorelist):
    total = 0
    for i in range(len(scorelist)):
        total = total + scorelist[i]
    return total


def ave(total,n):
    return float(total / n)

def variance(scorelist,ave,n):
    total = 0
    for i in range(len(scorelist)):
        total = total + math.pow(scorelist[i]-ave,2)
    return total / n

for i in range(len(n)):
    total_score = total(score[i])
    average = ave(total_score,n[i])
    var = variance(score[i],average,n[i])
    print(math.sqrt(var))

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

class RollingHash {
    static const ll base1 = 1009;
    static const ll base2 = 2009;
    static const ll mod1 = 1000000007;
    static const ll mod2 = 1000000009;
    vector<ll> hash1, hash2, pow1, pow2;

public:
    RollingHash(const string &S) {
        int n = (int) S.size();
        hash1.assign(n + 1, 0);
        hash2.assign(n + 1, 0);
        pow1.assign(n + 1, 1);
        pow2.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i + 1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i + 1] = (hash2[i] * base2 + S[i]) % mod2;
            pow1[i + 1] = (pow1[i] * base1) % mod1;
            pow2[i + 1] = (pow2[i] * base2) % mod2;
        }
    }

    inline pair<ll, ll> get(int l, int r) const {
        ll res1 = hash1[r] - hash1[l] * pow1[r - l] % mod1;
        if (res1 < 0) res1 += mod1;
        ll res2 = hash2[r] - hash2[l] * pow2[r - l] % mod2;
        if (res2 < 0) res2 += mod2;
        return {res1, res2};
    }

    inline int getLCP(int a, int b) const {
        int len = min((int) hash1.size() - a, (int) hash1.size() - b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a + mid) != get(b, b + mid)) high = mid;
            else low = mid;
        }
        return low;
    }
};

void Main() {
    int N;
    string S;
    cin >> N >> S;
    RollingHash rollingHash(S);
    ll ans = 0;
    rep(i, N) {
        rep2(j, i + 1, N) {
            ll lcp = rollingHash.getLCP(i, j);
            lcp = min(lcp, j - i);
            ans = max(ans, lcp);
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a;
  int nom=0;
  nom+=a/100;
  a%=100;
  nom+=a/10;
  a%=10;
  nom+=a;  
  cout << nom <<endl;
  // ここにプログラムを追記
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}

// index が条件を満たすかどうか
int main() {
	int n;
	cin >> n;
	vector<int> s;
	map<int, int> s1;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		s.push_back(a);
	}
	long long int min = 10000000000;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (min >= s[i]) {
			ans++;
			min = s[i];
		}
	}
	cout << ans;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)

vector<pair<int, string> > edge[40];
string cost[40][500];

int main() {
  while (true) {
    int n, a, s, g;
    cin >> n >> a >> s >> g;
    if (n == 0 && a == 0 && s == 0 && g == 0) break;
    rep (i, 40) edge[i].clear();
    rep (i, a) {
      int x, y;
      string s;
      cin >> x >> y >> s;
      edge[x].push_back(make_pair(y, s));
    }
    string INF;
    rep (i, 10000) INF += 'z';
    rep (i, n) rep (j, 500) cost[i][j] = INF;
    priority_queue<pair<string, int>, vector<pair<string, int> >, greater<pair<string, int> > > que;
    que.push(make_pair("", s));
    while (!que.empty()) {
      pair<string, int> now = que.top();
      que.pop();
      if (now.second == g) {
	if (now.first.size() >= 250u) cout << "NO" << endl;
	else cout << now.first << endl;
	goto next;
      }
      if (now.first.size() >= 490u || cost[now.second][now.first.size()] <= now.first) continue;
      cost[now.second][now.first.size()] = now.first;
      rep (i, edge[now.second].size()) {
	if (now.first.size() + edge[now.second][i].second.size() >= 490u || cost[edge[now.second][i].first][now.first.size() + edge[now.second][i].second.size()] <= now.first + edge[now.second][i].second) continue;
	que.push(make_pair(now.first + edge[now.second][i].second, edge[now.second][i].first));
      }
    }
    cout << "NO" << endl;
  next:;
  }
}

Measured memory_bytes: 33520
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

int main(){
  int n;
  cin >> n;
  vector<string> s(2);
  rep(snip_i, 2) cin >> s.at(snip_i);
  vector<int> tr;
  rep(i, n){
    if(s.at(0).at(i) == s.at(1).at(i)){
      tr.push_back(0);
    }else{
      tr.push_back(1);
      i++;
    }
  }
  mint ans = 0;
  rep(i, tr.size()){
    if(i == 0){
      if(tr.at(i) == 0){
        ans = 3;
      }else{
        ans = 6;
      }
    }else{
      if(tr.at(i) == 0){
        if(tr.at(i-1) == 0){
          ans *= 2;
        }
      }else{
        if(tr.at(i-1) == 0){
          ans *= 2;
        }else{
          ans *= 3;
        }
      }
    }
  }
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    int x;
    cin >> x;
    if(x<1200) cout << "ABC" << endl;
    else cout << "ARC" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAX 100005
using namespace std;
 
int main(){
  long long n, x, ans = 0, a, b;
  scanf("%lld%lld", &n, &x);
  a = max(x, n-x); b = min(x, n-x);
  ans += n;
  while(true){
    if(a%b == 0){
      ans += (a/b*2-1)*b;
      break;
    }else{
      ans += a/b*2*b;
      long long c = a%b;
      a = b; b = c;
    }
  }
  printf("%lld\n", ans);
}

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

using namespace std;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;

Graph G1;
Graph G2;
const long long INF = numeric_limits<long long>::max();
int n, m, s, t;

vector<long long> solve(Graph G, int start) {
	vector<long long> dp(n, INF);
	priority_queue<pair<long long, long long>,
		vector<pair<long long, long long>>,
		greater<pair<long long, long long>>> que;

	dp[start] = 0;
	que.push(make_pair(0, start)); // cost, node

	while (!que.empty()) {
		auto p = que.top();
		que.pop();
		int v = p.second; //node
		long long cost = p.first; //cost
		if (cost > dp[v]) continue;

		for (auto e : G[v]) {
			int nv = e.first; //next node
			long long ncost = e.second; // next cost;
			if (dp[nv] > dp[v] + ncost) {
				dp[nv] = dp[v] + ncost;
				que.push(make_pair(dp[nv], nv));
			}
		}

	}
	return dp;

}

int main(int, char**) {
	cin >> n >> m >> s >> t;
	s--;
	t--;

	G1.assign(n, vector<Edge>());
	G2.assign(n, vector<Edge>());

	for (int i=0; i<m; i++) {
		long long u, v, a, b;
		cin >> u >> v >> a >> b;
		u--;
		v--;
		G1[u].push_back(Edge(v, a));
		G1[v].push_back(Edge(u, a));
		G2[u].push_back(Edge(v, b));
		G2[v].push_back(Edge(u, b));
	}

	stack<long long> stk;
	long long prev = INF;
	vector<long long> dp1 = solve(G1, s);
	vector<long long> dp2 = solve(G2, t);
	for (int i=n-1; i>=0; i--) {
		long long cost = dp1[i] + dp2[i];
		if (prev > cost) {
			stk.push(cost);
			prev = cost;
		} else {
			stk.push(prev);
		}
	}
	for (int i=0; i<n; i++) {
		long long ans = pow(10, 15) - stk.top();
		stk.pop();
		cout << ans << endl;
	}
	return 0;
}





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

 int main()
{ 
    int n,m;
    cin>>n>>m;
    
    vector<string> kaif;
    for(int i=0;i<n;i++)
    {
    	string s;
    	cin>>s;
    	kaif.push_back(s);
	}
    
    long long int dp[n+1][m+1];
    for(int i=1;i<=m;i++)
    {
    	if(kaif[0][i-1]=='#')
    	{
    		for(int k=i;k<=m;k++)
    		 dp[1][k]=0;
    		 break;
		}
    	else
    	dp[1][i]=1;
   	}
   	for(int i=1;i<=n;i++)
    {
    		if(kaif[i-1][0]=='#')
    	{
    		for(int k=i;k<=n;k++)
    		 dp[k][1]=0;
    		 break;
		}
    	else
    	dp[i][1]=1;
   	}
   	
   	for(int i=2;i<=n;i++)
   	{
   		for(int j=2;j<=m;j++)
   		{
   			if(kaif[i-1][j-1]=='#')
   			 dp[i][j]=0;
   			 else
   			 dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
		   }
	   }
    
    cout<<dp[n][m]%1000000007<<endl;
return 0;
}




Measured memory_bytes: 9088
import bisect
def gcd(x , y):
    max_val = max(x , y)
    min_val = min(x , y)
    while min_val != 0:
        max_val , min_val = min_val , max_val % min_val
    return max_val
N , X = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
split_idx = bisect.bisect_left(x , X)
BeforeList = x[:split_idx]
AfterList = x[split_idx:]
now = X
ans = 0
DistanceList = []
for val in AfterList:
    distance = abs(val - now)
    DistanceList.append(distance)
    now = val
for val in BeforeList:
    distance = abs(val - now)
    DistanceList.append(distance)
    now = val

ans = DistanceList[0]
for i in range(1,len(DistanceList)):
    ans = gcd(DistanceList[i] , ans)
print(ans)

Measured memory_bytes: 14252
MOD = 10 ** 9 + 7
fac = [1] * (2 * 10 ** 5 + 10)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


def euler_tour(G, root=0):
    n = len(G)
    euler = []
    dq = [root]
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        dq += [u]
        for v in G[u]:
            if visited[v]:
                continue
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                dq += [v]
        visited[u] = 1
    return euler


n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
e = euler_tour(g)
pr = [-1] * n
d = [0] * n
for i, x in enumerate(e):
    if pr[x] == -1:
        pr[x] = i
    else:
        d[x] = (i - pr[x]) // 2
s = [0]
p = [0] * n
v = [0] * n
for node in e:
    if v[node]:
        for t in g[node]:
            if d[t] <= d[node]:
                p[node] = p[node] * \
                    pow(fac[d[t] + 1], MOD - 2, MOD) * p[t] % MOD
    else:
        v[node] = 1
        p[node] = fac[d[node]]
s = [0]
ans = [0] * n
ans[0] = p[0]
while s:
    p = s.pop()
    for node in g[p]:
        if not ans[node]:
            ans[node] = ans[p] * (d[node] + 1) * \
                pow(n - d[node] - 1, MOD - 2, MOD) % MOD
            s.append(node)
for row in ans:
    print(row)


Measured memory_bytes: 127248
import numpy as np
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
A = [a for a in A if "#" in a]
A = list(np.array(A).transpose())
A = [a for a in A if "#" in a]
A = list(np.array(A).transpose())
for a in A:
    print("".join(a))


Measured memory_bytes: 21304
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List<Integer> l = new ArrayList<>();
        for (int i = 0; i < N; i++){
            l.add(sc.nextInt());
        }
        int max = -1;
        int count = 0;
        for (int i = 0; i < l.size();i++){
            if (l.get(i) >= max){
                count++;
            }
            max = Math.max(max,l.get(i));
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 22740
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define poly vector<ll>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
inline ll read(){
	ll x=0;char ch=getchar();bool d=1;
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') d=0;
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return d?x:-x;
}
inline void write(ll x){
	if(x<0) x=-x,putchar('-');
	if(x>=10) write(x/10);
	putchar('0'+x%10);
}
inline void writeln(ll x){write(x);puts("");}
inline void writep(ll x){write(x);putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=1e5+5;
int fa[N],m,ans;
poly v[N];
int dfs(int u,int dep){
	int mx=dep;
	for(auto k:v[u]){
		mx=max(mx,dfs(k,dep+1));
	}
	if(fa[u]!=1&&mx-dep==m-1) return ans++,0;
	return mx;
}
int main(){
	int n=read();m=read();
	For(i,1,n) fa[i]=read();
	For(i,2,n) v[fa[i]].pb(i);
	if(fa[1]!=1) ans=fa[1]=1;
	dfs(1,0);cout<<ans;
}

Measured memory_bytes: 15620
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()

//#define MOD 1000000007LL
#define MOD 998244353LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;





signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int k = INF;
	int n; cin >> n;
	int ans = 0;
	rep(i, n) {
		int a; cin >> a;
		if (k >= a)ans++;
		k = min(k, a);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
N=int(input())
A=[]
for i in range(N):A.append(int(input()))
A=sorted(A)
B=[0]*N
if N%2==0:
    for i in range(N):
        if i==N//2-1:
            B[0]=A[i]
        elif i<N//2-1:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2-1]=A[i]
else:
    for i in range(N):
        if i==N//2:
            B[0]=A[i]
        elif i<N//2:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2]=A[i]
r=0
for i in range(1,N):
    r += abs(B[i-1]-B[i])
A=A[::-1]
B=[0]*N
if N%2==0:
    for i in range(N):
        if i==N//2-1:
            B[0]=A[i]
        elif i<N//2-1:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2-1]=A[i]
else:
    for i in range(N):
        if i==N//2:
            B[0]=A[i]
        elif i<N//2:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2]=A[i]
s=0
for i in range(1,N):
    s += abs(B[i-1]-B[i])
print(max(r,s))

Measured memory_bytes: 8552
def main():
    S=input()
    a=0 
    b=[0]*2019
    No=[0]*2019
    for i in S:
        l=No.copy()
        k=int(i)
        for j in range(2019):
            l[(j*10+k)%2019]=b[j]
        l[k]+=1
        a+=l[0]
        b=l
    print(a)
main()

Measured memory_bytes: 72140
#include <iostream>
int main() {
	int x, y;
	std::cin >> x >> y;
	if (x > y)
		std::cout << "a > b" << std::endl;
	else if (x == y)
		std::cout << "a == b" << std::endl;
	else
		std::cout << "a < b" << std::endl;
	return 0;
}

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

int main(void){
  int n, k, i, sum = 0;
  cin >> n >> k;
  int l[n] = {};
  for(i = 0; i < n; i++){
    cin >> l[i];
  }
  sort(l, l+n, [](const int a, const int b){ return a > b; });
  for(i = 0; i < k; i++){
    sum += l[i];
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
int main()
{
	LL A,B,C,K;
	scanf("%lld%lld%lld%lld",&A,&B,&C,&K);
	C=A-B;
	if(K&(1ll))
		C=C*(-1ll);
	printf("%lld",C);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
//#include<climits>
#define MAX 10000
#define NEG -10000

using namespace std;
static const long long INFTY = (1LL<<32);

long long path[MAX][MAX];//最小経路
int V;

void Floyd(){
    for(int k=0; k<V; k++){
        for(int i=0; i<V; i++){
            if(path[i][k] == INFTY){
                continue;
            }
            for(int j=0; j<V; j++){
                if(path[k][j] == INFTY){
                    continue;
                }
                
                path[i][j] = min(path[i][j], path[i][k] + path[k][j]);
            }
        }
    }
}

int main(){
    int E;
    int s, t, d;
    long long neg[MAX];
    
    cin >> V;
    for(int i=0; i<V; i++){
        for(int j=0; j<V; j++){
            if(i == j){
                path[i][j] =0;
            }else{
                path[i][j] = INFTY;
                neg[i] = INFTY;
            }
                
        }
    }
    
    
    cin >> E;
    for(int i=0; i<E; i++){
        cin >> s >> t >> d;
        path[s][t] = d;
    }
    
    Floyd();
    
    
    bool Neg = false;
    for(int i=0; i<V; i++){
        if(path[i][i] < 0){
            //neg[i] = NEG;
            Neg = true;
        }
    }
        //for(int i=0; i<V; i++){
            
        //}
    
    if(Neg){
        cout << "NEGATIVE CYCLE" << endl;
    }else{
        for(int j=0; j<V; j++){
            for(int k=0; k<V; k++){
                if(path[j][k] == INFTY){
                    if(k != 0) cout << " ";
                    cout << "INF";
                }else{
                    if(k != 0) cout << " ";
                    cout << path[j][k];
                }
            }
            cout << endl;
        }
                    
    }
    
    return 0;
}




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

int main()
{
  int n,k;
  string s;
  cin>>n>>k>>s;
  int i,j=0,ans=0,a[n];
  for(i=1;i<n;i++){
    if(s[i]!=s[i-1]){
      a[j]=i;
      j++;
    }
  }
  if((j+1)/2<=k){
    ans=n-1;
  }
  else{
    if(s[0]=='L'){
      for(i=0;i<a[2*k-1];i++){
        if(s[i]=='R'){
          s[i]='L';
        }
      }
    }
    else{
      for(i=0;i<a[2*k-1];i++){
        if(s[i]=='L'){
          s[i]='R';
        }
      }
    }
    if(s[0]=='R'&&s[1]=='R')ans++;
    if(s[n-1]=='L'&&s[n-2]=='L')ans++;
    for(i=1;i<=n-2;i++){
      if(s[i]=='L'&&s[i-1]=='L')ans++;
      if(s[i]=='R'&&s[i+1]=='R')ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 896