akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

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

	map<string, int> a;

	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;

		a[s]++;
	}

	cin >> m;

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

	int maxi = 0;
	for (map<string, int>::iterator it = a.begin(); it != a.end(); it++)
	{
		pair<string, int> p = *it;
		maxi = max(maxi, p.second);
	}

	cout << maxi << endl;
}

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

using namespace std;

typedef long long ll;

#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR1(i,n) for(int (i)=1;(i)<(n);(i)++)
#define eFOR(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define eFOR1(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define INF 1000000000

int main() {

	int a, b, c;
	cin >> a >> b >> c;
	if(a<=b)cout << min(b / a, c) << endl;
	else cout << 0 << endl;

	return 0;
}


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

using namespace std;

long long INF=1e15;

int prime[2000000];
bool is_prime[2000000];

int sieve(int n){
    int p=0;
    for(int i=0;i<=n;i++)is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            prime[p++]=i;
            for(int j=2*i;j<=n;j+=i)is_prime[j]=false;
        }
    }
    return p;
}

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

    while(1){
        int n;
        cin>>n;

        if(n==0)break;

        cout<<sieve(2*n)-sieve(n)<<endl;

    }
}


Measured memory_bytes: 3532
#include<stdio.h>

int main(void){
    int i, j;

    int d;//何日開催するのか
    scanf("%d", &d);

    int c[26];//各コンテストのペナルティ値
    for(i=0;i<26;i++) scanf("%d", &c[i]);

    int s[d][26];//コンテストiをD日目に開催したときの得点
    for(i=0;i<d;i++) for(j=0;j<26;j++) scanf("%d", &s[i][j]);

    int last[26] = {};//各コンテストを最後に開催したのは何日目か

    //初期解
    int hold[d];//d日目にコンテストiを開催
    int max_i, max_sum, tmp;
    for(i=0;i<d;i++){//今日=i、今日の終わり=i+1
        max_i = 0;
        max_sum = 0;
        for(j=0;j<26;j++){
            tmp = s[i][j] + c[j] * ( i+1 - last[j] );
            if( max_sum < tmp ){
                max_sum = tmp;
                max_i = j;
            }
        }
        last[max_i] = i+1;
        hold[i] = max_i;
    }

    //出力
    for(i=0;i<d;i++) printf("%d\n", hold[i]+1);

    return 0;
}

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

int main(){
	int H,W;

	while(1){
		cin >> H >> W;
		if( H==0 && W==0)
			break;
		

		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(i>0 && i<H-1){ //i???0??¨????????\??????????????????

					if(j>0 && j<W-1){//j???0??¨????????\??????????????????
						cout << '.';
					}else{ 
						cout << '#';//j???0??¨?????????????????????
					}

				}
				else cout << '#';//j???0??¨?????????????????????
			}
			cout << "\n";
		}
		cout << "\n";
	}
	
	return 0;
	
}

Measured memory_bytes: 1120
#include <bits/stdc++.h>
int ans = 700; 

int main(){
  for(int i = 0; i < 3; i++){
	char c;
    scanf("%c", &c);
    if(c == 'o'){
      ans += 100;
    }
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
	int x, y;
	cin >> x >> y;
	if (x == y) {
		puts("-1");
		return 0;
	}
	if (x < y)
		cout << x << endl;
	else {
		if (x%y == 0)
			puts("-1");
		else
			cout << x << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<double,double> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<vl> mat;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const double PI = 4*atan(1);
const ll INF = 1e18;
const int MX = 100001;

int N;
multiset<int> m;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    vpi a(N), b(N);
    F0R(i,N) cin >> a[i].f >> a[i].s;
    F0R(i,N) cin >> b[i].f >> b[i].s;
    sort(all(a)), sort(all(b));
    
    int ind = 0,ans=0;
    for (auto x: b) {
        while (ind < sz(a) && a[ind].f < x.f) m.insert(a[ind++].s);
        auto it = m.lb(x.s);
        if (it != m.begin()) {
            ans ++;
            m.erase(prev(it));
        }
    }
    cout << ans;
}

// read the question correctly (is y a vowel?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

Measured memory_bytes: 256
import re

def revPolish(f):
    f = re.sub(r'(\-?\d+\.?\d*)\s(\-?\d+\.?\d*)\s([\+\-\*/])(?!\d)',
        lambda m: str(eval(m.group(1) + m.group(3) + m.group(2))),
        f)
    if f[-1] in ('+','-','*','/'):
        return revPolish(f)
    else:
        return f

if __name__=='__main__':
    print(revPolish(input()))


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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll N, P;
vector<ll> s;
vector<ll> cnt(10000, 0);

signed main() {
  string tmp;
  cin >> N >> P >> tmp;
  s.push_back(0);
  rep(i, N) {
    s.push_back(tmp[N-1-i] - '0');
  }

  if (10 % P == 0) { // 10^m と P が互いに素でない場合は特例(P=2 or 5)
    ll ans = 0;
    for (ll i=1; i<=N; i++)
      if (s[i] % P == 0)
        ans += N-i+1;
    cout << ans << endl;
    return 0;
  }

  vector<ll> psum(N+1, 0);
  ll ten = 1;
  for (ll i=1; i<=N; i++, ten=(ten*10)%P) {
    psum[i] = (psum[i-1] + (s[i] * ten) % P) % P;
  }

  ll ans = 0;
  rep(i, N+1) {
    ans += cnt[psum[i]];
    cnt[psum[i]]++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3828
#include <stdio.h>
#include <stdlib.h>
int main(void){
  int n,a,i,min=1000000,sum;
  scanf("%d %d",&n,&a);
  
  for(i=0;i<n;i++){
    if(abs(a) < abs(min)){
      min = a;
    }
  	sum += a;
    a += 1;
  }
  sum -= min;
  printf("%d\n",sum);
  return 0;
}

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

using namespace std;

int main()
{

string s;
cin>>s;
int c=0;
for(int i=0;i<3;i++)
{
    if(s[i]=='7'){c++;}
}
if(c==0){cout<<"No";}
else {cout<<"Yes";}
      return 0;
}


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

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

int N;
vector<ll> psum;
vector<pii> S;

int main() {
    scanf("%d", &N);
    S.resize(N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &S[i].first);
        S[i].second = i;
    }
    sort(S.begin(), S.end());
    psum.resize(N);
    for(int i = 0; i < N; i++) {
        psum[i] = S[i].first;
        if(i) psum[i] += psum[i - 1];
    }
    int cnt = 0;
    for(int i = N - 1; i >= 0; i--) {
        if(i != N - 1 && S[i + 1].first > 2*psum[i]) break;
        cnt++;
    }
    printf("%d", cnt);
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X, i) ((X>>i)&1)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define r_all(a) (a).rbegin(), (a).rend()
#define in(x) cin>>x
#define ina(x, n) rep(x_i,n) cin>>x[x_i]
#define outa(x, n) rep(x_i,n) cout<<x[x_i]<<" \n"[x_i==n-1]

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = (1<<30);
const ll INFL = (1L<<62);

int main() {
  ll n, ans = 0; cin >> n;
  vl l(n); ina(l,n);
  sort(all(l));
  rep(i,n) {
    REP(j,i+1,n) {
      int k1 = j+1, k2 = upper_bound(all(l),l[i]+l[j]-1) - l.begin();
      ans += k2 - k1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int C(const void *a,const void *b)
{
	int x=*(int*)a,y=*(int*)b;
	return x<y;
}
int main()
{
	int i,n,m,v[1000],p;
	for(;scanf("%d%d",&n,&m),n,m;)
	{
		for(i=p=0;i<n;p+=v[i++])
			scanf("%d",&v[i]);
		qsort(v,n,4,C);
		for(i=m-1;i<n;i+=m)
			p-=v[i];
		printf("%d\n",p);
	}
	return 0;
}

Measured memory_bytes: 652
#include <bits/stdc++.h>
using namespace std;
typedef pair<pair<int,int>,int> pii;
bool vis[25][25];
string s[25];
int n, m, dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
queue<pii> Q;
int bfs(int i, int j) {
    for ( int i=0; i<25; ++i )
        for ( int j=0; j<25; ++j )
            vis[i][j] = 0;
    int mx = 0;
    while ( !Q.empty() )    Q.pop();
    Q.push(pii{make_pair(i,j),0});
    vis[i][j] = 1;
    while ( !Q.empty() ) {
        pii tmp = Q.front();  Q.pop();
        int cx = tmp.first.first;
        int cy = tmp.first.second;
        // cout << "." << cx << ' ' << cy << ' ' << tmp.second << '\n';
        mx = max(mx,tmp.second);
        for ( int _=0; _<4; ++_ ) {
            int x = cx+dx[_];
            int y = cy+dy[_];
            if ( x > 0 && x <= n && y > 0 && y <= m && !vis[x][y] && s[x][y] == '.' ) {
                vis[x][y] = 1;
                Q.push(pii{make_pair(x,y),tmp.second+1});
            }
        }
    }
    return mx;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int ans = 0;
    cin >> n >> m;
    for ( int i=1; i<=n; ++i ){
        s[i] = "#";
        string t;
        cin >> t;
        s[i] += t;
    }
    for ( int i=1; i<=n; ++i )
        for ( int j=1; j<=m; ++j ) {
            if ( s[i][j] == '#' )   continue;
            // cout << i << ' ' << j << "   " << bfs(i,j) << '\n';
            ans = max(ans,bfs(i,j));
        }
    cout << ans << '\n';
    
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int a[] = new int[N];
		int ans = 0;
		for(int i = 0; i < N; i++){
		    a[i] = sc.nextInt()-1;
		    ans += a[i];
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 40584
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;

ll a[202020];
ll dp[202020][5];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }


    for(int i=1;i<=n;i++){
        dp[i][0] = dp[i-1][0] + a[i];
        dp[i][1] = min({dp[i][0],dp[i-1][1] + (a[i]==0?2:a[i]%2), dp[i-1][0] + a[i]%2});
        dp[i][2] = min({dp[i][1], dp[i-1][2] + (a[i]%2?0:1)});
        dp[i][3] = min({dp[i][2], min(dp[i-1][2],dp[i-1][3])+(a[i]==0?2:a[i]%2)});
        dp[i][4] = min({dp[i][3], dp[i-1][3] + (a[i]==0?2:a[i]%2), dp[i-1][4] + a[i]});
    }

    printf("%lld\n", dp[n][4]);
}


Measured memory_bytes: 9600
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int s = sc.nextInt();
        int count = 0;
        for(int i = 0; i <= k; i++) {
            for(int j = 0; j <= k; j++) {
                int num = s - i - j;
                if(num >= 0 && num <= k) count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
//	Table is the complete reverse of dp
//	Always think of the pattern (LCM, GCD)
//	Be careful of unsigned
//	double epsilon = FLT_EPSILON;
//	Think of a solution that gets TLE and optimize it

int main()
{
    cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);
    int l, r, d;
    cin >> l >> r >> d;
    cout << r / d - (l - 1) / d;
}


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

#define ll long long
#define ff(i,c,n) for(ll i=c;i<n;i++)


int main(){
    ll n,k;
    cin>>n>>k;
    ll h[n];
    ff(i,0,n) cin>>h[i];
    if(n==2) cout<<abs(h[1]-h[0]);
    else{
        ll dp[n];
        dp[0]=0;
        dp[1]=abs(h[1]-h[0]);
        ff(i,2,n){
            ll min = INT_MAX;
            ff(j,0>(i-k)?0:(i-k),i){
                if((dp[j]+abs(h[i]-h[j]))<min){
                    min=dp[j]+abs(h[i]-h[j]);
                }
            }
            dp[i]=min;
        }
        cout<<dp[n-1];
    }

}

Measured memory_bytes: 1792
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def counter():
    cnt = 0
    while True:
        yield cnt
        cnt += 1

def dfs(here, visited, track, count, connect):
    visited |= {here}
    for c in connect[here]:
        if c not in visited:
            dfs(c, visited, track, count, connect)
    track[here] = next(count)

def kosaraju(here, visited, track, count, connect):
    visited |= {here}
    for c in connect[here]:
        if c not in visited:
            kosaraju(c, visited, track, count, connect)
    track[here] = count

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
reversed_connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
    reversed_connect[v2].append(v1)

visited = set()
track_gen = counter()
track = [-1 for n in range(vertices)]
for v in range(vertices):
    if v not in visited:
        dfs(v, visited, track, track_gen, connect)

visited = set()
track_gen = counter()
strongly_con = [-1 for n in range(vertices)]
for v in range(vertices - 1 ,- 1, -1):
    here = track.index(v)
    if here not in visited:
        num = next(track_gen)
        kosaraju(here, visited, strongly_con, num, reversed_connect)

q_num = int(input())
for _ in range(q_num):
    v1, v2 = (int(n) for n in input().split(" "))
    if strongly_con[v1] == strongly_con[v2]:
        print(1)
    else:
        print(0)

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

using namespace std;

using int64 = long long;
const int mod = 998244353;

int N, M, A[300][300];
bitset< 300 > X[301], Y[301];


int main() {
  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      cin >> A[i][j];
    }
  }
  int ret = 0;
  for(int i = 0; i < N; i++) {
    bitset< 300 > tap;
    for(int j = 0; j < M; j++) {
      tap[j] = A[i][j];
    }
    for(int j = 0; j <= M; j++) {
      if(tap[j]) {
        if(X[j][j]) {
          tap ^= X[j];
        } else {
          X[j] = tap;
          ++ret;
          break;
        }
      }
    }
  }
  int64 all = 1, sub = 1;
  for(int i = 0; i < N + M - 1; i++) (all *= 2) %= mod;
  for(int i = 0; i < N + M - ret - 1; i++) (sub *= 2) %= mod;
  cout << (all + mod - sub) % mod << endl;
}






Measured memory_bytes: 640
#include <iostream>
#define MAX 22
using namespace std;

int counter = 0;
char tile[MAX][MAX];

void redtile(int y, int x){
	tile[y][x] = '+';
	counter++;
	if (x + 1 < MAX && tile[y][x + 1] == '.')
		redtile(y, x + 1);
	if (x - 1 >= 0 && tile[y][x - 1] == '.')
		redtile(y, x - 1);
	if (y + 1 < MAX&&tile[y + 1][x] == '.')
		redtile(y + 1, x);
	if (y - 1 >= 0 && tile[y - 1][x] == '.')
		redtile(y - 1, x);
}


int main()
{
	int w, h, initi, initj;
	while (cin >> w >> h, w || h){
		for (int i = 0; i < MAX; i++){
			for (int j = 0; j < MAX; j++){
				tile[i][j] = 0;
			}
		}
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				cin >> tile[i][j];
				if (tile[i][j] == '@'){
					tile[i][j] = '.';
					initi = i;
					initj = j;
				}
			}
		}
		counter = 0;
		redtile(initi, initj);
		cout << counter << endl;
	}
	return 0;
}

Measured memory_bytes: 1172
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n;
        cin >> n;
        int a[n + 1];
        map<int, int> cnt;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            ans += cnt[i - a[i]];
            cnt[i + a[i]]++;
        }
        cout << ans << '\n';
    }
}


Measured memory_bytes: 58800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll n, m, a, s;
  in2(n, m);
  s = 0;
  ll c[n];
  rep(i, n){
    in(c[i]);
    s += c[i];
  }
  a = 0;
  rep(i, n){
    if(c[i] * 4 * m >= s)
      a++;
  }
  if(a >= m)
    out("Yes");
  else
    out("No");
  memi;
}

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

int main(){
    ll x;
    cin>>x;
    ll ans=0;
    ll flag=0;
    for(ll i=0;i<1e9;++i){
        if(flag >= x){
            break;
        }
        flag += i;
        ans++;
    }
    cout<<ans-1<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string st;
	cin>>st;
	for(register int i=0;i<st.length();++i){
		if(st[i]=='A'&&st[i+1]=='C'){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setprecision(20)
#define SHOWP(x) cerr<<"["<<(x).FI<<", "<<(x).SE<<"]";
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}

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

//ａをbで割る
long long mod_div(long long a,long long b){
  if(a % b == 0)return a/b;
  long long tmp = MOD - 2,c = b,ret = 1;
  while(tmp > 0){
    if(tmp & 1){
      ret *= c;ret %= MOD;
    }
    c *= c;c %= MOD;tmp >>= 1;
  }
  return a*ret%MOD;
}

//階乗の上限
#define MAX_K 333333
vector<long long> kaijo(MAX_K);
long long comb(long long n, long long r){
  if(n < r || n < 0 || r < 0)
    return 0;
  if(kaijo[0] != 1){
    kaijo[0] = 1;
    for(long long i = 1;i < MAX_K;i++) {
      kaijo[i] = (kaijo[i-1] * i) % MOD;
    }
  }
  long long ret = kaijo[n];
  long long tmp = (kaijo[r] * kaijo[n-r]) % MOD;
  return mod_div(ret,tmp);
}

void modsub(ll& a, ll b)
{
  a = (MOD + (a - b)) % MOD;
}

bool flag[110000];
int main()
{
  int N; cin >> N;
  vector<int> a(N + 1);
  REP(i, N + 1) {
    cin >> a[i];
    a[i]--;
    flag[a[i]] ^= 1;
  }
  int l, r;
  for (int i = 0; i <= N; i++) {
    if (!flag[a[i]]) {
      l = i;
      break;
    }
  }
  for (int i = N; i >= 0; i--) {
    if (!flag[a[i]]) {
      r = N - i;
      break;
    }
  }
  for (int k = 1; k <= N + 1; k++) {
    ll ans = comb(N + 1, k);
    if (l + r >= k - 1) modsub(ans, comb(l + r, k - 1));
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 4352
from math import sqrt
def factorint(n):
    d = {}
    for i in range(2, int(sqrt(n)+1)):
        c = 0
        q, r = divmod(n, i)
        while not r:
            c += 1
            n = q
            q, r = divmod(n, i)
        if c:
            d[i] = c
    if n != 1:
        d[n] = 1
    return d

n, p = map(int, input().split())
x = 1
for k, v in factorint(p).items():
    x *= k ** (v//n)
print(x)

Measured memory_bytes: 9168
from collections import Counter
N = int(input())
S = input()
ctr1 = Counter()
ctr2 = Counter()

for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += S[k]
        else:
            red += S[k]
    ctr1[(blue,red)] += 1

T = S[:-N-1:-1]
for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += T[k]
        else:
            red += T[k]
    ctr2[(blue,red)] += 1

ans = 0
for k,v in ctr1.items():
    ans += v * ctr2[k]
print(ans)

Measured memory_bytes: 174656
#include<iostream>
#include<cstdio>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
bool c[maxn],q[maxn];int a[maxn],cc[maxn];
inline int lowbit(int x){
	return x & -x;
}
inline void add(int x){
	while(x<=maxn){
		cc[x]++;
		x+=lowbit(x);
	}
}
inline int cal(int x){
	if(x<=0)return 0;
	int ans=0;
	while(x){
		ans+=cc[x];
		x-=lowbit(x);
	}
	return ans;
}
int main(){
	int n,l,r,tot=0;
	scanf("%d",&n);	
	for(int i=2;i<maxn;++i){
   		    if(!c[i]){
    	        a[++tot]=i;
    	        c[i]=true;
    	        q[i]=true;
				if(i%2!=0&&q[(i+1)/2])add(i);
    	    }
    	for(int j=1;j<=tot;++j){
    		if(a[j]*i>=maxn)break;
    		c[a[j]*i]=true;
           if(i%a[j]==0)break;
    	}
    }
    for(int i=1;i<=n;++i){
    	scanf("%d%d",&l,&r);
    	printf("%d\n",cal(r)-cal(l-1));
	}
	return 0;
}


Measured memory_bytes: 1280
import java.util.*;
public class Main{
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt(),w=sc.nextInt(),K=sc.nextInt();
        char[][]c=new char[h][w];
        for(int i = 0;i<h;i++)c[i]=sc.next().toCharArray();
        int ans = 0;
        for(int i = 0;i<1<<h;i++){
            for(int j = 0;j<1<<w;j++){
                int black = 0;
                for(int k=0;k<h;k++){
                    for(int l = 0;l<w;l++){
                        if((((i>>k)&1)==0)&&(((j>>l)&1)==0)&&c[k][l]=='#')black++;
                    }
                }
                if(black==K)ans++;
            }
        }
        System.out.println(ans);
	}
}


Measured memory_bytes: 35864
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  if(N<1200)
  {
    cout << "ABC" << endl;
  }
  else
  {
    cout << "ARC" << endl;
  }
  return 0;
}


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

using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, N;
  cin >> H >> N;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }

  vector<int> dp(H + 1, 1 << 28);
  dp[0] = 0;
  for (int h = 0; h < H + 1; h++) {
    for (int i = 0; i < N; i++) {
      chmin(dp[min(H, h + A[i])], dp[h] + B[i]);
    }
  }
  cout << dp[H] << '\n';
  return 0;
}


Measured memory_bytes: 256
using System;

public class Test
{
	public static void Main()
	{
		// your code goes here
		string s = Console.ReadLine();
		int s1 = int.Parse(s.Substring(0, 2));
		int s2 = int.Parse(s.Substring(2));
		
		
		if(s1 > 0 && s1 <= 12)
		{
			if(s2 > 0 && s2 <= 12) Console.WriteLine("AMBIGUOUS");
			else Console.WriteLine("MMYY");
		}
		else
		{
			if(s2 > 0 && s2 <= 12) Console.WriteLine("YYMM");
			else Console.WriteLine("NA");
		}
	}
}

Measured memory_bytes: 11092
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let mut a = read_vec::<i64>();
    a.sort();
    a.reverse();
    let mut count = 1;
    let mut pointer = 1;
    let mut ans = a[0];
    while count < n - 1 {
        if count == n - 2 {
            ans += a[pointer];
            count += 1;
        } else {
            ans += 2 * a[pointer];
            count += 2;
        }
        pointer += 1;
        // debug!(ans, count);
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "
#define cout(n) cout<<fixed<<setprecision(n)

ll ext_gcd(ll a, ll b, ll&x, ll&y){
  if(b==0){
    x=1;y=0;return a;
  }
  ll q=a/b;
  ll g=ext_gcd(b,a-q*b,x,y);
  ll z=x-q*y;
  x=y;y=z;
  return g;
}

ll invmod(ll a, ll m){
  ll x,y;
  ext_gcd(a,m,x,y);
  x%=m;
  if(x<0)x+=m;
  return x;
}

ll gcd(ll a, ll b){
  ll x;
	while(a!=b){
    if(b==0)break;
    a=a%b;
    x=b;
    b=a;
    a=x;
  }
  return a;
}


int comb(ll n, ll r){
	ll res = 1;
  ll z = 998244353;
  for(ll i=0; i<r; i++){
		res = res*(n-i)%z;
	}
  for(ll i=0; i<r; i++){
		res = (res*invmod((i+1),z))%z;
	}

	return res;
}

int main(){
  ll N,A,B,K;
  cin>>N>>A>>B>>K;
  ll z = 998244353;
  //ll res=0,lcm=a*b/(gcd(a,b));
  ll b=0,c=0;
  vector<ll> vec(N+1,1);
  FOR(i,1,N+1){
    vec[i]=(((vec[i-1]%z)*(N-i+1))%z*(invmod(i,z)))%z;
  }

  FOR(i,0,N+1){
    if((K-A*i)%B==0 ){
      b=(K-A*i)/B;
      if(0<=b && b<=N){
        c=((vec[i]*vec[b])%z+c)%z;
      //  cout<<"a="<<i<<" b="<<b<<" c="<<c<<endl;
      //  cout<<comb(N,i)<<" "<<comb(N,b)<<endl;
        c=c%z;
      }
    }
  }
  //coutv(vec,0,N+1);
  cout<<c<<endl;
}


Measured memory_bytes: 2560
import sys
def input(): return sys.stdin.readline().strip()

def main():
    a, b, c, d, e = map(int, input().split())
    if a == 0: print(1)
    if b == 0: print(2)
    if c == 0: print(3)
    if d == 0: print(4)
    if e == 0: print(5)
    

if __name__ == "__main__":
    main()


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

int main() {
  
  int n,m,x,y,a,b;
  cin >> n >> m >> x >> y;
  
  int MXx = -101,MNy = 101;
  
  for ( int i = 0; i < n; i++){
    cin >> a;
    MXx = max(MXx,a);
  }
  
  for ( int i = 0; i < m; i++){
    cin >> b;
    MNy = min(MNy,b);
  }
  
  for ( int i = x + 1; i <= y; i++){
    if ( MXx < i && i <= MNy ){
      cout << "No War" << endl;
      return 0;
    }
  }
  
  cout << "War" << endl;
  
  return 0; 
 
}

Measured memory_bytes: 256
n,m = map(int,input().split())
ans = [0]*n
for i in range(m):
  s,c = map(int,input().split())
  if ans[s-1] != 0 and ans[s-1] != c:
    print(-1)
    exit()
  elif n != 1 and s == 1 and c == 0:
    print(-1)
    exit()
  else:
    ans[s-1] = c
ans_f = "".join((map(str,ans)))
if n>1 and ans_f[0] == "0":
  print("1"+ans_f[1::])
else:
  print(ans_f)

Measured memory_bytes: 9220
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int N;
VPII d[SIZE];
int get_bit(int x,int v){return (x>>v)&1;}
int main(){
    R(N);
    FOR(i,1,N){
        int m;
        R(m);
        REP(j,m){
            int x,y;
            R(x,y);
            d[i].PB({x,y});
        }
    }
    int an=0;
    REP(i,1<<N){
        int bn=0;
        bool err=0;
        REP(j,N){
            if(get_bit(i,j)){
                bn++;
                for(auto x:d[j+1]){
                    if(get_bit(i,x.F-1)!=x.S)err=1;
                }
            }
        }
        if(!err)an=max(an,bn);
    }
    W(an);
    return 0;
}


Measured memory_bytes: 23680
import java.util.*;
import javax.lang.model.util.ElementScanner6;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

        // 入力
        int n = sc.nextInt();
        double n1 = (double) n;

        int x1 = (int) (n1 / 1.08);
        int n2 = (int) (x1 * 1.08);
        int n3 = (int) ((x1 + 1) * 1.08);

        String out = "";
        if (n == n2) {
            out = Integer.toString(x1);
        } else if (n == n3) {
            out = Integer.toString(x1 + 1);
        } else {
            out = ":(";
        }

        // 出力
		System.out.println(out);
    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N;
int p[20010];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }  
  int a[20010], b[20010];
  for (int i = 0; i < N; i++) {
    a[i] = b[N - 1 - i] = 1 + N * i;
  }
  for (int i = 0; i < N; i++) {
    a[p[i] - 1] += i;
  }
  for (int i = 0; i < N; i++) {
    cout << a[i] << " \n"[i + 1 == N];
  }
  for (int i = 0; i < N; i++) {
    cout << b[i] << " \n"[i + 1 == N];
  }

  return 0;
}

Measured memory_bytes: 896
#include<stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j,key;
  int A[N+1];
  scanf("%d", &n);

  for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
  
  trace(A, n);

  for(i = 2;i <= n;i++){
    key = A[i];
    j = i - 1;
    while(j > 0 && A[j] > key){
      A[j + 1] = A[j];
      j = j - 1;
    }
    A[j + 1] = key;
        trace(A,n);
  }
  return 0;
}



Measured memory_bytes: 2128
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

    private void solve(FastScanner sc) {
        char[] s = sc.next().toCharArray();
        char now = s[0];
        int cnt = 0;
        for (char c : s) {
            if (now != c) {
                now = c;
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    /*
     * template
     */

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        new Main().solve(sc);
    }

    static class FastScanner {
        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 static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
            return hasNextByte();
        }

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

        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() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

Measured memory_bytes: 9556
# -*- coding:utf-8 -*-
import sys


class Cell(object):
    __slots__ = ["value", "pre", "next"]

    def __init__(self, value=None, pre=None, _next=None):
        if pre is None and _next is None:
            self.value = None
            self.pre = self
            self.next = self
        else:
            self.value = value
            self.pre = pre
            self.next = _next


class MyList(object):
    def __init__(self):
        self._nil = Cell()

    def insert(self, value):
        self._nil.next = Cell(value, self._nil, self._nil.next)
        self._nil.next.next.pre = self._nil.next

    def delete(self, value):
        self._delete_to(self._search(value))

    def delete_first(self):
        self._delete_to(self._nil.next)

    def delete_last(self):
        self._delete_to(self._nil.pre)

    def toList(self):
        gen = self._val_generator()
        return [val for val in gen()]

    def _val_generator(self):
        def gen():
            current = self._nil.next
            while current is not self._nil:
                yield current.value
                current = current.next
        return gen

    def _delete_to(self, cell):
        if cell is not self._nil:
            cell.next.pre = cell.pre
            cell.pre.next = cell.next

    def _search(self, value):
        current = self._nil.next
        while current is not self._nil and current.value != value:
            current = current.next
        return current


def doubly_inked_list(commands):
    lst = MyList()
    for command in commands:
        if command[0] == "insert":
            lst.insert(command[1])
        elif command[0] == "delete":
            lst.delete(command[1])
        elif command[0] == "deleteFirst":
            lst.delete_first()
        elif command[0] == "deleteLast":
            lst.delete_last()
        else:
            raise ValueError
    return lst.toList()


if __name__ == "__main__":
    commands = [val.split() for val in sys.stdin.read().splitlines()]
    pop = commands.pop(0)
    print(" ".join(doubly_inked_list(commands)))

Measured memory_bytes: 644288
#include <bits/stdc++.h>
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  for(int i=0;i<N;i++)  cin >> A.at(i);

  for(int i=0;i<K;i++){
    vector<int> imos(N+1,0);
    for(int j=0;j<N;j++){
      int l=max(0,j-A.at(j));
      int r=min(N-1,j+A.at(j));
      imos.at(l)++;
      imos.at(r+1)--;
    }
    for(int j=1;j<N+1;j++)  imos.at(j)+=imos.at(j-1);
    for(int j=0;j<N;j++)  A.at(j)=imos.at(j);

    bool flag=true;
    for(int j=0;j<N;j++){
      if(A.at(j)<N) flag=false;
    }
    if(flag)  break;
  }

  for(int i=0;i<N;i++)  cout << A.at(i) << " ";
  cout << endl;

  return 0;
}

Measured memory_bytes: 4968
#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;
#pragma endregion

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i=0; i<n; i++) {
        cin >> a.at(i);
    }

    sort(a.begin(), a.end());
    int p = n;
    for (int i=0; i<n; i++) {
        if (a.at(i) >= 0) {
            p = i;
            break;
        }
    }

    ll ok = LINF, ng = -LINF;
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        ll cnt = 0;
        for (int i=0; i<n; i++) {
            if (mid >= 0) {
                if (a.at(i) > 0) {
                    cnt += upper_bound(a.begin()+p, a.end(), mid / a.at(i)) - a.begin();
                    if (a.at(i) <= mid / a.at(i)) cnt--;
                } else if (a.at(i) < 0) {
                    cnt += a.end() - lower_bound(a.begin(), a.begin()+p, mid / a.at(i));
                    if (a.at(i) >= mid / a.at(i)) cnt--;
                } else {
                    cnt += n-1;
                }
            } else {
                if (a.at(i) > 0) {
                    cnt += upper_bound(a.begin(), a.begin()+p, (mid+1) / a.at(i) - 1) - a.begin();
                } else if (a.at(i) < 0) {
                    cnt += a.end() - lower_bound(a.begin()+p, a.end(), (mid+1) / a.at(i) + 1);
                }
            }
        }
        cnt /= 2;
        if (cnt >= k) ok = mid;
        else ng = mid;
    }

    cout << ok << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std ;
 
#define reMin(a, b) a = min(a, b)
#define reMax(a, b) a = max(a, b)
 
#define lint long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define SET(x, val) memset(x, val, sizeof(x))
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
typedef vector < int > vi ;
typedef pair < int, int > pii ;
 
const int N = 1e6 + 2 ;
const int MOD = 1e9 + 7 ;
const lint INF = 1e18 ;
const int LN = 63 ;

int n ; 
lint a[N] ;
string s ;
lint basis[LN];

bool inSpan(lint x) {
    for(int i = LN - 1; i >= 0; i--) {
        if(x & (1LL << i)) {
            if(basis[i])
                x ^= basis[i] ;
        }
    }
    return (x == 0LL) ;
}

void insert(lint x) {
    for(int i = LN - 1; i >= 0; i--) {
        if(x & (1LL << i)) {
            if(!basis[i]) {
                basis[i] =x ;
                return ;
            }
            x ^= basis[i] ; 
        }
    }
}

int main() {
    fastio;
    int t ; cin >> t ;
    while(t--) {
        cin >> n ; SET(basis, 0);
        for(int i = 0; i < n; i++) cin >> a[i] ;
        cin >> s ;
        if(s[n-1] == '1') {
            cout << 1 << endl ;
            continue ;
        }
        int oneWins = 0 ; 
        for(int i = n-1; i >= 0; i--) {
            int current = s[i] - '0' ; 
            if(current == 0) insert(a[i]);
            else {
                if(!inSpan(a[i])) oneWins = 1 ;
            }
        }
        if(oneWins) cout << 1 << endl;
        else cout << 0 << endl ; 
    }
}

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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF             2e9
#define INF_LL          1LL<<60
#define ll              long long
#define Ceil(x, n)      (((((x))+((n)-1))/n))
#define CeilN(x, n)     (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)    ((x)-(x)%(n))
#define ALL(x)          (x).begin(),(x).end()
typedef pair<ll, ll>    P;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(b, c) << endl;
    if(b+c<=a) {
        cout << "0" << endl;
    } else {
        cout << b+c-a << endl;
    }

    return 0;
}

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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }


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

    int N; cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    sort(all(A));
    rep(i, N-1) {
        if (A[i] == A[i+1]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}

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

int main() {
  int N, K;
  std::cin >> N >> K;
  
  int ans = 0;
  
  for (int i = 0; i < N; i++){
    int x;
    std::cin >> x;
    
    if (x <= K - x){
      ans += 2*x;
    }
    else{
      ans += 2*(K - x);
    }
  }
  std::cout << ans << std::endl;
}


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

using namespace std;

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

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

    int range = 2*d+1;

    int ans = n/range;

    if(n%range != 0)
        ans++;

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

Measured memory_bytes: 256
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    n = NI()
    bit = [0] * (n+1)
    A = LI()
    def add(i,x):
        while i <= n:
            bit[i] += x
            i += i & -i

    def query(i):
        x = 0
        while i > 0:
            x += bit[i]
            i -= i & -i
        return x

    for i,a in enumerate(A):
        add(i+1,int(a))

    ans = INF
    bit_c = copy.deepcopy(bit)
    for s in (1,-1):
        bit = copy.deepcopy(bit_c)
        cnt = 0
        x = s
        for i in range(1,n+1):
            z = query(i)
            if z * x <= 0:
                add(i,x-z)
                cnt += abs(x-z)
            x = -x
        ans = min(ans,cnt)
    print(ans)


if __name__ == '__main__':
    main()

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

int main() {
string s;
cin >> s;
rep(i,3){
  if(s.at(i) =='1') s.at(i) = '9';
  else s.at(i) = '1';
}
cout << s << endl;
}
  


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


int main() {
    int k,x;
    cin>>k>>x;

    int a = -1000000;
    int b =  1000000;
    
    a = max(a,x-k+1);
    b = min(b,x+k-1);
    
    rep2(i,a,b) printf("%d ",i);
    printf("\n");
    return 0;
}

Measured memory_bytes: 256