akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=(n); i--)
#define LREP(lst,itr) for(auto itr = lst.begin(); itr != lst.end(); ++itr)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define P(s) cout<<(s)<<endl
#define P2(a, b) cout<<(a)<<" "<<(b)<<endl
#define P3(a, b, c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
#define V2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

vector<pair<ll, ll>> prime_factor(ll n) {
	vector<pair<ll, ll>> vp;

	// iがsqrt(n)となるまで繰り返す
	for (ll i = 2; i*i <= n; i++) {
		if (n%i == 0) {  // iが素因数
			vp.emplace_back(i, 0);

			// 素因数の数を求める
			do {
				vp[vp.size() - 1].second++;
				n /= i;
			} while (n%i == 0);
		}
	}

	if (n != 1) vp.emplace_back(n, 1);
	return vp;
}


int main(){
    ll A,B,ans=0;
    cin >> A >> B;
    vector<pair<ll,ll>> vp = prime_factor(A);
    for(auto v:vp){
        if(B%v.first==0)ans++;
    }
    P(ans+1);
}

Measured memory_bytes: 256
x, y = map(int, input().split())

A = [1, 3, 5, 7, 8, 10, 12]
B = [4, 6, 9, 11]
C = [2]

if (x in A and y in A) or (x in B and y in B) or (x in C and y in C):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
import math


def rren(): return list(map(int, input().split()))


N, A, B = rren()
h = []
for i in range(N):
    h.append(int(input()))


left = 0
right = math.ceil(max(h)/B)
while(left <= right):
    K = math.floor((left + right) / 2)
    if(left == right):
        print(K)
        break
    else:
        sum = 0
        for i in range(N):
            sum += max(0, math.ceil((h[i] - K*B)/(A-B)))
        if(sum <= K):
            right = K
        else:
            left = K+1



Measured memory_bytes: 7120
#include <iostream>
#include <stdlib.h>
using namespace std;

int main(){
  
  int n,m;

  cin >> n >> m;

  int **A = new int* [n];
  for(int i=0; i<n; i++){
    A[i] = new int [m];
  }
  
  int *b = new int [m];


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

  for(int j=0; j<m; j++){
      cin >> b[j];
  }
  
    
  int *ans = new int [n];
  for(int i=0; i<n; i++){
    ans[i]=0;
    for(int j=0; j<m; j++){
      ans[i] += A[i][j]*b[j];
    }
  }

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

Measured memory_bytes: 1228
import java.util.Scanner;

public class Main {
	static int cnt = 0,n;
	static String[] str = {"3" , "5", "7"};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		n = sc.nextInt();
		solve("0");
		System.out.println(cnt);
	}
	private static void solve(String s) {
		if(Long.parseLong(s) > n) {
			return;
		}
		if(s.equals("0")) {
			s = "";
		}
		if(s.length() >= 3 && s.contains("3") && s.contains("5")&& s.contains("7")) {
			cnt++;
		}
		for(int i = 0; i < 3; i++) {
			solve(s + str[i]);
		}

	}
}


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

int main(){
    int n;
    cin>>n;
    n*=2;
    int l[n];
    for(int i=0;i<n;i++){
        cin>>l[i];
    }

    sort(l,l+n);
    int sum=0;
    for(int i=0;i<n;i++){
        if(i%2==0) sum+=l[i];
    }
    cout<<sum;

}

Measured memory_bytes: 256
s=input()
t=input()
s2=sorted(list(s))
t2=sorted(list(t))
s2_mojiretu="".join(sorted(s2))
t2_mojiretu="".join(reversed(t2))
if s2_mojiretu<t2_mojiretu:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38256
#include<bits/stdc++.h>
#include<array>
using namespace std;
#define int long long
// #define ll long long
#define endl "\n"
#define fast_cin ios_base::sync_with_stdio(false); cin.tie(NULL)

void solve(){
 
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = a*c;
    ans = max(ans, a*d);
    ans = max(ans, b*c);
    ans = max(ans, b*d);
    cout << ans;
}
 
int32_t main(){
 
    fast_cin;
    // int t;
    // cin >> t;
    // while(t-- > 0){
        solve();
        cout << "\n";
    // }
    
    return 0;
}

Measured memory_bytes: 3648
N,M,X = map(int,input().split())
CA = []
for i in range(N):
    CA.append(list(map(int,input().split())))

m = 10**8
for i in range(1<<N):
    alg = [0]*M
    money = 0
    for j in range(N):
        if (i>>j)&1:
            money += CA[j][0]
            for k in range(M):
                alg[k] += CA[j][k+1]
    clear = True
    for k in range(M):
        clear = clear and alg[k]>=X
    if clear and money<m:
        m = money
if m == 10**8:
    m = -1
print(m)

Measured memory_bytes: 9216
class Item
  attr_accessor :v, :w

  def initialize(v, w)
    @v, @w = v, w
  end
end

n, w = gets.split.map &:to_i
items = [Item.new(0, 0)]
n.times do
  value, weight = gets.split.map &:to_i
  items << Item.new(value, weight)
end

c = Array.new(n+1).map { Array.new(w+1, 0) }

(1..n).each do |i|
  (1..w).each do |j|
    tmp = j >= items[i].w ? c[i-1][j-items[i].w] + items[i].v : 0
    c[i][j] = [ tmp, c[i-1][j] ].max
  end
end

puts c[n][w]

Measured memory_bytes: 16696
#include<bits/stdc++.h>
typedef  long long int ll;
typedef  long double ld;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define pb(x) push_back(x) 
#define si(a) scanf("%lld",&a)
#define pi(a) printf("%lld",a)
#define mod 1000000007
#define f first
#define s second 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
//recursions\
#pragma comment(linker, "/stack:200000000")
//loops\
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,greater_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
using namespace std;
int main()
{
	sync;
	ll n,l;
	cin>>n>>l;
	ll sum=0,ans=l;
	for(ll i=1;i<=n;i++)
	sum+=l+i-1;
	for(ll i=1;i<=n;i++)
	if(abs((l+i-1))<abs(ans))
	ans=l+i-1;
	cout<<sum-ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, int>;
using vpii = vector<pair<int, int>>;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep1(i, n) for (int i = 1; i < (int)n; i++)
const ll mod = 1e9 + 7;
const ll inf = 1e12;
const double pi = 3.141592;
const int di[4] = {1, 0, -1, 0};
const int dj[4] = {0, 1, 0, -1};

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n;
    cin >> n;
    if(n%2 == 1){
        cout << 0 << "\n";
        return 0;
    }
    ll i = 10;
    ll ecnt = 0;
    while(i <= n){
        ecnt += n / i;
        i *= 5;
    }
    cout << ecnt << "\n";
    return 0;
}

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

typedef long long ll;
const int MAX_N = 100;

int main() {
  int N, W[MAX_N];
  std::cin >> N;
  for(int i = 0; i < N; ++i) {
    std::cin >> W[i];
  }

  int ans = 10000;
  for(int T = 0; T < N; ++T) {
    int S1 = 0, S2 = 0;
    for(int i = 0; i <= T; ++i) {
      S1 += W[i];
    }
    for(int i = T + 1; i < N; ++i) {
      S2 += W[i];
    }
    ans = std::min(ans, std::abs(S1 - S2));
  }

  std::cout << ans << std::endl;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

        Map<Long, Integer> map = new HashMap<>();
        for (Long l : a) map.put(l, map.getOrDefault(l, 0) + 1);

        long ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (map.get(a[i]) == 0) continue;
            map.put(a[i], map.get(a[i]) - 1);
            long diff = 2 * Long.highestOneBit(a[i]) - a[i];
            if (map.containsKey(diff) && map.get(diff) > 0) {
                ans++;
                map.put(diff, map.get(diff) - 1);
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 105924
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
#include<utility>
#include<functional>
#include<math.h>
typedef long long ll;
using namespace std;

int memo[100001]={};

int DP(int n){
  if(n==0){
    return 0;
  }
  if(memo[n]>0){
    return memo[n];
  }
  int ans = DP(n-1)+1;
  for(int i=6;i<=n;i*=6){
    ans = min(ans,DP(n-i)+1);
  }
  for(int i=9;i<=n;i*=9){
    ans = min(ans,DP(n-i)+1);
  }
  memo[n] = ans;
  return memo[n];
}

int main(){
  int N;
  cin >> N;
  memo[1]=1;
  cout << DP(N) << endl;
  return 0;
}


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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,x,t;
    cin>>n>>x>>t;
    int val = ceil(double(n)/double(x));
    ll ans = val*t;
    cout<<ans;
    
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;

template<typename T>
struct BIT {
	int n;
	vector<T> bit;
	BIT() :n(0) {}
	BIT(int _n) :n(_n) { bit = vector<T>(n + 1); }
	void add1(int idx, T val) {
		for (int i = idx; i <= n; i += i & -i) bit[i] += val;
	}
	T sum1(int idx) {
		T res = 0;
		for (int i = idx; i > 0; i -= i & -i) res += bit[i];
		return res;
	}
	//0-indexed
	void add(int idx, T val) { add1(idx + 1, val); }
	//0-indexed [left, right)
	T sum(int left, int right) { return sum1(right) - sum1(left); }

	int lower_bound(T x) {
		int res = 0;
		int k = 1;
		while (2 * k <= n) k <<= 1;
		for (; k > 0; k >>= 1) {
			if (res + k <= n and bit[res + k] < x) {
				x -= bit[res + k];
				res += k;
			}
		}
		return res;
	}
};

template<typename T>
struct Compress {
	vector<T> v;
	Compress() {}
	Compress(vector<T> _v) :v(_v) { build(); }

	void add(T x) {
		v.emplace_back(x);
	}
	void build() {
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}
	void build(vector<T> _v) {
		v = _v;
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}
	int get(T x) {
		return lower_bound(v.begin(), v.end(), x) - v.begin();
	}

	T& operator[](int i) { return v[i]; }


	int size() {
		return (int)v.size();
	}
};

int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int kkt; cin >> kkt;
	vector<vector<int>> query(kkt);
	Compress<int> comp;
	for (int i = 0; i < kkt; i++) {
		int t; cin >> t;
		vector<int> v; v.emplace_back(t);
		if (t == 1) {
			int a, b; cin >> a >> b;
			v.emplace_back(a);
			v.emplace_back(b);
			comp.add(a);
		}
		query[i] = move(v);
	}
	comp.build();
	BIT<ll> bc(comp.size()), bs(comp.size());
	ll cur = 0;
	int cnt = 0;
	for (auto& v : query) {
		if (v[0] == 1) {
			bc.add(comp.get(v[1]), 1);
			bs.add(comp.get(v[1]), v[1]);
			cur += v[2];
			cnt++;
		}
		else {
			int idx = bc.lower_bound((cnt + 1) / 2);
			ll mid = comp[idx];
			ll res = cur;
			res += bs.sum(idx + 1, comp.size()) - mid * bc.sum(idx + 1, comp.size()) + mid * bc.sum(0, idx) - bs.sum(0, idx);
			cout << mid << " " << res << "\n";
		}
	}
	return 0;
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
ll x[10], y[10];

double dist(ll i, ll j) {
  double dx = x[i] - x[j];
  double dy = y[i] - y[j];
  return pow(dx * dx + dy * dy, 0.5);
}

int main() {
  ll n, cnt = 0;
  cin >> n;
  vector<ll> v(n);
  iota(v.begin(), v.end(), 0);
  for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
  double ans = 0;
  do {
    rep(j, n - 1) ans += dist(v[j], v[j + 1]);
  } while (next_permutation(v.begin(), v.end()));
  int t = 1;
  for (int i = 2; i <= n; ++i) t *= i;

  cout << setprecision(16) << ans / t << endl;
  return 0;
}


Measured memory_bytes: 4232
void main() {
  problem();
}

void problem() {
  auto N = scan.map!(x => x - '0').array;

  bool solve() {
    ulong sumDecimal;
    foreach(n; N) sumDecimal += n;

    return sumDecimal % 9 == 0;
  }

  writeln(solve() ? "Yes" : "No");
}

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

import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons, std.numeric;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; }
T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
void deb(T ...)(T t){ debug writeln(t); }
alias Point = Tuple!(long, "x", long, "y");

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


Measured memory_bytes: 3796
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

int dp[101010];
int check[101010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N),C(N);
    REP(i,N){
        cin >> A[i];
        C[i] = A[i];
    }
    sort(C.rbegin(),C.rend());
    REP(i,N){
        if(A[i] != C[0]) cout << C[0] << endl;
        else cout << C[1] << endl;
    }
}


Measured memory_bytes: 3200
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <functional>
using i64 = long long;

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

    std::vector<std::pair<int, int>> v;
    std::vector<int> q;
    std::string open, close;
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        for (const auto c : s) {
            if (c == '(') q.push_back('(');
            else if (!q.empty() && q.back() == '(') q.pop_back();
            else q.push_back(')');
        }
        if (q.front() == '(') open += std::string(q.size(), '(');
        else if (q.back() == ')') close += std::string(q.size(), ')');
        else {
            const int a = std::count(q.begin(), q.end(), '(');
            v.emplace_back(a, q.size() - a);
        }
        q.clear();
    }

    std::sort(v.begin(), v.end(), [](const auto &lhs, const auto &rhs) {
        const int l = lhs.first - lhs.second, r = rhs.first - rhs.second;
        if (l != r) return l > r;
        if (l > 0) return lhs.second < rhs.second;
        else return lhs.second > rhs.second;
    });

    int total = open.size();
    for (const auto [o, c] : v) {
        if (total < c) {
            std::cout << "No" << std::endl;
            return 0;
        }
        total += o - c;
    }

    std::cout << (total != close.size() ? "No" : "Yes") << std::endl;

    return 0;
}


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

int main(){
    int n, d;
    int** points;
    cin >> n >> d;

    points = new int*[n];
    for(int i = 0; i < n; i++){
        points[i] = new int[d];
    }

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

    int count = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int len = 0;
            for(int k = 0; k < d; k++){
                int dif = (points[i][k] - points[j][k]);
                len += (dif*dif);
            }
            double length = sqrt(static_cast<double>(len));

            if(ceil(length) == floor(length)) count++;
        }
    }

    for(int i = 0; i < n; i++){
        delete[] points[i];
    }
    delete[] points;

    cout << count << endl;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
N, M = map(int, input().split())
ab = [tuple(map(int, readline().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, size):
        self.rank = [-1] * (size + 1)
        self.number = [1] * (size + 1)
    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
uf = UnionFind(N)
p = N * (N - 1) // 2
ans = [p]
for x, y in ab[1:][::-1]:
    px = uf.find(x)
    py = uf.find(y)
    if px != py:
        p -= uf.number[px] * uf.number[py]
        uf.union(px, py)
    ans.append(p)
print(*ans[::-1], sep="\n")


Measured memory_bytes: 26056
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int         long long   
#define double      long double
#define endl        "\n"
#define pb          push_back
#define PI          3.1415926535897932384626433832795l
#define F           first
#define S           second
#define mp          make_pair
#define f(i,n)      for(int i=0;i<n;i++)
#define fastio      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v)      (v).begin(),(v).end()
#define sort(v)     sort((v).begin(),(v).end())
#define rall(v)     (v).rbegin(),(v).rend()
#define rsort(v)     sort((v).rbegin(),(v).rend())
#define gcd(a,b)    __gcd((a),(b))
#define minn(v)     *min_element(v.begin(), v.end());
#define maxx(v)     *max_element(v.begin(), v.end());
#define print(x)    cout<<(x)<<endl;
typedef pair<int,int> pii;  
typedef vector<int> vi;
//x.substr(start, length);

bool isPrime(int n) 
{ 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
}
struct type{
    int k, i, j;
};
signed main() 
{
    cout<<fixed<<setprecision(12);
    fastio;
    int n,m;
    cin>>n>>m;
    if(n==m)
    {
        f(i,n)cout<<n<<"";
        cout<<endl;
    }
    else
    {
        f(i,max(n,m)) cout<<min(n,m)<<"";
        cout<<endl;
    }
    
    
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>

using namespace std;

class DisjointSet {
    public:
        vector<int> rank, p;

        DisjointSet() {}
        DisjointSet(int size) {
            rank.resize(size, 0);
            p.resize(size, 0);
            for (int i = 0; i < size; i++) makeSet(i);
        }

        void makeSet(int x) {
            p[x] = x;
            rank[x] = 0;
        }

        bool same(int x, int y) {
            return findSet(x) == findSet(y);
        }

        void unite(int x, int y) {
            link(findSet(x), findSet(y));
        }

        void link(int x, int y) {
            if (rank[x] > rank[y]) {
                p[y] = x;
            } else {
                p[x] = y;
                if (rank[x] == rank[y]) {
                    rank[y]++;
                }
            }
        }

        int findSet(int x) {
            if (x != p[x]) {
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};

int main() {
    int n, a, b, q;
    int t;

    cin >> n >> q;
    DisjointSet ds = DisjointSet(n);

    for (int i = 0; i < q; i++) {
        cin >> t >> a >> b;
        if (t == 0) ds.unite(a, b);
        else if (t == 1) {
            if (ds.same(a, b)) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3176
//g++  7.4.0

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 1000005
#define MOD 1000000007
ll spf[MAXN];
map<ll,ll> mp;

void sieve() 
{ 
    spf[1] = 1; 
    for (ll i=2;i<MAXN;i++) 
    {
        spf[i] = i; 
    }
    
    for (ll i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
  
    for (ll i=3; i*i<MAXN; i++) 
    { 
        // checking if i is prime 
        if (spf[i] == i) 
        { 
            // marking SPF for all numbers divisible by i 
            for (ll j=i*i; j<MAXN; j+=i) 
            {
                if (spf[j]==j) 
                    spf[j] = i; 
            }
        } 
    } 
} 

void g1(ll x) 
{ 
    while (x != 1) 
    { 
        mp[spf[x]]++;
        x = x / spf[x]; 
    } 
    
}

vector<ll> g2(ll x) 
{ 
    vector<ll> ret; 
    while (x != 1) 
    { 
        ret.push_back(spf[x]); 
        x = x / spf[x]; 
    } 
    
    return ret; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    sieve();
    
    ll N; cin>>N;
    ll arr[N];
    ll total = 0;
    
    for(ll i=0;i<N;++i)
    {
        cin>>arr[i];
        g1(arr[i]);
        if(total == 0)
            total = arr[i];
        else
            total = __gcd(total,arr[i]);
    }
    
    ll flag = 1;
    for(ll i=0;i<N;++i)
    {
        vector<ll> temp = g2(arr[i]);
        map<ll,ll> m;
        for(auto it: temp)
            m[it]++;
        
        for(auto it: m)
        {
            if((mp[it.first] - it.second) != 0)
            {
                flag = 0;
                goto A;
            }
        }
    }
    A:
    ;
    
    //cout<<total<<endl;
    
    if(flag)
        cout<<"pairwise coprime"<<endl;
    else if(total == 1)
        cout<<"setwise coprime"<<endl;
    else
        cout<<"not coprime"<<endl;
    
}


Measured memory_bytes: 24092
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
  
int main()
{
  ll X, Y;
  cin >> X >> Y;

  int cnt = 0;
  while(X<=Y){
    X*=2;
    cnt++;
  }
  cout << cnt << endl;
}

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b)a=b;};
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b)a=b;};

template<typename T> void drop(T x){cout<<x<<endl;exit(0);};

template<typename T>
T extgcd(T a, T b, T &x, T &y){
  T d = a;
  if(b != 0){
    d = extgcd(b, a%b, y, x);
    y -=(a/b) * x;
  }else{
    x = 1;
    y = 0;
  }
  return d;
}

template<typename T>
T mod_inverse(T a, T mod){
  T x, y;
  extgcd(a, mod, x, y);
  return (mod + x%mod)%mod;
}

template<typename T>
pair<T, T> linear_congruence(const vector<T> &A,
                            const vector<T> &B,
                            const vector<T> &M){
  T x = 0, m = 1;
  for(int i=0;i<(int)A.size();i++){
    T a = A[i] * m, b = B[i] - A[i]*x, d = __gcd(M[i], a);
    if(b%d!=0) return make_pair(0, -1);
    T t=b/d*mod_inverse(a/d, M[i]/d)%(M[i]/d);
    x = x + m * t;
    m *= M[i]/d;
  }
  return make_pair((x%m + m)%m, m);
}


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

  int n;
  cin>>n;
  vector<int> ps(n),qs(n);
  for(int i=0;i<n;i++) cin>>ps[i],ps[i]--;
  for(int i=0;i<n;i++) cin>>qs[i],qs[i]--;

  using ll = long long;
  vector<ll> A,B,M;

  vector<int> used(n,0);
  for(int i=0;i<n;i++){
    if(used[i]) continue;
    int pos=i;
    vector<int> vs,ws;
    while(!used[pos]){
      vs.emplace_back(pos);
      ws.emplace_back(ps[pos]);
      used[pos]=1;
      pos=qs[pos];
    }
    {
      auto as=vs,bs=ws;
      sort(as.begin(),as.end());
      sort(bs.begin(),bs.end());
      if(as!=bs) drop(-1);
    }
    int m=vs.size();
    for(int j=0;j<m;j++)
      ws.emplace_back(int(ws[j]));

    const int DEBUG = 0;
    if(DEBUG){
      for(int j=0;j<m;j++) cout<<vs[j]<<" ";
      cout<<endl;
      for(int j=0;j<m;j++) cout<<ws[j]<<" ";
      cout<<endl;
    }

    for(int j=0;j<m;j++){
      if(ws[j]!=vs[0]) continue;
      for(int k=0;k<m;k++)
        if(ws[j+k]!=vs[k]) drop(-1);

      //cout<<1<<" "<<j<<" "<<m<<endl;
      A.emplace_back(1);
      B.emplace_back(j);
      M.emplace_back(m);
    }
  }

  auto res=linear_congruence(A,B,M);
  if(res.second<0) drop(-1);
  cout<<(long long)(res.first)<<endl;
  return 0;
}



Measured memory_bytes: 3212
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	   c = getchar();
    }
    while(c >= '0' && c <= '9') {
    	res = res * 10 +c - '0';
    	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N;
int c[MAXN][4];
int64 h[MAXN];
map<int64,int> zz;
void insert(int64 p,int d) {
    for(int i = 0 ; i < 4 ; ++i) {
        zz[p] += d;
        p = p / 1000 + (p % 1000) * 1000000000LL;
    }
}
int64 calc(int64 a,int64 b,int64 c,int64 d) {
    int64 res = d + c * 1000 + b * 1000000 + a * 1000000000;
    return res;
}
int64 getcol(int64 p,int t) {
    for(int i = 0 ; i < 3 - t ; ++i) p /= 1000;
    return p % 1000;
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {
        for(int j = 0 ; j < 4 ; ++j) {
            read(c[i][j]);
        }
        h[i] = calc(c[i][0],c[i][1],c[i][2],c[i][3]);
        insert(h[i],1);
    }
    int64 ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
        insert(h[i],-1);
        for(int j = i + 1 ; j <= N ; ++j) {
            insert(h[j],-1);
            for(int k = 0 ; k < 4 ; ++k) {
                int64 res = 1;

                int64 rec[4] = {0};
                rec[0] = calc(getcol(h[i],0),getcol(h[j],1),getcol(h[j],0),getcol(h[i],1));
                rec[1] = calc(getcol(h[i],1),getcol(h[j],0),getcol(h[j],3),getcol(h[i],2));
                rec[2] = calc(getcol(h[i],2),getcol(h[j],3),getcol(h[j],2),getcol(h[i],3));
                rec[3] = calc(getcol(h[i],3),getcol(h[j],2),getcol(h[j],1),getcol(h[i],0));
                for(int x = 0 ; x < 4 ; ++x) {
                    res = res * zz[rec[x]];
                    if(!res) {
                        for(int y = 0 ; y < x ; ++y) {
                            insert(rec[y],1);
                        }
                        goto fail;
                    }
                    insert(rec[x],-1);
                }
                for(int x = 0 ; x < 4 ; ++x) {
                    insert(rec[x],1);
                }
                fail:;
                ans += res;
                h[j] = h[j] / 1000 + (h[j] % 1000) * 1000000000;
            }
            insert(h[j],1);
        }
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 20352
#include<stdio.h>

int main()

{

    long long int a,b,i,X=1,Y=1,Lim=1000000000000000000;

    scanf("%lld",&a);

    long long int A[a+5];

    for(i=0;i<a;i++){

        scanf("%lld",&A[i]);

    }

        for(i=0;i<a;i++){


        if(A[i]==0){

                X=0;
                break;

        }

        else if(Lim/Y>=A[i]) Y=Y*A[i];

        else X=2;


    }

        if(X==0) printf("0\n");
        else if(X==1) printf("%lld\n",Y);
        else if(X==2) printf("-1\n");

    return 0;
}


Measured memory_bytes: 2512
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
using namespace std;
typedef long long ll;

int main(){
	ll N,a=0,b=0;
	map<ll,ll> ma;
	cin >> N;
	for(int i=0;i<N;i++){
		ll x;
		cin >> x;
		ma[x]++;
		if(ma[x]<2)continue;
		vector<ll> l = {a,b,x};
		sort(l.begin(), l.end());
		a = l[1];
		b = l[2];
		ma.erase(x);
	}
	cout << a*b << endl;
}


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

const int INF = 1000000000;

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

		if(n==0 && m==0)
			break;

		int C[100][100];
		int T[100][100];
		for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				if(i==j){
					C[i][j] = T[i][j] = 0;
				}
				else{
					C[i][j] = T[i][j] = INF;
				}
			}
		}

		for(int i=0; i<n; i++){
			int a, b, c, t;
			cin >> a >> b >> c >> t;

			C[a-1][b-1] = C[b-1][a-1] = c;
			T[a-1][b-1] = T[b-1][a-1] = t;
		}

		int N,p,q,r;
		int dt[100][100];
		int dc[100][100];
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				dt[i][j]=T[i][j];
			}
		}
		for(int k=0;k<m;k++){
			for(int i=0;i<m;i++){
				for(int j=0;j<m;j++){
					if(dt[i][j]>dt[i][k]+dt[k][j]){
						dt[i][j]=dt[i][k]+dt[k][j];
					}
				}
			}
		} 
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				dc[i][j]=C[i][j];
			}
		}
		for(int k=0;k<m;k++){
			for(int i=0;i<m;i++){
				for(int j=0;j<m;j++){
					if(dc[i][j]>dc[i][k]+dc[k][j]){
						dc[i][j]=dc[i][k]+dc[k][j];
					}
				}
			}
		} 
		cin >> N;
		for(int I=0;I<N;I++){
			cin >> p >> q >> r;
			cout << (r?dt[p-1][q-1]:dc[p-1][q-1]) << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3240
def solver(N):
  if N % 2 == 1:
    return oddodd(N)
  else:
    return (N+1) ^ oddodd(N+1)

def oddodd(N):
  return 1 if (N+1)/2 % 2 == 1 else 0 

A,B = map(int,input().split())

print(solver(B) ^ solver(A-1))

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

class Program
{
    static void Main(string[] args)
    {
        var N = sc.ReadInt();
        var L = sc.ReadIntArray(N);
        var ok = L.Sum() > L.Max() * 2;
        Console.WriteLine(ok ? "Yes" : "No");
    }
    static int MOD = (int)1e9 + 7;
    static int INF = (int)1e7 + 1;
    static long LINF = (long)1e13 + 1;
    static Scanner sc = new Scanner();
}

class Scanner
{
    string[] S = new string[0];
    int Index = 0;
    char[] Separators = new char[] { ' ' };

    public string Next()
    {
        if (this.Index < this.S.Length) return this.S[this.Index++];
        var line = "";
        while (line == "") line = Console.ReadLine();
        this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
        if (this.S.Length == 0) return this.Next();
        this.Index = 0;
        return this.S[this.Index++];
    }
    public string ReadStr()
    {
        return this.Next();
    }
    public char ReadChar()
    {
        return this.Next()[0];
    }
    public int ReadInt()
    {
        return int.Parse(this.Next());
    }
    public uint ReadUInt()
    {
        return uint.Parse(this.Next());
    }
    public long ReadLong()
    {
        return long.Parse(this.Next());
    }
    public double ReadDouble()
    {
        return double.Parse(this.Next());
    }
    public int[] ReadIntArray(int n)
    {
        var array = new int[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadInt();
        }
        return array;
    }
    public long[] ReadLongArray(int n)
    {
        var array = new long[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadLong();
        }
        return array;
    }
    public double[] ReadDoubleArray(int n)
    {
        var array = new double[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadDouble();
        }
        return array;
    }
    public char[] ReadCharArray(int n)
    {
        var array = new char[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadChar();
        }
        return array;
    }
    public string[] ReadStrArray(int n)
    {
        var array = new string[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadStr();
        }
        return array;
    }
}

class Debug
{
    public static void Dump<T>(T[,] array)
    {
#if !DEBUG
        return;
#endif
        Console.WriteLine();
        var h = array.GetLength(0);
        var w = array.GetLength(1);

        for (int r = 0; r < h; r++)
        {
            for (int c = 0; c < w; c++)
            {
                Console.Write(array[r, c]);
                Console.Write(" ");
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
    public static void Dump<T>(T[] array)
    {
#if !DEBUG
        return;
#endif
        Console.WriteLine();
        Console.WriteLine(string.Join(" ", array));
        Console.WriteLine();
    }
}

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

int main(){
  int n, y;
  cin >> n >> y;
  for(int i=0; i<=y/10000; i++){
    for(int j=0; j<=(y-10000*i)/5000; j++){
      if((y-10000*i-5000*j)/1000==n-i-j){
        cout << i << ' ' << j << ' ' << n-i-j;
        return 0;
      }
    }
  }
  cout << -1 << ' ' << -1 << ' ' << -1;
  return 0;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        a: i32,
        b: i32
    }

    let c = format!("{}{}", a, b);
    let num: i32 = c.parse().unwrap();

    let mut i = 1;
    let mut ret = "No";
    loop {
        if i * i > num {
            break;
        }
        if i * i == num {
            ret = "Yes";
            break;
        }
        i = i + 1;
    }

    println!("{}", ret);
}


Measured memory_bytes: 2132
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define INF 2147483647
using namespace std;
using Graph=vector<vector<int>>;

int main(){
  int ans=0;
  string s;
  cin>>s;
  for(int i=0;i<s.length()-1;i++){
    if(s[i]!=s[i+1]){
      ans++;
    }
  }
  cout<<ans;
}


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

int main()
{
	int a, b, c, x;
	cin >> a;
	cin >> b;
	cin >> c;
	cin >> x;
	int ans = 0;
	for(int i = 0; i <= a; i++)
	{
		for(int j = 0; j <= b; j++)
		{
			if (x - i * 500 - j * 100 < 0) break;
			ans += x - i * 500 - j * 100 <= c * 50;
		}
	}
	cout << ans << "\n";
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
tmp = 0

for a in A:
	tmp += 1/a

print(1/tmp)

Measured memory_bytes: 5400
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;

#define all(A) (A).begin(), (A).end()
#define II(A) int (A); scanf("%d",&(A));
#define DBG if(1)
#define NDBG if(0)
#define end _asdf_asdf_bumsoo

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

const int MN = 100000 + 1;

int N;
int A[MN];
int end[MN];

int val(int x,int y){
	if(x>=N) return true;
	if(y>=A[x])	return true;
	return end[x]^((A[x]-1-y)&1);
}

int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++) scanf("%d",&A[i]);
	sort(A, A+N, greater<int>());
	end[N-1] = 0;
	for(int i=N-2;i>=0;i--){
		if(A[i] == A[i+1]) end[i] = end[i+1]^1;
		else end[i] = 0;
	}
	int x=0,y=0;
	while(x<N-1 && y+1 < A[x+1]) x++, y++;
	if(!val(x,y+1) || !val(x+1,y)){
		puts("First");
	}
	else puts("Second");
	return 0;
} 


Measured memory_bytes: 896
h, w, k = gets.chomp.split.map(&:to_i)
c = []
h.times do
  c << gets.chomp.chars
end

res = 0

(1 << h).times do |i|
  (1 << w).times do |j|
    cnt = 0
    h.times do |h_i|
      w.times do |w_i|
        if c[h_i][w_i] == "#" && i[h_i] == 0 && j[w_i] == 0
          cnt += 1
        end
      end
    end
    if cnt == k
      res += 1
    end
  end
end

puts res


Measured memory_bytes: 14320
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[20], dp[1 << 20]; bool vis[1 << 20];
int rec(int used) {
	if (vis[used]) return dp[used];
	int r = 0;
	int b[20] = { 0 }, c[20] = { 0 };
	for (int i = 0; i < 20; i++) {
		if (used & (1 << i)) {
			b[r] = a[i], c[r++] = i;
		}
	}
	int ret = r;
	for (int i = 0; i < r; i++) {
		int ty = i >> 2, tx = i & 3;
		for (int j = -1; j <= 1; j++) {
			for (int k = -1; k <= 1; k++) {
				if (!j && !k) continue;
				int ry = ty + j, rx = tx + k, t = 4 * ry + rx;
				if (0 <= ry && ry < 5 && 0 <= rx && rx < 4 && t < r) {
					if (a[c[i]] == a[c[t]]) {
						int used2 = used - (1 << c[i]) - (1 << c[t]);
						ret = min(ret, rec(used2));
					}
				}
			}
		}
	}
	vis[used] = true;
	return dp[used] = ret;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		fill(vis, vis + (1 << 20), false);
		for (int j = 0; j < 20; j++) cin >> a[j];
		cout << rec((1 << 20) - 1) << endl;
	}
	return 0;
}

Measured memory_bytes: 6824
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
#include <list>
#include <iomanip>
#include <cctype>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;

	s[k - 1] = s[k - 1] + 32;

	cout << s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10 ;
using ll = long long ;
const ll inf = 1e18;
int  n;
ll k ;

int zero;
vector<ll> a;

bool ok (ll x) {
    /// how many pair <= x
    ll now = x >= 0 ? 1LL * zero * n + (1LL * zero * (zero - 1) / 2) : 0;
    for (int i = 0 ; i < n - 1 ; i ++ ) {
        if (a[i] < 0) {
            ll minreq ;
             if (x < 0) minreq = ceil((long double)x / (long  double)a[i]);
             else minreq = x / a[i];

            int l = i + 1 ,  r = n - 1 , mid , ans = -1;
            while (l <= r) {
                mid = l + r >> 1;
                if (a[mid] >= minreq) {
                    ans = mid ;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            if (ans == -1) continue;
            now += n - ans;
        }
        else if (a[i] > 0) {
            ll minreq ;
            if (x >= 0) minreq = x / a[i];
            else minreq = floor( (long double) x / (long double)a[i]);
            int l = i + 1 , r = n - 1 , mid , ans = -1;
            while (l <= r) {
                mid = l + r >> 1;
                if (a[mid] <= minreq) {
                    ans = mid ;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            if (ans == -1) continue;
            now += ans - i  ;
        }
        else throw;
    }
    return now >= k;
}

int main () {
    scanf("%d %lld", &n, &k);

    for (int i = 0 ;i < n; i++) {
        ll x;
        scanf("%lld", &x);
        if (x == 0) zero ++;
        else a.emplace_back(x);
    }
    sort(a.begin(), a.end());
    n = (int)a.size() ;
    ll l = -inf , r = inf, ans =-inf - 2;

    while (l <= r) {
        ll mid = l + r >> 1 ;
        if (ok(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    printf("%lld\n", ans);
}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int Q;
  cin >> Q;
  ll bs = 0;
  priority_queue<ll> q1;
  priority_queue<ll, vector<ll>, greater<ll>> q2;
  q1.push(-longinf); q2.push(longinf);
  ll sum1 = 0, sum2 = 0;
  int N = 0;
  rep(q, Q) {
    int t;
    cin >> t;
    if(t == 1) {
      ll a, b;
      cin >> a >> b;
      if(N%2==0) {
        if(a < q2.top()) {
          q1.push(a);
          sum1 += a;
        } else {
          q2.push(a);
          sum2 += a;
          a = q2.top(); q2.pop();
          sum2 -= a;
          q1.push(a);
          sum1 += a;
        }
      } else {
        if(a < q1.top()) {
          q1.push(a);
          sum1 += a;
          a = q1.top(); q1.pop();
          sum1 -= a;
          q2.push(a);
          sum2 += a;
        } else {
          q2.push(a);
          sum2 += a;
        }
      }
      bs += b;
      N++;
    } else {
      cout << q1.top() << ' '
           << q1.top()*((int)q1.size()-(int)q2.size())-sum1+sum2+bs << "\n";
    }
  }
  return 0;
}


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

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;

const char nl = '\n' ;
const ll MOD = 1e9 + 7;

bool check(string s)
{
   int k = s.size()/2;
   for(int i = 0; i <k; i++)
   {
      if(s[i] != s[i+k])
         return false;
   }
   return true;
}
int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   int a, b; cin >> a >> b;
   (a+b)%3 && a%3 && b%3 ? cout << "Impossible" : cout << "Possible";
   return 0;
}


Measured memory_bytes: 3556
#include <iostream>
#include <algorithm>

int main() {
  int n;
  int l[101];

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

  std::sort(l, l + n);

  int sum = 0;
  for (int i = 0; i < n - 1; ++i) {
    sum += l[i];
  }

  if (l[n - 1] < sum) {
    std::cout << "Yes" << std::endl;
  }
  else {
    std::cout << "No" << std::endl;
  }

  return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp> //required
#include <ext/pb_ds/tree_policy.hpp> //required

using namespace __gnu_pbds; 
using namespace std;

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
typedef long long  ll;
typedef vector<ll> VL;
typedef vector<int> VI;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define pb push_back

#define F first
#define S second
#define SZ(a) int((a).size())
#define ALL(a) a.begin(),a.end()
#define fr(i,x,y) for(int i=x;i<y;i++)
#define frr(i,x,y) for(int i=x-1;i>=y;i--)
#define inf 1e18+1
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mod=1000000007;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll power(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;}a=a*a;b>>=1;}return ans;}
ll powerm(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;ans%=mod;}a=a*a;a%=mod;b>>=1;}return ans%mod;}
VL dx={1,0,-1,0};
VL dy={0,1,0,-1};
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

void solve()
{
    ll n,ans=0;
    cin>>n;
    //VL arr(n);
    vector<PLL> tmp,arr(n);
    fr(i,0,n)
    {
        cin>>arr[i].F>>arr[i].S;
        tmp.pb({arr[i].F+arr[i].S,i});
    }
    sort(ALL(tmp));
    reverse(ALL(tmp));
    fr(i,0,n)
    {
        if(~i&1)ans+=(tmp[i].F-arr[tmp[i].S].S);
        else
            ans-=(tmp[i].F-arr[tmp[i].S].F);
    }
    cout<<ans<<endl;
    return;
}
int main()
{
    IOS;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        //cout<<"Case #"<<pp-t<<":\n";
        solve();
    }
    return 0;
}
/* stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
*/
/*
recursion - matrix exponential

*/
// BITMASK:
// 1)When some constrall is of the order of 15-20, think of bitmask DP.
// 2)When some constrall is around 40, try out meet in the middle
// 3) See Strings,palindromes,prefix,suffix etc -> KMP,Z algorithm

Measured memory_bytes: 6856
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pri 1000000007
#define PB push_back
#define MP make_pair
using namespace std;

void run(){
ll n;
cin>>n;
double p[n+1];
for(ll i=0;i<n;i++)cin>>p[i];	
double dp[n]={0};//no of hae
dp[0]=1;
for(ll j=0;j<n;j++){
for(ll i=n;i>=0;i--){
	dp[i]=p[j]*(i>=1?dp[i-1]:0)+(1-p[j])*dp[i];
}}

ll x=(n+1)/2;
double ans=0;
for(ll i=x;i<=n;i++){ans+=dp[i];}
cout<<setprecision(11)<<fixed<<ans<<endl;
}
 
int main() {
	ll t=1;
	//cin>>t;
	for(ll i=0;i<t;i++)run();
	// your code goes here
	return 0;
}

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

namespace mondai0006
{
	class Program
	{
		static void Main(string[] args)
		{
			var	str	= Console.ReadLine();
			for( int i = str.Length - 1; i >= 0; i-- ) {
				Console.Write( str[ i ] );
			}
			Console.WriteLine();
		}
	}
}

Measured memory_bytes: 5216
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>
#include <limits.h>
#include <cmath>
#include <stdio.h>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = false;

int main(){

    ll N;
    cin >> N;

    vector<ll> A(N+1);
    for(int i = 0; i <= N; i++) cin >> A[i];

    vector<ll> B(N);
    for(int i = 0; i < N; i++) cin >> B[i];

    ll ans = 0;
    ll remain = 0;
    for(int i = 0; i < N; i++){
        if(A[i] >= (B[i] + remain) ){
            ans += (B[i] + remain);
            remain = 0;
        } 
        else {
            ans += A[i];
            remain = min(B[i], (B[i] + remain) - A[i] );
        }
    }
    ans += min(remain, A[N]);
    cout << ans << endl;

}

Measured memory_bytes: 1792
use std::io;

fn gets() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

fn main() {
    let line = gets();
    let mut it = line
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<i32>().unwrap());
    let t = it.next().unwrap();
    let a = it.next().unwrap();
    let b = it.next().unwrap();
    if t * a < b {
        println!("{}", t * a);
    } else {
        println!("{}", b);
    }
}


Measured memory_bytes: 4352