akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1LL<<60;
const double EPS = 1e-10;
const ll mod=1000000007;
//const ll mod=998244353;
ll pw(ll a, ll b, ll mod) {
  if (b == 0) return 1;
  if (b % 2 == 1) return pw(a, b-1, mod) * a % mod;
  ll temp = pw(a, b/2, mod);
  return temp * temp % mod;
}
int main(void){
    ll n;
    cin>>n;
    cout<<(pw(10,n,mod)-2*pw(9,n,mod)+pw(8,n,mod)+10*mod)%mod<<endl;
}

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

// isDebug?
#ifndef ONLINE_JUDGE
#define _DEBUG
#endif

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// -* https://xn--kst.jp/blog/2019/08/29/cpp-comp/ *- Thx :)
// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    cout << __FILE__ << ": " << __LINE__ << ": " << __func__ << " -> ";   \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

// namespace / type / class / struct - alias, def:
using namespace std;

using ll = long long;
using ull = unsigned long long;

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;
const int FACN = 510000;

// Global Variables:
// ll fac[FACN], finv[FACN], inv[FACN];

// Prototype Declarations:
int gcd(int, int);
int lcm(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);

// ================ Main Loop ================
int main() {
    int n;
    vector<int> ans(n);
    cin >> n;
    for(int x = 1; x * x <= n; x++) {
        for(int y = 1; y * y <= n; y++) {
            for(int z = 1; z * z <= n; z++) {
                debug(x, y, z, x * x + y * y + z * z + x * y + y * z + z * x);
                if(x * x + y * y + z * z + x * y + y * z + z * x <= n) {
                    ++ans.at(x * x + y * y + z * z + x * y + y * z + z * x - 1);
                } else {
                    break;
                }
            }
        }
    }
    rep(i, n) {
        cout << ans[i] << endl;
    }
    return 0;
}
// ===========================================

// Functions:
// 最大公約数 O(log(min(a, b)))
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
// 最小公倍数 O(log(min(a, b)))
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

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


Measured memory_bytes: 3720
N = int(input())
for a in range(1,3501):
    for b in range(1,3501):
        if (4*a*b) - N*(a+b) != 0:
            r = (N*a*b) % ( (4*a*b) - N*(a+b) )
            if r == 0:
                c = (N*a*b) // ( (4*a*b) - N*(a+b) )
                if c > 0:
                    break
    else:
        continue
    break
print(a,b,c)

Measured memory_bytes: 41436
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long  h, n;
  string ans = "Yes";
  cin >> h >> n;
  vector<long long> a(n);
  long long sum = 0;
  for(int i=0;i<n;i++){
    cin >> a[i];
    sum += a[i];
  }
  if(sum < h){
    ans = "No";
  }
  
  cout << ans <<endl;
}

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

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define H(x) cout << #x << " " << x << endl;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 2e6+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

bitset <NMAX> isprime;
vector<int> primes;

int N, P;

signed main(){
    fast_io();
    isprime.set();
    isprime[0] = isprime[1] = 0;
    for(int i = 2; i*i < NMAX; i++) 
        if(isprime[i]) 
            for(int j = i*i; j < NMAX; j += i) 
                isprime[j] = 0;
    
    FOR(i, 0, NMAX) if(isprime[i]) primes.pb(i);

    cin >> N >> P;
    if( N == 1 ) {cout << P << endl; return 0;}
    int res = 1;
    for(int p : primes){
        int cnt = 0;
        while(P % p == 0) {
            cnt ++;
            P /= p;
        }
        FOR(i, 0, cnt/N) res *= p;
    }
    
    cout << res << endl;

}


Measured memory_bytes: 2676
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int n;
    cin >> n;
    cout << (n + 2 - 1) / 2;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 210000
using namespace std;
int n, k, i, a[N];
long long sum;
int main() {
	scanf("%d%d", &n, &k);
	for (i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n);
	for (i = 1; i <= n - k; i++) sum += a[i];
	printf("%lld", sum);
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int num[8], n, ans = 0;
bool r[8][8], flg[8];

void saiki(int a) {
  int i;
  if(a == n) {
    bool b = true;
    for(i = 1; i < n; ++i) if(!r[num[i - 1]][num[i]]) b = false;
    if(b) ++ans;
    return;
  }
  for(i = 1; i < n; ++i) if(flg[i]) {
    num[a] = i, flg[i] = false;
    saiki(a + 1);
    flg[i] = true;
  }
}

int main(void) {
  int i, m, j, x, y;
  scanf("%d%d", &n, &m);
  for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) r[i][j] = false;
  for(i = 0; i < n; ++i) flg[i] = true;
  for(i = 0; i < m; ++i) {
    scanf("%d%d", &x, &y);
    x--, y--;
    r[x][y] = r[y][x] = true;
  }
  num[0] = 0;
  saiki(1);
  printf("%d", ans);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<ll, ll> P;


bool validMonth(int x){
    return x >= 1 && x <= 12;
}

int main(){
    int s;   cin >> s;
    int f = s / 100;
    int l = s % 100;

    if(validMonth(f) && validMonth(l)){
        cout << "AMBIGUOUS" << endl;
    }
    else if(validMonth(f)){
        cout << "MMYY" << endl;
    }
    else if(validMonth(l)){
        cout << "YYMM" << endl;
    }
    else{
        cout << "NA" << endl;
    }



    return 0;
}


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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int main(){

    int n,k;
    cin >> n >> k;
    if(n%k == 0){
        cout << '0' << endl;
    }else{
        cout << "1" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include  <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define P pair<int,int>
//P pa(114,514);   ,vector<P>vec(N,0);
//vector<vector<int>> vec(縦, vector<int>(横));
#define REP(i,N) for(int i=0;i<N;i++)
int gcd(int a, int b) {
    if(a>b){
        swap(a,b);
        }
    while(b%a!=0){
        b%=a;
        swap(a,b);
    }
    return a;
}
ll llmin(ll a,ll b){
  if(a>b) return b;
  else return a;
}

//cout << setprecision(123);
int main(){
  int r,d,x;
  cin>>r>>d>>x;
  REP(i,10){
    x=r*x-d;
    cout << x <<endl;
  }
}


Measured memory_bytes: 256
<?php
$W=trim(fgets(STDIN));
$Wl=strlen($W);
for($k=0;$k<$Wl;$k++){
  $n=ord($W[$k]);
  if($n<65) continue;
  if($n<91) $W[$k]=chr($n+32);
}

$C=0;
while(1){
  $T=trim(fgets(STDIN));
  if($T=='END_OF_TEXT') break;

  $Tl=strlen($T);
  for($k=0;$k<$Tl;$k++){
    $n=ord($T[$k]);
    if($n<65) continue;
    if($n<91) $T[$k]=chr($n+32);
  }

  foreach(explode(' ',$T) as $t) if($t==$W) ++$C;
}
echo $C;
?>

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

using namespace std;

int main(){
	string s;
	cin >> s;

	for(int i =0;i < s.size();i++){
		if(s[i] == ',')cout << " " ;
		else cout << s[i];
	}
	cout << endl;
	

	return 0;
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
string str;
string mess;
int main(){
	int n;
	cin>>n;
	for(int i = 0;i <n;i++){
		cin>>str;
		cin>>mess;
		reverse(str.begin(),str.end());
		for(int j = 0;j < str.length();j++){
			//cout <<j <<" "<<mess<<endl;
			if(str[j]=='A'){
				reverse(mess.begin(),mess.end());
			}else if(str[j]=='J'){
				string str1 =mess.substr(mess.length()-1,1);
				string str2 =mess.substr(0,mess.length()-1);
				mess =str1+str2;
			}else if(str[j]=='C'){
				string str1 =mess.substr(0,1);
				string str2 =mess.substr(1,mess.length()-1);
				mess =str2+str1;
			}else if(str[j]=='E'){
				if(mess.length()%2!=0){
					string str1 =mess.substr(0,mess.length()/2);
					string str2 =mess.substr(mess.length()/2+1,mess.length()/2);
					string str3 =mess.substr(mess.length()/2,1);
					mess =str2 +str3+ str1;
				}else if(mess.length()%2==0){
					string str1 =mess.substr(0,mess.length()/2);
					string str2 =mess.substr(mess.length()/2,mess.length()/2);
					mess =str2+str1;
				}
			}else if(str[j]=='P'){
				for(int k = 0;k <mess.length();k++){
					if(isdigit(mess[k])){
						if(mess[k]>='1'){
							mess[k]--;
						}else if(mess[k]=='0'){
							mess[k]='9';
						}
					}
				}
			}else if(str[j]=='M'){
				for(int k = 0;k <mess.length();k++){
					if(isdigit(mess[k])){
						if(mess[k]<='8'){
							mess[k]++;
						}else if(mess[k]=='9'){
							mess[k]='0';
						}
					}
				}
			}
		}
		cout <<mess<<endl;
	}
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

char a[10][10];

bool is_a(int i, int j) {
    return (a[i][j+1]=='1'&&a[i+1][j]=='1'&&a[i+1][j+1]=='1');
}
bool is_b(int i, int j) {
    return (a[i+1][j]=='1'&&a[i+2][j]=='1'&&a[i+3][j]=='1');
}
bool is_c(int i, int j) {
    return (a[i][j+1]=='1'&&a[i][j+2]=='1'&&a[i][j+3]=='1');
}
bool is_d(int i, int j) {
    return (a[i+1][j]=='1'&&a[i+1][j-1]=='1'&&a[i+2][j-1]=='1');
}
bool is_e(int i, int j) {
    return (a[i][j+1]=='1'&&a[i+1][j+1]=='1'&&a[i+1][j+2]=='1');
}
bool is_f(int i, int j) {
    return (a[i+1][j]=='1'&&a[i+1][j+1]=='1'&&a[i+2][j+1]=='1');
}
bool is_g(int i, int j) {
    return (a[i][j+1]=='1'&&a[i+1][j]=='1'&&a[i+1][j-1]=='1');
}

int main() {
    while(cin >> a[0]) {
        FOR(i,1,8) cin >> a[i];
        //rep(i,8) cout << a[i] << endl;
        rep(i,8) rep(j,8) {
            if(a[i][j] == '1') {
                if(is_a(i,j)) cout<<"A"<<endl;
                if(is_b(i,j)) cout<<"B"<<endl;
                if(is_c(i,j)) cout<<"C"<<endl;
                if(is_d(i,j)) cout<<"D"<<endl;
                if(is_e(i,j)) cout<<"E"<<endl;
                if(is_f(i,j)) cout<<"F"<<endl;
                if(is_g(i,j)) cout<<"G"<<endl;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 1136
H, W, M = map(int, input().split())
HW = []
for _ in range(M):
    HW.append(list(map(int, input().split())))

A = [0] * (H + 1)
B = [0] * (W + 1)
for h, w in HW:
    A[h] += 1
    B[w] += 1

a = max(A)
b = max(B)

cnt = A.count(a) * B.count(b) - len([0 for h, w in HW if A[h] == a and B[w] == b])

print(a + b - (cnt == 0))

Measured memory_bytes: 70856
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<math.h>
#include<functional>
#include<bitset>
#include<cassert>
using namespace std;
using lint = long long;
using ld = long double;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(lint i=n;i<(int)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int n, m;
string s;

void allred() {
	lint v1 = 0, v2 = 0;
	lint ans = 0;
	v1 = 1;
	REP(i, n - 1) {
		lint nv1 = (v1 + v2) % MOD;
		lint nv2 = v1;
		v1 = nv1;
		v2 = nv2;
	}
	ans += (v1 + v2) % MOD;
	v1 = 0; v2 = 1;
	REP(i, n - 1) {
		lint nv1 = (v1 + v2) % MOD;
		lint nv2 = v1;
		v1 = nv1;
		v2 = nv2;
	}
	ans += v1;
	cout << (ans % MOD + MOD) % MOD << endl;
	return;
}



void solve(vector<int> suc_red, int omn) {
	int th = omn;
	if(suc_red[0] % 2 == 0) th = min(th, suc_red[0] + 1);
	lint ans = 0;
	/*
	if((n - 1) % 2 && (n - 1) <= th) {
		ans += n;
	}*/
	vector<lint> dpr(n), dpb(n);
	dpr[0] = 0;
	dpb[0] = 1;
	queue<lint> q0;
	queue<lint> q1;
	lint sum0 = 1, sum1 = 0;
	q0.push(1);
	FOR(i, 1, n) {
		if(i % 2 == 1) {
			while(!q0.empty() && (int)q0.size() > (th + 1) / 2) {
				sum0 -= q0.front(); sum0 %= MOD;
				q0.pop();
			}
			dpr[i] = sum0;
		} else {
			while(!q1.empty() && (int)q1.size() > (th + 1) / 2) {
				sum1 -= q1.front(); sum1 %= MOD;
				q1.pop();
			}
			dpr[i] = sum1;
		}
		dpb[i] = dpr[i - 1];
		if(i % 2 == 0) {
			q0.push(dpb[i]);
			sum0 += dpb[i]; sum0 %= MOD;
		} else {
			q1.push(dpb[i]);
			sum1 += dpb[i]; sum1 %= MOD;
		}
	}
	FOR(i, 1, n) {
		if(i > th) break;
		if(i % 2 == 0) continue;
		ans += dpb[n - 1 - i] * i;
		ans %= MOD;
	}
	ans += dpr[n - 1]; ans %= MOD;
	cout << (ans % MOD + MOD) % MOD << endl;
	return;
}

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

	cin >> n >> m;
	cin >> s;
	if(s[0] == 'B') {
		REP(i, m) {
			if(s[i] == 'B') s[i] = 'R';
			else s[i] = 'B';
		}
	}

	vector<int> suc_red;
	int c = 0;
	REP(i, m) {
		if(s[i] == 'R') c++;
		else {
			if(c != 0) suc_red.pb(c);
			c = 0;
		}
	}
	if(c != 0) suc_red.pb(c);

	if(suc_red[0] == m) {
		allred();
		return 0;
	}
 	int omn = INF;
	int roopmx = (int)suc_red.size();
	if(s[m - 1] == 'R') roopmx--;
	REP(i, roopmx) {
		if(suc_red[i] % 2) omn = min(omn, suc_red[i]);
	}
	solve(suc_red, omn);
	return 0;
}
/* --------------------------------------- */


Measured memory_bytes: 5268
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define ABS(x) ( (x)>0 ? x : -(x) )
#define MIN(x,y) ( (x) < (y) ? (x) : (y) )
#define MAX(x,y) ( (x) > (y) ? (x) : (y) )

#define INF 1000000000



//typedef long long ll;

void swap(int* a, int* b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

/*

int binary_search(int* a, int n,int key)
{
	int low, middle, high;

	low = 0, high = n - 1;

	while (low <= high)
	{
		middle = (low + high) / 2;

		if (key < a[middle])
			high = middle - 1;
		else if (key > a[middle])
			low = middle + 1;
		else
			return 1;
	}
	return 0;
}

void reverse(int a[], int b, int e)
{
	int i;

	for (i = 0; i <= (e-b-1) / 2; i++)
	{
		swap(&a[b+i], &a[e - 1 - i]);
	}
}

void CountingSort(int A[],int k,int n)
{
	int B[2000000] = { 0 };

	int i, C[20000] = { 0 };

	for (i = 0; i < n; i++)
		C[A[i]]++;

	for (i = 0; i < k; i++)
		C[i + 1] += C[i];

	for (i = n - 1; i >= 0; i--)
		B[--C[A[i]]] = A[i];

	for (i = 0; i < n; i++)
	{
		printf("%d", B[i]);
		if (i != n - 1)
			printf(" ");
	}
	printf("\n");
}
*/

int partion(int A[], int p, int r)
{
	int x = A[r-1];
	int i, j;

	i = p - 1;

	for (j = p; j < r;j++)
	{
		if (A[j] <= x)
		{
			i++;
			swap(&A[i], &A[j]);
		}
	}
	//swap(&A[i++], &A[r-1]);

	for (j = 0; j < r; j++)
	{
		if (j == r - 1)
			printf("%d\n", A[j]);
		else if (j == i)
			printf("[%d] ", A[j]);
		else
			printf("%d ", A[j]);
	}
	return i;
}

int main()
{
	int n;
	int A[100000];

	scanf("%d", &n);

	int i;

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

	partion(A, 0, n);



}


Measured memory_bytes: 2104
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>

using namespace std;

#define ll long long int
#define pii pair<ll,ll>

struct BIT
{
    std::vector<int> bit;
    
    BIT(int size) : bit(size, 0){ }
    
    void add(int k, int x) {
        while (k < bit.size()) {
            bit[k] += x;
            k += k &-k;
        }
    }
    int sum(int k) {
        int res = 0;
        while (k > 0) {
            res += bit[k];
            k -= k&-k;
        }
        return res;
    }
};

struct UnionFind {
    vector<int> data;
    
    UnionFind(int size) : data(size, -1) { }
    
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y)
        {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

vector<vector<pii>> v;
ll score[10000];
int n,m;

ll infi = (ll)1e15;

ll dfs(ll from, ll s, ll depth)
{
    if(depth > 2100)
    {
        return infi;
    }
    ll mm = -infi;
    for(auto e = v[from].rbegin(); e != v[from].rend();e++)
    {
        auto c = e->first + s;
        if(score[e->second] < c)
        {
            score[e->second] = c;
            mm = max(mm, dfs(e->second, c, depth+1));
        }
    }
    if(from == n)
    {
        if(mm == -infi)
        {
            return score[from];
        }
        return max(score[from], mm);
    }
    return mm;
}

map<ll,ll> mm;

int main(void)
{
    ll n,k;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
    {
        ll a, b;
        cin >> a >> b;
        mm[a]+=b;
    }
    for(auto e: mm)
    {
        k -= e.second;
        if(k <= 0)
        {
            cout << e.first << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 4224
#include <iostream>
#include <utility>
#include <cstring>
using namespace std;
#define MOD 1000000007

int n, m, s[2010], t[2010];
long dpij, sum[2010][2010];

int main(){
	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> s[i];
	for (int i = 0; i < m; ++i) cin >> t[i];
	sum[0][0] = (s[0] == t[0]);
	for (int i = 1; i < n; ++i) sum[i][0] = sum[i-1][0] + (s[i] == t[0]);
	for (int j = 1; j < m; ++j) sum[0][j] = sum[0][j-1] + (s[0] == t[j]);
	for (int i = 1; i < n; ++i){
		for (int j = 1; j < m; ++j){
			dpij = (s[i] == t[j]) ? (sum[i-1][j-1] + 1) : 0;
			sum[i][j] = (((sum[i-1][j] + sum[i][j-1]) % MOD - sum[i-1][j-1] + MOD) % MOD + dpij) % MOD;
		}
	}
	cout << (sum[n-1][m-1] + 1);
}

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

int main(){
	int mt[10];
	for(int i = 0; i < 10; i++)
		cin >> mt[i];
	for(int i = 0; i < 3; i++){
		for(int j = i + 1; j < 10; j++){
			if(mt[i] < mt[j]){
				int z = mt[i];
				mt[i] = mt[j];
				mt[j] = z;
			}
		}
	}

	cout << mt[0] << endl << mt[1] << endl << mt[2] << endl;
}

Measured memory_bytes: 1160
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1e9,maxn=3e5+5;
int n,a[maxn],b[maxn];
int main(){
	scanf("%d",&n);
	LL mn=1e18,ok=1,sum=0;for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),sum+=a[i],ok&=(a[i]==b[i]),mn=min(mn,a[i]>b[i]?b[i]:(LL)1e9);
	if(ok)return puts("0"),0;printf("%lld\n",sum-mn);

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
const ll MOD=1e9+7;
const int INF=1<<30;
const int dy[4]={0,0,1,-1};
const int dx[4]={1,-1,0,0};

int hosuu[50][50];

int main(){
  int H,W; cin >> H >> W;
  vector<string> G(H);
  rep(i,H){
    cin >> G[i];
  }
  queue<pair<int,int> > que;
  que.push(make_pair(0,0));
  while(!que.empty()){
    int y,x;
    tie(y,x)=que.front();
    que.pop();
    rep(dir,4){
      int ny=y+dy[dir];
      int nx=x+dx[dir];
      if(0<=ny&&ny<H&&0<=nx&&nx<W&&G[ny][nx]=='.'&&hosuu[ny][nx]==0){
        hosuu[ny][nx]=hosuu[y][x]+1;
        que.push(make_pair(ny,nx));
      }
    }
  }
  int sum=0;
  rep(i,H){
    rep(j,W){
      if(G[i][j]=='#'){
        sum++;
      }
    }
  }
  if(hosuu[H-1][W-1]>0) cout << H*W-(sum+hosuu[H-1][W-1]+1) << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
	
	int n;
	
	int max;
	
	int map[5][5];
	
	bool checker;
	
	cin >> n;
	
	for(int loop = 0; loop < n; loop++){
		for(int y = 0; y < 5; y++){
			for(int x = 0; x < 5; x++){
				cin >> map[x][y];
			}
		}
		max = 0;
		for(int sx = 0; sx < 5; sx++){
			for(int sy = 0; sy < 5; sy++){
				for(int gx = 0; gx < 5; gx++){
					for(int gy = 0; gy < 5; gy++){
						if(sx > gx || sy > gy){
							continue;
						}
						checker = true;
						for(int x = sx; x <= gx; x++){
							for(int y = sy; y <= gy; y++){
								if(map[x][y] == 0){
									checker = false;
								}
							}
						}
						if(checker){
							if(max < (gx - sx + 1) * (gy - sy + 1)){
								max = (gx - sx + 1) * (gy - sy + 1);
							}
						}
					}
				}
			}
		}
		printf("%d\n", max);
	}
	
	
	return 0;
}

Measured memory_bytes: 1144
#include<cstdio>
#define MAX 100005
using namespace std;

int main(){
  int n, c[MAX], s[MAX], f[MAX], t, i, j;
  scanf("%d", &n);
  for(i = 0; i < n-1; i++) scanf("%d%d%d", &c[i], &s[i], &f[i]);
  for(i = 0; i < n-1; i++){
    t = 0;
    for(j = i; j < n-1; j++){
      if(t <= s[j]) t = s[j] + c[j];
      else t += f[j] - 1 - ((t-1) % f[j]) + c[j];
    }
    printf("%d\n", t);
  }
  printf("0\n");
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
typedef long long ll;
typedef double ld;
#define pll pair<ll,ll>
#define pii pair<int, int>
#define pb push_back
#define mp(x, y) make_pair((x), (y))
#define F first
#define S second
#define I insert
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pll>
#define vpii vector<pii>
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()

const ll Mod = 1e9 + 7;
const int N = 1005;
int n , m , u , v;
vi G[N];
int par[N];
int vis[N];
int a , b;
bool done = false;
vpll edges;
void dfs(int s , int p){
	vis[s] = 1;
	par[s] = p;
	for(auto it : G[s]){
		if(vis[it] == 0){
			dfs(it , s);
		}
		else if(!done && vis[it] == 1){
			a = s;
			b = it;
			pii ok = mp(a , b);
			unordered_set<int> ver;
			ver.insert(b);
			
			while(a != -1 && a != b){
				ver.insert(a);
				a = par[a];
			}
			bool ans = true;
			
			for(int i =0;i < m ; i++){
				if(edges[i].F == ok.F && edges[i].S == ok.S )
					continue;

				if(ver.find(edges[i].F) != ver.end() && ver.find(edges[i].S) != ver.end() && edges[i].F != par[edges[i].S] && edges[i].S != par[edges[i].S]){
					//trace(edges[i], par[edges[i].F] , par[edges[i].S]);
					ans = false;
					break;
				}
			}
			if(ans){
				done = true;
				cout << ver.size() << endl;
				for(auto it : ver)
					cout << it << '\n';
			}
		}
	}
	vis[s] = -1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0;i < m; i++){
		cin >> u >> v;
		edges.pb(mp(u , v));
		G[u].pb(v);

	}

	for(int i= 1;i <= n ;i++)
		if(vis[i] == 0)
			dfs(i , -1);
	if(!done)
	cout << -1 << endl;

	return 0;
}


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

int main()
{
    string S;
    cin >> S;

    for(int i = 0; i < S.size()-1; i++) {
        if(S[i] == 'A' && S[i+1] == 'C') {
            cout << "Yes" << endl;
            return 0;
        }
    }

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

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split(' ');
		int a = int.Parse(str[0]);
		int b = int.Parse(str[1]);
		int c = int.Parse(str[2]);
		string s = "";
		if(a < b && b < c){
			s = "Yes";
		} else {
			s = "No";
		}
		Console.WriteLine(s);
	}
}


Measured memory_bytes: 8832
N, M = map(int, input().split(" "))
botlist = []
ans = 0
for n in range(M):
    bot = list(map(int, input().split(" ")))
    
    botlist.append(bot)
#botlist
plist = list(map(int, input().split(" ")))

pushlist = [[]for i in range(2**N)]

for p in range(N):
    for q in range(2**N):
        if q % (2**(p+1)) <2**p:
            pushlist[q].append(0)
        else:
            pushlist[q].append(1) 

for A in pushlist:
    #print(A)
    g = 0
    faa = 0
    for B in botlist:
        g += 1
        cou = 0
        for c in range(B[0]):
            cou += A[B[c+1]-1]

        if cou % 2 == plist[g-1]:
            faa += 1
    if faa == M:
        ans += 1
    

print(ans)


    





Measured memory_bytes: 3188
def resolve():
    N = int(input())
    S = [int(i) for i in input().split()]
    int(input())
    T = [int(i) for i in input().split()]

    ans = 0
    # S.append(-1)
    for t in T:
        for s in S:
            if s == t:
                ans += 1
                break
        # i = 0
        # S[N] = t
        # while S[i] != t:
        #     i += 1
        # if i != N:
        #     ans += 1
    print(ans)


resolve()


Measured memory_bytes: 6340
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

typedef unsigned long long UL;
typedef long long LL;
#define LP(i, a, b) for (int i = int(a); i < int(b); i++)
#define LPE(i, a, b) for (int i = int(a); i <= int(b); i++)
typedef pair<int, int> PII;
typedef vector<vector<PII> > WAL;
typedef vector<vector<int> > SAL;
#define Ep 1e-13

#define INF 1e9
int const MaxSize = 1e5 + 10;
int H, W, h, w;

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("/Users/george/A_1.in", "r", stdin);

	cin >> H >> W >> h >> w;

	if (H % h || W % w) {
		cout << "Yes" << endl;

		int numSq = (H / h) * (W / w);

		int padding = H * W - numSq * h * w;

		int pv = (numSq / padding) + 1;

		LP(i, 0, H)
		{
			LP(j, 0, W)
			{

				if (i % h == h - 1 && j % w == w - 1)
					cout << -pv * (h * w - 1) - 1;
				else
					cout << pv;

				if (j < W - 1)
					cout << " ";
			}

			cout << endl;
		}

	} else {
		cout << "No";

	}

	return 0;
}


Measured memory_bytes: 1408
#include <map>
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, c[8][8]; vector<int> p; map<vector<char>, int> m;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &c[i][j]);
		}
	}
	vector<char> s; for (int i = 0; i < n; i++) s.push_back((char)(i));
	priority_queue<pair<int, vector<char> > > que; que.push(make_pair(-1, s));
	while (!que.empty()) {
		pair<int, vector<char> > state = que.top(); que.pop();
		vector<char> v = state.second;
		if (m[v] != 0) continue;
		m[v] = state.first;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				swap(v[i], v[j]);
				que.push(make_pair(state.first - c[i][j], v));
				swap(v[i], v[j]);
			}
		}
	}
	int ret = 0;
	for (map<vector<char>, int>::iterator i = m.begin(); i != m.end(); i++) {
		ret = max(ret, -(*i).second - 1);
	}
	printf("%d\n", ret);
	return 0;
}

Measured memory_bytes: 58944
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
    int H, N; cin >> H >> N;
    vector<int> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    ll sum = 0;
    sort(A.rbegin(), A.rend());
    for(int i = 0; i < N; i++){
        sum+= A[i];
        //cout << sum << endl;
        if(H <= sum){ 
            cout << "Yes" << endl;
            return 0;
        }
    }
    //if(H <= sum) cout << "Yes" << endl;
    cout << "No" << endl;
}

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		StringBuilder sb = new StringBuilder();
		sb.append(a * b + "\n");
		System.out.println(sb);
	}

}

Measured memory_bytes: 36260
import java.util.Scanner;

public class Main
{
	private static void swap(int r[],int a,int b)
	{
		int tmp=r[a];
		r[a]=r[b];
		r[b]=tmp;
	}
	public static void main(String[] args)
	{
		Scanner scan=new Scanner(System.in);
		int w=scan.nextInt();
		int n=scan.nextInt();
		int a,b;
		int[] r=new int[w];
		for(int i=0;i<r.length;i++){
			r[i]=i+1;
		}
		for(int i=0;i<n;i++){
			String[] tmp=scan.next().split(",");
			a=Integer.parseInt(tmp[0]);
			b=Integer.parseInt(tmp[1]);
			swap(r,a-1,b-1);
		}
		for(int i=0;i<r.length;i++){
			System.out.println(r[i]);
		}
		scan.close();
	}
}

Measured memory_bytes: 26040
n = int(input())
cards = []
tarou = 0
hanako = 0
for i in range(n):
    a, b = input().split()
    if a < b:
        hanako += 3
    elif a > b:
        tarou += 3
    else:
        hanako += 1
        tarou += 1
print(tarou, hanako)


Measured memory_bytes: 5600
s=input()

l=int(s[:2])
r=int(s[2:4])

ans=""

if l<=12 and l>=1:
  if r<=12 and r>=1:
    ans="AMBIGUOUS"
  else:
    ans="MMYY"
elif r<=12 and r>=1:
  ans="YYMM"
else:
  ans="NA"

print(ans)


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

using namespace std;

int main() {
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<int> dp(k);
  for (int i = 1; i <= k; i++) {
    for (int j = 0; j < n; j++) {
      if (a[j] <= i && dp[i - a[j]] == 0) dp[i] = 1;
    }
  }
  if (dp[k]) cout << "First" << endl;
  else cout << "Second" << endl;
  return 0;
}


Measured memory_bytes: 640
import sys
def myAnswer(N:int,Y:int) -> None:
   for i in range(N+1):
      for j in range(N+1-i):
         if(10000*i + 5000*j + 1000*(N-i-j)==Y):
            print(i,j,(N-i-j))
            sys.exit()
   print(-1,-1,-1)

def modelAnswer():
   return
def main():
   N,Y = map(int,input().split())
   myAnswer(N,Y)
if __name__ == '__main__':
   main()

Measured memory_bytes: 38768
import java.util.*;
 
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int R = sc.nextInt();
        int S = sc.nextInt();
        int P = sc.nextInt();
        char[] T = sc.next().toCharArray();

        int x = 0;
        int y = K;

        boolean[] pick = new boolean[N];

        long ans = 0;
        for (int i = 0; i < K; i++) {
            if (T[i] == 'r') ans += P;
            if (T[i] == 's') ans += R;
            if (T[i] == 'p') ans += S;
            pick[i] = true;
        }
        while (y < N) {
            if (T[x] != T[y] || !pick[x]) {
                if (T[y] == 'r') ans += P;
                if (T[y] == 's') ans += R;
                if (T[y] == 'p') ans += S;
                pick[y] = true;
            }
            x++;
            y++;
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 28164
#include<bits/stdc++.h>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 1e2 + 10;

int a[N];

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

int main() {

	int n = read(),val = read();
	For(i,1,n)a[i] = read();

	sort(a + 1,a + n + 1);

	int cnt = 0;
	For(i,1,n) if(a[i] <= val) val -= a[i],cnt++;
	if(val > 0 && cnt == n)cnt--;

	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 256
import java.util.List;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

class Main {

	int count = 0;

	public static void main(String[] args) {

		InputOutput stdIO = new InputOutput();

		int n = stdIO.getValue();
		List<Integer> values = stdIO.getLine();

		Main my = new Main();

		my.selectionSort(values, n);
		stdIO.outputLine(values);
		System.out.println(my.count);

		stdIO.close();
	}

	private void selectionSort(List<Integer> values, int n) {

		for (int i = 0; i < n - 1; i++) {
			int minj = values.get(i);
			int minindex = 0;
			for (int j = i; j < n; j++) {
				if (minj > values.get(j)) {
					minj = values.get(j);
					minindex = j;
				}
			}
			if(values.get(i) > minj) {
			values.set(minindex, values.get(i));
//			System.out.println(values);
			values.set(i, minj);
//			System.out.println(values);
			count++;
			}
//			System.out.println(count);
		}
	}
}

class InputOutput {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public int getValue() {
		int n = 0;
		try {
			n = Integer.parseInt(br.readLine());
		} catch (IOException e) {
			e.printStackTrace();
		}
		return n;
	}

	public List<Integer> getValueLines(int n) {
		List<Integer> values = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			values.add(getValue());
		}
		return values;
	}

	public List<Integer> getLine() {
		try {
			String[] s = br.readLine().trim().split(" ");
			List<Integer> ary = new ArrayList<>();
			for (int i = 0; i < s.length; i++) {
				ary.add(Integer.parseInt(s[i]));
			}
			return ary;
		} catch (IOException e) {
			e.printStackTrace();
		}
		return null;
	}

	public void close() {
		try {
			br.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public void outputLine(List<Integer> values) {
		StringBuilder line = new StringBuilder();
		for(int k = 0; k < values.size(); k++) {
			line.append(values.get(k) + " ");
		}
		System.out.println(line.delete(line.length()-1, line.length()));
	}
}

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()

const int N = 1e7;

int d[N];

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  string s, t;
  cin >> s >> t;
  int a = stoi(s + t);
  for (int i = 1; i * i < N; i++) d[i * i] = 1;
  if (d[a]) cout << "Yes" << '\n';
  else cout << "No" << '\n';
}


Measured memory_bytes: 15792
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n,s=0,i,j,k;
cin>>n>>k;
long long int a[n+1],dp[n+1];
a[0]=1000000000;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
dp[0]=0;
dp[1]=0;
for(i=2;i<=n;i++)
{
 s=100000000000;
for(j=1;j<=k;j++)
{
 if(i<j)
    break;
 if(s>dp[i-j]+abs(a[i]-a[i-j]))
    s=dp[i-j]+abs(a[i]-a[i-j]);
}
dp[i]=s;
}
cout<<dp[n]<<endl;


}


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

ll f(ll b, ll n) {
  if (n < b)
    return n;
  else
    return f(b, n / b) + n % b;
}

int main() {
  ll n, s;
  cin >> n >> s;
  if (n == s) {
    cout << n + 1 << endl;
    return 0;
  }

  for (ll b = 2; b * b <= n; ++b) {
    if (f(b, n) == s) {
      cout << b << endl;
      return 0;
    }
  }

  // n == x * b + y
  // s == x + y
  ll ans = -1;
  for (ll x = 1; x * x < n; ++x) {
    ll b = (n - s) / x + 1;
    if (b >= 2 && f(b, n) == s) ans = b;
  }
  cout << ans << endl;

  return 0;
}


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

int main(void)
{
    int N;
    std::cin >> N;

    std::vector<int> d(N);
    for(int i = 0; i < N; ++i)
    {
        std::cin >> d[i];
    }

    std::sort(d.begin(), d.end());

    int K_num = d[N / 2] - d[N / 2 - 1];

    std::cout << K_num << std::endl;

    return 0;
}

Measured memory_bytes: 640
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or(len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)


Measured memory_bytes: 31928
def updateS(S, prev):
  if len(S)==2 and S[0]==S[1]:
    new = S[0:2]
    S = ''
  elif S[0]!=prev:
    new = S[0]
    S = S[1:]
  else:
    new = S[0:2]
    S = S[2:]
  return S, new

S = input()
K=1
current = S[0]
S = S[1:]
while len(S)>0:
  #print(K,S,current)
  K += 1
  S, current = updateS(S, current)
print(K)

Measured memory_bytes: 3500
# 幅優先探索 #双方向探索
import sys
import queue

SPACE = 0

adjacents_list = (
    (1, 3),       # 0
    (0, 2, 4),    # 1
    (1, 5),       # 2
    (0, 4, 6),    # 3
    (1, 3, 5, 7), # 4
    (2, 4, 8),    # 5
    (3, 7),       # 6
    (4, 6, 8),    # 7
    (5, 7)        # 8
)

class State:
    def __init__(self, board, space, prev):
        self.board = board
        self.space = space
        self.prev = prev

def mininum_steps(start, goal):
    if start == goal:
        return 0
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    history = {}
    history[tuple(start)] = True
    while not q.empty():
        state = q.get()
        for adjacent in adjacents_list[state.space]:
            board = state.board[:]
            board[state.space] = board[adjacent]
            board[adjacent] = SPACE
            if tuple(board) in history:
                 continue
            if board == goal:
                return go_back(state)
            history[tuple(board)] = True
            next_state = State(board, adjacent, state)
            q.put(next_state)

step = 0
def go_back(state):
    global step
    if state is not None:
        step += 1
        go_back(state.prev)
    return step


initial_board = list(map(int, sys.stdin.read().split()))
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

print(mininum_steps(initial_board, goal))



Measured memory_bytes: 72784
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
int b[16];
int p[16];
int fie[31];
int fie2[31];

int main(void){
	scanf("%d %d",&n,&m);
	int all=0;
	for(int i=0;i<n;i++){
		scanf("%d",&b[i]);
		fie[i]=b[i];
		fie2[i]=b[i];
		all+=b[i];
	}
	int all2=0;
	for(int i=0;i<m;i++){
		scanf("%d",&p[i]);
		if(i%2==0)all2+=p[i];
	}
	int cnt=0,cnt2=0,now=0;
	for(int i=0;i<m;i++){
		for(int j=now;j<now+p[i];j++){
			if(fie[j]!=i%2){
				int k=j;
				while(fie[k]!=i%2 && k<n-1)k++;
				for(int l=k;l>j;l--){
					swap(fie[l],fie[l-1]);
					cnt++;
				}
			}
			if(fie2[j]!=(i+1)%2){
				int k=j;
				while(fie2[k]!=(i+1)%2  && k<n-1)k++;
				for(int l=k;l>j;l--){
					swap(fie2[l],fie2[l-1]);
					cnt2++;
				}
			}
		}
		now+=p[i];
	}
	if(all==n-all)printf("%d\n",min(cnt,cnt2));
	else if(all==all2){
		printf("%d\n",cnt2);
	}else printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 1032
n, m, q = list(map(int, input().split()))
a, b, c, d = [0] * q, [0] * q, [0] * q, [0] * q
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = [0] * (n+1)
A[0] = 1
ans = 0
def dfs(k):
    global ans
    if k == n+1:
        now = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        ans = max(ans, now)
    else:
        for i in range(A[k-1], m+1):
            A[k] = i
            dfs(k+1)

dfs(1)
print(ans)


Measured memory_bytes: 9168
n, m = map(int, input().split())
ac = [0] * n
wa = [0] * n
for i in range(m):
    sp, s = input().split()
    p = int(sp) - 1
    if s == 'AC' and ac[p] == 0:
        ac[p] += 1
    if s == 'WA' and ac[p] == 0:
        wa[p] += 1

for i in range(n):
    if ac[i] == 0:
        wa[i] = 0
print(sum(ac), sum(wa))



Measured memory_bytes: 45656
#include <iostream>
#include <cstdio>
#define abs(a,b) (a<b)?b-a:a-b

struct point{
    int x,y;
    
}P[90011];
int sum[90011];

int main(int argc, const char * argv[]) {
  
    int h,w,d,tmp;
    scanf("%d %d %d",&h,&w,&d);
    
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            scanf("%d",&tmp);
            P[tmp].x = i;
            P[tmp].y = j;
        }
    }
    
    for(int i=1;i<=d;i++){
        
        int l = i;
        int r = h*w;
        sum[i]=0;
        while(l<r && l+d <= r){
            sum[l+d] += sum[l];
            sum[l+d] += abs(P[l].x,P[l+d].x);
            sum[l+d] += abs(P[l].y,P[l+d].y);
            l += d;
        }
    }
    
    int cnt;
    scanf("%d",&cnt);

//    for(int i=1;i<=9;i++){
//        printf(" %d is %d\n",i,sum[i]);
//    }
    
    for(int i=0;i<cnt;i++){
        int l,r;
        
        scanf("%d %d",&l,&r);
        printf("%d\n",sum[r] - sum[l]);
    }
    
    return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
 
typedef long long ll;
typedef long double ld;
 
#define REP(i,a,n) for(int (i)=(a); (i)<(int)(n); (i)++)
#define rep(i,n) REP(i,0,n)
#define vec vector 

ll gcd(ll& a, ll& b){
  if(b == 0) return a;
  ll temp = a%b;
  return gcd(b, temp);
}


int main(){
  ll A, B, C;
  cin >> A >> B >> C;
  
  if(gcd(A, B) == 1){
    cout << "YES";
  }else{
    if(C % gcd(A, B) == 0){
      cout << "YES";
    }else{
      cout << "NO";
    }
  }
  
  
  
  
}

Measured memory_bytes: 256
n, m = gets.strip.split.map(&:to_i)
h = gets.strip.split.map(&:to_i)
r = Array.new(n,1)

m.times do
  a, b = gets.strip.split.map{|v| v.to_i-1}
  d = h[a]-h[b]
  r[a] = 0 if d <= 0
  r[b] = 0 if d >= 0
end
p (r-[0]).size


Measured memory_bytes: 23368
#include <stdio.h>
int i, j, k, n, m, a[1005], ans=0, d, x;
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
    	scanf("%d", &d);
    	for(j=1; j<=d; j++){
    	    scanf("%d", &x);
    	    a[x] = -1;
    	}
    }
    for(i=1; i<=n; i++){
    	if(a[i] != -1) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

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

int main(){
  int n,m;
  cin>>n>>m;
  string f="-1 -1 -1";
  if(m%1000>0)
    cout<<f<<endl;
  int a=0,b=0,c=0;
  bool baka=false;
  for(int j=0;j<=n;j++){
      for(int k=0;k<=n;k++){
        c=n-j-k;
        if(c+j+k==n&&10000*j+5000*k+1000*c==m&&c>=0){
          a=j;
          b=k;
          baka=true;
        }
        if(baka==true)
          break;
        c=0;
      }
    if(baka==true)
      break;
  }
  if(a==0&&b==0&&c==0)
    cout<<f<<endl;
  else
    cout<<a<<" "<<b<<" "<<c<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
in int read() {
	re int t=0;
	re char v=getchar();
	while(v<'0'||v>'9')v=getchar();
	while(v>='0'&&v<='9') {
		t=(t<<3)+(t<<1)+(v^48);
		v=getchar();
	}
	return t;
}
int n,m,ans,k;
bool vis[100002];
signed main(){
	n=read();m=read();
	while(m--){
		k=read();
		while(k--)vis[read()]=1;
	}
	for(re int i=1;i<=n;++i)if(!vis[i])++ans;
	printf("%d",ans);
}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

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

    int N;
    string S, T;
    cin >> N >> S >> T;

    string ans = "";
    REP(i, N) {
        ans += S[i];
        ans += T[i];
    }

    printf("%s\n", ans.c_str());

    return 0;
}


Measured memory_bytes: 256