akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 100100;
const long long mod = 1e9 + 7;

using namespace std;

int n;
int p[N];
int s[N];
int f[N];
long long d[N];
vector < int > v[N];
pair < long long, int > a[N];

int get(int x){ return f[x] == x ? x : f[x] = get(f[x]); }

void dfs(int x, int p, int dip = 0)
{
        d[1] += dip;
        s[x] = 1;
        for(int y: v[x]) if(y != p){
                dfs(y, x, dip + 1);
                s[x] += s[y];
        }
}

void trace(int x, int p)
{
        for(int y: v[x]) if(y != p){
                d[y] = d[x] + (n - s[y]) - s[y];
                trace(y, x);
        }
}

int main()
{
        ios_base::sync_with_stdio(false);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> a[i].fi;
                a[i].se = i;
                s[i] = 1;
                f[i] = i;
        }
        sort(a + 1, a + n + 1);
        map < long long, int > id;
        for(int i = 1; i <= n; i++){
                id[a[i].fi] = i;
        }

        for(int i = n; i > 1; i--){
                long long dp = a[i].fi;
                dp = dp + s[i] - (n - s[i]);
                if(id.find(dp) == id.end() || dp > a[i].fi){
                        cout << -1 << "\n";
                        return 0;
                }
                p[i] = id[dp];
                s[p[i]] += s[i];

                int px = get(i), py = get(p[i]);
                if(px == py){
                        cout << -1 << "\n";
                        return 0;
                }
                f[px] = py;
        }
        if(s[1] != n){
                cout << -1 << "\n";
                return 0;
        }
        for(int i = 2; i <= n; i++){
                int x = a[i].se;
                int y = a[p[i]].se;
                v[x].push_back(y);
                v[y].push_back(x);
        }
        dfs(1, 1);
        trace(1, 1);
        for(int i = 1; i <= n; i++){
                if(d[a[i].se] != a[i].fi){
                        cout << -1 << "\n";
                        return 0;
                }
        }
        for(int i = 2; i <= n; i++){
                int x = a[i].se;
                int y = a[p[i]].se;
                cout << x << " " << y << "\n";
        }
}


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

const ll INF = (ll)INT32_MAX;
int wt[105],val[105];
ll dp[105][100005];


int main()
{
	int n,w;
	scanf("%d %d",&n,&w);
	
	for(int i=1;i<=n;i++)
	scanf("%d %d",&wt[i],&val[i]);
	
	//dp[i][j] = min weight needed to get to value j using  1 to i items;;;;
	for(int i=0;i<=101;i++)
	for(int j=0;j<100002;j++)
	dp[i][j] = INF;
	
	for(int i=0;i<=n;i++)
	dp[i][0] = 0;
	
	for(int i=1;i<=n;i++)
	{
		for(int value=1;value<=100001;value++)
		{
			if(value-val[i]>=0)
			dp[i][value] = min(dp[i-1][value],(ll)wt[i]+dp[i-1][value-val[i]]);
			
			else
			dp[i][value] = dp[i-1][value];
		}
	}
	
	int ans = 0;
	
	for(int i=1;i<=100001;i++)
	{
	  // cout<<dp[n][i]<<" "<<i<<endl;
		if(dp[n][i]<=w)
		ans = max(ans,i);
	}
	
	printf("%d\n",ans);
	return 0;	
	
}

Measured memory_bytes: 83460
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int[] bells = new int[3];
        for (int i = 0; i < 3; i++) {
            bells[i] = Integer.parseInt(sc.next());
        }
        Arrays.sort(bells);
        System.out.println(bells[0] + bells[1]);
    }
}


Measured memory_bytes: 21844
// c++include
#include <iostream>
// cinclude
#include <stdio.h>
#include<string.h>
#include<math.h>
//c++標準ライブラリ
#include<vector>
#include<string>
//std使用<-namespace
using namespace std;

// define, typedef
#define rpt(i, n) for(i = 0; i < (n); i++)
typedef long long ll;

// main関数
int main(void) {
	int a, b;
	cin >> a >> b;
	int c = 1, count = 0;
	while (true) {
		if (c >= b) {
			cout << count;
			break;
		}
		else {
			c += a - 1;
			count++;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define PIGRECO 3.141592653589793
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c> {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
	~debug() { cerr << endl; }
	eni( != ) cerr << boolalpha << i; ris;
}
eni( == ) ris << range(begin(i), end(i));
}
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
#define int long long
const int mod = 998244353;
const int maxn = 2e5 + 5;
int fact[maxn], fin[maxn];


long long binpow(long long a, long long b) {

	long long res = 1;

	a = a % mod;

	while (b > 0) {

		if (b & 1)
			res = (res * a) % mod;


		a = (a * a) % mod;

		b >>= 1;

	}

	return res;

}


long long inverse(long long a) {
	return binpow(a, mod - 2);
}

long long nCr(long long n, long long r) {

	if (r < 0 || r > n)
		return 0;

	return ((fact[n] * fin[r]) % mod * fin[n - r]) % mod;

}





int32_t main() {


	int n, m, k;
	cin >> n >> m >> k;
	fact[0] = 1;

	for (int i = 1; i < maxn; i++)
		fact[i] = fact[i - 1] * i % mod;

	fin[maxn - 1] = inverse(fact[maxn - 1]);

	for (int i = maxn - 2; i >= 0; i--) {
		fin[i] = fin[i + 1] * (i + 1) % mod;
	}



	long long ans = 0;


	for (int i = 0; i <= k; i++) {

		ans = (ans + (((nCr(n - 1, i) * m) % mod) * binpow(m - 1, n - 1 - i)) % mod) % mod;

	}


	cout << ans << endl;




}

Measured memory_bytes: 6740
H, W = map(int, input().split())
if H%3==0 or W%3==0:
    print(0)
else:
    minH = float("inf")
    for i in range(1, H):
        A = W * i
        BH = W * ((H-i)//2)
        CH = H*W - A - BH
        BW = W//2 * (H-i)
        CW = H*W - A - BW
        Hdiff = max(A, BH, CH) - min(A, BH, CH)
        Wdiff = max(A, BW, CW) - min(A, BW, CW)
        minH = min(minH, min(Hdiff, Wdiff))

    minW = float("inf")
    for i in range(1, W):
        A = H * i
        BH = H * ((W-i)//2)
        CH = H*W - A - BH
        BW = H//2 * (W-i)
        CW = H*W - A - BW
        Hdiff = max(A, BH, CH) - min(A, BH, CH)
        Wdiff = max(A, BW, CW) - min(A, BW, CW)
        minW = min(minW, min(Hdiff, Wdiff))

    print(min(minH, minW))

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <cassert>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to, s;
};
signed main() {

	ll n, k;
	cin >> n >> k;
	ll ans = 0;
	if (k % 2 == 0) {
		ll c = n/k + 1;
		if ((c-1) *k + k / 2 > n) c--;
		ans += c * c * c;
	}

	ll c = n/k;
	ans += c * c * c;

	cout << ans << endl;
	return 0;
}


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

using ll=long long; 

void solve(){
	int d,n;
	cin>>d>>n;
	if(d==0)d=1;
	else if(d==1)d=100;
	else if(d==2)d=10000;
	if(n==100){
		n+=1;
	}
	cout<<n*d<<endl;
}

signed main(){
	//while(1)
	solve();
}


Measured memory_bytes: 256
#include<stdio.h>

int n,y,b,r,t,bm;
int i,j;
double gen,max,a;

int main(void)
{
	scanf("%d",&n);
	while(n!=0){
		gen=1.0;
		max=0.0;
		scanf("%d",&y);
		for(i=0;i<n;i++){
			scanf("%d %d %d",&b,&r,&t);
			if(t==1){
				gen=1.0+y*(r/100.0);
			}
			else if(t==2)	{
				gen=1.0+(r/100.0);
				a=gen;
				for(j=0;j<y-1;j++){
					gen*=a;
				}	
			}
			if(max<gen){
				bm=b;
				max=gen;
			}
		}
		printf("%d\n",bm);
		scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 600
#include<cstdio>
#include<algorithm>
using namespace std;
int N,A,B,que[300005];
int main(void){
	int i,bl,l,r,t,now=0;
	scanf("%d%d%d",&N,&A,&B);
	if(A+B>N+1||1ll*A*B<N){
		puts("-1");
		return 0;
	}
	r=N,l=r-A+1;
	for(;now<A;)que[++now]=l+now-1;t=1;
	r=l-1,l=max(1,r-A+1);
	while(r&&t+r+1-min(A,r-l+1)>=B){
		for(i=1;i<=A&&l+i-1<=r;++i)que[++now]=l+i-1;++t,r=l-1,l=max(1,r-A+1);
	}
	l=1,r=B-t,bl=r+1;
	for(i=r;i;--i)que[++now]=i;
	for(i=1;now<=N;++i)que[++now]=bl+i-1;
	for(i=1;i<=N;++i)printf("%d ",que[i]);
	return 0;
}


Measured memory_bytes: 3328
import sys

s = input()

for i in range(len(s)-1):

    if s[i] == s[i+1]:
        print (i+1,i+2)
        sys.exit()

for i in range(len(s)-2):

    if s[i] == s[i+2]:
        print (i+1,i+3)
        sys.exit()

print (-1,-1)


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

using namespace std;

#define MAXN 100001

vector <int> adj[MAXN];

bool visited[MAXN][3];
int dista[MAXN][3];

int main(){
	#ifdef EVAL
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	int N, M;
	cin >> N >> M;
	for(int i = 0, a ,b; i < M; i++){
		cin >> a >> b;
		adj[a].push_back(b);
	}
	int S, T;
	cin >> S >> T;
	memset(dista,-1,sizeof(dista));
	queue <pair <int,int>> q;
	for(int &i : adj[S]){
		visited[i][0] = true;
		dista[i][0] = 0;
		q.push({0,i});
	}
	while(!q.empty()){
		int node = q.front().second;
		int jump = q.front().first;
		int nextJump = (jump + 1) % 3;
		int w = (nextJump == 2) ? 1 : 0;
		q.pop();
		for(int &i : adj[node]){
			if(visited[i][nextJump])continue;
			visited[i][nextJump] = true;
			dista[i][nextJump] = dista[node][jump] + w;
			q.push({nextJump,i});
		}
	}
	cout << dista[T][2];
}

Measured memory_bytes: 7168
#include <stdio.h>

int main(int argc, char** argv){
	int n,value;
	int base,max_diff;
	int i;

	// Input n + two number
	scanf("%d%d%d",&n, &base, &value);
	max_diff = value - base;
	if( value < base ) {
		base = value;
	}

	// Check Rest Number
	for(i=3;i<=n;i++){
		scanf("%d",&value);
		if( value - base > max_diff ){
			max_diff = value - base;
		}
		if( value < base ) {
			base = value;
		}
	}

	// Output
	printf("%d\n",max_diff);

	return 0;
}

Measured memory_bytes: 596
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node{
  int key;
  struct Node *left,*right,*parent;
};

struct Node * treeMinimum(struct Node *);
struct Node * find(struct Node *,int);
struct Node * treeSuccessor(struct Node *);
void treeDelete(struct Node *);
void insert(int);
void inorder(struct Node *);
void preorder(struct Node *);

struct Node *root,*NIL;

int main(){
  int n,i,x;
  char com[10];
  struct Node *t;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",com);
    if(strcmp(com,"find")==0){
      scanf("%d",&x);
      t=find(root,x);
      if(t!=NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(strcmp(com,"insert")==0){
      scanf("%d",&x);
      insert(x);
    }
    else if(strcmp(com,"print")==0){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(strcmp(com,"delete")==0){
      scanf("%d",&x);
      treeDelete(find(root,x));
    }
  }
  return 0;
}

struct Node * find(struct Node *u,int k){
  while(u!=NIL && k!=u->key){
    if(k < u->key) u=u->left;
    else u=u->right;
  }
  return u;
}

void insert(int k){
  struct Node *y=NIL;
  struct Node *x=root;
  struct Node *z;

  z=(struct Node *)malloc(sizeof(struct Node));
  z->key=k;
  z->left=NIL;
  z->right=NIL;
  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL){
    root=z;
  }
  else{
    if(z->key < y->key){
      y->left=z;
    }
    else{
      y->right=z;
    }
  }
}

void inorder(struct Node *u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(struct Node *u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

void treeDelete(struct Node *z){
  struct Node *y;
  struct Node *x;

  if(z->left==NIL || z->right==NIL) y=z;
  else y=treeSuccessor(z);
  if(y->left !=NIL){
    x=y->left;
  }
  else{
    x=y->right;
  }
  if(x!=NIL){
    x->parent=y->parent;
  }
  if(y->parent==NIL){
    root=x;
  }
  else{
    if(y==y->parent->left){
      y->parent->left=x;
    }
    else{
      y->parent->right=x;
    }
  }
  if(y!=z){
    z->key=y->key;
  }

  free(y);
}

struct Node * treeSuccessor(struct Node *x){
  if(x->right!=NIL) return treeMinimum(x->right);
  struct Node *y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

struct Node * treeMinimum(struct Node *x){
  while(x->left!=NIL) x=x->left;
  return x;
}

Measured memory_bytes: 19364
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int inf = 2e9+5;

int main(){
	int n;
	cin>>n;
	ll arr[n];

	for(int i=0;i<n;i++) cin>>arr[i];
	for(int i=1;i<n;i++) arr[i] = arr[i]+arr[i-1];

	ll res = inf;
	for(int i=0;i<n-1;i++){
		res = min(res,abs(arr[i]-(arr[n-1]-arr[i])));
	}
	cout<<res;
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main(void){
    ll k;
    cin >> k;
    ll ok = 1e12, ng = 0;
    while (ok - ng > 1){
        ll x = (ok + ng) / 2, y = x;
        VI d;
        while (y){
            d.push_back(y % 10);
            y /= 10;
        }
        reverse(ALL(d));
        // cout << "check " << x << endl;
        int n = d.size();
        vector<VVL> dp(n, VVL(10, VL(2)));
        FOR(j,1,d[0]){
            dp[0][j][j<d[0]] = 1;
        }
        REP(i,n-1) REP(j,10){
            if (j > 0) dp[i+1][j][1]++;
            REP(f,2) FOR(k,max(0,j-1),min(9,j+1)){
                if (!f && k > d[i + 1]) continue;
                dp[i+1][k][f | (k < d[i + 1])] += dp[i][j][f];
            }
        }
        // REP(i,n){
        //     REP(f,2){
        //         REP(j,10) cout << dp[i][j][f] << " ";
        //         cout << endl;
        //     }
        //     cout << endl;
        // }
        ll s = 0;
        REP(f,2) REP(j,10) s += dp[n-1][j][f];
        // cout << s << endl;
        if (s >= k) ok = x;
        else ng = x;
    }
    cout << ok << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main() {
	int m, n;
	long ans = 1;
	scanf("%d %d", &m, &n);
	long long beki[31], num[31];
	beki[0] = 1;
	num[0] = m;
	for (int i = 1; i < 31; i++) {
		beki[i] = 2 * beki[i - 1];
		num[i] = num[i - 1] * num[i - 1] % 1000000007;
	}
	for (int i = 30; i >= 0; i--) {
		if (n >= beki[i]) {
			ans *= num[i];
			ans %= 1000000007;
			n -= beki[i];
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 2740
import io.StdIn._

object Main extends App {
  val arr       = readLine.split(" ")
  val tHitPoint = arr(0).toInt
  val tAttack   = arr(1).toInt
  val aHitPoint = arr(2).toInt
  val aAttack   = arr(3).toInt

  def process(tHitPointRest: Int, aHitPointRest: Int, isTsTurn: Boolean): Unit = {
    if (isTsTurn) {
      if ((aHitPointRest - tAttack) > 0) process(tHitPointRest, aHitPointRest - tAttack, !isTsTurn)
      else print("Yes")
    } else {
      if ((tHitPointRest - aAttack) > 0) process(tHitPointRest - aAttack, aHitPointRest, !isTsTurn)
      else print("No")
    }
  }

  process(tHitPoint, aHitPoint, true)
}


Measured memory_bytes: 54616
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main () {
  LL N;
  cin >> N;
  vector<LL> A(N);
  for(auto& i: A) cin >> i;
  A.emplace_back(0);
  A.insert(begin(A), 0);
  LL S = 0;
  for(auto i=1; i<=N+1; ++i) S += abs(A[i]-A[i-1]);
  for(auto i=1; i<=N; ++i) {
    LL sum = S;
    sum -= abs(A[i]-A[i-1]);
    sum -= abs(A[i]-A[i+1]);
    sum += abs(A[i-1]-A[i+1]);
    cout << sum << endl;
  }
}


Measured memory_bytes: 2032
#include <cstdio>
#include <algorithm>
using namespace std;
const int NN = 105;
int N, x, A[NN];
int main() {
	scanf("%d%d", &N, &x);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &A[i]);
	sort(A + 1, A + N + 1);
	for (int i = 1; i <= N; ++i)
		if (x >= A[i])
			x -= A[i];
		else {
			printf("%d\n", i-1);
			return 0;
		}
	if (x == 0)
		printf("%d\n", N);
	else printf("%d\n", N - 1);
	return 0;
}

Measured memory_bytes: 3192
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
    int d;
    cin>>d;
    vector<int>c(26),t(d),nod(26);
    rep(j,26)cin>>c[j];
    vector<vector<int>>s(d,vector<int>(26));
    rep(i,d)rep(j,26)cin>>s[i][j];
    //rep(i,d)cin>>t[i];
    int pt=0,mx,tx;
    rep(i,d){
        mx=-1000000;
        rep(j,26){
            tx=s[i][j]+nod[j]*c[j];
            if(tx>mx){
                mx=tx;
                t[i]=j+1;
            }
        }
        
        rep(j,26){
            if(t[i]-1==j){
                pt+=s[i][j];
                nod[j]=0;
            }
            else{
                nod[j]++;
                pt-=c[j]*nod[j];
            }
        }
        //cout<<pt<<endl;
        
    }
    rep(i,d)cout<<t[i]<<endl;
	return 0;
}


Measured memory_bytes: 3696
use std::cmp::{max, min};
use std::io::{stdin, Read};

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: ty),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, t: usize);
    const M: usize = 61;
    let msb = |x: &usize| {
        let mut ret = M;
        while ret > 0 && *x >> ret == 0 {
            ret -= 1
        }
        ret
    };
    'outer: for _ in 0..t {
        parse!(it, n: usize, a: [usize; n]);
        let s: Vec<bool> = it.next().unwrap().bytes().map(|x| x == b'1').collect();
        let mut bases = vec![];
        for i in (0..n).rev() {
            let mut res = a[i];
            while res > 0 {
                let m = msb(&res);
                if let Ok(i) = bases.binary_search_by_key(&m, msb) {
                    res ^= bases[i];
                } else {
                    break;
                }
            }
            if res != 0 {
                if s[i] {
                    println!("{}", 1);
                    continue 'outer;
                } else {
                    bases.push(res);
                    bases.sort()
                }
            }
        }
        println!("{}", 0);
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


int main(){
    string s;
    cin >> s;
    
    int ans = 0;
    int tmp = 0;
    REP(i, s.size()){
        if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] =='T'){
            tmp++;
            ans = max(ans, tmp);
        }else{
            tmp = 0;
        }
    }
  
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
function Main(input) {
    input = new Date(input);
    if( input.getFullYear() <= 2019 &&
        input.getMonth() <= 3 &&
        input.getDate() <= 30) console.log("Heisei");
    else console.log("TBD")
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 9416
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

O = s()
E = s()

p = ''
for i in range(len(E)):
    p += O[i] + E[i]

if len(O) > len(E):
    p += O[-1]
print(p)


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long double ld;

double rad(double x) { return x * M_PI / 180; }

int main() {
    ld a, b, h, m;
    cin >> a >> b >> h >> m;

    ld hAngle = (h * 60 + m) / 2, mAngle = m * 6;
    pair<ld, ld> x = {cos(rad(hAngle)) * a, sin(rad(hAngle)) * a};
    pair<ld, ld> y = {cos(rad(mAngle)) * b, sin(rad(mAngle)) * b};

    ld ret = sqrt(pow(x.first - y.first, 2) + pow(x.second - y.second, 2));
    cout << fixed << setprecision(15) << ret << endl;
    return 0;
}

Measured memory_bytes: 4044
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main(){
  string str;
  int sum = 0,num;

  while(getline(cin,str)){
    for(int i = 0 ; i < str.size() ; i++){
      if('0' <= str[i] && str[i] <= '9') continue;
      else str[i] = ' ';
    }

    stringstream s;
    s << str;
    while(s >> num){
      sum += num;
    }
  }
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 1224
def main():
    #import sys
    #input = sys.stdin.readline
    A,B = map(int, input().split())
    m = B-A
    A2 = []
    B2 = []
    Atmp = A
    Btmp = B
    i = 2
    while i//2 < B+1:
        B2.append(int((B+1)//i*i/2 + max((B+1)%i - i/2,0)))
        i *= 2
    j = 2
    while j//2 < A:
        A2.append(int(A//j*j/2 + max(A%j - j/2,0)))
        j *= 2
    
    for _ in range(len(B2)-len(A2)):
        A2.append(0)
    
    ans = 0
    tmp = 1
    for i in range(len(B2)):
        ans += tmp * ((B2[i] - A2[i])%2)
        tmp *= 2
    print(ans)
    
    
    
main()

Measured memory_bytes: 38384
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>

using namespace std;


/*--- Macro ---*/
#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 mp make_pair
#define pb push_back


/*---  Type ---*/
typedef long long ll;


/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;


// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// -------------------------------------------------------------------------------------

int main() {
  int n;
  vector<string> s;

  cin >> n;
  s.resize(n);
  rep(i, n) cin >> s[i];

  vector< vector<int> > counts(26, vector<int>(n, 0)); // 1行目はa, 2行目はb, ...
  rep(i, n) {
    rep(j, s[i].length()) {
      counts[s[i][j]-'a'][i]++;
    }
  }

  string ans = "";
  rep(i, 26) {
    auto min_e = min_element(counts[i].begin(), counts[i].end());
    rep(j, *min_e) ans += (i + 'a');
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define sz(c) int(c.size())
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define vlong long long
int main() {
	int n;
	cin >> n;
	int x;
	vector<int> v;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &x);
		if (x == i + 1)
			v.push_back(x);
	}
	int ans = sz(v);
	for (int i = 1; i < sz(v); ++i) {
		if (abs(v[i] - v[i - 1]) == 1) {
			ans--;
			i ++;
		}
	}
	cout << ans << endl;

}


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

using namespace std;

int main() {

    int n ;
    cin>>n;
    string s;
    cin>>s;
    int idx;

    idx = s.find("ABC");

    int ans=0;

    while(idx!=-1){
        ans++;
        idx = s.find("ABC",idx+1);
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <fstream>

using namespace std;

//ifstream fin ("data.in");

int main() {
    int n, mat[100000][4];

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 3; j++) {
            cin >> mat[i][j];
        }
    }

    for (int i = n - 1; i >= 1; i--) {
        mat[i][1] = max(mat[i][1] + mat[i + 1][2], mat[i][1] + mat[i + 1][3]);
        mat[i][2] = max(mat[i][2] + mat[i + 1][1], mat[i][2] + mat[i + 1][3]);
        mat[i][3] = max(mat[i][3] + mat[i + 1][1], mat[i][3] + mat[i + 1][2]);
    }

    cout << max(max(mat[1][1], mat[1][2]), mat[1][3]);
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int maxn=67108866;
int dp[maxn];
char str[200004];
int main()
{
    memset(dp,127,sizeof(dp));
    dp[0]=0;
    scanf("%s",str);
    int l=strlen(str),now=0,ans;
    for(int i=0;i<l;i++)
    {
        int num=str[i]-'a';
        now=now^(1<<num);
        int best=dp[now];
        for(int j=0;j<26;j++)
        {
            best=min(best,dp[now^(1<<j)]);
        }
        best++;
        dp[now]=min(dp[now],best);
        //printf("%d %d\n",i,best);
        ans=best;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 262656
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <numeric>
#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
using namespace std;

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};
const int MOD = 1000000007;

ll y[10000005];

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;


    vector<int> z, o;
    if (s[0] == '0') o.pb(0);
    int t = 0, cnt = 0;
    while (t < n) {
        if (s[t] == s[t + 1]) {
            t++;
            cnt++;
        } else {
            cnt++;
            if (s[t] == '0') z.pb(cnt);
            else o.pb(cnt);
            t++;
            cnt = 0;
        }
    }
    if(s[n-1] == '0') o.pb(0);

    if(k > z.size()){
        cout << n << endl;
        return 0;
    }

    int zsum = 0, osum = 0, ans = 0, Sum = 0;
    for(int i = 0; i < k; i++) zsum += z[i];
    for(int i = 0; i < k+1; i++) osum += o[i];
    for(int i = 0; i < o.size() - k - 1; i++){
        Sum = zsum + osum;
        ans = max(ans,Sum);
        zsum -= z[i];
        zsum += z[i+k];
        osum -= o[i];
        osum += o[i+k+1];
    }
    ans = max(ans,zsum + osum);
    cout << ans << endl;
}

Measured memory_bytes: 3932
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] count = new int[n];
        for (int i = 0; i < m; i++) {
            count[scanner.nextInt() - 1]++;
            count[scanner.nextInt() - 1]++;
        }
        for (int i = 0; i < n; i++) {
            if (count[i] % 2 == 1) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}

Measured memory_bytes: 64272
// +build ignore
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []byte {
	return []byte(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

func gcd(x, y int) int {
	if x%y != 0 {
		return gcd(y, x%y)
	}
	return y
}

func run(input io.Reader, output io.Writer) int {
	sc := NewScanner()
	a := sc.nextStr()
	b := sc.nextStr()

	if a == b {
		fmt.Println("H")
	} else {
		fmt.Println("D")
	}

	return 0
}

func main() {
	os.Exit(run(os.Stdin, os.Stdout))
}


Measured memory_bytes: 640
#include <iostream>
//#define max(a, b) a > b ? a : b //謎挙動
//#define min(a, b) a < b ? a : b

typedef unsigned long long ull;
using namespace std;

ull max(ull x, ull y) { return x > y ? x : y; };
ull min(ull x, ull y) { return x < y ? x : y; };

int main()
{
  int A, B, C;
  int X, Y;
  ull minVal = 1e10;

  cin >> A >> B >> C >> X >> Y;
  int Z = max(X, Y) * 2;

  for (int cId = 0; cId <= Z; cId += 2)
  {
    int aId = X - cId / 2;
    int bId = Y - cId / 2;
    if (aId < 0) aId = 0;
    if (bId < 0) bId = 0;
    
    ull sum = aId * A + bId * B + cId * C;

    minVal = min(minVal, sum);

  }

  cout << minVal << "\n";
}



Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      n: usize,
      a: usize,
      b: usize,
    }

    if a > b {
        return println!("{}", 0);
    }
    if n == 1 {
        if a == b {
            println!("{}", 1);
        } else {
            println!("{}", 0);
        }
        return;
    }
    let ans = (b-a)*(n-2) + 1;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

int main(){
    ll D, G;
    cin >> D >> G;
    G /= 100;
    vector<ll> p(D), c(D);
    VVL dp(D+10, VL(1010, 0));
    rep(i, 0, D){
        cin >> p[i] >> c[i];
        c[i] /= 100;
    }

    rep(i, 0, D){
        rep(k, 1, 1001){
            rep(j, 1, p[i]){
                if(k-j >= 0) dp[i+1][k] = max(dp[i][k], dp[i][k-j] + j*(i+1));
            }
            if(k-p[i] >= 0) dp[i+1][k] = max(dp[i][k], dp[i][k-p[i]] + p[i]*(i+1) + c[i]);
        }
    }
    ll ans = 1e18;
    rep(i, 0, 1001){
        if(dp[D][i] >= G) ans = min(ans, i);
    }
    cout << ans << endl;
    cerr << dp[D][ans] << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (ll)b; ++i)
#define digit(a) to_string(a).size()
#define INF 10e12
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
using namespace std;
int main(void)

{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(b / a, c) << endl;
}


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

// Problem https://atcoder.jp/contests/abc087/tasks/abc087_b

int solver(int fhundY,int hundY,int fiftyY,int total){
    int result=0;
    // 全パターン求める
    for(int j=0;j < fhundY+1;j++){
        for(int k=0;k < hundY+1;k++){
            for(int m=0; m < fiftyY+1 ; m++ ){
                int sum = j * 500 + k * 100 + m *50;
                if(sum==total) result=result+1;
            }
        }
    }
    return result;
}

int main(void){
    int A,B,C,X,answer;
    cin >> A >> B >> C >> X;
    answer = solver(A,B,C,X);
    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int P = 1e9 + 7;
inline int add(int a, int b) {if((a += b) >= P) a -= P; return a;}
inline int sub(int a, int b) {if((a -= b) < 0) a += P; return a;}
inline int mul(int a, int b) {return 1ll * a * b % P;}
inline int kpow(int a, int b) {int r=1;for(;b;b>>=1,a=mul(a,a)) {if(b&1)r=mul(r,a);}return r;}
//----
const int N = 101010;
int n, k;
int a[N];
int main(){
	scanf("%d%d", &n, &k);
	rep(i, 0, n) scanf("%d", a + i);
	int m;
	rep(i, 0, n) if(a[i] == 1) m = i;
	int le = m, ri = n - 1 - m;
	int mn = min(le, ri), mx = max(le, ri);
	int t = (mn + k - 2) / (k - 1);
	int ans = t + (mx - (t * (k - 1) - mn) + k - 2) / (k - 1);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
using namespace std;

class Union_Find_Size{
private:
    vector<int> par;
public:
    Union_Find_Size(int n){
        par=vector<int>(n,-1);
    }
    int find(int x){
        if(par.at(x)<0) return x;
        else return par.at(x)=find(par.at(x));
    }
    int size(int x){
        return -par.at(find(x));
    }
    void unite(int x, int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(size(x)<size(y)) swap(x,y);
        par.at(x)+=par.at(y);
        par.at(y)=x;
    }
};

signed main(){
    int n,m; cin>>n>>m;
    vector<int> a(m),b(m);
    rep(i,m){
        cin>>a.at(i)>>b.at(i);
        a.at(i)--; b.at(i)--;
    }
    Union_Find_Size UN(n);
    int size=n*(n-1)/2;
    reverse(all(a)); reverse(all(b));
    vector<int> ans(m);
    rep(i,m){
        ans.at(i)=size;
        if(UN.find(a.at(i))!=UN.find(b.at(i))){
            size-=UN.size(a.at(i))*UN.size(b.at(i));
            UN.unite(a.at(i),b.at(i));
        }
    }
    reverse(all(ans));
    rep(i,m){
        cout<<ans.at(i)<<endl;
    }
}

Measured memory_bytes: 4480
def main():
    n = int(input())
    txy = []
    for _ in range(n):
        txy.append(list(map(int,input().split())))
    
    x = 0
    y = 0
    pt = 0
    for t in txy:
        d = abs(t[1]-x) + abs(t[2]-y)
        dt = t[0]-pt
        if d > dt or (d % 2) != (dt % 2):
            print("No") 
            exit(0)
        x = t[1]
        y = t[2]
        pt = t[0]
    
    print("Yes")

if __name__ == '__main__':
    main()

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

int main()
{
  int p,q,r;
    cin>>p>>q>>r;
    int a,b,c;
    a=p+q;
    b=p+r;
    c=q+r;
    if(a<=b&&a<=c)
    {
        cout<<a;
    }
    else if(b<=a&&b<=c)
    {
        cout<<b;
    }
else
{
    cout<<c;
}

return 0  ;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int n,m;
char cmap[600][600];

bool can(int x1, int y1, int x2, int y2) {
    if(x1 > x2) swap(x1,x2), swap(y1,y2);

    int xd = x2-x1 ? (x2-x1)/abs(x2-x1) : 0;
    int yd = y2-y1 ? (y2-y1)/abs(y2-y1) : 0;

    if(xd == 0) {
        if(y1+yd==y2) return false;
        for(int y=y1+yd; y!=y2; y+=yd)
            if(cmap[y][x1] != '.')
                return false;
        return true;
    }

    if(yd == 0) {
        if(x1+1==x2) return false;
        for(int x=x1+1; x<x2; x++)
            if(cmap[y1][x] != '.')
                return false;
        return true;
    }

    for(int x=x1+1; x<=x2; x++)
        if(cmap[y1][x] != '.')
            goto next;
    for(int y=y1+yd; y!=y2; y+=yd)
        if(cmap[y][x2] != '.')
            goto next;
    return true;
next:
    for(int y=y1+yd; y!=y2; y+=yd)
        if(cmap[y][x1] != '.')
            return false;
    for(int x=x1; x<x2; x++)
        if(cmap[y2][x] != '.')
            return false;
    return true;
}

int main(void) {
    int map['Z'-'A'+1][2][2];
    memset(map, 0xFF, sizeof(map));

    scanf("%d%d",&m,&n);
    for(int i=0; i<m; i++) {
        scanf("%s",cmap[i]);
    }
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++) {
            if(cmap[j][i] == '.') continue;
            if(map[cmap[j][i]-'A'][0][0] == -1)
                map[cmap[j][i]-'A'][0][0] = i, map[cmap[j][i]-'A'][0][1] = j;
            else
                map[cmap[j][i]-'A'][1][0] = i, map[cmap[j][i]-'A'][1][1] = j;
        }

    int res=0;
    for(int i=0; i<100; i++)
        for(char c='A'; c<='Z'; c++) {
            if(map[c-'A'][0][0] == -1) continue;
            if(can(map[c-'A'][0][0], map[c-'A'][0][1], map[c-'A'][1][0], map[c-'A'][1][1])) {
                res+=2;
                cmap[map[c-'A'][0][1]][map[c-'A'][0][0]] = '.';
                cmap[map[c-'A'][1][1]][map[c-'A'][1][0]] = '.';
                map[c-'A'][0][0] = -1;
            }
        }
    printf("%d\n", res);

    return 0;
}

Measured memory_bytes: 3036
//Kaori Miyazono, did I reach you ?
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;              

const int maxn = 100;
vector<int> adj[maxn];
bool mark[maxn];
vector< pair<int, int> > edges;

void dfs(int v, int ini, int nop){
	mark[v] = 1;
	for(int u : adj[v]){
		if ( !mark[u] && (v != ini || u != nop)) dfs(u, ini, nop);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		edges.push_back(make_pair(a, b));
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int ans = 0;
	for(int i = 0; i < m; i++){
		memset(mark, 0, sizeof mark);
		dfs(edges[i].first, edges[i].first, edges[i].second);
		if ( !mark[edges[i].second] ) ans++;		
	}
	cout << ans;
	return 0;	
}    

Measured memory_bytes: 256
N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: a-1, As))))
  A.append(As)
#print(A)
d = 0
n = 0
l = list(range(N))
while True:
  n2 = 0
  l2 = []
  s2 = set()
  for i in l:
    if A[i] == []:
      continue
    j = A[i][-1]
    if A[j] == []:
      continue
    if i in s2 or j in s2:
      continue
    if A[j][-1] == i:
      n += 1
      n2 += 1
      s2.add(i)
      s2.add(j)
      l2.append(i)
      l2.append(j)
      A[i].pop()
      A[j].pop()
  if n2 == 0:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  l = l2
  d += 1
print(d)


Measured memory_bytes: 35548
n, x = map((x) -> parse(Int, x), split(readline(stdin), ' '))

longline = max(n-x, x)
shortline = min(n-x, x)
sum = n
while shortline != 0
    global sum += 2 * div(longline, shortline) * shortline
    tmp = longline
    global longline = shortline
    global shortline = tmp % shortline
    if shortline == 0
        sum -= longline
    end
end

println(sum)
    

Measured memory_bytes: 164824
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		long[]A = new long[str.Length];
		for(var i=0;i<str.Length;i++){
			A[i] = long.Parse(str.Substring(i,1));
		}
		long ans = 0;
		if(A[0] == 0){
			ans = -1;
		}
		if(A[str.Length-1] == 1){
			ans = -1;
		}
		if(str.Length % 2 == 0){
			for(var i=0;i<str.Length/2;i++){
				if(A[i] != A[str.Length-2-i]){
					ans = -1;
					break;
				}
			}
		} else {
			for(var i=0;i<(str.Length-1)/2;i++){
				if(A[i] != A[str.Length-2-i]){
					ans = -1;
					break;
				}
			}
		}
		if(ans == -1){
			Console.WriteLine(ans);
		} else {
			long act = 2;
			long[,] D = new long[str.Length-1,2];
			for(var i=0;i<str.Length-1;i++){
				D[i,0] = 1;
				D[i,1] = i+2;
			}
			var list = new List<long>();
			for(var i=(str.Length-2)/2;i>0;i--){
				if(A[i] == 1){
					list.Add(act);
				}
				act += 1;
			}
			long act2 = -1;
			while(list.Count > 0){
				act = list[0];
				if(list.Count > 1){
					act2 = list[1];
				} else {
					act2 = (str.Length-2)/2+2;
				}
				for(var j=act-1;j<act2-1;j++){
					D[j,0] = act;
				}
				list.RemoveAt(0);
			}
			for(var i=0;i<str.Length-1;i++){
				Console.WriteLine(D[i,0]+" "+D[i,1]);
			}
		}
	}
}

Measured memory_bytes: 18512
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}

template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int n;
	cin >> n;
	vector<int>a(n);
	rep(i, n) {
		cin >> a[i];
	}
	int ans = 0;
	int maxheight = a[0];
	rep1(i, n) {
		if (maxheight > a[i]) {
			ans += maxheight - a[i];
		}
		else {
			maxheight = a[i];
		}
	}
	print(ans);
}

Measured memory_bytes: 4768
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const ll mx = 1e5 + 5;

ll n, k, a[mx];
bool dp[mx];

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

	cin >> n >> k;
	memset(dp, -1, sizeof dp);
	for(ll i=0; i<n; i++)
	{
		cin >> a[i];
	}
	memset(dp, 1, sizeof dp);
	for(ll i=0; i<=k; i++)
	{
		for(ll j=0; j<n; j++)
		{
			if(i >= a[j])
			{
				if(dp[i-a[j]]==1)
					dp[i] = 0;
			}
		}
	}
	if(!dp[k])
		cout << "First\n";
	else
		cout << "Second\n";

	return 0;
}

Measured memory_bytes: 512
import math
n=int(input())
A = list(map(int, input().split()))
res=[0]*n
import collections
def com(n, r):
    if n<r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

af=collections.Counter(A)
res2=list(af.items())
res3=[0]*n
s=0
for i in range(0,len(res2)):
    s=s+com(res2[i][1],2)
for j in range(0,len(res2)):
    res3[res2[j][0]-1]=s-res2[j][1]+1
for i in range(n):
    res[i]=res3[A[i]-1]

for j in range(n):
    print(res[j])


Measured memory_bytes: 35248