akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Text;
 
namespace ALDS1_14_D
{
	class SuffixArray
	{
		internal int[] sa, rank, tmp;
		internal string S;
		internal int n, k;
		
		public SuffixArray(string SS)
		{
			S = SS;
			n = S.Length;
			sa = new int[n + 1];
			rank = new int[n + 1];
			tmp = new int[n + 1];
			Construct_SA();
		}
		
		public int Compare_SA(int i, int j)
		{
			if(rank[i] > rank[j]) return 1;
			if(rank[i] < rank[j]) return -1;
			
			int ri = i + k  <= n ? rank[i + k] : -1;
			int rj = j + k <= n ? rank[j + k] : -1;
			if(ri > rj) return 1;
			if(ri < rj) return -1;
			return 0;
		}
		
		public void Construct_SA()
		{
			for(int i = 0; i <= n; i++)
			{
				sa[i] = i;
				rank[i] = i < n ? S[i] : -1;
			}
			
			for(k = 1; k <= n; k*= 2)
			{
				Array.Sort(sa, Compare_SA);
				
			    /*Console.WriteLine();
                Console.WriteLine(0 +" " + sa[0]+ "   "+rank[sa[0]]);             
                for (int i = 1; i <= n; i++)
                {
                    Console.WriteLine(i  + " " + sa[i] + " " + S[sa[i]] + " " + rank[sa[i]]);
                }*/
                
                
                tmp[sa[0]] = 0;
                for (int i = 1; i <= n; i++)
                {
                    tmp[sa[i]] = tmp[sa[i - 1]] + ((Compare_SA(sa[i - 1], sa[i]) < 0) ? 1 : 0);
                }
                for (int i = 0; i <= n; i++)
                {
                    rank[i] = tmp[i];
                }
 
			}
		}
		
		public bool Contains(string pattern)
		{
			int l = 1, r = n + 1;
			int pl = pattern.Length;
			
			/*
			Console.WriteLine();
			Console.WriteLine(pattern);
			*/
			
			while(l < r)
			{
				int m = (l + r) / 2;
				
				string subStr = (sa[m] + pl > n) ? S.Substring(sa[m]) : S.Substring(sa[m], pl);
                    
                   
                int comp = subStr.CompareTo(pattern);
                
                 //Console.WriteLine(l + " " + r + " " + m + " " + subStr +" "+ comp);
                if (comp == 0) return true;
                
                if (comp < 0) l = m + 1;
                else r = m;
			}
			return false;
		}
	}
	
	
    class Program
    {
        static void Main(string[] args)
        {
        	var T = Console.ReadLine();
        	
            SuffixArray SA = new SuffixArray(T);
            StringBuilder sb = new StringBuilder();
 
            var Q = int.Parse(Console.ReadLine());
 
            for (int i = 0; i < Q; i++)
            {
                var P = Console.ReadLine();
 
                sb.AppendLine(SA.Contains(P) ? "1" : "0");
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 33104
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int a[110];
  int sum = 0;
  cin >> N;
  for (int i=0; i<N; i++)
    cin >> a[i];
  a[N] = 0;
  sort(a, a+N, greater<int>());
  for (int i=0; i<N; i += 2)
    sum += a[i] - a[i+1];
  cout << sum;
}


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

int main() {
    string o,e; cin >> o >> e;
    string ans;
    for (int i = 0; i < o.length()+e.length(); i++) {
        if(i%2==1) ans += e[i/2];
        else ans += o[i/2];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;

const int CN = 1e5+5;

int n,l[CN],r[CN],id[CN],mnr,pr,mxl,pl;
long long ans = 0;

long long d(int cl,int cr) {return 1ll * max(0, cr - cl + 1);}
bool cmp(int x,int y){
	return r[x] != r[y] ? r[x] < r[y] : l[x] < l[y];
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
	
	mnr = 0x7f7f7f7f;
	for(int i=1;i<=n;i++) if(r[i] < mnr) mnr = r[pr = i];
	mxl = 0;
	for(int i=1;i<=n;i++) if(l[i] > mxl) mxl = l[pl = i];
	
	/* in same */
	for(int i=1;i<=n;i++)
	    if(i != pl && i != pr) ans = max(ans, d(mxl, mnr) + d(l[i], r[i]));
	
	/* in diff */
	for(int i=1;i<=n;i++) id[i] = i;
	sort(id + 1, id + n + 1, cmp);
	int premxl = 0;
	for(int i=2;i<=n;i++){
		premxl = max(premxl, l[ id[i - 1] ]);
		ans = max(ans, d(mxl, r[ id[i] ]) + d(premxl, mnr));
	}
	
	printf("%lld",ans);
	
	return 0;
}

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

#define N_MAX 105

using namespace std;

int main(void){

	int N;
	int arry[N_MAX];
	int min_i;
	int cnt=0;

	cin>>N;

	for(int i=0;i<N;i++){
		cin>>arry[i];
	}

	for(int i=0;i<N;i++){
		min_i=i;
		for(int j=i;j<N;j++){
			if(arry[j]<arry[min_i]){
				min_i=j;
			}
		}
		if(min_i!=i){
			swap(arry[i],arry[min_i]);
			cnt++;
		}
	}

	for(int i=0;i<N-1;i++){
		cout<<arry[i]<<" ";
	}
	cout<<arry[N-1]<<endl;
	cout<<cnt<<endl;

	return 0;
}

Measured memory_bytes: 1164
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
	int x;
	int numbit[10];
	int inall;
	memset(numbit,0,sizeof(numbit));
	scanf("%d",&x);
	int anotherx=x;
	int i=0;
		while(x!=0)
		{
			numbit[i]=x%10;
			x/=10;
			i++;
		}
	for(int i=0; i<10; i++)
	{
		inall+=numbit[i];
	}
	if((anotherx%inall)==0)
	{
		printf("Yes");
	}
	else
	{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int N,M,h,i,T,A;

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

	T=0;
	for(i=0;i<M;i++){
		scanf("%d",&h);
	       T=T+h;}
	
	if(N>=T) printf("%d",N-T);
	else printf("-1");

	return 0;

}


Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    int n,x,i;cin>>n;
    vector<int>v;
  	for(i=1;i<=n;i++){
    	cin>>x;
    	if(x>i) {cout<<-1<<endl;return 0;}
    	v.insert(v.begin()+x-1,x);
  	}
  	for(auto it:v)cout<<it<<endl;
    return 0;
}


Measured memory_bytes: 256
def f(n):
	e=[1,0,0,1];z=[1,1,1,0]
	while n:e=[e,g(e,z)][n%2];z=g(z,z);n/=2
	return e[1]
M=998244353;g=lambda a,b:[(a[x]*b[y]+a[z]*b[w])%M for x,y,z,w in[[0,0,1,2],[0,1,1,3],[2,0,3,2],[2,1,3,3]]];n,m=map(int,raw_input().split());I=[1,1];r=f(m+2*n-2);c=1
for i in range(2,n):I+=[(M-M/i)*I[M%i]%M]
for i in range(n-1):r=(r+c*(M-f(2*n-2-2*i)))%M;c=c*(m+i)*I[i+1]%M
print r

Measured memory_bytes: 24432
import copy
N = int(input())
a = list(map(int,input().split()))
b = copy.deepcopy(a)
while max(a) != min(a):
    mina = min(a)
    for i in range(N):
        if a[i] % mina == 0:
            a[i] = mina
        else:
            a[i] = a[i] % mina
print(min(a))


Measured memory_bytes: 14820
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>



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

using namespace std;
int a,b,c;

int main(){
  cin >> a >> b >> c;
  if(a==5 && b==5&&c==7) cout << "YES" << endl;
  else if(a==5 && b==7&&c==5) cout << "YES" << endl;
  else if(a==7 && b==5&&c==5) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int h, w, n, s;
char g[1001][1001];
bool v[1001][1001];
int id[8] = {0, -1, 0, 1, -1, 0, 1, 0};
int main() {
    scanf("%d %d %d", &h, &w, &n);
    for (int i = 0; i < h; ++i) {
        getchar();
        for (int j = 0; j < w; ++j) {
            while (~scanf("%c", &g[i][j]) && g[i][j] == ' ');
            //printf("%c",g[i][j]);
            if (g[i][j] == 'S') s = i * w + j;
        }
    }
    int ans = 0;
    char c = '0';
    while (c != n + '0') {
        c += 1;
        queue<pair<int, int> > q;
        memset(v, 0, sizeof v);
        v[s / w][s % w] = true;
        q.push({s, 0});
        while (!q.empty()) {
            int i = q.front().first / w, j = q.front().first % w, step = q.front().second;
            //printf("123%d\n%c\n", step, g[i][j]);
            if (g[i][j] == c) {
                s = i * w + j;
                ans += step;
                //printf("%d %d %d\n", i, j, ans);
                break;
            }
            q.pop();
            for (int k = 0; k < 8; k += 2) {
                int ni = i + id[k], nj = j + id[k + 1];
                if (ni >= 0 && ni < h && nj >= 0 && nj < w && !v[ni][nj] && g[ni][nj] != 'X') {
                    v[ni][nj] = true;
                    q.push({ni * w + nj, step + 1});
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}



Measured memory_bytes: 4560
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c=0,d=0;
  cin>>a>>b;
  if(a==2) c=1;
  if(b==2) d=1;
  if(a==4||a==6||a==9||a==12) c=2;
  if(b==4||b==6||b==9||b==12) d=2;
  if(c==d) cout<<"Yes";
  else cout<<"No";
  cout<<"\n";
}


Measured memory_bytes: 256
/* ICPC2008 国内予選問題 Problem A */
// http://sparth.u-aizu.ac.jp/icpc2008/d_problem.php?lang=jp#section_A
// filename = a.c
// アルゴリズム：
//  ts = 太郎が最初に持っているカードの合計点、
//  hs = 花子が最初に持っているカードの合計点、
//  t = 太郎が花子に渡すカード、 h = 花子が太郎の渡すカード とすると
//  題意より ts - t + h = hs + t - h が成立しなければならない。
//  これを整理すると、ts - hs = 2 (t - h) なので
//  ts - hs が奇数の時は題意を満たす交換は存在しない。
//  ts - hs が偶数の時は t - h = (ts - hs)/2 を満たす最小の t, h を探す。
//  このためには、太郎と花子が持っているカードをソートし、小さい方から探す。

#include <stdio.h>

int n;		// 太郎が最初に持っているカードの枚数,  1 <= n <= 100
int m;		// 花子が最初に持っているカードの枚数,  1 <= m <= 100
int tc[100];	// 太郎が持っているカードを記憶する配列,  0 <= tc[i] <= 100
int hc[100];	// 花子が持っているカードを記憶する配列,  0 <= hc[i] <= 100

// 配列 c に入っている nc 個の整数を昇順にソート（バブルソート）
void sort(int c[], int nc)
{
  int i, j;
  for(i=nc-1; i>0; i--){
    for(j=0; j<i; j++){
      if(c[j] > c[j+1]){	// c[j] > c[j+1] なら c[j] と c[j+1] を交換
	int tmp;
	tmp = c[j];
	c[j] = c[j+1];
	c[j+1] = tmp;
      }
    }
  }
}

void solve()
{
  int i, j, t, h, ts=0, hs=0;	// ts, hs は各々太郎と花子が持っているカードの合計点
  int df, found;
  for(i=0; i<n; i++) ts += tc[i];
  for(i=0; i<m; i++) hs += hc[i];
  df = ts - hs;
  if(df & 1){		// df = ts - hs が奇数
    printf("-1\n");	// 交換方法無し
    return;
  }
  sort(tc,n);	// 太郎の持っているカードを昇順にソート
  sort(hc,m);	// 花子の持っているカードを昇順にソート
  found = 0;
  for(i=0; i<m; i++){
    h = hc[i];		// h = 花子が持っているカード
    t = h + df/2;	// t = 太郎が持っているべきカード
    if(t < 0 || t > 100)	// 太郎は負や100を超える値のカードを持っていない
      continue;
    for(j=0; j<n; j++){
      if(t == tc[j]){	// 太郎はその値のカードを持っていた
	found = 1;
	break;
      }
      if(t < tc[j])	// 太郎のカードはソートされているのでこれ以上探しても無駄
	break;
    }
    if(found) break;
  }
  if(found)
    printf("%d %d\n", t, h);
  else
    printf("-1\n");
}

int main()
{
  int i;
  while(1){
    scanf("%d %d", &n, &m);		// n, m を入力
    if(n == 0 && m == 0) break;		// 両方とも0なら終了
    for(i=0; i<n; i++) scanf("%d", &tc[i]);	// 太郎のカードを読み込む
    for(i=0; i<m; i++) scanf("%d", &hc[i]);	// 花子のカードを読み込む
    solve();		// この問題を解く
  }
}



Measured memory_bytes: 2600
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<stdio.h>
#include<math.h>
#include<stdio.h>
#include<complex>
using namespace std;

#define rep(i,n) for(long long i = 0; i < n; i++)

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

const ll INF = ll(1e18) + 1;
const int intINF = 1e9 * 2 + 3;
//--------------------------------------------------
ulli powN(ulli num,ulli i) {
	return (i > 1) ? num : powN(num * 9, i - 1);
}

ulli gcd(ulli a, ulli b) {return (b <= 0) ? a : gcd(b, a % b);}
ulli lcm(ulli a, ulli b) {return a * b / gcd(a, b);}

bool isPrime(int n)
{
	if (n <= 3)return n > 1;
	if (n % 2 == 0)return false;
	if (n % 3 == 0)return false;
	for (int i = 5; i * i < n; i += 6) {
		if (n % i == 0 || n % (i + 2) == 0) { return false; }
	}
	return true;
}
//---------------------------------------------------


ulli func(int num) {
	if (num < 2) {
		return 1;
	}
	else if (num >= 2) {
		return num * func(num - 2);
	}
}

void Main()
{
	char n[4];
	rep(i, 3) {
		cin >> n[i];
	}
	rep(i, 3) {
		if (n[i] == '7') {
			cout << "Yes" << endl;
			return;
		}
	}
	cout << "No" << endl;
}


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

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) ll(i.size())
#define FOR(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (ll i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

template<class T> inline bool cmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool cmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MOD=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll MAXN=1e5+5;
const ll MAXLG=__lg(MAXN)+2;

int n,c;
double dp[302][302][302];
double solve(int cnt1,int cnt2,int cnt3) {
    if (dp[cnt1][cnt2][cnt3] != 0) {
        return dp[cnt1][cnt2][cnt3];
    }
    int cnt0 = n - cnt1 - cnt2 - cnt3;
    if (cnt0 == n) {
        return 0;
    }

    double ret = 0;
    double r = double(cnt0)/n;
    if (cnt1) {
        ret += double(cnt1)/n * ((solve(cnt1-1,cnt2,cnt3)+1)/(1-r) + r/(1-r)/(1-r));
    } 
    if (cnt2) {
        ret += double(cnt2)/n * ((solve(cnt1+1,cnt2-1,cnt3)+1)/(1-r) + r/(1-r)/(1-r));
    }
    if (cnt3) {
        ret += double(cnt3)/n * ((solve(cnt1,cnt2+1,cnt3-1)+1)/(1-r) + r/(1-r)/(1-r));
    }
    debug(cnt1,cnt2,cnt3,ret);
    return dp[cnt1][cnt2][cnt3] = ret;
}
/********** Good Luck :) **********/
int main()
{
    IOS();
    cin >> n;
    int cnt[4] = {};
    REP (i,n) {
        cin >> c;
        cnt[c]++;
    }
    cout << setprecision(20) << solve(cnt[1],cnt[2],cnt[3])<< endl;
    return 0;
}


Measured memory_bytes: 215296
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){

    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(all(v));

    vector<int> p;
    p.push_back(v[0]);
    for(int i = 0; i < n; i++){
        if( *(p.end()-1) != v[i] ) p.push_back(v[i]);
    }
    cout << p.size() << endl;

}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int a,b,c;
  scanf("%d%d%d",&a,&b,&c);
  int max=10*a+b+c;
  if(max<10*b+a+c)
    max=10*b+a+c;
  if(max<10*c+a+b)
    max=10*c+a+b;
  printf("%d\n",max);
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=100100;
long long a[MAXN*3]={0},n,m;
int main(){
	scanf("%lld",&n);
	m=n*3;
	for(int i=1;i<=m;i++)
		scanf("%lld",&a[i]);
	sort(a+1,a+m+1);
	long long ans=0;
	for(int i=3*n-1,j=1;i>=1&&j<=n;i-=2,j++)
		ans+=a[i];
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

#define INF 1000000000

int N, A, B, C;
vector<int> bamboo(8);

int get_bamboo(int cur, int a, int b, int c){
    if(cur == N){
        if(min(a, min(b, c)) > 0){
            return abs(a - A) + abs(b - B) + abs(c - C) -30;
        }else return INF;
    }
    int ret0,ret1,ret2,ret3;
    ret0 = get_bamboo(cur + 1, a, b, c);
    ret1 = get_bamboo(cur + 1, a + bamboo[cur], b, c) +10;
    ret2 = get_bamboo(cur + 1, a, b + bamboo[cur], c) +10;
    ret3 = get_bamboo(cur + 1, a, b, c + bamboo[cur]) +10;
    return min(min(ret0, ret1), min(ret2, ret3));
}

int main(){
    cin >> N >> A >> B >> C;
    for(int i=0; i<N; i++){
        cin >> bamboo[i];
    }

    cout << get_bamboo(0, 0, 0, 0) << endl;;

    return 0;
}

Measured memory_bytes: 256
import numpy as np
import collections

K=int(input())

arr=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

answer=arr[K-1]

print(answer)



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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin >> N;
  vector<ll> L(N);
  for (ll i = 0; i < N; ++i) {
    cin >> L.at(i);
  }
  sort(L.begin(), L.end());
  ll ans = 0;
  for (ll i = 0; i < N; ++i) {
    for (ll j = i + 1; j < N; ++j) {
      ll ab = L.at(i) + L.at(j);
      ll index = lower_bound(L.begin(), L.end(), ab) - L.begin() - j - 1;
      ans += index;
      // cout << ab << ' ' << index << "\n";
    }
  }
  cout << ans << "\n";
}


Measured memory_bytes: 3676
#include <stdio.h>
int main(void){
    int n, m;
    int a[101];
    
    for(int i=0; i<101; i++){
        a[i]=0;
    }

    while(scanf("%d", &n) != EOF){
        a[n]++;
    }
    
    int max=0;
    for(int i=0; i<101; i++){
        if(max<a[i]) max=a[i];
    }
    
    for(int i=0; i<101; i++){
        if(max==a[i]) printf("%d\n", i);
    }
    
}


Measured memory_bytes: 2032
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

#以下が an mod p を求めるソースコードです.
def power_func(a, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p
        n = n >> 1
    return res

A.sort()
if N % 2 == 0 and A == [2*(i // 2)+1 for i in range(N)] or\
        N % 2 == 1 and A == [2*((i+1) // 2) for i in range(N)]:
    #print(2**(N // 2))
    print(power_func(2,N//2,MOD))
else:
    print(0)

Measured memory_bytes: 14008
/*
这是Task F,但是网址是 d 。。。 
*/
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
#define int long long
#define debug cout<<__LINE__<<" "<<__FUNCTION__<<"\n"

inline int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*y;
}
void put(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar((x%10)+48);
}
int n,a[N],id[N],siz[N],fa[N];
inline int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
inline int cmp(const int&A,const int&B){
	return a[A]<a[B];
}
vector<int> l[N];
int dfs(int x){
//	cout<<x<<"       ljsn\n";
	int num=siz[x]-1;
	for(int i=0;i<l[x].size();i++) num+=dfs(l[x][i]);
	return num;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();id[i]=fa[i]=i;siz[i]=1;
	}
	sort(id+1,id+n+1,cmp);sort(a+1,a+n+1);
	int root=0;
	for(int i=n,pos,fx;i>=1;i--){
		fx=find(i);
		pos=lower_bound(a+1,a+n+1,a[i]-n+2*siz[i])-a;
		while(pos<=n&&fx==find(pos)) ++pos;
		if(a[pos]!=a[i]-n+2*siz[i]){
//			cout<<root<<"\n";
			if(!root){
				root=i;
				continue;
			}
			puts("-1");
			return 0;
		}
		siz[pos]+=siz[i];
		l[pos].push_back(i);
		fa[fx]=find(pos);
//		cerr<<i<<"\n";
	}
//	cout<<root<<"\n";
	int res=dfs(root);
//	cout<<res<<" "<<a[root]<<"\n";
	if(res!=a[root]){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<l[i].size();j++) cout<<id[i]<<" "<<id[l[i][j]]<<"\n";
	}
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}


Measured memory_bytes: 12416
#include <stdio.h>
 
int main(int argc, char **argv){
    int i,j,k;
    int n,m,l,*a,*b;
    int nm,ml,c1,c2;
 
    // Input N*M
    scanf("%d %d %d",&n,&m,&l);
    // Input a
    nm = n * m;
    a = malloc(sizeof(int)*nm);
    for(i=0;i<nm;i++){
        scanf("%d", a+i);
    }
    // Input b
    ml = m * l;
    b = malloc(sizeof(int)*ml);
    for(i=0;i<ml;i++){
        scanf("%d",b+i);
    }
    // Calc c & Output c
    for(i=0;i<n;i++){
        for(j=0;j<l;j++){
            c1 = c2 = 0;
            for(k=0;k<m;k++){
                c1 += a[m*i+k] * b[l*k+j];
                if( c1 >= 100000000 ){
                    c2++;
                    c1 -= 100000000;
                }
            }
            if( c2 > 0 ){
                printf("%d%08d",c2,c1);
            } else {
                printf("%d",c1);
            }
            if( j < l-1 ){
                printf(" ");
            } else {
                printf("\n");
            }
        }
    }
 
    return 0;
}

Measured memory_bytes: 692
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
int main()
{
	ll n;
	cin>>n;
	ll p = n%10;
	switch(p){
		case 3:
			cout<<"bon"<<endl;
			break;
			case 0: case 1: case 6: case 8:
				cout<<"pon"<<endl;
				break;
				default:
					cout<<"hon"<<endl;
					break;
	}
	return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>


int rokufunc(int n){
	int roku[] = {1,
		6,
		36,
		216,
		1296,
		7776,
		46656};
	int i;
	int temp = n;
	int ret = 0;
	for(i = 6; i >= 0; i--){
		ret += temp / roku[i];
		temp = temp % roku[i]; 
	}
	return ret;
}

int kyufunc(int n){
	int kyu[] = {1,
		9,
		81,
		729,
		6561,
		59049};
	int i;
	int temp = n;
	int ret = 0;
	for(i = 5; i >= 0; i--){
		ret += temp / kyu[i];
		temp = temp % kyu[i]; 
	}
	return ret;
}

int main(int argc, char *argv[]) {
	
	
	
	int n;
	int i;
	int ans = 9999999;
	int wa = 0;
	scanf("%d",&n);
	
	for(i = 0; i <= n; i++){
		wa = rokufunc(i) + kyufunc(n - i);
		if(wa < ans)ans = wa;
	}
	printf("%d",ans);
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  cout.precision(12);

  long N, M;
  cin >> N >> M;

  priority_queue<long, vector<long>, greater<long>> q;
  rep (i, N) {
    long A;
    cin >> A;
    q.push(A);
  }

  vector<pair<long, long>> BCs(M);

  rep (i, M) {
    long B, C;
    cin >> B >> C;
    BCs[i] = make_pair(B, C);
  }

  sort(BCs.rbegin(), BCs.rend());

  for (auto it: BCs) {
    long B = it.first;
    long C = it.second;
    rep (j, B) {
      long current = q.top();
      if (C <= current) break;
      q.pop();
      q.push(C);
    }
  }

  long result = 0;
  while (q.size()) {
    result +=  q.top();
    q.pop();
  }

  cout << result << endl;

  return 0;
}


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

int main(){
    long long n, x;
    cin >> n >> x;
    long long ans = n;

    long long noko = n-x;
    long long a = x;
    while(noko % a != 0){
        ans += noko/a * 2*a;
        long long tmp = noko;
        noko = a;
        a = tmp % a;
    }

    ans += noko/a * 2*a-a;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define FOR1(i, n) FOR(i, 1, n+1)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define int long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));

#define dl(line) cerr << "RUN: until " << (line) << "th line." << endl
#define dv(name, value) cerr << (name) << " is " << (value) << endl
#define da(v)  cerr << "["; REPI(itr, v){cerr << *itr << (itr != --v.end() ? ", " : "");} cerr << "]" << endl


void solve(long long W, long long H, long long N, std::vector<long long> x, std::vector<long long> y, std::vector<long long> a){
  int x1 = 0; int x2 = W;
  int y1 = 0; int y2 = H;

  REP(i, N) {
    if (a.at(i) == 1) {
      x1 = max(x1, x.at(i));
    } else if (a.at(i) == 2) {
      x2 = min(x2, x.at(i));
    } else if (a.at(i) == 3) {
      y1 = max(y1, y.at(i));
    } else if (a.at(i) == 4) {
      y2 = min(y2, y.at(i));
    }
  }

  int whiteH = max(x2 - x1, (ll)0);
  int whiteW = max(y2 - y1, (ll)0);

  cout << whiteH * whiteW << endl;
}

signed main(){
  long long W;
  scanf("%lld",&W);
  long long H;
  scanf("%lld",&H);
  long long N;
  scanf("%lld",&N);
  std::vector<long long> x(N);
  std::vector<long long> y(N);
  std::vector<long long> a(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&x[i]);
    scanf("%lld",&y[i]);
    scanf("%lld",&a[i]);
  }
  solve(W, H, N, std::move(x), std::move(y), std::move(a));
}


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



ll len(ll y,ll x,ll s){
    ll k=x/y,r=x%y;
    if(!r) return s+(2*k-1)*y;
    else return len(r,y-r,s+2*k*y+2*r);
}

int main(){
    ll n,x,ans;
    cin >> n >> x;
    if(2*x==n) ans = (n/2)*3;
    else if(2*x<n) ans = n+2*x+len(n-2*x,x,0);
    else {
        ll k = x/(n-x),r = x%(n-x);
        if(r==0) ans = x+2*k*(n-x);
        else ans = x+(2*k+1)*(n-x)+2*r+len(r,n-x-r,0); 
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
K = []
for i in range(M):
  i = list(map(int, input().split()))
  K.append(i[1:])
p = list(map(int, input().split()))

ans = 0
for i in range(2**N):
  tmp = i
  flag = True
  cnt = 0
  for j in range(len(K)):
    for k in range(N):
      if ((i>>k) & 1):
        if k+1 in K[j]:
          cnt += 1
    if cnt % 2 != p[j]:
      flag = False
      break
    else:
      cnt = 0
      i = tmp
  if flag:
    ans += 1
print(ans)

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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  LL s;
  Solver(LL s) : s(s){};

  void solve() {
    LL x = 1000000000;
    LL a = (s + x - 1) / x;
    LL d = x;
    LL b = x - s % x;
    if (s % x == 0) b = 0;
    LL c = 1;
    cout << 0 << " " << 0 << " " << a << " " << b << " " << c << " " << d << endl;
  }
};

}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0;
  std::cin >> n;

  Problem::Solver sol(n);
  sol.solve();
  return 0;
}


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

const int LIMIT = 10000000;

char in[LIMIT], *p = in;

__inline int nextInt(void) {
		
	register int res = 0;
	
	while (*p < '0' || *p > '9')p++;
	
	while (*p >= '0' && *p <= '9')
		res = res * 10 + *p++ - '0';
		
	return res;
		
}

const int N = 10005;

int n, m;
int father[N];

__inline int find(int u) {
	
	if (father[u] == u)
		return u;
		
	return father[u] = find(father[u]);
	
}

signed main(void) {
	
	fread(p, 1, LIMIT, stdin);
	
	n = nextInt();
	m = nextInt();
	
	for (register int i = 1; i <= n; ++i)
		father[i] = i;
	
	for (register int i = 1; i <= m; ++i) {
		
		int k = nextInt();
		int x = nextInt();
		int y = nextInt();
		
		if (k)	
			printf("%d\n", find(x) == find(y));
		else 
			father[find(x)] = find(y);
		
	}
	
	return 0;
	
}

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



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

	return 0;
}


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

typedef long long ll;
const ll MOD = 998244353;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

ll n,s;
map<ll,ll> mm;
map<ll,ll> mm2;

ll pow(ll a, ll b) {
    if(mm.find(b) != mm.end()){
        return mm[b];
    }

  if (b == 0) {
    return 1;
  } else if (b % 2 == 0) {
    ll d = pow(a, b / 2);
    mm[b] = (d * d) % MOD;
    return mm[b];
  } else {
    ll d = pow(a, b - 1);
    mm[b] = (a * d) % MOD;
    return mm[b];
  }
}

int main(){
    cin >> n >> s;
    vector<ll> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    ll dp[n+1][s+1];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= s; j++){
            dp[i][j] = 0;
        }
    }
    
    dp[0][0] = pow(2L,n);
    ll inv = pow(2L, MOD-2);
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= s; j++){
            if(j+a[i] <= s && dp[i][j] > 0){
                dp[i+1][j+a[i]] += dp[i][j]*inv;
                dp[i+1][j+a[i]] %= MOD;
            }
            dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= MOD;
        }
    }

    cout << dp[n][s]%MOD << endl;

    return 0;
}

Measured memory_bytes: 73944
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> a = new ArrayList<Integer>();
		for(int i=0;i<10;++i)
			a.add(sc.nextInt());
		Collections.sort(a);
		for(int i=9;i>=7;--i)
			System.out.println(a.get(i));
	}
}

Measured memory_bytes: 17176
#!/usr/bin/env python3

import numpy as np

# line1 = "2 3"
# line2 = ['1 32', '2  63', '1 12']

N, M = map(int,  input().split())
prefinfo = [input() for i in range(M)]
PY = [list(map(int, line.split())) for line in prefinfo]

PY = np.array(PY)
cn = np.array([np.arange(np.shape(PY)[0])])
cc = np.array([np.zeros(np.shape(PY)[0], dtype=int)])

city_list = np.hstack([cn.T, PY, cc.T])
cl_ysort = city_list[np.argsort(city_list[:, 2])]
city_count = np.zeros(N+1, dtype=int)
for i, cinfo in enumerate(cl_ysort):
    pref = cinfo[1]
    city_count[pref] += 1
    cl_ysort[i, 3] = city_count[pref]

cl_idsort = cl_ysort[np.argsort(cl_ysort[:, 0])]

[print('{:06d}{:06d}'.format(cl[1], cl[3])) for cl in cl_idsort]


Measured memory_bytes: 45660
/** omgursocute **/
#include <bits/stdc++.h>

using namespace std;
typedef int64_t ll;
typedef uint64_t ull;
typedef long double ld;

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

	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);

	ld res = a[0];
	for(int i = 1; i < n; i++)
		res = (res+a[i])/2;

	cout << setprecision(16) << res;

	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms.\n";
}

// g++ o .cpp -O2 -std=c++11 -D cute -Wall -Wno-unused-result



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define DEBUG if(1)
#define lli long long int
#define ldouble long double
using namespace std;

const int maxK = 5000; int k, q;
const lli mod = 1e9 + 7;
lli d[maxK], n, x, m;
lli acc[maxK + 1];

int main()
{
  while (scanf("%d %d", &k, &q) != EOF)
  {
    for (int i = 0; i < k; i ++)
      scanf("%lld", &d[i]);

    while (q --)
    {
      scanf("%lld %lld %lld", &n, &x, &m);

      for (int i = 0; i < k; i ++)
        acc[i + 1] = acc[i] + (d[i] == 0 ? m : (d[i] - 1) % m + 1);

      lli last = x + (n - 1) / k * acc[k] + acc[(n - 1) % k];
      lli ans = n - 1 - last / m + x / m;
      printf("%lld\n", ans);
    }
  }
  return 0;
}

Measured memory_bytes: 384
n=int(input())
s=[input() for _ in range(n)]
 
 
 
count={}
for i in range(n):
    if s[i] not in count:
        count[s[i]] = 1
    else:
        count[s[i]] += 1
 
max = max(count.values())
#ans = []
#for word in count:
#    if count[word] == max:
#        ans.append(word)
ans = [k for k,v in count.items() if v == max]
ans.sort()
for i in ans:
    print(i)


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

typedef long long ll;
#define pl pair<ll,ll>

int main(){
  pl p1,p2;
  int x,y;cin>>x>>y;
  p1.first=x;
  p1.second=y;
  cin>>x>>y;
  p2.first=x;
  p2.second=y;
  pl v1;
  v1.first=p2.first-p1.first;
  v1.second=p2.second-p1.second;
  pl v2;
  v2.first=v1.second;
  v2.second=-v1.first;

  cout<<p2.first-v2.first<<" "<<p2.second-v2.second<<" "<<p1.first-v2.first<<" "<<p1.second-v2.second<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
ll a[3050];
 
int main(){
int n=read();
ll llx=0;
for (;n--;){
  llx+=read()-1;
  }write(llx),pl;
}

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

#define ALL(v) (v).begin(),(v).end()

using namespace std ;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;




int main()
{
  int x, a, b, da, db ;
  cin >> x >> a >> b ;
  
  da = a-x ;
  db = b-x ;
  
  if(da<0){
    da = 0-da ;
  }
  if(db<0){
    db = 0-db ;
  }
  
  if(da<db){
    cout <<"A"<<endl ;
  }
  else{
    cout <<"B"<<endl ;
  }
 
    
    return 0 ;
}

/*　吾輩はやれば出来る子である。 
　　　　∩∩ 
　　　（´･ω･） 
　　 ＿|　⊃／(＿＿_ 
　／　└-(＿＿＿_／ 
　￣￣￣￣￣￣￣ 
　やる気はまだない 

　　 ⊂⌒／ヽ-、＿_ 
　／⊂_/＿＿＿＿ ／ 
　￣￣￣￣￣￣￣　　*/

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
#define N 20
#define T 3.305785

int main(void){
	double n,m;
	char str[N];

	fgets(str,sizeof(str),stdin);
	sscanf(str,"%lf %lf",&n,&m);
	printf("%f\n",n*m/T);
	return 0;
}

Measured memory_bytes: 652
def solver():
    m, nmin, nmax = map(int, input().split())
    if m == 0 and nmin == 0 and nmax == 0:
        return None
    p = [int(input()) for _ in range(m)]
    ans = 0
    maxdelta = 0
    for a in range(nmin, nmax+1):
        delta = p[a-1] - p[a]
        if delta >= maxdelta:
            maxdelta = delta
            ans = a
    return ans

outputs = []
while True:
    ans = solver()
    if ans == None:
        break
    outputs.append(ans)
print('\n'.join(map(str, outputs)))

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

using namespace std;

const int N = 1e5 + 5;

int n;

int a[N], ans[N];

int main () {
    cin >> n;
    for (int i = 1;i <= n;i ++) {
        int x;
        cin >> x;
        a[x] = i;
    }
    for (int i = 1;i <= n;i ++) {
        cout << a[i] << ' ';
    }
}


Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n,k;
  while(cin >> n >> k, n+k) {
    int s[k];
    for(int i=0; i<k; i++)
      cin >> s[i];
    int f=0;
    
    for(int i=0; i<n; i++) {
      for(int j=0; j<k; j++) {
        int x;
        cin >> x;

        s[j] -= x;
        if (s[j] < 0)
          f = 1;
      }
    }
    if (f)
      cout << "No" << endl;
    else
      cout << "Yes" << endl;
  }
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    string S;
    cin >> S;
    int n = S.size();
    rep(i, n) cout << 'x';

}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Mod = 1e9+7;
int f[21][1<<19], g[21][1<<19], nxt[21][1<<19];
int n, m, K;
int s0[25], s1[25];
void up(int &x, int y) { x = (x + y) % Mod; }
int main() {
	int i, j, k;
	scanf("%d%d%d", &n, &m, &K);
	for(i = 1; i <= K; i++){
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if(z == 0) s0[x] |= (1<<y-1);
		else s1[x] |= (1<<y-1);
	}
	n--;
	for(i = 0; i < n; i++){
		for(j = 0; j < 1<<n; j++){
			if(j&(1<<i)){
				nxt[i][j] = j^(1<<i);
				for(k = i+1; k < n; k++){
					if(!(j&(1<<k))){
						nxt[i][j] ^= 1<<k;
						break;
					}
				}
			}
		}
	}
	f[0][0] = 1;
	int mx = (1<<n)-1;
	for(i = 1; i <= m; i++){
		for(j = 0; j < 1<<n; j++) g[n][j] = f[i-1][j];
		for(k = n-1; k >= 0; k--){
			for(j = 0; j < 1<<n; j++){
				g[k][j] = g[k+1][j];
				if(j&(1<<k)) up(g[k][j], g[k+1][nxt[k][j]]);
			}
		}
		for(j = 0; j < 1<<n; j++){
			if(((j^mx)&s0[i]) == s0[i] && (j&s1[i]) == s1[i]) f[i][j] = g[0][j];
		}
	}
	int ans = 0;
	for(i = 0; i < 1<<n; i++) up(ans, f[m][i]);
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

#define REP(i,x,y) for (int i=x;i<y;i++)

int main()
{
    int x,y,a,b;
    cin >> x >> y >> a >> b;
    x-=a;
    y-=b;
    cout << x*y << endl;
    return 0;
}

Measured memory_bytes: 256
use std::io;
use std::cmp;


fn main() {
    let (n, mut m) = {
        let i = read::<usize>();
        (i[0], i[1])
    };

    let mut ans:usize = 0;

    let a = cmp::min(n, m / 2);
    ans += a;
    m -= a * 2;
    ans += m / 4;

    println!("{}", ans);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
#prdさんのを写経
import sys
input=sys.stdin.readline

n=int(input())
a=[list(reversed(list(map(lambda x:int(x)-1, input().split())))) for _ in range(n)]
b={i:r for i,r in enumerate(a)}

end=0
for k in range(8000):
    used=set()
    dels=[]
    for i,q in b.items():
        if not q:
            continue
        if i in used:
            continue
        j=q[-1]
        if j in used:
            continue
        if a[j][-1]==i:
            a[j].pop()
            a[i].pop()
            used.add(i)
            used.add(j)
            if not a[i]:
                end+=1
                dels.append(i)
            if not a[j]:
                end+=1
                dels.append(j)
    if not used:
        print(-1)
        exit()
    if end==n:
        print(k+1)
        exit()
    for i in dels:
        del b[i]

print(n*(n-1)//2)


Measured memory_bytes: 58332
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORS(i,a,b) for(int i=a+1;i<=b;i++)
#define REP(i,N) FOR(i,0,N)
#define REPS(i,N) FORS(i,0,N)
#define debug(x) cout<<#x<<"="<<x<<endl
#define debugarr(arr,N,M){REP(i,N){REP(j,M){if(arr[i][j]==INF)printf(" INF");\
	else printf(" %3d",arr[i][j]);} cout<<endl;}}
#define pb push_back
#define pob pop_back
#define cint(a) int a;cin>>a
#define cint2(a,b) int a,b;cin>>a>>b
#define cint3(a,b,c) int a,b,c;cin>>a>>b>>c
typedef long long ll;
const int INF=100000000;
//--------------------------------------//
int main(){
	string s;
	cin>>s;
	cint(k);

	vector<pair<char,int> > pairs;

	REP(i,s.size()){
		pairs.pb(make_pair(s[i],i));
	}
	sort(pairs.begin(), pairs.end());
	queue<int> q;
	int r=0;
	while(true){
		q.push(pairs[r].second);
		r++;
		if(r>5&&pairs[r-1].first!=pairs[r].first||r==s.size())
			break;
	}
	vector<string> vs;
	while(!q.empty()){
		REPS(i,5){
			if(q.front()+i>s.size()) break;
			vs.pb(s.substr(q.front(),i));
		}
		q.pop();
	}
	sort(vs.begin(),vs.end());
	vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
	/*REP(i,vs.size()){
		cout<<vs[i]<<endl;
	}*/
	cout<<vs[k-1]<<endl;
	return 0;
}


Measured memory_bytes: 1660
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int xsize, ysize;
char G[10][10];
bool used[10][10];
const char color[] = {'R', 'G', 'B'};

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

struct State {
    int push;
    char grid[10][10];
    State(){};
    State(int p, char g[][10]){
        push = p;
        for(int i = 0; i < ysize; ++i){
            for(int j = 0; j < xsize; ++j){
                grid[j][i] = g[j][i];
            }
        }
    }
};

bool check(){
    char tmp = G[0][0];
    for(int i = 0; i < ysize; ++i){
        for(int j = 0; j < xsize; ++j){
            if(G[j][i] != tmp) return false;
        }
    }
    return true;
}

void dfs(int x, int y, int idx){
    used[x][y] = true;
    for(int k = 0; k < 4; ++k){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if(0 <= nx && nx < xsize && 0 <= ny && ny < ysize && G[x][y] == G[nx][ny] && !used[nx][ny]){
            dfs(nx, ny, idx);
        }
    }
    G[x][y] = color[idx];
}

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

    while(cin >> xsize >> ysize && (xsize || ysize)){

        for(int i = 0; i < ysize; ++i){
            for(int j = 0; j < xsize; ++j){
                cin >> G[j][i];
            }
        }

        int ans = 0;
        if(!check()){
            queue<State> q;
            q.push(State(0, G));
            while(!q.empty() && ans == 0){
                State st = q.front();
                q.pop();

                for(int k = 0; k < 3; ++k){
                    if(st.grid[0][0] != color[k]){
                        for(int i = 0; i < ysize; ++i){
                            for(int j = 0; j < xsize; ++j){
                                G[j][i] = st.grid[j][i];
                                used[j][i] = false;
                            }
                        }
                        dfs(0, 0, k);
                        if(check()){
                            ans = st.push + 1;
                            break;
                        }
                        if(G[0][0] == G[0][1] || G[0][0] == G[1][0]){
                            q.push(State(st.push + 1, G));
                        }
                    }
                }
            }
        }

        cout << ans << endl;
    }

   return 0;
}

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define debug(x) cerr << #x << " : " << x << endl

ll modpow(ll n, ll m, ll mod) {
    ll ret = 1;
    while(m > 0) {
        if(m & 1) ret = ret * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return ret;
}

vector<vector<ll>> combination_array(int n, ll MOD) {
    vector<vector<ll>> nCk(n + 1, vector<ll>(n + 1));
    nCk[0][0] = 1;
    repeat(i, 1, n + 1) {
        nCk[i][0] = nCk[i-1][0];
        repeat(j, 1, i + 1) {
            nCk[i][j] = (nCk[i-1][j] + nCk[i-1][j-1]) % MOD;
        }
    }
    return nCk;
}

class Solver {
  public:
    bool solve() {

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

        vector<vector<ll>> ways2(N + 1, vector<ll>(N + 1, 0));
        // ways2[i][j] := 1,..,i がすべて１杯以下 and
        //                1,...,i の少なくとも１つが乗っているラーメンがちょうど j 杯である
        //                ようなラーメンの組み合わせの総数
        rep(i, N + 1) ways2[i][0] = 1;

        repeat(i, 1, N + 1) {
            repeat(j, 1, N + 1) {
                ways2[i][j] += ways2[i - 1][j];     // i を使わない
                ways2[i][j] %= M;
                ways2[i][j] += ways2[i - 1][j - 1]; // i だけが乗った新規ラーメンを生成
                ways2[i][j] %= M;
                ways2[i][j] += ways2[i - 1][j] * j; // i を既存のラーメンに乗っける
                ways2[i][j] %= M;
            }
        }
        // debug(ways2);
        vector<ll> ways(N + 1);
        // ways[i] := 1,...,i がすべて１杯以下 なラーメンの組み合わせの総数
        rep(i, N + 1) {
            vector<ll> p(N + 1); {
                // p[j] := (2^(N-i))^j
                ll base = modpow(2, N - i, M);
                p[0] = 1;
                rep(j, N) p[j + 1] = p[j] * base % M;
            }
            rep(j, N + 1) {
                ways[i] += ways2[i][j] * p[j] % M;
                ways[i] %= M;
            }
        }

        auto nCk = combination_array(N, M);
        vector<ll> pow22i(N + 1); {
            // pow22i[i] := 2^(2^i)
            pow22i[0] = 2;
            rep(i, N) pow22i[i + 1] = pow22i[i] * pow22i[i] % M;
        }

        ll ans = 0;
        rep(i, N + 1) {
            ll a = nCk[N][i] * ways[i] % M;
            a = a * pow22i[N - i] % M; // modpow(2, modpow(2, N - i, M - 1), M) % M;
            if(i % 2 == 0) ans = (ans + a) % M;
            else {
                a *= -1;
                while(a < 0) a += M;
                ans = (ans + a) % M;
            }
        }
        cout << ans << endl;
        return 0;
    }
};

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


Measured memory_bytes: 141184
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <list>

using namespace std;
using ll = long long;

int main()
{
    int N, W;
    scanf("%d%d", &N, &W);

    vector<int> w(N), v(N);

    for(int i = 0; i < N; ++i)
        scanf("%d%d", &w[i], &v[i]);

    vector<ll> dp(W + 1, 0);

    for(int item = 0; item <  N; ++item)
    {
        vector<ll> new_dp(W + 1, 0);
        for(int weight = 1; weight <= W; ++weight)
        {
            /* check if value fits in the bag */
            if(weight - w[item] >= 0)
                new_dp[weight] = max(dp[weight], dp[weight - w[item]] + v[item]);
            else
                new_dp[weight] = dp[weight];

            //cout << "adding item  " << item  << "  to bag " << weight << " : " << new_dp[weight] << "\n";
        }
        dp = new_dp;
    }

    cout << dp[W] << "\n";

    return 0;
}


Measured memory_bytes: 1908
#include<iostream>
#include<vector>
using namespace std;
#define int long long
#define pb push_back
#define vi vector<int>
int32_t main()
{
   
        int a;
        cin>>a;
        int ans= a+ a*a + a*a*a;
        cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3140
from itertools import groupby

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

c = 0
add = 0
xor = 0
r = 0
for l in range(N):
    # print(l, r, bin(add)[2:], bin(xor)[2:])
    if r < l:
        r = l
        add = 0
        xor = 0
    while r < N and add+A[r] == xor^A[r]:
        add += A[r]
        xor ^= A[r]
        r += 1
        # print(l, r, add, xor)
    # l <= i < r までの add と xor が等しい
    c += r - l
    add -= A[l]
    xor ^= A[l]
    # print(add, xor, c)

print(c)

Measured memory_bytes: 25220