akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define endl '\n'
typedef long long ll;


const double PI=acos(-1);
typedef complex<double> base;
inline void fft (vector<base> & a, bool invert) {
	int n=(int) a.size();
	for (int i=1, j=0; i<n; ++i) {
		int bit=n>>1;
		for (;j>=bit;bit>>=1)
			j-=bit;
		j+=bit;
		if(i<j)
			swap(a[i],a[j]);
	}
	for (int len=2; len<=n; len<<=1) {
		double ang = 2*PI/len * (invert ? -1 : 1);
		base wlen(cos(ang), sin(ang));
		for (int i=0; i<n; i+=len) {
			base w(1);
			for (int j=0; j<len/2; ++j) {
				base u=a[i+j], v=a[i+j+len/2]*w;
				a[i+j]=u+v;
				a[i+j+len/2]=u-v;
				w*=wlen;
			}
		}
	}
	if (invert)
		for(int i=0;i<n;++i)
			a[i]/=n;
}

// a, b => coefs to multiply,  res => resulting coefs
// a[0], b[0], res[0] = coef x^0
inline void multiply (const vector<int> & a, const vector<int> & b, vector<int> & res) {//change res to ll if needed
	if(a.size() * b.size() <= 256) {
		res.resize(a.size() + b.size()+1, 0);
		for(int i = 0; i < (int)a.size(); i++)
			for(int j = 0; j < (int)b.size(); j++)
				res[i + j] += 1LL * a[i] * b[j];
		while(res.size()>1 && res.back() == 0) res.pop_back();
		return;
	}
	vector<base> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
	size_t n=1;
	while (n<max(a.size(),b.size())) n<<=1;
	n<<=1;
	fa.resize(n),fb.resize(n);
	fft (fa,false);  fft(fb,false);
	for (size_t i=0; i<n; ++i)
		fa[i]*=fb[i];
	fft (fa, true);
	res.resize (n);
	for(size_t i=0; i<n; ++i)
		res[i]=(int)(fa[i].real()>0 ? fa[i].real()+0.5 : fa[i].real()-0.5);
	while(res.size()>1 && res.back() == 0) res.pop_back();
}

//returns a^pw % mod
ll fastPow(ll a, ll pw, ll mod) {
	ll res = 1;
	a %= mod;
	while(pw > 0) {
		if(pw & 1) res = (res*a)%mod;
		a = (a*a)%mod;
		pw >>= 1;
	}
	return res;
}

const int p = 200003;
const int g = 110341;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	/*
	vector<int> facs = {1 , 2 , 11 , 22 , 9091 , 18182 , 100001};
	for(int i = 2; i < p; ++i) {
		bool gen = true;
		for(int power : facs) {
			if(fastPow(i,power,p) == 1) {
				gen = false;
			}
		}
		if(gen) {
			cout << "generator: " << i << endl;
		}
	}
	return 0;
	*/
	int n;
	cin >> n;
	vector<int> arr;
	for(int i = 0; i < n; ++i) {
		int val;
		cin >> val;
		if(val > 0) arr.push_back(val);
	}
	n = arr.size();


	vector<int> order(2*p,0);
	int powG = g;
	for(int i = 1; i < 2*p; ++i) {
		order[i] = powG;
		powG = (powG * g) % p;
	}
	vector<int> inv(p,0);
	for(int i = 1; i < p; ++i) {
		inv[order[i]] = i;
	}
	vector<int> cnts(p,0);
	for(int val : arr) {
		++cnts[inv[val]];
	}
	vector<int> product;
	multiply(cnts,cnts,product);
	int res = 0;
	for(int i = 0; i < product.size(); ++i) {
		res += order[i] * product[i];
	}
	for(int val : arr) {
		res -= (val*val)%p;
	}
	cout << res/2;
}


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

using namespace std;

int main(void){
	int i, n, j, k=0, flag=0;
	int max_num=0, max_id=0;
	vector<long int> a(200000);

	cin >> n;

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

	if (n % 2 == 0){
		for (i = n; i >= 2; i -= 2){
			cout << a[i] << " ";
		}
		for (i = 1; i <= n - 1; i += 2){
			cout << a[i] << " ";
		}

	}
	else if (n % 2 == 1){
		for (i = n; i >= 1; i -= 2){
			cout << a[i] << " ";
		}
		for (i = 2; i <= n - 1; i += 2){
			cout << a[i] << " ";
		}
	}


	return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
  int a,b,c;
  int cnt = 0;
  cin >> a >> b >> c;
  for(int i = a;i<= b;i++){
    if (c % i == 0){
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 3084
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

typedef long long ll;

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

  ll N, M;
  cin >> N >> M;

  // N > 2 && M > 2
  cout << abs((M - 2) * (N - 2)) << endl;

  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
int n,k,ans,p;
int map[12][6]={
    {4,2,0,9,7},
    {1,10,8,6,4},
    {9,7,5,3,1},
    {6,4,2,0,9},
    {3,1,10,8,6},
    {0,9,7,5,3},
    {8,6,4,2,0},
    {5,3,1,10,8},
    {2,0,9,7,5},
    {10,8,6,4,2},
    {7,5,3,1,10}};
int main()
{
    scanf("%d%d",&n,&k);n-=2;
    p=n%11;n/=11;
    ans=n*5;
    for(int i=0;i<p;i++)
     for(int j=0;j<5;j++)
      if(map[i][j]==k)ans++;
    printf("%d\n",ans);
    return 0;//OK.
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1000000007;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N,A,B,C,D;
    cin >> N >> A >> B >> C >> D;
    rep(m,N){
        if(C*(N-1-m)-D*m <= B-A && B-A <= D*(N-1-m) - C*m){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    /*if(B < A - D*(N-1) || A + D*(N-1) < B){
        cout << "NO" << endl;
        return 0;
    }
    if(A-C-D*(N-2) < B && B < A+C-D*(N-2)){
        cout << "NO" << endl;
        return 0;
    }else if(A-C+D*(N-2) < B && B < A+C+D*(N-2)){
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;*/

}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=2e5+5;
int n,k,a[N][7],c[32][7];
pii ST[32][N*4];

void update(int mask,int id,int l,int r,int pos,int val)
{
    if(pos>r||pos<l) return ;
    if(l==r)
    {
        ST[mask][id].fi=ST[mask][id].se=val;
        return ;
    }
    int mid=(l+r)/2;
    update(mask,id*2,l,mid,pos,val);
    update(mask,id*2+1,mid+1,r,pos,val);
    ST[mask][id].fi=max(ST[mask][id*2].fi,ST[mask][id*2+1].fi);
    ST[mask][id].se=min(ST[mask][id*2].se,ST[mask][id*2+1].se);
}

pii get(int mask,int id,int l,int r,int u,int v)
{
    if(u>r||v<l) return mp(-1e9,1e9);
    if(u<=l&&r<=v) return ST[mask][id];
    int mid=(l+r)/2;
    pii lson=get(mask,id*2,l,mid,u,v);
    pii rson=get(mask,id*2+1,mid+1,r,u,v);
    return mp(max(lson.fi,rson.fi),min(lson.se,rson.se));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    k=2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++) cin>>a[i][j];
    }
    for(int mask=0;mask<(1<<k);mask++)
    {
        for(int i=1;i<=k;i++)
        {
            c[mask][i]=(mask>>(i-1)&1);
            if(!c[mask][i]) c[mask][i]--;
        }
        for(int i=1;i<=n;i++)
        {
            int val=0;
            for(int j=1;j<=k;j++) val+=c[mask][j]*a[i][j];
            update(mask,1,1,n,i,val);
        }
    }
    int q;
    q=1;
    while(q--)
    {
        int type=2;
        if(type==2)
        {
            int l,r;
            l=1,r=n;
            int res=0;
            for(int mask=0;mask<(1<<k);mask++)
            {
                pii cur=get(mask,1,1,n,l,r);
                res=max(res,cur.fi-cur.se);
            }
            cout<<res<<'\n';
        }
    }
}


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

int main() {
	int a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	int ans = 1001001001;
	if(x > y) {
		swap(x, y); // x <= y
		swap(a, b);
	}
	int t = a * x + b * y;
	ans = min(ans, t);
	t = 2 * c * x + b * (y-x);
	ans = min(ans, t);
	t = 2 * c * y;
	ans = min(ans, t);
	cout << ans << endl;
	
	return 0;
}

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

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

	int count;
	for (int i = 0; i < 3; i++) {
		if (S.at(i) == 'o')
			count++;
	}

	cout << 700 + 100 * count << endl;
}

Measured memory_bytes: 256
bingo = []
for i in range(3):
    a, b, c = map(int,input().split())
    bingo.append(a)
    bingo.append(b)
    bingo.append(c)
N = int(input())
b= []
for i in range(N):
    b_ele = int(input())
    b.append(b_ele)
    if b_ele in bingo:
        ind = bingo.index(b_ele)
        bingo[ind] = None
ans = "No"

if (not bingo[0] and bingo[0] == bingo[1] and bingo[0] == bingo[2]):
    ans = "Yes"
elif (not bingo[3] and bingo[3] == bingo[4] and bingo[3] == bingo[5]):
    ans = "Yes"
elif (not bingo[6] and bingo[6] == bingo[7] and bingo[6] == bingo[8]):
    ans = "Yes"
elif (not bingo[0] and bingo[0] == bingo[3] and bingo[0] == bingo[6]):
    ans = "Yes"
elif (not bingo[1] and bingo[1] == bingo[4] and bingo[1] == bingo[7]):
    ans = "Yes"
elif (not bingo[2] and bingo[2] == bingo[5] and bingo[2] == bingo[8]):
    ans = "Yes"
elif (not bingo[0] and bingo[0] == bingo[4] and bingo[0] == bingo[8]):
    ans = "Yes"
elif (not bingo[2] and bingo[2] == bingo[4] and bingo[2] == bingo[6]):
    ans = "Yes"

print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{	ios_base::sync_with_stdio(0);
	cin.tie(0);
 	int n;cin>>n;
 	int arr[n];
 	for(int i=0;i<n;++i)cin>>arr[i];
 	int res[n];res[0]=0;
 	res[1]=abs(arr[0]-arr[1]);
 	for(int i=2;i<n;++i)
    {	res[i]=abs(arr[i]-arr[i-1])+res[i-1];
     	res[i]=min(res[i],abs(arr[i]-arr[i-2])+res[i-2]);
    }
 	cout<<res[n-1]<<"\n";
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
string s;
cin >>s;
sort(s.begin(),s.end());
char p=s[0];
int cnt=1;
if(s.size()==1){
  cout << "No"<<endl;
  return 0;
}
for(int i=1;i<s.size();i++){
  if(p==s[i]) cnt++;
  else{
    if(cnt%2==1){
      cout <<"No"<<endl;
      return 0;
    }
    cnt=1;
    if(i==s.size()-1) {
      cout <<"No"<<endl;
      return 0;
    }
    p=s[i];
  }
}
cout <<"Yes"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define REP(i,a,n) for(int i = a ; i < n ; i++)
#define rep(i,n) REP(i,0,n)

class State{
public:
  int x,y,cost;

  State(){}
  State(int _x,int _y,int _cost){
    x = _x;
    y = _y;
    cost = _cost;
  }
};

typedef long long ll;

int n,m;
int sx,sy;
bool t[1000][1000];
bool closed[1000][1000];
int dx[] = {0,1,1,0,-1,-1};
int dy[] = {1,1,0,-1,-1,0};

void solve(){
  queue<State> open;
  memset(closed,0,sizeof(closed));
  open.push(State(sx,sy,0));

  int ans = 0;

  while(!open.empty()){
    State st = open.front(); open.pop();
    if(closed[st.x][st.y] || st.cost>n || t[st.y][st.x]) continue;
    closed[st.x][st.y] = true;

    ans++;

    rep(i,6){
      int nx = st.x + dx[i];
      int ny = st.y + dy[i];
      open.push(State(nx,ny,st.cost+1));
    }
  }

  cout<<ans<<endl;
}

int main(){
  while(cin>>n>>m,n||m){
    memset(t,0,sizeof(t));
    rep(i,m){
      int x,y;
      cin>>x>>y;
      x += 300;
      y += 300;
      t[y][x] = true;
    }

    cin>>sx>>sy;
    sx += 300;
    sy += 300;

    solve();
  }
}

Measured memory_bytes: 2888
N, M, X = [int(nmx) for nmx in input().split()]
A = [int(a) for a in input().split()]
A.append(X)
A.sort()
idx_X = A.index(X)
if len(A)//2 < idx_X+1:
  ans = len(A)- (idx_X+1)
else:
  ans = (idx_X+1) - 1
print(ans)

Measured memory_bytes: 3060
a=gets.chomp.to_i
b=gets.chomp.split.map(&:to_i)
sum=b.inject(&:+)
av=(sum.to_f/a.to_f).round
c=0
sum2=0
b.each do |x|
  sum2+=(av-x)*(av-x)
end
puts sum2

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

typedef long long ll;

void print()
{
  std::cout << std::endl;
}

template<class T>
void print(T param)
{
  std::cout << param << std::endl;
  return;
}

int main()
{
  ll N;
  std::cin >> N;
  N %= 10;

  std::string ans;
  if (N == 2 || N == 4 || N == 5 || N == 7 || N == 9) {
    ans = "hon";
  }
  if (N == 0 || N == 1 || N == 6 || N == 8) {
    ans = "pon";
  }
  if (N == 3) {
    ans = "bon";
  }

  print(ans);
  return 0;
}


Measured memory_bytes: 3608
#include<iostream>
#include<string>
using namespace std;
int main(){
        string s;
        cin>>s;
        int x=0;
        for(int i=0;i<s.size()-1;i++){
                for(int j=i+1;j<s.size();j++){
                        if(s[i]==s[j]){
                                x=1;
                                break;
                        }
                }
        }
        if(x==0){
                cout<<"yes";
        }
       else{
               cout<<"no";
       }
}

Measured memory_bytes: 256
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

n, a, b = map(int, input().split())

ans = n//(a+b)*a + min(n%(a+b), a)
print(ans)

Measured memory_bytes: 27256
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <tuple>

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

void solve(){
  int n,k;
  string s;
  cin >> n >> k >> s;
  k -= 1;
  if(s[k]=='A') s[k] = 'a'; 
  else if(s[k]=='B') s[k] = 'b';
  else s[k] = 'c';
  cout << s << endl;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using namespace std;

int main() {
    fastIO;
    int a, b;
    cin >> a >> b;
    if (a == 2 || b == 2)
        cout << "No";
    else
        cout << "Yes";
}

Measured memory_bytes: 3652
import numpy as np
def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
n=int(input())
pri1=seachPrimeNum(n)
ma=pri1.index(max(pri1))
pri=seachPrimeNum(n*2)
if pri[ma]==n:
    print(n)
else:
    print(pri[ma+1])

Measured memory_bytes: 21196
#include<iostream>

using namespace std;

#define N 1000

int main() {

	int n;
	cin >> n;

	int ans = 0;

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

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

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

	cout << ans << endl;




	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define INF 1000000000000000000
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;

int main() {
    ll q, h, s, d;
    cin >> q >> h >> s >> d;
    ll n;
    cin >> n;

    cout << (n / 2) * min(8 * q, min(4 * h, min(2 * s, d))) +
                (n % 2) * min(4 * q, min(2 * h, s))
         << endl;
}

Measured memory_bytes: 3600
N=int(input())
num=9
ans=0
ans_fin=0

for i in range(9):
    if N%num==0:
        ans=N/num
        if ans>=10:
            break;
        else :
            ans_fin+=1
            break;
    else :
        num-=1
if ans_fin==1:
    print('Yes')
else :
    print('No')

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
const int MAX = 200010;
int town[MAX],flag[MAX],cnt=0,cnt2=0,ans[MAX];
int main() {
	int N;
	long long K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++)cin >> town[i];
	int tis = 1;
	while (flag[tis] != 2) {
		if (flag[tis] == 0)++cnt;
		if (flag[tis] == 1) {
			ans[++cnt2] = tis;
		}
		flag[tis]++;
		tis = town[tis];
	}
	if (K > cnt - cnt2) {
		int a = (K - cnt + cnt2) % cnt2;
		cout << ans[a + 1];
	}
	else {
		int k = K,tis=1;
		while (k--) {
			tis = town[tis];
		}
		cout << tis;
	}
	return 0;
}

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

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
  
    int n;
    cin >> n;
    unordered_set<string> seen;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        seen.insert(s);
    }
    cout << seen.size() << endl;
    return 0;
}


Measured memory_bytes: 17700
def gcd(a,b):
    if b == 0:
        return abs(a)
    else:
        return gcd(b, a%b)

N,K = map(int, input().split())
A = sorted(list(map(int,input().split())))

Im = 'IMPOSSIBLE'
Po = 'POSSIBLE'

if max(A) < K:
    print(Im)
else:
    for i in range(N):
        if i == 0:
            tmp = gcd(A[i], 0)
        else:
            tmp = gcd(A[i],tmp)
        if tmp == 1:
            break
    if K%tmp == 0:
        print(Po)
    else:
        print(Im)


Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,ans=0;cin>>n;
  for(ll i=1;i<=n;++i) {
    if(i%3!=0&&i%5!=0) ans+=i;
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
const int RANDOM1 = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return hash<int>{}(x ^ RANDOM1); }
};
#define ll long long
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define deb(x) cout<<#x<<" : "<<x<<"\n";
#define debug(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\n";
#define ff first
#define ss second
#define ub upper_bound
#define lb lower_bound
#define all(a) (a).begin(),(a).end()
#define bs binary_search
#define sz size()
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define clr fflush(stdout);
//#define clr cout.flush();
#define N 100001
#define fpr(i,a,b) for(int i=a;i<b;i++)
#define fdr(i,a,b) for(int i=a;i>b;i--)
#define repp(i,a,b,d) for(int i=a;i<b;i+=d)
#define repd(i,a,b,d) for(int i=a;i>b;i-=d)
#define LLMIN LLONG_MIN
#define LLMAX LLONG_MAX
#define AKASH_PATEL ios_base::sync_with_stdio(false);
#define SVNIT_SURAT cin.tie(NULL);cout.tie(NULL);
#define mset(x,a) memset(x,a,sizeof(x));
#define nl cout<<'\n';
#define print(c) cout<<c<<'\n';
#define setp(n) cout << fixed << setprecision(n)
#define take_arr(a,n) fpr(i,0,n) cin>>a[i];
#define print_arr(a,n) for(int i=0;i<n;i++) {cout<<a[i]<<" ";} cout<<'\n';
#define take_mat(mat,n,m) fpr(i,0,n) fpr(j,0,m) cin>>mat[i][j];
#define set_mat(mat,n,m,k) fpr(i,0,n) fpr(j,0,m) mat[i][j]=k;
#define print_mat(dist,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<dist[i][j]<<" ";}cout<<'\n';}
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
int n;
vector <string> res;
void fun(int id,string s)
{
    if(id==n)
    {
        res.pb(s);
        return;
    }
    set<char> tmp;
    for(auto it:s)
    {
        tmp.insert(it);
    }
    int len=tmp.sz;
    fpr(i,0,len+1)
    {
        char c1='a'+i;
        string s2=s;
        s2+=c1;
        fun(id+1,s2);
    }
}
int main()
{
    AKASH_PATEL;
    SVNIT_SURAT;
    cin>>n;
    string s="a";
    fun(1,s);
    sort(all(res));
    for(auto it:res)
    {
        print(it)
    }
    return 0;
}





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

int main() {
  int N, M;
  string str;

  cin >> str;

  bool c = false, f = false;
  for (int i = 0; i < str.size(); i++) {
    if (!c) {
      if (str[i] == 'C') c = true;
    } else {
      if (str[i] == 'F') f = true;
    }
  }

  if (f) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
import sys

def digits_sum(x):
    return sum(list(map(int, str(x))))

def solve(n):
    ans = sys.maxsize
    for a in range(1, n):
        b = n - a
        ans = min(ans, digits_sum(a) + digits_sum(b))

    return ans

if __name__ == '__main__':
    n = int(input())
    print(solve(n))


Measured memory_bytes: 3060
import java.util.Scanner;
public class Main {
public static void main(String[] args) {// ?¨??????\???????????????????????????????????????
	Scanner sc= new Scanner(System.in);
	int w = sc.nextInt();
	int n = sc.nextInt();
	int [] values = new int[w];
	for(int i= 0; i < values.length; i++) {
		values[i] = i + 1;
}
	for(int i= 0; i< n; i++) {
		String str= sc.next();
		String[] ab = str.split(",");
		int a = Integer.parseInt(ab[0]) -1;
		int b = Integer.parseInt(ab[1]) -1;
		int v =values[a];
		values[a] = values[b];
		values[b] = v;// a??¨b????????£???values??????????????????
}
	for(int j = 0;j<values.length; j++) 
	System.out.println(values[j]);
// values??????????????????
}
}

Measured memory_bytes: 26472
#include<stdio.h>
#include<stdlib.h>

int main()
{
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if(a < b && b < c )
    {
    	printf("Yes\n");
	}
    else
    {
    	printf("No\n");
	}
	return 0;
} 


Measured memory_bytes: 2084
#include "bits/stdc++.h"

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int cost[200][200];
int tim[200][200];


int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0)break;
        rep(i,200)rep(j,200){
            cost[i][j]=999999999;
            tim[i][j]=999999999;
        }
        rep(i,n){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            a--,b--;
            cost[a][b]=cost[b][a]=c;
            tim[a][b]=tim[b][a]=d;
        }
        
        rep(k,m){
            rep(i,m){
                rep(j,m){
                    cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
                    tim[i][j]=min(tim[i][j],tim[i][k]+tim[k][j]);
                }
            }
        }
        int x;
        cin>>x;
        rep(i,x){
            int a,b,c;
            cin>>a>>b>>c;
            a--,b--;
            if(c==0){
                cout<<cost[a][b]<<endl;
            }else cout<<tim[a][b]<<endl;
        }
    }
}

Measured memory_bytes: 1468
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using namespace std;

int main(){
  int H,W;
  while(true){
    cin >> W >> H;
    if(!H)break;
    vector<vector<char>> mp(H,vector<char>(W));
    vector<vector<int>> c(H,vector<int>(W,0));
      REP(i,H)
      REP(j,W)cin >> mp[i][j];
      int Bct=0;int Wct =0;
    REP(i,H){
      REP(j,W){
	if(!c[i][j] && mp[i][j] == '.'){
	  queue<pair<int,int>> que;
	  que.push(make_pair(i,j));
	  int ct = 1;//????§???§?¨???????
	  c[i][j] = 1;
	  bool isBlack = false;
	  bool isWhite = false;
	  while(que.size()){
	    int x = que.front().first;
	    int y = que.front().second;
	    que.pop();
	    REP(k,4){
	      int nx = x + dx[k];
	      int ny = y + dy[k];
	      if(nx<H&&nx>=0&&ny<W&&ny>=0){
		if(mp[nx][ny] == 'B')isBlack = true;
		else if(mp[nx][ny] == 'W')isWhite = true;
		else if(c[nx][ny] == 0){
		  ct++;
		  que.push(make_pair(nx,ny));
		}
		c[nx][ny] = 1;
	      }
	    }
	  }
	  if(isBlack&&!isWhite)Bct += ct;
	  else if(isWhite&&!isBlack)Wct += ct;
	}
      }
    }
    cout << Bct << " " << Wct << endl;

  }
  return 0;
}

Measured memory_bytes: 3156
// Doubly_Linked_List.cs

using System;
using System.Linq;
using System.Collections.Generic;

class Doubly_Linked_List {
	public static void Main(string[] args) {


		int n = int.Parse(Console.ReadLine());

		var<string> list = new LinkedList<string>();

		for(int i = 0; i < n; i++) {
			
			string[] str = Console.ReadLine().Split(' ');

			if(str[0] == "insert") {
				list.AddFirst(str[1]);
			} else if(str[0] == "delete") {
				list.Remove(str[1]);
			} else if(str[0] == "deleteLast") {
				list.RemoveLast();
			} else if(str[0] == "deleteFirst") {
				list.RemoveFirst();
			}

		}
		int c = 0;
		foreach(string s in list) {
			if(c != list.Count - 1)
			Console.Write(s + " ");
			else
			Console.WriteLine(s);
			c++;
		}
	}

}

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


int main() {
  string S, S_a, S_b;
  cin >> S;

  int half_N = S.size()/2;

  S_a = S.substr(0, half_N);
  S_b = S.substr(half_N);

  int i, ret=0;
  for(i=0;i<half_N;i++){
    if(S_a.at(i) != S_b.at(S_b.size()-1-i)) ret++;
  }

  cout << ret << endl;
}


Measured memory_bytes: 256
N = int(input())
hoge = 0
M = 1
while True:
    hoge += M
    if hoge == N:
        print("Yes")
        break
    if hoge > N:
        print("No")
        exit()
    M += 1
print(M+1)

ans = []
hoge = 1
for i in range(M):
    ans.append([])
    for j in range(i+1):
        ans[-1].append(hoge)
        hoge += 1
for i in range(M):
    print(M,end = " ")
    for j in range(i+1):
        print(ans[i][j],end = " ")
    for j in range(i+1,M):
        print(ans[j][i],end=" ")
    print()
print(M,end=" ")
for i in range(M):
    print(ans[i][i],end=" ")
print()

Measured memory_bytes: 8456
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
void solve(long long n, long long m, std::vector<long long> a) {
    vector<vector<int>> open_at(m + 1), close_at(m + 1);
    for(int i = 0; i < n - 1; i++) {
        open_at[a[i] % m + 1].push_back(i + 1);
    }
    vector<ll> cost(n);
    for(int i = 1; i < n; i++) {
        close_at[a[i]].push_back(i);
        cost[i] = (a[i] - a[i - 1] + m) % m;
    }
    ll running_cost = 0;
    int active = 0;
    for(int i = 1; i < n; i++) {
        running_cost += min(cost[i], a[i]);
        active += a[i] < a[i - 1];
    }
    ll ans = running_cost;
    for(int x = 2; x <= m; x++) {
        for(int i : close_at[x - 1]) {
            running_cost--;
            running_cost += cost[i];
            active--;
        }
        running_cost -= active;
        ans = min(ans, running_cost);
        active += open_at[x].size();
    }
    cout << ans << endl;
}
int main() {
    long long n;
    scanf("%lld",&n);
    long long m;
    scanf("%lld",&m);
    std::vector<long long> a(n);
    for(int i = 0 ; i < n ; i++){
        scanf("%lld",&a[i]);
    }
    solve(n, m, std::move(a));
    return 0;
}


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

int main(){
  int N,i,j,pt=0;
  string X;
  cin >> N;
  vector<pair<string,int>> pl(N);

  for(i=0;i<N;i++){
    cin >> pl.at(i).first >> pl.at(i).second;
  }
  cin >> X;
  if(N==1)
  cout << pt << endl;
  else{
    for(i=0;i<N;i++){
      if(pl.at(i).first==X){
        for(j=i+1;j<N;j++)
        pt += pl.at(j).second;
      }
    }
    cout << pt << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  // ios::sync_with_stdio(0);
  int MAX_VALUE = 100000;
  int k, x;
  int max, min;
  
  cin >> k >> x;
  min = x - k + 1;
  max = x + k - 1;
  
  for(int ans = min; ans <= max; ans++) {
    cout << ans;
    if(max - ans) {
      cout << " ";
    } else {
      cout << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

#include <atcoder/lazysegtree>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;

struct S{
    mint a,b;
};

struct F{
    mint a,b;
};

S op(S x,S y){
    x.a += y.a;
    x.b += y.b;
    return x;
}

S e(){ return S{0,0};}

S mapping(F l,S r){
    return S{r.a*l.a+r.b*l.b,r.b};
}

F composition(F l,F r){
    l.b = l.a*r.b + l.b;
    l.a *= r.a;
    return l;
}

F id(){ return F{1,0};}

int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    vector<S> a(n);
    rep(i,n){
        int x;
        scanf("%d",&x);
        a[i].a = x;
        a[i].b = 1;
    }

    lazy_segtree<S,op,e,F,mapping,composition,id> seg(a);

    while(q--){
        int t;
        cin >> t;
        if(t==0){
            int l,r,c,d;
            scanf("%d%d%d%d",&l,&r,&c,&d);
            seg.apply(l,r,F{c,d});
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            cout << seg.prod(l,r).a.val() << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 19388
N,X = map(int, input().split())
burger = [(1,0)]
prev = (1,0)
for i in range(N):
    burger.append((2*prev[0]+1, 2*prev[1]+2))
    prev = burger[-1]

lev = N
cur = X-1
ps = 0
for i in range(N+1):
    if lev == 0:
        ps += 1
        break

    if cur == 0:
        break
    elif cur == sum(burger[lev-1])+1:
        ps += burger[lev-1][0]+1
        break
    elif cur == sum(burger[lev])-1:
        ps += 2*burger[lev-1][0] + 1
        break

    if cur < sum(burger[lev])/2:
        cur -= 1
        lev -= 1
    else:
        ps += burger[lev-1][0] + 1
        cur -= sum(burger[lev-1]) + 2
        lev -= 1
print(ps)

Measured memory_bytes: 9244
#include <stdio.h>

int main() {
	int N;
	scanf("%d", &N);
	switch (N % 10) {
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:
			printf("hon\n");
			break;
		case 0:
		case 1:
		case 6:
		case 8:
			printf("pon\n");
			break;
		case 3:
			printf("bon\n");
			break;
	}
}


Measured memory_bytes: 1656
import numpy as np

n = int(input())

v_list = np.array(list(map(int,input().split())))
c_list = np.array(list(map(int,input().split())))
e_list = list(v_list - c_list)

ans = 0

for i in range(n):
    if e_list[i] > 0:
        ans += e_list[i]

print(ans)


Measured memory_bytes: 17204
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;

using namespace std;

struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


const int NM = 100000;


void solve() {
    ll a, b;
    cin >> a >> b;

    int sum = (a*(a-1))/2 + (b*(b-1) / 2);
    cout << sum;
}



int main() {
    solve();
    return 0;
}







Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(int argc, char *argv[])
{
  for(;;) {
    int n;
    cin >> n;
    if(n==0) break;
    vector<char> ops;
    vector<int> vs;
    ops.push_back('+');
    vs.push_back(0);
    auto update = [&ops,&vs](const int v) {
      switch(ops.back()) {
      case '+': { (vs.back()) += v; break; }
      case '*': { (vs.back()) *= v; break; }
      default : { throw string("Something Wrong in default!"); }
      }
    };
    auto pops = [&ops,&vs,&update](const int l){
      while(l < ops.size()) {
        int v = vs.back();
        vs.pop_back();
        ops.pop_back();
        update(v);
      }
    };
    for(int i = 0; i < n; i++) {
      string s;
      cin >> s;
      // cout << "read: " << s << endl;
      pops(s.size());
      char c = s[ops.size()-1];
      // cout << "c = " << c << endl;
      switch(c){
      case '.' : { throw string("Something Wrong!"); }
      case '+' : {
        ops.push_back('+');
        vs.push_back(0);
        break;
      }
      case '*' : {
        ops.push_back('*');
        vs.push_back(1);
        break;
      }
      default : { // '0'--'9'
        update(c - '0');
      }
      }
    }
    pops(1);
    cout << vs[0] << endl;
  }
  return 0;
}



Measured memory_bytes: 3220
#include "bits/stdc++.h"
using namespace std;

long long INF = (1 << 31) - 1;

class LazySegmentTree {
private:
	long long Size;
	vector<long long> Node, Lazy;
	vector<bool> Flag;
public:
	LazySegmentTree(long long N) {
		Size = 1;
		while (Size < N) Size <<= 1;
		Node.assign(Size * 2, INF);
		Lazy.assign(Size * 2, INF);
		Flag.assign(Size * 2, false);
	}
	void Eval(long long K, long long L, long long R) {
		if (Flag[K]) {
			Node[K] = Lazy[K];
			if (R - L > 1) {
				Lazy[K * 2] = Lazy[K];
				Flag[K * 2] = true;
				Lazy[K * 2 + 1] = Lazy[K];
				Flag[K * 2 + 1] = true;
			}
			Lazy[K] = INF;
			Flag[K] = false;
		}
	}
	void Update(long long A, long long B, long long X, long long K, long long L, long long R) {
		Eval(K, L, R);
		if (B <= L || R <= A) return;
		if (A <= L && R <= B) {
			Lazy[K] = X;
			Flag[K] = true;
			Eval(K, L, R);
			return;
		}
		Update(A, B, X, K * 2, L, (L + R) / 2);
		Update(A, B, X, K * 2 + 1, (L + R) / 2, R);
		Node[K] = min(Node[K * 2], Node[K * 2 + 1]);
	}
	void Update(long long A, long long B, long long X) {
		Update(A, B, X, 1, 0, Size);
		return;
	}
	long long Query(long long A, long long B, long long K, long long L, long long R) {
		Eval(K, L, R);
		if (B <= L || R <= A) return INF;
		if (A <= L && R <= B) return Node[K];
		return min(Query(A, B, K * 2, L, (L + R) / 2), Query(A, B, K * 2 + 1, (L + R) / 2, R));
	}
	long long Query(long long A, long long B) {
		return Query(A, B, 1, 0, Size);
	}
};

int main() {
	long long N, Q;
	cin >> N >> Q;
	LazySegmentTree Seg(N);
	for (int i = 0; i < Q; i++) {
		long long Mode;
		cin >> Mode;
		if (Mode == 0) {
			long long A, B, X;
			cin >> A >> B >> X;
			Seg.Update(A, B + 1, X);
		}
		else {
			long long A, B;
			cin >> A >> B;
			cout << Seg.Query(A, B + 1) << endl;
		}
	}
}


Measured memory_bytes: 7064
while True:
    h, w = map(int, input().split())
    if h == 0 and w == 0:
        break
    for i in range(h):    
        for j in range(w):
            if i == 0 or i ==  h - 1 or j == 0 or j == w - 1:   
                print("#", end="")
            else:
                print(".", end="")
        print()
    print()


Measured memory_bytes: 7008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed
#define endl '\n'

const ll MOD = 1e9 + 7;
struct mint {
    ll x;
    mint() : x(0) {}
    mint(ll x) : x((x % MOD + MOD) % MOD) {}
    mint& operator+=(const mint& r) { if ((x += r.x) >= MOD) { x -= MOD; } return *this; }
    mint& operator-=(const mint& r) { if ((x -= r.x) < 0) { x += MOD; } return *this; }
    mint& operator*=(const mint& r) { if ((x *= r.x) > MOD) { x %= MOD; } return *this; }
    mint& operator++() { if ((++x) >= MOD) { x -= MOD; } return *this; }
    mint operator++(int) { mint ret = x; if ((++x) >= MOD) { x-= MOD; } return ret; }
    mint& operator--() { if ((--x) < 0) { x += MOD; } return *this; }
    mint operator--(int) { mint ret = x; if ((--x) < 0) { x += MOD; } return ret; }
    mint operator+(const mint& r) { mint ret; return ret = x + r.x; }
    mint operator-(const mint& r) { mint ret; return ret = x - r.x; }
    mint operator*(const mint& r) { mint ret; return ret = x * r.x; }
    mint operator-() { return mint() - *this; }
    bool operator<(const mint& a) { return x < a.x; }
    bool operator>(const mint& a) { return x > a.x; }
    bool operator<=(const mint& a) { return x <= a.x; }
    bool operator>=(const mint& a) { return x >= a.x; }
    bool operator==(const mint& a) { return x == a.x; }
    bool operator!=(const mint& a) { return x != a.x; }
};
ostream& operator<<(ostream& os, const mint& r) { os << r.x; return os; }
ostream& operator>>(ostream& os, const mint& r) { os >> r.x; return os; }

void solve(istream& cin, ostream& cout) {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  REP(i, n-2) {
    if (s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C') ans++;
  }
  cout << ans << endl;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
}
#endif


Measured memory_bytes: 256
class dice:
    def __init__(self, f):
        assert(len(f) == 6)
        self.face = f
        self.N = [1, 5, 2, 3, 0, 4]
        self.S = [4, 0, 2, 3, 5, 1]
        self.E = [3, 1, 0, 5, 4, 2]
        self.W = [2, 1, 5, 0, 4, 3]

    def rotate(self, dir):
        rot = self.__getattribute__(dir)
        old = self.face
        new = [-1 for _ in range(6)]
        for i in range(6):
            new[i] = old[rot[i]]
        self.face = new

d = list(map(int, input().split()))
D = dice(d)
Q = input()
for c in Q:
    D.rotate(c)
print(D.face[0])


Measured memory_bytes: 5604
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

#define int long long
#define MOD (int)(1e9 + 7)

int pow_mod(int x, int n) {
    int ret;
    if (!n) ret = 1;
    else if (!(n%2)) ret = pow_mod(x * x % MOD, n / 2);
    else if (n&1) ret = pow_mod(x * x % MOD, n / 2) * x % MOD;
    return ret;
}

int a[100005], ans[100005];

signed main(void) {
    int n, p;
    bool flag = true;
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p;
        a[p]++;
        if (a[p] > 2) flag = false; 
    }
    //for (int i = 0; i < n; i++) cout << a[i] << " ";
    //cout << endl;
    for (int i = 0; i < n; i++) {
        if (i != 0 && (n % 2 == 0 && i % 2 == 0 && a[i] > 0) || (n % 2 == 1 && i % 2 == 1 && a[i] > 0)) { flag = false; break; }
        if (i != 0 && a[i] != 0) {
            //cout << i << endl;
            ans[i]++;
            if (ans[i] % 2 == 0) flag = true;
            else flag == false;
        } else if (i == 0 && a[i] == 1) {
            ans[i]++;
            flag = true;
        } else if (i == 0 && a[i] > 1) {
            flag = false;
            break;
        }
    }
    //for (int i = 0; i < n; ++i) cout << ans[i] << " ";
    //cout << endl;
    if (flag) cout << pow_mod(2, n / 2) << endl;
    else cout << 0 << endl;

    return 0;
}

Measured memory_bytes: 1792
import numpy as np
from heapq import heapreplace, heapify
N=int(input())
A=np.array([int(a) for a in input().split(" ")])
lheap, rheap = list(A[:N]), list(-A[2*N:])
heapify(lheap)
heapify(rheap)
Lsum, Rsum = sum(lheap), sum(rheap)
left = [Lsum]
right = [Rsum]

for i in range(N):
    if A[N+i] > lheap[0]:
        Lsum += (A[N+i]-lheap[0])
        heapreplace(lheap, A[N+i])
    
    if -A[2*N-i-1] > rheap[0]:
        Rsum += (-A[2*N-i-1]-rheap[0])
        heapreplace(rheap, -A[2*N-i-1])
    
    left.append(Lsum)
    right.append(Rsum)
print(max(np.array(left)+np.array(right)[::-1]))


Measured memory_bytes: 46176
#include<stdio.h>
#include<stdlib.h>

int main(){

	int N,M;
	scanf("%d %d",&N,&M);

	int a[N+1];
	int b[N+1];
	int c[M+1];
	int d[M+1];
	int dis = 200000000;
	int num = 1;

	for(int i=1; i<=N; i++){
		scanf("%d %d",&a[i],&b[i]);
	}

	for(int j=1; j<=M; j++){
		scanf("%d %d",&c[j],&d[j]);
	}	

	for(int k=1; k<=N; k++){
		for(int l=1; l<=M; l++){
			if(dis > ( abs(a[k]-c[l]) + abs(b[k]-d[l]))){
				num = l;
				dis = abs(a[k]-c[l]) + abs(b[k]-d[l]);
			}
		}
		printf("%d\n",num);
		dis = 200000000;
		num = 1;
	}

	return 0;

}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rand() (rand() << 15 | rand())
using namespace std;
typedef long long  ll;
#define EPS 1e-9
#define PI acos(-1.0)
const int N = 2e5 + 4 , M = 1e6 + 3;
const int MOD = 998244353;
int a[N] , inv[M] , n , cnt[M] , f[M];

int mul(int a , int b , int m = MOD){
   return (1LL * (a % m) * (b % m)) % m;
}

int add(int a , int b , int m = MOD){
   return (1LL * (a % m) + (b % m) + MOD) % m;
}

int powMOD(int x , int n , int m = MOD){
   if(!n)return 1;
   int ret = 1;
   if(n & 1)ret = mul(x , powMOD(x , n - 1 , m) , m);
   else{
      int y = powMOD(x , n / 2 , m);
      ret = mul(y , y , m);
   }
   return ret;
}

void pre(){
   for(int i = 1 ; i < M ; ++i)
      inv[i] = powMOD(i , MOD - 2);
}

int solve(int g){
   int sum = 0;
   for(int i = g ; i < M ; i += g)
      sum = add(sum , mul(cnt[i] , i));
   int res = 0;
   for(int i = g ; i < M ; i += g)
      res = add(res , mul(mul(cnt[i] , i) , sum));
   for(int i = 2 * g ; i < M ; i += g)
      res = (res - f[i] + MOD) % MOD;
   return f[g] = res;
}

int main() {
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   cin >> n;
   for(int i = 0 ; i < n ; ++i)
      cin >> a[i] , cnt[a[i]]++;
   pre();
   int ans = 0;
   for(int i = M - 1 ; i >= 1 ; --i){
      int cur = (1ll * solve(i) * inv[i]) % MOD;
      ans += cur;
      ans %= MOD;
   }

   for(int i = 0 ; i < n ; ++i)
      ans = (ans - a[i] + MOD) % MOD;
   ans = (1ll * ans * inv[2]) % MOD;
   cout << ans << "\n";
}

Measured memory_bytes: 12800
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

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

int main() {
    int n; cin >> n;
    vector<int> a(n + 1), idx(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        idx[a[i]] = i;
    }

    ll ans = 0;
    UnionFind uf(n + 1);
    for (int j = n; j >= 1; j--) {
        int i = idx[j];
        ans += a[i];
        if (i - 1 >= 1 && a[i - 1] > a[i]) {
            ans += 1LL * uf.size(i - 1) * uf.size(i) * a[i];
            uf.unionSet(i - 1, i);
        }
        if (i + 1 <= n && a[i + 1] > a[i]) {
            ans += 1LL * uf.size(i + 1) * uf.size(i) * a[i];
            uf.unionSet(i + 1, i);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
import std.stdio, std.string, std.conv;

void main()
{
	auto ip = readln.split.to!(int[]), A = ip[0], B = ip[1], C = ip[2], D = ip[3];
	if(A+B > C+D){
		writeln("Left");
	} else if(A+B < C+D){
		writeln("Right");
	} else {
		writeln("Balanced");
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) *b;
}

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////





int main() {

	ll N;
	string S;
	cin >> N >> S;

	ll ans = 0;
	ll x = 0;

	rep(i, N) {
		if (S[i] == 'I') { x++; }
		else { x--; }
		ans = max(x, ans);
	}

	cout << ans;
	system("PAUSE");
}


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

  
int main() {
  int N,x;
  cin >>N>>x;
  vector<int> a(N);
  rep(i,N)cin>>a[i];
  sort(a.begin(),a.end());
  rep(i,N) {
    x -= a[i];
    if (x<0){
      cout<<i<<endl;
      break;
    }
    else if (i==N-1&&x==0)cout<<N<<endl;
    else if(i==N-1&&x>0)cout<<N-1<<endl;//あめが余る。一人を犠牲にその子にめっちゃもらってもらえばよい（笑）
  }
  
  return 0;
}


Measured memory_bytes: 256
program FizzBuzzSum;
var
	n, sum, i : int64; 
begin	
	sum := 0;
	readln(n);
	i := 1;
	while i <= n do begin
		if ( i mod 3 <> 0 )
			then if ( i mod 5 <> 0 )
					then sum := sum + i;
		i := i + 1;
	end;
		
	writeln(sum);
end.

Measured memory_bytes: 1384
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0 ; i < n ; i++) {
			a[i] = sc.nextInt();
		}
		int count = 0;
		for(int i = 1 ; i < n - 1 ; i++) {
			if((a[i - 1] < a[i] && a[i] < a[i + 1]) || (a[i - 1] > a[i] && a[i] > a[i + 1]))
				count++;
		}
		System.out.println(count);
		}
}



Measured memory_bytes: 35640
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

N = int(input())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

F = Factorial(N + 2, MOD)

root = 1
stack = [root]
check = [False] * (N + 1)
check[root] = True
p = [0] * (N + 1) 

DAG = []

while stack:
    now_ = stack.pop()
    DAG.append(now_)
    for next_ in G[now_]:
        if check[next_]:
            continue
        stack.append(next_)
        check[next_] = True
        p[next_] = now_

size1 = [0] * (N + 1)
dp1 = [1] * (N + 1)

for now_ in DAG[::-1]:
    size1[now_] += 1
    size1[p[now_]] += size1[now_]
    dp1[now_] *= F.factorial(size1[now_] - 1)
    dp1[now_] %= MOD
    dp1[p[now_]] *= dp1[now_] * F.ifactorial(size1[now_])
    dp1[p[now_]] %= MOD

# print (size1)
# print (dp1)

size2 = [N - size1[i] + 1 for i in range(N + 1)]
dp2 = [1] * (N + 1)

for i in DAG:
    parent = i
    for now_ in G[i]:
        if now_ == p[i]:
            continue
        x = dp1[parent]
        x *= F.ifactorial(size1[parent] - 1)
        x *= F.factorial(size1[now_])
        x *= pow(dp1[now_], MOD - 2, MOD)
        x *= dp2[parent]
        x *= F.ifactorial(size2[parent] - 1)
        x *= F.factorial(size2[now_] - 2)
        dp2[now_] = x % MOD
 
# print (size2)
# print (dp2)

for i in range(1, N + 1):
    ans =  dp1[i] * F.ifactorial(size1[i] - 1) * dp2[i] * F.ifactorial(size2[i] - 1) * F.factorial(N - 1)
    print (ans % MOD)


Measured memory_bytes: 83060