akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  fspcnt = 0;
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}*/


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  string s;
  cin >> s;
  int n = s.size();
  int mindiff = 10000000;
  for(int i=0;i+2<n;i++){
     int N = 100*(s.at(i)-'0')+10*(s.at(i+1)-'0')+(s.at(i+2)-'0');
     mindiff = min(mindiff,abs(N-753));
  }
  cout << mindiff << endl; 
        
    
  
}

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

using namespace std;
int N, M, ans[10], fg=1;

int main(){
    cin >> N >> M;
    for (int i=1; i<=N; i++) ans[i]=-1;
    for (int i=1; i<=M; i++){
        int s, c;
        cin >> s >> c;
        if ((ans[s]!=-1&&ans[s]!=c)||(N>1&&s==1&&c==0)){
            cout << -1;
            return 0;
        }
        else ans[s]=c;
    }
    int res=0;
    for (int i=1; i<=N; i++){
        res*=10;
        if (ans[i]>=0) res+=ans[i];
        else if (i==1&&N>1) res+=1;
    }
    cout << res;
}


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

void CountTriangles(vector <int> A){

    int n=A.size();

    sort(A.begin(), A.end());

    ll cnt = 0;

    for( int i = n-1; i >= 1; i--){
        int l = 0, r = i-1;
        while( l < r){
            if( A[l] + A[r] > A[i]){

                // If it is possible with a[l], a[r]
                // and a[i] then it is also possible
                // with a[l+1]..a[r-1],a[r] and a[i]
                cnt += r - l ;

                //checking for more possible solutions
                r--;
            }
            else

                // if not possible check for
                // higher values of arr[l]
                l++;
        }
    }
    printf("%lld\n",cnt);

    //cout<<"No of possible solutions: "<<count;
}
int main(){
    int n;
    scanf("%d",&n);



    vector<int> A ;

    for(int i=0;i<n;i++)
    {
        int v;
        scanf("%d",&v);
        A.push_back(v);
    }

    CountTriangles(A);

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<unistd.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define ST first
#define ND second
#define ll long long
#define ld long double
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using namespace std;
using namespace __gnu_pbds;
 
// replace ll  with pair if multiset needed
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set secik;
 
const ll  INF = 1e9 + 9;
const ll  MOD = 1e9 + 7;
const long long LINF = (ll)1e18 + 3;
 
// secik.insert({x, t++});
// secik.erase(secik.lower_bound({x,-1}));
// *secik.find_by_order(x)).first << "\n";
// secik.order_of_key(x)
 
//random_device device;
//mt19937 gener(device());
//uniform_int_distribution<ll > gen(0,n-1);
//gen(gener); // generate random number

const int SIZE = 2100;
ll s;
ll dp[SIZE][3*SIZE];
ll pref[SIZE];
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> s;
	dp[0][0] = 1;
	pref[0] = 1;
	for(int i = 1; i <= s; i++) pref[i] = pref[i-1] + dp[0][i];
	for(int i = 1; i < SIZE; i++){
		for(int j = 3; j <= s; j++){
			dp[i][j] = pref[j-3];
		}
		pref[0] = dp[i][0];
		for(int j = 1; j <= s; j++) pref[j] = (pref[j-1] + dp[i][j]) % MOD;
	}
	
	ll ans = 0;
	
	for(int i = 0; i < SIZE; i++) ans = (ans + dp[i][s]) % MOD;
	
	if(ans < 0) ans += MOD;
	
	cout << ans;	













	
	return 0;
 
}

Measured memory_bytes: 44792
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int main()
{
   int n, a[N], dp[N];
   cin >> n;
   for ( int i=0; i<n; i++) cin >> a[i];
   dp[0]=0, dp[1]=abs(a[1]-a[0]);
   for ( int i=2; i<n; i++){
        int dif1= abs(a[i]-a[i-1]), dif2 = abs(a[i]-a[i-2]);
    dp[i]= min(dp[i-1]+dif1, dp[i-2]+dif2);
   }
   cout << dp[n-1];
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 2e5 + 5;

int n;
vector<int> a;
int b[maxn];
bool cmp(int x, int y)
{
    return x > y;
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &b[i]);
        a.push_back(b[i]);
    }
    sort(a.begin(), a.end(), cmp);
    for(int i=1; i<=n; i++)
    {
        int mid = n/2;
        if(b[i] < a[mid-1])
            printf("%d\n", a[mid-1]);
        else
            printf("%d\n", a[mid]);
    }
    return 0;
}
/****

****/


Measured memory_bytes: 3828
while True:
    a,op,b=input().split()
    if op=='?': break
    elif op=='+': print( int(a) +  int(b) )
    elif op=='-': print( int(a) -  int(b) )
    elif op=='*': print( int(a) *  int(b) )
    elif op=='/': print( int(a) // int(b) )


Measured memory_bytes: 5592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define debug(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec)
{ for (auto v : vec) os << v << ' '; os << '\n'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{ os << '(' << pa.first << ',' << pa.second << ')'; return os; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{ cerr << " " << H; debug_out(T...); }
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; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int n, d;
    cin >> n >> d;
    d *= 2;
    d++;
    cout << (n + d - 1) / d << endl;
}

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


Measured memory_bytes: 3608
N=int(input())
S=input()
L=[]
#print(int(ord(S[0]))+N)
for i in range(len(S)):
  if int(ord(S[i]))+N >= 91:
    ans=chr(int(ord(S[i]))+N-26)
  else:
    ans=chr(int(ord(S[i]))+N)
  L.append(ans)
print(''.join(L))

Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <fstream>
#include <iomanip>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }
template<typename V> void printVec(V v) {ll i=0;for(auto x : v){std::cout << " [" << i++ << "] " << x;} print();}

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

  ll N;
  std::cin >> N;

  ll ans = (N % 2 == 0) ? N : N * 2;
  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 256
(let ((n (read))
    (a (read))
    (b (read))
    (ans 0))
    (if (= a b)
        (setq ans 1)
        (if (and (< a b) (> n 1))
            (setq ans (+ (* (- n 2) (- b a)) 1))
        )
    )
    (format t "~D~%" ans)
)

Measured memory_bytes: 24244
#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    ll t,i;
    cin >> t;
    string s;

    map <string,ll> poll;
    map <string,ll>::iterator itr;

    while(t--)
    {
        cin >> s;

        if(!poll[s])
            poll[s]=1;

        else
            poll[s]++;
    }
    int ocMax = 0;

    for (itr = poll.begin(); itr != poll.end(); ++itr)
    {
        //cout << itr-> first << " " << itr->second <<endl;
        if ( itr -> second >= ocMax)
        {
            ocMax = itr -> second;
        }
    }

    for (itr = poll.begin(); itr != poll.end(); ++itr)
    {
        if ( itr -> second == ocMax)
        {
            cout << itr -> first << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 19228
#include <iostream>

int main()
{
	long long a, b;
	long c, d;
	std::cin >> a >> b >> c >> d;
	long long byc, byd,bycd;
	long long gcd;
	long long temp1,temp2;
	temp1 = c < d ? c : d;
	gcd = c >= d ? c : d;
	while (true) {
		temp2 = gcd % temp1;
		
		if (temp2 == 0)break;

		gcd = temp1;
		temp1 = temp2;
	}
	gcd = temp1;
	byc = b / c - (a - 1) / c;
	byd = b / d - (a - 1) / d;
	bycd = b / ((c * d)/gcd) - (a - 1) / ((c * d)/gcd);
	long long result = (b - a + 1) - (byc + byd - bycd);

	std::cout << result;
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
        int n,k,i,s=1;
        scanf("%d%d",&n,&k);
        for(i=0;i<n;i++){
                if(s*2<s+k) s=s*2;
                else s=s+k;
        }
        printf("%d\n",s);
        return 0;
}


Measured memory_bytes: 1704
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const ll MOD = 1000000007;
int N;
vector<int> G[100005];

ll dp[100005][2];

ll solve(int p, int v, int color){
  if(dp[v][color] != -1) return dp[v][color];
  if(G[v].size() == 1 && G[v][0] == p){
    return dp[v][color] = 1;
  }

  ll ret = 1;
  rep(i,G[v].size()){
    if(G[v][i] == p) continue;
    if(color == 0){
      ret *= (solve(v, G[v][i], 0) + solve(v, G[v][i], 1) ) % MOD;
      ret %= MOD;
    }else{
      ret *= solve(v, G[v][i], 0);
      ret %= MOD;      
    }
  }

  return dp[v][color] = ret;
}

int main(){
  cin >> N;
  rep(i,N-1){
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }

  rep(i,100005) rep(j,2) dp[i][j] = -1;
  
  cout << (solve(-1, 1, 0) + solve(-1, 1, 1)) % MOD << endl;
  
  return 0;
}


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

int main() {
  int n, a;
  cin >> n;
  
  a = n - n/1000*1000; // 下三桁

  if (n%1110 < 10 || a%111 == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


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

using namespace std;

long long Q[1005];
int top = -1;

int main() {
    long long n, x, ans = 0;
    cin >> n >> x;
    if(n - x > x) {
        Q[++top] = x;
        Q[++top] = n - x;
        Q[++top] = x;
        ans += n;
    }
    else {
        Q[++top] = x;
        Q[++top] = n - x;
        ans += n;
    }
    while(Q[top]) {
        long long k = Q[top - 1] / Q[top];
        ans += 2 * k * Q[top];
        Q[top + 1] = Q[top - 1] - k * Q[top];
        top ++ ;
    }
    ans -= Q[top - 1];
    printf("%lld\n", ans);
    return 0;
}

//21:56:00
//思考时间有点长。对全新模型的建立/理解能力不够强。

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
int main()
{
    long n,m;
    while(cin>>n>>m)
    {
        string s;
        fr(i,n)
        {
            cin>>s;
            cout<<s<<"\n";
            cout<<s<<"\n";
        }
    }
        return 0;

}




Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
int main() {
    int N;
    int d[110];
    int c = 0;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> d[i];
    sort(d, d+N, greater<int>());
    for(int i = 0; i < N; i++){
        if(d[i] == d[i + 1]) continue;
        c++;
    }
    cout << c << endl;
    
    return 0;
}

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

using namespace std;

int main(int argc, char const *argv[])
{
    string s;
    int count = 0;

    cin >> s;

    sort(s.begin(), s.end());

    if (s[1] == s[0])
        count++;
    if (s[2] == s[3])
        count++;
    if (s[0] == s[2] || s[0] == s[3] || s[1] == s[3] || s[1] == s[2])
        count--;

    if (count == 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define NUM 10000
int main(void)
{
	int num[NUM];
	int i, j;
	for (i = 0; i < NUM; i++){
		scanf("%d", &num[i]);
		if (num[i] == 0)break;
	}

	for (j = 0; j < NUM; j++){
		if (num[j] == '\0')break;
		printf("Case %d: %d\n", j + 1, num[j]);
	}

	return 0;
}

Measured memory_bytes: 636
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uld = unsigned long long;
const ll mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
template<class T> inline bool chmax(T &a,T& b){if(a < b){a = b; return true;} else return false;}
template<class T> inline bool chmin(T &a,T& b){if(a > b){a = b; return true;} else return false;}
int main(){
    int a,b;
    cin >> a >> b;
    cout << max({2*a-1,a+b,2*b-1}) << endl;
}

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

int main()
{
	string s;
	cin >> s;
	int n = s.size();
	bool N = false , W =false , S = false,E = false;
	rep(i,n)
	{
		if(s[i]=='N')N=true;
		if(s[i]=='W')W=true;
		if(s[i]=='S')S=true;
		if(s[i]=='E')E=true;
	}
	if(N!=S||W!=E)
	{
		cout<<"No"<<endl;
	}
	else
	{
		cout<<"Yes"<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
import Control.Applicative ((<$>))
import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = solve <$> B.getLine >>= print

solve :: ByteString -> Int
solve = joi 0

joi :: Int -> ByteString -> Int
joi lv bs | B.null bs = lv
          | otherwise = joi (max lv lv') rs
  where (lv', rs) = j bs

j :: ByteString -> (Int, ByteString)
j bs | B.null js = (0, B.empty)
     | otherwise = o (B.length js') rs
  where (_, js) = B.break (=='J') bs
        (js', rs) = B.span (=='J') js

o :: Int -> ByteString -> (Int, ByteString)
o lv bs | B.null os = (0, rs)
        | B.length os > lv = (0, rs)
        | otherwise = i (B.length os) rs
  where (os, rs) = B.span (=='O') bs

i :: Int -> ByteString -> (Int, ByteString)
i lv bs | B.null is = (0, rs)
        | B.length is < lv = (0, rs)
        | otherwise = (lv, rs)
  where (is, rs) = B.span (=='I') bs



Measured memory_bytes: 101236
#include <stdio.h>

int main(){
    int W,H,x,y,r;
    
    scanf("%d%d%d%d%d",&W,&H,&x,&y,&r);
    
    if((x+r)-W<=0 && (y+r)-H<=0 && x-r>=0 && y-r>=0)printf("Yes\n");
    else printf("No\n");
    
    return 0;
}


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

typedef long long ll;

const int MAXV = 1e5 + 10;
const int MAXN = 1e3 + 10;
const ll INF = 1e13;

ll dp[MAXV];
int N,W,V,wi[MAXN],vi[MAXN];

int main(){

	cin >> N >> W;
	for(int i = 1;i<=N;i++){
		cin >> wi[i] >> vi[i];
		V += vi[i];
	}

	for(int i = 1;i<=V;i++) dp[i] = INF;
	dp[0] = 0;
	
	for(int item = 1;item<=N;item++){
		int w = wi[item], v = vi[item];
		for(int i = V;i>=v;i--){
			dp[i] = min(dp[i],dp[i - v] + w);
		}
	}

	for(int i = V;i>=0;i--){
		if(dp[i] <= W){
			cout << i << endl;
			break;
		}
	}

	return 0;

}

Measured memory_bytes: 1024
N,Q = map(int, input().split())
answer = (N-2)**2

q1 = [(N,N-2)]
q2 = [(N,N-2)]

def binary_search(q,n):
  left = 0
  right = len(q) - 1
  while right > left:
    index = (left + right) // 2
    if q[index+1][0] > n:
      left = index + 1
    else:
      right = index
  return left

for _ in range(Q):
  n,x = map(int, input().split())
  if n == 1:
    index = binary_search(q1,x)
    q = q1[index]
    answer -= q[1]
    if index == len(q1)-1:
      q1.append((x,q[1]))
      q2_last = q2[-1]
      q2[-1] = (q2_last[0],x-2)
  if n == 2:
    index = binary_search(q2,x)
    q = q2[index]
    answer -= q[1]
    if index == len(q2)-1:
      q2.append((x,q[1]))
      q1_last = q1[-1]
      q1[-1] = (q1_last[0],x-2)
      
print(answer)

Measured memory_bytes: 88292
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

template<class T> inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
void cmps(vector<int>&v,int &i){
	i=lower_bound(all(v),i)-v.begin();
}
constexpr int mod = 998244353;
constexpr int inf = 3e18;

int mod_pow(int x,int y,int m=mod){
	int res=1;
	while(y>0){
		if(y&1)res=res*x%m;
		y>>=1;x=x*x%m;
	}
	return res;
}
int perm[1000001],inv[1000001];
void init_perm(){
	perm[0]=1;
	REP(i,1000001)perm[i]=perm[i-1]*i%mod;
	inv[1000000]=mod_pow(perm[1000000],mod-2);
	for(int i=999999;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
}
int nCk(int x,int y){
	if(x<y)return 0;
	return perm[x]*inv[x-y]%mod*inv[y]%mod;
}


signed main(){
	init_perm();
	int N,A,B,K;cin>>N>>A>>B>>K;
	int ans=0;
	rep(i,N+1){
		if((K-A*i)%B||K<A*i)continue;
		int j=(K-A*i)/B;
		ans+=nCk(N,i)*nCk(N,j)%mod;
		ans%=mod;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    string S;
    cin >> N;
    cin >> S;
    vector<int> ans(N+1);
    ans.push_back(0);
    int tmp = 0;
    for (int i = 0; i < N; i++){
        if (S[i] == 'I') tmp++;
        else tmp--;
        ans.at(i+1) = tmp;
    }

    cout << *max_element(ans.begin(), ans.end()) << endl;
}

Measured memory_bytes: 256
import copy
N = int(input())
A = [[i for i in item] for item in input().split()]

B = copy.deepcopy(A)

def bubbleSort(A, N):
    for i in range(N):
        for i in reversed(range(i, N-1)):
            if A[i][1] > A[i+1][1]:
                A[i], A[i+1] = A[i+1], A[i]

    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res



def selectionSort(A, N):
    cnt = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
    
    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res

A_res = bubbleSort(A, N)
B_res = selectionSort(B, N)

print(*A_res)
print('Stable')
print(*B_res)
if A_res == B_res:
    print('Stable')
else:
    print('Not stable')


Measured memory_bytes: 6348
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

N,Q=map(int,input().split())
a=[0]*(N-1)
b=[0]*(N-1)
p=[0]*Q
x=[0]*Q
c=[[] for _ in range(N)]  #接続リスト
cnt=[0]*N  #カウンター値

for i in range(N-1):
  a[i],b[i]=map(int,input().split())
  c[a[i]-1].append(b[i]-1)
  c[b[i]-1].append(a[i]-1)
for i in range(Q):
  p[i],x[i]=map(int,input().split())
  cnt[p[i]-1] += x[i]

def dfs(x,parent):
  if parent!=-1:
    cnt[x] += cnt[parent]
  for child in c[x]:
    if child!=parent:
      dfs(child,x)

dfs(0,-1)
print(*cnt)

Measured memory_bytes: 256232
// #pragma GCC optimize("O3", "unroll-loops")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

#define endl '\n'
#define int long long
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define point pair <double, double>
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl

void __print(int x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "\n[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const int INF = 1e16 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;

void solve(){
  int n, weight, w, p;
  cin >> n >> weight;
  vector <int> dp(n*1000 + 5, INF);
  dp[0] = 0;
  for(int i = 1; i <= n; i++){
     cin >> w >> p;
     for(int j = n*1000; j >= 1; j--){
        if((j-p) >= 0){
           dp[j] = min(dp[j], dp[j-p] + w);
        }
     }
  }
  int ans = 0;
  for(int i = 1; i <= n*1000; i++){
     if(dp[i] <= weight) ans = i;
  }
  cout << ans << '\n';
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
        clock_t t1 = clock();
  int t = 1; //cin >> t;
  while(t--){      
     solve();
  }
        clock_t t2 = clock();
  //cout << "Time-Taken: " << ((t2 - t1) / (double)CLOCKS_PER_SEC) << endl;      
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int a,b,c,d;
    
    cin >> a >> b >> c >>d;
    
    //if (abs(c - a) < d){
    //    cout << "YES";
    //}else if (c - b < d && b - a < d){
    if (abs(c - b) <= d && abs(b - a) <= d){
        cout << "Yes";
    }else if (abs (c - a) <= d){
        cout << "Yes";
    }
    else{
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	ll H, W, K;
	cin >> H >> W >> K;
	VVLL MAP;   //1->あり
	MAP.resize(W+1, VLL(H+1,0));
	VVLL MAPP;
	MAPP.resize(W + 1, VLL(H + 1, 0));
	for (ll y = 1; y <=H; y++) {
		string S;
		cin >> S;
		for (ll x = 1; x <= W; x++) {
			if (S[x - 1] == '#') {
				MAP[x][y] = 1;
				MAPP[x][y] = 1;
			}
			
		}
	}
	for (ll y = 1; y <= H; y++) {
		for (ll x = 1; x <= W; x++) {
			MAPP[x][y] += MAPP[x - 1][y] + MAPP[x][y - 1] - MAPP[x - 1][y - 1];
		}
	}
	VVLL ans;
	ans.resize(W+1, VLL(H+1, 0));
	ll sy = 1;
	for (; sy <= H; sy++) {
		if (MAPP[W][sy] != 0)break;
	}
	ll count = 0;
	for (ll y = sy; y <= H; y++) {
		//その段にイチゴがある
		if (MAPP[W][y] != MAPP[W][y - 1]) {
			count++;
			ll x = 1;
			for (; x <= W; x++) {
				if (MAP[x][y] == 0)ans[x][y] = count;
				else break;
			}
			ans[x++][y] = count;
			for (; x <= W; x++) {
				if (MAP[x][y] == 0)ans[x][y] = count;
				else {
					count++;
					ans[x][y] = count;
				}
			}
		}
		else {
			for (ll x = 1; x <= W; x++) {
				ans[x][y] = ans[x][y-1];
			}
		}
	}
	for (ll y = sy - 1; y >= 1; y--) {
		for (ll x = 1; x <= W; x++) {
			ans[x][y] = ans[x][y + 1];
		}
	}
	for (ll y = 1; y <= H; y++) {
		for (ll x = 1; x <= W; x++) {
			cout << ans[x][y] << " ";
		}
		cout << "\n";
	}
	return 0;
}


Measured memory_bytes: 2944
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

string S;

int main() {
	cin >> S;
	if (S == "Sunny")cout << "Cloudy" << endl;
	if (S == "Cloudy")cout << "Rainy" << endl;
	if (S == "Rainy")cout << "Sunny" << endl;
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var a,b int
	fmt.Scan(&a,&b)

	if a > b {
		fmt.Println(a + a - 1)
	} else if a == b {
		fmt.Println(a + b)
	} else {
		fmt.Println(b + b - 1)
	}
}

Measured memory_bytes: 512
#include<stdio.h>
#define true 1
#define false 0

int main(){
  int n, x,i,r;
  int count=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
    r = isPrime(x);
    count = count + r;
  }
  printf("%d\n",count);

  return 0;
}

int isPrime(int x){
  int i;
  
  if(x==2) return true;

  if(x<2) return false;
  if(x%2==0) return false;

  i=3;
  while(i*i<=x){
    if( x % i == 0) return false;
    i = i + 2;
  }
  return true;
}



Measured memory_bytes: 2084
use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    let m = 1000000007;
    let mut dp = vec![vec![vec![0usize; 2]; 2]; n + 1];
    dp[0][0][0] = 1;

    for i in 0..n {
        for j in 0..2 {
            for k in 0..2 {
                for num in 0..=9 {
                    let next_j = if j != 0 || num == 0 { 1 } else { 0 };
                    let next_k = if k != 0 || num == 9 { 1 } else { 0 };
                    dp[i + 1][next_j][next_k] += dp[i][j][k];
                    dp[i + 1][next_j][next_k] %= m;
                }
            }
        }
    }

    println!("{}", dp[n][1][1]);
}


Measured memory_bytes: 150252
N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

vc = []
i = 0
for v in V:
    vc.append(V[i] - C[i])
    i += 1

d_sum = 0
for d in vc:
    if 0 < d:
        d_sum += d

print(d_sum)


Measured memory_bytes: 3060
A,B = input().split()
A=int(A)
B=int(B)
if A==1or B==1 :
  if A!=B:
    print("Alice" if A==1 else("Bob"))
  else:
    print("Draw")
else:
  if A!=B:
    print("Alice" if A-B>0 else("Bob"))
  else:
    print("Draw")

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


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

using ll = long long;

ll k, a, b;

int main(){
    cin >> k >> a >> b;
    if(k < a || b - a <= 2) cout << k + 1 << endl;
    else cout << (a + (k + 1 - a) / 2 * (b - a) + (k + 1 - a) % 2) << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define INF (2000000000)
using namespace std;

typedef vector<int> VI;
typedef vector<int>::iterator VII;
typedef vector<double> VD;
typedef vector<double>::iterator VDI;


int dp[5][100001];

int main()
{
	dp[0][0] = 1;
	for (int i = 1; i <= 400; i++){
		for (int j = 1; j <= 4; j++){
			for (int k = i * i; k <= 100000; k++){
				dp[j][k] += dp[j - 1][k - i * i];
			}
		}
	}
	
	int n;
	while (scanf("%d", &n), n){
		int sum = 0;
		for (int i = 1; i <= 4; i++){
			sum += dp[i][n];
		}
		
		printf("%d\n", sum);
	}
	
	return 0;
}

Measured memory_bytes: 2756
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp make_pair
#define F first
#define S second
#define pf pop_front
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=200005;
const ll inf=1e9+7;
int a,b,c;
int main()
{
    while(cin>>a>>b>>c)
    {
        set<int> s;
        s.insert(a);
        s.insert(b);
        s.insert(c);
        cout<<s.size()<<"\n";
    }
}


Measured memory_bytes: 256
#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(){
  int h, w;
  cin >> h >> w;
  vector<vector<int>> sum(h+1,vector<int>(w+1));
  rep(i,h) rep(j,w) cin >> sum[i+1][j+1];
  rep(i,h+1) for(int j = 1; j <= w; j++) sum[i][j] += sum[i][j-1];
  rep(i,w+1) for(int j = 1; j <= h; j++) sum[j][i] += sum[j-1][i];
  int ans = 0;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      int l = 0;
      int r = min(w-j,h-i) + 2;
      while(r-l > 1) {
        int m = (l+r) / 2;
        if(sum[i+m-1][j+m-1]-sum[i+m-1][j-1]-sum[i-1][j+m-1]+sum[i-1][j-1] == 0) l = m;
        else r = m;
      }
      ans = max(ans,l*l);
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 10452
import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
N = int(input()); MOD=pow(10,9)+7

beki = [-1]*(N+1); beki[0] = 1; beki[1] = 2 #階乗
for i in range(2,N+1):
  beki[i] = beki[i-1]*2%MOD
#print(beki)

G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b);G[b].append(a)
#print(G)
ans = 0

def dfs(v,p): #自分と親
  global ans #ansをGlobal変数として宣言
  res = 1 #戻り値。vを含めた部分木のサイズ。自分の分で最初は1
  ts = [] #vから生えている部分木のリスト
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) #uの部分木のサイズが戻り値
    res += t
    ts.append(t)
  if p != -1: #根以外なら親側の部分木が存在する。
    ts.append(N-res)
  now = beki[N-1] - 1 #自分以外を決めるのが2^(N-1)通り。自分以外が全部0が1通り。
  for x in ts:
    now -= beki[x] - 1 #各部分木に一個以上黒がある場合の数。全通り - 全部白
  ans = (ans+now)%MOD
  return res #vを含めた部分木のサイズ

dfs(0,-1)
ALL = pow(2,N,MOD)
#print(ans,ALL)
ans = ans*pow(ALL,MOD-2,MOD)%MOD #フェルマーの小定理より1/ALL = ALL^(MOD-2)
print(ans)
           

Measured memory_bytes: 188476
/*input
4 5
1 2
2 3
2 4
4 1
4 3
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=1005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,y)
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
vector<int> v[maxn];
int prev1[maxn];
int main() {
    string a;
    cin>>a;
    set<char> s;
    REP(i,a.length()) s.insert(a[i]);
    if (s.count('N') != s.count('S')) {
		cout << "No" << endl;
	}else
	if (s.count('W') != s.count('E')) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
}


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

using namespace std; 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>; 

#define INF 1000000000000000000
#define MOD 10007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

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

  int memo=H[0];
  int ans=1;
  for(int i=1;i<N;i++){
    if(memo<=H[i]){
      ans++;
      memo=H[i];
    }
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 256
//#include "debug.h"
#include <string.h>
#include <limits.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 100000

int n;

int input() {
	if (scanf("%d", &n) < 0) return 0;
	return 1;
}

void init() {
}

typedef double T;

T f(long n) {
	T r = n;
	int s = 0;
	while(n) s += n%10, n /= 10;
	return r/s;
}

vector<long> check(vector<pair<T,long>> &a) {
	vector<long> r;
	sort(a.begin(), a.end());
	int n = unique(a.begin(), a.end()) - a.begin();
	long m = LONG_MIN;
	for (int i=0; i<n; i++) {
		if (m < a[i].second) r.push_back(a[i].second);
		m = max(m, a[i].second);
	}
	return r;
}

long solve() {
	vector<pair<T,long>> a;
	long b = 1;
	for (int i=0; i<15; i++) {
		for (int j=1; j<150; j++) {
			long x = b*j-1;
			if (x) a.push_back({f(x), x});
		}
		b *= 10;
	}
	vector<long> r = check(a);
	for (int i=0; i<n; i++)
		printf("%ld\n", r[i]);
	return 1;
}

void output(long ans) {
}

void cleanup() {
}

/*
void pre() {
	int n = 400000;
	vector<pair<T,int>> a;
	for (int i=1; i<=n; i++) {
		a.push_back({f(i),i});
	}
	for (auto x: check(a)) p(x);
}
*/

int main() {
	//pre(); return 0;
	while (input()) {
		init();
		output(solve());
		cleanup();
		//break;
	}
}





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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

string table[10]={
"",
"\',.!?",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};

signed main(){
    string S;
    while(cin>>S){
        int cur=0;
        string ans;
        while(cur<S.size()){
            int next=cur;
            while(next<S.size()&&S[cur]==S[next])next++;
            int len=next-cur;
            if(S[cur]=='0'){
                if(cur)len--;
                ans+=string(len,' ');
            }
            else{
                len--;
                int t=S[cur]-'0';
                char c=table[t][len%table[t].size()];
                if(len%(2*table[t].size())>=table[t].size())c=toupper(c);
                ans+=c;
            }
            cur=next;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 3188
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))
    ruiseki = [0] * n
    ruiseki[0] = A[0]
    for i in range(1, n):
        ruiseki[i] = ruiseki[i - 1] + A[i]

    idx = 0
    for i in range(n - 1):
        if ruiseki[i] * 2 < A[i + 1]:
            idx = i + 1

    print(n - idx)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 63856
n = int(input())
a = [int(i) for i in input().split()]

count = 0
for i in range(8):
    if len(list(filter(lambda x:i*400<=x and x<400*(i+1), a))) > 0:
        count+=1

x = len(list(filter(lambda x:3200<=x, a)))
if count==0:
    count=1
    x-=1

print("{} {}".format(count, count+x))

Measured memory_bytes: 3064
import bisect

A, B, Q = map(int, input().split())
INF = 10**18
s = [-INF] + [int(input()) for y in range(A)] + [INF]
t = [-INF] + [int(input()) for z in range(B)] + [INF]


for i in range(Q):
    x = int(input())
    a = bisect.bisect_right(s, x)
    b = bisect.bisect_right(t, x)
    cost = INF
    for j in [s[a-1], s[a]]:
        for k in [t[b-1], t[b]]:
            d1, d2 = abs(j-x)+abs(j-k), abs(k-x)+abs(j-k)
            cost = min(cost, d1, d2)
    print(cost)


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }

typedef long long ll;
int const inf = 1<<29;

int main() {
  int N; cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];  
  A.erase(unique(A.begin(), A.end()), A.end());
  int ans = 1;
  REP(i, 2, A.size()) {
    if ((A[i - 2] < A[i - 1] && A[i - 1] > A[i]) ||
        (A[i - 2] > A[i - 1] && A[i - 1] < A[i])) {
      ans++;
      i++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
s=list(input())[::-1]
t=list(input())[::-1]
if len(s)<len(t):print('UNRESTORABLE')
else:
	for i in range(len(s)-len(t)+1):
		for j in range(len(t)):
			if s[i+j] not in ['?',t[j]]:break
		else:
			s[i:i+len(t)]=t
			break
	else:
		print('UNRESTORABLE')
		exit()
	print(''.join(s[::-1]).replace('?','a'))

Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <complex>
using namespace std;
const int mod = 200003;
const int N = 1 << 19;
const double pi = atan(1.) * 4;
typedef complex<double> C;
int b[mod], v[mod], f[mod], g[N];
long long r[mod];
C c[N], w[N];
void init() {
	for (int i = 0; i < N; i++) {
		w[i] = polar(1., 2 * pi * i / N);
	}
}
void fft(C *a, int inv = 0) {
	for (int i = 1, j = 0; i < N - 1; i++) {
		int s = N;
		do {
			s >>= 1;
			j ^= s;
		} while (~j & s);
		if (i < j) swap(a[i], a[j]);
	}
	for (int i = 2; i <= N; i *= 2) {
		int h = i / 2, inc = N / i;
		if (inv) inc = N - inc;
		for (int j = 0; j < N; j += i) {
			int wi = 0;
			for (int k = 0; k < h; k++) {
				C x = a[j+k], y = a[j+k+h] * w[wi];
				a[j+k] = x + y;
				a[j+k+h] = x - y;
				wi = (wi + inc) & (N - 1);
			}
		}
	}
	if (inv) {
		for (int i = 0; i < N; i++) {
			a[i] /= N;
		}
	}
}
int main() {
	int n;
	scanf("%d", &n);
	long long x = 2;
	b[1] = 0;
	for (int i = 1; i < mod - 1; i++) {
		b[x] = i;
		v[i] = x;
		x = x * 2 % mod;
	}
	v[0] = 1;
	for (int i = 0; i < n; i++) {
		int x; 
		scanf("%d", &x);
		if (x) f[b[x]]++;
	}
	for (int i = 0; i < mod; i++) {
		c[i] = f[i];
		r[(i+i)%(mod-1)] -= f[i];
	}
	init();
	fft(c);
	for (int i = 0; i < N; i++) {
		c[i] = c[i] * c[i];
	}
	fft(c, 1);
	for (int i = 0; i < N; i++) {
		long long x = real(c[i]) + 0.5;
		r[i%(mod-1)] += x;
	}
	long long ans = 0;
	for (int i = 0; i < mod - 1; i++) {
		ans += r[i] * v[i];
	}
	printf("%lld\n", ans / 2);
	return 0;
}


Measured memory_bytes: 22940
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long
using namespace std;
int main()
{
    int a, b, q;
    cin >> a >> b >> q;
    vector<ll> s(a+2),t(b+2),x(q);
    
    rep(i,a){
        cin >> s[i+1];
    }
    rep(i,b){
        cin >> t[i+1];
    }
    s[0]=-20'000'000'000;
    t[0]=-20'000'000'000;
    s[a+1]=30'000'000'000;
    t[b+1]=30'000'000'000;
    rep(i,q){
        cin >> x[i];
    }
    rep(i,q){
    ll sh1, sh2;
    ll te1, te2;
    auto e = upper_bound(s.begin(),s.end(), x[i]);
    auto g = upper_bound(t.begin(), t.end(), x[i]);
    sh1 = *e - x[i];//右
    sh2 = *(e - 1) - x[i];//左
    te1 = *(g)-x[i];//右
    te2 = *(g - 1) - x[i];//左
    ll ans = 30'000'000'000;
    ans = min(ans, max(sh1, te1)); //右s右t
    ans = min(ans, max(-sh2, -te2)); //左s左t
    ans = min(ans, min(sh1*2-te2,sh1-te2*2));//右s左t
    ans = min(ans, min(te1*2 - sh2, te1 - sh2*2));//右t左s
    cout << ans << endl;
    }
}


Measured memory_bytes: 3712
import java.io.IOException;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        Scanner input = new Scanner(System.in);
        
        int x = input.nextInt(); // 12
        
        int count = 0;
        
        for (int i = 1; i <= x; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                count += 1;
                //System.out.println(i);
                if (count == x)
                {
                    System.out.println(i);
                    System.exit(0);
                }
            }
        }
    }
}


Measured memory_bytes: 21204
#include<bits/stdc++.h>
#include <cctype>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  string s;
  cin>>s;
  if(s.at(a)=='-'){
      s.erase(s.begin()+a);
      for(int i=0;i<a+b;i++){
          if(isdigit(s[i]))continue;
          else{
               cout<<"No"<<endl;
               return 0;
      }
      }
      cout<<"Yes"<<endl;
  }
  else{
      cout<<"No"<<endl;
  }
}
      


Measured memory_bytes: 256
n = gets.to_i
balls = gets.split(" ").map(&:to_i).sort{|a,b| b<=>a}

h = Hash.new(0)
balls.each do |b|
  h[b] += 1
end

count = 0

twos = []
(1..31).each do |i|
  twos.push(2**i)
end
twos.reverse!

balls.each do |ball|
  next if h[ball] < 1
  h[ball] -= 1
  twos.each do |t|
    break if t < ball
    if h[t - ball] > 0
      h[t - ball] -= 1
      count += 1
      next
    end
  end
end

puts count

Measured memory_bytes: 34412
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int  a, b;
    cin >> a >> b;
    int res = 0;    
    int maxi = max(a,b);
    int mini = min(a,b);
    res += maxi;
    maxi--;
    cout << res+max(maxi,mini);
    cout << endl;
}


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

#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  rep(i, 5){
    int a;
    cin >> a;
    if(!a){
      cout << i + 1 << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3620
#include <iomanip>
#include <iostream>
#include <list>
#include <string>

#define REP(i,n) for(int i=0;i<n;++i)

using namespace std;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	list<int> l;
	cin >> n;
	REP(i, n) {
		string s;
		cin >> s;
		if (s[0] == 'i') {
			int x;
			cin >> x;
			l.push_front(x);
		}
		else {
			if (s[6] == 'F') {
				l.pop_front();
			}
			else if (s[6] == 'L') {
				l.pop_back();
			}
			else {
				int x;
				cin >> x;
				for (auto itr = l.begin();itr != l.end();++itr) {
					if (*itr == x) {
						l.erase(itr);
						break;
					}
				}
			}

		}
	}
	int i = 0;
	
	for (auto itr = l.begin(); itr != l.end();++itr) {
		if(i++)cout << " ";
		cout << *itr;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 34416
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef int in;
#define int long long
#define f first
#define s second
#define pb push_back
#define pp push
#define RETURN exit(0)
#define pow(x,y) (int)(pow(x,y))
#define ceil(x) (int)(ceil(x))
#ifndef ONLINE_JUDGE
#define debug(x) cout<<x<<endl;
#else
#define debug(x) 42
#endif
const int MAX=1e4;
const int MOD=1e9+7;
const int MAAX=1e15;
const long double EPS=1e-6;
const int N=1e6;
int power(int x,int y)
{
    if (y == 0)
        return 1;
    int a=power(x,y/2)%MOD;
    if (y % 2 == 0)
        return a * a % MOD;
    else
        return x * a % MOD * a % MOD;
}
long double sq(int x){
    long double s=0,e=x,mid;
    while(e-s>=EPS){
        mid=(s+e)/2;
        if(mid*mid<=x){
            s=mid;
        }
        else{
            e=mid-EPS;
        }
    }
    return s;
}
vector<int> primes;
bool visted[N+5];
void sieve(){
    visted[0]=visted[1]=1;
    for(int i=2;i*i<=N;i++){
        if(visted[i]==0){
            primes.pb(i);
            for(int j=i*i;j<=N;j+=i){
                visted[j]=1;
            }
        }
    }
    for(int i=sqrt(N)+1;i<=N;i++){
        if(visted[i]==0)
            primes.pb(i);
    }
    return;
}



in main()
{
    //freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
    int tc=1;
    //sieve();
    //scanf("%lld",&tc);
    while(tc--)
    {
        int n,k;
        cin>>n>>k;
        int ans1=0,ans2=0;
        long double ans=0;
        for(int i=1;i<=n;i++){
            int x=i,cou=1;
            while(x<k)
                cou*=2,x*=2;
            ans+=(1.0/n)*(1.0/cou);
        }
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }
    RETURN;
}


Measured memory_bytes: 256