akhauriyash/Code-Regression huggingface dataset:
import collections


Q = collections.deque()
n = int(input())

for _ in range(n):
    input_value = input().split()
    if input_value[0] == 'insert':
        Q.appendleft(input_value[1])
    elif input_value[0] == 'delete':
        if input_value[1] in Q:
            Q.remove(input_value[1])
    elif input_value[0] == 'deleteFirst':
        Q.popleft()
    elif input_value[0] == 'deleteLast':
        Q.pop()
    else:
        raise Error("illegal state")

print(' '.join(map(str, Q)))



Measured memory_bytes: 69728
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define INF 10000000
using ll = long long ;

using namespace std;

int main(){
    int w,h,n;
    cin >> w >> h >> n;
    int maxx=0,minx=w,maxy=0,miny=h;
    int ans;
    rep(i,n){
        int x,y,a;
        cin >> x >> y >> a;
        if (a==1){
            if (maxx < x) maxx = x;
        }
        if (a==2){
            if (minx > x) minx = x;
        }
        if (a==3){
            if (maxy < y) maxy = y;
        }
        if (a==4){
            if (miny > y) miny = y;
        }

    }
    ans = (minx-maxx) * (miny-maxy);
    if ((maxx>minx) || (maxy>miny)) ans = 0;
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(),b = sc.nextInt(),c=sc.nextInt();
        int count = 0;
        if(a/2+b/2==c&&b/2+c/2==a&&c/2+a/2==b){
            System.out.println(-1);
        } else {
            while(a%2==0&&b%2==0&&c%2==0){
                int tmpc = a/2+b/2, tmpa = b/2+c/2,tmpb = c/2+a/2;
                a = tmpa;
                b=tmpb;
                c=tmpc;
                count ++;
            }
            System.out.println(count);
        }
    }
}

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int nb;
	long long m=0,a=0,r=0,c=0,h=0;
	cin >> nb;
	string s;
	for (int i=0; i<nb; ++i){
		cin >> s;
		if (s[0] == 'M'){
			++m;
		}
      if (s[0] == 'A'){
         ++a;
      }
      if (s[0] == 'R'){
         ++r;
      }
      if (s[0] == 'C'){
         ++c;
      }
      if (s[0] == 'H'){
         ++h;
      }		
	}
	cout << m*a*r + m*a*c + m*a*h + a*r*c + a*r*h + a*c*h + r*c*h + m*r*c + m*c*h + m*r*h;
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
class BIT():
    def __init__(self, number):
        self.n = number
        self.list = [0] * (number + 1)

    def add(self, i, x):  # ith added x  1indexed
        while i <= self.n:
            self.list[i] += x
            i += i & -i

    def search(self, i):  # 1-i sum
        s = 0
        while i > 0:
            s += self.list[i]
            i -= i & -i
        return s

    def suma(self, i, j):  # i,i+1,..j sum
        return self.search(j) - self.search(i - 1)

N,M=map(int,input().split())
L=[[] for i in range(M+1)]
bit=BIT(M+1)
for i in range(N):
    l,r=map(int,input().split())
    L[r-l+1].append((l,r))
ans=N
for i in range(1,M+1):
    num=0
    for l,r in L[i]:
        ans-=1
        bit.add(l,1)
        bit.add(r+1,-1)
    num+=ans
    for j in range(i,M+1,i):
        num+=bit.search(j)
    print(num)


Measured memory_bytes: 83248
#include <iostream>

using namespace std;

int main(int argc, char** argv){
    int n;
    cin >> n;
    if(n == 0){
        cout << 0;
        return 0;
    }
    int mountains[n];
    for(int i = 0; i < n; i++){
        cin >> mountains[i];
    }
    int m = mountains[0];
    int total = 1;
    for(int i = 1; i < n; i++){
        if(mountains[i] >= m){
            total++;
            m = max(m, mountains[i]);
        }
    }
    cout << total;
    return 0;
}


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

int main(){
  int m,ns,nd,P[201];
  while(cin >> m >> ns >> nd , m){
    for(int i=0;i<m;i++){
      cin >> P[i];
    }
    int ans = 0;
    int mmax = -1;
    for(int i=nd;i>=ns;i--){
      int gapp = P[i-1] - P[i];
      if(mmax < gapp){
	mmax = gapp;
	ans = i;
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1160
#include<iostream>
#include<list>
#include<cstdio>
#include<stdlib.h>
#include<string>
using namespace std;
list<int> ls;
int main(){
	int n,a;
	cin>>n;
	string name;
	for(int i=0;i<n;i++){
		cin>>name;
		if(name[0] == 'i'){
			cin>>a;
			ls.push_front(a);
		}
		else if(name[6]=='F'){
			ls.pop_front();
		}
		else if(name[6]=='L'){
			ls.pop_back();
		}
		else{
			cin>>a;
			for(list<int>::iterator it =ls.begin(); it !=ls.end();it++){
				if(*it == a){
					ls.erase(it);
					break;
				}
			}
		}	
	}
	int i=0;
	for(list<int>::iterator it =ls.begin(); it !=ls.end();it++){
		if(i++)cout<<" ";
		cout<<*it;
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 34384
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
int main(){

    int n;
    scanf("%d",&n);

    bool flag=true;
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        int t,nx,ny;
        scanf("%d%d%d",&t,&nx,&ny);
        int dis=abs(nx-x)+abs(ny-y);
        nx=x,ny=y;
        if(dis>t)
            flag=false;
        else{
            if(dis%2==0 && t%2!=0)
                flag=false;
            else if(dis%2==1 && t%2!=1)
                flag=false;
        }
    }

    if(flag)
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

Measured memory_bytes: 256
package main
import "fmt"
func main(){
     var hp,n,at int
     sum:=0
     fmt.Scanf("%d %d",&hp,&n)
     for i:=0;i<n;i++{
         fmt.Scanf("%d",&at)
         sum+=at
     }
     if sum<hp{
        fmt.Println("No")
     }else{
        fmt.Println("Yes")
     }
}

Measured memory_bytes: 5504
#include<cstdio>//AT3855
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>

using namespace std;

int n,a,b;

int main(){
    scanf("%d%d%d",&n,&a,&b);
    if((b-a-1)%2){
        printf("Alice\n");
    }
    else{
        printf("Borys\n");
    }
    return 0;
}


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

using namespace std;

using int64 = long long;
using vint = vector<int>;

#define FOR(i, a, b) for(int64 i=(a); i<(b); i++)
#define ROF(i, a, b) for (int64 i=(a)-1; i>=(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define PRE(i, n) ROF(i, n, 0)

#define ALL(x) (x).begin(),(x).end()
#define OUT(x) cout << (x) << endl;
#define DUMP(x) cerr << (x) << endl;

#define INF INFINITY
#define eps 1e-14

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

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

    if (i == 3 or i == 5 or i == 7) {
        OUT("YES")
    }else{
        OUT("NO")
    }

    return 0;
}

Measured memory_bytes: 256
import sys

def Ss():
  return sys.stdin.readline().rstrip().split(' ')

def Is():
  ss = Ss()
  return map(int, ss) if len(ss) > 1 else int(ss[0])

a, b, c = Is()
k = Is()

while b <= a:
    b = b * 2
    k = k - 1
    
while c <= b:
    c = c * 2
    k = k - 1

print('Yes' if k >= 0 else 'No')

Measured memory_bytes: 9184
import sys

N = int(input())
Atmp = [0] + list(map(int, input().split()))
A = {}

for i,a in enumerate(Atmp):
    A[i] = a

#print(A)

X = {}

for i in reversed(list(range(1,N+1))):
    Xsum = 0
    j = 2
    while(i*j <= N):
        Xsum += X[i*j]
        j += 1
        continue
    odd = Xsum % 2
    if odd == A[i]:
        X[i] = 0
    else:
        X[i] = 1
    
M = 0
for i in range(1, N+1):
    if X[i] == 1:
        M += 1

print(M)
if M == 0:
    sys.exit()

xxx = []
for i in range(1, N+1):
    if X[i] == 1:
        xxx.append(str(i))

print(' '.join(xxx))


Measured memory_bytes: 106592
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
int a[100010],b[100010];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
   	int n=read();
	for(int i=1;i<=n+1;i++)a[i]=read();
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		int tot=read(),uf;
		uf=min(a[i],tot);
		a[i]-=uf,tot-=uf;ans+=uf;
		uf=min(a[i+1],tot);
		a[i+1]-=uf,tot-=uf;ans+=uf;
	}printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)
typedef long long ll;
const ll INF = 1LL<<60;
const ll MOD = 1000000007;

inline ll add(ll x, ll y) {return (x+y)%MOD;}
inline ll mul(ll x, ll y) {return (x*y)%MOD;}
inline ll sub(ll x, ll y) {
    ll res = x - y;
    if(res < 0) res += MOD;
    return res;
}


map<ll,ll> ans;
ll func(ll x) {
    if(ans.find(x)!=ans.end()) return ans[x];
    else {
        ans[x] = 1 + 2*func(x/2);
        return ans[x];
    }
}
int main(){
    ans[1] = 1;
    ll H; cin >> H;
    cout << func(H) << endl;
    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

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

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	ll sum = 0;
	vector<ll> a(n);
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];

		sum += a[i];
	}


	ll res = inf;
	ll s0 = 0;
	for (ll i = 0; i < n - 1; i++)
	{
		s0 += a[i];
		ll s1 = sum - s0;

		res = min(res, abs(s0 - s1));
	}

	println(res);
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int main()
{
   static long i,j,k,l;
   long n;
   long cnt = 0;
   int f;
   long left,right,mid;
   long ans = 0;
   cin >> n;
   for(i = 1;i <= n;i++) {
      f = 0;
      int x = i;
      if (i % 3 == 0) {
         cout << " " << i;
         f = 1;
      }
      while(1) {
         if( (x % 10 == 3) && f == 0) {
            cout << " " << i; break;
         }
         x /= 10;
         if(x == 0 || f == 1) break;
      }
   }
   cout << endl;

   return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

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

const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

template<class TYPE>
struct edge{
    TYPE to,cost; 
    edge(TYPE t,TYPE c){
        to = t;
        cost = c;
    }
};

int main(){
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    int sum = a + b + c;
    int maxi = max(a,max(b,c));
    int minus = maxi;
    for(int i = 1; i <= k; i++) minus *= 2;
    cout << sum - maxi + minus << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000+10;
int a[maxn];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

int main()
{
    // cout<<gcd(12,8)<<endl;
    long long sum = 0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i],sum+=a[i];
    cout<<sum-n;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int  a[100];
void revNum(int n)
{
    for(int i=0; i<3; i++)
    {
        a[i] = n%10;
        n /= 10;
    }
}

int main()
{
    int n,x,reversedNumber = 0, remainder;;
    cin>>n;

    while(1){
       revNum(n);
       if(a[0] == a[1] && a[1] == a[2] && a[0]==a[2]){
           cout<<n;
           break;
       }else{
           n++;
       }

    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

VV<int> G;
int I;
V<ll> a,ans;
void dfs(int v,int p){
	ans[v] = a[I++];
	for(int u:G[v]) if(u!=p){
		dfs(u,v);
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N;
	cin >> N;
	G.resize(N);
	rep(i,N-1){
		int x,y;
		cin>>x>>y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	a.resize(N);
	rep(i,N) cin >> a[i];
	sort(all(a),greater<ll>());
	ans.resize(N);
	dfs(0,-1);
	ll S = 0;
	rep(i,N) if(i) S+=a[i];
	cout<<S<<endl;
	rep(i,N) cout << ans[i] << " ";
	cout<<endl;
}


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

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) 0
#endif
//#define endl '\n'
#define pb push_back
#define mod 1000000007
typedef int integer;
#define int long long
using namespace std;

int powmod(int a, int b) {
    int res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

const integer NN = (int) 5e5 + 2;
int ar[NN];
int n, m, k, x;
string s;

integer main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
//    cin >> T;
    while (T--) {
        string t;
        cin >> s >> t;
        int ans = 0;
        for (int i = 0; i < s.length(); i++){
            ans += s[i] != t[i];
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3800
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

int N;
string S, T;

int main() {

	cin >> N >> S >> T;

	rep(i, N) {
		cout << S[i] << T[i];
	}

	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	const int MOD = 1e9+7;
	int n,k;
	cin >> n >> k;
	vector<ll> neg,po;
	for (int i = 0; i < n; ++i) {
		ll x; cin >> x;
		if (x > 0) po.push_back(x);
		else neg.push_back(x);
	}
	sort(rall(po)); // 9 8 7 ...
	sort(all(neg)); // -9 -8 ...
	int i1 = min(k,len(po));
	int i2 = k-i1;
	if (i2 % 2 == 1) { 
		if (i1 == 0 || i2 == len(neg)) {
			for (int x : neg) po.push_back(-x);
			sort(all(po));
			ll res = (MOD-1);
			for (int i = 0; i < k; ++i) {
				res = (res*po[i])%MOD;
			}
			cout << res << "\n";
			return 0;
		}
		--i1; ++i2;
	}
	while (i1 >= 2 && i2+1 < len(neg) && po[i1-1]*po[i1-2] < neg[i2]*neg[i2+1]) {
		i1 -= 2;
		i2 += 2;
	}
	ll res = 1;
	for (int i = 0; i < i1; ++i) {
		res = (res*po[i])%MOD;
	}
	for (int i = 0; i < i2; ++i) {
		res = (res*(neg[i]+MOD))%MOD;
	}
	cout << res << "\n";
}


Measured memory_bytes: 7940
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n, x[3001], y[3001], dx, dy, ans;
bool xy[5001][5001];

void solve(int x1, int y1, int x2, int y2){
	if(x1 == x2){
		ans = max(ans, dy * dy);
	} else if(y1 == y2){
		ans = max(ans, dx * dx);
	} else{
		if(dx < 0){
			dx = -dx;
		}
		if(dy < 0){
			dy = -dy;
		}
		ans = max(ans, (dy + dx) * (dy + dx) - (dy * dx) * 2);
	}

	return;
}

int main(){
	while(1){
		cin >> n;
		if(n == 0){
			break;
		}

		for(int i = 0; i < n; i++){
			cin >> x[i] >> y[i];
			xy[x[i]][y[i]] = 1;
		}

		for(int i = 0; i < n; i++){
			for(int j = i + 1; j < n; j++){
				dx = x[i] - x[j];
				dy = y[i] - y[j];

				if(x[i] + dy < 5001 && x[j] + dy < 5001 && x[i] + dy >= 0 && x[j] + dy >= 0 && y[i] - dx < 5001 && y[j] - dx < 5001 && y[i] - dx >= 0 && y[j] - dx >= 0){
					if(xy[x[i] + dy][y[i] - dx] == 1 && xy[x[j] + dy][y[j] - dx] == 1){
						solve(x[i], y[i], x[j], y[j]);
					}
				}
				if(x[i] - dy < 5001 && x[j] - dy < 5001 && x[i] - dy >= 0 && x[j] - dy >= 0 && y[i] + dx < 5001 && y[j] + dx < 5001 && y[i] + dx >= 0 && y[j] + dx >= 0){
					if(xy[x[i] - dy][y[i] + dx] == 1 && xy[x[j] - dy][y[j] + dx] == 1){
						solve(x[i], y[i], x[j], y[j]);
					}
				}
			}
		}

		cout << ans << endl;

		memset(xy, false, sizeof xy);
		ans = 0;
	}		
	return 0;
}

Measured memory_bytes: 25616
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <map>
#include <cstdlib>
#include <cctype>
#include <ctype.h>
#include <math.h>
#define ll long long
char toupper(char c);
char toupper(char c)
{
    return (c - 0x20);
}

using namespace std;
int main()
{
  int n;
  cin >> n;
  cout << n*n << endl;

return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include <set>
#include <queue>
#include <iomanip>
#include <sstream>
typedef long long ll;

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

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 long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[510][510];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}

int main() {
	string t;
	cin >> t;
	rep(i, t.size()-1) {
		if (t[i] == 'P') {
			if (t[i + 1] == '?') {
				t[i + 1] = 'D';
			}
		}
		else if (t[i] == '?') {
			if (t[i + 1] == 'D') {
				t[i] = 'P';
			}
			else if (t[i + 1] == 'P') {
				t[i] = 'D';
			}
			else if (t[i + 1] == '?') {
				t[i] = 'P';
				t[i + 1] = 'D';
			}
		}
	}
	if (t[t.size() - 1] == '?') {
		t[t.size() - 1] = 'D';
	}
	cout << t << endl;
}

Measured memory_bytes: 3744
from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.insert(0,-10**10)
S.append(2*10**10)
T = [int(input()) for _ in range(B)]
T.insert(0,-10**10)
T.append(2*20**10)
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    indt = bisect_right(T,x)
    dmin = 10**11
    d = x-S[inds-1]+abs(S[inds-1]-T[indt-1])
    dmin = min(dmin,d)
    d = x-S[inds-1]+abs(S[inds-1]-T[indt])
    dmin = min(dmin,d)
    d = S[inds]-x+abs(S[inds]-T[indt-1])
    dmin = min(dmin,d)
    d = S[inds]-x+abs(S[inds]-T[indt])
    dmin = min(dmin,d)
    d = x-T[indt-1]+abs(T[indt-1]-S[inds-1])
    dmin = min(dmin,d)
    d = x-T[indt-1]+abs(T[indt-1]-S[inds])
    dmin = min(dmin,d)
    d = T[indt]-x+abs(T[indt]-S[inds-1])
    dmin = min(dmin,d)
    d = T[indt]-x+abs(T[indt]-S[inds])
    dmin = min(dmin,d)
    print(dmin)

Measured memory_bytes: 102300
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
string s;
int q;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>s;
  int a,b;
  pair<string,int> l={"",0};
  pair<string ,int> r={"",0};
  cin>>q;
  int count=0;
  while(q--)
  {
      cin>>a;
      if(a==1)
      {
          count++;
          auto it=l;
          l.first=r.first;
          if(r.second==0)
          {
          l.second=r.first.size()-1;
          }
          else 
          {
               l.second=0;
          }


          r.first=it.first;
          if(it.second==0)
          {
               r.second=it.first.size()-1;
          }
          else
           r.second=0;
         
         
      }
      else
      {
          cin>>b;
          char ch;
          cin>>ch;
          if(b==1)
          {
            if(l.second!=0)
            {
               l.first+=ch;
               l.second+=1;
            }
            else
            {
                l.first.insert(l.first.begin(),ch);
            }
          }
          else 
          {
              if(r.second==0)
            {
               r.first+=ch;
            }
            else
            {
                r.first.insert(r.first.begin(),ch);
                r.second+=1;
            }
        
          }
      }
  } 
  string temp="";
  if(l.second==l.first.size()-1)
  {
    reverse(l.first.begin(),l.first.end());
    temp+=l.first;
  }
  else 
  {
      temp+=l.first;
  }
  if(count%2==0)
  {
     temp+=s;
  }
  else 
  {
      reverse(s.begin(),s.end());
      temp+=s;
  }

  if(r.second==r.first.size()-1)
  {
    reverse(r.first.begin(),r.first.end());
    temp+=r.first;
  }
  else 
  {
      temp+=r.first;
  }
  cout<<temp<<endl;
}

Measured memory_bytes: 1432
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
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; }
using ll=long long;
using namespace std;
int main(){
   string s;
   cin>>s;
   int answer=0;
   int a=0;
   for(int i=0;i<s.size();i++){
       if(s.at(i)=='A' ||s.at(i)=='C' ||s.at(i)=='G'||s.at(i)=='T') {
          a++; 
          answer=max(answer,a);
       }
       else{
          
          a=0;
        } 
   }
   cout<<answer<<endl;
}


Measured memory_bytes: 3544
import java.util.Scanner;

public class Main {

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

	    int N = Integer.parseInt(scanner.next());
	    long K = Long.parseLong(scanner.next());
	    int Q = Integer.parseInt(scanner.next());
	    int[] A  = new int[Q];
	    int[] num = new int[N];

	    for (int i=0; i<Q; i++) {
	        A[i]= Integer.parseInt(scanner.next());
	        num[A[i]-1]++;
	    }

        for (int i=0; i<N; i++) {
	        if (K - Q + num[i] > 0) {
	        	System.out.println("Yes");
	        }else {
	        	System.out.println("No");
	        }
	    }

	}

}

Measured memory_bytes: 60080
#include <stdio.h>

int main(void)
{
	int table[10] = {0x3f, 0x6, 0x5b, 0x4f, 0x66, 0x6d, 0x7d, 0x27, 0x7f, 0x6f};
	int n;
	int number;
	unsigned int data;
	
	while (1){
		data = 0;
		
		scanf("%d", &n);
		if (n == -1){
			break;
		}
		for (int i = 0; i < n; i++){
			unsigned int ans;
			scanf("%d", &number);
			
			ans = table[number] ^ data;
			for (int i = 0; i < 7; i++){
				printf("%d", ((ans >> (6 - i)) & 1));
			}
			data = table[number];
			
			puts("");
		}
	}
	
	return (0);
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
 
int main(){
 
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int long long n;
    cin >> n;
    int long long a[n];
    int long long i, j, k, ans;
 
    for(i = 0; i < n; i++){
        cin >> a[i];
    }
    
    int plus = 1;
    int minus = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == plus)
        {
            plus++;
        }
        else
        {
            minus++;
        }
    }
 
    if (minus == n)
    {
        minus = -1;
    }
 
    cout << minus << endl;
}

Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int total;

        Scanner inp = new Scanner(System.in);
        total = inp.nextInt();

        int[] a = new int[total];

        for (int k = 0; k < total; k++) {
            a[k] = inp.nextInt();
        }

        int swapcount = 0;

        for (int i = 0; i < a.length; i++) {
            for (int j = a.length - 1; j > i; j--) {
                if (a[j] < a[j - 1]) {
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;

                    swapcount++;
                }
            }
        }

        for (int l = 0; l < total; l++) {
            if (l == 0) {
                System.out.printf("%d", a[l]);
            } else {
                System.out.printf(" %d", a[l]);
            }
        }

        System.out.printf("\n" + swapcount+"\n");
    }
}



Measured memory_bytes: 26444
"""
list(map(int,input().split()))
map(int,input().split())
"""
import numpy as np
N,M = map(int,input().split())

arr = [list(input())for i in range(N)]

for i in range(N):
    for j in range(M):

        if arr[i][j] == "#":
            arr[i][j] = 0
        else:
            arr[i][j] = 1

arr = np.array(arr)
arr = np.pad(arr,1,"constant",constant_values=1)
key = 0

for i in range(N):
    for j in range(M):
        if arr[i+1][j+1] == 0:
            if arr[i+1][j+1] + arr[i][j+1] + arr[i+1][j] + arr[i+2][j+1] + arr[i+1][j+2] >= 4:
                key+=1

if key>=1:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 12528
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
const int SZ = 1e6;
int dp[SZ];
 
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    fill(dp, dp + SZ, 0);
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        dp[i + 1] = max(dp[i + 1], dp[i]);
        if (s[i] == '1' || i == 0 || i == n - 1) continue;
        if (s[i-1] != '1' || s[i + 1] != '1') continue;
        int i1 = i - 1, i2 = i + 1;
        while (s[i1] == '1' && i1 >= 0)
            i1--;
        while (s[i2] == '1' && i2 < n)
            i2++;
        for (int j = i1 + 1; j < i; j++)
            dp[i + 2] = max(dp[i + 2], i - j + dp[j]);
        for (int j = i2 - 1; j > i; j--)
            dp[j + 1] = max(dp[j + 1], j - i + dp[i - 1]);
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 4856
import numpy as np

class Combination : 
    def __init__ (self, N=10**6, mod=10**9+7) :
        self.mod = mod
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]
        for i in range(2, N+1) :
            self.fact.append( (self.fact[-1]  * i) % mod )
            self.inv .append( (-self.inv[mod%i] * (mod//i) ) % mod )
            self.factinv.append( (self.factinv[-1] * self.inv[-1]) % mod )

    def nCr(self, n, r) :
        if ( r < 0 ) or ( n < r ) : return 0
        r = min(r, n-r)
        return self.fact[n]*self.factinv[r]*self.factinv[n-r] % self.mod

    def nPr(self, n, r) :
        if ( r < 0 ) or ( n < r ) : return 0
        return self.fact[n]*self.factinv[n-r] % self.mod


n, k = map(int, input().split())

mod = 10**9+7
comb = Combination(2*10**5+100)
ans = 0
for m in range(min(n+1,k+1)) :
    ans = ans%mod + (comb.nCr(n,m) * comb.nCr(n-1, n-m-1))%mod
print(ans%mod)


Measured memory_bytes: 35928
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
//#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
//#include <array>
#include <valarray>
#include <stdio.h>
//#include <random>
//#include <windows.h>
//#pragma comment(lib, "winmm.lib")
#include <algorithm>

using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

long long  int nCm(long long int n, long long int m) {
	if (m == 1) {
		return n;
	}
	else {
		return n*nCm(n - 1, m - 1) / m;
	}
}

long long int npm(long long int n,long long int m) {
	if (m == 1) {
		return n;
	}
	else 
		if (m == 0) {
			return 1;
		}else {
		return n*npm(n, m - 1);
	}
}

 int main() {
	 string s,l;
	 cin >> s;
	 l = "0123456789012";
	 for (int i = 11; i >= 4; --i) {
		 l[i + 1] = s[i];
	 }
	 l[4] = ' ';
	 for (int i = 3; i >= 0; --i) {
		 l[i] = s[i];
	 }
	 cout << l << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i];

  Int ans=0,t=1;
  for(Int a:as){
    Int num=(a-1)/t;
    ans+=num;
    if(t==1) a=1;
    else if(num) a=t-1;
    chmax(t,a+1);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
  long double a,b,c,d,e;
  
  cin >> a >> b >> c >> d >> e;
  
  if(a == 0){
    cout << 1 << endl;   
  }else if(b == 0){
    cout << 2 << endl;
  }else if(c == 0){
    cout << 3 << endl;
  }else if(d == 0){
    cout << 4 << endl;
  }else if(e == 0){
    cout << 5 << endl;
  }
  

}


Measured memory_bytes: 3692
a=[chr(i) for i in range(97,97+26)]
n=int(input())
c=26
count=1
while 1:
  if n<=c:
    nn=(n-1)%c
    break
  else:
    n-=c
    c*=26
    count+=1
aa=[]
while count>0:
  aa.append(int(nn))
  nn=int(nn/26)
  count-=1
aa=aa[::-1]
ans=[]
cc=26
for i in aa:
  ans.append(a[int(i%cc)])
  i/=26
print("".join(ans))

Measured memory_bytes: 9220
cnv s =
  map (\ss -> length $ filter (== ss) s) s

ans n s =
  let c = cnv s
  in
    if c == s
    then (n,s)
    else ans (n+1) c

ans' ([0]:_) = []
ans' ([n]:s:r) =
  (ans 0 s):(ans' r)

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Int]]
      o = ans' i
  mapM_ putStrLn $ map (\(n,s) -> (show n) ++ "\n" ++ (unwords $ map show s) ) o

Measured memory_bytes: 4176
/**
  * @brief atcoder
  * @author yao
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#define ft first
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#   define NDEBUG
#endif //DBG
#include <cassert>

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

#define N 262144

int a[N];

int main()
{
    int n, x = 0;
    scanf("%d", &n);
    for(int i=0;i<n;++i)scanf("%d", &a[i]), x^=a[i];
    for(int i=0;i<n;++i)printf(" %d"+!i, a[i]^x);
    printf("\n");
    return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define watch(x) cout <<(#x)<<" is "<<(x)<<endl
#define debug cout <<"hi"<<endl
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
ll modpow(ll b, ll i){
  ll s=1;
  while(i){
    if(i%2) s=(s*b)%MOD;
    b=(b*b)%MOD; i/=2;
  }
  return s;
}
int main(){
  int n,a,b; cin >>n >>a >>b;
  ll fa=1,ga=1,fb=1,gb=1;
  for(int i=0; i<a; i++){
    fa=(fa*(n-i))%MOD; ga=(ga*(a-i))%MOD;
  }
  for(int i=0; i<b; i++){
    fb=(fb*(n-i))%MOD; gb=(gb*(b-i))%MOD;
  }
  cout <<(((modpow(2,n)-fa*modpow(ga,MOD-2)-fb*modpow(gb,MOD-2)-1)%MOD)+MOD)%MOD;
return 0;}

Measured memory_bytes: 256
x,y = map(int,input().split())

res = 0
if x == 1:
    res += 300000
elif x == 2:
    res += 200000
elif x == 3:
    res += 100000
    
if y == 1:
    res += 300000
elif y == 2:
    res += 200000
elif y == 3:
    res += 100000
    
if x == 1 and y == 1:
    res += 400000
    
print(res)

Measured memory_bytes: 38460
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <set>
using namespace std;


int main(int argc, char *args[]) {
	int A[100];
	int N;
	int max = 0;
	int min = 10000000000;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		if (A[i] > max)max = A[i];
	}
	for (int i = 0; i < N; i++) {
		if (A[i] < min)min = A[i];
	}
	cout << max - min << endl;
}


Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int w = sc.nextInt();
        if (s>w){
            System.out.println("safe");
        } else {
            System.out.println("unsafe");
        }
    }
}


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

int main() {
int N,x;
  cin >> N;
  x = N % 10;
  
  if(x==2||x==4||x==5||x==7||x==9){
  cout <<"hon"<<endl;
  }
  
  else if(x==0||x==1||x==6||x==8){
  cout <<"pon"<<endl;
  }
  
  else{
  cout <<"bon"<<endl;
  }
}

Measured memory_bytes: 3600
N = int(input())
a = list(map(int, input().split()))
h = list(map(int, input().split()))

mint = 1000000
j = 0

for i in range(N):
    if mint > abs(a[1]-(a[0] - h[i] * 0.006)):
        mint = abs(a[1]-(a[0] - h[i] * 0.006))
        j = i + 1

print(j)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <bitset>
#include <tuple>
#include <stack>

using namespace std;
int main(){
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    vector<int> x(N), y(M);
    int x_max = X;
    int y_min = Y;
    for(int i=0; i<N; i++){
        cin >> x[i];
        x_max = max(x_max, x[i]);
    }
    for(int i=0; i<M; i++){
        cin >> y[i];
        y_min = min(y_min, y[i]);
    }
    if(x_max < y_min) cout << "No War" << endl;
    else cout << "War" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<string.h>
#include<queue>
#include<math.h>
#include<set>
#include<unordered_set>
#include<limits.h>
using namespace std;

typedef long long ll;

const int INF = 1e9;


int main(){
//    freopen("/Users/shitian/Desktop/gcj/gcj/fighting_the_zombies.txt","r",stdin);
//    freopen("/Users/shitian/Desktop/gcj/gcj/fighting_the_zombies_out.txt", "w", stdout);
//    int tcase;
//    cin>>tcase;
//    for(int tt=1;tt<=tcase;tt++){
//        cout<<"Case #"<<tt<<": ";
//        /*
//         
//         */
//        int n,m,k;//n towns, m roads, k families
//        cin>>n>>m>>k;
//        vector<vector<int> >vec(n,vector<int>(n,INF));
//        for(int i=0;i<n;i++){
//            int a,b,g;
//            cin>>a>>b>>g;
//            vec[a-1][b-1]=min(vec[a-1][b-1],g);
//            vec[b-1][a-1]=min(vec[b-1][a-1],g);
//        }
//        for(int k=0;k<n;k++){
//            for(int i=0;i<n;i++){
//                for(int j=0;j<n;j++){
//                    vec[i][j]=min(vec[i][j],vec[i][k]+vec[k][j]);
//                }
//            }
//        }
//        vector<pair<int,int> >sd(k);
//        for(int i=0;i<n;i++){
//            cin>>sd[i].first>>sd[i].second;
//        }
//        /*
//         subproblem:            sd[i:]
//                                dp[i]: min_cost delivered i
//         guess:                 before deliver i, load i+1 or not
//         
//         recurse:               dp[i][j] =
//         topological order:
//         answer:
//         */
//    }
    int n;
    cin>>n;
    ll ans=1;
    vector<bool>prime(1003,true);
    for(int i=2;i<=n;i++){
        if(prime[i]){
            for(int j=i*2;j<=n;j+=i){
                prime[j]=false;
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(prime[i]){
            int co=0;
            for(int j=2;j<=n;j++){
                int tem=j;
                while(tem>0&&tem%i==0){
                    co+=1;
                    tem/=i;
                }
            }
            ans*=(co+1);
            ans=ans%(ll)(1e9+7);
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

const int XN=4e5+11,P=998244353;

void M(int &x) {
    ((x>=P) && (x-=P)) || ((x<0) && (x+=P));
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    //freopen("input","r",stdin);
    static char x[XN];
    int n;std::cin>>n>>(x+1);
    auto IsValid=[&](int i)->bool {
        return 2*n%i==0 && (2*n/i)%2==1;
    };
    static int f[XN],sum[XN];
    for(int i=1;i<=n;++i)
        sum[i]=(sum[i-1]*2LL+x[i]-'0')%P;
    for(int i=1;i<=2*n;++i) {
        if(IsValid(i)) {
            assert(i%2==0);
            f[i]=sum[i/2];
            bool tak=1;
            if(i!=2*n) {
                assert(i<=n);
                std::string s(x+1,x+1+i/2);
                while(s.length()!=n) {
                    s+=s.substr(s.length()-i/2,i/2);
                    for(int j=s.length()-i/2;j<s.length();++j)
                        s[j]^=1;
                }
                if(s>std::string(x+1,x+1+n))
                    tak=0;
            }
            M(f[i]+=tak);
        }
    }
    for(int i=1;i<=2*n;++i)
        if(IsValid(i))
            for(int j=2;i*j<=2*n;++j)
                if(IsValid(i*j))
                    M(f[i*j]-=f[i]);
    int Ans=0;
    for(int i=1;i<=2*n;++i)
        if(IsValid(i))
            M(Ans+=1LL*i*f[i]%P);
    
    int gs=P-1;
    for(int i=1;i<=2*n;++i)
        M(gs+=f[i]);
    assert(sum[n]==gs);
    std::cout<<Ans<<'\n';
    return 0;
}



Measured memory_bytes: 1888
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 c = sc.nextInt();
        boolean[] b = new boolean[n];
        char[] cc = sc.next().toCharArray();
        for (int i = 0; i < n; i++) {
            b[i] = cc[i] == 'o';
        }
        int[] last = new int[k];
        int[] first = new int[k];

        int pos = n -1;
        int num = k;
        while(pos >= 0) {
            while(pos>=0 && !b[pos]) pos--;
            if(pos < 0) break;
            last[--num] = pos;
            if(num == 0) break;
            pos-=c+1;
        }

        num = 0;
        pos = 0;
        while(pos < n) {
            while(pos<n && !b[pos]) pos++;
            if(pos == n) break;
            first[num++] = pos;
            if(num == k) break;
            pos+=c+1;
        }

        for(int i=0; i<k; i++) {
            if(first[i] == last[i]) System.out.println(first[i]+1);
        }

    }



}

Measured memory_bytes: 44932
#include <cstdio>
#include <cstring>

const int MOD=10007;
int main(){
    int N;
    scanf("%d\n",&N);
    char c;
    int at=0,dp[2][8],now;
    memset(dp[1],0,sizeof(dp[1]));
    dp[1][1]=1;
    for(int i=0;i<N;i++){
        memset(dp[i&1],0,sizeof(dp[i&1]));
        scanf("%c",&c);
        if(c=='J') now=0; else if(c=='O') now=1; else now=2;
        for(int j=0;j<8;j++){
            if(j&(1<<now)){
                for(int k=0;k<8;k++){
                    if(j&k){
                        dp[i&1][j]+=dp[(i-1)&1][k];
                        dp[i&1][j]%=MOD;
                    }
                }
            }
        }
    }
    int sum=0;
    for(int i=0;i<8;i++){
        sum+=dp[(N-1)&1][i];
    }
    sum%=MOD;
    printf("%d\n",sum);
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int N;
  cin >> N;
  VL xs(N), acc(N+1);
  REP(i,N){
	cin >> xs[i];
	acc[i+1] = acc[i] + xs[i];
  }

  LL a1 = 0, s = 0;
  REP(i,N){
	if((N-i)%2==1){
	  if(acc[i+1]+s <= 0){
		LL d = -(acc[i+1]+s)+1;
		a1 += abs(d);
		s += d;
	  }
	}
	else{
	  if(acc[i+1]+s >= 0){
		LL d = -(acc[i+1]+s)-1;
		a1 += abs(d);
		s += d;
	  }
	}
  }
  LL a2 = 0;
  s = 0;
  REP(i,N){
	if((N-i)%2==1){
	  if(acc[i+1]+s >= 0){
		LL d = -(acc[i+1]+s)-1;
		a2 += abs(d);
		s += d;
	  }
	}
	else{
	  if(acc[i+1]+s <= 0){
		LL d = -(acc[i+1]+s)+1;
		a2 += abs(d);
		s += d;
	  }
	}
  }
  cout << min(a1, a2) << endl;

  return 0;
}


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

using namespace std;

const int MAX_N = 200000;
vector<int> v[MAX_N];
int score[MAX_N];

int N, Q;

void dfs(int node, int parent){
    for(auto it=v[node].begin(); it != v[node].end(); it++){
        if(*it == parent) continue;
        score[*it] += score[node];
        dfs(*it, node);
    }
}

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

    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        a--;b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=0; i<N; i++){
        score[i] = 0;
    }

    for(int i=0; i<Q; i++){
        int p, x;
        cin >> p >> x;
        p--;
        score[p] += x;
    }

    dfs(0, 0);

    for(int i=0; i<N; i++){
        cout << score[i] << " ";
    }

    cout << endl;
    
    return 0;
}

Measured memory_bytes: 23424
gets
b = gets.chomp.split(' ').map(&:to_i)
answer = []

while b.length > 0 do
  len = b.length
  (len- 1).downto(0) do |i|
    if b[i] == i + 1
      popped = b.delete_at(i)
      answer.unshift(popped)
      break
    end
  end
  break if len == b.length
end
if b.length > 0
  puts -1
else
  answer.each { |i| puts i }
end

Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long LL;
LL i,j,k,n,m;
LL mod=1000000007;
string s;

int main() {
  cin >> n;
  map<int, int> mpe,mpo;
  std::vector<int> v(n);
  for (i=0;i<n;++i) {
    cin >> v[i];
    if (i%2==0){
      if (mpe.find(v[i]) != mpe.end()) {
        mpe[v[i]] +=1;
      } else {
        mpe[v[i]] =1;
      }
    } else {
      if (mpo.find(v[i]) != mpo.end()) {
        mpo[v[i]] +=1;
      } else {
        mpo[v[i]] =1;
      }
    }
  }
  vector<pair<int, int>> ve,vo;
  for (auto const& elee: mpe) {
    ve.push_back(make_pair(elee.first,elee.second));
  }
  for (auto const& eleo: mpo) {
    vo.push_back(make_pair(eleo.first,eleo.second));
  }
  sort(ve.begin(), ve.end(), [](const pair<int, int>& a,const pair<int, int>& b){return a.second > b.second;});
  sort(vo.begin(), vo.end(), [](const pair<int, int>& a,const pair<int, int>& b){return a.second > b.second;});
  int e,o;
  if (ve[0].first!=vo[0].first) {
    e = ve[0].first;
    o = vo[0].first;
  } else {
    if (ve.size() == 1 && vo.size() == 1){
      e = 0;
    } else if(ve.size() == 1 && vo.size() > 1) {
      e = ve[0].first;
      o = vo[1].first;
    }else if(ve.size() >1 && vo.size() == 1) {
      e = ve[1].first;
      o = vo[0].first;
    } else {
      if (ve[0].second + vo[1].second > ve[1].second + vo[0].second) {
        e = ve[0].first;
        o = vo[1].first;
      } else {
        e = ve[1].first;
        o = vo[0].first;
      }
    }
  }
  int cnt =0;
  for (i=0;i<n;++i) {
    if (i%2==0){
      if (v[i] != e) ++cnt;
    } else {
      if (v[i] != o) ++cnt;
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 6520