akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
using namespace std;

void quicksort(int array[], int left, int right){
    if(left >= right) return;
    
    int pivot = array[right];
    int cnt = left;
    
    for(int i = left; i <= right; i++){
        if(array[i] <= pivot){
            int tmp = array[cnt];
            array[cnt] = array[i];
            array[i] = tmp;
            cnt++;
        }
    }
    
    quicksort(array, left, cnt - 2);
    quicksort(array, cnt, right);
}

int main() {
    int input;
    
    cin >> input;
    
    int items[input];
    // Create non-duplicate array
    for(int i = 0; i < input; i++){
        cin >> items[i];
    }
    
    quicksort(items, 0, input - 1);
    
    float diff = items[0];
    for(int i = 1; i < input; i++){
        diff = (diff + items[i]) / 2;
    }
    
    cout << diff << endl;
    
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define max 1000000000
int main()
{
  int N,M;
  int i,j;
  scanf("%d %d",&N,&M);
  if(N > M)
  {
  	for(i=0;i<N;i++)
  		printf("%d",M);
  }
  else
  {
  	for(i=0;i<M;i++) printf("%d",N);
   } 
}

Measured memory_bytes: 128
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>

using namespace std;

typedef pair<int, int> P;
#define FOR(i, a, b) for(ll (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define _1 first
#define _2 second
#define pb push_back
#define bigmod 1000000007
#define INF 1050000000

const int maxn = 1e5 + 10;
vi G[maxn];
int n, m, u, v;
int a;

int main() {
	cin >> n;
	map<ll, int> m;
	vl v;
	rep(i, n) {
		cin >> a;
		if (not m[a]) m[a]++;
		else if (m[a] == 1)m[a]++,v.pb(a);
		else if (m[a] == 3)m[a]++, v.pb(a);
		else m[a]++;
	}
	sort(all(v),greater<>());

	if (v.size() < 2) {
		cout << 0 << endl;
	}
	else {
		cout << v[0] * v[1] << endl;
	}
	return 0;
}

Measured memory_bytes: 8832
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

long long int INF = 1e18;
long long int mod = 1000000007;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "RULD";
//↓,→,↑,←

#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,n) for(i=0;i<n;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl

ll rui(ll number1,ll number2){
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
    if(number1 > number2){
        swap(number1 , number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1 , number1);
    }
}

ll i,j,k,ii,jj;
ll n,m;
ll a,b,c,d,e,g,h,r,w;
ll l,ans,sum;
ll num;
ll x[500005],y[500005],z[500005];
bool dame,flag;

bool solve(ll v){
	num = 0;
	for(int i=0;i<n;i++){
		if(v < x[i])continue;
		num += (v-x[i])/y[i];
		num++;
	}
	if(num >= k){
		return true;
	}else{
		return false;
	}
}

int main(){
	cin >> n >> k;
	for(i=0;i<n;i++){
		cin >> x[i] >> y[i];
	}
	ll ng = 0,ok = 3*INF;
	ll mid ;
	while(ok - ng > 1){
		mid = (ng+ok)/2;
		if(solve(mid)){
			ok = mid;
		}else{
			ng = mid;
		}
	}
	p(ok);


    return 0;
}

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

int main() {
    int H,W,N;
    cin >> H >> W >> N;

    int result = 0;
  
	if( H >= W ) {
      result = N / H;
      if( N % H != 0){
        result += 1;
      }
    } else {
      result = N / W;
      if( N % W != 0){
        result += 1;
      }
    }

    cout << result << endl; 

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define sz(x) (int)(x).size()

struct UnionFind {
  vector<int> p, r, s;
  UnionFind (int n) {
    p.assign(n, 0);
    for (int i = 0; i < n; i++) p[i] = i;
    r.assign(n, 0);
    s.assign(n, 1);
  }
  int findSet (int x) { return (p[x] == x ? x : p[x] = findSet(p[x])); }
  bool sameSet (int x, int y) { return findSet(x) == findSet(y); }
  void unionSet (int x, int y) {
    x = findSet(x); y = findSet(y);
    if (x == y) return;
    if (r[x] > r[y]) {
      p[y] = x; s[x] += s[y];
    } else {
      p[x] = y; s[y] += s[x];
      if (r[x] == r[y]) r[y]++;
    }
  }
  int sizeOfSet (int x) { return s[findSet(x)]; }
};

const int N = 100010;
int n, m;
ll res[N];
vector<ii> edges;

void solve() {
  ll z = n;
  z = z * (z - 1) / 2;
  res[m - 1] = z;
  UnionFind uf (n);
  for (int i = m - 1; i >= 1; i--) {
    ii e = edges[i];
    if (uf.sameSet(e.first, e.second)) { res[i - 1] = res[i]; continue; }
    ll p = uf.sizeOfSet(e.first), q = uf.sizeOfSet(e.second);
    res[i - 1] = res[i] - p * q;
    uf.unionSet(e.first, e.second);
  }
  for (int i = 0; i < m; i++) printf("%lld\n", res[i]);
}

int main() {
  scanf("%d%d", &n, &m);
  int u, v;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    edges.push_back({u - 1, v - 1});
  }
  solve();
}



Measured memory_bytes: 4084
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>

int N, Q;
int V[1 << 18], W[1 << 18];
std::pair<int, int> top[1 << 9];
int botv[1 << 9], botw[1 << 9];
int best[1 << 9];

void chmax(int &lhs, int rhs) {
  if (lhs < rhs) lhs = rhs;
}
void chmax(long long &lhs, long long rhs) {
  if (lhs < rhs) lhs = rhs;
}

int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d %d", &V[i], &W[i]);
  }
  scanf("%d", &Q);
  while (Q--) {
    int v, l;
    scanf("%d %d", &v, &l);
    int topsize = 1, botsize = 1;
    while (v >= 512) {
      for (int i = 0; i < botsize; ++i) {
        botv[i + botsize] = botv[i] + V[v];
        botw[i + botsize] = botw[i] + W[v];
      }
      botsize <<= 1;
      v >>= 1;
    }
    while (v >= 1) {
      for (int i = 0; i < topsize; ++i) {
        top[i + topsize] = { top[i].first + W[v], top[i].second + V[v] };
      }
      std::inplace_merge(top, top + topsize, top + (topsize << 1));
      topsize <<= 1;
      v >>= 1;
    }
    best[0] = top[0].second;
    for (int i = 1; i < topsize; ++i) {
      best[i] = best[i - 1];
      chmax(best[i], top[i].second);
    }
    long long ans = 0;
    for (int i = 0; i < botsize; ++i) {
      if (botw[i] > l) continue;
      chmax(ans, (long long) botv[i] + best[std::lower_bound(top, top + topsize, std::make_pair(l - botw[i] + 1, 0)) - top - 1]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}


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

int main(void)
{
    ll N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<string> S(N);
    vector<string> ANS(N);
    for(ll i=0;i<N;i++){
        cin >> S.at(i);
    }
    for(ll i=0;i<N;i++){
        if(S.at(i) == "AB"){
            if(A==B && i!=N-1){
                if(S[i+1] == "BC"){
                    B++;
                    ANS[i] = "B";
                    A--;
                }else{
                    A++;
                    ANS[i] = "A";
                    B--;
                }
            }else if(A>B){
                A--;
                B++;
                ANS[i] = "B";
            }else{
                A++;
                ANS[i] = "A";
                B--;
            }
        }else if(S[i] == "BC"){
            if(B==C && i!=N-1){
                if(S[i+1]=="AB"){
                    B++;
                    ANS[i] = "B";
                    C--;
                }else{
                    B--;
                    ANS[i] = "C";
                    C++;
                }
            }else if(B>C){
                B--;
                C++;
                ANS[i] = "C";
            }else{
                B++;
                ANS[i] = "B";
                C--;
            }
        }else{
            // CA
            if(A==C && i!=N-1){
                if(S[i+1]=="AB"){
                    A++;
                    ANS[i] = "A";
                    C--;
                }else{
                    A--;
                    C++;
                    ANS[i] = "C";
                }
            }else if(A>C){
                A--;
                C++;
                ANS[i] = "C";
            }else{
                A++;
                C--;
                ANS[i] = "A";
            }
        }
        if(A<0 || B<0 || C<0){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    for(int i=0;i<N;i++){
        cout << ANS[i] << endl;
    }
    return 0;
}


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

int main(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; i++) cin >> x[i] >> y[i];
    map<pair<int, int>, int> dist;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i==j) continue;
            dist[{x[i]-x[j], y[i]-y[j]}]++;
        }
    }
    int cnt = 0;
    auto it = dist.begin();
    while (it != dist.end()) {
        cnt = max(cnt, (*it).second);
        it++;
    }
    cout << N-cnt << endl;
}


Measured memory_bytes: 384
A = input()
B = input()
C = input()

S = dict()
S['a'] = list(A[::-1])
S['b'] = list(B[::-1])
S['c'] = list(C[::-1])

next_p = 'a'
while S[next_p]:
    next_p = S[next_p].pop()
print(next_p.upper())

Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

int main() {
	int N;
	int A[100005];
	cin >> N;
	REP(i, N) {
		cin >> A[i];
	}

	sort(A, A + N);

	long long a1 = 0, a2 = 0;
	bool flag = 0;
	for (int i = N - 1;i >= 0;i--) {
		if (flag == 0) {
			if (A[i] == A[i - 1]) {
				a1 = A[i];
				flag = 1;
				i--;
				continue;
			}
		}
		if (flag == 1) {
			if (A[i] == A[i - 1]) {
				a2 = A[i];
				break;
			}
		}
		
	}

	long long ans = a1 * a2;

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#Union Find
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())

#根なら-size,子なら親の頂点
par = [-1]*n

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]

for i in range(m):
    X,Y,Z = map(int,input().split())
    unite(X-1,Y-1)
 
tank = set([])
for i in range(n):
    p = find(i)
    tank.add(p)
print(len(tank))

Measured memory_bytes: 12780
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)    \
  for (auto v : (V)) { \
    cout << v << " ";  \
  }                    \
  cout << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
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 (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> using vec = std::vector<T>;
template <class T> void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int A, B;
  cin >> A >> B;
  int ret = 0;
  for (int i = A; i <= B; i++) {
    string s = to_string(i);
    string tmps = s;
    reverse(ALL(tmps));
    if (s == tmps) ret++;
  }
  print(ret);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int a,b,x;
  cin >> a >> b >> x;
  if(x-a>=0&&x-a<=b){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}



Measured memory_bytes: 256
n = int(input())
a = [[int(i) for i in input().split()] for _ in range(2)]

if n == 1:
  temp_max = a[0][0] + a[1][0]
else:
  temp_max = 0
  for i in range(1, n):
    temp_l = 0
    for j in range(i):
      temp_l += a[0][j]
    for j in range(i-1, n):
      temp_l += a[1][j]
    if temp_max < temp_l:
      temp_max = temp_l
print(temp_max)


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

using namespace std;

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

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

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

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

  string s;
  cin >> s;
  vector<lint> ans(s.size() + 1, 0);
  lint r = 0, l = 0;
  rep(i, (int)s.size() - 1) {
    if (s[i] == 'R') r++;
    if (s[i] == 'R' && s[i + 1] == 'L') {
      ans[i] += (r + 1) / 2;
      ans[i + 1] += r / 2;
      r = 0;
    }
  }

  for (int i = (int)s.size() - 1; 0 < i; i--) {
    if (s[i] == 'L') l++;
    if (s[i] == 'L' && s[i - 1] == 'R') {
      ans[i] += (l + 1) / 2;
      ans[i - 1] += l / 2;
      l = 0;
    }
  }

  for (int i = 0; i < s.size(); i++) {
    cout << ans[i] << (i != (int)s.size() - 1 ? " " : "");
  }
  cout << "\n";

  return 0;
}

Measured memory_bytes: 1488
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

char c[200000];

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

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

	int l = -1;
	for (int i=0; i<N; i++) {
		if (c[i] == 'W') {
			l = i;
			break;
		}
	}

	if (l == -1) {
		cout << 0 << endl;
		return 0;
	}

	int ans = 0;
	for (int r = N-1; l < r; r--) {
		//cout << l << " " << r << endl; // **** debug ****
		if (c[r] == 'W') continue;

		ans++;

		while(1) {
			l++;
			if (c[l] == 'W' || l >= r) break;
		}
	}

	cout << ans << endl;

	return 0;
}

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

int alpha(char c){
  string u = "abcdefghijklmnopqrstuvwxyz";
  for(int i = 0;i < u.size();i++){
    if(c == u.at(i)){
      return i;
    }
  }
}
int main() {
  string s;
  cin >> s;
  vector<int>num(26);
  for(int i = 0;i < s.size();i++){
    num.at(alpha(s.at(i)))++;
  }
  for(int i = 0;i < 26;i++){
    if(num.at(i)%2 != 0){
      cout << "No" << endl;
      return 0;
    }
    else if(i == 25){
      cout << "Yes" << endl;
    }
  }
}


Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

vector<ll> cnt;
ll n;
vector<deque<pll>> DP; //(0,1)
vector<ll> node;
vector<vector<ll>> children;

ll mod_pow(ll a,ll x){
    ll ret=1;
    while(x>0){
        if(x&1){(ret*=a)%=MOD;}
        (a*=a)%=MOD;
        x>>=1;
    }
    return ret;
}

ll R(ll a){return mod_pow(a,MOD-2);}

void merge(ll p){
    if(children[p].size()==0){return;}
    ll w=-1,mx=-1;
    for(auto &I:children[p]){
        if(mx<(ll)DP[node[I]].size()){
            mx=DP[node[I]].size();
            w=I;
        }
    }
    if(w==-1){
        cout<<p<<" "<<mx<<endl;
        for(auto &I:children[p]){cout<<I<<" "<<node[I]<<" "<<DP[node[I]].size()<<" "<<(mx<(ll)DP[node[I]].size())<<endl;}
        assert(w!=-1);
    }
    vector<ll> H1,H2,H3;
    for(auto &I:children[p]){
        if(I==w){continue;}
        while(H1.size()<DP[node[I]].size()){H1.push_back(1); H2.push_back(1); H3.push_back(0);}
        for(int i=0;i<DP[node[I]].size();i++){
            (H1[i]*=DP[node[I]][i].F)%=MOD;
            (H2[i]*=DP[node[I]][i].F+DP[node[I]][i].S)%=MOD;
        }
    }
    for(int i=0;i<H1.size();i++){
        (H1[i]*=DP[node[w]][i].F)%=MOD;
        (H2[i]*=DP[node[w]][i].F+DP[node[w]][i].S)%=MOD;
    }
    for(auto &I:children[p]){
        for(int i=0;i<DP[node[I]].size() && i<H1.size();i++){
            H3[i]+=H1[i]*R(DP[node[I]][i].F)%MOD*DP[node[I]][i].S%MOD;
            H3[i]%=MOD;
        }
    }
    //if(p==0){cout<<H2[0]<<endl;}
    for(int i=0;i<H1.size();i++){
        DP[node[w]][i].F=(H2[i]-H3[i])%MOD;
        DP[node[w]][i].S=H3[i];
    }
    assert(DP[node[p]][0]==pll(1,1));
    DP[node[w]].push_front(DP[node[p]][0]);
    node[p]=node[w];
}


void dfs(ll w,ll d){
    cnt[d]++;
    for(auto &I:children[w]){
        dfs(I,d+1);
    }
    merge(w);
}



int main(){
    cin>>n;
    children.resize(n+1);
    node.resize(n+1);
    DP.resize(n+1,deque<pll>(1,{1,1}));
    cnt.resize(n+1,0);
    for(int i=0;i<=n;i++){node[i]=i;}
    for(int i=1;i<=n;i++){
        ll p;
        cin>>p;
        children[p].push_back(i);
    }
    dfs(0,0);
    ll ans=0;
    for(int i=0;i<DP[node[0]].size();i++){
        ans+=DP[node[0]][i].S*mod_pow(2,n+1-cnt[i])%MOD;
        ans%=MOD;
    }
    ans%=MOD;
    if(ans<0){ans+=MOD;}
    cout<<ans<<endl;
    
    
    return 0;
}


Measured memory_bytes: 168704
#include<bits/stdc++.h>
#define L long long
#define pb push_back
using namespace std;
int n,f[200010],g[200010],u[200010],fa[200010],y[200010],p;
L x[200010],z[200010];
inline int ff(int i)
{
    return i==fa[i]?i:fa[i]=ff(fa[i]);
}
inline bool chk(int i,int j)
{
    return y[i]==0 || y[j]!=0 && z[i]*y[j]>z[j]*y[i];
}
inline void up(int i)
{
    while(i>1 && chk(f[i],f[i>>1]))
      {
       swap(f[i],f[i>>1]);
       swap(g[f[i]],g[f[i>>1]]);
       i>>=1;
      }
}
inline void down(int i)
{
    int j;
    while(i*2<=p)
      {
       if(i*2==p || chk(f[i*2],f[i*2+1]))
         j=i*2;
       else
         j=i*2+1;
       if(chk(f[j],f[i]))
         {
          swap(f[i],f[j]);
          swap(g[f[i]],g[f[j]]);
          i=j;
         }
       else
         break;
      }
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k;
	scanf("%d",&n);
	fa[1]=1;
	for(i=2;i<=n;i++)
	  {
       scanf("%d",&j);
       fa[i]=i;
       u[i]=j;
      }
    for(i=1;i<=n;i++)
      {
       scanf("%d",&j);
       if(j)
         y[i]=1;
       else
         z[i]=1;
      }
    for(i=2;i<=n;i++)
      {
       f[++p]=i;
       g[i]=p;
       up(p);
      }
    while(p)
      {
       i=f[1];
       f[1]=f[p];
       g[f[1]]=1;
       p--;
       if(p)
         down(1);
       j=ff(u[i]);
       fa[i]=j;
       x[j]+=x[i]+y[j]*z[i];
       y[j]+=y[i];
       z[j]+=z[i];
       up(g[j]);
       //cout<<i<<" "<<j<<" "<<x[j]<<" "<<y[j]<<" "<<z[j]<<"!!\n";
      }
      //cout<<x[1]<<" "<<y[1]<<" "<<z[1]<<"\n";
    printf("%lld\n",x[1]);
	return 0;
}


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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int A, B;
  cin >> A >> B;
  if(A == 1) A = 14;
  if(B == 1) B = 14;
  if(A == B) puts("Draw");
  else if(A > B) puts("Alice");
  else puts("Bob");

  return 0;
}


Measured memory_bytes: 256
b = int(input())
a = [input() for i in range(b)]
ac = a.count('AC')
wa = a.count('WA')
tle = a.count('TLE')
re = a.count('RE')
print ('AC x '+str(ac))
print ('WA x '+str(wa))
print ('TLE x '+str(tle))
print ('RE x '+str(re))

Measured memory_bytes: 79188
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b,c;
  cin>>a>>b>>c;
  cout<<min(b,c);
  if(c+b-a<0){
    cout<<" 0";
  }else{
    cout<<" "<<(c+b)-a;
  }
  cout<<"\n";
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

class Amondai
{
    static void Main()
    {
        var HW = Console.ReadLine().Split(' ').Select(x=> Int32.Parse(x)).ToArray();
        var hw = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var all = HW[0] * HW[1];
        var ans = all - (HW[1] * hw[0] + (HW[0] - hw[0]) * hw[1]);
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13268
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main(){
  int n;
  double x;
  cin >> n;
  if(n%2 == 0){
    printf("0.5\n");
  }else{
    x = (n+1)/2;
    x = x/n;
    printf("%lf\n", x);
  }
  return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const ll INF = (1LL << 60)-1;

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

  ll n, W; cin >> n >> W;
  vector<ll> w(110), v(110);
  rep(i, n) cin >> w[i] >> v[i];

  // dp[i][j] := i まで見た時、価値が j となる重さの最小値
  ll dp[110][101010] = {};
  rep(i, 110) rep(j, 101010) dp[i][j] = INF;
  dp[0][0] = 0;

  rep(i, n) {
    rep(j ,101010) {
      if(j-v[i] >= 0) {
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]]+w[i]);
      }
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
    }
  }

  int ans = 0;
  rep(j, 101010) {
    if(dp[n][j] <= W) ans = max(ans, j);
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 87040
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>
#include<assert.h>
#include<random>
using namespace std;
#define int long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
// #define MOD 998244353 
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solve(void)
{
  int N,K;cin>>N>>K;
  string str;cin>>str;
  int cnt_dc = 0;
  for (int i = 0; i < N-1; i++)
  {
    if(str[i+1] != str[i])cnt_dc++;
  }
  cout<<min(N - cnt_dc -1 + K*2,N-1)<<endl;
  
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


Measured memory_bytes: 3744
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int Maxn = 2010;
const int Mod = 1e9+7;
int n, K;
int f[Maxn][Maxn], C[Maxn][Maxn], g[Maxn];
void up(int &x, int y) { x = x + y >= Mod ? x+y-Mod : x+y; }
int main() {
	int i, j, k;
	scanf("%d%d", &n, &K);
	C[0][0] = 1;
	for(i = 1; i <= n; i++){
		C[i][0] = 1;
		for(j = 1; j <= i; j++) C[i][j] = (C[i-1][j-1]+C[i-1][j])%Mod;
	}
	f[1][1] = 1; g[0] = 1;
	for(i = 1; i < K; i++){
		for(j = 1; j <= i; j++) up(f[i+1][j+1], f[i][j]);
		int sum = 0;
		for(j = i; j >= 1; j--){
			up(sum, f[i][j]);
			up(f[i+1][j], sum);
		}
		g[i] = sum;
	}
	int ans = g[K-1];
	for(i = 1; i < K; i++){
		j = K-1-i;
		if(n-2-j >= i){
			int p = C[n-2-j][i];
			if(!j) up(ans, p);
			else {
				for(k = 1; k <= j; k++) up(ans, 1ll*p*f[j][k]%Mod*C[i+k][i]%Mod);
			}
		}
	}
	for(i = 1; i < n-K; i++) ans = ans*2%Mod;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 30848
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
#出力の制限
#フェルマーの小定理なので、素数のみ使用
mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
flag = False
x , y = map(int,input().split())
MOD = 10 ** 9 + 7
for s in range(max(x,y)):
    if 2 * x - 3 * s == y:
        flag = True
        break
t = x - 2 * s
if flag:
    print(cmb((t+s),s,mod))
else:
    print(0)

Measured memory_bytes: 122048
N = int(input())


def dfs(s):
    if int(s) > N:
        return 0
    if all(s.count(c) > 0 for c in '753'):
        ret = 1
    else:
        ret = 0
    for c in '753':
        ret += dfs(s + c)
    return ret


print(dfs('0'))

Measured memory_bytes: 2940
import math as ma

n = int(input())
m = [list(map(int, input().split())) for i in range(n)]
t = [[0 for j in range(n) ] for i in range(n)]
ans = 0

for i in range(n):
    for j in range(n):
        if i == j or t[i][j] > 0:
            pass
        else:
            x = m[i][0] - m[j][0]
            y = m[i][1] - m[j][1]
            l = x**2 + y**2
            t[i][j] = ma.sqrt(l)
            t[j][i] = ma.sqrt(l)
    ans += sum(t[i])    

print(ans/n)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#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(int i = m;i < n;i++)
typedef int64_t llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define ld PRId64


int main(){
    int n,m;
    cin >> n >> m;
    cout << (n-1)*(m-1) << endl;
}



Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    ll a,b,x;
    cin >> a >> b >>x;
    if(a==0)cout << b/x+1;else cout << b/x-(a-1)/x;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)
#define SZ(a) int((a).size())

template <class T>
void chmax(T &a, T b) {
  if (a < b) a = std::move(b);
}
template <class T>
void chmin(T &a, T b) {
  if (a > b) a = std::move(b);
}

template <typename T>
using V = std::vector<T>;
template <typename T>
vector<T> make_vec(size_t n, T a) {
  return vector<T>(n, a);
}
template <typename... Ts>
auto make_vec(size_t n, Ts... ts) {
  return vector<decltype(make_vec(ts...))>(n, make_vec(ts...));
}
template <typename Container>
ostream &pprint(const Container &a, string_view sep = " ",
                string_view ends = "\n", ostream *os = nullptr) {
  if (os == nullptr) os = &cout;
  auto b = std::begin(a), e = std::end(a);
  for (auto it = std::begin(a); it != e; ++it) {
    if (it != b) *os << sep;
    *os << *it;
  }
  return *os << ends;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
  return pprint(a, ", ", "", &(os << "[")) << "]";
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &a) {
  return pprint(a, ", ", "", &(os << "{")) << "}";
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &a) {
  return pprint(a, ", ", "", &(os << "{")) << "}";
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &a) {
  return pprint(a, ", ", "", &(os << "{")) << "}";
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &a) {
  return os << "(" << a.first << ", " << a.second << ")";
}

#ifdef ENABLE_DEBUG
template <typename T>
void debug(T value) {
  cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  cerr << value << ", ";
  debug(args...);
}
#define DEBUG(...)                              \
  do {                                          \
    cerr << " \033[33m (L" << __LINE__ << ") "; \
    cerr << #__VA_ARGS__ << ":\033[0m ";        \
    debug(__VA_ARGS__);                         \
    cerr << endl;                               \
  } while (0)
#else
#define debug(...)
#define DEBUG(...)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int H, W;
  cin >> H >> W;
  V<int> A(H), B(H);
  REP(i, H) {
    cin >> A[i] >> B[i];
    A[i]--;
  }

  // start[cur] = rightmost start point to reach cur.
  map<int, int> start;
  start[-1] = -1;  // sentinel
  multiset<int> moves;
  REP(i, W) {
    start[i] = i;
    moves.insert(0);
  }

  for (int i = 0; i < H; ++i) {
    int l = A[i], r = B[i];
    auto it = start.lower_bound(l);
    int new_start = -1;
    while (it != start.end() && (it->first <= r)) {
      new_start = max(new_start, it->second);
      int m = it->first - it->second;
      moves.erase(moves.find(m));
      it = start.erase(it);
    }
    if (new_start != -1 && r < W) {
      start[r] = new_start;
      moves.insert(r - new_start);
    }
    if (moves.empty()) {
      cout << -1 << '\n';
    } else {
      cout << (*moves.begin()) + (i + 1) << '\n';
    }
  }
}


Measured memory_bytes: 23388
#include<iostream>
#include<string>
using namespace std;
int main () {
  string S;
  cin >> S;
  int N = S.size();
  string key = "Cqwertyuiopasdfghjklzxcvbnm";
  if (S[0] != 'A') {
    cout << "WA" << endl;
    return 0;
  }
  if (S[1] == key[0]) {
    cout << "WA" << endl;
    return 0;
  }
  bool did = false;
  for (int i = 1; i < N; i ++) {
    int ju = -1;
    for (int j = 0; j < 27; j ++) {
      if (S[i] == key[j]) ju = j;
    }
    if (ju == -1) {
      cout << "WA" << endl;
      return 0;
    }
    if (ju == 0 && did) {
      cout << "WA" << endl;
      return 0;
    }
    if (ju == 0) {
      did = true;
      if (i == N - 1) {
        cout << "WA" << endl;
        return 0;
      }
    }
  }
  if (!did) {
    cout << "WA" << endl;
    return 0;
  }
  cout << "AC" << endl;
}



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

using namespace std;

int main() {
	long long n, m;
	scanf ("%lld %lld", &n, &m);
	long long ans;
	ans = (m * 1900 + (n - m) * 100) * pow(2, m);
	printf("%lld\n", ans);
	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;

int main() {
    cin.tie(0)->sync_with_stdio(false);

	int n; cin >> n;
	vector<ll> a(n), b(n), c(n);
	REP(i, n) cin >> a[i];
	sort(a.begin(), a.end());
	REP(i, n) cin >> b[i];
	REP(i, n) cin >> c[i];
	sort(c.begin(), c.end());

	ll res = 0;
	REP(i, n) {
		auto itr = lower_bound(a.begin(), a.end(), b[i]);
		ll cnt_a = distance(a.begin(), itr);
		itr = upper_bound(c.begin(), c.end(), b[i]);
		ll cnt_c = distance(itr, c.end());
		res += cnt_a * cnt_c;
	}
	cout << res << '\n';
    return 0;
}


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


#define ll long long
#define pb push_back
#define mp make_pair
#define loop(i, a, b) for(int i = (a); i < (b); i++)
#define loopb(i, a, b) for(int i = (a); i > (b); --i)

typedef pair <int,int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <ll> vl;

const int mod = 1e9+7;
const int inf = 2e18+5;


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll n;
  cin>>n;
  int h[n+1];
  ll dp[n+1];
  loop(i,1,n+1){
    cin>>h[i];
    dp[i]=inf;
  }
  dp[1]=0;
  loop(i,1,n){
    for(int j: {i+1,i+2})
        if(j<=n) dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]));
  }
  cout<<dp[n];
  return 0;
}


Measured memory_bytes: 1408
N = int(input())
time = list(map(int, input().split()))
M = int(input())

eff = list(range(M*2))

for i in range(M):
    eff[i*2], eff[(i*2)+1] = map(int, input().split())
    
for i in range(M):
    total = sum(time) - time[eff[i*2]-1] + eff[(i*2)+1]
    print(total)

Measured memory_bytes: 3064
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    vector<int> h(n,0);
    vector<bool> good(n,true);

    for(int i=0; i!=n; i++) cin >> h.at(i);
    int i1, i2;
    for(int i=0; i!=m; i++){
        cin >> i1 >> i2;
        i1--;
        i2--;
        if(!(h.at(i1) > h.at(i2))) good.at(i1) = false;
        if(!(h.at(i2) > h.at(i1))) good.at(i2) = false;
    }
    int out = 0;
    for(auto i : good) if(i) out++;
    cout << out << endl;
    return 0; 
}

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

using namespace std;

long long dp[2][55];

int main()
{
  memset(dp, 0, sizeof(dp));
  int n, p, x;
  scanf("%d %d", &n, &p);
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &x);
    x = x & 1;
    dp[x][i] = 1;
    for (int j = 0; j < i; ++j) {
      dp[0][i] += dp[x][j];
      dp[1][i] += dp[x ^ 1][j];
    }
    ans += dp[p][i];
  }
  if (p == 0)
    ++ans;
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define yes(n) cout << ((n) ? "yes" : "no") << endl

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

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};

void chmin(int &a, int b) { if (a > b) a = b; }

ll GCD(ll a, ll b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll LCM(ll a, ll b) {
    ll g = GCD(a, b);
    return a / g * b;
}


int main() {
    int n, d;
    cin >> n >> d;
    int x[n][d];
    rep(i, n)rep(j, d) cin >> x[i][j];

    int ans = 0;
    for (int i=0;i<n-1;++i) {
        for (int j=i+1;j<n;++j) {
            ll dist = 0;
            rep(k, d) {
                dist += abs(x[i][k] - x[j][k]) * abs(x[i][k] - x[j][k]);
            }
            for (int l=1;l<=(40*40)*10;++l) {
                if ((double)dist / l == (double)l) ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
/* Author: Dhruv Rastogi */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define all(sdk) sdk.begin(),sdk.end()
#define mll map<int, int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define endl '\n'
#define vvll vector<vector<int> >
#define vll vector<int>
#define mint map<int,int> 
#define sz(x) (int)x.size()
#define sll set<int>
#define pll pair<int,int>
#define F first
#define S second
const long double PI = acos(-1.0);

void solve(){  
	double a,b,x;
	cin>>a>>b>>x;
	double h=x/(a*a);
	double rad;
	double k=2*h-b;
	if(k<0){
		k=2*x/(b*a);
		rad=atan(b/k);
		cout<<fixed<<setprecision(12)<<rad*180.0/PI<<endl;
	}
	else{
		rad=atan(a/(b-k));
		cout<<fixed<<setprecision(12)<<90.0-rad*180.0/PI<<endl;	
	}
	
	
}

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

Measured memory_bytes: 256
import random
N = int(input())
a = [int(ai) for ai in input().split()]

random.seed(42)
count = 0
for i in range(0, N-1):
    if a[i] == a[i+1]:
        count += 1
    while a[i] == a[i+1]:
        a[i+1] = random.randint(1, N)
        if i < N - 2:
            while a[i+1] == a[i+2]:
                a[i+1] = random.randint(1, N)

print(count)

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

int main() {
  string s;
  cin >> s;
  string t = s;
  int n = s.size();
  string s1 = s.substr(0, (n - 1) / 2);
  string s2 = s.substr((n + 1) / 2, (n - 1) / 2);
  string t1 = s1;
  string t2 = s2;
  reverse(s.begin(), s.end());
  reverse(s1.begin(), s1.end());
  reverse(s2.begin(), s2.end());
  bool flag = true;
  if (s != t) {
    flag = false;
  }
  if (s1 != t1) {
    flag = false;
  }
  if (s2 != t2) {
    flag = false;
  }
  if (flag) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)


var S []string
var P []int

type Idx []int

func (id Idx) Len() int {
	return len(id)
}

func (id Idx) Less(i, j int) bool {
	if S[id[i]] == S[id[j]] {
		return P[id[i]] > P[id[j]]
	}
	return S[id[i]] < S[id[j]]
}

func (id Idx) Swap(i, j int) {
	id[i], id[j] = id[j], id[i]
}

func main() {
	var N int
	fmt.Scan(&N)

	S = make([]string, N)
	P = make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&S[i])
		fmt.Scan(&P[i])
	}


	var id Idx = make([]int, N)
	for i := 0; i < N; i++ {
		id[i] = i
	}

	sort.Sort(id)

	for i := 0; i < N; i++ {
		fmt.Println(id[i] + 1)
	}
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
    cin >> n;
  int b[n];
    for(int i=0; i<n; i++) cin >> b[i];

  int state=1;
    for(int i=0; i<n; i++){
      state = b[state-1];
      if(state == 2){
        cout << i+1 << endl;
        return 0;
      }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();

        if (a < b && b < c){
            System.out.println("Yes");
        }else
            System.out.println("No");
    }
}

Measured memory_bytes: 26040
#include<stdio.h>
#include<string.h>

char s1[1000];
char s2[2000];

int lcs(int l1,int l2){
  int i,j,x,answer[1000][1000];
  x=0;
  for(i=0;i<l1;i++)answer[i][0]=0;
  for(i=0;i<l2;i++)answer[0][i]=0;

  for(i=0;i<l1;i++){
    for(j=0;j<l2;j++){
      if(s1[i]==s2[j] && s1[i]!=' '){
	if(i==0 || j==0){answer[i][j]=1;}
	else {answer[i][j]=answer[i-1][j-1]+1;}
      }
    
      else{
	if(i == 0 && j != 0){
	  answer[i][j] = answer[0][j-1];
	}
	else if(i !=0 && j == 0){
	  answer[i][j] = answer[i-1][0];
	}
	else if(i == 0 && j == 0){
	  answer[0][0] = 0;
	}
	else if(i != 0 && answer[i-1][j] > answer[i][j-1]){
	  answer[i][j] = answer[i-1][j];
	}
	else if(answer[i-1][j] <= answer[i][j-1]){
	  answer[i][j] = answer[i][j-1];
	}
      }
    }
  }
  return answer[l1-1][l2-1];
}

int main(){
  int sumstring,i,j,k;
  scanf("%d",&sumstring);

  for(i=0;i<sumstring;i++){
    scanf("%s %s",s1,s2);
    printf("%d\n",lcs(strlen(s1),strlen(s2)));    
  }

  return 0;
}



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

using namespace std;

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

int N, M;
int k[22], s[22][22], p[22];

signed main() {
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> k[i];
        for (int j = 1; j <= k[i]; j++)cin >> s[i][j];
    }
    for (int i = 1; i <= M; i++)cin >> p[i];
    int ans = 0;
    for (int i = 0; i < (1 << N); i++) {
        int c = i << 1;
        for (int j = 1; j <= M; j++) {
            int a = 0;
            for (int l = 1; l <= k[j]; l++) {
                a ^= ((c & (1 << s[j][l])) != 0);
            }
            if (a != p[j])goto nene;
        }
        ans++;
        nene:;
    }
    cout << ans << endl;
}

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

using namespace std;

int main()
{
    int n,k;cin>>n>>k;
    int h[n];
    for(int i=0;i<n;i++)
        cin>>h[i];
    int dp[n+1];
    for(int i=0;i<=n;i++)
        dp[i]=INT_MAX;
    dp[0]=dp[1]=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i-1-j>=0)
            {
                int cost=abs(h[i-1]-h[i-1-j]);
                dp[i]=min(dp[i],dp[i-j]+cost);
            }
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}


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

using namespace std;

#define MAXN 100500

int a[MAXN];

int ans[MAXN];

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

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


	ans[0] = 0;
	ans[1] = abs(a[1] - a[0]);


	for (int i = 2; i < n; i++) {
		ans[i] = min(ans[i-1] + abs(a[i-1]-a[i]), ans[i-2] + abs(a[i-2]-a[i]));
	}

	cout << ans[n-1];
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005,M=200005,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,m,cnt,S,T,ans,a[N],b[N],bela[N],belb[N];
int fir[N],firr[N],siz;
struct edge{int u,v,w,nex;}e[M*2];
void add(int u,int v,int w){
	e[++siz]=(edge){u,v,w,fir[u]};fir[u]=siz;
	e[++siz]=(edge){v,u,0,fir[v]};fir[v]=siz;
}
int dist[N],que[N];
void dec(int x,int fl){e[x].w-=fl;e[x^1].w+=fl;}
bool bfs(int S,int T){
	memset(dist,0x3f,4*(cnt+1));
	int l=1,r=1;que[l]=S;dist[S]=0;
	while (l<=r){
		int x=que[l];
		for (int i=fir[x];i;i=e[i].nex)
		if ((e[i].w)&&(dist[e[i].v]>dist[x]+1)){
			que[++r]=e[i].v;
			dist[e[i].v]=dist[x]+1;
		}
		l++;
	}
	return dist[T]!=inf;
}
int dfs(int x,int flow){
	if (x==T) return flow;
	int fl=0,t=0;
	for (int i=firr[x];i;i=e[i].nex)
	if (e[i].w&&(dist[e[i].v] == dist[x] + 1)){
		t=dfs(e[i].v,min(flow-fl,e[i].w));
		dec(i,t);fl+=t;
		if (fl==flow) {firr[x]=i;return fl;}
	}
	firr[x]=0;
	return fl;
}
int dinic(){
	int flow=0;
	while (bfs(S,T)){
		for (int i=0;i<=cnt;i++) firr[i]=fir[i];
		flow+=dfs(S,inf);
		//cerr<<flow<<endl;
	}
	return flow;
}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	siz=1;
	n=read();
	for (int i=1;i<=n;i++) a[i]=read()+1;
	for (int i=1;i<=n;i++) b[i]=read()+1;
	for (int i=1;i<=n;i++)
	if ((a[i]!=i)&&(!bela[i])){
		cnt++;int x=i;
		while (!bela[x]){bela[x]=cnt;x=a[x];}
	}
	for (int i=1;i<=n;i++)
	if ((b[i]!=i)&&(!belb[i])){
		cnt++;int x=i;
		while (!belb[x]){belb[x]=cnt;x=b[x];}
	}
	S=0;T=cnt+1;cnt++;ans=n;
	for (int i=1;i<=n;i++)
	if (bela[i]&&belb[i]) {
		add(bela[i],belb[i],1);
		if (a[i]==b[i]) add(belb[i],bela[i],1);
	}
	else if (bela[i]) add(bela[i],T,1);
	else if (belb[i]) add(S,belb[i],1);
	else ans--;
	ans-=dinic();
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 15616
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 502;
const ll lmod = 1e9+7;

int main(){
  int N;
  int ans[MAX_N];
  cin >> N ;
  rep(i,N-1){
    int c,s,f;
    cin >> c >> s >> f ;
    ans[i] = s;
    rep(j,i+1){
      ans[j] = max(s,(ans[j]+f-1)/f*f);
      ans[j] += c;
    }
  }
  rep(i,N-1) cout << ans[i] << endl;
  cout << "0" << endl;
  
  return 0;
}

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


int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b < c + d) {
		cout << "Right";
	}
	else if (a + b == c + d) {
		cout << "Balanced";
	}
	else {
		cout << "Left";
	}
	return 0;
}


Measured memory_bytes: 256