akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;


struct node{
    int parent;
    int degree;
    int sibling; //anh em
    int depth;
    int height; // li??n k???t
    vector<int> child;
};

int setheight(vector<node> tree, int id)
{
    int l = 0, r = 0;
    if (tree[id].degree >= 1)
    {
        l = setheight(tree, tree[id].child[0]) + 1;
    }
    if (tree[id].degree >= 2)
    {
        r = setheight(tree, tree[id].child[1]) + 1;
    }
    return tree[id].height = max(l, r);
}

int main()
{
    int n;
    cin >> n;
    vector<node> tree;
    tree.resize(n);
    int id, child1, child2;
    for (int i = 0; i < n; i++)
    {
        tree[i].depth = 0;
        tree[i].sibling = -1;
        tree[i].parent = -1;

    }
    for (int i = 0; i < n; i++)
    {
        cin >> id >> child1 >> child2;

        if (child1 != -1 && child2 != -1)
        {
            tree[id].child.resize(2);
            tree[id].degree = 2;
            tree[child1].sibling = child2;
            tree[child2].sibling = child1;
            tree[id].child[0] = child1;
            tree[id].child[1] = child2;

        }

        else if (child1 != -1 && child2 == -1)
        {
            tree[id].child.resize(1);
             tree[id].degree = 1;
             tree[id].child[0] = child1;
        }
            else if (child2 != -1 && child1 == -1)
            {
                tree[id].child.resize(1);
                tree[id].degree = 1;
                tree[id].child[0] = child2;
            }
            else tree[id].degree = 0;

    }
    for (int i = 0; i < n; i++)
    {
        tree[i].height = setheight(tree, i);
        if (tree[i].degree != 0)
        {
            for (int j = 0; j < tree[i].degree; j++)
            {
                tree[tree[i].child[j]].parent = i;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {

        int j = i;
        while(tree[j].parent != -1)
        {
            j = tree[j].parent;
            ++tree[i].depth;
        }

    }

    for (int i = 0; i < n; i++)
    {
        cout << "node " << i << ": " << "parent = " << tree[i].parent << ", sibling = " << tree[i].sibling << ", degree = " << tree[i].degree << ", depth = " << tree[i].depth << ", height = " << tree[i].height << ", ";
        if (tree[i].parent == -1)
            cout << "root" << endl;
        else if (tree[i].degree == 0)
            cout << "leaf" << endl;
        else cout << "internal node" << endl;
    }
    return 0;
}

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

int main() {
	cin.tie(0);
  ios::sync_with_stdio(false);
 
	int n,k,i,j,r,a,b,sum;
  vector<int> v;
  string s;
  cin>>s;
  if(s.length() % 2 != 0){
    cout<<"No";
    return 0;
  }
  for(int i = 0; i<s.length(); i++){
    if(i%2==0){
      if(s[i] != 'h'){
        cout<<"No";
        return 0;
      }
    } else {
      if(s[i] != 'i'){
        cout<<"No";
        return 0;
      }
    }
  }
  cout<<"Yes";
  

  return 0;
}

Measured memory_bytes: 256
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
 
ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
 
ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}
 
 
int n, arr[5005], b[5005];
 

int main(){
 
    ios_base::sync_with_stdio(0);
 
    ll x;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        arr[i+n] = arr[i];
    }

    ll ans = 0;
    for(int i=0;i<n;i++){
    	ans += arr[i];
    	b[i] = arr[i];
    }

// for(int i=0;i<n;i++)	cout<<b[i]<<" ";cout<<endl;

    for(int k=1;k<n;k++){

    	for(int i=0;i<n;i++){
    // if(k==2)	cout<<"yolo "<<i<<" "<<b[i]<<endl;
    		b[i] = min(b[i], arr[(i-k%n+n)%n]);
    	}

    	ll temp = 1LL*k*x;
    	for(int i=0;i<n;i++){
    		temp += b[i];
    	}

   // cout<<k<<" "<<temp<<endl;
    	ans = min(ans, temp);
    }
 
    cout<<ans;
    return 0;
}




Measured memory_bytes: 256
from collections import deque
n,q=map(int,input().split())
K=[set() for _ in range(n)]
V=[False]*n
P=[0]*n
for i in range(n-1):
      a,b=map(int,input().split())
      K[a-1].add(b-1)
      K[b-1].add(a-1)
for i in range(q):
      c,d=map(int,input().split())
      P[c-1]+=d
que=deque([0])
while que:
      s=que.popleft()
      V[s]=True
      for ni in K[s]:
            if V[ni]==False:
                  P[ni]+=P[s]
                  que.append(ni)
print(*P)

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

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

  int n;
  cin >> n;
  map<string, int> counter;
  int max_num = 0;
  for (int i = 0; i < n; i++)
  {
    string s;
    cin >> s;
    if(counter.count(s)) counter.at(s)++;
    else counter[s] = 1;
    max_num = max(max_num, counter.at(s));
  }
  for (auto elem : counter)
  {
    auto value = elem.second;
    if(max_num == value) cout << elem.first << endl;
  }
  return 0;
}

Measured memory_bytes: 25728
import sys
from heapq import heapify, heappop, heappush
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = S()

if N%2 == 0:
  num = N//2
  if s[:num] == s[num:]:
    print("Yes")
    exit()
print("No")

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

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 1000000007

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

int dp[111][11111];

int main()
{
	int n,W;cin >> n >> W;
	for(int i = 0;i < n;i++){
		int v,w;cin >> v >> w;
		for(int j = 0;j <= 10000;j++){
			dp[i+1][j] = max(dp[i][j],dp[i+1][j]);
			dp[i][j+1] = max(dp[i][j],dp[i][j+1]);
			dp[i+1][j+w] = max(dp[i+1][j+w],dp[i][j]+v);
		}
	}
	cout << dp[n][W] << endl;

	return 0;
}


Measured memory_bytes: 7476
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

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

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))

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

const int mod = 1000000007;

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

  long n;
  cin >> n;

  vector<long> d(n);
  fillLong(d, n);

  long res = 0;
  rep(i, n) {
    for(int j = i+1; j < n; j++) {
      res += (d[i]*d[j]);
    }
  }

  cout << res << endl;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)

using namespace std;
typedef long long int ll;

// a b ... z  aa ab ac ... zz
// 0 1     25 26 27 28     701

int main(void) {
  ll N;
  cin >> N;
  string ans;
  while (N >= 1) {
    N--;
    string t{'a' + (N % 26)};
    ans = t + ans;
    N /= 26;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3592
/*
 * atcoder/abc122_2nd/d.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

#define MOD 1000000007
template <class T> void madd(T &a, T b){ if((a+=b)>=MOD) a-=MOD; }
template <class T> void msub(T &a, T b){ if((a+=MOD-b)>=MOD) a-=MOD; }

/*
 * ダメなパターン.
 * AGC
 * GAC
 * ACG
 * A*GC
 * AG*C
 *
 * 前2つと今回だけ見ればよさそう.
 */
int N;
enum {
  A = 1,
  C,
  G,
  T
};
ll dp[110][5][5][5];

ll rec(int n=0, int n_3 = 0, int n_2 = 0, int n_1 = 0) {
  ll &cc = dp[n][n_3][n_2][n_1];
  if (~cc) return cc;
  if (n==N) {
    return cc = 1;
  }
  ll num = 0;
  loop(i,1,5) {
    // AGC
    if (n_2 == A and n_1 == G and i == C) continue;
    // GAC
    if (n_2 == G and n_1 == A and i == C) continue;
    // ACG
    if (n_2 == A and n_1 == C and i == G) continue;
    // A*GC
    if (n_3 == A and n_1 == G and i == C) continue;
    // AG*C
    if (n_3 == A and n_2 == G and i == C) continue;
    madd(num, rec(n+1, n_2, n_1, i));
  }
  return cc = num;
}
void solve() {
  cin >> N;
  memset(dp, -1, sizeof(dp));
  cout << rec() << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cmath>
using namespace std;
int a[1005];
int main()
{
	int x;
	cin>>x;
	if(x==1) {
		cout<<1<<endl;
		return 0;
	}
	for(int i=2;i*i<=x;i++)
	   for(int j=2;pow(i,j)<=x;j++)
	         {
	         	int temp=pow(i,j);
	         	a[temp]=1;
			 }
    for(int i=1000;i>=1;i--)
    {
    	if(a[i]) {
    		 cout<<i<<endl;
    		 break;
		}
	}
	return 0;
 } 

Measured memory_bytes: 256
class UnionFind:
    __slots__ = ["N", "root"]

    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        """
        self.N = N
        self.root = [-1] * N

    def __repr__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def find(self, x):
        """頂点xの根を見つける"""
        r = x
        while self.root[r] >= 0:
            r = self.root[r]

        while self.root[x] >= 0:
            self.root[x], x = r, self.root[x]

        return r

    def union(self, x, y):
        """x, yが属する木をunion"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.root[y] < self.root[x]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

    def same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find(i) == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        """連結成分の数"""
        return len(self.roots())

    def all_group_members(self):
        """{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    x, y = map(int, input().split())
    uf.union(x - 1, y - 1)
k = uf.group_count()

print(k - 1)


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

int32_t main(){

	int n;
	cin >> n;
	std::vector<int> v(n);
	int xx = 0;
	for(int i =0 ; i < n; ++i){
		cin >> v[i];
		xx ^= v[i];
	}

	for(int i = 0; i < n; ++i)
		cout << (xx ^ v[i]) << " ";
	cout << "\n";
}

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

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

  int n;

  for(int i=0;i<3;i++){
    for(int j=1;j<3;j++){
      if(a[i]>a[j] && i < j){
        n = a[i];
        a[i] = a[j];
        a[j] = n;
      }
    }
  }

  for(int i=0;i<3;i++){
    if(i==2){
      cout << a[i] << endl;
    }else{
      cout << a[i] << " ";
    }
  }

  return 0;
}



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

using namespace std;

int n , d , x , y , ans;

int main() {
	scanf("%d %d" , &n , &d);
	for (int i = 0; i < n; i++) {
		scanf("%d %d" , &x , &y);
		if (sqrt(pow(x , 2)+pow(y , 2)) <= d) ans++;	
	}
	
	printf("%d" , ans);
	
	return 0;
}

Measured memory_bytes: 3768
using System.Collections;
using System;
using System.Collections.Generic;

public class Program{

	public static void Main(){

		string line;
		List <string> numberList = new List<string> ();

		// ??\???
		while (true) {

			line = Console.ReadLine ();
			if (line != null) {
				numberList.Add (line);
			} else {
				break;
			}
		}

		foreach (var n in numberList) {

			string[] numbers = n.Split (' ');

			long least = LeastCommonMultiple (long.Parse(numbers[0]), long.Parse(numbers[1]));
			long greatest = GreatestCommonDivisor (long.Parse(numbers[0]), long.Parse(numbers[1]));

			// ??????
			Console.WriteLine ("{0} {1}",greatest, least);
		}

	}

	// ????°???¬?????°
	public static long LeastCommonMultiple(long n1, long n2){

		long temp=Math.Max(n1,n2);
		n2=Math.Min(n1,n2);//n2?????????????????°???????°????

		n1=temp;//n1?????????????????°????????§???

		long product=n1*n2;//?±?????????°???????§?

		while(n2!=0)
		{
			n1=n1>n2?n1:n2;//???n1????????°??§???n2????????°
			long m=n1%n2;
			n1=n2;
			n2=m;
		}
		return(product/n1);//????°???¬?????°
	}

	// ?????§??¬?´???°
	public static long GreatestCommonDivisor(long n1, long n2){


		long temp=Math.Max(n1,n2);
		n2=Math.Min(n1,n2);//n2?????????????????°???????°????

		n1=temp;//n1?????????????????°????????§???

		//int product=n1*n2;//?±?????????°???????§?

		while(n2!=0)
		{
			n1=n1>n2?n1:n2;//???n1????????°??§???n2????????°
			long m=n1%n2;
			n1=n2;
			n2=m;
		}
		return n1;//????°???¬?????°
	}
}

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,k; cin>>n>>k;
	if(((n+1)/2)>=k) cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
    string S, T;
    cin >> S >>  T;
  bool ans = true;
  if(T.size() != S.size() + 1){
    ans = false;
  }
  for(int i = 0; i < S.size(); i++){
    if(S.at(i) != T.at(i)){
      ans = false;
      break;
    }
  }
  if(ans == true){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h, w, ch, cw, dh, dw;
  cin >> h >> w >> ch >> cw >> dh >> dw;
  ch--;
  cw--;
  dh--;
  dw--;
  //h = 1000, w = 1000, ch = cw = 0, dh = dw = 999;
  vector<vector<char>> s(h, vector<char>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> s[i][j];
    }
  }
  
  vector<vector<int>> d(h, vector<int>(w, 1e9));
  priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
  pq.push(make_tuple(0, ch, cw));
  d[ch][cw] = 0;
  while (!pq.empty()) {
    auto [dist, nowx, nowy] = pq.top();
    pq.pop();
    if (d[nowx][nowy] < dist) continue;
    for (int i = 0; i < 4; i++) {
      int nx = nowx + dx[i], ny = nowy + dy[i];
      if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '.' && d[nx][ny] > dist) {
        d[nx][ny] = dist;
        pq.push(make_tuple(dist, nx, ny));
      }
    }
    for (auto i : {-2, -1, 0, 1, 2}) {
      for (auto j : {-2, -1, 0, 1, 2}) {
        int nx = nowx + i, ny = nowy + j;
        if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '.' && d[nx][ny] > dist + 1) {
          d[nx][ny] = dist + 1;
          pq.push(make_tuple(dist + 1, nx, ny));
        }
      }
    }
  }
  /*
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cout << d[i][j] << " ";
    }
    cout << endl;
  }*/
  
  if (d[dh][dw] == 1e9) cout << -1 << '\n';
  else cout << d[dh][dw] << '\n';
}

Measured memory_bytes: 8328
#include<stdio.h>

int bubbleSort(int *, int);

main(){

  int n,i,num[100],c;

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++)
    scanf("%d",&num[i]);

  c = bubbleSort(num, n);

  for(i = 0 ; i < n ; i++){
    printf("%d",num[i]);
    if(i!=n-1) printf(" ");
  }

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

  return 0;
}

int bubbleSort(int *num, int n){

  int flag = 1,tmp,count=0,j;

  while(flag){

    flag = 0;

    for(j = n-1 ; j >= 1 ; j--){
      if(num[j] < num[j-1]){
	tmp = num[j];
	num[j] = num[j-1];
	num[j-1] = tmp;
	flag = 1;
	count++;
      }
    }
  }

  return count;
}

Measured memory_bytes: 604
import java.util.*;

public class Main {    
    public static void main(String[] args){

       Scanner sc = new Scanner(System.in);
       
       long X = sc.nextLong();
       long A = sc.nextLong();
       long B = sc.nextLong();
       
        if(B <= A){
            System.out.println("delicious");
        }else if(B <= A + X){
            System.out.println("safe");
        }else if(B >= A + X + 1){
            System.out.println("dangerous");      
        }
    
    }        
}        
    

Measured memory_bytes: 21716
#include "stdio.h"

int main(void) {
  int N;
  int aa[100];
  int bb[100];
  int max, max2;
  int cnt;
  int i, j, h;
  
  scanf("%d", &N);
  for(i=0; i < N; i++)
  {
      scanf("%d", &aa[i]);
  }
  
  for(i=0; i < N; i++)
  {
      scanf("%d", &bb[i]);
  }
  
  cnt = 0;
  max = 0;
  max2 = 0;
  for(j=0; j < N; j++)
  {
    for(i=0; i < N; i++)
    {
        max = max + aa[i];
        cnt++;
        if (cnt == N - j )
        {
          for(h=i; h < N; h++)
          {
            max = max + bb[h];
          }
          if(max > max2)
          {
            max2 = max;
          }
        }
    }
    cnt = 0;
    max = 0;
  }
  
  printf("%d\n", max2);
  
  return 0;
}

Measured memory_bytes: 128
from bisect import bisect_left

N,H=map(int,input().split())
amax=0
B=[]
for i in range(N):
  a,b=map(int,input().split())
  if a>amax:amax=a
  B.append(b)

B = sorted(B)
idx = bisect_left(B,amax)
B = B[idx:][::-1]
cum=[0]
for i in range(len(B)):
  cum += [cum[-1]+B[i]]
  if cum[-1]>=H:
    print(i+1)
    exit()
print(len(B) + ((H-cum[-1])+amax-1)//amax)

Measured memory_bytes: 17596
from collections import deque

def push(d, x):
    if d == 0:
        ary.appendleft(x)
    elif d == 1:
        ary.append(x)

def random_access(p):
    print(ary[p])

def pop(d):
    if d == 0:
        ary.popleft()
    elif d == 1:
        ary.pop()

q = int(input())
ary = deque()
for _ in range(q):
    op = list(map(int, input().split()))
    if op[0] == 0:
        push(op[1], op[2])
    elif op[0] == 1:
        random_access(op[1])
    elif op[0] == 2:
        pop(op[1])



Measured memory_bytes: 21840
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    ll ans=1;
    for(int i=1;i*i<=N;i++){
        ans=i*i;
    }
    cout << ans << endl;


    return 0;
    

}

Measured memory_bytes: 3596
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<iomanip>

#define mod 1000000007
#define ll long long int
#define pb(x) push_back(x)
#define MP(x,y) make_pair(x,y)

using namespace std;

ll power(ll a, ll b, ll m)
{
	if (b == 0)
		return(1);
	ll sol = power(a, b / 2, m);
	sol = (sol * sol) % m;
	if (b % 2 == 1)
		sol = (sol * a) % m;
	return(sol);
}
ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	else
	{
		return gcd(b, a % b);
	}
}
void solve()
{
	int a, b;
	cin >> a >> b;
		for (int i = b - (a - 1); i <= b + (a - 1); i++)
		{
			cout << i << " ";
		}
}
int main()
{
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

Measured memory_bytes: 256
n=int(input())
s=[list(input()) for i in range(2)]
mod=10**9+7
idx=0
dp=[0]*n
if s[0][0]==s[1][0]:
  dp[0]=3
  idx+=1
else:
  dp[0]=6
  dp[1]=dp[0]
  idx+=2
while idx<n:
  if s[0][idx]==s[1][idx] and s[0][idx-1]!=s[1][idx-1]:
    dp[idx]=dp[idx-1]
    idx+=1
  elif s[0][idx]!=s[1][idx] and s[0][idx-1]==s[1][idx-1]:
    dp[idx+1]=dp[idx]=(dp[idx-1]*2)%mod
    idx+=2
  elif s[0][idx]==s[1][idx] and s[0][idx-1]==s[1][idx-1]:
    dp[idx]=(dp[idx-1]*2)%mod
    idx+=1
  else:
    dp[idx+1]=dp[idx]=(dp[idx-1]*3)%mod
    idx+=2
print(dp[n-1])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define PI 3.1415926535897932
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  
  int low=max(A,C);
  
  int up=min(B,D);
  
  
  cout<<max(0,up-low)<<endl;
}

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

int main(){
    int a, b;
    cin >> a >> b;
    // n * (a-1) + 1 >= b
    // n >= (b-1) / (a-1)
    if (b == 1){
        cout << 0 << endl;
    } else{
    cout << (b-2) / (a-1) + 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
from collections import deque
n=int(raw_input())
q = deque()
for i in xrange(n):
    o = raw_input()
    if o == 'deleteFirst':  q.popleft()
    elif o == 'deleteLast': q.pop()
    else:
        c,p = o.split(); p = int(p)
        if c == 'insert': q.appendleft(p)
        elif c == 'delete':
            try: q.remove(p)
            except: pass
print ' '.join(map(str,q))

Measured memory_bytes: 49124
import sys
input = sys.stdin.readline
from itertools import product
INF = 10**9
MOD = 10**9 + 7

def main():
    n,c = map(int,input().split())
    sushi = [list(map(int,input().split())) for _ in range(n)]
    
    r = [0] * (n+1)
    l = [0] * (n+1)
    r_max = [0] * (n+1)
    l_max = [0] * (n+1)

    x = 0
    y = c
    for i in range(n):
        r[i+1] = r[i] + sushi[i][1] - sushi[i][0] + x
        r_max[i+1] = max(r_max[i],r[i+1])
        x = sushi[i][0]

        l[-i-2] = l[-i-1] + sushi[-i-1][1] - y + sushi[-i-1][0]
        l_max[-i-2] = max(l_max[-i-1],l[-i-2])
        y = sushi[-i-1][0]
    
    ans = max(r_max[-1], l_max[0])
    for i in range(n-1):
        tmp1 = r[i+1] + l_max[i+1] - sushi[i][0]
        tmp2 = l[i+1] + r_max[i+1] - c + sushi[i+1][0]
        ans = max (ans ,tmp1 ,tmp2 )
    
    print(ans)
  
if __name__=='__main__':
    main()



Measured memory_bytes: 38080
S = input()

if S[0] == S[1] == S[2] == S[3]:
  print('No')
elif S[0] == S[1] and S[2] == S[3]:
  print('Yes')
elif S[0] == S[2] and S[1] == S[3]:
  print('Yes')
elif S[0] == S[3] and S[1] == S[2]:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans = 0;
set<ll> A;
int main() {
	cin >> m;
	x = 0;
	rep(i, m) {
		cin >> a >> b;
		x += a * b;
		ans += b;
	}
  
  k=(x-1)%9+1;
 
	cout << ans - 1 + (x-k)/9 << endl;
}

Measured memory_bytes: 256
def slove():
    import sys
    import heapq
    input = sys.stdin.readline
    ab = [-i for i in list(map(int, input().rstrip('\n').split()))]
    heapq.heapify(ab)
    t = 0
    for i in range(2):
        p = heapq.heappop(ab)
        t -= p
        heapq.heappush(ab, p + 1)
    print(t)


if __name__ == '__main__':
    slove()


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n){
    cin >> a[i];
  }
  int s = 0;
  rep(i,n)
    for(int j=i+1;j<n;j++)
      s += a[i]*a[j];
  cout << s << endl;
}



Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int[] p = in.readIntArray(6);
            int[] q = in.readIntArray(6);
            double min = 1.0;

            for (int i = 0; i < 6; i++) {
                if (q[i] + p[i] == 0) continue;
                double frac = 0;
                for (int j = 0; j < 6; j++) {
                    int g = Math.max(q[i] * p[j], p[i] * q[j]);
                    frac += g;
                }
                frac /= 100.0;
                frac /= (double) (p[i] + q[i]);
                min = Math.min(min, frac);
            }
            out.printf("%.20f\n", min);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int[] readIntArray(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 8912
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, k, n) for (int i = k; i < (int)(n); i++)
#define repd(i, n) for (int i = n-1; i >= 0; i--)
#define rrepd(i, k, n) for (int i = n-1; i >= (int)(k); i--)
#define all(x) (x).begin(),(x).end()
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
//V,Pは大文字i,l,bは小文字
using ll = long long;
using Vi = vector<int>;
using VVi = vector<Vi>;
using Vl = vector<ll>;
using VVl = vector<Vl>;
using Vb = vector<bool>;
using VVb = vector<Vb>;
using P = pair<int,int>;
using Pll = pair<ll, ll>;
const ll mod = 1000000007;
const ll inf = 1000000000000;//10の12乗
long long keta(long long x){
  int y=0;
  while(x!=0){
    y++;
    x/=10;
  }
  return y;
}

int main(void){
    // Your code here!
  int n;
  cin >> n;
  int k=keta(n);
  ll ans=0;
  VVi v(10,vector<int>(10));
  rrep(i,1,10)rrep(j,1,10){
    rrep(l,1,k){
      int x=(n-i*pow(10,l)-j);
      if(x<=0) continue;
      x/=10;x++;
      int z=pow(10,l-1);
      int y=min(z,x);
      v[i][j]+=y;
    }
  }
  rrep(i,1,10){
    v[i][i]++;
  }
  rrep(i,1,10)rrep(j,1,10){
    ans+=v[i][j]*v[j][i];
  }
  if(n<=9) ans=n;
  cout << ans << endl;
  
    
}


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

int main() {
    int n;
    cin >> n;
    vector<int> b(n-1);
    rep(i,n-1) cin >> b[i];
    int ans = b[0]+b[n-2];
    rep(i,n-2){
        ans += min(b[i],b[i+1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
N,K = map(int,input().split())
A = list(map(int,input().split()))

max_len = max(len(bin(K)[2:]),len(bin(max(A))[2:]))
one = [0]*max_len
for a in A:
    for i,b in enumerate(bin(a)[2:].zfill(max_len)):
        if b == "1":
            one[i] += 1
one = one[::-1]
# print(one)
x = 0
for i in range(max_len-1,-1,-1):
    if x+2**i <= K and one[i] < (N+1)//2:
        x += 2**i
# print(x)
ans = 0
for a in A:
    ans += a^x
print(ans)

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

int main(int argc, char *argv[]) {
    int n, l;
    char str[100][100 + 1];
    char tmp[101];

    scanf("%d%d", &n, &l);

    for (int i = 0; i < n; i++) {
        scanf("%s", str[i]);
    }

    for (int j = 0; j < n - 1; j++) {
        for (int i = 0; i < n - 1; i++) {
            if (strcmp(str[i], str[i + 1]) > 0) {
                strcpy(tmp, str[i + 1]);
                strcpy(str[i + 1], str[i]);
                strcpy(str[i], tmp);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%s", str[i]);
    }

    putchar('\n');

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mod 1000000007
ll exp(ll taban, ll us) {
    ll carpan = taban % mod;
    ll temp = us;
    ll res = 1;
    while(temp){
        if(temp % 2) res = (res*carpan) % mod;
        temp /= 2;
        carpan = (carpan*carpan) % mod;
    }
    return res;
}
ll ebob(ll a, ll b){
	if(!a)return b;
	return ebob(b%a, a);
}
ll ekok(ll a, ll b){
	return (a*b)/ebob(a, b);
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	double ar[n+1] = {};
	ar[0] = 1.0;
	for(int i = 0; i < n; i++){
		double x; cin>>x;
		for(int u = i+1; u >= 0; u--){
			if(u == 0){
				ar[0] = ar[0] * (1.0-x);
				continue;
			}
			ar[u] = (x*ar[u-1]+(1.0-x)*ar[u]);
		}
	}
	double ans = 0;
	for(int i = (n+1)/2; i <= n; i++){
		ans += ar[i];
	}
	printf("%.9lf", ans);
}

Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
  // 1行目がinput[0], 2行目がinput[1], …に入る
  input = input.trim().split("\n");
  const N = input[0].split(" ").map((n) => parseInt(n));
  var arr = input.slice(1)
  var AC =0, TLE =0, WA=0, RE =0
  for (i = 0; i < arr.length; i++){
    if (arr[i]== "AC") {
      AC++
    } else if (arr[i]== "TLE") {
      TLE++
    } else if (arr[i]== "WA") {
      WA++
    } else if (arr[i]== "RE") {
      RE++
    }
  }
  ans = `AC x ${AC}\nWA x ${WA}\nTLE x ${TLE}\nRE x ${RE}`





  console.log(ans);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
// Main(require("fs").readFileSync("./input.txt", "utf-8"));


Measured memory_bytes: 38040
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();

		System.out.printf("%d %d %.10f\n", a/b,a%b,(double)a/(double)b);
	}
}



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

int main() {
    int N, T;
    scanf("%d %d", &N, &T);
    int a, m, p, ans;
    p = -1;
    ans = 0;
    m = 1000000005;
    for (int i = 0; i < N; i++) {
        scanf("%d", &a);
        m = min(m, a);
        if (a - m == p) {
          ans++;
        } else if (a - m > p) {
            p = a - m;
            ans = 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

int main(void)
{
	char s[100];
	int i = 0;
	int end = 0;
	int len;
	
	while (fgets(s, 100, stdin) != NULL) {
		end = 0;
		len = strlen(s);
		
		s[len - 1] = '\0';
		
		while (1) {
			i = 0;
			
			while (s[i] != '\0') {
				if (s[i] == 'z') {
					s[i] -= 25;
				}
				
				else if (s[i] == ' ' || s[i] == '.') {
					i++;
					continue;
				}
				
				else {
					s[i]++;
				}
				i++;
			}
			
			i = 0;
			
			while (s[i] != '\0') {
				if (s[i] == 't') {
					i++;
					
					if (s[i] == 'h') {
						i++;
						
						if (s[i] == 'a' || s[i] == 'i') {
							i++;
							
							if (s[i] == 't' && s[i - 1] == 'a') {
								end++;
							}
							
							else if (s[i] == 's' && s[i - 1] == 'i') {
								end++;
							}
						}
						
						else if (s[i] == 'e') {
							end++;
						}
					}
					
				}
				
				if (end == 1) {
					break;
				}
				i++;
			}
			
			if (end == 1) {
				break;
			}
		}
		
		printf("%s\n", s);
	}
	
	return 0;
}

Measured memory_bytes: 524
#include <stdio.h>

long long int gcd( long long int m, long long int n ){	
	while( n > 0 ){
		long long int r = m % n;
		m = n;
		n = r;
	}
	return m;	
}

int main(){
	
	int n, i;
	long long int T[100];
	scanf("%d", &n);
	for( i = 0; i < n; i++ ){
		scanf( "%lld", &(T[i]) );
	}
	
	long long int g;
	long long int result = T[0];
	for( i = 1; i < n; i++ ){
		g = gcd( result, T[i] );
		result *= T[i]/g;
	}
	
	printf("%lld", result);
	
	return 0;
	
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
struct man{
  string name;
  int buy,sell;
  man(string name):name(name){buy=sell=0;}
  bool operator<(const man &m) const{
    return name.compare(m.name)<0;
  } 
};
vector<string> vs;
struct item{
  string name;
  int mi,ma,su,n;
  set<P> ss,sb;
  item(string name):name(name){n=su=0;}
  bool operator<(const item &i) const{
    return name.compare(i.name)<0;
  } 
  P finds(int x,int i){
    P p=P(-1,-1);
    for(set<P>::iterator it=ss.begin();it!=ss.end();++it){
      if(vs[i]==vs[it->second]) continue;
      if(~p.first){
    if(it->first<p.first) p=*it;
    if(it->first==p.first&&it->second<p.second) p=*it;
      }else p=*it;
    }
    if(p.first>x) p=P(-1,-1);
    if(~p.first) ss.erase(p);
    return p;
  }
  P findb(int x,int i){
    P p=P(-1,-1);
    for(set<P>::iterator it=sb.begin();it!=sb.end();++it){
      if(vs[i]==vs[it->second]) continue;
      if(~p.first){
    if(it->first>p.first) p=*it;
    if(it->first==p.first&&it->second<p.second) p=*it;
      }else p=*it;
    }
    if(p.first<x) p=P(-1,-1);
    if(~p.first) sb.erase(p);
    return p;
  }
};
int main(){
  int n;
  while(cin>>n,n){
    int i,j,k;
    map<string,int> mm,mi;
    string name,order,com;
    vector<man> vm;
    vector<item> vi;
    vs.resize(n);
    for(i=0;i<n;i++){
      cin>>name>>order>>com>>k;
      vs[i]=name;
      if(mm.find(name)==mm.end()){
    mm[name]=vm.size();
    vm.push_back(man(name));
      }
      if(mi.find(com)==mi.end()){
    mi[com]=vi.size();
    vi.push_back(item(com));
      }
      if(order=="BUY"){
    P p=vi[mi[com]].finds(k,i);
    if(p.first==-1){
      vi[mi[com]].sb.insert(P(k,i));
      continue;
    }
    j=(k+p.first)/2;
    if(vi[mi[com]].n){
      vi[mi[com]].mi=min(vi[mi[com]].mi,j);
      vi[mi[com]].ma=max(vi[mi[com]].ma,j);
    }else{
      vi[mi[com]].mi=vi[mi[com]].ma=j;
    }
    vm[mm[vs[p.second]]].sell+=j;
    vm[mm[name]].buy+=j;
    vi[mi[com]].su+=j;
    vi[mi[com]].n++;
      }else{
    P p=vi[mi[com]].findb(k,i);
    if(p.first==-1){
      vi[mi[com]].ss.insert(P(k,i));
      continue;
    }
    j=(k+p.first)/2;
    if(vi[mi[com]].n){
      vi[mi[com]].mi=min(vi[mi[com]].mi,j);
      vi[mi[com]].ma=max(vi[mi[com]].ma,j);
    }else{
      vi[mi[com]].mi=vi[mi[com]].ma=j;
    }
    vm[mm[vs[p.second]]].buy+=j;
    vm[mm[name]].sell+=j;
    vi[mi[com]].su+=j;
    vi[mi[com]].n++;
      }
    }
    sort(vm.begin(),vm.end());
    sort(vi.begin(),vi.end());
    for(i=0;i<(int)vi.size();i++){
      if(!vi[i].n) continue;
      cout << vi[i].name << " " << vi[i].mi << " " << (vi[i].su/vi[i].n) << " " << vi[i].ma << endl;
    }
    puts("--");
    for(i=0;i<(int)vm.size();i++){
      cout << vm[i].name << " " << vm[i].buy << " " << vm[i].sell << endl; 
    }
    puts("----------");
  }
  return 0;
}

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

int main() {
  int n,ans = 0;
  cin >> n;
  vector<int>a(n);
  rep(i,0,n){
    cin >> a[i];
    if(i%2 == 0 && a[i]%2 == 1) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
template<typename T> inline void debug(const vector<T> &xs){
#ifdef DEBUG
	pr(xs);
#endif
}

struct UnionFind{
	std::vector<int> par, rnk, cnt;
	UnionFind(int n){
		par.assign(n, 0);
		rnk.assign(n, 0);
		cnt.assign(n, 1);
		for(int i=0; i<n; i++) par[i]=i;
	}
	int root(int i){
		if(par[i]==i) return i;
		return par[i]=root(par[i]);
	}
	void unite(int i, int j){
		int ri = root(i);
		int rj = root(j);
		if(ri==rj) return;

		if(rnk[ri]==rnk[rj]){
			cnt[rj] += cnt[ri];
			par[ri] = rj;
			rnk[rj]++;
		}
		else if(rnk[ri] < rnk[rj]){
			cnt[rj] += cnt[ri];
			par[ri] = rj;
		}
		else{
			cnt[ri] += cnt[rj];
			par[rj] = ri;
		}
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	int count(int i){
		return cnt[root(i)];
	}
};

int main(){
	int N, K, L;
	cin >> N >> K >> L;
	UnionFind uf1(N), uf2(N);
	for(int i=0; i<K; i++){
		int p, q;
		cin >> p >> q;
		uf1.unite(p-1, q-1);
	}
	for(int i=0; i<L; i++){
		int r, s;
		cin >> r >> s;
		uf2.unite(r-1, s-1);
	}

	vector<pair<pair<int, int>, int>> ps;
	for(int i=0; i<N; i++){
		ps.push_back({{uf1.root(i), uf2.root(i)}, i});
	}
	sort(ps.begin(), ps.end());
	UnionFind uf3(N);
	for(int i=0; i<N-1; i++){
		if(ps[i].first==ps[i+1].first) uf3.unite(ps[i].second, ps[i+1].second);
	}

	for(int i=0; i<N; i++){
		cout << uf3.count(i) << (i==N-1?"\n":" ");
	}

	return 0;
}


Measured memory_bytes: 9968
#include <bits/stdc++.h>
//#pragma GCC optimize "-O3"
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned short us;
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll infll=(1ull<<63)-1;
const int inf=(1ull<<31)-1;
string a,b;
int s=0;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(18);
	cin>>a>>b;
	for (int i=0;i<3;i++)
		s+=(a[i]==b[i])?1:0;
	cout<<s;
	return 0;
}

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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, c; cin>>n>>m>>c;
    vector<int> b(m);
    REP(i,m) cin>>b[i];
    int code = 0;
    int ans = 0;
    int in; 
    REP(i,n){
        REP(j,m){
            cin>>in;
            code += (in*b[j]);
        }
        if ((code + c) > 0) {
            ans++; 
        }
        code = 0;
    }
    print(ans);
    return 0;
}

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

using namespace std;

#ifndef ONLINE_JUDGE
  #define pr_debug(...) do { printf("DEBUG: line %d: %s: ", __LINE__, __PRETTY_FUNCTION__); printf(__VA_ARGS__); } while(0)
  #define pr_vars(...) do { pr_debug(" "); pr_var(split(#__VA_ARGS__, ',').begin(), __VA_ARGS__); } while(0)
#else
  __attribute__ ((constructor)) static void fast_cin() { ios_base::sync_with_stdio(false); cin.tie(0); }
  #define pr_debug(...) do { } while(0)
  #define pr_vars(...) do { } while(0)
#endif /* ONLINE_JUDGE */

using ll = int64_t;
using ull = uint64_t;

template<typename T> ostream &operator<< (ostream &fout, const vector<T> &vec)
{ for (const auto &el : vec) fout << el << ' '; return fout; }

template<typename T> istream &operator>> (istream &fin, vector<T> &vec)
{ for (size_t i = 0; i < vec.size(); i++) fin >> vec[i]; return fin; }

vector<string> split(const string &s, char c) { vector<string> v; ull st = 0, fn = 0, lvl = 0;
for ( ; fn < s.size(); fn++ ) { if (s[fn] == c && lvl == 0) { v.push_back(s.substr(st, fn - st)); st = fn + 1; }
if (s[fn] == '(') { lvl++; } if (s[fn] == ')') { lvl--; } } v.push_back(s.substr(st, fn - st)); return v; }

void pr_var(vector<string>::iterator it) { (void) it; cout << endl; }
template<typename T, typename... Args> void pr_var(vector<string>::iterator it, T a, Args... args)
{ cout << *it << "=" << a << "  "; pr_var(++it, args...); }

ll div_ceil(ll n, ll d) { ll res = n / d; if (res >= 0) res += n % d ? 1 : 0; return res; }
ll gcd(ll a, ll b) { a = llabs(a); b = llabs(b); while (a && b) a > b ? a %= b : b %= a; return a + b; }
ll lcm(ll a, ll b) { ll c = gcd(a, b); return c == 0 ? 0 : llabs(a / c * b); }

#define setp(a) fixed << setprecision(a)
const double PI = acos(-1.0);
constexpr double EPS = 1e-9;
constexpr double INF = 2e18;

using mp = pair<ll, ll>;
using mt = tuple<ll, ll, ll>;    // unpack: tie(ll, ll, ll) = mt;

constexpr ll MAX = 1e5 + 5;

const int mod = 1e9 + 7;

// the last found prime will be 9999991
constexpr ll sieve_max_size = 1e7 + 10;
static bitset<sieve_max_size> bs;
static ll sieve_size;
static vector<int> primes;

// creates list of primes in [0..upperbound]
void sieve(ll upperbound) {
    sieve_size = upperbound + 1;
    bs.set();
    bs[0] = bs[1] = 0;
    for (ll i = 2; i <= sieve_size; i++) {
        if (bs[i] == 0) continue;
        for (ll j = i * i; j <= sieve_size; j += i)
            bs[j] = 0;
        primes.push_back((int)i);
    }
}

// deterministic prime tester for N <= sieve_size ** 2
bool isPrime(ll N) {
    if (N <= sieve_size) return bs[N];
    for (ull i = 0; i < primes.size(); i++)
        if (N % primes[i] == 0) return false;
    return true;
}

static vector<int> v;

int main()
{
    sieve(1e5);
    for (ull i = 0; i < primes.size(); i++) {
        if (isPrime((primes[i] + 1) / 2))
            v.push_back(primes[i]);
    }
    //pr_vars(v.size());

    ll q; cin >> q;
    while (q--) {
        ll l, r; cin >> l >> r;
        ll res = 0;
        for (auto i: v)
            if (i >= l && i <= r)
                res++;
        cout << res << '\n';
    }

    return 0;
}


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

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

int kai[200010];

void setkai(int n) {
	kai[0] = 1;
	for (int i = 1; i <= min((int)200000, n); i++) {
		kai[i] = kai[i - 1] * i;
		kai[i] %= MOD;
	}
}

int perm(int n, int r) {
	if (n < 0 || r < 0 || n < r) return 0;
	return kai[n] * modinv(kai[n - r], MOD) % MOD;
}

int comb(int n, int r) {
	if (n < 0 || r < 0 || n < r) return 0;
	return perm(n, r) * modinv(kai[r], MOD) % MOD;
}

signed main() {
	int n, p, ki = 0, gu = 0, ans = 0;
	cin >> n >> p;
	rep(i, n) {
		int a;
		cin >> a;
		if (a % 2 == 0) gu++;
		else ki++;
	}
	int cnt = 1;
	rep(i, gu) {
		cnt *= 2;
	}
	setkai(51);
	rep(i, ki + 1) {
		if (i % 2 == p) {
			ans += cnt * comb(ki, i);
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String args[] ) throws Exception {
        Scanner ob=new Scanner(System.in);
        int n=ob.nextInt();
        int a[]=new int[n];
        for(int i=0;i<n;i++)a[i]=ob.nextInt();
        int dp[]=new int[n];
        dp[0]=0;
        dp[1]=Math.abs(a[1]-a[0]);
        if(n>2)
        dp[2]=Math.min(Math.abs(a[2]-a[1])+dp[1],Math.abs(a[2]-a[0])+dp[0]);
        
        //System.out.println(Arrays.toString(a));
        //System.out.println(Arrays.toString(dp));
        
        for(int i=3;i<n;i++)
        dp[i]=Math.min(dp[i-2]+Math.abs(a[i-2]-a[i]),dp[i-1]+Math.abs(a[i]-a[i-1]));
        System.out.println(dp[n-1]);
        
        //System.out.println(Arrays.toString(dp));
        //System.out.println("Hello World!");
    }
}


Measured memory_bytes: 51772
#include <stdio.h>

int main(void)
{
    int n, i, x;
    scanf("%d", &n);

    for(i = 3; i <= n; i++){
        if(i % 3 == 0){
            printf(" %d", i);
        }else{
            x = i;
            while(x){
                if(x % 10 == 3){
                    printf(" %d", i);
                    break;
                }else{
                    x /= 10;
                }
            }
        }
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 2052
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();  
        
        int K = (A + B)/2;
        if((A+B) % 2 == 0){
            System.out.println(K);
        }else{
            System.out.println("IMPOSSIBLE");
        }
    }
}   

Measured memory_bytes: 21844