akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(1000000000)

N = int(input())
data = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
seed = ['a'] * N

def rec(S, depth, count):
    if depth == N:
        print(''.join(S))
        return
    for i in range(count+1):
        S.append(data[i])
        if i == count:
            count += 1
        rec(S, depth+1, count)
        S.pop()


rec([], 0, 0)


Measured memory_bytes: 54616
s = input()
q = int(input())
z = ""

for i in range(q):
    m = input().split()
    x = int(m[1])
    y = int(m[2])
    if m[0] == "print":
        print(s[x:y+1])
    elif m[0] == "reverse":
        s = s[0:x] + "".join(list(reversed(s[x:y+1]))) + s[y+1:]
    else:
        s = s[0:x] + m[3] + s[y+1:]



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

int main(void){
    
    int N;
    cin >> N;
    
    int ans = 0;
    for(int i = 1; i <= N; i+=2){

        int divisor_Count = 0;
        for(int j = 1; j <= i; j++){
            if(i % j == 0) divisor_Count++;
        }
        
        if(divisor_Count == 8) {
            ans++;
        }
    }
    
    cout << ans << endl;
    
}


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

string alphabet {"zabcdefghijklmnopqrstuvwxy"};
void toalpha(ll num, string &result){
  if(num<=0) return;
  int odd = num % 26;
  char c = alphabet[odd];
  result = c + result;

  ll next_num = num / 26;
  if(odd == 0) next_num--;
  toalpha(next_num, result);
}
int main(){
  // 標準入力高速化のおまじない
  // scanfとの同期を切る。以降紛らわしいのでscanf使用不可。
  ios::sync_with_stdio(false);
  // // cin前の自動flashをやめる
  cin.tie(nullptr);
  ll N;
  string result="";
  cin >> N;
  toalpha(N,result);

  cout << result << endl;
  return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
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<double,vector<double>,greater<double> >
#define MX              200005
#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 pw(b,p)         pow(b,p) + 0.1
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

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
}

int32_t main()
{
   // c_p_c();
    int n; cin>>n;

    pqs pq;

    for(int i=0;i<n;++i)
    {
        int x; cin>>x;
        pq.push((double)x);
    }

    while(pq.size()>1)
    {
        double tp = pq.top();
        pq.pop();

        tp += pq.top();
        pq.pop();

        pq.push(tp/2.0);
    }

    cout<<pq.top()<<'\n';

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    string s;
    cin >> s;
    ll n = s.size();

    rep(i, n-1) {
        if(s[i] == s[i+1]) {
            cout << i+1 << " " << i+2 << endl;
            re0;
        }
        if(i <= n-3 && s[i] == s[i+2]) {
            cout << i+1 << " " << i+3 << endl;
            re0;
        }
    }

    cout << -1 << " " << -1 << endl;
    re0;
}

Measured memory_bytes: 512
n,m = map(int, input().split())
t = [[n] for i in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  t[a-1].append(b-1)
g = []
for i in t:
  g.append(min(i))
k = 0
ans=0
while k <=n-1:
  e = min(g[k:])
  if e==n:
    break
  ans+=1
  k = e
print(ans)

Measured memory_bytes: 219888
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using pll=pair<ll,ll>;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define MOD 1000000007

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

int main() {
	int N;
	ll H;
	cin >> N >> H;
	vector<pll> A(N);
	rep(i,N) cin >> A[i].se >> A[i].fi;
	ll d = 0;
	ll maxi = -1, idx = -1;
	rep(i,N) {
		if(maxi < A[i].se) {
			maxi = A[i].se;
		}
	}
	sort(A.begin(), A.end(), greater<>());
	rep(i,N) {
		if(A[i].se == maxi) idx = i;
	}
	int cnt=0, cnt1 = 0;
	//cout << maxi << endl;
	ll H2 = H;
	rep(j,N) {
		if(A[j].fi > maxi) {
			H2 -= A[j].fi;
			cnt1++;
			if(H2 <= 0) break;
		}
	}
	if(H2>0) cnt1 = 1e9;
	//cout << cnt1 << endl;
	rep(j,N) {
		//cout << A[j].fi << " " << A[j].se << " " << H << " " << idx << endl;
		
		if(A[j].fi > maxi && j != idx) {
			H -= A[j].fi;
			cnt++;
			if(H <= 0) break;
		}
	}
	if(H > 0) {
		if(A[idx].fi > A[idx].se) {
			H -= A[idx].fi;
			cnt++;
		}
		if(H > 0) {
			if(H % A[idx].se != 0) cnt++;
			cnt += H / A[idx].se;
		}
	}
	cout << cnt << endl;

  return 0;
}


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

int main()
{
    double a,b,f,c,d,e,x1,x2,y1,y2;

    cin>>x1>>y1>>x2>>y2;

    a=(x1-x2);
    b=pow(a,2);
    //cout<<b;
    c=(y1-y2);
    d=pow(c,2);
    //cout<<d;
    e=(b+d);
    f=sqrt(e);
    printf("%.8lf\n",f);

    return 0;
}



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

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();
		String S = scan.next();

		List<String> A = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			A.add(String.valueOf(S.charAt(i)));
		}

		int count = 0;
		for(int i = 0; i < N -1; i++) {
			if(!(A.get(i).equals(A.get(i+1)))) {
				//System.out.println(A.get(i)+"と"+A.get(i + 1)+"が違う");
				count++;
			}
		}

		System.out.println(count+1);
	}
}

Measured memory_bytes: 29720
object Main extends App {
  import scala.io.StdIn._

  val usage = Array(2, 5, 5, 4, 5, 6, 3, 7, 6)
  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val a = readLine.trim.split(' ').map(_.toInt)
  println(solve(n, a).mkString)
  def solve(n: Int, canUse: Array[Int]): List[Int] = {
    val minUse = canUse.map(i ⇒ usage(i - 1)).min
    val maxDigit = n / minUse
    val numbers = canUse.sorted(Ordering.Int.reverse)
    val memo = Array.tabulate(n + 1){_ ⇒ State(-1, 0)}
    memo(0).length = 0
    for (i ← 0 to n if memo(i).length != -1){
      for (number ← numbers if i + usage(number - 1) <= n){
        if (memo(i + usage(number - 1)).length < memo(i).length + 1) {
          memo(i + usage(number - 1)).length = memo(i).length + 1
          memo(i + usage(number - 1)).head = number
        }else if (memo(i + usage(number - 1)).length == memo(i).length + 1 && memo(i + usage(number - 1)).head < number){
          memo(i + usage(number - 1)).head = number
        }
      }
    }
    var using = n
    var result = Nil: List[Int]
    while (using != 0){
      result ::= memo(using).head
      using -= usage(memo(using).head - 1)
    }
    result.reverse
  }
  case class State(var length: Int, var head: Int)
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline def also(@inline func: T ⇒ Unit): T = {
      func(value)
      value
    }
    @inline def let[A](@inline func: T ⇒ A): A = func(value)
  }

}

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

// 構造体
struct team{
	int t, c, m;	// チームNo., 正解数, 所要時間合計
	int p[10];		// ペナルティー
};

// オーバーロード
bool operator<(const team team1, const team team2){
	bool rep;
	if(team1.c == team2.c){
		rep = (team1.m == team2.m) ? team1.t > team2.t : team1.m < team2.m;
	}else{
		rep = (team1.c > team2.c);
	}
	return rep;
}

int main(){
	int M, T, P, R;
	while( cin >> M >> T >> P >> R, M || T || P || R ){
		vector<team> teams(T);
		for(int i = 0; i < T; i++){
			teams[i].t = i+1;
//			teams[i].c = 0;
//			teams[i].m = 0;
		}
		for(int i = 0; i < R; i++){
			int m, t, p, j;
			cin >> m >> t >> p >> j;
			if( j == 0 ){
				teams[t-1].c++;
				teams[t-1].m += (m + 20 * teams[t-1].p[p-1]);
			}else{
				teams[t-1].p[p-1]++;
			}
		}
		sort(teams.begin(), teams.end());
		// 出力
		cout << teams[0].t;
		for(int i = 1; i < T; i++){
			if( teams[i].c == teams[i-1].c && teams[i].m == teams[i-1].m ) cout << "=";
			else cout << ",";
			cout << teams[i].t;
		}
		cout << endl;
	}
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
long long int n, i, A, B;
int main()
{
    cin >> A >> B >> n;
    if(n>=B)
        cout << (A*(B-1))/B - A*((B-1)/B) << endl;
    else
        cout << (A*n)/B - A*(n/B) << endl;
    return 0;
}


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

int main() {

	char S[10];
	cin >> S;

	if (S[0] != S[1] && S[1] != S[2] && S[2] != S[0]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    string S;
    cin >> S;
    int n = 0;
    REP(i, S.length())
    {
        if (S[i] == '0')
            n--;
        else
            n++;
    }
    cout << S.length() - abs(n) << endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;



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

    int N,M;
    cin >> N >> M ;
    bool can = false;
    // vector<pair<int,int> >  route;
    vector<vector<int> >  route(N+1,vector<int>());
    vector<int> ok1(N,0);
    vector<int> okn(N,0);

    for (int i=0; i< M; ++i)
    {
        int a,b;
        cin >> a >> b;
        route[a].push_back(b);
        route[b].push_back(a);
        if(a==1) ok1[b] = 1;
        if(a==N) ok1[b] = 1;
        if(b==1) okn[a] = 1;
        if(b==N) okn[a] = 1;
    }

    // for (int i=0; i<route[N].size(); ++i)
    // {   
    //     for ( int j=0; j<route[1].size(); ++j)
    //     {
    //         if ( route[N][i] == route[1][j])
    //         {
    //             can = true;
    //             break;
    //         } 
    //     }
    //    if(can) break;  
    // }

    for (int i=0; i<N; ++i)
    {
        if(ok1[i]==1 && okn[i]==1) can =true;
        // cout << ok1[i] << " " << okn[i] << endl;
    }

    if(can) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 13552
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int INF = 100100100;
using namespace std;

int main()
{
  int K, X;
  cin >> K >> X;

  int left  = (X-K+1 < -100000) ? -1000000 : X-K+1;
  int right = (X+K-1 >  100000) ?  1000000 : X+K-1;

  for(int i=left; i<=right; i++) cout << i << " ";
  cout << endl;
  return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

string append( const string &a, const string &b )
{
	if ( a.find( b ) != string::npos )
	{
		return a;
	}
	if ( b.find( a ) != string::npos )
	{
		return b;
	}

	const int L = min( a.size(), b.size() );

	for ( int l = L; l; l-- )
	{
		if ( a.substr( a.size() - l ) == b.substr( 0, l ) )
		{
			return a + b.substr( l );
		}
	}

	return a + b;
}

struct CompSSS : public binary_function< string, string, bool >
{
	bool operator ()( const string &a, const string &b ) const
	{
		return a.size() == b.size() ? a < b : a.size() < b.size();
	}
};

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

	for ( int n; cin >> n, n; )
	{
		VS words( n );
		FOR( w, words )
		{
			cin >> w;
		}

		vector<VS> dp( 1 << n, VS( n, string( 108, '~' ) ) );
		REP( i, 0, n )
		{
			dp[ 1 << i ][i] = words[i];
		}

		REP( bits, 1, 1 << n )
		{
			REP( i, 0, n )
			{
				REP( j, 0, n )
				{
					if ( !( bits & 1 << i ) || bits & 1 << j )
					{
						continue;
					}

					dp[ bits | 1 << j ][j] = min( dp[ bits | 1 << j ][j], append( dp[ bits ][i], words[j] ), CompSSS() );
				}
			}
		}

		cout << *min_element( ALL( dp.back() ), CompSSS() ) << endl;
	}

	return 0;
}

Measured memory_bytes: 1744
import sys
val = []
result = [] 
count = 0

for line in sys.stdin:
    if line != '\n':
        for word in line.split():
            val.append(int(word))
        result.append(sum(val))
        val = []
        count = count + 1
    else:
        break

for x in result:
    print(x)

Measured memory_bytes: 7420
#include <bits/stdc++.h>
using namespace std ;
int main()
{
    int x , s1 , s2 ,s3 ;
    cin >> x ;
    if(x % 10 == 1)
        s3 = 9 ;
    else if(x % 10 == 9)
        s3 = 1 ;
    x = x / 10 ;
    if(x % 10 == 1)
        s2 = 9 ;
    else if(x % 10 == 9)
        s2 = 1 ;
    x = x / 10 ;
    if(x % 10 == 9)
        s1 = 1 ;
    else if(x % 10 == 1)
        s1 = 9 ;
    cout << s1 << s2 << s3 ;

    return 0 ;
}


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

int main(){
    int a[4],b[4];
    int abc[4][4];
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin >> abc[i][j];
        }
    }
    a[1]=0;
    b[1]=abc[1][1]-a[1];
    b[2]=abc[1][2]-a[1];
    b[3]=abc[1][3]-a[1];
    a[2]=abc[2][1]-b[1];
    a[3]=abc[3][1]-b[1];
    
    string str="Yes";
    
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(abc[i][j]!=a[i]+b[j]) str="No";
        }
    }
    
    cout << str << endl;
    
    return 0;
}










Measured memory_bytes: 256
n, m, q = map(int, input().split())
l = []
for i in range(q):
    l.append(list(map(int,input().split())))

t = [1]*(n+1)
ans = 0
while t[0] == 1:
    s = 0
    for i in range(q):
        if t[l[i][1]]-t[l[i][0]] == l[i][2]:
            s += l[i][3]
    ans = max(ans, s)
    k = n
    while t[k] == m and k >= 1:
        k -= 1
    t[k] += 1
    for i in range(k+1, n+1):
        t[i] = t[i-1]

print(ans)

Measured memory_bytes: 73888
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>

typedef long long ll;

using namespace std;

int main(void)
{
	int a, b;
	string str1, str2;
	cin >> a >> b;

	str1 = to_string(a);
	str2 = to_string(b);

	if (str1 >= str2) {
		for (int i=0; i<a; i++) {
			cout << b;
		} 
	} else {
		for (int i=0; i<b; i++) {
			cout << a;
		}
	}

	cout << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		long mod = (long) (Math.pow(10.0, 9.0) + 7);
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		long k = in.nextInt();
		int a[] = new int[n];

		for ( int i = 0; i < a.length; i++ ) {
			a[i] = in.nextInt();
		}

		long inner = 0; // 内部で成立する転倒数の個数
		long outer = 0; // 他のｎとの関係で成立しうる転倒数の個数
		for ( int i1 = 0; i1 < n; i1++ ) {
			for ( int i2 = 0; i2 < n; i2++ ) {
				if ( a[i1] > a[i2] ) {
					outer++;
					if ( i1 < i2 ) {
						inner++;
					}
				}
			}
		}
		long kk = (k - 1) * k / 2 % mod;
		long ans = (inner * k) % mod + (outer * kk) % mod;
		System.out.println(ans % mod);
		in.close();
	}
}


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

int main() {
  
  string s;
  cin >> s;
  
  if ( s[0] == s[1] && s[1] == s[2] && s[2] == s[3] ){
    cout << "No" << endl;
  }else if ( ( s[0] == s[1] && s[2] == s[3] ) ||
             ( s[0] == s[2] && s[1] == s[3] ) ||
             ( s[0] == s[3] && s[1] == s[2] ) ){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n;ll m;
vector<vector<int>> G;
vector<vector<ll>> C1,C2;
vector<ll> D,ans;

void dfs1(int s,int par){
    //cout << s << endl;
    C1[s].push_back(1);C2[s].push_back(1);
    rep(i,G[s].size()){
        int t=G[s][i];
        if (t==par) {
            C1[s].push_back(C1[s].back());
            continue;
        }
        dfs1(t,s);
        D[s]*=D[t]+1;D[s]%=m;
        C1[s].push_back(C1[s].back()*(D[t]+1)%m);
    }
    per(i,G[s].size()){
        int t=G[s][i];
        if (t==par) {
            C2[s].push_back(C2[s].back());
            continue;
        }
        C2[s].push_back(C2[s].back()*(D[t]+1)%m);
    }
    
    reverse(C2[s].begin(),C2[s].end());
    
      

}

void dfs2(int s,int par,ll D_par){
    //cout << s << endl;
    ans[s]=D[s]*(D_par+1)%m;
    rep(i,G[s].size()){
        int t=G[s][i];
        if (t==par) continue;
        //cout << C1[s][i] << " " << C2[s][i+1] << " " << D_par+1 << endl;
        dfs2(t,s,C1[s][i]*C2[s][i+1]%m*(D_par+1)%m);
    }
}

void solve(){
    cin >> n >> m;
    G.resize(n,{});C1.resize(n,{});C2.resize(n,{});
    D.resize(n,1);ans.resize(n,0);
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    dfs1(0,-1);
    dfs2(0,-1,0);
    rep(i,n){
        cout << ans[i] << endl;
    }
}

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

Measured memory_bytes: 27648
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

const int MAX = 5000;

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

// 二項係数計算
ll 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;
}

int main(){
    int n, k, i;
    COMinit();
    cin >> n >> k;
    for(i=1; i<=k; i++){
        cout << (COM(k-1, i-1)*COM(n-k+1, i))%MOD << "\n";
    }
    return 0;
}

Measured memory_bytes: 384
import java.awt.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i< n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);

        PriorityQueue<Point> queue = new PriorityQueue<>((a1, b1) -> b1.y - a1.y);

        for (int i = 0; i< m; i++) {
            queue.add(new Point(sc.nextInt(), sc.nextInt()));
        }

        int ind = 0;
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            int limit = ind + now.x < a.length ? ind + now.x : a.length;
            for (;ind < limit; ind++) {
                a[ind] = a[ind] < now.y ? now.y : a[ind];
            }
        }

        System.out.println(Arrays.stream(a).sum());
    }
}


Measured memory_bytes: 98476
H, W = map(int, input().split())

ans = float("inf")
for h, w in zip([H, W], [W, H]):
    # ah の全探索
    for ah in range(1, h):
        # 残りを縦割り
        Sa = ah * w
        bw = (w - 1) // 2 + 1
        Sb = (h - ah) * bw
        Sc = (h - ah) * (w - bw)
        ans = min(ans, (max(Sa, Sb, Sc)-min(Sa, Sb, Sc)))

        # 残りを横割り
        if (h - ah) > 1:
            bh = ((h - ah) - 1) // 2 + 1
            Sb = bh * w
            Sc = (h - ah - bh) * w
            ans = min(ans, (max(Sa, Sb, Sc)-min(Sa, Sb, Sc)))
        
print(ans)

Measured memory_bytes: 3064
#include <stdio.h>

int main(void)
{
	int a,b,c,k,d,i;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
	c=a+b;
	d=1;
	while(c/10!=0)
	{
	d++;
    c=c/10;
	}
	printf("%d\n",d);
	}
	return(0);
}

Measured memory_bytes: 600
s = input()

for _ in range(int(input())):
    a, *b = input().split()
    if a == "replace":
        *b, p = b
    i, j = map(int, b)
    
    if a == "print":
        print(s[i:j+1])
    elif a == "reverse":
        s = s[:i] + s[i:j+1][::-1] + s[j+1:]
    else:
        s = s[:i] + p + s[j+1:]



Measured memory_bytes: 5612
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifdef rd
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
	const char *comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
#else
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef float f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b, int mod) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
int a[200005];


void solve()
{
    int n;
    cin>>n;
    fr(i,1,n)
     cin>>a[i];

    multiset<int>lol;
    fr(i,1,n)
    {
         auto it= lol.lower_bound(a[i]);
         if(it!=lol.begin())
         {
             it--;
             lol.erase(it); ///agar bada hai toh erase the shorter element and make it as last el of lis
         }
         /// otherwise it is smaller
         lol.insert(a[i]);
    }
    cout<<lol.size();
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=1;
//	cin>>t;
	fr(i,1,t) {
		solve();
	}
#ifdef rd
	cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}



Measured memory_bytes: 5760
import Foundation
//10^15
//1000000000000001
// Decimal型の有効桁数は38桁
var N = UInt(readLine()!)!
let m = UInt(26)

var a: UInt
var output = ""
var c: String

repeat {
    a = N % m
    N = N / m

    switch (a) {
    case 1:
        c = "a"
    case 2:
        c = "b"
    case 3:
        c = "c"
    case 4:
        c = "d"
    case 5:
        c = "e"
    case 6:
        c = "f"
    case 7:
        c = "g"
    case 8:
        c = "h"
    case 9:
        c = "i"
    case 10:
        c = "j"
    case 11:
        c = "k"
    case 12:
        c = "l"
    case 13:
        c = "m"
    case 14:
        c = "n"
    case 15:
        c = "o"
    case 16:
        c = "p"
    case 17:
        c = "q"
    case 18:
        c = "r"
    case 19:
        c = "s"
    case 20:
        c = "t"
    case 21:
        c = "u"
    case 22:
        c = "v"
    case 23:
        c = "w"
    case 24:
        c = "x"
    case 25:
        c = "y"
    case 0:
        c = "z"
        N = N - 1
    default:
        fatalError()
    }
    output = c + output
} while (N != 0)

print(output)


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

const int N = 3e5+10;
int h,w,m;
int r[N] , c[N] ;

void solve(){
    cin >> h >> w >> m;
    map<pair<int,int>,bool>st;
    for(int i=0;i<m;++i) {
        int x,y;
        cin >> x >> y ;
        x-- , y--;
        r[x]++ , c[y]++;
        st[{x,y}] = 1;
    }
    int mr=0,mc=0 , mri=-1,mci=-1;
    for(int i=0;i<h;++i) 
        if(mr < r[i])
            mr = r[i] , mri = i;
    for(int i=0;i<w;++i)
        if(mc < c[i])
            mc = c[i] , mci = i;
    int ans=0;
    //cout << mr << " " << mc << " " << mri << " " << mci << "\n";
    if(mr >= mc) {
        for(int i=0;i<w;++i) 
            ans = max(ans , mr + c[i] - st[{mri,i}]);
        for(int i=0;i<h;++i)
            ans = max(ans , mc + r[i] - st[{i,mci}]);
    }
    else {
        for(int i=0;i<h;++i) 
            ans = max(ans , mc + r[i] - st[{i,mci}]);
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--)
        solve();
    return  0;
}


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

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

using namespace std;
typedef long long ll;

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

    int amari = n % 10;

    if (amari == 2 || amari==4 || amari==5 || amari==7 || amari==9){
        cout << "hon";
    } else if (amari == 0 || amari==1|| amari==6 || amari == 8){
        cout << "pon";
    } else {
        cout << "bon";
    }

    return 0;
}


Measured memory_bytes: 3104
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;

int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> ab(m);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        ab[i] = make_pair(b, a);
    }
    sort(ab.begin(), ab.end());
    int ans=0, broken=0;
    for(int i = 0; i < m; i++)
    {
        if(ab[i].second<broken) continue;
        ans++;
        broken=ab[i].first;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 1024
let () =
  let n = read_int () in
  Printf.printf "%d:" n;
  let rec doit i x =
    if i*i > n then begin
      if x <> 1 then Printf.printf " %d\n" x
      else print_newline ()
    end else begin
      if x mod i = 0 then begin
        Printf.printf " %d" i;
        doit i (x / i)
      end else
        doit (i + 1) x
    end in
  doit 2 n

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

# print(n)
# print(m)

d = {str(i):0 for i in range(1, m + 1)}
# print(d)

for _ in range(n):
    l = input().split()
    k = l[0]
    a = l[1:]
    
    # print(k)
    # print(a)
    
    for aa in a:
        d[aa] += 1
        
# print(d)

count = 0
for key, value in d.items():
    if value == n:
        count += 1
        
print(count)

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

using namespace std;

typedef long long ll;

const ll mod = 1e9+7;
const int N = 4e5;

ll iv[N+1], f[N+1], f2[N+1];
ll nck(ll n, ll k){
    return f[n]*f2[n-k]%mod*f2[k]%mod;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    iv[1] =1;
    for(ll i=2;i<=N; i++)
        iv[i]=mod-mod/i*iv[mod%i]%mod;
    f[0]=f2[0]=1;
    for(int i=1; i<=N; i++){
        f[i] = i*f[i-1]%mod;
        f2[i] = iv[i]*f2[i-1]%mod;
    }
    int n, k;
    cin >> n >> k;
    ll ans=nck(2*n-1, n-1);
    for(int i=k+1; i<n; i++){
        ans += 2*mod;
        ans -= (nck(n, i)*nck(n-1, n-i-1))%mod;
        ans%=mod;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 9600
#include <iostream>
#include <string>

using namespace std;

int main(void){
    string s;
    int num=0;

    cin >> s;

    for(int i=0;i<=3;i++){
        if(s[i]=='+')num++;
        else if(s[i]=='-')num--;
    }

    cout << num << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
  int main(){
  int n,a,b=0,c;
  cin>>n>>a;
  while(n-c>0){
    b++;
    c=(a*2+1)*b;
    if(n-c==0)
      break;
    } 
  cout<<b<<'\n';
  return(0);
} 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

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

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  string s;
  cin >> s;

  // bitで全探索
  ll ans = 0;
  for (int i = 0; i < (1 << (s.size() - 1)); i++) {
    ll sum = 0;
    string tmp = "";
    for (int j = 0; j < s.size() - 1; j++) {
      tmp += s[j];
      if ((i >> j) & 1) {
        sum += stoll(tmp);
        tmp = "";
      }
    }
    tmp += s[s.size()-1];
    sum += stoll(tmp);
    ans += sum;
  }

  // 解答
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <assert.h>
typedef int64_t ll;
typedef uint64_t ull;
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)

#define MAXN (300)
#define MOD (1000000007)

ll h[MAXN+1];
ll dp[MAXN+1][MAXN+1];
int main(void)
{
    ll n,k;
    scanf("%ld %ld",&n,&k);

    for(int i=0;i<n;i++) scanf("%ld",&h[i+1]);
    ll m = n-k;
    if(m==0)
    {
        printf("0\n");
        return 0;
    }
    for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j] = INT64_MAX/10;
    dp[0][0] = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int l=0;l<i;l++)
            {
                dp[i][j] = min(dp[i][j], dp[l][j-1] + max(0, h[i]-h[l]));
            }
        }
    }

    
    ll ans=INT64_MAX/10;
    for(int i=1;i<=n;i++) ans = min(ans, dp[i][m]);
    printf("%ld\n", ans);
    return 0;
}


Measured memory_bytes: 896
public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		java.util.Scanner sc = new java.util.Scanner(System.in);

		double r = sc.nextDouble();

		double mennseki = r * r * Math.PI;
		double ennshuu = 2 * r * Math.PI;

		System.out.printf("%f %f\n", mennseki, ennshuu);
	}

}

Measured memory_bytes: 28216
#include "bits/stdc++.h"
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;

    int answer;
    if(A >= 13) {
        answer = B;
    } else if(A >= 6) {
        answer = B / 2;
    } else {
        answer = 0;
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def Yes(): print("Yes"); return
def No(): print("No"); return

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()
l = inputSLs(N)

if len(set(l))!=N:
  No()
  exit()
else:
  for i in range(N-1):
    if l[i][-1]!=l[i+1][0]:
      No()
      exit()
Yes()


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

int main()
{
  int h, w, k;
  cin >> h >> w >> k;
  vector<vector<int>> grid(h, vector<int>(w));

  for (int i = 0; i < h; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < w; j++) {
      grid.at(i).at(j) = s.at(j) == '.' ? 0 : 1;
    }
  }

  int ans = 0;

  for (int y = 0; y < (1 << h); y++) {
    for (int x = 0; x < (1 << w); x++) {
      int black = 0;
      for (int i = 0; i < h; i++) {
        if (((y >> i) & 1) == 0) continue;
        for (int j = 0; j < w; j++) {
          if (((x >> j) & 1) == 0) continue;
          black += grid.at(i).at(j);
        }
      }
      if (black == k) ans++;
    }
  }

  cout << ans << endl;
}


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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(ll i = (m); i < (n); ++i)

#define INF 1e9

int main(){
  int N;
  cin >> N;
  vector<int> a(N), b(N);
  ll adiff = 0, bdiff =0;
  REP(i, N){
    cin >> a[i];
  }
  REP(i, N){
    cin >> b[i];
  }
  REP(i, N){
    if(a[i] > b[i]){
      bdiff += a[i] - b[i];
    }
    else{
      adiff += b[i] - a[i] - (b[i]-a[i])%2;
    }
  }
  if(bdiff * 2 <= adiff){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
   

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(4);
  int cnt = 0;
  while(1) {
    cnt++;
    int r, n; cin >> r >> n;
    if(r == 0 && n == 0) break;
    map<P, int> mp;
    for(int i=0;i<n;++i) {
      int x1, x2, h; cin >> x1 >> x2 >> h;
      mp[{x1, 1}] = max(mp[{x1, 1}], h);
      mp[{x2, -1}] = max(mp[{x2, -1}], h);
      for(int j=x1+1;j<=x2-1;++j) {
        mp[{j, 1}] = max(mp[{j, 1}], h);
        mp[{j, -1}] = max(mp[{j, -1}], h);
      }
    }
    double mi = INF;
    for(int i = -r+1;i<r;++i) {
      double tmp1 = mp[{i, -1}], tmp2 = mp[{i, 1}];
      mi = min(mi, tmp1 + r - sqrt(r * r - i * i));
      mi = min(mi, tmp2 + r - sqrt(r * r - i * i));
    }
    cout << mi << endl;
  }
}



Measured memory_bytes: 3248
while 1:
    n=int(input())
    if n==0:
        break
    _dic={}
    dic={}
    s=input().split()
    for p in s:
        if p in _dic:
            _dic[p]+=1
        else:
            _dic[p]=1
            dic[p]=0
    data=sorted(_dic.items(), key=lambda x:-x[1])
    if len(data)==1:
        print(data[0][0],n//2+1)
        continue
    if data[0][1]==data[1][1]:
        print('TIE')
        continue
    i=1
    for p in s:
        dic[p]+=1
        d=sorted(dic.items(), key=lambda x:-x[1])
        if d[0][1]>d[1][1]+(n-i):
            print(d[0][0],i)
            break
        i+=1


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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int a[300000];
vector<int>E[300000];
int sz[300000];

void dfs(int v,int p){
	sz[v]=1;
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v);
		sz[v]+=sz[u];
	}
}
int main(){
	int n;cin>>n;
	rep(i,n-1){
		scanf("%d",&a[i]);a[i]--;
		sz[a[i]]++;
	}
	rep(i,n){
		printf("%d\n",sz[i]);
	}
}

Measured memory_bytes: 12292
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split()))
    kabu = 0
    kane = 1000
    for i in range(n-1):
        if A[i+1] > A[i]:
            kabu += kane // A[i]
            kane %= A[i]
        elif A[i+1] < A[i]:
            kane += kabu * A[i]
            kabu = 0
    kane += kabu * A[n-1]
    print(kane)

if __name__=='__main__':
    main()

Measured memory_bytes: 61888
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int initialize(void);
int isEmpty(void);
int isFull(void);
void push(int);
int pop(void);

int top=0, S[100];

int main()
{
  int x, a, b;
  char s[100];

  while(scanf("%s", s) != EOF){

    if(s[0] == '+'){
      a = pop();
      b = pop();
      push(a + b);   /* top = 0 */
    }

    else if(s[0] == '-'){
      a = pop();
      b = pop();
      push(b - a);
    }

    else if(s[0] == '*'){
      a = pop();
      b = pop();
      push(a * b);
    }

    else{
      x = atoi(s);
      push(x);
    }

  }
  printf("%d\n", S[top]);
  return 0;
}

int isEmpty(void)
{
  if(top == 0) return 0;
  if(top != 0) return 1;
}

int isFull(void)
{
  if(top > 100 - 1) return 0;
  else return 1;
}

void push(int x)
{
  if(isFull() == 1){
    top++;
    S[top] = x;
  }

}

int pop(void)
{
  if(isEmpty() == 1){
  top--;
  return S[top+1];
  }
}

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

#define rep(i, n) for(int i=0; i < n; i++)
#define REP(i, n, m) for(int i=n; i < m; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

using namespace std;
using ll=long long;

ll mod=1000000007;

const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}


int main() {
  string s;cin>>s;
  rep(i,3){
    if(s[i]=='7'){
      cout<<"Yes";return 0;
    }
  }
  cout<<"No";
}

Measured memory_bytes: 3596
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int[] num = new int[3];
		for(int i = 0;i < 3;i++){
			num[i] = saori.saori_hayami();
		}
		Arrays.sort(num);
		int k = saori.saori_hayami();
		for(int i = 1;i <= k;i++){
			num[2] = num[2]*2;
		}
		int ans = 0;
		for(int i = 0;i < 3;i++){
			ans += num[i];
		}
		System.out.println(ans);
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
int main (){
    string s,t;
    int count=0,same=0;
    cin >> s >> t;
    for(int i=0;i<s.size();i++){
        for(int j=0;j<t.size();j++){
            if(s.at(i)>=t.at(j)){
                count++;
            }
            if(s.at(i) == t.at(j)){
                same++;
            }
        }
    }
    
    if(count == s.size()*t.size() && same != s.size()*t.size()){
        cout << "No" << endl;//sの全文字がtの全文字より後ろの時
    }
    else if(same == s.size()*t.size()){ //s,t全文字が同じとき
        if(s.size() < t.size()){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
    else{
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
import bisect

A,B,Q=map(int,input().split())
INF=10**18
s=[-INF]+[int(input()) for _ in range(A)]+[INF]
t=[-INF]+[int(input()) for _ in range(B)]+[INF]
q=[int(input()) for _ in range(Q)]

def solve(start):
    ans=[]
    c,d=bisect.bisect_left(s,start),bisect.bisect_left(t,start)
    for S in [s[c],s[c-1]]:
        for T in [t[d],t[d-1]]:
            ans.append(min(abs(start-S)+abs(S-T),abs(start-T)+abs(S-T)))

    print(min(ans))

for e in q:
    solve(e)

Measured memory_bytes: 16128
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>  // abs() for integer
using namespace std;

int main()
{
  int n,m;
  cin>>n>>m;
  int ax[100],bx[100],ay[100],by[100];
  int tmp;
  int ans[100];
  int ans2[100];

  for(int i=0;i<100;i++){
    ans[i]=1000000001;
  }
  for(int i=0;i<n;i++){
    cin>>ax[i]>>ay[i];
  }
   for(int i=0;i<m;i++){
    cin>>bx[i]>>by[i];
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      tmp=abs(ax[i]-bx[j])+abs(ay[i]-by[j]);
      if(tmp<ans[i]){
        ans[i]=tmp;
        ans2[i]=j;
      }
    }
  }  

  for(int i=0;i<n;i++){
    cout<<ans2[i]+1<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]
use std::collections::HashSet;
use std::collections::HashMap;
use std::cmp::{max, min};

#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($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)*}
    };
}

#[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, usize1) => {
        read_value!($iter, usize) - 1
    };

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

fn main() {
    input! {
        n: usize,
        x: [usize; n],
    }
    let mut v = x.clone();
    v.sort();
    let sin = v[n/2-1];
    for i in 0..n {
        if x[i] > sin {
            println!("{}", sin);
        } else {
            println!("{}", v[n/2]);
        }
    }
}

Measured memory_bytes: 12412