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

int main(){
  int n,m;
  char cha, chb;
  char c;
  char *out;
  out = new char[100000001];

  while(cin >> n, n){
    map<char, char> conv;
    map<char, char>::iterator itr;    
    for(int i=0; i<n; i++){
      cin >> cha >> chb;
      conv.insert(make_pair(cha, chb));
    }
    cin >> m;
    for(int i=0; i<m; i++){
      cin >> c;
      if((itr = conv.find(c)) != conv.end()) out[i] = itr->second;
      else out[i] = c;
    }
    out[m] = '\0';
    cout << out << endl;
  }
  return 0;
}

Measured memory_bytes: 1296
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

int main(){
  ll N, K; cin>>N>>K;
  map<ll,ll> m;

  rep(i,K){
    ll a; cin>>a;
    rep(j,a){
      ll b; cin>>b;
      m[b]++;
    }
  }

  ll ans = 0;
  repn(i,N){
    if(m[i] == 0) ans++;
  }
  cout<<ans<<endl;
}


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

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

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

bool comp(P a, P b) { return a.second > b.second; }

void solve(){
    int N; cin >> N;
    vector<ll> A(N), B(N);
    vector<P> AB(N);
    for(int i = 0; i < N ; ++i){
        cin >> A[i] >> B[i];
        AB[i] = {i, A[i] + B[i]};
    }
    sort(AB.begin(), AB.end(), comp);

    ll ans = 0;
    for(int i = 0; i < N ; ++i){
        if(i % 2 == 0) {
            ans += A[AB[i].first];
        }
        else{
            ans -= B[AB[i].first];
        }
    }
    cout << ans << '\n';
}



int main() {
    #ifdef MYLOCAL
    const int CASES = 3;
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
    #else

    solve();

    #endif
    return 0;
}



Measured memory_bytes: 3328
#pragma GCC optimize "03"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
 
int sz[N], par[N];

int root(int x){
    if(par[x] != x)
        par[x] = root(par[x]);
    return par[x];
}

void merge(int x, int y){
    x = root(x), y = root(y);
    par[x] = y;
}

signed main() {
    IOS;
    #ifdef LOCAL
        freopen("input.txt","r", stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n, m;   cin >> n >> m;
    for(int i = 1; i <= n; i++)
        par[i] = i;
    for(int i = 1; i <= m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        if(root(x) != root(y))
            merge(x, y);
    }   
    set<int> s;
    for(int i = 1; i <= n; i++)
        s.insert(root(i));
    cout << s.size();
    return 0;
}

Measured memory_bytes: 5376
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left
from math import factorial


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n = I()
L = sorted(LI())
if L[n // 2] == L[n // 2 - 1]:
    print(0)
else:
    print(L[n // 2] - L[n // 2 - 1])









Measured memory_bytes: 53484
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define INF 11000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;

int main(){
  ll S;
  cin>>S;
  ll x[3],y[3];
  x[0]=0; y[0]=0;x[1]=1000000000; y[1]=1;
  y[2]=S/1000000000+1; x[2]=y[2]*x[1]-S;
  if(S==1000000000000000000){
    y[1]=0;
    y[2]--;
    x[2]=0;
  }

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


Measured memory_bytes: 256
k =  int(input())

#make a list by 1-9


def swap(a,b):
    x = a
    a = b
    b = x

    return a,b

a = [i+1 for i in range(9)]

while(1):
    if k <= len(a):
        print (a[k-1])
        break

    b = []
    k = k - len(a)
    a,b = swap(a,b)

    for x in b:
        for i in [-1,0,1]:
            d =  x%10  + i
            if d < 0 or d > 9: continue
            a.append( x*10 + d)


Measured memory_bytes: 11028
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		Map<Integer, Integer> ma = new HashMap<>();
		for (int i = 0; i < N; i++) {
			ma.merge(sc.nextInt(), 1, Integer::sum);
		}
		List<Integer> nums = new ArrayList<>(ma.values());
		Collections.sort(nums);
		int nowk = ma.size();
		int ans = 0;
		for (int i=0; nowk > K; i++, nowk--) {
			ans += nums.get(i);
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 101252
# UnionFind
import sys
sys.setrecursionlimit(1000000)
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.siz = n

  def find_root(self, x):
    if self.n[x] < 0:
      return x
    else:
      self.n[x] = self.find_root(self.n[x])
      return self.n[x]

  def unite(self, x, y):
    x = self.find_root(x)
    y = self.find_root(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.siz -= 1

  def root_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

  def count(self, x):
    return -self.n[self.find_root(x)]

  def size(self):
    return self.siz

n,m=map(int,input().split())
u=UnionFind(n)
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  u.unite(a,b)
print(u.size()-1)

Measured memory_bytes: 11448
#include<bits/stdc++.h>
using namespace std;
typedef signed long long ll;
 
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int gcd(int a, int b){
	int t;
	while(b != 0){
		t = a%b;
		a = b;
		b = t;
	}
	return a;
}

int main(){
	int i,j,k,n,m,l,f,x,y,z; string s;
	cin >> n;
	int a[100010];
	rep(i, n) cin >> a[i];

	int b = 1000000001;
	int c = 0;
	rep(i, n){
		b = min(b, a[i]);
		c = max(c, a[i]);
	}

	int d = gcd(c,b);
	x = d;
	rep(i, n){
		if(a[i] % d != 0 )
			x = 1;
	}
	cout << x << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
long long n,mx,mn,k,ans=0,sum[200002];
const long long base=1000000007;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    cin>>n>>k;
    sum[0]=0;
    for (int i=1;i<=200001;i++) sum[i]=sum[i-1]+i;
    for (int i=k;i<=n+1;i++) 
    {
        mn=sum[i-1];
        mx=sum[n]-sum[n-i];
        //cout<<mx<<" "<<mn<<endl;
        ans=ans+(mx-mn+1);
        ans=ans%base;
    }
    cout<<ans%base;
}

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

int main() {
	int N;
	double p, q,D;
	int cnt = 0;
	cin >> N >> D;
	for (int i = 0; i < N; i++) {
		cin >> p >> q;
		if (sqrt(p * p + q * q) <= D) {
			cnt += 1;
		}
	}
	cout << cnt << endl;
}

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

struct Data {
    ll a, b, c, d;
};
ll N, M, Q;
Data D[55];

ll dfs(vector<ll> v) {
    if (v.size() == N) {
        ll sum = 0;
        REP(i, Q) {
            if (v[D[i].b] - v[D[i].a] == D[i].c)
                sum += D[i].d;
        }
        return sum;
    }

    ll s = 1;
    if (v.size() > 0)
        s = v.back();
    ll ret = 0;
    FOR(i, M + 1, s) {
        v.push_back(i);
        ret = std::max(ret, dfs(v));
        v.pop_back();
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    REP(i, Q) {
        cin >> D[i].a >> D[i].b >> D[i].c >> D[i].d;
        D[i].a--;
        D[i].b--;
    }

    cout << dfs(vector<ll>()) << endl;
    return 0;
}

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


using namespace std;

int main(){
	int n;
	cin >> n;
	int ans=0;
	for(int i=1;i<=n;i+=2) {
		int d=0;
		for(int j=1;j<=i;j++) {
			if(i%j==0) d++;
		}
		if(d==8) ans++;
	}
	printf("%d",ans);
	return 0;
}




Measured memory_bytes: 3740
#include <bits/stdc++.h> 
using namespace std;
#define ll long long 
#define mod 1000000007
#define MOD 99824435300000000
inline ll mul(ll a,ll b){
  a=(a+MOD)%MOD;
  b=(b+MOD)%MOD;
  ll c=a*b;
  c=(c+MOD)%MOD;
  return c;
}
inline ll add(ll a,ll b){
  a=(a+MOD)%MOD;
  b=(b+MOD)%MOD;
  ll ans=(a+b);
  ans=(ans+MOD)%MOD;
  return ans;
}

ll power(ll a,ll b,ll c){
  ll ans=1;
  while(b){
    if(b&1){
      ans=mul(ans,a);
    }
    a=mul(a,a);
    b=b/2;
  }
  return ans;
}
inline ll max(ll a,ll b){return a>b?a:b;}
inline ll min(ll a,ll b){return a<b?a:b;}
void f(vector<int> v[],int dp[],int src,int vis[]){
  vis[src]=1;
  for(auto x: v[src]){
    if(!vis[x])
      f(v,dp,x,vis);
      dp[src]=max(dp[src],1+dp[x]);
  }
}
int main()
{
  int n,m; cin>>n>>m;
  vector<int> v[n+1];
  for(int i=0;i<m;++i){
    int a,b; cin>>a>>b;
    v[a].push_back(b);
  }
  int dp[n+1];
  memset(dp,0,sizeof(dp));
  int vis[n+1];
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;++i){
    if(!vis[i]){f(v,dp,i,vis);}
  }
  int ans=0;
  for(int i=1;i<=n;++i)ans=max(ans,dp[i]);
  cout<<ans;
  return 0;
}

Measured memory_bytes: 9856
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>

int main() {
	long long  r, d, x[11];
	std::cin >> r >> d >> x[0];
	for (int i = 1; i <=10; ++i) {
		x[i] = x[i - 1] * r - d;
		std::cout << x[i] << std::endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
   int n,a[105],p,s=0,smin=1e9;
   cin >> n;
   for(int i=1;i<=n;i++)
   {
       cin >> a[i];
   }
   for(p=1;p<=100;p++)
   {
       s=0;
       for(int i=1;i<=n;i++)
       {
           s+=(a[i]-p)*(a[i]-p);
       }
       smin=min(s,smin);
   }
   cout << smin;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int findGCD(int x,int y,int z, int n)
{
    int arr[]={x,y,z};
    int result = arr[0];
    for (int i = 1; i < n; i++)
    {
        result = gcd(arr[i], result);

        if(result == 1)
        {
           return 1;
        }
    }
    return result;
}


int32_t main(){

int k;
cin>>k;
int sum=0;

for(int x=1;x<=k;x++){
    for(int y=1;y<=k;y++){
        for(int z=1;z<=k;z++){
            sum+=findGCD(x,y,z,3);
        }
    }
}
cout<<sum<<"\n";
return 0;
}


Measured memory_bytes: 3636
n, m = gets.split.map(&:to_i)
list = Array.new( n ){ gets.split.map(&:to_i) }.sort

ans = 0
list.each do |l|
  
  l[1] = m if l[1] > m  
  
  ans += l[0] * l[1]
  
  m -= l[1] 
  
  break if m <= 0
  
end

puts ans

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

struct edge{
    int to,color,num;
};
vector<edge> G[MAX_V];

void input_graph(int E){
    int s,t;
    REP(i,E){
        cin>>s>>t;s--;t--;
        G[s].push_back({t,-1,i});
        G[t].push_back({s,-1,i});
    }
}

int main(){
  int V,E,k=0;cin>>V;E=V-1;
  input_graph(E);
  queue<int> q;q.push(0);
  vector<bool> h(V,false);h.at(0)=true;
  vector<int> ans(E,0),edge_from(V,0);

  while(!q.empty()){
    int now=q.front();q.pop();
    int cur_color=1;
    for(int i=0;i<G[now].size();i++){
      int next=G[now].at(i).to;
      if(h.at(next)==0){
        h.at(next)=true;
        if(cur_color==edge_from.at(now)) cur_color++;
        G[now].at(i).color=edge_from.at(next)=cur_color;
        k=max(k,cur_color);
        ans.at(G[now].at(i).num)=cur_color;
        cur_color++;
        q.push(next);
      }
    }
  }
  
  cout<<k<<endl;
  REP(i,E) cout<<ans.at(i)<<endl;
}

Measured memory_bytes: 7936
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;cin>>n;
    string s;cin>>s;
    int ans=n;
    for(int i=0;i<n-1;i++){
        if(s[i]==s[i+1])ans--;
    }
    cout<<ans<<endl;
}

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

using namespace std;

typedef long long int ll;


void solve()
{
	ll a, b;
	cin >> a >> b;
	cout << a * b;
}

int main()
{
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}



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

// Process
#define rep(i, l, r) for(int i = (l); i <= (r); i++)

// Debug
template<typename F, typename S>
ostream& operator << (ostream& os, pair<F, S>& p){
	os << '(' << p.first << ", " << p.second << ')';
	return os;
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	os << '[';
	bool flg = 1;
	for(auto i : v){
		flg ? os << "" : os << ", ";
		os << i;
		flg = 0;
	}
	os << ']';
	return os;
}
#define deb(x) cerr << #x << " = " << (x) << "\n"
#define mes(x) cerr << "/ " << x << " /\n"

// Global variable
int n;
string s;
unordered_map<string, int> um;

void solve(){
	cin >> n;
	rep(_, 1, n){
		cin >> s;
		um[s]++;
	}
	cout << "AC x " << um["AC"] << "\n";
	cout << "WA x " << um["WA"] << "\n";
	cout << "TLE x " << um["TLE"] << "\n";
	cout << "RE x " << um["RE"] << "\n";
}

int main(){
	#ifndef ONLINE_JUDGE
		freopen("E:/PROGRAM/CP/std.in", "r", stdin);
		freopen("E:/PROGRAM/CP/std.out", "w", stdout);
		freopen("E:/PROGRAM/CP/std.err", "w", stderr);
	#endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int t = 1;
	// cin >> t;
	while(t--) solve();

	return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
//mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count());
//int rnd(int x) { return mrand()%x;}
typedef long long ll;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
//D
const ll md=1e9+7;
ll s;
ll dp[2100];
int main(){
	scanf("%lld",&s);
	dp[0]=1;
	for(int i=1;i<=s;i++){
		for(int j=3;j<=i;j++){
			if(i-j>=0) dp[i]=(dp[i]+dp[i-j])%md;
			else break;
		}
	}
	printf("%lld\n",dp[s]);
	return 0;
}


Measured memory_bytes: 3724
/*For the name of God*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const ll MAX = 1e7 + 20;
#define fast ios_base:: sync_with_stdio( false ); cin.tie(0); cout.tie(0);
#define eb              emplace_back
#define em              emplace
#define pb              push_back
#define Mp              make_pair
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define rep(i,n)        for(int i=0;i<n;i++)
#define rep1(i,n)       for(int i=1;i<=n;i++)
#define rrep(i,a,n)     for(int i=a;i<=n;i++)
#define per(i,n,a)      for(int i=n;i>=a;i--)
#define pf(n)           printf("%lld",n)
#define pfi(n)          printf("%d",n)
#define sp              printf(" ")
#define ln              "\n"

template< class T > T gcd(T a, T b)
{
    return (b != 0 ? gcd<T>(b, a%b) : a);
}
template< class T > T lcm(T a, T b)
{
    return (a / gcd<T>(a, b) * b);
}
const int N = 200200;
pair<int,int>c[1000001];
int main()
{
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    fast

    ll a,b,c,sum=0;
    vector<ll>v;
    cin>>a>>b;
    for(int i=0; i<a; i++)
    {
        cin>>c;
        v.push_back(c);
    }
    sort(v.begin(),v.end());
    if(b>a)
    {
        b=a;
    }
    for(int i=0; i<a-b; i++)
    {
        sum=sum+v[i];
    }
    cout<<sum<<endl;
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

template<class T,T op(T,T)> class segtree{
public:
    int n,size_;
    vector<T> dat;
    T id_;
    segtree()=default;
    segtree(int size,T id,T initial_value){ init(size,id,initial_value); }
    void init(int size,T id,T initial_value){
        size_=size;
        id_=id;
        n=1;
        while(n<size) n*=2;
        dat.assign(2*n-1,id);
        for(int i=0; i<size; ++i) update(i,initial_value);
    }
    int size()const{ return size_; }
    void update(int k, T a) {
        k+=n-1; // leaf
        dat[k]=a;
        while(k>0) {
            k=(k-1)/2;
            dat[k]=op(dat[k*2+1],dat[k*2+2]);
        }
    }
    T at(int index){ return dat[index+n-1]; }
    void add(int k,T a){ update(k,at(k)+a); }
    T query(int a,int b) { return query(a,b,0,0,n); }
    T query(int a,int b,int k,int l,int r) {
        if(r<=a or b<=l) return id_;
        if(a<=l and r<=b) return dat[k];
        int m=(l+r)/2;
        return op(query(a,b,k*2+1,l,m),query(a,b,k*2+2,m,r));
    }
};

int min_(int x,int y){
    return min(x,y);
}

void solve(){
    int N;
    cin >> N;

    vector<int> p(N),val_to_index(N+1);
    segtree<int,min_> seg_even(N,inf,inf),seg_odd(N,inf,inf);
    rep(i,0,N){
        cin >> p[i];
        if(i%2==0) seg_even.update(i,p[i]);
        else seg_odd.update(i,p[i]);
        val_to_index[p[i]]=i;
    }

    auto min_pair=[&](int l,int r){
        int l_=l%2==0?val_to_index[seg_even.query(l,r-1)]:val_to_index[seg_odd.query(l,r-1)],
            r_=l%2==0?val_to_index[seg_odd.query(l_+1,r)]:val_to_index[seg_even.query(l_+1,r)];
        return make_pair(l_,r_);
    };

    vector<int> ans;
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
    pq.push(make_tuple(p[min_pair(0,N).first],0,N));

    while(!pq.empty()){
        int l=get<1>(pq.top()),r=get<2>(pq.top());
        pq.pop();
        
        auto tmp=min_pair(l,r);
        int l_=tmp.first,r_=tmp.second;
        ans.push_back(p[l_]);
        ans.push_back(p[r_]);
        
        if(l_-l>=2) pq.push(make_tuple(p[min_pair(l,l_).first],l,l_));
        if(r_-(l_+1)>=2) pq.push(make_tuple(p[min_pair(l_+1,r_).first],l_+1,r_));
        if(r-(r_+1)>=2) pq.push(make_tuple(p[min_pair(r_+1,r).first],r_+1,r));
    }

    rep(i,0,N){
        cout << ans[i];
        if(i==N-1) cout << endl;
        else cout << " ";
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 8628
#include <stdio.h>          // printf(), scanf()
#include <stdbool.h>

int
main(int argc, char **argv)
{
	int h, m, s;
	int time1;
	int time2;

	while (true)
	{
		scanf("%d %d %d", &h, &m, &s);
		if (h == -1 && m == -1 && s == -1)
			break;

		time1 = 3600 * 2 - (3600 * h + 60 * m + s);
		time2 = time1 * 3;

		s = time1 % 60;
		time1 /= 60;
		m = time1 % 60;
		h = time1 / 60;
		printf("%02d:%02d:%02d\n", h, m, s);

		s = time2 % 60;
		time2 /= 60;
		m = time2 % 60;
		h = time2 / 60;
		printf("%02d:%02d:%02d\n", h, m, s);
	}

	return 0;
}

Measured memory_bytes: 612
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.NoSuchElementException;

class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner();
		int N = sc.nextInt();
		long[] A = new long[N];
		for (int i = 0; i < N; ++i) {
			A[i] = sc.nextLong() - (i + 1);
		}
		Arrays.sort(A);
		long ans = 0;
		for (int i = 0; i < N; ++i) {
			ans += Math.abs(A[i] - A[N / 2]);
		}
		System.out.println(ans);
	}

	class Scanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		private void skipUnprintable() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
		}

		public boolean hasNext() {
			skipUnprintable();
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		int nextInt() {
			return (int) nextLong();
		}
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}


Measured memory_bytes: 25892
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int > mp;
    for (int i = 1; i <= n; i++) {
        string s;
        double p;
        cin >> s >> p;
        string ss = to_string(1/p);
        mp[s + ss] = i;
    }
    for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
        cout << itr->second << endl;
    }
}


Measured memory_bytes: 256
class Problem
  attr_accessor :a, :b, :n, :m, :h, :w

  def initialize
    @n = gets.to_s.to_i
    @a = Array.new(n){ gets.to_s.to_i }.sort
  end

  def solve
    ans = 0
    each do |n|
      ans += 1 if n.odd?
    end
    ans
  end

  def each
    cnt = 1
    n.times do |i|
      if i == n - 1 || a[i] != a[i+1]
        yield cnt
        cnt = 1
      else
        cnt += 1
      end
    end
  end

  def show(ans)
    puts ans
  end
end

Problem.new.instance_eval do
  show(solve)
end


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

int main() {
    int x;
    cin >> x;
    if (x == 7 || x == 5 || x == 3) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 256
def main():
	N = int(input())
	a = list(map(int, input().split()))
	num = 1
	cnt = 0
	if 1 not in a:
		print(-1)
	else:
		for i in range(N):
			if a[i] == num:
				num += 1
			else:
				cnt += 1
		print(cnt)



if __name__ == '__main__':
	main()

Measured memory_bytes: 26268
K = int(input())

if K % 2 == 0 or K % 5 == 0:
  print(-1)
else:
  if K % 7 == 0:
    L = 9 * K // 7
  else:
    L = 9 * K
  a = 10 % L
  check = False
  for i in range(L):
    a %= L
    if a == 1:
      print(i + 1)
      check = True
      break
    a *= 10
  if not check:
    print(-1)

Measured memory_bytes: 9192
#include<iostream>

using namespace std;

int main(){

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

   int ans=0;
   for(int i=0; i<N; i++){
      if(i==a[a[i]]) ans++;
   }

   cout<< ans/2<< endl;

   return 0;
}


Measured memory_bytes: 768
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  if(n == 3){
    cout << "2 5 63" << endl;
    return 0;
  }else if(n == 4){
    cout << "2 5 20 63" << endl;
    return 0;
  }
  ll sum = 0;
  int curr = 2;
  vector<int> vec;
  while(vec.size() < n){
    if(curr % 2 == 0 || curr % 3 == 0){
      vec.pb(curr);
      sum += curr;
    }
    curr++;
  }
  if(sum % 6 == 2){
    while(curr % 6 != 0)curr++;
    vec[4] = curr;
  }else if(sum % 6 == 3){
    while(curr % 6 != 0)curr++;
    vec[5] = curr;
  }else if(sum % 6 == 5){
    while(curr % 6 != 3)curr++;
    vec[4] = curr;
  }
  sort(vec.begin(), vec.end());
  rep(i, n){
    cout << vec[i];
    if(i == n - 1)cout << endl;
    else cout << " ";
  }
	return 0;
}


Measured memory_bytes: 512
A,B,C,D,E,F = gets.split.map(&:to_i)

le = E.to_f/100

m = 0.0
v1,v2 = [A*100,0]
rest = F
(0..rest/(100*A)).each{ |a|
  water = a*A*100
  rest = F - water
  (0..rest/(100*B)).each{ |b|
    water = water + b*B*100
    next if water == 0
    rest_sugar = [F - water, water*E/100].min
    sugar = (0..rest_sugar/C).map{ |c|
      sc = c*C
      sd = (rest_sugar - sc)/D*D
      sc + sd
    }.max
    mm = sugar.to_f/water.to_f
    next if mm > le
    next if mm <= m
    #$stderr.puts "#{[a,b,c,d,sugar,water,mm]}"
    m = mm
    v1,v2 = [water,sugar]
  }
}
puts "#{(v1+v2).to_i} #{v2.to_i}"

Measured memory_bytes: 1788
import java.io.*;
import java.util.*;
import java.lang.*;
import java.lang.Math;

class Main{
  public static void main(String[] args) throws IOException{
    Scanner scan=new Scanner(System.in);
    double a=Double.parseDouble(scan.next());
    double b=Double.parseDouble(scan.next());
    int c=Integer.parseInt(scan.next());

    double s=a*b*Math.sin(Math.toRadians(c))/2;
    double l=a+b+Math.sqrt(Math.pow(a,2)+Math.pow(b,2)-2*a*b*Math.cos(Math.toRadians(c)));
    double h=b*Math.sin(Math.toRadians(c));
    System.out.println(s);
    System.out.println(l);
    System.out.println(h);
  }
}


Measured memory_bytes: 26424
#include<bits/stdc++.h>
#define int   long long int  
#define pb push_back
#define BOOST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debugL(i)  cout<<"line no-> "<<i<<" working"<<endl
#define debugVL(i,l)  cout<<"val at line no."<<i<< " ->"<<l<<endl
#define  init(st,et,val,arr) for(int i=st;i<=et;i++)arr[i]=val;
const int M=1e9 + 7;
using namespace std;
int N=200000;
int32_t main() {
	BOOST;
    int n;cin>>n;
    n--;
    int ans=(n*(n+1))/2;
    cout<<ans<<endl;
    return 0;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Measured memory_bytes: 256
(K,N) = map(int,input().split())
A_list = list(map(int,input().split()))
A_list.sort()
dist_min = A_list[N-1]-A_list[0]
for i in range(1,N):
    dist_min = min(dist_min,K-A_list[i]+A_list[i-1])
print(dist_min)

Measured memory_bytes: 26420
#include<bits/stdc++.h>
using namespace std;
#define inf 1001001001

int dp[1000][1000] = {0};
int maps[1000][1000] = {0};
int d[1000] = {0};
int c[1000] = {0};

void id(int i, int j) {
  int res1 = 0;
  int res2 = 0;
  if (i == 0) {
    dp[i][j] = 0;
  }
  else if (i > j) {
    dp[i][j] = inf;
  }
  else {
    res1 = dp[i-1][j-1] + maps[i][j-1];
    res2 = dp[i][j-1];
    dp[i][j] = min(res1 ,res2);
  }
}

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

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

  for (int j = 0; j <= m; j++) {
    for (int i = 0; i <= n; i++) {
      maps[i][j] = d[i-1] * c[j];
    }
  }
  for (int j = 0; j <= m; j++) {
    for (int i = 0; i <= n; i++) {
      id (i, j);
    }
  }

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



Measured memory_bytes: 9360
#include <iostream>

using namespace std;

int main(){
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  
  int a, b, c;
  a = s1[0] - 'a', b = s2[0] - 'a', c = s3[0] - 'a';
  char A, B, C;
  A = a + 'A', B = b + 'A', C = c + 'A';
  cout << A << B << C;
}


Measured memory_bytes: 256
H, W, K = map(int, input().split())
c = list(input() for i in range(H))

result = 0

for i in range(2 ** H):
    h = str(format(i, 'b')).zfill(H)
    for j in range(2 ** W):
        w = str(format(j, 'b')).zfill(W)
        count = 0
        for k in range(H):
            for l in range(W):
                if c[k][l] == "#" and h[k] == "0" and w[l] == "0":
                    count += 1
        if count == K:
            result += 1

print(result)

Measured memory_bytes: 74180
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
string s;
int main()
{
	SPEED;
	cin>>s;
	ll cur=0;
	ll ans=s.length();
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='S')
			cur++;
		else
		{
			if(cur)
				cur--,ans-=2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

#define SIZE 100010

int L[SIZE], R[SIZE];

void solve(int &n, int &m) {
    int lb = 1, ub = n;
    bool flag = true;
    for (int i=0; i<m; ++i) {
        if (R[i] < lb || ub < L[i]) {
            flag = false;
            break;
        }
        lb = std::max(lb, L[i]);
        ub = std::min(ub, R[i]);
    }
    if (!flag || n < lb) {
        std::cout << 0 << std::endl;
    } else {
        std::cout << std::min(n, ub) - lb + 1 << std::endl;
    }
}
int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i=0; i<m; ++i) std::cin >> L[i] >> R[i];
    solve(n, m);
    return 0;
}


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

using namespace std;

using LL = long long int;
using LD = long double;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }

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

	string s;
	cin >> s;
	set<int> se;
	for (auto c : s) se.insert(c);

	int res = INF;
	for (auto c : se) {
		int cur = 0, cnt = 0;
		for (auto c2 : s) {
			if (c == c2) {
				cur = max(cur, cnt);
				cnt = 0;
			} else {
				cnt++;
			}
		}
		cur = max(cur, cnt);
		res = min(res, cur);
	}

	cout << res << endl;
	return 0;
}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);	
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,v)    	memset(x,v,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll ,ll> 			pll;
typedef pair<ld,ld> 			pld;
typedef unordered_map<ll,ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5+7;
const ll 	MAX7 	= 	1e+7+7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9+7;
const ll 	N 		= 	2*1e6;

set<ll> adj[N];ll lvl[N]={};
//int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};

// <------------- Declare Variables Here ------------> //

ll T=1;
ll n,m,p,q,k;
string s,t;

// <------------- Implement Functions Here ----------> //
set<pll,greater<pll>> X,Y;
map<ll,ll> x,y;
set<pll> ppp;

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n >> m >> k;
	for(ll i=0;i<k;i++) {
		cin>>p>>q;
		x[p]++;
		y[q]++;
		ppp.insert({p,q});
	}

	for(auto it : x) {
		X.insert({it.s,it.f});
	}


	for(auto it : y) {
		Y.insert({it.s,it.f});
	}

	
	pll maxx = *(X.begin()) , maxy =  *(Y.begin());
	ll maxi = maxx.f + maxy.f;
	
	if(ppp.find({maxx.s,maxy.s})==ppp.end()) cout<<maxi;
	else {
		vll xx,yy;
		while((*X.begin()).f == maxx.f) {
			xx.pb((*X.begin()).s);
			X.erase(X.begin());
		}	
		while((*Y.begin()).f == maxy.f) {
			yy.pb((*Y.begin()).s);
			Y.erase(Y.begin());
		}	

		for(auto xi : xx) {
			for(auto yi : yy) {
				if(ppp.find({xi,yi})==ppp.end()) {
					cout<<maxi;
					return;
				}
			}
		}

		cout<<maxi-1;
	}
}

int main() {
	fastio;randomINT;
	//cin>>T;
	while(T--) {
		MAIN();
	}
	return 0;
}



Measured memory_bytes: 191132
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> L(N);
    int sum = 0;
    for (int i=0;i<N;i++) {
        cin >> L[i];
        sum += L[i];
    }
    bool ans = true;
    for (int i=0;i<N;i++) {
        if (L[i] >= sum - L[i]) {
            ans = false;
            break;
        }
    }
    cout << (ans ? "Yes" : "No") << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    string S;
    cin >> S;
    if (S[0] == S[1] || S[1] == S[2] || S[2] == S[0])
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[300005], ans;

int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=3*n;i++) scanf("%lld",&a[i]);
	sort(a+1, a+1+3*n);
	for(int i=1;i<=n;i++) {
		ans += a[3*n-2*i+1];
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 2560
#include <cstdio>
using namespace std;
int A[4][4], N; bool C[4][4];
int main() {
  for(int i = 1; i <= 3; ++i) {
    for(int j = 1; j <= 3; ++j) {
      scanf("%d", &A[i][j]);
    }
  }
  scanf("%d", &N);
  for(int i = 1, b; i <= N; ++i) {
    scanf("%d", &b);
    for(int j = 1; j <= 3; ++j) {
      for(int k = 1; k <= 3; ++k) {
        if(A[j][k] == b) C[j][k] = true;
      }
    }
  }
  bool bingo = false;
  if(C[1][1] && C[2][2] && C[3][3]) bingo = true;
  if(C[1][3] && C[2][2] && C[3][1]) bingo = true;
  for(int i = 1; i <= 3 && !bingo; ++i) {
    if(C[i][1] && C[i][2] && C[i][3]) bingo = true;
    if(C[1][i] && C[2][i] && C[3][i]) bingo = true;
  }
  printf("%s\n", bingo?"Yes":"No");
}

Measured memory_bytes: 128
from collections import deque

int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int1, input().split())
    G[a].append(b)
    G[b].append(a)

# bfs
ans_lst = [None] * N
ans_lst[0] = 0
D = deque([0])
while D:
    v = D.popleft()
    for x in G[v]:
        if ans_lst[x] is None:
            ans_lst[x] = v
            D.append(x)
print('Yes')
for x in ans_lst[1:]:
    print(x + 1)


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

const ll INF = pow(10, 9) + 7;

  
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint f(int n){
  if(n==0) return 1;
  mint x = f(n/2);
  x *= x;
  if(n%2==1) x *=2;
  return x;
};

mint choose(int n, int k){
  mint x=1,y=1;
  rep(i,k){
    x *= n-i;
    y *= i+1;
  }
  return x/y;
};
int main() {
  int n,a,b;
  cin >> n >> a >> b;
  mint ans = f(n);
  ans -= 1;
  ans -= choose(n,a);
  ans -= choose(n,b);
  cout << ans.x << endl;
}


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

#include <fstream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  /*
  ifstream in("input.txt");
  cin.rdbuf(in.rdbuf());
  //*/
  int N, K;
  cin >> N >> K;
  unordered_set<char> s;
  for(int i = 0; i < K; i++){
    char d;
    cin >> d;
    s.insert(d);
  }
  bool good = true;
  for(int i = 0; i < 1000000; i++){
    good = true;
    string S = to_string(N+i);
    for(int j = 0; j < S.size(); j++){
      if(s.count(S[j])){
        good = false;
        break;
      }
    }
    if(good){
      cout << N + i <<endl;
      return 0;
    }
  }
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
#define ll  long long
#define dd long double
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,a,b;cin>>n>>a>>b;
    if(n==2){
        cout<<1<<endl;
        return 0;
    }
    ll abs1=abs(b-a);
    if(abs1%2==0)cout<<abs1/2<<endl;
    else if(abs1==1){
         ll mn=min(max(abs(n-a),abs(n-b)),max(abs(1-b),abs(1-a)));
         cout<<mn<<endl;
    }
    else{
        ll bad1=abs(1-a)+1;
        ll bad2=b-bad1;
        ll ogo=abs(1-bad2)/2;
        ll mn=bad1+ogo;
       /// cout<<"mn1 = "<<mn<<endl;
        bad1=abs(n-b)+1;
         bad2=a+bad1;
         ll mn2=(abs(n-bad2)/2)+bad1;
        /// cout<<"mn2 = "<<mn2<<endl;
         mn=min(mn,mn2);
        cout<<mn<<endl;
    }

    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
#include <random>
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 ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int D;

int calc_score(vector<int>& t, vector< vector<int> >& s, vector<int>& c) {
    vector<int> last(26, 0);
    int ans = 0;
    FOR(d, 1, D) {
        ans += s[d-1][t[d-1] - 1];
        last[t[d-1] - 1] = d;
        REP(i, 26) {
            ans -= c[i] * (d - last[i]);
        }
    }
    return ans;
}

int rand_contest() {
    return rand() % 26 + 1;
}

int rand_day() {
    return rand() % D + 1;
}

int main() {
    cin >> D;
    vector<int> c(26);
    REP(i, 26) cin >> c[i];
    vector< vector<int> > s(D+1, vector<int>(26));
    REP(i, D) REP(j, 26) cin >> s[i][j];

    vector<int> t(D, 1);
    int M = 10;
    int score = calc_score(t, s, c);
    REP(trial, M) {
        int contest = rand_contest();
        int day = rand_day();
        int old_contest = t[day-1];
        t[day-1] = contest;
        int v = calc_score(t, s, c);
        if(v > score) {
            score = v;
        } else {
            t[day-1] = old_contest;
        }
    }

    cerr << "final score = " << score << endl;
    REP(i, D) {
        cout << t[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    rep(i, n) {
        int u, k;
        cin >> u >> k;
        u--;
        rep(j, k) {
            int v;
            cin >> v;
            v--;
            g[u].push_back(v);
        }
    }
    vector<int> d(n, -1);
    queue<int> q;
    q.push(0);
    d[0] = 0;
    while (sz(q)) {
        int now = q.front();
        q.pop();
        for (int nxt : g[now]) {
            if (d[nxt] != -1) continue;
            d[nxt] = d[now] + 1;
            q.push(nxt);
        }
    }
    rep(i, n) cout << i + 1 << " " << d[i] << endl;
}


Measured memory_bytes: 3164
// ref. https://www.youtube.com/watch?v=v8ppNGf49Nk

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

const int K = 43;

// dp[i][j][k] .. i: digit i, j: carry, k: 0 .. eqal or smqll, 1 .. large. maximum number.
ll dp[K][2][2];

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  vector<ll> _a(n);
  rep(i,n) {
    cin >> _a[i];
  }
  ll x = 0;
  for (int i = 2; i < n; ++i) {
    x ^= _a[i];
  }
  ll a = _a[0], b = _a[1];
  ll s = a+b;

  // Digit dp
  // initialize
  rep(i,K)rep(j,2)rep(k,2) {
    dp[i][j][k] = -1;
  }
  dp[0][0][0] = 0;
  ll v = 1;
  rep(i,K-1) {
    int cx = x&1;
    int cs = s&1;
    int ca = a&1;
    rep(j,2)rep(k,2) {
      if (dp[i][j][k] == -1) { continue; } // invalid
      rep(na,2)rep(nb,2) {
        int ni = i+1;
        int nj = 0, nk;
        if ((na^nb) != cx) { continue; } // invalid.
        int ns = na+nb+j;
        if (ns%2 != cs) { continue; } // invalid.
        if (ns >= 2) { nj = 1; } // carry
        if (ca < na) {
          nk = 1;
        } else if (ca == na) {
          nk = k;
        } else { // ca > na
          nk = 0;
        }
        chmax(dp[ni][nj][nk], dp[i][j][k]|(v*na));
      }
    }
    x >>= 1;
    s >>= 1;
    a >>= 1;
    v <<= 1;
  }

  // For Debug
  // rep(i,K) {
  //   rep(j,2)rep(k,2) {
  //     cout << dp[i][j][k] << " ";
  //   }
  //   cout << endl;
  // }
  // For Debug
  // cout << "a': " << dp[K-1][0][0] << endl;

  if (dp[K-1][0][0] <= 0) { // 0 or -1
    cout << -1 << endl;
  } else {
    cout << (_a[0] - dp[K-1][0][0]) << endl;
  }
}


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

using namespace std;

int main(){
  int N,ans=10000000;
  cin >> N;
  vector<int> ary(N);

  for(int i = 0 ; i < N ; i++){
    cin >> ary[i];
  }
  sort(ary.begin(),ary.end());
  for(int i = 1 ; i <= ary[N-1] ;i ++){
    int P = i;
    int tmp = 0;
    for(int j = 0 ; j < N ; j++){
            tmp += (ary[j] - P) * (ary[j] - P);
    }
    if(ans > tmp){
      //cout << "tmp is refresh " << tmp << " when p is " << P << endl;
      ans = tmp;
    }else{
      break; 
    }
  }

    cout << ans << endl;
}


Measured memory_bytes: 3632