akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  int N, K;
  cin >> N >> K;
  string S, SS;
  cin >> S;
  if (N == 1) {
    cout << 0 << endl;
    return 0;
  }
  if (N == 2) {
    if (S[0] == S[1] || K >= 1)
      cout << 1 << endl;
    else
      cout << 0 << endl;
    return 0;
  }

  SS += S[0];
  int ans = 0;
  for (int i = 1; i < N; i++) {
    if (S[i] == S[i - 1])
      ans++;
    else
      SS += S[i];
  }
  for (int i = 1; i < SS.size() - 1 && K > 0; i += 2) {
    ans += 2;
    K--;
    SS[i] = SS[i - 1];
  }
  if (K > 0 && (SS[0] != SS[(int)SS.size() - 1])) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<unistd.h>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<set>
#include<unordered_map>
#include<cstdio>
#include<map>
#include<numeric>
using namespace std;
#define F first
#define S second
#define mk(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define gc getchar_unlocked
typedef long long ll;
const int MAXN = 1e5 + 10;
const int MAX = 4*1e6 + 100;
double pi = 3.1415926535897932384626433832795;
const ll inf=1e10 ;
vector<int> adj[MAXN] ;
bool v[MAXN] ;
int main(){
    string s ;
    cin >>s ;
    int o=0,x=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='x')x++;
        else o++ ;
    }
    cout<<700 + o*100<<endl;
    return 0;
}


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

const ll MX = 1e18;

int main(){
    int n;
    cin >> n;
    ll ans = 1;
    bool ng = false;
    rep(i,n){
        ll a;
        cin >> a;
        if(a == 0){
            cout << 0 << endl;
            return 0;
        }
        if(ng || MX/ans < a){
            ng = true;
        }
        ans *= a;
    }
    if(ng) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5, mod = 1e9+7;
ll C[N], ans[N], fac[N];
ll power(ll x, ll y)
{
	if(y == 0) return 1;
	ll temp = power(x, y/2);
	temp *= temp, temp %= mod;
	if(y%2) temp *= x, temp %= mod;
	return temp;
}
void pre()
{
	fac[0] = 1;
	for(int i=1; i<N; i++) fac[i] = fac[i-1]*i, fac[i]%= mod;
}
void operate(int n)
{
	C[0] = 1;
	ll cur = 1;
	for(ll i=1; i<=n; i++)
	{
		cur *= (n-i+1), cur %= mod;
		C[i] = (cur * power(fac[i], mod-2))%mod;
	}
}
int main()
{
	int n;
	cin >> n;
	n++;
	int a[n];
	for(int i=0; i<n; i++) cin >> a[i];
	set<int> s;
	int l = 0, r = 0;
	for(int i=0; i<n; i++)
	{
		s.insert(a[i]);
		if(s.size() != i+1)
		{
			r = i;
			for(int j=0; j<i; j++) if(a[i] == a[j])
			{
				l = j;
				break;
			}
			break;
		}
	}
	pre();
	operate(n);
	for(int i=1; i<=n; i++)
	{
		ans[i] = C[i];
	}
	operate(n - (r-l+1));
	for(int i=1; i<=(n-(r-l)); i++)
	{
		ans[i] = (ans[i] - C[i-1] + mod)%mod;
	}
	for(int i=1; i<=n; i++) cout << ans[i] << endl;
}

Measured memory_bytes: 10368
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

int n , x , ans , fas;
int num[1000];

bool cmp ( int x , int y ) {
	return x < y;
}

int main ( void ) {
	scanf ( "%d%d" , &n , &x );
	for ( int i = 1 ; i <= n ; i++ )
		scanf ( "%d" , &num[i] );
	std :: sort ( num + 1 , num + 1 + n , cmp );
	for ( int i = 1 ; i <= n ; i++ ) {
		if ( x >= num[i] ) {
			x -= num[i];
			ans++;
		}
		else {
			fas = i;
			break;
		} 
	}
	if ( x > 0 && fas == 0 ) 
		ans--; 
	printf ( "%d\n" , ans );
	return 0;
}

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

#define fi              first
#define se              second
#define ll             long long
#define pb              push_back
#define mp              make_pair
#define pll             pair<ll,ll>
#define vll              vector<int>
#define mll             map<ll,ll>
#define pqg             priority_queue<ll>
#define pqs             priority_queue<ll,vll,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define md             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x

void hi()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
}
 
int main()
{
    //hi();
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll a,b,c,k; cin>>a>>b>>c>>k;
    ll ans=0;
    ans+=min(a,k);
    k-=ans;
    if(k>0) k-=b;//cout<<ans<<" ";
    if(k>0) {ans-=k;}
    cout<<ans<<"\n";
    return 0;
}

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

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

  if (N <= A) {
    cout << "Yes" << endl;
  } else if (N % 500 <= A) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

const int MAXN = 105;

int K, T;
int a[MAXN];

int main() {
	scanf("%d%d", &K, &T);
	for (int i = 0; i < T; i++)
		scanf("%d", a + i);
	
	int prev = -1;
	int sol = 0;
	for (int i = 0; i < K; i++) {
		int mx = 0, who = -1;
		for (int j = 0; j < T; j++) {
			if (j == prev) continue;
			if (a[j] > mx) {
				mx = a[j];
				who = j;
			}
		}
		if (who == -1) {
			who = prev;
			sol++;
		}
		a[who]--;
		prev = who;
	}
	
	printf("%d\n", sol);
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main(){
    ll H,W,A,B;cin>>H>>W>>A>>B;
    if(B>H/2||A>W/2){
        cout  << "No" << endl;
        return 0;
    }
    rep(i,H){
        rep(j,W){
            if(i<B){
                if(j<A){
                    cout<<0;
                }
                else{
                    cout<<1;
                }
            }
            else{
                if(j<A){
                    cout<<1;
                }
                else{
                    cout<<0;
                }
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define F first
#define S second
#define pb push_back
mt19937 rnd;

map<ll, ll> mp;

ll solve(ll n) {
    if (mp.count(n)) {
        return mp[n];
    }
    if (n == 1) {
        return mp[1] = 1;
    }
    return 2 * solve(n / 2) + 1;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    ll n;
    cin >> n;
    cout << solve(n) << "\n";

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using ll = long long int;

int main(){
    ll N;  cin >> N;
    vll a(N);
    for(int i=0; i<N; i++){
        cin >> a[i];
    }
    ll c = 0, s = N-1, t = 0;
    if(N%2 == 1){t++;}
    while(c < N){
        if(s >= 0){
            cout << a[s] << " ";
            s -= 2;
        }else{
            cout << a[t] << " ";
            t += 2;
        }
        c++;
    }
}

Measured memory_bytes: 3712
n = int(input())
f = [list(input().split()) for i in range(n)]
p = [list(map(int, input().split())) for i in range(n)]


l = []

for i in range(1, 1024):
    a = format(i, '010b')
    b = list(a)
    l.append(b)

ans = 0

for i in range(n):
    y = 0

    for j in range(10):
        if l[0][j] == f[i][j] == '1':
            y += 1
    ans += p[i][y]

for x in l:
    z = 0

    for i in range(n):
        y = 0

        for j in range(10):
            if x[j] == f[i][j] == '1':
                y += 1
        z += p[i][y]
    ans = max(ans, z)

print(ans)

Measured memory_bytes: 3316
#include <iostream>

int main()
{
  unsigned long long A, B, N;
  std::cin >> A >> B >> N;
  
  const double dB = (double)B;
  const double dAB = A / dB;
  
  unsigned long long x = 0;
  unsigned long long max = 0;
  for(int i = 0; x < N ; ++i)
  {
    x = B * (i + 1) - 1;
    x = x > N? N : x;
   
    const unsigned long long result = (unsigned long long)(x * dAB) - 
      		A * (unsigned long long)(x / dB);
    
    if(result > max)
	    max = result;
    else
      break;
  }
  
  std::cout << max << std::endl;
  
  return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define M 2000000000

int cnt = 0;
vector<int> L(250005);
vector<int> R(250005);

void merge(vector<int> &vec,int n,int left,int mid,int right){
  int n1 = mid - left;
  int n2 = right - mid;

  for(int i=0;i<n1;i++) L.at(i) = vec.at(left+i);
  for(int i=0;i<n2;i++) R.at(i) = vec.at(mid+i);
  L.at(n1) = M;
  R.at(n2) = M;
  int i = 0, j = 0;
  for(int k = left;k<right;k++){
    cnt++;
    if(L.at(i) <= R.at(j)){
      vec.at(k) = L.at(i++);
    }else{
      vec.at(k) = R.at(j++);
    }
  }
}

void mergeSort(vector<int> &vec,int n,int left,int right){
  if(left+1<right){
    int mid = (left + right) / 2;
    mergeSort(vec,n,left,mid);
    mergeSort(vec,n,mid,right);
    merge(vec,n,left,mid,right);
  }
}

int main(){
  int n,i;

  cin >> n;
  vector<int> vec(n);
  for(i=0;i<n;++i){
    cin >> vec.at(i);
  }

  mergeSort(vec,n,0,n);
  for(i=0;i<n-1;i++){
    cout << vec.at(i);
    cout << " ";
  }
  cout << vec.at(n-1) << endl;
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 6720
#include<bits/stdc++.h>
using namespace std;
#define sight(c) ('0'<=c&&c<='9')
int n,a[1000007],k;
long long maxx,minn;
inline void read(int &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar())x=x*10+c-48;
}
int main () {
	read(k);
	for (int i=1;i<=k;i++) read(a[i]);
	maxx=minn=2;
	for (int i=k;i&&maxx>=minn;i--) {
		if(minn%a[i])  minn=minn/a[i]*a[i]+a[i];  
        maxx=(maxx/a[i]+1)*a[i]-1;  
	}
	if(maxx>=minn) printf("%lld %lld",minn,maxx);
	else puts("-1");
	
}

Measured memory_bytes: 640
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10],k;
int main()
{
    cin>>a[1]>>a[2]>>a[3]>>a[3]>>a[4]>>k;
    sort(a+1,a+4+1);
    if(a[4]-a[1]>k){
        cout<<":("<<endl;
    }
    else cout<<"Yay!"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define endl        "\n"
#define si(a)       scanf("%d",&a)
#define si2(a,b)    scanf("%d%d",&a,&b)
#define si3(a,b,c)  scanf("%d%d%d",&a,&b,&c)
#define sl(a)       scanf("%lld",&a)
#define sl2(a,b)    scanf("%lld%lld",&a,&b)
#define sl3(a,b,c)  scanf("%lld%lld%lld",&a,&b,&c)
#define pb          push_back
#define mk          make_pair
#define loop(n)     for(int i=0; i<n; i++)
#define FOR(a,b)    for(int i=a; i<=b; i++)
#define sz          size()
#define pY          printf("YES")
#define pN          printf("NO")
#define py          printf("Yes")
#define pn          printf("No")
#define mem(a,val)  memset(a, val, sizeof(a))



vector<ll>g[200005];
bool vis[200005];
ll cnt=0;
void dfs(ll rt)
{
    vis[rt]=1;
    cnt++;
    //mx=max(mx, cnt);
    //cout<<rt<<" "<<mx<<" "<<cnt<<endl;
    for(auto x: g[rt])
    {
        if(vis[x]==0)
        {
            dfs(x);
        }
    }
}
int main()
{
   ll n,m,a,b;
   sl2(n,m);

   for(int i=0; i<m; i++)
   {
       sl2(a,b);
       g[a].pb(b);
       g[b].pb(a);
   }

   ll mx=0;
   for(int i=1; i<=n; i++)
   {
       if(vis[i]==0)
       {
           cnt=0;
           dfs(i);
           mx=max(mx, cnt);
       }
   }

   cout<<mx<<endl;
}







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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    ll N, K; cin >> N >> K;
    ll ans = 0;
    for (ll i = K; i <= N + 1; i++) {
        ans += i * N - i * (i - 1) + 1;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

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

const int INF = 2e9;

int main(){
    int x;
    cin >> x;
    if(x < 30) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a[n];
  int b[n];
  int i;
  for(i=0;i<n;i++)cin>>a[i]>>b[i];
  vector<pair<int,int> >p(n);
  for(i=0;i<n;i++)p[i] = make_pair(a[i]+b[i],i);
  sort(p.begin(),p.end(),greater<pair<int,int> >());
  long ans = 0;
  for(i=0;i<n;i++){
    if(i%2==0){
      ans += a[p[i].second];
    }else{
      ans -= b[p[i].second];
    }
  }
  cout<<ans<<endl;
}


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

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int main(){
	int n; cin >> n;
	while(n--){
		int h, w; cin >> h >> w;
		int g = __gcd(h, w);
		h /= g; w /= g;
		
		if(h > w) swap(h, w);
		/*
		int A = 0, B = 0, cnt = 0;
		rep(i, w){
			if(cnt + h >= w) A += w - cnt, B += cnt + h - w, cnt += h - w;
			else A += h, cnt += h, swap(A, B);
		}
		*/
		ll x = ((ll)w * h + 1) / 2, y = (ll)w * h / 2, gg = __gcd(x, y);
		cout << x / gg << " " << y / gg << endl;
	}
	return 0;
}

Measured memory_bytes: 3100
s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i,d in enumerate(s):
	if d=="?":
		for x in range(10):
			for y in range(13):
				dp[i+1][(y*10+x)%13] += dp[i][y]
	else:
		d = int(d)
		for y in range(13):
			dp[i+1][(y*10+d)%13] += dp[i][y]
	for j in range(13):
		dp[i+1][j] %= mod
print(dp[n][5])

Measured memory_bytes: 61916
#include <bits/stdc++.h>
using namespace std;
int read();

int n, root;
int a[200005], l[200005], r[200005];
vector<int> e[200005];
void add(int f, int t) { e[f].push_back(t), e[t].push_back(f); }
void dfs(int u, int fa) {
    if (e[u].size() == 1) return l[u] = r[u] = a[u], void();
    int mxl = 0, suml = 0, sumr = 0;
    for (int i = 0, v; i < e[u].size(); ++i)
        if ((v = e[u][i]) != fa)
            dfs(v, u), suml += l[v], sumr += r[v], mxl = max(mxl, l[v]);
    l[u] = max(0, 2 * a[u] - sumr), r[u] = min(2 * a[u] - suml, a[u]);
    if (l[u] > r[u] || a[u] < mxl) puts("NO"), exit(0);
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    if (n == 2) return puts(a[1] == a[2] ? "YES" : "NO"), 0;
    for (int i = 1, u, v; i < n; ++i) u = read(), v = read(), add(u, v);
    for (int i = 1; i <= n; ++i)
        if (e[i].size() > 1) root = i;
    dfs(root, 0), puts(l[root] ? "NO" : "YES");
    return 0;
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

#include <bits/stdc++.h>
using namespace std;

const ll INF = 1e15;

template<typename T>
void cmpmax(T& reference, T value) {
	reference = max(reference, value);
}

template<typename T>
void cmpmin(T& reference, T value) {
	reference = min(reference, value);
}

int main() {
	ll n, w;
	cin >> n >> w;
	vector<P> as(n);
	rep(i, n) {
		cin >> as[i].second >> as[i].first;
	}
	unordered_map<ll, ll> mW[2];
	mW[0][0] = 0;
	rep(i, n) {
		for (auto p : mW[0]) {
			if (mW[1].count(p.first)) {
				mW[1][p.first] = min(mW[1][p.first], p.second);
			}
			else {
				mW[1][p.first] = p.second;
			}
			auto cw = p.second + as[i].second;
			if (cw > w) continue;
			auto cv = p.first + as[i].first;
			if (mW[1].count(cv)) {
				mW[1][cv] = min(mW[1][cv], cw);
			}
			else {
				mW[1][cv] = cw;
			}
		}
		swap(mW[0], mW[1]);
		mW[1].clear();
	}
	ll u = 0;
	for (auto p : mW[0]) {
		u = max(u, p.first);
	}
	cout << u << endl;
	return 0;
}


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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

ll a, b, c, d, e, n, m, k;
string s, t, r;
char c1, c2, c3;

int A[200005];
int B[200005];
int C[200005];

int main() {
	cin >>a>>b;
  	a%=b;
  	cout <<min(a, b-a)<<endl;
	return 0;
}

Measured memory_bytes: 256
// !Start && !End 
//  0 se divide
//https: //www.youtube.com/watch?v=6Nb-prB-4P0&list=RD6Nb-prB-4P0&start_radio=1

// https: //www.youtube.com/watch?v=eYDI8b5Nn5s
// Electrify my OOOoooooOOOoooOOOOOoooooOOOooo!
#pragma optimise GCC(-O2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define ve(x) vector<x>
#define f(a,b,c) for(int a=b;a<c;a++)
#define foto(x,v) for(auto x:v)
#define read(t) ll t; cin>>t;
#define reads(t) string t; cin>>t;
#define readarr(arr,n) ll arr[n]; f(i,0,n) cin>>arr[i];
#define forstl(i,v) for(auto &i: v)
#define ln endl
#define Endl endl
#define dbg(x) cout<<#x<<" = "<<x<<ln;
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<ln;
#define dbgstl(v) cout<<#v<<" = \n"; { int c=0; forstl(it,v) \
cout<<"    Term "<< ++c <<" = "<<it<<ln;} cout<<ln;
#define dbgstlp(v) cout<<#v<<" = \n"; { int c=0; forstl(it,v) \
cout<<"    Term "<< ++c <<" = "<<it.fi<<" , "<<it.se<<ln;} cout<<ln;
#define dbgarr(v,s,e) cout<<#v<<" = "; f(i,s,e) cout<<v[i]<<", "; cout<<ln;
#define addEdge(tr,k) f(i,0,k) { ll x,y; cin>>x>>y, tr[x].push_back(y), tr[y].push_back(x);}
#define all(v) v.begin(),v.end()

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

//														GLOBAL VARS
ll INF =LLONG_MAX;
const ll M= 1000000007;

//														USEFUL FUNCTIONS
ll powm(ll ,ll);

// 														MAIN
int main()
{ 
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    //It gets easier day by day, but the hard part is to........
    reads(s) if(s== "ABC")cout<<"ARC"; else cout<<"ABC";
}










//													FUNCTIONS DECLARATIONS
ll powm(ll a, ll b) {
	ll res=1;
	while(b) {
		if(b&1)
			res=(res*a)%M;
		a=(a*a)%M;
		b>>=1;
	}
	return res;
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    sort(all(h));
    if (k >= n){
        cout << 0 << endl;
    } else{
        ll sum = 0;
        for (int i = 0; i < n-k; ++i) {
            sum += h[i];
        }
        cout << sum << endl;
    }
}

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

d = [0]
o = c = 0
for i in range(N):
    if S[i] == '(':
        o += 1
    else:
        c += 1
    d.append(o - c)
x = min(d)
print('(' * -x + S + ')' * (d[-1] - x))


Measured memory_bytes: 3060
n,l = map(int,input().split())
s = sum([i for i in range(l,l+n)])
x = [i for i in range(l,l+n) ]

find = 10**9
data = 0
for i in x:
    if abs(i)<find:
        find = abs(i)
        data = i

print(s-data)

Measured memory_bytes: 38384
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
struct edge
{
    int to, cost;
    edge(int to, int cost) { this->to = to, this->cost = cost; }
};
int n, m;
int MST(vector<edge> G[])
{
    priority_queue<P, vector<P>, greater<P>> que;
    vector<int> used(n, 0);
    que.push(make_pair(0, 0));
    int res = 0;
    while(que.size())
    {
        P p = que.top(); que.pop();
        int v = p.second;
        if(used[v]) continue;
        used[v] = 1;
        res += p.first;
        for(int u = 0; u < G[v].size(); u++)
        {
            edge e = G[v][u];
            que.push(make_pair(e.cost, e.to));
        }
    }
    return res;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n >> m, n | m)
    {
        vector<edge> G[n];
        for(int i = 0; i < m; i++)
        {
            int a, b, c; cin >> a >> b >> c;
            G[a].push_back(edge(b, c));
            G[b].push_back(edge(a, c));
        }
        cout << MST(G) << endl;
    }
    return 0;
}




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


ll dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
ll counterb=0,counterw=0;
void dfs(ll x,ll y,ll H, ll W,vector<vector<bool>> &field,vector<vector<bool>> &check){
    check[x][y]=1;
    if(field[x][y]==1){counterb++;}
    if(field[x][y]==0){counterw++;}
    bool meter=(x+y+field[x][y])%2;
    for(int i=0;i<4;i++){if(x+dx[i]>=0&&x+dx[i]<H&&y+dy[i]>=0&&y+dy[i]<W){
        if(check[x+dx[i]][y+dy[i]]==0&&(x+y+dx[i]+dy[i]+field[x+dx[i]][y+dy[i]])%2==meter){
            dfs(x+dx[i],y+dy[i],H,W,field,check);
        };}
    ;}
    

}




int main(){
ll H;
cin >> H;
ll W;
cin >> W;
vector<vector<bool>> field(H, vector<bool>(W, 0));
vector<vector<bool>> check(H, vector<bool>(W, 0));
for(int i=0;i<H;i++){
 for(int j=0;j<W;j++){
     char k;
     cin>>k;
     if(k=='#'){field[i][j]=1;}
 ;}
;}
    ll ans=0;
for(ll i=0;i<H;i++){
 for(ll j=0;j<W;j++){
     
     if(check[i][j]==0){
         dfs(i,j,H,W,field,check);ans+=counterb*counterw;
         counterb=0;counterw=0;
     }
     
 ;}
;}
cout<<ans<<endl;
return 0;


}  



Measured memory_bytes: 15360
# tolist つけ忘れ
# https://atcoder.jp/contests/abc163/submissions/16270790

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def dfs1(v, G, Siz):
    siz = 1
    for u in G[v]:
        G[u].remove(v)
        siz += dfs1(u, G, Siz)
    Siz[v] = siz
    return siz

def dfs(v, N, C, G, Cnt, Siz, Ans):
    color = C[v]
    cnt_old = Cnt[color]
    siz = 1
    siz_up = N
    for u in G[v]:
        Cnt[color] = N - Siz[u]  # 上を塞ぐ
        s = dfs(u, N, C, G, Cnt, Siz, Ans)
        siz += s
        siz_up -= s
        Ans[color] += s * (siz_up - cnt_old)
    Ans[color] += siz_up - cnt_old
    Cnt[color] = cnt_old + siz
    return siz

def solve(N, C, AB):
    G = [[0]*0 for _ in range(N)]
    for i in range(N-1):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    Cnt = np.zeros(N, dtype=np.int64)
    Ans = np.zeros(N, dtype=np.int64)
    Siz = np.zeros(N, dtype=np.int64)
    dfs1(0, G, Siz)
    dfs(0, N, C, G, Cnt, Siz, Ans)
    return Ans

numba_compile([
    [dfs1, "i8(i8,List(List(i8)),i8[:])"],
    [dfs, "i8(i8,i8,i8[:],List(List(i8)),i8[:],i8[:],i8[:])"],
    [solve, "i8[:](i8,i8[:],i8[:,:])"],
])

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(505050)
N = int(input())
C = np.array(input().split(), dtype=np.int64) - 1
AB = np.array([list(map(int, input().split())) for _ in range(N-1)], dtype=np.int64) - 1
Ans = solve(N, C, AB)
print("\n".join(map(str, Ans.tolist())))


Measured memory_bytes: 159616
#include<iostream>
#include<algorithm>
#include<numeric>

using namespace std;

const int MAX_N = 20;
const int MAX_q = 200;

bool dp[MAX_N][40001];
int A[MAX_N];
int m[MAX_q];

int main()
{
	int n,q;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> A[i];
	}
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> m[i];
	}
	int sum = accumulate(A,A+n,0);
	for(int i=0;i<n;i++){
		for(int j=0;j<=sum;j++){
			dp[i][j] = false;
		}
	}
	dp[0][0] = true;
	dp[0][A[0]] = true;
	for(int i=1;i<n;i++){
		for(int j=0;j<=sum;j++){
			if(dp[i-1][j] == true){
				dp[i][j] = true;
				dp[i][j+A[i]] = true;
			}
		}
	}
	for(int i=0;i<q;i++){
		if(dp[n-1][m[i]] == true){
			cout << "yes\n";
		}else{
			cout << "no\n";
		}
	}
}

Measured memory_bytes: 3168
#include<stdio.h>
#include<stdlib.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
const int sz=1e5;
int qLen,qHead,Q[sz],*cave[sz];
void PUSH(int n){Q[(qHead+qLen)%sz]=n;qLen++;}
int POP(void){int q=Q[qHead];qLen--;qHead=(qHead+1)%sz;return q;}
int main(void)
{
  int A,B,N,M,x,y;
  x=scanf("%d %d",&N,&M);
  int room[N],path[N]={0};
  rep(i,N)room[i]=-1;
  rep(i,M)
  {
    x=scanf("%d %d",&A,&B);A--,B--;
    cave[A]=(int*)realloc(cave[A],sizeof(int)*(path[A]+2));
    cave[A][path[A]]=B;path[A]++;
    cave[B]=(int*)realloc(cave[B],sizeof(int)*(path[B]+2));
    cave[B][path[B]]=A;path[B]++;
  }
  room[0]=0;PUSH(0);
  while(qLen)
  {
    x=POP();
    rep(i,path[x]){y=cave[x][i];if(!(room[y]<0))continue;room[y]=x,PUSH(y);}
  }
  puts("Yes");rep(i,N-1)printf("%d\n",room[i+1]+1);
}

Measured memory_bytes: 8348
#include<bits/stdc++.h>
using namespace std;
priority_queue<int>pq;
int n,m;
long long ans=0;
int main()
{
	int i,j,tmp;
	cin>>n>>m;
	for(i=1;i<=n;i++){scanf("%d",&tmp);pq.push(tmp);}
	for(i=1;i<=m;i++){
		tmp=pq.top();pq.pop();
		tmp>>=1;pq.push(tmp);
	}
	for(i=1;i<=n;i++){ans+=pq.top();pq.pop();}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 892
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))

    queue = deque([0])
    color = [0] * (N - 1)
    color_from_parent = [0] * N
    color_from_parent[0] = -1

    while queue:
        v = queue.popleft()
        c = 1
        for i, nv in G[v]:
            if color_from_parent[nv] != 0:
                continue
            if c == color_from_parent[v]:
                c += 1
            color_from_parent[nv] = c
            color[i] = c
            c += 1
            queue.append(nv)

    print(max(color))
    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 53320
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;vvi E2;
  const ll Inf = llINF;const int MAX_V=2555;vector<ll>d;
  Graph(int n):E(n),E2(n){d.resize(MAX_V);E.resize(MAX_V);V=n;E2.resize(MAX_V);}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});E2[to].pb(from);}
  //bellman_ford
  bool bellman_ford(int s) { // nは頂点数、sは開始頂点
    init();
    bool li[2555]={};
    li[V-1]=true;
    queue<ll>que;
    que.push(V-1);
    while(!que.empty()){
      ll now=que.front();
      que.pop();
     
      for(int i=0;i<E2[now].size();i++)
	if(li[E2[now][i]]==false){
	  li[E2[now][i]]=true;
	  que.push(E2[now][i]);
	}
    }
    d[s]=0;
    /*   for(int i=0;i<V;i++)
      cout<<li[i]<<" ";
      cout<<endl;*/
    for (int i=0;i<MAX_V;i++) {
      for (int v=0;v<MAX_V;v++) {
	for (int k=0;k<E[v].size();k++) {
	  Edge e=E[v][k];
	  if (d[v]!=Inf&&d[e.to]>d[v]+e.cost) {
	    d[e.to]=d[v]+e.cost;
	    if(i==MAX_V-1){
	      //cout<<v<<" "<<e.to<<endl;
	      if(li[e.to])
		return true; // n回目にも更新があるなら負の閉路が存在
	    }
	  }
	}
      }
    }
    return false;
  }
};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,m,p;cin>>n>>m>>p;
  Graph g(n);
  for(int i=0;i<m;i++){
    ll a,b,c;cin>>a>>b>>c;
    --a;--b;
    g.add_edge(a,b,-(c-p));
  }
  if(g.bellman_ford(0)==false){
    cout<<max(0LL,-g.d[n-1])<<endl;
  }else{cout<<-1<<endl;}
  return 0;
}

Measured memory_bytes: 640
n, k = map(int, input().split())
a = list(map(int, input(). split()))

res = 1 << 60 # 最小値が知りたいので答えの初期値はでかい数で
for i in range(1<<n): # k 個のビルが条件を満たすとし、その選び方をbit全探索する。選んだビル数がk以外の時はcontinueという方法で
    if(i%2 == 0): continue # 先頭のビルを見ないのは不可能なので一つ目のbitは必ず立っている必要がありその必要十分条件は「奇数であること」（最初のbitが1）

    use_idx = [0 for _ in range(n)] # どのビルに着目するか 0: 無視
    use_cnt = 0 # 着目するビルの数 kになる時だけ考える
    for j in range(n):
        if(i & (1<<j)):
            use_idx[j] = 1 # 1: 着目
            use_cnt += 1 # ＋＋着目

    if(use_cnt != k): continue # k個のビルに着目することだけを考える

    sm = 0 # 一つ目、先頭。いじる必要はないのでコストも0
    mx = a[0] # 先頭の高さが暫定最大の高さ
    for j in range(1, n):

        if(use_idx[j]): # 二つ目からみていく
            if(a[j] <= mx): # もし暫定最大の高さがこのビル以上の高さならば
                sm += mx+1 - a[j] # このビルは最大＋１の高さまで最低伸ばす必要があり
                mx += 1 # その高さが暫定最大の高さになる

        mx = max(mx, a[j]) # 着目するビルかどうかにかかわらず暫定最大高さは更新される（これをif(use)内に書くとだめだよ。見ないからと言って透明にはならないので）

    res = min(res, sm) # 全てのコストを計算したら暫定最安コストと戦う

print(res)

Measured memory_bytes: 3064
def median(array, sorted)
  array.sort! unless sorted
  if array.length.odd?
    return array[array.length / 2]
  else
    (array[array.length / 2 - 1] + array[array.length / 2]) / 2.0
  end
end

n = gets.to_i
smalls = []
larges = []
n.times do
  small, large = gets.split.map(&:to_i)
  smalls << small
  larges << large
end
smalls.sort!
larges.sort!
if n.odd?
  puts median(larges, true) - median(smalls, true) + 1
else
  puts (larges[larges.length / 2 - 1] + larges[larges.length / 2]) - 
       (smalls[smalls.length / 2 - 1] + smalls[smalls.length / 2]) + 1
end

Measured memory_bytes: 20380
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
class d{
    public static void Main(){
        long n = long.Parse(Console.ReadLine());
        long[] num = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
        Array.Sort(num);
        long ans = 0;
        long count = 1;
        long pos= n-1;
        for(int i=1; i<n; i++){
            ans += num[pos];
            count++;
            if(count == 2){
                count = 0;
                pos--;
            }
        }
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 44464
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct City{
  int b_n;
  int num;
  int p;
  int old;
  bool operator<( const City& right ) const {
        return p == right.p ? old < right.old : p < right.p;
    }
};

bool asc1( const City& left, const City& right ) {
    return left.b_n < right.b_n;
}
bool asc2( const City& left, const City& right ) {
    return left.p == right.p ? left.old < right.old : left.p < right.p;
}

int n,m;
City c[100009];
int main(){
  cin >> n >> m;
  for(int i=0;i<m;i++){
    cin >> c[i].p >> c[i].old;
    c[i].b_n = i;
  }
  sort(c,c+m,asc2);
  int a=1;
  c[0].num = a;
  for(int i=1;i<m;i++){
    if(c[i].p == c[i-1].p){
      a++;
      c[i].num = a;
    }else{
      a = 1;
      c[i].num = a;
    }
  }
  sort(c,c+m,asc1);

  for(int i=0;i<m;i++){
    printf("%06d%06d\n",c[i].p,c[i].num);
  }
  return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

int main(){
    int N;
    double R;
    while(cin >> N >> R && N > 0) {
        vector<double> xs(N), ys(N);
        REP(i, N) cin >> xs[i] >> ys[i];

        vector<double> p;
        REP(i, xs.size()){
            double x = xs[i];
            if(xs.front() <= x + R && x + R <= xs.back()) {
                p.push_back(x);
            }
        }
        REP(i, xs.size()){
            double x = xs[i] - R;
            if(xs.front() <= x && x <= xs.back()) {
                p.push_back(x);
            }
        }
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        double ans = 0.0;
        for(int i = 0; i + 1 < p.size(); i++) {
            double lx = p[i];
            double rx = p[i+1];
            double cx = (lx + rx) / 2;

            int k = upper_bound(xs.begin(), xs.end(), cx) - xs.begin() - 1;
            //assert(xs[k] <= lx && rx <= xs[k+1]);
            assert(k >= 0);
            double A = (ys[k+1] - ys[k]) / (xs[k+1] - xs[k]);
            double B = ys[k] - A * xs[k];
            
            double lxr = p[i] + R;
            double rxr = p[i+1] + R;
            double cxr = (lxr + rxr) / 2;
            int kr = upper_bound(xs.begin(), xs.end(), cxr) - xs.begin() - 1;
            //assert(xs[kr] <= lxr && rxr <= xs[kr+1]);
            assert(kr >= 0);
            double C = (ys[kr+1] - ys[kr]) / (xs[kr+1] - xs[kr]);
            double D = ys[kr] - C * xs[kr] + C * R;

            double E = A * C;
            double F = A * D + B * C;
            double G = B * D;
            // E * x^3/3 + F * x^2/2 + G*x
            auto f = [&](double x) -> double {
                return E*x*x*x/3 + F*x*x/2 + G*x;
            };
            ans += f(p[i+1]) - f(p[i]);
        }
        printf("%.12f\n", ans);
    }
    return 0;
}

Measured memory_bytes: 1268
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define _size(X) (int)((X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 200000, MAX_M = 200000;
int N, M;
int A[MAX_N];
int X[MAX_M], Y[MAX_M];
int _count[MAX_N+1];
int dp[MAX_N+1];

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

  cin >> N >> M;
  rep(i, N) cin >> A[i];
  rep(j, M) {
      cin >> X[j] >> Y[j];
      --X[j];
  }

  rep(i, N) {
      ++_count[A[i]];
  }

  rep(i, 1, N) {
      for (int j = 0; j < _count[i]; ++j) {
          if (i-j > 0) {
              ++dp[i-j];
          }
      }
  }

  int zeroNum = 0;
  rep(i, 1, N) {
      if (dp[i] == 0) ++zeroNum;
  }
 
  vector<Pii> xchg;
  rep(j, M) {
      int before = A[X[j]];
      int after = Y[j];
      A[X[j]] = Y[j];
      xchg.push_back(Pii(before, after));
  }

  for (int m = 0; m < M; ++m) {
      Pii pii = xchg[m];
      if (pii.fi - _count[pii.fi] + 1 > 0) {
          ll t = --dp[pii.fi - _count[pii.fi] + 1];
          if (t == 0) ++zeroNum;
      }
      --_count[pii.fi];
      ++_count[pii.sc];
      if (pii.sc - _count[pii.sc] + 1 > 0) {
          ll t = ++dp[pii.sc - _count[pii.sc] + 1];
          if (t == 1) --zeroNum;
      }
      cout << zeroNum << endl;
  }

  return 0;
}


Measured memory_bytes: 7536
class Node

  attr_accessor:id, :parent, :left, :right, :depth, :height, :sibling

  def initialize(id)
    @id = id
    @parent = nil
    @left = nil
    @right = nil
    @depth = 0
    @height = 0
    @sibling = nil
  end

  def depth
    if @parent.nil?
      0
    else
      @parent.depth + 1
    end
  end

  def height
    left_height =
      if @left.nil?
        -1
      else
        @left.height
      end
    right_height =
      if @right.nil?
        -1
      else
        @right.height
      end
    if left_height > right_height
      left_height + 1
    else
      right_height + 1
    end
  end

  def type
    if @parent == nil
      "root"
    elsif @child_left.nil?
      "leaf"
    else
      "internal node"
    end
  end

  def to_s
    parent_id =
      if @parent.nil?
        -1
      else
        @parent.id
      end

    sibling =
      if @sibling.nil?
        -1
      else
        @sibling.id
      end

    degree = 0
    if @left != nil
      degree = degree + 1
    end
    if @right != nil
      degree = degree + 1
    end

    type =
      if @parent.nil?
        "root"
      elsif @left.nil? && @right.nil?
        "leaf"
      else
        "internal node"
      end

    "node #{@id}: parent = #{parent_id}, sibling = #{sibling}, degree = #{degree}, depth = #{depth}, height = #{height}, #{type}"
  end

  def children_to_s
    ss = []
    if @child_left.nil?
      ss
    else
      a = @child_left
      while a != nil
        ss.push(a.id.to_s)
        a = a.right_sibling
      end
      ss
    end
  end
end

n = STDIN.gets.to_i

tree = []
for i in 0..(n - 1)
  as = STDIN.gets.split(' ')
  id = as[0].to_i
  left_id = as[1].to_i
  right_id = as[2].to_i

  node = tree[id]
  if node.nil?
    node = Node.new(id)
    tree[id] = node
  end

  if left_id != -1
    left = tree[left_id]
    if left.nil?
      left = Node.new(left_id)
      tree[left_id] = left
    end
    left.parent = node
    node.left = left
  end

  if right_id != -1
    right = tree[right_id]
    if right.nil?
      right = Node.new(right_id)
      tree[right_id] = right
    end
    right.parent = node
    node.right = right
  end

  if left_id != -1 && right_id != -1
    node.left.sibling = node.right
    node.right.sibling = node.left
  end

end

for i in 0..(n-1)
  puts tree[i].to_s
end

Measured memory_bytes: 8668
#include<bits/stdc++.h>
using namespace std;
int main(){
  int w,h,ans;
  bool b;
  int mp[70][70];
  while(1){
    cin>>w>>h;
    if(w==0 && h==0) break;
    for(int i=0;i<70;i++){
      for(int j=0;j<70;j++){
	mp[i][j]=0;
      }
    }
    ans=2;
    for(int i=1;i<=h;i++){
      for(int j=1;j<=w;j++){
	cin>>mp[i][j];
      }
    }
    for(int i=1;i<=h;i++){
      for(int j=1;j<=w;j++){
	b=true;
	if(mp[i][j]==1){
	  mp[i][j]=ans;
	  while(b){
	    b=false;
	    for(int k=1;k<=h;k++){
	      for(int l=1;l<=w;l++){
		if(mp[k][l]==ans){
		  for(int m=k-1;m<=k+1;m++){
		    for(int n=l-1;n<=l+1;n++){
		      if(mp[m][n]==1){
			mp[m][n]=ans;
			b=true;
		      }
		    }
		  }
		}
	      }
	    }
	  }
	  ans++;
	}
      }
    }
    cout<<ans-2<<endl;
  }
  return 0;
}
	  



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

int main()
{
	string S; cin >> S;
	ll bitnum = S.length() - 1;
	ll ans = 0;
	rep(i,(1<<bitnum)) {
		string tmp = "";
		int index = 0;
		rep(j,bitnum){
			tmp += S[index];
			if (i >> j & 0x01) {
				ans += atol(tmp.c_str());
				tmp = "";
			}
			else {
			}
			index++;
		}
		tmp += S[index];
		ans += atol(tmp.c_str());
	}
	cout << ans << endl;


}


Measured memory_bytes: 3632
#include<stdio.h>

int main()
{
    int i = 1;
    int x;

    while(1){
        scanf("%d", &x);
        if ( x == 0 /*|| 1<=x<=10000*/ ) break;
        printf("Case %d: %d\n",i ,x);
        i++;
    }

	return 0;
}


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

// dp[items][weight]
long long dp[101][100001];

int main() {
	int n, w;
	cin >> n >> w;
	vector<int> wt(n, 0), val(n, 0);

	for (int i = 0; i < n; i++) {
		cin >> wt[i] >> val[i];
	}

	//Base Case
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= w; j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 0;
			} else if (wt[i - 1] <= j) {
				dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	cout << dp[n][w] << endl;
	return 0;
}

Measured memory_bytes: 82504
#include <stdio.h>

int main(void)
{
	int i, j, n, t, ice[10];
	
	while (scanf("%d", &n), n != 0){
		for (i = 0; i < 10; i++){
			ice[i] = 0;
		}
		
		for (i = 0; i < n; i++){
			scanf("%d", &t);
			ice[t]++;
		}
		
		for (i = 0; i < 10; i++){
			if (ice[i] == 0){
				printf("-\n");
			}
			else {
				for (j = 0; j < ice[i]; j++){
					printf("*");
				}
				puts("");
			}
		}
	}
	
	return (0);
}

Measured memory_bytes: 588
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef vector<int> VE;
#define int long long
#define INF 1000000009
#define INFL 1000000000000000018
#define mod 1000000007
#define pb push_back
#define MAXN 100005

int n, a[100005], b, c;

signed main()
{
    cin >> n >> b;
    if(n % b){
        printf("1\n");
    }
    else{
        cout << 0 << endl;
    }

    return 0;
}


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

int main(){
    string s;
    cin >> s;

    rep(i,s.length()){
        cout << "x";
    }

    cout << "" << endl;
    return 0;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

typedef long long ll;

void solve() {

}

struct Data {
  int v;
  string s;
  bool operator < (const Data&d) const {
    if( v != d.v ) return v > d.v;
    return s < d.s;
  }
};

int main() {
  int n;
  cin >> n;
  map<string,int> mp;
  string s;
  rep(i,n) {
    cin >> s;
    ++mp[s];
  }
  int maxi = 0;
  for(auto v : mp) {
    maxi = max(maxi,v.snd);
  }
  vector<Data> vec;
  for(auto v : mp) {
    if( maxi == v.snd ) {
      vec.pb((Data){v.snd,v.fst});
    }
  }
  sort(ALL(vec));
  rep(i,(int)vec.size()) cout << vec[i].s << endl;

  return 0;
}


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

using namespace std;

typedef long long ll;
const int N = 200000 + 7;
int n, m;
ll s1[N], s2[N], k;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    cin >> s1[i];
    s1[i] += s1[i - 1];
  }
  for (int i = 1; i <= m; i++) {
    cin >> s2[i];
    s2[i] += s2[i - 1];
  }
  int j = m, sol = 0;
  for (int i = 0; i <= n && s1[i] <= k; i++) {
    while (s1[i] + s2[j] > k) {
      j--;
    }
    sol = max(sol, i + j);
  }
  cout << sol << "\n";
  return 0;
}


Measured memory_bytes: 6776
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <complex>
#include <regex>
#include <random>
using namespace std;

#define rep(i,n)	for(lint i = 0; i < n; i++)
#define repr(i,n)	for(lint i = n - 1; i >= 0; i--)
#define repi(i,ini,n)	for(lint i = ini; i < n; i++)
#define repir(i,ini,n)	for(lint i = n-1; i >= ini; i--)
#define repb(i,start,end)	for(lint i = start; i <= end; i++)
#define repbr(i,start,end)	for(lint i = end; i >= start; i--)

#define bit(n)				(1LL << (n))

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define rg(v, ini, end) v.begin() + ini, v.begin()+end

#define ret return 0;
#define chmax(a, b) a=mmax(a,b)
#define chmin(a, b) a=mmin(a,b)

using lint = long long;
using ulint = unsigned long long;
using ld = long double;
struct xy
{
	lint x, y;
	xy() :x(0), y(0) {}
	xy(lint _x, lint _y) : x(_x), y(_y) {}
	xy operator+(const xy& p) const
	{
		return xy(x + p.x, y + p.y);
	}
	bool operator<(xy p) const
	{
		if (y == p.y)
			return x < p.x;
		return y < p.y;
	}
};
struct xyd
{
	ld x, y;
	xyd() :x(0), y(0) {}
	xyd(long double _x, long double _y) : x(_x), y(_y) {}
};
using vec = vector<lint>;
using vecd = vector<ld>;
using vecs = vector<string>;
using vecp = vector<xy>;
template<class T> using vect = vector<T>;
class vec2 : public vector<vector<lint>>
{
public:
	vec2() {}
	vec2(lint n) : vector(n) {}
	vec2(lint h, lint w) : vector(h, vector<lint>(w)) {}
	vec2(lint h, lint w, lint v) : vector(h, vector<lint>(w, v)) {}
};

template<class T> using priq = priority_queue<T>;
template<class T> using rpriq = priority_queue<T, vector<T>, greater<T>>;
template<class Key, class Val> using hashmap = unordered_map<Key, Val>;
template<class Key> using hashset = unordered_set<Key>;

mt19937 mtrand((random_device())());

const double pi = 3.141592653589793238462;
const lint intmax = 9223372036854775807;
const lint inf = 1100100100100100100LL;

constexpr lint div2(lint p, lint q)
{
	return (p + q - 1) / q;
}

#if(__cplusplus < 201703L)

	lint gcd(lint a, lint b) {
		while (1) {
			if (a < b) swap(a, b);
			if (!b) break;
			a %= b;
		}
		return a;
	}

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

#endif

template<class T>
struct nval {
	lint n;		// counts
	T val;
	nval() : n(0) {};
	nval(lint _n, T _val) : n(_n), val(_val) {};
};

template<class It, class It2>
auto spacel(It i, It2 end)
{
	if (i + 1 == end)
	{
		return '\n';
	}
	else
	{
		return ' ';
	}
}

ostream& setp(ostream& ost)
{
	cout << setprecision(60) << fixed;
	return ost;
}

const ulint mod = 1000000007;
//const ulint mod = 998244353;
const ld eps = 0.0000001;


int main()
{
	ld r;
	cin >> r;
	cout << setp << r * r * pi << ' ' << 2 * r * pi << endl;
	return 0;
}



Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  string s,t="";

  cin >> s;

  for(int i=0;i<s.size();i++){
    if(i%2==0){
    t += s.at(i);
    }
  }

    cout << t << endl;
  

  return 0;
}

Measured memory_bytes: 512
#include<algorithm>
#include <bits/stdc++.h>
#include <math.h>
#include <queue>
using namespace std;
int main(void){
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	cout<<a[0]+a[1]<<endl;
	return 0;
}

Measured memory_bytes: 256