akhauriyash/Code-Regression huggingface dataset:
class BinarySearchTree
  class Node
    attr_reader :key
    attr_accessor :parent, :left, :right

    def initialize(key, parent)
      @key = key
      @parent = parent
    end
  end

  def insert(key)
    parent = nil
    current = @root
    while current
      parent = current
      if key < current.key
        current = current.left
      else
        current = current.right
      end
    end

    new_node = Node.new(key, parent)
    if !parent
      @root = new_node
    elsif key < parent.key
      parent.left = new_node
    else
      parent.right = new_node
    end

    return self
  end

  def find(key)
    current = @root
    while current && current.key != key
      if key < current.key
        current = current.left
      else
        current = current.right
      end
    end
    return current
  end

  def delete(key)
    target = find(key)
    return nil unless target
    delete_helper(target)
  end

  def keys_inorder
    inorder_helper(@root)
  end

  def keys_preorder
    preorder_helper(@root)
  end

  private
  def copy_node(node, new_key=nil)
    new_key ||= node.key
    copied = Node.new(new_key, node.parent)
    copied.left = node.left
    copied.right = node.right
    return copied
  end

  def replace(node, new_node)
    parent = node.parent
    new_node.parent = parent if new_node

    if !parent
      @root = new_node
    elsif parent.left && parent.left.key == node.key
      parent.left = new_node
    else
      parent.right = new_node
    end
    return node
  end

  def delete_helper(node)
    if node.left && node.right
      next_node_index = inorder_helper(node.right).first
      next_node = find(next_node_index)

      copied = copy_node(node, next_node.key)
      node.right.parent = copied
      node.left.parent = copied
      replace(node, copied)
      delete_helper(next_node)
      return node
    end
    return replace(node, node.left) if node.left
    return replace(node, node.right) if node.right
    replace(node, nil)
  end

  def inorder_helper(node)
    return [] unless node
    result = []
    result.concat(inorder_helper(node.left))
    result.push(node.key)
    result.concat(inorder_helper(node.right))
  end

  def preorder_helper(node)
    return [] unless node
    result = [node.key]
    result.concat(preorder_helper(node.left))
    result.concat(preorder_helper(node.right))
  end
end

tree = BinarySearchTree.new
n = gets.chomp.to_i
n.times do
  command, param = gets.chomp.split[0..1]
  if command == "insert"
    tree.insert(param.to_i)
  elsif command == "find"
    puts (tree.find(param.to_i) ? "yes" : "no")
  elsif command == "delete"
    tree.delete(param.to_i)
  elsif command == "print"
    puts " #{tree.keys_inorder.join(" ")}"
    puts " #{tree.keys_preorder.join(" ")}"
  else
    raise "Unexpected input #{command}, #{param}"
  end
end

Measured memory_bytes: 97900
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

#define ll long long
#define pb push_back

ll MAX(ll a, ll b) {

	if (a > b)return a;
	else return b;

}
ll MIN(ll a, ll b) {

	if (a < b)return a;
	else return b;

}
ll powsur(ll a, ll b, ll p) {

	if (b == 0) {

		return 1;

	}
	else if (b % 2 == 0) {

		ll d = powsur(a, b / 2, p);
		return ((d%p)*(d%p)) % p;

	}
	else {

		return ((a%p)*powsur(a, b - 1, p) % p) % p;

	}

}//pは素数,aのb乗をpで割った余り
ll CMOD(ll n, ll r, ll p) {

	ll a = 1, b = 1, c = 1, re;
	for (int i = 1; i <= n; i++) {

		a *= i;
		a = a%p;

	}
	for (int i = 1; i <= r; i++) {

		b *= i;
		b = b%p;

	}
	for (int i = 1; i <= n - r; i++) {

		c *= i;
		c = c%p;

	}
	b = powsur(b, p - 2, p);
	c = powsur(c, p - 2, p);
	re = ((a%p)*(b%p)) % p;
	re = ((re%p)*c%p) % p;

	return re;

}//pは素数,(nCr)%p
ll gcd(ll a, ll b) {

	if (a < b) {

		ll tmp = a;
		a = b;
		b = tmp;

	}
	if (a%b == 0)return b;
	return gcd(b, a%b);

}//最大公約数
ll lcm(ll a, ll b) {

	return a / gcd(a, b)*b;

}//最小公倍数

bool check_continue(int P,vector<int> V){
	if(P!=0)return true;
	int cnt=0;
	for(int i=0;i<V.size();i++){
		if(V[i]>0)cnt++;
	}
	if(cnt==1)return false;
	return true;
}

int main() {
	
	while(1){
		int N,M;
		cin>>N>>M;
		if(N==0&&M==0)break;
		int t_sum=0,h_sum=0;
		vector<int> T,H;
		for(int i=0;i<N;i++){
			int t;
			cin>>t;
			T.pb(t);
			t_sum+=t;
		}
		for(int i=0;i<M;i++){
			int h;
			cin>>h;
			H.pb(h);
			h_sum+=h;
		}
		bool flag=false;
		int ttoh=1000,htot=1000;
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(t_sum-T[i]+H[j]==h_sum-H[j]+T[i]){
					flag=true;
					if(T[i]+H[j]<ttoh+htot){
						ttoh=T[i];
						htot=H[j];
					}
				}
			}
		}
		if(flag)cout<<ttoh<<" "<<htot<<endl;
		else cout<<-1<<endl;
	}

	return 0;
}


Measured memory_bytes: 3000
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int n, mi, ma;
    while (cin >> n >> mi >> ma && n){
        int ans = 0, x = 0;
        VI p(n);
        REP(i,n) cin >> p[i];
        FOR(i,mi-1,ma-1){
            int y = p[i] - p[i+1];
            if (y >= x){
                ans = i+1;
                x = y;
            }
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 3068
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll h, w;
    cin>>h>>w;
    if (h % 3 == 0 || w % 3 == 0) {
        cout<<0<<endl;
        return 0;
    }

    ll ans = LINF;
    chmin(ans, h * ((w + 2) / 3 - w / 3));
    chmin(ans, w * ((h + 2) / 3 - h / 3));
    rep(i, h) {
        ll s1 = w * i;
        ll s2 = (h - i) * (w / 2);
        ll s3 = (h - i) * ((w + 1) / 2);
        chmin(ans, max(abs(s1 - s2), abs(s1 - s3)));
    }
    rep(i, w) {
        ll s1 = h * i;
        ll s2 = (w - i) * (h / 2);
        ll s3 = (w - i) * ((h + 1) / 2);
        chmin(ans, max(abs(s1 - s2), abs(s1 - s3)));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()


vector<string> p={"ABC","ARC","AGC"};

int main(){
    int n;; cin>>n;;
    if(n<1200){
        cout<<p[0]<<endl;
        return 0;
    }
    if(n<2800){
        cout<<p[1]<<endl;
        return 0;
    }
    cout<<p[2]<<endl;
    return 0;
}

Measured memory_bytes: 256
def judge(A,B,C,X):
    count = 0
    for n in range(A+1):
        for l in range(B+1):
            for m in range(C+1):
                if X == 500*n+100*l+50*m:
                    count += 1
    print(count)
    
A = int(input())
B = int(input())
C = int(input())
X = int(input())
judge(A,B,C,X)

Measured memory_bytes: 3064
// "header" {{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <tuple>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int long long
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

inline double sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
// }}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	rep(i,n){
		cin >> h[i];
	}
	vector<int> dp(n);
	reps(i,n-1){
		int minv = INF;
		for(int j = i-1;j >= i-k && j >= 0;--j){
			minv = min(minv,abs(h[i]-h[j]) + dp[j]);
		}
		dp[i] = minv;
	}
	cout << dp[n-1] << '\n';
	return 0;	
}


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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  int n;
  const int max_n = 3 * 1e3;
  int l[max_n + 1];

  cin >> n;
  for(int i = 0; i < n; i++) cin >> l[i];
  sort(l, l+n);

  long long ans = 0;
  for(int i = 0; i < n - 2; i++){
    for(int j = i + 1; j < n - 1; j++){
      for(int k = n - 1; k > j; k--){
        if(l[i] + l[j] > l[k]){
          ans += k - j;
          break;
        }
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    string s;
    cin >> s;
    rep(i,s.size()){
        cout << "x";
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define pint pair<int,int>
#define SEG_LEN (1 << 18)
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
int main(){
  ll a,b,c,k;
  cin >> a >> b >> c >> k;
  ll ans = 0;
  if(a >= k)cout << k << endl;
  else{
    ans += a;
    k -= a;
    if(b >= k)cout << ans << endl;
    else{
      k -= b;
      k = max((ll)0,k);
      cout << ans - k << endl;
    }
  }
  return 0;
}
 

Measured memory_bytes: 3620
#include<iostream>
#include<iomanip>

using namespace std;
using ll=long long;

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

int main(){
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  std::cout << std::fixed << std::setprecision(15);  // 小数を10進数表示
  int r;
  cin>>r;
  r<1200 ? cout<<"ABC"<<endl : r<2800 ? cout<<"ARC"<<endl : cout<<"AGC"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int Pflg[1001][1001];
int main(void)
{
	int c,n;
	int d;
	int dr,dc;
	int i,j;
	int cnt1,cnt2;
	char P[1001];
	cin>>c>>n;
	for(i=1;i<=n;i++){
		cin>>P;
		for(j=0;j<n;j++){
			Pflg[i][j+1]=P[j]-48;
		}
	}
	cnt1=0; cnt2=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(Pflg[i][j]==1){
				if(n/2>=j&&Pflg[i][j]!=Pflg[i][j+((n/2-j)*2)+1]) cnt2++;
				else if(n/2<j&&Pflg[i][j]!=Pflg[i][j-((j-n/2-1)*2)-1]) cnt2++;
				
				if(n/2>=i&&Pflg[i][j]!=Pflg[i+((n/2-i)*2)+1][j]) cnt2++;
				else if(n/2<j&&Pflg[i][j]!=Pflg[i][j-((j-n/2-1)*2)-1]) cnt2++;
			}
		}
	}
	
	if(cnt2==0) cnt1++;
//	cout<<"cnt2="<<cnt2<<endl;
	for(i=0;i<c-1;i++){
		cin>>d;
		for(j=0;j<d;j++){
			cin>>dr>>dc;
			if(Pflg[dr][dc]==0) Pflg[dr][dc]=1;
			else Pflg[dr][dc]=0;
			
			if(n/2>=dc){
				if(Pflg[dr][dc]!=Pflg[dr][dc+((n/2-dc)*2)+1]) cnt2++;
				else cnt2--;
			}
			else if(n/2<dc){
				if(Pflg[dr][dc]!=Pflg[dr][dc-((dc-n/2-1)*2)-1]) cnt2++;
				else cnt2--;
			}
			
			if(n/2>=dc){
				if(Pflg[dr][dc]!=Pflg[dr+((n/2-dr)*2)+1][dc]) cnt2++;
				else cnt2--;
			}
			else if(n/2<dc){
				if(Pflg[dr][dc]!=Pflg[dr-((dr-n/2-1)*2)-1][dc]) cnt2++;
				else cnt2--;
			}
		}
		if(cnt2==0){
			cnt1++;
//			cout<<"i="<<i+2<<endl;
		}
	}
	cout<<cnt1<<endl;
	
	return 0;
}


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

int main() {
  int A, B; cin >> A >> B;
  int ans = 0;
  for (int i = A; i <= B; ++i) {
    string s = to_string(i);
    ans += (s[0] == s[4] && s[1] == s[3]);
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

#define int_ int64_t
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define lb long double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

ll n;

int main()
{
    scanf("%lld",&n);
    if (n==3) {
        printf("2 5 63\n");
    } else if (n<=15002) {
        printf("3 9 ");
        n-=2;
        ll rem=n%3;
        for (ll i=1;i<=n-rem;i++) {
            printf("%lld ",i*2);
        }
        if (rem==1) {
            printf("%lld\n",(n+2)*2);
        } else if (rem==2) {
            printf("%lld %lld\n",(n-1)*2,n*2);
        } else {
            printf("\n");
        }
    } else {
        for (ll i=1;i<15000;i++) {
            printf("%lld ",i*2);
            n--;
        }
        if (n%2==1) {
            printf("30000 ");
            n--;
        }
        for (ll i=1;i<=n;i++) {
            printf("%lld ",3*(2*i-1));
        }
        printf("\n");
    }
}

Measured memory_bytes: 384
#include<algorithm>//sort(all(変数),greater<型名>())　で降順に
#include<cmath>//切り上げceil(値)
#include<deque>
#include<iomanip>//setprecision(数字)
#include<iostream>
#include<list>
#include<map>
#include<numeric> //xとyの最大公約数は__gcd(x,y),xとyの最小公倍数は(x*y)/__gcd
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>

#include<bits/stdc++.h>
#include<cstdio>
#include<cstdlib>
#include<tuple>
#include<utility>
#define rep(i,n) for(ll i=0; i<n; i++)
#define vll vector<ll>
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  vi x(5);
  rep(i,5){
    cin >> x[i];
  }
  int max = 0, ans = 0;
  rep(i,5){
    if(x[i]%10 != 0){
      if(max < 10-x[i]%10){
        max = 10-x[i]%10;
      }
      x[i] /= 10;
      x[i]++;
      x[i] *= 10;
    }
    ans += x[i];
  }
  cout << ans-max;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <tuple>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

string LongestCommonSubsequence(string s1, string s2) {
    int N = (int) s1.size();
    int M = (int) s2.size();
    vector < vector < int > > dp(N + 1, vector < int > (M + 1, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (s1[i] == s2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }
    string ret;
    int i = N, j = M;
    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i - 1][j]) {
            i--;
        } else if (dp[i][j] == dp[i][j - 1]) {
            j--;
        } else {
            i--;
            j--;
            ret.push_back(s1[i]);
        }
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

int main ()
{
    string s,t;
    cin >> s >> t;
    cout << LongestCommonSubsequence(s, t) << endl;
    return 0;
}


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

nums = list(map(int, input().split()))

def insertionSort(A, N):
    for i in range(1, N):
        show(A)
        v = A[i]
        j = i-1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j = j-1

        A[j+1] = v

    show(A)

def show(lst):
    print(*lst)


insertionSort(nums, N)


Measured memory_bytes: 5980
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc =new Scanner(System.in);
        int[] a = new int[1000000];
        a[0] = sc.nextInt();        
        int ans = 0;
  
        //計算処理          
        for(int i = 1; i <1000000; i++){
           if(a[i-1] % 2 == 0){
               a[i] = a[i-1]/2;
           }else if(a[i-1] % 2 == 1){
               a[i] = 3*a[i-1] + 1;
           }

            //評価
           for(int j = 0; j < i; j++){
               if(a[j] == a[i]){
                   ans = i+1;
               }
            }
            if(ans != 0)break;
       }
       
       System.out.println(ans);
    }
}


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

int main(){
    int N,tmp,Bob = 0,Alice = 0;
    cin >> N;
    int a[N];
    
    for(int i = 0; i < N; ++i){
        cin >> a[i];
    }
    for(int i = 1; i < N; ++i){
        tmp = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] < tmp){
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = tmp;
    }
    
    
    for(int i = 0; i < N; ++i){
        if(i % 2 == 0){
            Alice += a[i];
        }else{
            Bob += a[i];
        }
    }
    
    cout << Alice - Bob;
}


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

using namespace std;

using ll = long long;
using vl = vector<long long>;
using vi = vector<int>;
using vvl = vector<vl>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

int n, m;
vvi adj;
vi incoming_cnt, dist;

void doofus(int node, int dis)
{
    incoming_cnt[node]--;
    dist[node] = max(dist[node], dis);
    if (!incoming_cnt[node])
    {
        for (auto &e : adj[node])
            doofus(e, dist[node] + 1);
    }
}

int main()
{
    cin >> n >> m;
    adj = vvi(n + 1, vi());
    incoming_cnt = vi(n + 1, 0);
    dist = vi(n + 1, 0);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        incoming_cnt[y]++;
    }
    incoming_cnt[0] = 1;
    for (int i = 1; i < n + 1; i++)
    {
        if (!incoming_cnt[i])
        {
            adj[0].push_back(i);
            incoming_cnt[i]++;
        }
    }
    doofus(0, 0);
    cout << *max_element(dist.begin(), dist.end()) - 1;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
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; }
const ll MOD = 1e9+7;

ll A[300100];

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

    map<ll, ll> B;
    REP(i,N){
        ll a = A[i];
        REP(b,61){
            if((a >> b) & 1) B[b]++;
        }
    }

    ll ans = 0;
    REP(i,N){
        ll a = A[i];
        REP(b,61){
            ll tmp;
            if((a >> b) & 1) {
                B[b]--;
                tmp = (1LL << b) % MOD * (N-(i+1)-B[b]) % MOD;
            }
            else{
                tmp = (1LL << b) % MOD * B[b] % MOD;
            }
            tmp %= MOD;
            ans += tmp;
            ans %= MOD;
        }
        //cout << ans << endl;
    }

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


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

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

    int N,M; cin >> N >> M;

    vector<P> G[1005];

    for (int i = 0;i < M;i++){
        ll a,b,c; cin >> a >> b >> c;
        G[a].push_back(P(b,-c));
    }

    queue<ll> que;
    ll dist[1005]; fill(dist,dist+N+3,LLONG_MAX);

    dist[1] = 0;
    bool flagN = false;
    ll cnt = 1;

    que.push(1);

    while(que.size()){
        cnt++;
        if(cnt >= N*4) break;
        int from = que.front(); que.pop();
        //cout << from << endl;
        if(from == N){
            if(flagN && cnt > N*2){
                cout << "inf" << endl;
                return 0;
            }
            flagN = true;
        }
        for (int i = 0;i < G[from].size();i++){
            int to = G[from][i].first;
            ll cost  = G[from][i].second;
            if(dist[from]+cost < dist[to]){
                dist[to] = dist[from]+cost;
                que.push(to);
            }
        }
    }

    cout << -dist[N] << endl;

    return 0;

}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int, int>

const int N = 1e5 + 10;
vector<vector<pii>> g(N);
vector<int> dist(N, 0);
vector<bool> visited(N, false);

void dfs(int v, int par, int w) {
    visited[v] = true;
    dist[v] = dist[par] + w;
    for(auto &u : g[v]) {
        if(!visited[u.fi]) {
            dfs(u.fi, v, u.se);
        }
    }
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    int q, k;
    cin >> q >> k;
    dfs(k, 0, 0);
    for(int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        cout << dist[x] + dist[y] << "\n";
    }
}

Measured memory_bytes: 14336
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll a,b,k;cin>>a>>b>>k;
    bool abc=0;
    while(k--){
        if(abc==0){
            abc=1;
            if(a%2!=0)
                a--;
            a/=2;
            b+=a;
        }
        else{
            abc=0;
            if(b%2!=0)
                b--;
            b/=2;
            a+=b;
        }
    }
    cout<<a<<" "<<b<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------









Measured memory_bytes: 384
#include<stdio.h>
int binarySearch(int);
int s[10000000],n;
int main(){
  int i,q,judge,count=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&judge);
    if(binarySearch(judge)) count++;
  }
  printf("%d\n",count);
  return 0;
}

int binarySearch(int key){
  int l=0,r=n,mid;
  while(l<r){
    mid=(l+r)/2;
    if(key==s[mid]) return 1;
    if(key>s[mid]) l=mid+1;
    else if(key<s[mid]) r=mid;
  }
  return 0;
}



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

int N;
double x[105], y[105];
int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%lf %lf", &x[i], &y[i]);
	double atas = 0.0, bawah = 0.0;
	for(int i = 0; i < N; i++){
		atas += (x[i]*y[(i-1+N)%N]);
		bawah += (x[i]*y[(i+1)%N]);
	}
	printf("%.1lf\n", 0.5*(bawah-atas));
	return 0;
}

Measured memory_bytes: 3232
#include <bits/stdc++.h>
#define dbug(x) cout<<#x<<"="<<x<<endl
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
int n,d,ans=100,vis[21],cnt;
int main() {
	//freopen("1.txt","r",stdin);
	read(n); read(d);
	for (int t=0;t<(1<<n);t++) {
		memset(vis,0,sizeof(vis));
		cnt=0; int flag=1;
		for (int i=1;i<=n;i++)
			if (t&(1<<(i-1))) cnt++;
		if (cnt>ans) continue;
		for (int i=1;i<=n;i++)
			if (t&(1<<(i-1)))
				for (int j=max(1,i-d);j<=min(n,i+d);j++) vis[j]=1;
		for (int i=1;i<=n;i++)
			if (!vis[i]) { flag=0; break; }
		if (flag) ans=min(ans,cnt);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
/*AtCorder Beginner Contest137 B*/

int main(void)
{
  int K,X;
  int end,begin;
  int i;

  scanf("%d%d",&K,&X );
  begin=X-(K-1);
  end  =X+(K-1);

  for(i=begin;i<=end;i++){
    printf("%d ",i);
  }
  return 0;
}


Measured memory_bytes: 128
let rec gcd a b =
    if a == b then a 
    else if a < b then gcd a (b-a)
    else if a > b then gcd (a-b) b
    else 0

let lcm a b =
     (a * b) / (gcd a b)

let () =
    try
        while true do
            let a, b = Scanf.scanf "%d %d\n" (fun a b -> a, b) in
            Printf.printf "%d %d\n" (gcd a b) (lcm a b)
        done
    with
        End_of_file -> ()

Measured memory_bytes: 2320
#!/usr/bin/env python3
#ABC147 A

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a1,a2,a3 = LI()

if a1+a2+a3 >= 22:
    print('bust')
else:
    print('win')
    

Measured memory_bytes: 38384
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;

void solve() {
    int b, c;
    cin >> b >> c;
    int h, m;
    cin >> h >> m;
    int totmin = h * 60 + m;
    double angh = totmin * 0.5;
    double angm = m * 6;
    double ans = abs(angh - angm);
    if (ans > 180)
        ans = 360 - ans;
    ans = ans / 360 * 2 * acos(-1);
    double a = b * b + c * c - cos(ans) * 2 * b * c;
    cout << fixed << setprecision(11) << sqrt(a);
}

signed main() {
    start;
    while (T--)
        solve();
    return 0;
}

Measured memory_bytes: 4204
#!/usr/bin/ruby
#encoding: utf-8

MOD = 1e9.to_i + 7

#input 
n,k = gets.split.map(&:to_i)

(1..k).each do |i|
  a = Array.new(k-1).combination(i-1).size%MOD
  b = Array.new(n-k+1).combination(i).size%MOD
  puts (a*b)%MOD
end

Measured memory_bytes: 3508
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define K 10000

int main(){
  int *a,*b;
  int n;
  int c[K+1]={};
  cin>>n;
  n++;
  a=(int*)malloc(sizeof(int)*n);
  b=(int*)malloc(sizeof(int)*n);

  for(int i=1;i<n;i++){
    cin>>a[i];
    c[a[i]]++;
  }
  for(int i=1;i<K;i++)c[i]+=c[i-1];

  for(int i=1;i<n;i++){
    b[c[a[i]]]=a[i];
    c[a[i]]--;
  }

  for(int i=1;i<n-1;i++)
    cout<<b[i]<<' ';

  cout<<b[n-1]<<endl;

  return 0;
}

Measured memory_bytes: 16856
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if ((a * b) % 2 == 0) System.out.println("Even");
    else System.out.println("Odd");
  }
}


Measured memory_bytes: 20820
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂
                   
                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            
 
 */ 
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long 
#define mod 1000000007
#define inf 100000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}
#define ar array
const ll maxN=1e5+5 , N=1e3+5;
ll n ,m ;
ll a[maxN];
ll dp[maxN];
void solve(){
	cin>> n ;
	for(ll i=0;i<n ;i++)cin>>a[i];
	dp[0]=0,dp[1]=abs(a[1]-a[0]);
	for(ll i=2;i<n ;i++){
		dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
	}
	// for(ll i=0;i<n;i++)cerr<<dp[i]<<" ";
	cout<<dp[n-1]<<endl;
}
int main(){
	//mahakal(),fast;
	ll t=1;
	// cin>> t ;
	while(t--)solve();

	return 0;
}

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

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int num, candy;
    cin >> num >> candy;
    int limit[num];
    memset(limit, 0, num*sizeof(int));
    for (int i = 0; i < num; i++)
        cin >> limit[i];

    sort(limit, limit+num);

    int temp = candy, count = 0;
    for (int i = 0; i < num; i++)
        if (i == num-1){
            if(temp == limit[i])
                count ++;
            else
                break;
        }
        else{
            if (temp >= limit[i]){
                temp -= limit[i];
                count ++;
            }
        }

    cout << count << "\n";



}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m,x;
  cin >> n >> m >> x;
  int a=0,b=0;
  for(int i=0;i<m;i++){
    cin >> n;
    if(n>x){
      a++;
    }else{
      b++;
    }
  }
  cout << min(a,b) << endl;
}

Measured memory_bytes: 256
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

    for i in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        e[a].append([b,c])
        e[b].append([a,-c])


    dis = [float("INF")]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append(x)
        while q:
            now = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == float("INF"):
                    dis[nex] = dis[now]+d
                    q.append(nex)
                else:
                    if dis[nex] != dis[now]+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == float("INF"):
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

Measured memory_bytes: 98976
import scala.io.StdIn.readLine

object Main {
  def main(args: Array[String]): Unit = {
    val Array(len, width) = readLine.split(" ").map { s => s.toInt }
    val area = len * width
    val perimeter = len * 2 + width * 2
    println(area + " " + perimeter)
  }
}

Measured memory_bytes: 43812
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    map<string, int> mp;
    for (int i=0; i<n; i++) {
        string s;
        cin >> s;
        mp[s]++;
    }
    int maxNum = 0;
    vector<string> v;
    for (auto itr=mp.begin(); itr!=mp.end(); itr++) {
        if (itr->second > maxNum) {
            v.clear();
            v.push_back(itr->first);
            maxNum = itr->second;
        } else if (itr->second == maxNum) {
            v.push_back(itr->first);
        }
    }
    sort(v.begin(), v.end());
    for (int i=0; i<v.size(); i++) {
        cout << v[i] << endl;
    }
}

Measured memory_bytes: 27272
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] height = new int[10];
    for (int i = 0; i < 10; i++) {
      height[i] = sc.nextInt();
    }
    Arrays.sort(height);
    for (int i = 9; i >= 7; i--) {
      System.out.println(height[i]);
    }
  }
}


Measured memory_bytes: 26048
// Author: Ishaan Gupta

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
#define endl '\n'
#define pb push_back
#define DEB(x) cout << '>' << #x << ':' << x << endl;
inline ll add(ll a,ll b){return (a%MOD+b%MOD)%MOD;}
inline ll sub(ll a,ll b){return (a%MOD-b%MOD+MOD)%MOD;}
inline ll mult(ll a,ll b){return ((a%MOD)*(b%MOD))%MOD;}
inline ll power(ll a,ll b){a%=MOD;ll r=1;while(b){if(b&1)r=mult(r,a);a=mult(a,a);b>>=1;}return r;}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed;
#ifdef IG_PC
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    ll n;
    cin >> n;
    vector<ll>dp(3);
    vector<ll>new_dp(3);
    for(ll day = 0; day < n; ++day)
    {
        vector<ll>c(3);
        for(ll &i : c)
        {
            cin >> i;
        }
        for(ll i=0;i<3;++i)
        {
            for(ll j=0;j<3;++j)
            {
                if(i!=j)
                {
                    new_dp[j] = max(new_dp[j],dp[i]+c[j]);
                }
            }
        }
        dp = new_dp;
    }
    cout<<max({dp[0],dp[1],dp[2]});

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline
import numpy as np

D = int(input())
c = np.array(input().split(), dtype=np.int32)
s = np.array([input().split() for _ in range(D)], dtype=np.int32)
last = np.zeros(26, dtype=np.int32)
# print(s)
# print(s.shape)

ans = []
point = 0
for i in range(D):
    down = (i+1-last)*c
    loss = down * 3 + s[i,:]
    idx = np.argmax(loss)
    ans.append(idx+1)
    point += s[i, idx] - down.sum()
    last[idx] = i+1
    # print(loss)

for i in range(D):
    print(ans[i])

Measured memory_bytes: 27568
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    vstr s(3);
    rep(i, 3) cin >> s[i];

    string ans = "";
    rep(i, 3) {
        ans += s[i][0]-'a'+'A';
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;
#define MODSIZE 1000000007
// priority_queue<int, vector<int>, greater<int> > PQ; // 昇順PQ
priority_queue<int> PQ;

int main(){
  int h1,m1,h2,m2,k;
  int h,m;
  scanf("%d %d %d %d %d", &h1, &m1, &h2, &m2, &k);

  h = h2 - h1;
  m = m2 - m1;

  printf("%d\n", h*60 + m - k);

  return 0;
}


Measured memory_bytes: 3828
char T[10][10000];
main(Y,X,i,j,r,s,s0,y){
	for(;scanf("%d%d",&Y,&X),Y;printf("%d\n",r)){
		for(j=0;j<Y;j++)for(i=0;i<X;i++)scanf("%hhd",T[j]+i);
		for(r=y=0;y<1<<Y;y++){
			for(s=i=0;i<X;i++){
				for(s0=j=0;j<Y;j++)s0+=(y>>j&1)==T[j][i];
				s+=Y-s0>s0?Y-s0:s0;
			}
			if(r<s)r=s;
		}
	}
exit(0);}

Measured memory_bytes: 696
#include <stdio.h>
#define N 500000
#define MAX 1000000000

int cnt = 0;

void merge(int *a,int left,int mid,int right){
  int n1,n2,i,j,k;

  n1 = mid - left;
  n2 = right - mid;

  int L[n1+1], R[n2+1];

  for(i=0;i<n1;++i)L[i]=a[left+i];
  L[n1]=MAX;

  for(i=0;i<n2;++i)R[i]=a[mid+i];
  R[n2]=MAX;

  i = j = 0;

  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      a[k]=L[i];
      i++;
    }
    else {
      a[k]=R[j];
      j++;
    }
    cnt++;
  }
 
}

void mergeSort(int *a,int left,int right){
  int mid;
  if(left+1<right){
    mid = (left + right)/2;
    mergeSort(a,left,mid);
    mergeSort(a,mid,right);
    merge(a,left,mid,right);

  }
}


int main(){
  int a[N],n,i;

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

  mergeSort(a,0,n);

  for(i=0;i<n-1;++i)printf("%d ",a[i]);

  printf("%d\n%d\n",a[n-1],cnt);

  return 0;

  
}



Measured memory_bytes: 5624
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }


int main() {
	int n;
	cin >> n;
	vector<int> w(n);
	REP(i, n) {
		cin >> w[i];
	}
	//SORT(w);
	vector<int> sw(n + 1);
	/*vector<int> cnt(101, 0);
	REP(i, n) {
		cnt[w[i]]++;
	}
	vector<int> sc(102, 0);
	REP(i, 101) {
		sc[i + 1] = sc[i] + i * cnt[i];
	}
	int res = INT_MAX;
	REP(i, 101) {
		chmin(res, abs(sc.back() - sc[i] * 2));
	}
	put(res);*/
	sw[0] = 0;
	REP(i, n) {
		sw[i + 1] = sw[i] + w[i];
	}
	int res = INT_MAX;
	REP(i, n+1) {
		chmin(res,abs(sw.back() - sw[i]*2));
	}
	put(res);
	return 0;
}


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

int main() {
    int N;
    cin >> N;
    map<char, int> mp;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        mp[c]++;
    }

    cout << (mp.size() == 3 ? "Three" : "Four") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double eps=1.0e-9;

long long pow_2(ll a, ll n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

int main() {
  ll N,M;
  cin >> N >> M;
  priority_queue<ll> pq;

  for(ll i=0;i<N;i++){
    ll a;
    cin >> a;
    pq.push(a);
  }
  
  for(ll i=0;i<M;i++){
    ll a = pq.top();
    pq.pop();
    pq.push(a/2);
  }
      
  ll sum=0;
  while(!pq.empty()){
    sum += pq.top();
    pq.pop();
  }
  
  cout << sum << endl;
  return(0);
}

Measured memory_bytes: 1400
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define int ll
typedef vector<int> vi;
typedef pair<int,int> pii;

signed main(void) {
  int i,j;
  int n;
  string s;
  cin>>n;
  vi a(n),b(n);
  rep(i,n)cin>>a[i],b[i]=a[i];
  for(i=n-1;i>0;i--)b[i-1]+=b[i];
  rep(i,n-1)a[i+1]+=a[i];
  int sum=a[n-1];
  int ans=INF*INF;
  rep(i,n-1)b[i]=b[i+1];
  rep(i,n-1){
    ans=min(ans,abs(a[i]-b[i]));
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3328
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fromIntegral . fst . fromJust . BS.readInteger

readIntList = map readInt . BS.words

getIntList = readIntList <$> BS.getLine

main = do
  [h, a] <- getIntList
  print $ (h + a - 1) `div` a


Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

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; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()



int main() {
    int n, k;
    cin >> n >> k;
    int p = n / k;
    ll ans = 0;
    ans = 1ll * p * p * p;
    if (k % 2 == 0) {
        int q = n / (k / 2) - p;
        ans += 1ll * q * q * q;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1000000007;
ll mod(ll x){
        return ((x%M + M)%M);
    }
ll add(ll a, ll b){
        return mod(mod(a)+mod(b));
    }
ll mul(ll a, ll b){
        return mod(mod(a)*mod(b));
    }
ll minu(ll a, ll b){
        return mod(mod(a)-mod(b));
    }
ll power(ll a, ll b){
    ll res=1;
    while(b>0){
        if(b&1) res=mul(res,a);
        b = b>>1;
        a=mul(a,a);
    }
    return res;
}
int main(){
    ll x,k,d;
    cin>>x>>k>>d;
    x=abs(x);
    ll l = min(k,x/d);
    x-=(l*d);
    k-=l;
    if(k%2==0) cout<<x;
    else cout<<abs(x-d);
    return 0; 
}

Measured memory_bytes: 3568
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a - 1 for a in A]
D = 60
MAX_N = 200005
to = [[0] * MAX_N for _ in range(D)]
for i, a in enumerate(A):
    to[0][i] = a

for i in range(D - 1):
    for j in range(N):
        to[i + 1][j] = to[i][to[i][j]]

v = 0
for i in range(D - 1, -1, -1):
    l = 1 << i
    if l <= K:
        v = to[i][v]
        K -= l
print(v + 1)

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

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

    int n; cin >> n;
    int a = 0;
    rep(i, n) {
        string s; cin >> s;
        if (s=="A") a++;
        else if (s=="Un" && a) a--;
        else {
            puts("NO");
            return 0;
        }
    }
    if (a) puts("NO");
    else puts("YES");
}


Measured memory_bytes: 3248
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <cmath>
using namespace std;
typedef vector<int> VI;
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

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

    vector<vector<int>> triangles;
    
    int n;
    cin >> n;
    
    REP(i, 0, n) {
        vector<int> tmp;
        int a, b, c;
        cin >> a >> b >> c;
        tmp.push_back(a);
        tmp.push_back(b);
        tmp.push_back(c);
        
        sort(tmp.begin(), tmp.end());
        triangles.push_back(tmp);
    }

    for(auto sides : triangles) {
        if (sides[2] * sides[2] == sides[0]*sides[0]+sides[1]*sides[1]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 1268
n = int(input())
nums = list(map(int, input().split(' ')))
nums.reverse()

pre_n = nums[0]
output = 'Yes'
for i in range(1, len(nums)):
  n = nums[i]
  if pre_n < n:
    if pre_n < n - 1:
      output = 'No'
      break
    else:
      pre_n = n - 1
  else:
    pre_n = n
print(output)

Measured memory_bytes: 14224
import math

S = input()

l = [0]
ans = [0]*len(S)

tmp = "R"
for i in range(len(S)):
  if tmp != S[i]:
    l.append(i)
  tmp = S[i]

l.append(len(S))

for i in range(1, len(l), 2):
  ans[l[i]-1] = math.ceil((l[i]-l[i-1])/2) + math.floor((l[i+1]-l[i])/2)
  ans[l[i]] = math.floor((l[i]-l[i-1])/2) + math.ceil((l[i+1]-l[i])/2)

print(' '.join(map(str, ans)))

Measured memory_bytes: 61536