akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

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

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

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int dp[N];
int ans, res;
int cur;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mult (int a, int b) {
	return a * (ll)b % mod;
}

void add (int &a, int b) {
	a += b;
	if (a >= mod) a-=mod;
	if (a < 0) a += mod;
}


int bpow (int a, int b) {
	int res = 1;
	while(b > 0) {
		if (b&1) res = mult(a, res);
		a = mult(a, a);
		b /= 2;
	}
	return res;
}

int main () {
	SpeedForce;
	cin >> n >> k;
	int ans = 0;
	for (int i = k; i >= 1; --i) {
		int cnt = 0;
		for (int j = i; j <= k; j += i)
			++cnt;
		dp[i] = bpow(cnt, n);
		for (int j = i + i; j <= k; j += i) {
			add(dp[i], -dp[j]);
		}
		add(ans, mult(dp[i], i));
	}
	cout << ans << '\n';

	return Accepted;
}

// B...a

Measured memory_bytes: 18076
Scanf.scanf "%d" (fun n ->
    let a = Array.init n (fun _ -> Scanf.scanf " %d" (fun a -> a)) in
    Array.sort compare a;

    let rec loop rest c acc =
        if rest = 0 then acc else
            if rest > 1 then loop (rest - 2) (c - 1) (acc + a.(c) * 2)
                        else loop (rest - 1) (c - 1) (acc + a.(c))
    in
    loop (n - 2) (n - 2) a.(n - 1) |> Printf.printf "%d\n"
)


Measured memory_bytes: 7560
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll div[n+2]={0};
    ll sum=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=i)div[j]++;
    }
    for(int i=1;i<=n;i++)sum+=(i*div[i]);
    cout<<sum<<endl;
}


Measured memory_bytes: 81708
#include<bits/stdc++.h>
using namespace std;
string s;
int ans;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>s;
	for(int i=0;i<s.length();i++)
		if(s[i]=='o')
			ans++;
	if(ans+15-s.length()>=8)
		cout<<"YES";
	else
		cout<<"NO";
	return 0;
}


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

namespace AtCoder_solve
{
    class Program
    {
        public const ulong mod = 1000000007;

        static void Main(string[] args)
        {
            var n = Input();
            var a = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long ans = 0;

            for(int i = 1; i < n; i++)
            {
                if (a[i - 1] > a[i])
                {
                    ans += a[i - 1] - a[i];
                    a[i] = a[i - 1];
                }
            }

            Console.WriteLine(ans);





        }

        static public long Input()
        {
            return long.Parse(Console.ReadLine());
        }

        static public string[] Input2()
        {
            return Console.ReadLine().Split();
        }
        
        static public long[] Input3()
        {
            string[] data = Console.ReadLine().Split();
            long[] res = new long[data.LongLength];
            for(long i = 0; i < data.LongLength; i++)
            {
                res[i] = long.Parse(data[i]);
            }
            return res;
        }
        public static long Choose(long n, long a)
        {
            long x = 1;
            long y = 1;
            for (long i = 0; i < a; i++)
            {
                x *= n - i;
                y *= i + 1;
            }
            return x / y;
        }

        public static long Gcd(long a, long b)
        {
            long x = Math.Max(a, b);
            long y = Math.Min(a, b);
            if (x % y == 0) return y;
            else return Gcd(y, x % y);
        }
    }
}


Measured memory_bytes: 47444
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int N = 1e5+5;

int n,m,f[N],ans;
int get(int x) {return x==f[x]?x:f[x]=get(f[x]);}
void join(int a, int b){
	int fa=get(a), fb=get(b);
	if(fa!=fb){
		f[fa] = fb;
		--ans;
	}
}

int main(){
	scanf("%d%d", &n, &m);
	ans = n;
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=0;i<m;++i){
		int a,b,z;
		scanf("%d%d%d", &a, &b, &z);
		join(a, b);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 640
N = int(input())
h_ls = [int(i) for i in input().split()]
memo_ls = [0 for i in range(N)]
memo_ls[-2] = abs(h_ls[-1] - h_ls[-2])
for i in range(3,N+1):
    memo_ls[-i] = min(memo_ls[-i+1] + abs(h_ls[-i] - h_ls[-i+1]),
                        memo_ls[-i+2] + abs(h_ls[-i] - h_ls[-i+2]))
print(memo_ls[0])

Measured memory_bytes: 13928
/* Life is all about calculated risks.
    But man am I bad at math. */

#include <bits/stdc++.h> 
#define ll long long int
#define INF (ll)1e12
#define MOD 1000000007
#define double long double

#define DEBUG(x) cerr<<"> "<< #x << ':' <<x<<endl;

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll L;
    cin>>L;

    double l = (double)((double)((double)L/3));

    printf("%0.12Lf\n",(l*l*l));

    return 0;
}

Measured memory_bytes: 256
n =int(input())
a = list(map(int,input().split()))

seta = sorted(list(set(a)))

resn = seta[-1]
resr = seta[0]
for sa in seta:
    sabun = abs(resn / 2 - sa)
    if sabun  == 0 or sabun == 0.5:
        resr = sa
        break
    elif sabun < abs(resn / 2 - resr):
        resr = sa

print(str(resn) + " " + str(resr))

Measured memory_bytes: 15712
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int> > Matrix;


int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  int m;
  cin >> m;
  vector<string> t(m);
  rep(i, m) cin >> t[i];
  int ans = -1000;
  for (int i = 0; i < n; i++){
    int score = 0;
    for (int j = i; j < n; j++){
      if (s[i] == s[j]) score++;
    }
    for (int j = 0; j < m; j++){
      if (s[i] == t[j]) score--;
    }
    ans = max(ans, score);
  }
  
  if (ans < 0) cout << 0;
  else cout << ans;
  cout << endl;
  
}

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

ans = 0

a = []
for i in A:
    ans += abs(i)
    a.append(abs(i))

gusu = False

count = 0
for i in A:
    if i == 0:
        gusu = True
        break
    if 0 > i:
        count += 1

if count % 2 == 0:
    gusu = True

if gusu == True:
    print(ans)
else:
    print(ans - min(a)*2)

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

int main(){
    string s,t;
    cin>>s>>t;
    int ans=0;
    for (int i = 0; i <3; ++i) {
        if(s[i]==t[i])ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
const int mod= 1e+9+7;

int main() {
    string S;
    cin>>S;
    int n =S.size();
    for(int i=0;i<n/2;i++){
        if(S[i]!=S[n-1-i]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    for(int i=0;i<(n-1)/4;i++){
        if(S[i]!=S[(n-1)/2-1-i]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    for(int i=(n+3)/2;i<n;i++){
        if(S[i]!=S[n-1-i]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

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

int main() {
 long long n,sum=0;
  cin >> n;
 vector<int> a(n);
 vector<int> b(n);
 vector<int> c(n-1);
 vector<int> d;

 for(int i=0;i<n;i++){
   cin >> a[i];
   if(a[i]==a[i-1]+1){
     d.push_back(a[i-1]-1);
   }
  }

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

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


 for(int i=0;i<d.size();i++){
   sum+=c[d[i]];
 }
 cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define per(i,n) for(long long i = (long long)(n-1);i >= 0;--i)
#define REP(i,s,t) for(long long i=s;i<t;i++)
#define PER(i,s,t) for(long long i=s;i>t;--i)
#define all(x) x.begin(),x.end()
#define sp(n) setprecision(n)
typedef long long ll;
using namespace std;
int main(){
  char a;
  cin>>a;
  string s;
  s="abcdefghijklmnopqrstuvwxyz";
  int k=0;
  rep(i,25){if(a==s[i]){k=i+1;}}
  cout<<s[k]<<endl;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true; } return false; }
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true; } return false; }

//INT_MAX	2,147,483,647 = 2*1.0e9

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

  set<string> st;
  string w; cin >> w;
  char last = w[w.size()-1];
  st.insert(w);

  for(int i = 1; i < N; i++){
    string wtmp; 
    cin >> wtmp;
    auto it = st.find(wtmp);
    if(it != st.end()) {
      cout << "No" << endl;
      return 0;
    }
    if(wtmp[0] != last){
      cout << "No" << endl;
      return 0;
    }
    last = wtmp[wtmp.size()-1];
    st.insert(wtmp);
  }

  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long

using namespace std;

int main(){

  int N, M;
  cin >> N >> M;
  int ans = 0;

  if(N >= 2){
    ans += (N*(N-1))/2;
  }
  if(M >= 2){
    ans += (M*(M-1))/2;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
a_list = [int(x) for x in input().split()]
left_flag = n % 2 == 1
d = deque()
for a in a_list:
    if left_flag:
        d.appendleft(a)
    else:
        d.append(a)
    left_flag = not left_flag
print(*d)

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;

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

static const int MAX_N = 2999;

double p[MAX_N+1];
double dp[MAX_N+1][MAX_N+1];

void solve() {
  // dp[i][j]
  dp[0][0] = 1.0;
  rep(i, 1, MAX_N+1) {
    rep(j, 0, i+1) {
      if (j == 0) {
        dp[i][j] = dp[i-1][j] * (1.0 - p[i]);
      } else {
        dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1.0 - p[i]);
      }
    }
  }
};

int main() {
  int N;
  cin >> N;
  rep(i, 1, N+1) {
    cin >> p[i];
  }

  solve();

  double ans = 0.0;
  rep(j, 0, N+1) {
    if (j >= (N/2 + 1)) {
      ans += dp[N][j];
    }
  }

  printf("%.10f\n", ans);
};


Measured memory_bytes: 68864
#include<stdio.h>
int main(void)
{
 int N,M,A,i;
 int S=0;
 scanf("%d",&N);
 scanf("%d",&M);
 for(i=1;i<=M;i++){
 scanf("%d",&A);
 S+=A;
 }
 if(N>=S)
 printf("%d",N-S);
 else 
 printf("-1");
  
 return 0;
}


Measured memory_bytes: 1732
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = input()
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    # A = []
    # cnt = 0
    # for i in range(len(n)):
    #     A.append((n[i]))
    #     if n[i] == "?":
    #         cnt += 1

    N = list(n)
    for i in range(len(N)):
        if N[i] == "?":
            N[i] = "D"

    print("".join(N))

resolve()

Measured memory_bytes: 74312
import math

def s(n):
    ret = 0

    while n > 0:
        ret += n % 10
        n = n // 10
        
    return ret

def snuke(n):
    candidate = []

    for d in range(int(math.log(n, 10)) + 2):
        x = n - (n % 10**d) + (10**d - 1)
        candidate.append(x)
    
    min_value = candidate[0] / s(candidate[0])
    ans = candidate[0]
    for c in candidate[1:]:
        tmp = c / s(c)
        if tmp < min_value:
            min_value = tmp
            ans = c
            
    return ans

K = int(input())

N = 0
for i in range(K):
    N = snuke(N + 1)
    print(N)
        

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

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

  map<int, int> mp;
  for (int i = 0; i < N; i++) mp[a[i]]++;

  int ans = 0;
  for (auto p: mp) {
	int x = p.first;
	int n = p.second;
	if (n < x) ans += n;
	else ans += n - x;
  }
  cout << ans << endl;
  return 0;
}


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

int main() 
{
   string s1, s2, s3;
   cin >> s1 >> s2 >> s3;

   cout << char(s1.at(0) - 32) << char(s2.at(0) - 32) << char(s3.at(0) - 32) << endl;
}


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

using db = double;
using ll = long long;
using vi = vector <int>;
#define op operator
#define pb push_back

int main() {
	cout << fixed << setprecision(9);
	ios :: sync_with_stdio(0);

	int a, b, c;
	while(cin >> a >> b >> c) {
		int cnt = 0;
		for(int i = 1; i <= 10; i ++)
			if(a + b + i <= 20 && i != a && i != b && i != c)
				cnt ++;
		cout << (cnt >= 4 ? "YES" : "NO") << '\n';
	}

	return 0;
}

Measured memory_bytes: 3004
#include<stdio.h>
int main()
{
    char ch;
    long int a,b,sum;
    scanf("%ld %c %ld",&a,&ch,&b);
    if((a>=1&&a<=1000000000)&&(b>=1&&b<=1000000000)){
        if(ch=='+'){
            sum=a+b;
            printf("%ld\n",sum);
        }
        else if(ch=='-'){
            sum=a-b;
            printf("%ld\n",sum);
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,ans=4113;
int countmit(int i)
{
	int ret=0;
	while(i)
	{
		ret+=i%10;
		i/=10;
	}
	return ret;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
		ans=min(ans,countmit(i)+countmit(n-i));
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
using namespace std;
/*
struct Monoid {
    using T = _underlying_set_;
    static  T op(const T& a, const T& b) { return _a_op_b_; }
    static constexpr T id() { return _identity_element_; }
    static T update(const T& a,const T& b) {return _a_update_b_;}
};
*/

template <class Monoid>
class SegTree {
   private:
    using T = typename Monoid::T;
    const size_t n;
    vector<T> t;
    void prop_to(size_t i) { t[i] = Monoid::op(t[2*i+1],t[2*i+2]); }
    // 更新
   public:
    SegTree(size_t m,T val) : n(m){
        t.resize(2*n-1,Monoid::id());
        for (long long i = 0;i < n;i++) t[i+(n-1)] = val;
        for (long long i = (n-2); i >= 0; --i) prop_to(i);
    }

    SegTree(vector<T> &a)
        : n(a.size()){ 
        t.resize(2*n-1,Monoid::id());
        for (long long i = 0;i < n;i++) t[i+(n-1)] = a[i];
        for (long long i = (n-2); i >= 0; --i) prop_to(i);
    }

    T operator[](size_t i) {return t[i+(n-1)];} // 列のi番目を返す

    void update(size_t i, const T& v) { // 列のi番目に対し、vを作用。
        t[i += (n-1)] = Monoid::update(t[i],v);
        while (i && ((--i) >>= 1)) prop_to(i);
        if(n >= 2) prop_to(0);
    }

    T find(size_t l, size_t r) { // [l,r)の範囲で見つける。
        T accl = Monoid::id(), accr = Monoid::id();
        for (l += (n-1), r += (n-1); l < r; l >>= 1, (--r) >>= 1) {
            if(!(l & 1)) accl = Monoid::op(accl, t[l]);
            if(!(r & 1)) accr = Monoid::op(t[r-1], accr);
        }
        return Monoid::op(accl, accr);
    }
};

struct RSQ { //区間の合計
    using T = long long;
    static T op(const T&a,const T& b) {return a+b;}
    static constexpr T id() {return 0;}
    static T update(const T& a,const T& b) {return a+b;}
};

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N;
    cin >> N;
    vector<long long> a(N);
    vector<long long> sub_mid(N+1);
    REP(i,N) cin >> a[i];

    // aの降順ソート
    vector<long long> sorted_a(a);
    sort(sorted_a.begin(), sorted_a.end(), greater<long long>() );

    // 二分探索
    long long pairn = (N+1)*(N)/2;
    long long ng = (-1);
    long long ok = a.size() - 1;

    while (abs(ok - ng) > 1) {
        long long mid_idx = (ok + ng) / 2; // 中央値の候補のindex
        long long mid = sorted_a[mid_idx]; // 中央値の候補
        sub_mid[0] = 0; // 余分に作る

        long long potential = 0;
        REP(i,N) {
            // 中央値の候補以上 -> 1 , その他 -> -1 に置き換え.
            if (a[i] >= mid) sub_mid[i+1] = 1; 
            else sub_mid[i+1] = (-1);

            // 累積和
            sub_mid[i+1] += sub_mid[i];
            // 後でsub_midから負の値をなくす用.
            potential = min(sub_mid[i+1],potential);
        }

        // BITとして使う.転倒数 inversion を算出.
        SegTree<RSQ> sg(N+1,0);
        long long inversion = 0;
        REP(i,N+1) {
            inversion += (i - sg.find(0,(sub_mid[i]-potential)+1));
            sg.update((sub_mid[i]-potential),1);
        }

        // pairn - inversion : Sl <= Srの通り数 
        // if ( (pairn - inversion)*2 >= pairn ) <=>
        if (pairn >= inversion*2) ok = mid_idx;
        else ng = mid_idx;
    }
    cout << sorted_a[ok] << endl;
}




Measured memory_bytes: 4224
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
#include<string>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)

int main(){
	int N;	
	string str1,str2;
	cin>>N;
	cin>>str1;
	cin>>str2;

	ll answer = 1;

	ll flag = 3;	
	for(int i = 0; i < N; i++){

		if(str1[i] == str2[i]){

			answer *= flag;

			answer = answer % 1000000007;
			flag = 2;
		}
		else{
			if(flag == 1){
				flag = 3;
				answer *= flag;
				answer = answer % 1000000007;
				i++;
				flag = 1;
			}
			else{
				answer *= flag;
				answer = answer % 1000000007;
				flag -= 1; 
				answer *= flag;
				answer = answer % 1000000007;
				flag = 1;
				i++;
			}
		}
	}

	cout<<answer<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b,array[]={1,0,1,2,1,2,1,1,2,1,1,2,1};
  cin>>a>>b;
  if(array[a-1]==array[b-1]){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x, y;  
  cin >> x >> y;
  if((4*x-y)%2 == 0 && y <= 4*x && 4*x <= 2*y){
  	cout << "Yes"<<endl;
  }
  else{
    cout <<"No" <<endl;
  }
}

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

#define ll long long

template<typename T> void drop(const T &x){cout<<x<<'\n';exit(0);}

void solve() {
  int m; cin >> m;
  cout << 48-m << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T=1;
  //cin >> T;
  while(T--) solve();

  return 0;
}


Measured memory_bytes: 3604
//set many funcs template
//Ver.20190820
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#include<math.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384

long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}

long long x[16],y[16],n;
double c=0.0;

void rep(long long pv,double len,long long fl,long long cnt){
  double d;
  if(cnt==n){
    c+=len;
    return;
  }
  long long i;
  for(i=0;i<n;i++){
    if(cnt>=1){
      d=sqrt(llzt(x[pv],x[i])*llzt(x[pv],x[i])+llzt(y[pv],y[i])*llzt(y[pv],y[i]));
    }
    if(!(fl&(1ll<<i))){
      rep(i,len+d,fl|(1ll<<i),cnt+1);
    }
  }
}

int main(void){
  long long i,j,m,k,a[524288],b,h,w,r=0,l,t;
  scanf("%lld",&n);
  for(i=0;i<n;i++){
    scanf("%lld%lld",&x[i],&y[i]);
  }
  rep(-1,0.0,0,0);
  printf("%.12lf\n",((double)c)/((double)llfact(n)));
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(a,i,n) for(int i=0;i<n;i++){cin>>a[i];}


int main(){
  vector<int> v[1000];
  int n,q;
  cin>>n>>q;
  lp(i,q){
    int a,b,c;
    cin>>a>>b;
    if(a==0){
      cin>>c;
      v[b].push_back(c);
    }
    if(a==1){
      for(int j=0;j<v[b].size();j++){
	if(j!=0) cout<<" ";
	cout<<v[b][j];
      }
      cout<<endl;
    }
    if(a==2){
      v[b].clear();
    }
  }
  return 0;
}



Measured memory_bytes: 5784
fun main(args: Array<String>) = println(run {
    val (l, r) = readLine()!!.split(" ").map { it.toInt() }

    if (r - l >= 2019) return@run 0

    (l..r-1).map { i ->
        (i+1..r).map { j ->
            ((i%2019) * (j%2019)) % 2019
        }.min()!!
    }.min()!!

})

Measured memory_bytes: 49144
N,K=gets.split.map &:to_i
as=gets.split.map &:to_i

class Integer
    def divisor_list
        return [1] if self == 1
        (1..Math.sqrt(self).to_i).select do |i|
            self%i == 0
        end.map {|e| [e, self/e]}.flatten.uniq.sort
    end
end

cand=as.inject(:+).divisor_list
cand.reverse.each do |m|
    as_mod=as.map{|i|m-i%m}.sort.reverse
    rcnt=as_mod.inject(:+)
    lcnt=0
    for i in 0..as_mod.size-2
        rcnt+=-as_mod[i]
        lcnt+=-(m-as_mod[i])
        if rcnt % m == -lcnt % m && [rcnt,-lcnt].max <= K
            puts m
            exit 0
        end
    end
end


Measured memory_bytes: 1916
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y, z, t = map(int, readline().split())
a = sorted(map(int, readline().split()), reverse=True)
b = sorted(map(int, readline().split()), reverse=True)
c = sorted(map(int, readline().split()), reverse=True)

ans = []

for i in range(len(a)):
    for j in range(len(b)):
        ans.append(a[i] + b[j])

ans = sorted(ans, reverse=True)
fin_ans = []
for j in range(len(c)):
    for i in range(min(len(ans), t)):
        fin_ans.append(ans[i] + c[j])

fin_ans = sorted(fin_ans, reverse=True)

for i in fin_ans[:t]:
    print(i)

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






// https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/
vector<int> z_algo( const string &s ){
	int len = s.length();
	vector<int> Z(len);
	Z[0] = len;
	
	// LとR: 区間[L,R]が、文字列先頭の区間[0,R-L]と一致していることを表す
	int L = 0, R = 0;
	
	for ( int i = 1; i < len; i++ ){
		
		if ( R < i ){
			L = R = i;
			while ( R < len && s[R-L] == s[R] )
				R++;
			Z[i] = R-L;
			R--;
		}
		else {
			int k = i-L;
			
			if ( Z[k] < R-i+1 ){
				Z[i] = Z[k];
			}
			else {
				L = i; 
				
				while ( R < len && s[R-L] == s[R] )
					R++;
				Z[i] = R-L;
				R--;
			}
		}
	}
	
//	cout << s << endl;
//	for ( auto it : Z )
//		cout << it << " ";
//	cout << endl;
	
	return Z;
}

// 周期を調べる
int get_period( const vector<int> z ){
	int len = z.size();
	
	for ( int i = 1; i <= len / 2; i++ ){
		if ( i + z[i] == len && len % i == 0 ){
			return i;
		}
	}
	return len;
}




int main(){
	string s, t;
	cin >> s;
	cin >> t;
	
	int slen = s.size();
	int tlen = t.size();
	auto zs = z_algo(s);
	auto zt = z_algo(t);
	
	int period_s = get_period(zs);
	int period_t = get_period(zt);
	
	if ( period_s == period_t ){
		// 無限かどうか調べる。周期が同じで、周期以上の長さの部分一致があれば無限
		string sxtt = s + "X" + t + t;
		auto z_sxtt = z_algo(sxtt);
		for ( int i = 0; i < period_s; i++ ){
			if ( z_sxtt[slen+1+i] >= period_s ){
				cout << "-1" << endl;
				return 0;
			}
		}
	}
	
	
	// ttXsss...sX の文字列を作る
	int ssslen = slen*2+tlen*2;
	string sss(ssslen, ' ');
	for ( int i = 0; i < ssslen; i++ )
		sss[i] = s[i%slen];
	string ttxsss = t + t + "X" + sss + "X";
	auto z = z_algo(ttxsss);
	int pos = tlen*2+1;
	
	int max_repeat = 0;
	vector<int> ct(ssslen); // ct[i] : 位置iで一致回数を調べるとき、それより前に ct[i]回分の一致があることを表す
	for ( int i = 0; i < ssslen; i++ ){
		if ( z[pos+i] >= tlen ){
			// この位置から数えると、少なくとも1回分の長さの一致がある。
			max_repeat = max( max_repeat, ct[i]+1 );
			if ( i+tlen < ssslen )
				ct[i+tlen] = ct[i]+1;
		}
	}
	
	cout << max_repeat << endl;
	
	return 0;
}



Measured memory_bytes: 30564
#include<iostream>
#include<bitset>
using namespace std;
int henkan1(int x) {
	int y;
	switch (x) {
	case 0:y = 0b0111111; break;
	case 1:y = 0b0000110; break;
	case 2:y = 0b1011011; break;
	case 3:y = 0b1001111; break;
	case 4:y = 0b1100110; break;
	case 5:y = 0b1101101; break;
	case 6:y = 0b1111101; break;
	case 7:y = 0b0100111; break;
	case 8:y = 0b1111111; break;
	case 9:y = 0b1101111; break;
	default:break;
	}
	return y;
}
int henkan1(int x,int i) {
	if (!i)return 0;
	int y;
	switch (x) {
	case 0:y = 0b0111111; break;
	case 1:y = 0b0000110; break;
	case 2:y = 0b1011011; break;
	case 3:y = 0b1001111; break;
	case 4:y = 0b1100110; break;
	case 5:y = 0b1101101; break;
	case 6:y = 0b1111101; break;
	case 7:y = 0b0100111; break;
	case 8:y = 0b1111111; break;
	case 9:y = 0b1101111; break;
	default:break;
	}
	return y;
}
int henkan2(int x, int y,int i) {
	return henkan1(x,i) ^ henkan1(y);
}
int main() {
	int n;
	while (true) {
		cin >> n;
		if (n == -1)return 0;
		for (int i = 0; i < n; i++) {
			int x, y;
			cin >> y;
			cout << static_cast<bitset<7>>(henkan2(x, y, i)) << endl;
			x = y;
		}
	}
	return 0;
}

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

using namespace std;

typedef long long int llint;

int N;

int main() {
	cin >> N;
	vector<llint> H(N);
	for (int i = 0; i < N; i++) { 
		cin >> H[i];
	}

	bool ans = true;
	for (int i = 1; i < N; i++) {
		if (H[i] > H[i - 1]) { H[i]--; }
		if (H[i] < H[i - 1]) { ans = false; break; }
	}
	if (ans) { cout << "Yes" << endl; }
	else { cout << "No" << endl; }
}

Measured memory_bytes: 1152
#include <stdio.h>

int main(void) {
	long long i,n,buy,tbuy = 0;
	scanf ("%lld",&n);
	for (i = 1;i <= n;i++){
		scanf("%lld",&buy);
		tbuy = tbuy + buy;
	}
	printf("%lld\n",tbuy / n);
	return 0;
}

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

const int N = 2e5 + 10;

int a[N];
long long pre[N];

int main(){
	int n, cnt;
	long long ans;
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
	pre[0] = 0;
	for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
	sort(pre, pre + n + 1);
	cnt = 1; ans = 0;
	for (int i = 1; i <= n; i++){
		if (pre[i] > pre[i - 1]){
			ans += 1LL * cnt * (cnt - 1) / 2;
			cnt = 1;
		}
		else cnt++;
	}
	ans += 1LL * cnt * (cnt - 1) / 2;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2560
import heapq
from collections import defaultdict

N, M = map(int, input().split())
d = defaultdict(list)
for i in range(N):
    A, B = map(int, input().split())
    d[A].append(-B)

ans = 0
work = []
for i in range(1, M+1):
    for j in range(len(d[i])):
        heapq.heappush(work, d[i][j])
    if len(work):
        ans -= heapq.heappop(work)
print(ans)

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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
vector<int> to[100100];
int dist[100100][3];
const int inf = 1e9+7;
int main()
{
	int n,m,s,t;
	cin >> n >> m;
	rep(i,m){
		int x, y;
		cin >> x >> y;
		--x, --y;
		to[x].push_back(y);
	}
	cin >> s >> t;
	--s, --t;
	// 状態を3つ持つ。
	rep(i,n)rep(j,3)dist[i][j] = inf;
	dist[s][0] = 0;
	queue<P> q;
	q.push({s,0});
	while(!q.empty()){
		int v = q.front().first;
		int type = q.front().second;
		q.pop();
		int d = dist[v][type]; 
		int nd = d;
		if(type == 2) nd += 1;

		int ntype = (type + 1)%3;
		for(int nv : to[v]){
			if(dist[nv][ntype] != inf) continue;
			dist[nv][ntype] = nd;
			q.push({nv,ntype});
		}
	}

	int ans =  dist[t][0];
	cout << (ans == inf ? -1 : ans) << endl;
}



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

int main(){
	int n; cin >> n;
	map<long long, int> m; 
	for (int i = 0; i < n; ++i) {
		long long k; cin >> k;
		m[k]++;
	}
	vector<long long> v; map<long long, int> s;
	for (auto it = m.begin(); it != m.end(); ++it) {
		v.push_back(it->first); 
	}
	sort(v.begin(), v.end(), greater<long long>());
	for (int i = 0; i < n; i++) {
		s[v[i]] = i;
	}
	long long d = 1LL << 32; int ans = 0;
	for (int i = 0; i < n; i++) {
		while (d/2 > v[i]) {
			d /= 2;
		}
		long long c = d - v[i];
		if (m[c] > 0) {
			int tmp = min(m[v[i]], m[c]);
			if (v[i] == c) tmp = m[c] / 2;
			ans += tmp; m[v[i]] -= tmp; m[c] -= tmp;
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
        ll N; cin >> N;
        vector<ll> L;

        L.push_back(2);
        L.push_back(1);

        for (int i = 2; i <= N; ++i) {
                L.push_back(L[i-1] + L[i-2]);
        }
        cout << L[N] << endl;


}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>

using namespace std;

const int MOD = 1000000007;
typedef long long ll;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c;
  cin>>a>>b>>c;
  
  cout<<max({a,b,c})*9+a+b+c<<endl;
}


Measured memory_bytes: 256
/*
TASK: AGC143 - F - Many Slimes
LANG: C++
NAME: picolylamine
*/
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define N_MAX 20
#define S_MAX 300000 // >262144

int N, tail;
long long int table[S_MAX], make_table[N_MAX][S_MAX];

void calc()
{
	if (1 != table[tail - 1]){
		printf("No");
		return;
	}

	for (int i = 0; i < N_MAX; i++){
		fill(make_table[i], make_table[i] + S_MAX, 0);
	}

	make_table[0][tail - 1] = 1;
	for (int i = 1; i <= N; i++){
		make_table[i][tail - 1] = 1;
		long long int carry = 0;
		for (int j = tail - 2; j >= 0; j--){
			make_table[i][j] = make_table[i - 1][j + 1] + make_table[i - 1][j] + carry;
			if (make_table[i][j] > table[j]){
				carry = make_table[i][j] - table[j];
				make_table[i][j] = table[j];
			}
			else{
				carry = 0;
			}
		}
		if (0 != carry){
			printf("No");
			return;
		}
	}

	for (int i = 0; i < tail; i++){
		if (table[i] != make_table[N][i]){
			printf("No");
			return;
		}
	}

	printf("Yes");

	return;
}

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);

	scanf("%d", &N);
	int size = pow(2,N), S[S_MAX];
	for (int i = 0; i < size; i++){
		scanf("%d", S + i);
	}

	sort(S, S + size);

	fill(table, table + S_MAX, 0);
	int cur = S[0];
	tail = 0;
	for (int i = 0; i < size; i++){
		if (cur != S[i]){
			tail++;
			cur = S[i];
		}
		table[tail]++;
	}

	tail++;
	calc();

	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

Measured memory_bytes: 50432
import java.util.*;

public class Main {
  public static long MOD = (long)Math.pow(10, 9) + 7;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long n = sc.nextLong();
    long m = sc.nextLong();
    HashMap<Long, Long> map = new HashMap<Long, Long>();
    long s = m;
    for(long i = 2; i * i <= m; i++) {
      while(s % i == 0) {
        s /= i;
        if(map.containsKey(i)) {
          map.put(i, map.get(i) + 1);
        } else {
          map.put(i, (long)1);
        }
      } 
    }
    if(s != 1) map.put(s, (long)1);
    long ans = 1;
    for(long key : map.keySet()) {
      long k = map.get(key);
      long t1 = 1;
      long t2 = 1;
      long t3 = 1;
      for(long i = 1; i <= n + k - 1; i++) {
        t1 = (t1 * i) % MOD;
      }
      for(long i = 1; i <= k; i++) {
        t2 = (t2 * i) % MOD;
      }
      for(long i = 1; i <= n - 1; i++) {
        t3 = (t3 * i) % MOD;
      }
      ans = (ans * t1) % MOD;
      ans = (ans * func(t2, MOD - 2)) % MOD;
      ans = (ans * func(t3, MOD - 2)) % MOD;
    }
    if(m == 1) ans = 1;
    System.out.println(ans);
  }
  public static long func(long a, long t) {
    if(t > 1) {
    if(t % 2 == 0) {
      long c = func(a, t / 2);
      return ((c * c) % MOD);
    } else {
      return ((a * func(a, t - 1)) % MOD);
    }
    } else {
      return a % MOD;
    }
  }
}

Measured memory_bytes: 24404
import scala.io.StdIn._
object Main extends App {

  val str = readLine.trim
  println(
    if (isYYMM(str) && isMMYY(str)) "AMBIGUOUS"
    else if (isYYMM(str)) "YYMM"
    else if (isMMYY(str)) "MMYY"
    else "NA"
  )
  def isYYMM(str: String): Boolean = {
    (1 to 12).contains(str.substring(2, 4).toInt)
  }
  def isMMYY(str: String): Boolean = {
    (1 to 12).contains(str.substring(0, 2).toInt)
  }
}

Measured memory_bytes: 25412
o[256],z[257];main(N,S,A,C,s,a,c,r,i){for(;scanf("%d",&N),N;printf("%d %d %d\n",S,A,C)){
	double H=9,h,n=N;
	for(i=1;i<=N;i++)scanf("%d",z+i);
	for(s=0;s<16;s++)for(a=0;a<16;a++)for(c=0;c<16;c++){
		for(r=s,h=0,i=1;i<=N;i++)o[(z[i]+(r=(a*r+c)%256))%256]++;
		for(i=0;i<256;i++)if(o[i])h-=o[i]/n*log(o[i]/n),o[i]=0;
		if(h+1e-9<H)H=h,S=s,A=a,C=c;
	}
}exit(0);}

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

int main(){
  int N;
  cin >> N;
  vector<string> S(N);

  for(int i = 0;i < N;i++){
    cin >> S.at(i);
  }

  sort(S.begin(),S.end());
  S.erase(unique(S.begin(), S.end()), S.end());

  cout << S.size() << endl;
}


Measured memory_bytes: 9520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


int main(){
    ll n;
    cin >> n;
    if(n%2==0){
        cout << n/2 - 1 << endl;
    }else{
        cout << n/2 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

int main() {
  ll n, m; cin >> n >> m;
  V<set<ll>> nodes(n, set<ll>());
  REP(i, m) {
    ll a, b; cin >> a >> b;
    nodes.at(a-1).insert(b-1);
    nodes.at(b-1).insert(a-1);
  }
  vll perm(n);
  iota(perm.begin(), perm.end(), 0);
  ll ans = 0;
  do {
    if (perm.at(0) != 0) break;
    bool is_exist = true;
    for (ll i = 1; i<n; i++) {
      if (nodes.at(perm.at(i-1)).find(perm.at(i)) == nodes.at(perm.at(i-1)).end()) is_exist = false;
    }
    if (is_exist) ans++;
  } while(next_permutation(perm.begin(), perm.end()));
  cout << ans << endl;
  return 0;
}


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

using namespace std;

const int MX = 2000006;

template <typename T> void cmin(T &x, const T &y)
{
	if(y < x) x = y;
}

template <typename T> void cmax(T &x, const T &y)
{
	if(y > x) x = y;
}

template <typename T> void read(T &x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

set<int> pos[2];
char seq[2][MX];

void solve(int p, int k, int a, int b)
{
	if(k<0 || (!a&&!b)) return;
	int nxt[2], near, from;
	for(int i=0; i<2; i++) nxt[i] = *pos[i].lower_bound(p);
	near = min(nxt[0], nxt[1]);
	from = (near == nxt[1]);
	if(a && b)
	{
		if(near-p > k)
		{
			pos[0].insert(p+k);
			pos[1].insert(p+k);
		}
		else
		{
			pos[from].erase(near);
			pos[from^1].insert(near);
			solve(near+1, k-(near-p), !from, from);
		}
	}
	else
	{
		if(p != near) pos[b==1].insert(p);
		else if((b==1) != from)
		{
			if(k) pos[from].erase(p), solve(p+1, k-1, 1, 1);
			else pos[!from].insert(p);
		}
		else pos[from].erase(p), solve(p+1, k, a, b);
	}
}

int len[2], n, k;
char out[2][MX];

int main()
{
	read(len[0]), read(len[1]), read(k);
	n = max(len[0], len[1]);
	for(int i=0; i<2; i++)
	{
		scanf("%s", seq[i]);
		fill(seq[i]+len[i], seq[i]+n, '0');
		reverse(seq[i], seq[i]+len[i]);
		pos[i].insert(1e9);
	}
	for(int i=n-1; i>=0; i--) solve(i, k, seq[0][i]-'0', seq[1][i]-'0');
	for(int i=0; i<2; i++)
	{
		pos[i].erase(1e9);
		len[i] = *pos[i].rbegin()+1;
		fill(out[i], out[i]+len[i], '0');
		for(auto x : pos[i]) out[i][x] = '1';
		reverse(out[i], out[i]+len[i]);
		puts(out[i]);
	}
	return 0;
}

Measured memory_bytes: 45440
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
//#include <chrono> //1e+9で割る auto end= chrono::system_clock::now()-st;  cout<<end.count()%1e+9<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
typedef long double db;

#define fr first
#define sc second
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
int v[3];
int ans=1000000;
int main()
{
	rep(i,3)cin>>v[i];
	sort(v,v+3);
	v[1]-=v[0];
	v[2]-=v[0];
	rep(i,51){
		int cnt=0;
		if(i!=0){
			if(i%2){
				cnt+=(i+1)/2+1;
			}
			else{
				cnt+=i/2;	
			}
		}
		if(v[1]<i){
			int d=i-v[1];
			if(d%2){
				cnt+=(d+1)/2+1;
			}
			else{
				cnt+=d/2;	
			}
		}
		else if(v[1]>i){
			cnt+=v[1]-i;
		}
		if(v[2]<i){
			int d=i-v[2];
			if(d%2){
				cnt+=(d+1)/2+1;
			}
			else{
				cnt+=d/2;	
			}
		}
		else if(v[2]>i){
			cnt+=v[2]-i;
		}
		ans=min(ans,cnt);
	}
	cout<<ans<<endl;
}

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

int main(void){
  int n; cin >> n;
  double x, sum = 0;
  for(int i=0; i<n; i++){
    cin >> x;
    sum += 1 / x;
  }
  cout << 1 / sum << endl;
  
  return 0;
}


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

using namespace std;

typedef pair<int, int> P;

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

    vector<int> ans(n, 0);
    vector<P> x((size_t)n, P(0, 0));
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        x[i] = P(a, i);
    }
    sort(x.begin(), x.end());

    for (int i = 0; i < n; ++i) {
        if (i < n / 2) ans[x[i].second] = x[n / 2].first;
        else ans[x[i].second] = x[n / 2 - 1].first;
    }

    for(auto i : ans) cout << i << endl;
}

Measured memory_bytes: 4480
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            // 整数の入力
         
            string[] input = Console.ReadLine().Split(' ');
            int ans;
            int A= int.Parse(input[0]);
            int B= int.Parse(input[1]);

            ans = A * B;

            if (A>0&&A<10&&B>0&&B<10)
            {
                Console.WriteLine(ans);
            }
            else
            {
                Console.WriteLine(-1);
            }

            
        }
    }
}

Measured memory_bytes: 11092
S = input()
T = input()
F = 1
DD = [0 for i in range(1001)]
NUM = [0 for i in range(1001)]
grid = [i for i in range(ord('a'),ord('z')+1)]
for i in range(len(S)):
    if (not DD[ord(S[i])] == ord(T[i])) and (not DD[ord(S[i])] == 0):
        F = 0
    if DD[ord(S[i])] == 0:
        NUM[ord(T[i])] = NUM[ord(T[i])] + 1
    DD[ord(S[i])] = ord(T[i])
for i in NUM:
    if i >= 2:
        F = 0
print("Yes" if F == 1 else "No")


Measured memory_bytes: 3632
#include <iostream>
#include <string>

using namespace std;

int main()
{
  int n, m, cnt, res;
  string str;

  while(cin>>n && n){
    cin >> m;
    cin >> str;

    res = 0;
    for(int i = 0; i < m; ++i)
      if(str[i] == 'I'){
	++i;
	cnt = 0;
	while(i+1 < m && str[i] == 'O' && str[i+1] == 'I'){
	  ++cnt;
	  i += 2;
	}
	if(cnt >= n) res += (cnt-n+1);
	if(cnt) i -= 3;
	else --i;
      }

    cout << res << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include<string.h>
int main(){
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);                    
    cout.tie(NULL);
   	ll n;
   	cin>>n;
   	string str;
   	ll i=0;
   	while(n!=0){
   		ll var=n%26;
   		if(var==0){
   			var=26;
   			if(n>=26) n-=26;
   		}
   		n=n/26;
   		str[i]=(char)(var+'a'-1);
   		i++;
   	}
   	i--;
   	for(;i>=0;i--) cout<<str[i];
   	return 0;
}

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

typedef long long ll;
const ll INF = 1e+17;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n;
    cin >> n;
    
    ll res = INF;
    for(ll i = 1; i * i <= n; ++i){
        if(n % i != 0)  continue;
        
        ll j = n / i;
        res = min(res, i + j - 2);
    }
    
    cout << res << endl;
}

Measured memory_bytes: 256
n=int(input())
c,i=0,1
while i <= n:
    if c==0:
        x=i
        if x%3==0:
            print(' '+str(i), end='')
            i+=1
            continue
    c=0
    if x%10==3:
        print(' '+str(i), end='')
        i+=1
        continue
    x//=10
    if x == 0:
        i+=1
        continue
    else:
        c=1
print()

Measured memory_bytes: 7856
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,k,vis[N];
vector<ll>v[N];
multiset<ll>one,two,three;
vector<pair<ll,int> >jewels;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        v[x].emplace_back(y*2);
    }
    for(int i=1;i<=k;i++)
    {
        sort(v[i].begin(),v[i].end(),greater<int>());
        two.insert(v[i][0]+v[i][1]);
        if(v[i].size()>2) three.insert(v[i][0]+v[i][1]+v[i][2]);
        ll avg=v[i][0]+v[i][1]>>1;
        jewels.push_back({avg,i});
        jewels.push_back({avg,i});
        for(int j=2;j<v[i].size();j++)
        jewels.push_back({v[i][j],i});
    }
    sort(jewels.begin(),jewels.end(),greater<pair<ll,int>>());
    ll sum=0,mnone=1ll<<60,mntwo=1ll<<60;
    for(int i=0;i<n;i++)
    {
        ll ans=-2,value=jewels[i].first,c=jewels[i].second;
        if(vis[c]==0)
        {
            if(!one.empty())
                ans=max(ans,sum+*one.rbegin());
            if(!two.empty())
                ans=max(ans,sum-mnone+*two.rbegin());
            if(!three.empty())
                ans=max(ans,sum-mntwo+*three.rbegin());
            two.erase(two.find(v[c][0]+v[c][1]));
            if(v[c].size()>2)
                three.erase(three.find(v[c][0]+v[c][1]+v[c][2]));
        }
        else
        {
            ans=sum+value;
            if(vis[c]==1)
            {
                for(int j=2;j<v[c].size();j++)
                    one.insert(v[c][j]);
                mntwo=min(mntwo,v[c][0]+v[c][1]);
            }
            else
            {
                one.erase(one.find(value));
                mnone=min(mnone,value);
            }
        }
        vis[c]++;
        sum+=value;
        printf("%lld\n",ans/2);
    }
}


Measured memory_bytes: 22892
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::string> v(n + 1);
    std::vector<std::vector<int>> cnt(n + 1, std::vector<int>(m + 1));
    auto ve(cnt), he(cnt);
    for (int i = 1; i <= n; i++) {
        std::cin >> v[i];
        for (int j = 1; j <= m; j++) {
            cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + (v[i][j - 1] == '1');
            ve[i][j] = ve[i - 1][j] + ve[i][j - 1] - ve[i - 1][j - 1] + (v[i][j - 1] == '1' && v[i - 1][j - 1] == '1');
            if (j == 1) continue;
            he[i][j] = he[i - 1][j] + he[i][j - 1] - he[i - 1][j - 1] + (v[i][j - 1] == '1' && v[i][j - 2] == '1');
        }
    }

    while (q--) {
        int x, y, z, w;
        std::cin >> x >> y >> z >> w;
        auto e = ve[z][w] + ve[x][y - 1] - ve[x][w] - ve[z][y - 1]
            + he[z][w] + he[x - 1][y] - he[x - 1][w] - he[z][y];
        auto c = cnt[z][w] + cnt[x - 1][y - 1] - cnt[x - 1][w] - cnt[z][y - 1];
        std::cout << c - e << std::endl;
    }

    return 0;
}


Measured memory_bytes: 52992