akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef unsigned long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
struct bity
{
	#define d 64
	vector<ll> wek;
	bity(){}
	bity(int v)
	{
		wek.resize((v/d)+2, 0);
	}
	void upper(int v)
	{
	    while(wek.size() < (v/d)+2) wek.pb(0);
	}
	void upp(int v){
	    while(wek.size() < v) wek.pb(0);
	}
	void ustaw(int v)
	{
		wek[v/d]|=(1LL<<(v%d));
	}
	void zeruj()
	{
		fill(wek.begin(), wek.end(), 0);
	}
	int licz()
	{
		int ret=0;
		for (const ll &i : wek)
			ret+=__builtin_popcountll(i);
		return ret;
	}
};
 
void oruj(bity &a, const bity &b)
{
	int r=min(a.wek.size(), b.wek.size());
	for (int i=0; i<r; i++)
		a.wek[i]|=b.wek[i];
}

int n;
char f[1505][1505];
bity B[10][1505];
ll ans;
int C[10];
int cur[10];
int main(){
	scanf("%d",&n); //n = 950; srand((unsigned)time(NULL));
	for(int i=0;i<n;i++) scanf("%s",&f[i]);
	rep(i,n)rep(j,n)if(f[i][j]!='#')C[f[i][j]-'0']++;
	//repn(x,9) rep(i,n) B[x][i] = bity(0);
	for(int i=0;i<2*n-1;i++){
		for(int j=min(i,n-1);j>=max(0,i-n+1);j--){
			int x = j, y = i-j;
			if(f[x][y] != '#'){
			    B[f[x][y]-'0'][x].upper(cur[f[x][y]-'0']+1);
			    repn(w,9) B[w][x].upp(B[w][x-1].wek.size());
				if(x){
				    repn(w,9) oruj(B[w][x],B[w][x-1]);
				}
				repn(w,9) ans += 1LL*w*(f[x][y]-'0')*(B[w][x].licz());
				B[f[x][y]-'0'][x].ustaw(cur[f[x][y]-'0']++);
			}
			else{
			    repn(w,9) B[w][x].upp(B[w][x-1].wek.size());
				repn(w,9) B[w][x].zeruj();
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 19968
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;

int main()
{
//	freopen("input.txt","r",stdin);
	int a;
	string s;
	cin>>a>>s;
	if(a>=3200) cout<<s<<endl;else cout<<"red\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
using namespace std;

int main(void){
   //cout << fixed << setprecision(10);
  long long int s,n,a[200005],sum[300000]={},res=1;
  cin>>n;
  for(int i=1;i<=n;i++){
      cin>>a[i];
  }
  sort(a+1,a+n+1);
  for(int i=1;i<=n;i++){
      sum[i]=sum[i-1]+a[i];
  }
  
  for(int i=1;i<n;i++){
      if(sum[i]*2>=a[i+1]){
          res++;
      }else{
          res=1;
      }
  }
  cout<<res<<endl;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<50);
template<class T> bool chmin(T &a, const T &b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T &b){
    if(a < b) {a = b; return true;}
    else return false;
}

int main() {
    cin>>N;
    ll x = 100, ans = 0;
    while(x < N){
        ++ans;
        x += x / 100;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3636
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    before = -1
    cnt = 0
    ans = 0
    for a in A:
        if(before != a):
            ans += cnt//2
            cnt = 0
        cnt += 1
        before = a
    if(cnt):
        ans += cnt//2
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 65516
def solve():
    mod = 10 ** 9 + 7
    N, M = map(int, input().split())
    isBreakable = [False] * (N+1)
    for i in range(M):
        a = int(input())
        isBreakable[a] = True

    dp = [0] * (N+1)
    dp[0] = 1
    for i in range(1, N+1):
        if isBreakable[i]:
            continue
        if i == 1:
            dp[1] = 1
            continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
    
    print(dp[-1])

if __name__ == '__main__':
    solve()

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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int N, M;
vector<pii> es;

int main() {
  scanf("%d%d", &N, &M);
  rep(i, N) {
    int a, b;
    scanf("%d%d", &a, &b);
    es.eb(pii(a, b));
  }
  sort(all(es));

  LL ans = 0;
  for (auto &p : es) {
    int num = min(p.Y, M);
    M -= num;
    ans += LL(num)*p.X;
    if (M == 0) break;
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 1400
#include <iostream>
#include <map>
#include <sstream>
#include <cstring>
#include <cctype>

using namespace std;

constexpr int MAX = 1010;
constexpr int LIMIT = 50000000;

int N, line[MAX], order[MAX];
char c1[MAX], c2[MAX], c3[MAX];
int v[MAX];

int getNum(string& s)
{
    if (s == "SET") return 0;
    if (s == "ADD") return 1;
    if (s == "SUB") return 2;
    if (s == "IF")  return 3;
    return 4;
}

map<char, int> mp;

bool solve()
{
    int idx = 0, v1, v2, next;
    for (int i = 0; i < LIMIT; i++) {
        if (idx == N) return 1;
        switch (order[idx]) {
            case 0:
                if (v[idx] != -1) {
                    mp[c1[idx]] = v[idx];
                } else {
                    mp[c1[idx]] = mp[c2[idx]];
                }
                break;
            case 1:
                v1 = mp[c2[idx]];
                v2 = (v[idx] != -1 ? v[idx] : mp[c3[idx]]);
                if (v1 + v2 >= 16) return 1;
                mp[c1[idx]] = v1 + v2;
                break;
            case 2:
                v1 = mp[c2[idx]];
                v2 = (v[idx] != -1 ? v[idx] : mp[c3[idx]]);
                if (v1 - v2 < 0) return 1;
                mp[c1[idx]] = v1 - v2;
                break;
            case 3:
                next = line[v[idx]];
                if (next == -1) return 1;
                if (mp[c1[idx]] != 0) { 
                    idx = next;
                    continue;
                }
                break;
            case 4:
                return 1;
        }
        idx++;
    }
    return 0;
}

int main()
{
    int x;
    string s;
    memset(line, -1, sizeof(line));
    memset(v, -1, sizeof(v));
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x >> s;
        line[x] = i;
        order[i] = getNum(s);
        stringstream ss;
        switch (order[i]) {
            case 0:         
            case 3:
                cin >> c1[i] >> s;
                mp[c1[i]] = 0;
                if (isdigit(s[0])) {
                    ss << s;
                    ss >> v[i];
                } else {
                    c2[i] = s[0];
                    mp[c2[i]] = 0;
                }
                break;
            case 1:
            case 2:
                cin >> c1[i] >> c2[i] >> s;
                if (isdigit(s[0])) {
                    ss << s;
                    ss >> v[i];
                } else {
                    c3[i] = s[0];
                    mp[c3[i]] = 0;
                }
                break;
        }
    }
    if (solve()) {
        for (auto& it : mp) {
            cout << it.first << "=" << it.second << endl;
        }       
    } else {
        cout << "inf" << endl;  
    }
    return 0;
}

Measured memory_bytes: 3176
N, K = map(int, input().split())
A = list(map(int, input().split()))

# N = 10 ** 5 * 2
# K = N
# A = [0] * (N+1)

cnt = 0
while (A[0] < N or A[-1] < N) and cnt < K:
    cnt += 1
    next_A = [0] * (N+1)
    for j in range(N):
        tmp = A[j]
        next_A[max(j-tmp, 0)] += 1
        next_A[min(N, tmp+1+j)] -= 1
    for j in range(N):
        next_A[j+1] += next_A[j]
    next_A.pop()
    A = next_A
print(" ".join([str(i) for i in A]))


Measured memory_bytes: 164856
#include <iostream>

#define BOARD_SIZE 8

void show(char a[][BOARD_SIZE])
{
	for (int i=0; i<BOARD_SIZE; i++) {
		for (int j=0; j<BOARD_SIZE; j++) std::cout << a[i][j];
		std::cout << std::endl;
	}
}

void copy(char a[][BOARD_SIZE], char b[][BOARD_SIZE])
{
	for (int i=0; i<BOARD_SIZE; i++) {
		for (int j=0; j<BOARD_SIZE; j++) a[i][j] = b[i][j];
	}
}

void rotate(char a[][BOARD_SIZE])
{
	char b[BOARD_SIZE][BOARD_SIZE];
	for (int i=0; i<BOARD_SIZE; i++) {
		for (int j=0; j<BOARD_SIZE; j++) b[i][j] = a[BOARD_SIZE-1-j][i];
	}
	copy(a, b);
}

int main()
{
	char board[BOARD_SIZE][BOARD_SIZE];
	for (int i=0; i<BOARD_SIZE; i++) {
		for (int j=0; j<BOARD_SIZE; j++) std::cin >> board[i][j];
	}
	for (int d=90; d<=270; d+=90) {
		std::cout << d << std::endl;
		rotate(board);
		show(board);
	}
	
	return 0;
}




Measured memory_bytes: 3012
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=2e3+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
}
const int mo=998244353;
int k,n,ans;
void input()
{
	k=read<int>(),n=read<int>();
}
int pw[N],C[N<<1][N<<1];
void init()
{
	pw[0]=1;
	For(i,1,n)pw[i]=(pw[i-1]<<1)%mo;
	C[0][0]=1;
	For(i,1,4000)
	{
		C[i][0]=1;
		For(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
}
int Comb(int x,int y)
{
	return C[x+y-1][x];
}
int cal(int num1,int num2,int tot)
{
	int res=0;
	For(i,0,min(num1,tot))res=(res+1ll*pw[i]*Comb(tot-i,num2+i)%mo*C[num1][i]%mo)%mo;
	return res;
}
void work()
{
	int num1,num2;
	For(now,2,k*2)
	{
		if(now<=k+1)
		{
			num2=k-now+1;
			num1=(now-1)/2;
		}
		else
		{
			num2=now-k-1;
			num1=(k*2-now+1)/2;
		}
	//	cout<<now<<' '<<num1<<' '<<num2<<endl;
		ans=cal(num1,num2,n);
		if(now%2==0)ans=(ans+cal(num1,num2,n-1))%mo;
		write(ans,'\n');
	}
}
int main()
{

	input();
	init();
	work();
	return 0;
}


Measured memory_bytes: 61440
S = input()
T = input()
s = len(S)
t = len(T)

tmp = []

for i in range(s - t + 1):
    tmp.append(S[i:i+t])

ans = 0
ansl = []

for i in range(len(tmp)):
    for j in range(t):
        if tmp[i][j] != T[j]:
            ans += 1
    ansl.append(ans)
    ans = 0

print(min(ansl))

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

int main() {
	int a, b, c;
	while (cin >> a >> b >> c) {
		int want = 20 - a - b;
		int cnt = min(10, want);
		if (a <= want)cnt--; if (b <= want)cnt--; if (c <= want)cnt--;
		if (want > 0 && cnt >= 4)puts("YES");
		else puts("NO");
	}
	return 0;
}

Measured memory_bytes: 3016
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
ans=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            pro=[0,0,0]
            pro[0]=lis[i]
            pro[1]=lis[j]
            pro[2]=lis[k]
            if pro[0]==pro[1] or pro[0]==pro[2] or pro[1]==pro[2]:
                continue
            pro.sort()
            if pro[0]+pro[1]>pro[2]:
                ans+=1
print(ans)
    
            
            

Measured memory_bytes: 68948
N, K = map(int, input().split())
S = list(input())
if S[K-1] == 'A':
    S[K-1] = S[K-1].replace('A', 'a')
    print(''.join(S))
elif S[K-1] == 'B':
    S[K-1] = S[K-1].replace('B', 'b')
    print(''.join(S))
else:
    S[K-1] = S[K-1].replace('C', 'c')
    print(''.join(S))

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int x, y;

int solve() {
    return x + y / 2;
}

void input() {
    cin >> x >> y;
}

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

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 256
using System;

class Prog{
  static void Main(){
    int[] ls = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
    int n = ls[0];
    int k = ls[1];
    if(n % (2*k +1) == 0){
      Console.WriteLine(n / (2*k +1));
    }else{
      Console.WriteLine(n / (2*k +1) +1);
    }
  }
}

Measured memory_bytes: 27504
#include<cstdio>
#include<cstring>
#define max 100010
int set[max],count;
long long ans[max],sum[max];
int x[max],y[max];
long long flag;
int find(int x)
{
	int r=x;
	int t;
	while(r!=set[r])
		r=set[r];
	while(r!=x)
	{
		t=set[x];
		set[x]=r;
		x=t;
	}
	return r;
}
 
void merge(int a,int b,int k)
{
	int fa=find(a);
	int fb=find(b);
//	printf("~%d %d\n",fa,fb);
	if(fa!=fb)
	{
		long long temp1=1ll*sum[fa]*sum[fb];
	//	printf("%lld\n",temp1);
		flag=flag-temp1;
		sum[fb]+=sum[fa]; 
		set[fa]=fb;
	}
	ans[k]=flag;
}
 
int main()
{
	int n,m,i;
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i)
	{
		sum[i]=1;
	    set[i]=i;
	}
	for(i=0;i<m;++i)
		scanf("%d%d",&x[i],&y[i]);
	ans[m]=1ll*n*(n-1)/2ll;
	flag=ans[m];
	for(i=m-1;i>=0;i--)
	   merge(x[i],y[i],i);
	for(i=1;i<=m;++i)
	   printf("%lld\n",ans[i]);
	return 0;
}

Measured memory_bytes: 3968
#include <iostream>
#define ll long long
using namespace std;

ll mod=1000000007, dp[62][2][4][4];

int main() {
	ll L, R;
	cin >> L >> R;
	dp[61][0][0][0]=1;
	for(int i=60; i>=0; --i){
	    for(int j=0; j<32; ++j){
	        int a=(j/4)%4, b=j%4, t=j/16;
	        if(((a&1) || !(L&((ll) 1<<i))) && ((b&1) || !(L&((ll) 1<<i)))){
	            int c=a, d=b;
	            if((R&((ll) 1<<i))){
	                c |= 2;
	                d |= 2;
	            }
	            dp[i][t][c][d]=(dp[i][t][c][d]+dp[i+1][t][a][b])%mod;
	        }
	        if(((a&2) || (R&((ll) 1<<i))) && ((b&2) || (R&((ll) 1<<i)))){
	            int e=a, f=b;
	            if(!(L&((ll) 1<<i))){
	                e |= 1;
	                f |= 1;
	            }
	            dp[i][1][e][f]=(dp[i][1][e][f]+dp[i+1][t][a][b])%mod;
	        }
	        if((((a&1) || !(L&((ll) 1<<i))) && ((b&2) || (R&((ll) 1<<i)))) && t){
	            int g=a, h=b;
	            if((R&((ll) 1<<i))) g |= 2;
	            if(!(L&((ll) 1<<i))) h |= 1;
	            dp[i][t][g][h]=(dp[i][t][g][h]+dp[i+1][t][a][b])%mod;
	        }
	    }
	}
	ll ans=0;
	for(int i=0; i<16; ++i){
	    ans=(ans+dp[0][1][i/4][i%4])%mod;
	}
	cout << ans << endl;
	return 0;
}


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

struct StNode
{
  StNode* m_poParnt;
  StNode* m_poLeft;
  StNode* m_poRigt;
  int m_nKey;

  StNode(int nNo) :
    m_poParnt(nullptr), m_poLeft(nullptr), m_poRigt(nullptr), m_nKey(nNo)
  { }
};

void fnPreOrder(StNode* poNode)
{
  if (poNode == nullptr)  return;

  cout << " " << poNode->m_nKey;
  fnPreOrder(poNode->m_poLeft);
  fnPreOrder(poNode->m_poRigt);
}

void fnInOrder(StNode* poNode)
{
  if (poNode == nullptr)  return;

  fnInOrder(poNode->m_poLeft);
  cout << " " << poNode->m_nKey;
  fnInOrder(poNode->m_poRigt);
}

void fnInsert(StNode*& rpoRoot, StNode* poNewNod)
{
  StNode* poParnt = nullptr;
  StNode* poNode = rpoRoot;

  while (poNode != nullptr)
  {
    poParnt = poNode;
    if (poNewNod->m_nKey < poNode->m_nKey)
      poNode = poNode->m_poLeft;
    else
      poNode = poNode->m_poRigt;
  }

  poNewNod->m_poParnt = poParnt;
  if (poParnt == nullptr)
    rpoRoot = poNewNod;
  else if (poNewNod->m_nKey < poParnt->m_nKey)
    poParnt->m_poLeft = poNewNod;
  else
    poParnt->m_poRigt = poNewNod;
}

void fnBinSchTree(StNode*& rpoRoot)
{
  int nMaxSiz;
  cin >> nMaxSiz;

  for (int i = 0; i < nMaxSiz; ++i)
  {
    string sCmd;
    cin >> sCmd;
    if (sCmd[0] == 'i')
    {
      int nNo;
      cin >> nNo;
      StNode* poNewNod = new StNode(nNo);
      fnInsert(rpoRoot, poNewNod);
    }
    if (sCmd[0] == 'p')
    {
      fnInOrder(rpoRoot);
      cout << endl;
      fnPreOrder(rpoRoot);
      cout << endl;
    }
  }
}

void fnPstOrder(StNode* poNode)
{
  if (poNode == nullptr)  return;

  fnPstOrder(poNode->m_poLeft);
  fnPstOrder(poNode->m_poRigt);
  delete poNode;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  StNode* poRoot = nullptr;

  fnBinSchTree(poRoot);
//fnPstOrder(poRoot);
}

Measured memory_bytes: 26576
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=998244353;
int main(){
    ll n,m;cin>>n>>m;
    vector<ll>s(n);
    vector<ll>t(m);
    rep(i,n){
        cin>>s[i];
    }
    rep(i,m){
        cin>>t[i];
    }
    vector<vector<ll> >dp(n,vector<ll>(m));
    if(s[0]==t[0])dp[0][0]=2;
    else dp[0][0]=1;
    REP(i,1,n){
        if(s[i]==t[0])dp[i][0]=(dp[i-1][0]+1)%inf;
        else dp[i][0]=dp[i-1][0];
    }
    REP(i,1,m){
        if(s[0]==t[i])dp[0][i]=(dp[0][i-1]+1)%inf;
        else dp[0][i]=dp[0][i-1]%inf;
    }
    REP(i,1,n){
        REP(j,1,m){
            if(s[i]==t[j])dp[i][j]=(dp[i][j-1]+dp[i-1][j])%inf;
            else{
                dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1])%inf;
            }
        }
    }
    if(dp[n-1][m-1]<0)dp[n-1][m-1]+=inf;
    cout<<dp[n-1][m-1]<<endl;
}

Measured memory_bytes: 31616
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define N 3009
#define inf 1e18
int mod=1e9+7;
int maxN=1e9;

int nc2(int n){
    if(n<2)return 0;
    int ans=n*(n-1)/2;
    return ans;
}

void solve(){
    int n;cin>>n;
    int a[n];
    map<int,int>mp;
    for(int i=0;i<n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    int tot=0;
    for(auto it:mp){
        tot+=nc2(it.second);
    }
    for(int i=0;i<n;i++){
        int curr=nc2(mp[a[i]]);
        int perr=nc2(mp[a[i]]-1);
        cout<<tot-curr+perr<<"\n";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    //cin>>t;
    int x=0;
    while(t--){
        //cout<<"Case #"<<++x<<": ";
        solve();
    }
   
    return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < n; i++)

int count(vector<char> v, char target) {
  int count = 0;
  for (char c : v) {
    if (c == target) {
      count++;
    }
  }
  return count;
}

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

  vector<char> even;
  vector<char> odd;
  for (int i = 0; i < S.size(); i++) {
    if (i % 2 == 0) {
      even.push_back(S[i]);
    } else {
      odd.push_back(S[i]);
    }
  }

  bool many0InEven = false;
  bool many1InEven = false;
  bool many0InOdd = false;
  bool many1InOdd = false;

  if (count(even, '0') >= count(even, '1')) {
    many0InEven = true;
  } else {
    many1InEven = true;
  }

  if (count(odd, '0') >= count(odd, '1')) {
    many0InOdd = true;
  } else {
    many1InOdd = true;
  }

  // cout << count(even, '0') << endl;
  // cout << count(even, '1') << endl;
  // cout << count(odd, '0') << endl;
  // cout << count(odd, '1') << endl;

  int result = 0;
  if (many0InEven) {
    if (many0InOdd) {
      // even:0 , odd: 0
      if (count(even, '0') >= count(odd, '0')) {
        result = count(odd, '0') + count(even, '1');
      } else {
        result = count(even, '0') + count(odd, '1');
      }
    } else {
      // even:0 , odd: 1
      if (count(even, '0') >= count(odd, '1')) {
        result = count(odd, '0') + count(even, '1');
      } else {
        result = count(even, '1') + count(odd, '0');
      }
    }
  } else {
    if (many0InOdd) {
      // even:1 , odd: 0
      if (count(even, '1') >= count(odd, '0')) {
        result = count(odd, '1') + count(even, '0');
      } else {
        result = count(even, '0') + count(odd, '1');
      }
    } else {
      // even:1 , odd: 1
      if (count(even, '1') >= count(odd, '1')) {
        result = count(odd, '1') + count(even, '0');
      } else {
        result = count(even, '1') + count(odd, '0');
      }
    }
  }

  cout << result << endl;

  return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
  
        static void Main(string[] args)
        {
            int[] NMXY = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            int N = NMXY[0];
            int M = NMXY[1];
            int A = NMXY[2];
            int B = NMXY[3];
            int[] X = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            int[] Y = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            int cnt = 0;
            for(int i = A + 1; i <= B; i++)
            {
                if (X.Max() < i && i <= Y.Min())
                {
                    cnt++;
                    break;
                }
            }
            if (cnt > 0)
                Console.WriteLine("No War");
            else
                Console.WriteLine("War");
        }
    }
}

Measured memory_bytes: 13396
#include<stdio.h>

void ans(long n){
	long i=1;
	if(n==0) return;
	while(i*(i+1)/2<n){
		i++;
	}
	printf("%ld\n",i);
	ans(n-i);
}

int main(){
	long n;
	scanf("%ld",&n);
	ans(n);
	return 0;
}


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

int main(){
    int n,ans=0;
    cin >> n;
    map<ll,int> mp;
    for(int i = 0;i < n;i ++){
        ll a;
        cin >> a;
        mp[a] ++;
    }
    auto ite = mp.rbegin();
    while(ite != mp.rend()){
        ll a = ite->first,pa = pow(2ll,ll(log2(a)+1))-a;
        if(mp.find(pa)!=mp.end()){
            mp[a] --;
            mp[pa] --;
            ans ++;
            if(mp[a]<0) ans --,ite ++;
            if(!mp[a]) mp.erase(a);
            if(!mp[pa]) mp.erase(pa);
        }else ite ++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12800
#define _USE_MATH_DEFINES
#define INF 10000000

#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

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

static const double eps = 1e-8;

int main(){
  int N;
  while(~scanf("%d",&N)){
    if(N==0) break;

    int divisor = -10;
    stack<int> stk;
    while(abs(N)>0){
      int rem = (N % 10 < 0 ? N % 10 + 10 : N % 10);
      stk.push(rem);
      N = (N-rem) / divisor;
    }
    while(!stk.empty()){
      printf("%d",stk.top());
      stk.pop();
    }
    printf("\n");
  }
}

Measured memory_bytes: 1196
def myAnswer(N,M,L,R) -> int:
   MAXL=max(L)
   MINR =min(R)
   ans = [i for i in range(1,N+1) if(MAXL<= i and MINR >= i)]
   return len(ans)


def modelAnswer():
   tmp=1
def main():
   N, M = map(int,input().split())
   L =[]
   R = []
   for _ in range(M):
      l,r = map(int,input().split())
      L.append(l)
      R.append(r)
   print(myAnswer(N,M,L[:],R[:]))
   

if __name__ == '__main__':
   main()

Measured memory_bytes: 13960
import math

N = int(input())
a = [int(input()) for _ in range(N)]


count = N
for x in a:
    if x != 2 and x % 2 == 0:
        count -= 1
        continue
    n = int(math.sqrt(x))
    for i in reversed(range(3, n+1, 2)):
        if x % i == 0:
            count -= 1
            break
print(count)



Measured memory_bytes: 6012
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(int argc, const char * argv[]) {
    vector<int> v(3);
    int x, k;
    
    for (int i = 0; i < 3; i++) {
        cin >> x;
        v[i] = x;
    }
    cin >> k;
    sort(v.begin(), v.end());
    int max;
    max = v[2];
    for (int i = 0; i < k; i++) {
        max *= 2;
    }
    cout << v[0] + v[1] + + max << endl;
    return 0;
}


Measured memory_bytes: 256
var
sys = require('sys');

function main() {
  sys.print(input.toUpperCase());
}

var
input = '';

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  main();
});

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

#define int long long
#define pb push_back
const int N = 100005;
int in[N];
int out[N];
vector<int>g[N];
int n,m;
int vis[N];
int len[N];
void dfs(int x,int p){
    vis[x] = 1;
    for(int i:g[x]){
        if(!vis[i]){
            dfs(i,x);
        }
        else{
            len[x] = max(len[x],len[i]);
        }
    }
    len[x]++;
    len[p] = max(len[x],len[p]);
}
int32_t main(){
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        g[a].pb(b);
        in[b]++;
        out[a]++;
    } 
    for(int i=1;i<=n;i++){
        if(vis[i] == 0){
            dfs(i,0);
        }
    }       
    // for(int i=0;i<=n;i++){
    //     cout<<len[i]<<" ";
    // }
    // cout<<endl;
    cout<<len[0]-1<<endl;
}

Measured memory_bytes: 14720
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
sa=sum(a)
aa=a
bb=b
for i in range(n):
    if aa[i]==0:
        if aa[i+1]<=bb[i]:
            bb[i]-=aa[i+1]
            aa[i+1]=0
        else:
            am=aa[i+1]
            aa[i+1]-=b[i]
            bb[i]-=am
    else:
        if aa[i]<=bb[i]:
            bb[i]-=aa[i]
            aa[i]=0
            if aa[i+1]<=bb[i]:
                aa[i+1]=0
            else:
                aa[i+1]-=bb[i]
        else:
            aa[i]-=bb[i]
print(sa-sum(aa))

Measured memory_bytes: 19004
#include<iostream>
 
using namespace std;
 
#define MAX 500000
#define INFTY 2000000000
 
int L[MAX / 2 + 2], R[MAX / 2 + 2], count;
 
void marge (int A[], int n, int left, int mid, int right) {
 
    int n1 = mid -left, n2 = right - mid;
    int i, j, k;
 
    for (i = 0; i < n1; i++) {
        L[i] = A[left + i];
    }
 
    for (i = 0; i < n2; i++) {
        R[i] = A[mid + i];
    }
 
    L[n1] = INFTY;
    R[n2] = INFTY;
 
    i = 0;
    j = 0;
 
    for (k = left; k < right; k++) {
 
        count++;
 
        if (L[i] <= R[j]) {
 
            A[k] = L[i];
            i++;
 
        } else {
 
            A[k] = R[j];
            j++;
 
        }
 
    }
 
}
 
void margeSort (int A[], int n, int left, int right) {
 
    int mid;
 
    if (left + 1 < right) {
 
        mid = (left + right) / 2;
 
        margeSort (A, n, left, mid);
        margeSort (A, n, mid, right);
 
        marge (A, n, left, mid, right);
 
    }
 
}
 
int main () {
 
    int A[MAX], n, i;
    count = 0;
 
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> A[i];
    }
 
    margeSort (A, n, 0, n);
 
    for (i = 0; i < n; i++) {
 
        if (i) {
            cout << " ";
        }
 
        cout << A[i];
 
    }
 
    cout << endl;
 
    cout << count << endl;
 
    return 0;
 
}

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

class Dice{

public:
	Dice(){
		number     = new int[6];
		checkTable = new int[101];
		for(int i=0; i<101; i++){checkTable[i]=-1;}//init
	};

	~Dice(){
		delete[] number;
		delete[] checkTable;
	};
	
	void setLabel(int index, int num){
		number[index]   = num;
		checkTable[num] = index;
	};

	void roll(char ch){
		switch(ch){
		case 'E':
			setNumber(number[3],number[1],number[0],number[5],number[4],number[2]);
			break;
		case 'W':
			setNumber(number[2],number[1],number[5],number[0],number[4],number[3]);
			break;
		case 'N':
			setNumber(number[1],number[5],number[2],number[3],number[0],number[4]);
			break;
		case 'S':
			setNumber(number[4],number[0],number[2],number[3],number[5],number[1]);
			break;
		case 'R':
			setNumber(number[0],number[3],number[1],number[4],number[2],number[5]);
			break;
		}
	};

	bool isSameDice(int given[]){
		for(int i=0; i<6; ++i){
			if(checkTable[given[i]] == -1){return false;}
		}

		// need to include '\n' that occupies 1 unit.
		//char order[25] = "NNNNWNNNWNNNENNNENNNWNNN";
		char order[30] = "RRRRNRRRRNRRRRERRRRNRRRRNRRRR";
		for(int i=0; i<30; ++i){
			roll(order[i]);
			for(int j=0; j<6; ++j){
				if(number[j]!=given[j]){break;}
				if(j==5){return true;}
			}
		}
		return false;
	};

private:
	void setNumber(int n0,int n1,int n2,int n3,int n4,int n5){
		number[0] = n0;	
		number[1] = n1;	
		number[2] = n2;	
		number[3] = n3;	
		number[4] = n4;	
		number[5] = n5;	
	};

private:
	int* number;
	int* checkTable;

};

int main(){
	Dice dice;
	int given[6];
	int label;
	
	for(int i=0; i<6; ++i){
		cin >> label;
		dice.setLabel(i,label);
	}

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

	dice.isSameDice(given) ? cout<<"Yes"<<endl : cout<<"No"<<endl;
	return 0;

}



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

int main(){
  ll N; cin >> N;
  auto b = vector<ll>(N,0);
  for(ll i=0;i<N;i++){
      cin >> b[i];
      b[i]--;
  }

  auto a = vector<ll>();
  bool f=true;
  while(f){
    f=false;
    for(ll i=b.size()-1;i>=0;i--){
            if(b[i]!=i) continue;
            a.push_back(b[i]);
            b.erase(b.begin()+i);
            f=true;
      		break;
    }
    
  }
  
  if(!b.empty()){
  	cout << -1 << endl;
    return 0;
  }
  
  
  for(ll i= a.size()-1;i>=0;i--)
    cout << a[i]+1 << endl;
  
}

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

int main(){
  int N,M,X,ans;
  cin>>N>>M>>X;
  vector<int> A(M);
  int case1=0;
  int case2=0;

  for(int i = 0;i<M;i++){
    cin>>A.at(i);
    if(A.at(i)<X)case1++;
    if(A.at(i)>X)case2++;
  }

  if(case1<case2)ans=case1;
  else ans=case2;


  cout<<ans<<endl;
}


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

//C++14 (GCC 5.4.1)

#define LLINF (1LL<<60)
typedef long long ll;
#define mod 1000000007

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)

template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<typename T> inline T divrup(T a, T b) { if (a % b) return a/b+1; else return a/b;}

#define dbg_v1(i,V) do{cout<<"-v1----\n";rep(i,V.size())cout<<" "<<i<<"\t:"<<V[i]<<endl;cout<<endl;}while(0)
#define dbg_v2(i,k,V) do{cout<<"-v2----\n";rep(i,V.size()){rep(k,V[0].size())cout<<" "<<V[i][k];cout<<endl;}}while(0)

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

    vector<int> A(N);
    rep(i,N) cin >> A[i];
    
    //-----------------------------------
    vector<int> X(N);
    ll c=1,xi=0;
    rep(i,N){
        xi+=A[i]*c;
        c*=-1;
    }
    X[0]=xi;
    repd(i,1,N){
        X[i]=2*A[i-1]-X[i-1];
    }
    cout << X[0];
    repd(i,1,N){
        cout <<" "<<X[i];
    }
    cout<<endl;
    return (0);
}

Measured memory_bytes: 2048
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long[] tp = new long[5];
        for (int i = 0; i < tp.length; i++) {
            tp[i] = sc.nextLong();
        }
        long time = 0;
        long m = n;
        long limitOftp = tp[0];
        for (int i = 0; i < tp.length; i++) {
            time += m / limitOftp;
            if (m % limitOftp != 0) {
                time++;
                m %= limitOftp; 
            } else {
                m = limitOftp;
            }
            if (i < tp.length - 1) {
                if (limitOftp > tp[i + 1]) {
                    m += (limitOftp - tp[i + 1]) * (time - 1 - i);
                    limitOftp = tp[i + 1];
                }           
            }
        }
        System.out.println(time);
        sc.close();
    }
}

Measured memory_bytes: 23124
#include<iostream>
using namespace std;
int main(){
  int n,a[101],i;
  cin >> n;
  for(i=0; i<n;i++)
  cin >> a[i];
  cout << a[n-1];
  for(i=1;i<n;i++)
  cout<< " " << a[n-i-1];
  cout << endl;
  return 0;
}


Measured memory_bytes: 3088
N,K = map(int,input().split())
V = list(map(int,input().split()))

import heapq
ans = 0
for a in range(min(N,K)+1):
    for b in range(min(N,K)-a+1):
        A = V[:a] + V[N-b:]
        heapq.heapify(A)
        for c in range(min(a+b, K-a-b)):
            small = heapq.heappop(A)
            if small > 0:
                heapq.heappush(A,small)
                break
        ans = max(ans, sum(A))
print(ans)


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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)


Measured memory_bytes: 105976
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 4018

int A, B, i, n;
stack<int> S;
int ans[maxN];

int ask(int a, int b) {
    printf("? %d %d\n", a - 1, b - 1);
    fflush(stdout);

    char c;
    cin >> c;

    if (c == 'Y')
        return 1;
    else
        return 0;
}

int main()
{

    cin >> A >> B; n = A + B;
    if (A <= B) {
        printf("Impossible\n");
        fflush(stdout);
        return 0;
    }

    for (i = 1; i <= n; i++) {
        if (S.empty()) {
            S.push(i);
        } else {
            if (ask(S.top(), i)) {
                S.push(i);
            } else {
                S.pop();
            }
        }
    }

    int R = S.top();
    for (i = 1; i <= n; i++)
        ans[i] = ask(R, i);

    printf("! ");
    for (i = 1; i <= n; i++)
        printf("%d", ans[i]);
    printf("\n");
    fflush(stdout);


    return 0;
}


Measured memory_bytes: 724
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int H,W; cin>>H>>W;
  int d = 0;
  rep(i, H) rep(j,W) {
    char c;
    cin >> c;
    if (c=='#') d++;
  }
  if (d == H+W-1) {
    puts("Possible");
  } else {
    puts("Impossible");
  }
  return 0;
}

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

#define ll long long
 
const int N=3e5+5,MAX=3e7,MOD=1e9+7,M=1007;
 
using namespace std;

std::vector<int> g[M];
int n,days[M];
bool games[M];

int main()
{
    scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1,x;j<n;j++){
			scanf("%d",&x);
			g[i].push_back(x);
		}
	}
	for(int i=1;i<=50000;i++){
		memset(games,0,sizeof(games));
		bool ok = false;
		for(int j=1;j<=n;j++){
			if(games[j] || days[j]==n-1)continue;
			int op = g[j][days[j]];
			if(games[op])continue;
			if(g[op][days[op]]==j){
				ok = true;
				days[op]++;
				days[j]++;
				games[op]=games[j]=true;
			}
		}

		if(!ok)return !printf("-1\n");
		int cnt = 0;
		for(int j=1;j<=n;j++)cnt+=(days[j]==(n-1));

		if(cnt==n)return !printf("%d\n",i );

	}

	printf("%d",n*(n-1)/2);
}	


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll x,y;
  cin>>x>>y;
  if(y>4*x) cout<<"No";
  else{
    if((y-2*x)%2==0 && ((y-2*x)>=0)) cout<<"Yes";
    else cout<<"No";
  }
  return 0;
}

Measured memory_bytes: 3564
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

// union find
class union_find {
public:
    int n;
    vector<int> parent, rnk, num;
    
    union_find(int n) : n(n), parent(n), rnk(n, 0), num(n, 1) {rep(i, n) parent[i] = i; }
    
    int root(int x){ return (parent[x] == x) ? x : root(parent[x]); }
    
    void unite(int x, int y){
        x = root(x);
        y = root(y);
        if (x == y) {
            return;
        }
        if (rnk[x] < rnk[y]) {
            parent[x] = y;
            num[y] += num[x];
        }
        else{
            parent[y] = x;
            num[x] += num[y];
            if (rnk[x] == rnk[y]) {
                rnk[x]++;
            }
        }
        n--;
    }
    
    bool same(int x, int y) {return root(x) == root(y);}
    
    int count(int x){ return num[root(x)]; }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    
    int N;
    cin >> N;
    vector<pair<int, int>> A(N);
    union_find uf(N);
    vector<int> X(100010, -1), Y(100010, -1);
    rep(i, N) {
        cin >> A[i].first >> A[i].second;
        if (X[A[i].first] == -1) X[A[i].first] = i;
        else uf.unite(X[A[i].first], i);
        if (Y[A[i].second] == -1) Y[A[i].second] = i;
        else uf.unite(Y[A[i].second], i);
    }
    vector<set<int>> XX(N), YY(N);
    rep(i, 100010) {
        if(X[i] >= 0) XX[uf.root(X[i])].insert(i);
        if(Y[i] >= 0) YY[uf.root(Y[i])].insert(i);
    }
    
    ll ans = 0;
    rep(i, N) {
        if(uf.root(i) == i) ans += (ll)XX[i].size() * (ll)YY[i].size() - (ll)uf.count(i);
    }
    output(ans);
}


Measured memory_bytes: 17024
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using vi = vector<int>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

template<typename T> T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }

const int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int N;
    cin >> N;
    map<int, int> m;
    rep(i, N) {
        int x;
        cin >> x;
        m[x]++;
    }

    bool flag = true;

    for (auto&& p : m) {
        if (p.second > 1) flag = false;
    }

    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


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

const long long INF = 1LL << 60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define vi vector<int>
#define vii vector< vector<int> >

int N;
int sara[4];
double dp[310][310][310];

int main() {

	cin >> N;
	rep(i, N) {
		int a;
		cin >> a;
		sara[a] += 1;
	}

	rep(i, N + 1) {
		rep(j, N + 1) {
			rep(k, N + 1) {

				int nz = i + j + k;  //nonzero
				if (nz == 0) dp[i][j][k] = 0;
				else{
					dp[i][j][k] = (double)N / nz;
					if (i - 1 >= 0) dp[i][j][k] += dp[i - 1][j + 1][k] * i / nz;
					if (j - 1 >= 0) dp[i][j][k] += dp[i][j - 1][k + 1] * j / nz;
					if (k - 1 >= 0) dp[i][j][k] += dp[i][j][k - 1] * k / nz;
				}
			}
		}
	 }

	//cout << dp[sara[3]][sara[2]][sara[1]] << endl;
	printf("%.15lf\n", dp[sara[3]][sara[2]][sara[1]]);
}

Measured memory_bytes: 227584
#include <math.h>
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <ostream>
#include <set>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef int _lcint;
#define REP(i, n) for (_lcint i = 0; i < n; i++)
#define FOR(i, a, b) for (_lcint i = (_lcint)(a); i < (_lcint)(b); i++)
#define FORREV(i, a, b) for (_lcint i = (_lcint)(b)-1; i >= (_lcint)(a); i--)
#define DEBUG(x) cout << #x << ": " << x << endl;
#define DEBUG_VEC(v)  \
  cout << #v << ": "; \
  REP(i, v.size()) cout << " " << v[i] << endl;

#define ALL(a) (a).begin(), (a).end()
#define CHMIN(a, b) a = min((a), (b))
#define CHMAX(a, b) a = max((a), (b))

// permutation
ll mPn(ll m, ll n) {
  ll a = 1;
  REP(i, n) { a *= m - i; }
  return a;
}

// excrametion
ll exc(ll m) {
  ll a = 1;
  FOR(i, 1, m) { a *= i + 1; }
  return a;
}

// combination
ll mCn(ll m, ll n) {
  ll a = 1, b = 1;
  REP(i, n) {
    a *= m - i;
    b *= n - i;
  }
  return a / b;
}

// 最大公約数を求める 条件
ll eculidean(ll a, ll b) {
  ll tmp;
  if (a < b) {
    tmp = a;
    a = b;
    b = tmp;
  }

  ll r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }

  return b;
}

int main() {
  int N;
  cin >> N;
  vi H(N + 1);
  int maxH = 0;
  REP(i, N) {
    cin >> H[i];
    maxH = max(maxH, H[i]);
  }

  int count = 0;

  REP(h, maxH) {
    int gh = -1;
    bool add = false;
    FOR(i, 0, N) {
      if (add && H[i] > h) {
        continue;
      }
      add = false;
      if (H[i] > h) {
        count++;
        add = true;
      }
    }
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 888