akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

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

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}

int N;
string S;
int main(){
    cin >> N >> S;
    int count = 0;
    for(int i=0;i<N-2;i++){
        if(S[i]=='A' && S[i+1] == 'B'&&S[i+2]=='C'){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int Maxn = 1e5 + 5;
int main ()
{
	char x,y;
	scanf("%c %c",&x,&y);
	if (x > y) printf(">");
	else if (x < y) printf("<");
	else printf("=");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int a=(C+B-1)/B;
  int b=(A+D-1)/D;
  if(a<=b){
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

int main(){
    int k, x; cin >> k >> x;
    int left = x - k + 1;
    int right = x + k - 1;
    for(int i = left; i <= right; ++i){
        printf("%d%c", i, i==right?'\n':' ');
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define int long long

signed main() {
  int n;
  cin >> n;
  char s[n];
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == 'Y') {
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;
  return 0;
}


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

using namespace std;

long long count_balls(long long N, long long A, long long B) {
	return A * (N / (A + B)) + min(A, N % (A + B));
}

int main() {
	long long N, A, B;
	cin >> N >> A >> B;
	cout << count_balls(N, A, B);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	char ch;
	cin>>ch;
	if(ch=='A')
		cout<<'T'<<endl;
	if(ch=='T')
		cout<<'A'<<endl;
	if(ch=='G')	
		cout<<'C'<<endl;
	if(ch=='C')
		cout<<'G'<<endl;
	return 0;
} 

Measured memory_bytes: 256
q=int(input())
for _ in range(q):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a
  if a==b:
    print(2*a-2)
  elif a==b+1:
    print(2*a-1)
  else:
    c=int((a*b)**0.5)
    if c*c==a*b:
      c-=1
    if c*(c+1)>=a*b:
      print(2*c-2)
    else:
      print(2*c-1)

Measured memory_bytes: 3064
N,W,*L=map(int,open(0).read().split())
w1=L[0]
l=[[] for _ in range(4)]
for w,v in zip(*[iter(L)]*2):
	l[w-w1].append(v)
l=[sorted(t)[::-1] for t in l]
a,b,c,d=map(len,l)
ans=0
for h in range(a+1):
	for i in range(b+1):
		for j in range(c+1):
			for k in range(d+1):
				if w1*h+(w1+1)*i+(w1+2)*j+(w1+3)*k<=W:
					ans=max(ans,sum(l[0][:h]+l[1][:i]+l[2][:j]+l[3][:k]))
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define inf 0x6fffffff
using namespace std;
const int N=5e5+10;
const int MOD=1e9+7;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll a[N],sum[N],s0[N];
vector<int>ps[2100000];
bool vis[N];
int main()
{
    int n=read();
    ll s=0;
    for(int i=1;i<=n;i++)s^=(a[i]=read());
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]^a[i];
    for(int i=1;i<=n;i++)s0[i]=s0[i-1]+(sum[i]==0);
    if(s!=0)
    {
        ll s1=0,s2=0,pre=0;
        for(int i=1;i<=n;i++)
            if(sum[i]==s)
            {
                if(pre==0)s1=s2=1,pre=i;
                else{
                    ll l=s0[i]-s0[pre-1];
                    s2=(s2+l*s1%MOD)%MOD;
                    s1+=s2;
                    pre=i;
                }
            }
        cout<<s2%MOD<<endl;
    }
    else{
        ll ans=0;
        for(int i=1;i<=n;i++)ps[sum[i]].push_back(i);
        for(int i=1;i<=n;i++)
            if(!vis[i])
            {
                ll w=sum[i];
                if(w==0)continue;
                ll s1=0,s2=0,pre=0;
                //printf("%lld:",w);
                for(int j=0;j<ps[w].size();j++)
                {
                    int ii=ps[w][j];
                    vis[ii]=1;
                    if(pre==0)s1=s2=1,pre=ii;
                    else{
                        ll l=s0[ii]-s0[pre-1];
                        //printf(" /%d/",l);
                        s2=(s2+l*s1%MOD)%MOD;
                        s1+=s2;
                        pre=ii;
                    }
                    //printf(" %d",ii);
                }
                //puts("");
                //printf("%d\n",s1);
                ans=(ans+s1)%MOD;
            }
        ll tmp=1;
        for(int i=1;i<s0[n];i++)tmp=(tmp*2)%MOD;
        ans=(ans+tmp)%MOD;
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 71284
#include <bits/stdc++.h>
using namespace std;
int main () {
  string S, T = "";
  cin >> S;
  int front = 0, count = 0;;
  for(int i = 0; i < S.size(); i++){
    if(T != S.substr(front, i + 1 - front)){
      count++;
      T = S.substr(front, i + 1 - front);
      front = i + 1;
    }
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, m, diff;
map<int, int> ca;
int main() {
   cin >> n;
   for (int i=0; i<n; i++) {
       int x; cin >> x;
       ca[x]++;
   }
   
   cin >> m;
   while (m--) {
       cin >> diff;
       if (ca[diff]) {
           ca[diff]--;
       } else {
           cout << "NO"; return 0;
       }
   }
   cout << "YES";
}

Measured memory_bytes: 12972
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iterator>
#include<cstdio>
#include<cstdlib>

using namespace std;
#define ll long long

const int MAX = 5e5+10;

vector<int>adj[MAX],adj1[MAX],comp[MAX];

int col[MAX] , col1[MAX];
bool vis[MAX] , vis1[MAX];
int cur = 1;
int cnt[MAX] , ans[MAX];

void DFS(int src)
{
    col[src] = cur;
    vis[src] = 1;
    comp[cur].push_back(src);

    for(int j=0;j<adj[src].size();j++)
    {
        int i = adj[src][j];
        if(!vis[i])
            DFS(i);
    }
}
void DFS1(int src)
{
    col1[src] = cur;
    vis1[src] = 1;

    for(int j=0;j<adj1[src].size();j++)
    {
        int i = adj1[src][j];
        if(!vis1[i])
            DFS1(i);
    }
}

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

    int n,m1,m2;

    //memset(col,-1,sizeof col);
    //memset(col1,-1,sizeof col1);

    cin >> n >> m1 >> m2;

    int u,v;

    for(int i=0;i<m1;i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<m2;i++)
    {
        cin >> u >> v;
        adj1[u].push_back(v);
        adj1[v].push_back(u);
    }

    vector<int>compN;

    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            compN.push_back(cur);
            DFS(i);
            cur++;
        }
        if(!vis1[i])
        {
            DFS1(i);
            cur++;
        }
    }

    for(int z=0;z<compN.size();z++)
    {
        int i = compN[z];

        for(int j=0;j<comp[i].size();j++)
        {
            int x = comp[i][j];
            cnt[col1[x]]++;
        }
        for(int j=0;j<comp[i].size();j++)
        {
            int x = comp[i][j];
            ans[x] += cnt[col1[x]];
        }
        for(int j=0;j<comp[i].size();j++)
        {
            int x = comp[i][j];
            cnt[col1[x]]--;
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(i > 1)
            cout << " ";
        cout << ans[i];
    }
    cout << endl;
}


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

int main() {
	int K, S, n;
	scanf("%d%d", &K, &S);
	n = S < K ? S : K;
	int ans = 0;
	for(int i = 0; i <= n; i++) {
		int rem = S - i;
		if(rem <= K) ans += rem + 1;
		else if(rem <= 2 * K) ans += 2 * K - rem + 1;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
     
int main(){
     
  while(true) {
    int m, f, r;
    cin >> m >> f >> r;
    if (m == -1 && f == -1 && r == -1) break;
    if (m == -1 || f == -1) {
      cout << "F" << endl;
    }
    else if ((m + f) >= 80){
      cout << "A" << endl;
    }
    else if (65 <= (m + f) && (m + f) < 80){
      cout << "B" << endl;
    }
    else if (50 <= (m + f) && (m + f) < 65){
      cout << "C" << endl;
    }
    else if (30 <= (m + f) && (m + f) < 50){
      if (r >= 50) {
        cout << "C" << endl;
      }
      else {
        cout << "D" << endl;
      }
    }
    else {
      cout << "F" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1152
A, B = gets.chomp.split(" ").map(&:to_i)
W = 25

def calc(w, cnt, rev, neg)
  ret = []
  while w >= W do
    ret << '#.'*W
    ret << '##'*W
    w -= W
  end
  ret << '#.'*w + '##'*(W-w)
  ret << '##'*W
  ret.map!{|r| r.tr('#.', '.#')} if neg
  rev ? ret.reverse : ret
end

ans = []
if A > 1 && B > 1 then
  ans += calc(A-1, 1, false, false)
  ans += calc(B-1, 1, true, true)
elsif B == 1 then
  ans += calc(A, 1, false, false)
else
  ans += calc(B, 1, true, true)
end

puts [ans.size, 2*W]*?\s
puts ans


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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    int m = 1 << 28;
    for (int i = 0; i < n; i++) cin >> v[i], m = min(m, v[i]);
    for (int i = 1; i <= m; i++) {
        bool flag = true;
        for (int j = 0; flag && j < n; j++) if (v[j] % i > 0) flag = false;
        if (flag) cout << i << endl;
    }

    return 0;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5+5 , M = 1e3+5, OO = 0x3f3f3f3f;
typedef long long ll;
int n;
int main()
{
    cin >> n;
    if(n <= 9) cout << n << endl;
    else if(n < 100) cout << 9 << endl;
    else if(n <= 999) cout << n-100+10;
    else if(n < 10000) cout << 909 << endl;
    else if(n <= 99999) cout << n-10000+910;
    else cout << 90909 << endl;
	return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int main2() {
  string s; cin >> s;
  ll K; cin >> K;

  int trailingOne = 0;
  for (int i = 0; i < (int)s.size(); i++) {
    if (s[i] == '1') {
      trailingOne++;
    } else 
      break;
  }
  if (trailingOne >= K) {
    cout << 1 << endl;
  } else {
    cout << s[trailingOne] << endl;
  }
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define debug int debug = 0;
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define rrep(i,a,b) for(int i=a-1;i>=b;i--)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<int, Pi> V;
typedef vector<ll> VE;
const ll mod = 1e9 + 7; //10^9+7

int main(){
    string s, t;
    cin >> s >> t;
    bool f;

    RREP(i, s.size() - t.size() + 1){
        f = true;
        REP(j, t.size()){
            if(s[i + j] != t[j] && s[i + j] != '?'){
                f = false;
                break;
            }
        }
        if(!f)continue;
        REP(k, t.size())s[i + k] = t[k];
        REP(k, s.size())if(s[k] == '?')s[k] = 'a';
        REP(k, s.size())cout << s[k];
        return 0;
    }

    print("UNRESTORABLE");
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  long long mod = 1000000007;
  std::string S;
  std::cin >> S;
  std::vector<std::vector<long long > > dp(S.length()+1, std::vector<long long > (13, 0));
  dp[0][0] = 1;
  for (int i=1; i<=S.length(); i++){
    if (S[i-1]!='?'){
      int num = int(S[i-1])-int('0');
      for (int j=0; j<13; j++){
        dp[i][(j*10+num)%13]=dp[i-1][j];
      }
    } else {
      for (int j=0; j<13; j++){
        for (int k=0; k<10; k++){
          dp[i][(j*10+k)%13]+=dp[i-1][j];
          dp[i][(j*10+k)%13]%=mod;
        }
      }
    }
  }
  printf("%lld\n", dp[S.length()][5]);
  return 0;
}


Measured memory_bytes: 13632
n = int(input())
s = [input() for i in range(n)]

l = [0] * 4
sl = ['AC', 'WA', 'TLE', 'RE']
for i in s:
    if i == sl[0]:
        l[0] += 1
    elif i == sl[1]:
        l[1] += 1
    elif i == sl[2]:
        l[2] += 1
    else:
        l[3] += 1

for i in range(len(l)):
    print(sl[i] + ' x ' + str(l[i]))


Measured memory_bytes: 16276
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; --i)
#define FOR(i, n, m) for (int i = m; i < n; i++)
#define MM(i, n, m) for (int i = m; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

typedef long long ll;
/**
 * C問以降は ll を使う.
 * double型にするのを忘れない.
 * nC2の求め方 (1/2)*n*(n-1)
 * vector<型> 変数名(要素数, 初期値)
*/
#define MAX 10000
#define NIL -1
struct Node { int p, l, r; };
struct Node T[MAX];
int n;

void preParse(int u) {
    if (u==NIL) return;
    printf(" %d", u);
    preParse(T[u].l);
    preParse(T[u].r);
}

void inParse(int u) {
    if (u==NIL) return;
    inParse(T[u].l);
    printf(" %d", u);
    inParse(T[u].r);
}

void postParse(int u) {
    if (u==NIL) return;
    postParse(T[u].l);
    postParse(T[u].r);
    printf(" %d", u);
}

int main()
{
    int root;
    cin >> n;
    REP(i, n) T[i].p = NIL;
    REP(i, n) {
        int v, l, r;
        cin >> v >> l >> r;
        T[v].l = l;
        T[v].r = r;
        if (l != NIL) T[l].p = v;
        if (r != NIL) T[r].p = v;
    }
    REP(i, n) if(T[i].p == NIL) root = i;
    cout << "Preorder" << endl;
    preParse(root);
    cout << endl;
    cout << "Inorder" << endl;
    inParse(root);
    cout << endl;
    cout << "Postorder" << endl;
    postParse(root);
    cout << endl;
    return 0;
}


Measured memory_bytes: 3200
import numpy as np

def main():
    with open(0) as f:
        N = int(f.readline())
        F = np.array([list(map(int, f.readline().split())) for _ in range(N)])
        P = [list(map(int, f.readline().split())) for _ in range(N)]

    max_profit = -np.inf
    for i in range(1,2**10):
        Open = np.array([(i>>j)&1 for j in range(10)])
        conflict = np.dot(F, Open.T)
        profit = sum(P[i][v] for i,v in enumerate(conflict))
        max_profit = max(max_profit, profit)
    print(max_profit)

main()

Measured memory_bytes: 26932
lis=input().split(' ')
N=int(lis[0])
L=int(lis[1])
sum=int((2*L+N-1)*N*0.5)
if(L<0 and N+L-1<0):
  print(sum-(N+L-1))
elif(L>0 and N+L-1>0):
  print(sum-L)
else:
  print(sum)

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

int main() {
  int n;
  cin>>n;
  long ans = 0;
  for (long i=1; i<1e5; i++) {
    if (i * i <= n) {
      ans = i * i;
    } else {
      break;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N,M = gets.split.map(&:to_i)
A = N.times.map { gets.chomp }
B = M.times.map { gets.chomp }

(N-M+1).times do |i|
  (N-M+1).times do |j|
    if M.times.all? { |m| B[m] == A[i+m][((i+j)..(M-1+i+j))] }
      puts 'Yes'
      exit
    end
  end
end
# ここまで来たら不一致
puts 'No'

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

int main()
{
	int n;
	cin >> n;
	
	float point[4][2];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 2; k++) {
				cin >> point[j][k];
			}
		}

		if ((point[1][1] - point[0][1]) / (point[1][0] - point[0][0]) == (point[3][1] - point[2][1]) / (point[3][0] - point[2][0]))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 3132
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1000000000
#define ll long long
using namespace std;
int main()
{
    int a, b, c, d, ans = 0;
    cin >> a >> b >> c >> d;
    if (a != c && b != (d + 1))
        ans = 1;
    else
        ans = 0;
    cout << ans << "\n";
}


Measured memory_bytes: 256
package main

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

// algorithm: bfs
func main() {
	n, m := readInt(), readInt()

	mat := make([][]int, n)
	for i := 0; i < m; i++ {
		a, b := readInt()-1, readInt()-1
		mat[a] = append(mat[a], b)
		mat[b] = append(mat[b], a)
	}

	q := make([]int, 0, n)
	q = append(q, 0)
	ans := make([]int, n)
	ans[0] = -1
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		for _, next := range mat[cur] {
			if ans[next] != 0 {
				continue
			}
			ans[next] = cur + 1
			q = append(q, next)
		}
	}

	fmt.Println("Yes")
	for i := range ans[1:] {
		fmt.Println(ans[i+1])
	}
}

func main0() {
	n, m := readInt(), readInt()

	mat := make(map[int][]int)
	for i := 0; i < m; i++ {
		a, b := readInt(), readInt()
		if _, ok := mat[a]; !ok {
			mat[a] = make([]int, 0)
		}
		mat[a] = append(mat[a], b)
		if _, ok := mat[b]; !ok {
			mat[b] = make([]int, 0)
		}
		mat[b] = append(mat[b], a)
	}

	nexts := make([]move, len(mat[1]))
	for i := range mat[1] {
		nexts[i] = move{mat[1][i], 1}
	}

	visited := map[int]bool{1: true}
	ans := make([]int, n)
	for len(nexts) > 0 && len(visited) < n {
		tmpNexts := make([]move, 0)
		// fmt.Println(nexts)
		for i := range nexts {
			if visited[nexts[i].cur] {
				continue
			}
			visited[nexts[i].cur] = true

			ans[nexts[i].cur-1] = nexts[i].pre

			if _, ok := mat[nexts[i].cur]; !ok {
				continue
			}
			for j := range mat[nexts[i].cur] {
				tmpNexts = append(tmpNexts, move{mat[nexts[i].cur][j], nexts[i].cur})
			}
		}
		nexts = tmpNexts
	}

	fmt.Println("Yes")
	for i := range ans[1:] {
		fmt.Println(ans[i+1])
	}
}

type move struct {
	cur int
	pre int
}

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	log.SetFlags(log.Lshortfile)
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readInt() int {
	return int(readInt64())
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcd(m, n int) int {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcm(m, n int) int {
	return m / gcd(m, n) * n
}


Measured memory_bytes: 16044
using System;
using System.Collections.Generic;

namespace AtCoder_CSharp
{
    class AtCoder
    {
        static void Main(string[] args)
        {
            string S;

            S = Console.ReadLine();

            int Slength = S.Length;
            int circlecount = S.Length - S.Replace("o", "").Length;

            if (15 - Slength + circlecount >= 8)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }

    }
}


Measured memory_bytes: 11092
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			
			int h = sc.nextInt();
			int w = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			int val = 0;
			
			StringBuilder sb = new StringBuilder();
			
			for (int i = 0; i < h; i++) {
				
				for (int j = 0; j < w; j++) {
					
					if (i < b) {
					
						if ( j < a) {
							val = 0;
						}else {
							val = 1;
						}
						
						sb.append(val);
					
					
					
					}else if (i >= b) {
						
						if ( j < a) {
							val = 1;
						}else {
							val = 0;
						}
						sb.append(val);
					}
				}
				sb.append("\n");
			}
			
			System.out.println(sb);
		}
	}
}


Measured memory_bytes: 29640
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"sort"
	"strconv"
)

// const abcd = "abcdefghijklmnopqrstuvwxyz"
// const ABCD = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
var dr = [...]int{0, 1, 1, 1, 0, -1, -1, -1, 0}
var dc = [...]int{1, 1, 0, -1, -1, -1, 0, 1, 0}

func main() {
	log.SetFlags(log.Lshortfile)
	nextReader = NewScanner()
	N := nextInt()
	X := nextInt()
	x := nextInts(N)
	x = append(x, X)
	sort.Ints(x)
	var m int
	var g int
	for i := 1; i < N+1; i++ {
		m = x[i] - x[i-1]
		if g == 0 {
			g = m
		} else {
			g = gcd(g, m)
		}
	}
	fmt.Println(g)
}

func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func lcm(a, b int) int {
	return a * b / gcd(a, b)
}

func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func minmax(a, b int) (int, int) {
	if a > b {
		return b, a
	}
	return a, b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

var nextReader func() string

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}
func nextString() string {
	return nextReader()
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(nextReader(), 64)
	return f
}


Measured memory_bytes: 3968
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        long ans = 0;
        for(int i=1;i<n;i++) {
            ans += a[n-1-i/2];
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 49920
#include <stdio.h>

int main() {
	int n, ans = 0;
	scanf("%d", &n);
	char str[n + 1];
	scanf("%s", str);
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < 10; k++) {
				int idx = 0;
				for (int l = 0; l < n; l++) {
					int pos[] = {i, j, k};
					if (str[l] - '0' == pos[idx]) {
						idx++;
					}
					if (idx == 3) {
						ans++;
						break;
					}
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1724
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

template<typename T>
vector <T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e:t) fill_v(e, v);
}

typedef pair<int, int> P;

class CFiveTransportations {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int N, A, B, C, D, E;
        cin >> N >> A >> B >> C >> D >> E;
        int m = min({A, B, C, D, E});

        if (m >= N) {
            cout << 5 << endl;
            return;
        }
        N -= m;

        int res = 5 + (N / m);
        if (N % m != 0) res++;
        cout << res << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    CFiveTransportations solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
# include<cstdio>
# include<cmath>

int main() {
    double a, b, C;
    double S, L, h;
    double PI = acos(-1);
    scanf("%lf %lf %lf", &a, &b, &C);
    double rad = C*PI/180;
    S = a*b*sin(rad)/2;
    L = a + b + sqrt(a*a+b*b-2*a*b*cos(rad));
    h = 2*S/a;
    printf("%lf\n%lf\n%lf\n", S, L, h);
    return 0;
}


Measured memory_bytes: 2920
N,M=map(int,input().split())
L=[[]for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)

P=[-1 for i in range(N+1)]
P[1]=1
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(10**7):
    if i==len(Q):
        break
    q1,q2=Q[i]
    if P[q1]!=(-1):
        continue
    else:
        P[q1]=q2
        for j in L[q1]:
            if P[j]==(-1):
                Q.append([j,q1])
#print(P)
print("Yes")
for i in range(2,len(P)):
    print(P[i])

Measured memory_bytes: 118336
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    int n;
    long long ans = 0,ans2 = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i++) cin >> a[i];
    sort(a.begin(), a.end());
    if(n %2 == 0){
        for(int i = n-1;i >= (n/2)+1;i--){
            ans += 2*a[i];
        }
        for(int i = 0;i < (n/2)-1;i++){
            ans -= 2*a[i];
        }
        ans += a[n/2];
        ans -= a[n/2-1];
    }else{
        for(int i = n-1;i >= (n/2)+1;i--){
            ans += 2*a[i];
        }
        for(int i = 0;i <= (n/2)-2;i++){
            ans -= 2*a[i];
        }
        ans -= a[n/2];
        ans -= a[n/2-1];
        
        for(int i = n-1;i >= (n/2)+2;i--){
            ans2 += 2*a[i];
        }
        for(int i = 0;i <= (n/2)-1;i++){
            ans2 -= 2*a[i];
        }
        ans2 += a[n/2+1];
        ans2 += a[n/2];
        ans = max(ans,ans2);
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const ll INF = 1e9;
inline ll read(){
	ll X = 0,w = 0 ;
	char ch = 0;
	while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
	while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();
	return w ? -X : X;
}
ll n,m;
ll dc[1000005],dr[1000005];
ll r,c,pot;
ll ans=1;
ll mod=1e9+7;
int main()
{
	cin>>n>>m;
	for(ll i=1,x;i<=n;i++)
	{
		cin>>x;
		if(dr[x])
		{
			cout<<0<<endl;
			return 0;
		}
		dr[x]=1;
	}
	for(ll i=1,x;i<=m;i++)
	{
		cin>>x;
		if(dc[x])
		{
			cout<<0<<endl;
			return 0;
		}
		dc[x]=1;
	}
	for(ll i=n*m;i;i--)
	{
		if(dc[i] and dr[i])
		{
			pot+=c+r;
			c++;r++;
		}
		else if(dc[i])
		{
			if(!r)
			{
				cout<<0<<endl;
				return 0;
			}
			(ans*=r)%=mod;
			pot+=r-1;
			c++;
		}
		else if(dr[i])
		{
			if(!c)
			{
				cout<<0<<endl;
				return 0;
			}
			(ans*=c)%=mod;
			pot+=c-1;
			r++;
		}
		else
		{
			if(!pot)
			{
				cout<<0<<endl;
				return 0;
			}
			(ans*=pot)%=mod;
			pot--;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  cin >> s >> t;
  bool b=false;
  for(int i=0;i<s.size();i++){
    if(s==t){
      b=true;
      break;
    }
    else {
      s=s.back()+s.substr(0,s.size()-1);
    }
  }
  if(b){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int color[9];
int main()
{
    int n;
    int ct = 0;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        color[min(x/400,8)]++;
    }
    for (int i = 0; i<8; i++)
        ct += (color[i]>=1);
    printf("%d %d",max(1,ct),ct+(color[8]));
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	D, N = map(int, input().split(" "))
	
	tmp = str(N)
	if D == 0 and tmp == "100":
		tmp = "101"
	if D == 1:
		if tmp != "100":
			tmp = tmp + "00"
		else:
			tmp = "10100"
	if D == 2:
		if tmp != "100":
			tmp = tmp + "0000"
		else:
			tmp = "1010000"
	
	print(tmp)
	
	
if __name__ == "__main__":
	main()


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

typedef long long ll;
using namespace std;

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

	int n; cin >> n;

	int t[100][3][2];

	vector<int> lt[3];

	int h,m;
	for (int i = 0;i < n;i++){
		for (int j = 0;j < 3;j++){
			for (int k = 0;k < 2;k++){
				cin >> h >> m;
				t[i][j][k] = h*100+m;
				lt[j].push_back(t[i][j][k]);
			}
		}
	}

	int ans = -1;

	for (int i = 0;i < lt[0].size();i++){
		for (int j = 0;j < lt[1].size();j++){
			for (int k = 0;k <lt[2].size();k++){
				int cnt = 0;
				for (int l = 0;l < n;l++){
					if(t[l][0][0] <= lt[0][i] && lt[0][i] <= t[l][0][1] &&
					   t[l][1][0] <= lt[1][j] && lt[1][j] <= t[l][1][1] &&
					   t[l][2][0] <= lt[2][k] && lt[2][k] <= t[l][2][1]) cnt++;
				}
				ans = max(cnt,ans);
			}
		}
	}

	cout << ans << endl;

	return 0;

}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s[k - 1] += 'a' - 'A';
    cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,n) for(ll i=0;i<n;i++)
#define nforn(i,n) for(ll i=n-1;i>=0;i--)
#define forne(i,n) for(ll i=1;i<=n;i++)
#define forse(i,s,e) for(ll i=s;i<e;i++)
#define all(v) v.begin(),v.end()
#define MOD 1000000007
#define d1(x) cerr <<"> "<<#x<<" = "<<x<<'\n'
#define d2(x, y) cerr <<"> "<<#x<<" = "<<x<<' '<<#y<<" = "<<y<<'\n'
#define d3(x, y, z) cerr <<"> "<<#x<<" = "<<x<<' '<<#y<<" = "<<y<<' '<<#z<<" = "<<z<<'\n'
ll a[1005],b[1005];
ll dp[10005][1005];
ll filldp(ll index,ll power){
	// d2(power,index);
	if(power<=0) return 0;
	if(index<0) return ll(1e12);
	if(dp[power][index]!=-1) return dp[power][index];
	return dp[power][index] = min(filldp(index-1,power),b[index] + filldp(index,power-a[index]));
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t = 1;
	memset(dp,-1,sizeof dp);
	// cin>>t;
	while(t--){
		ll h,n;
		cin>>h>>n;
		forn(i,n){
			cin>>a[i]>>b[i];
		}
		cout<<filldp(n-1,h)<<"\n";
	}
}

Measured memory_bytes: 79232
#include <cmath>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define REP(i,n) for(int i = 0; i < n; i++)

int main(void)
{
    char b;
    cin >> b;
    switch(b)
    {
        case 'A':
            cout << 'T' << endl;
            break;
        case 'T':
            cout << 'A' << endl;
            break;
        case 'G':
            cout << 'C' << endl;
            break;
        case 'C':
            cout << 'G' << endl;
            break;
    }
    
    return 0;
}

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

#define int long long
#define fi first
#define se second
#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 repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807

string s;

signed main() {
    cin >> s;
    if (s.size()==2 && s[0]==s[1]) {cout << 1 << " " << 2 << endl;return 0;}
    rep(i,s.size()-2) {
        map<char,int> m;
        rep(j,3) m[s[i+j]]++;
        for(auto j : m) if (j.se > 1) {cout << i+1 << " " << i+3 << endl;return 0;}
    }
    cout << -1 << " " << -1 << endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
#define INF (1ULL<<20)
using namespace std;

int dp[1001][1001];

int main()
{
	fill(dp[0], dp[1000],INF);
	string s1, s2;
	cin >> s1 >> s2;
	int s1size = s1.size(), s2size = s2.size();
	for (int i = 0; i < s1size + 1; ++i) {
		for (int j = 0; j < s2size + 1; ++j) {
			if (j == 0) {
				dp[i][0] = i;
				continue;
			}
			if (i == 0) {
				dp[0][j] = j;
				continue;
			}
			dp[i][j] = min(min(dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]), dp[i][j - 1] + 1), dp[i - 1][j] + 1);
		}
	}
	cout << dp[s1size][s2size] << endl;
}

Measured memory_bytes: 5096
#!/usr/bin/env python3
import sys
 
 
def solve(N: int, H: "List[int]"):
    longest = 0
    current = 0
    for i in range(N-1):
        if H[i] >= H[i+1]:
            current += 1
        else:
            if current > longest:
                longest = current
            current = 0
    if current > longest:
        longest = current
    print(longest)
    return
 
 
# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, H)
 
if __name__ == '__main__':
    main()

Measured memory_bytes: 15384
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#include <list>
#include <utility>
#include <memory>
#include <cstring>
#include <fstream>
#include <numeric>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
int N,h[100004],c[100004];
int main(){
	cin>>N;
	for (int i=0;i<N;i++) cin>>h[i];
	c[0]=0;
	c[1]=abs(h[1]-h[0]);
	for (int i=2;i<N;i++){
		c[i]=min(c[i-1]+abs(h[i]-h[i-1]),c[i-2]+abs(h[i]-h[i-2]));
	}
	cout<<c[N-1];
}

Measured memory_bytes: 1024
#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,K,Q,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

int main() {
    cin>>N>>K;
    vector<string> s(N);
    rep(i,N) cin>>s[i];
    sort(ALL(s));
    rep(i,N) cout<<s[i];
    cout<<endl;
}

Measured memory_bytes: 256
a,b,c = map(int, input().split())
d,e,f = map(int, input().split())
g,h,i = map(int, input().split())
aa = 0
bb = 0
cc = 0
dd = 0
ee = 0
ff = 0
gg = 0
hh = 0
ii = 0

j = int(input())

for k in range(j):
  l = int(input())
  if a == l:
    aa = 1
  elif b == l:
    bb = 1
  elif c == l:
    cc = 1
  elif d == l:
    dd = 1
  elif e == l:
    ee = 1
  elif f == l:
    ff = 1
  elif g == l:
    gg = 1
  elif h == l:
    hh = 1
  elif i == l:
    ii = 1
if aa == 1 and bb == 1 and cc == 1:
  print('Yes')
elif dd == 1 and ee == 1 and ff == 1:
  print('Yes')
elif gg == 1 and hh == 1 and ii == 1:
  print('Yes')
elif aa == 1 and dd == 1 and gg == 1:
  print('Yes')
elif bb == 1 and ee == 1 and hh == 1:
  print('Yes')
elif cc == 1 and ff == 1 and ii == 1:
  print('Yes')
elif aa == 1 and ee == 1 and ii == 1:
  print('Yes')
elif cc == 1 and ee == 1 and gg == 1:
  print('Yes')
else:
  print('No')

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

#define ll long long 
#define d  double 
#define endl "\n"

const ll int MOD=1e9+7;

void solve()
{
	ll n,i,j,flag,ans=0;
	cin >> n;
	vector<ll> v(n),cnt((int)1e6+1,0);
	for(i=0;i<n;i++)
	{
		cin >> v[i];
		cnt[v[i]]++;
	}
	for(i=0;i<n;i++)
	{
		flag=1;
		if(cnt[v[i]]>1)
			continue;

		for(j=1;j*j<=v[i];j++)
		{
			if(v[i]%j==0)
			{
				if(cnt[j] or cnt[v[i]/j])
					flag=0;

				if(j==1 and cnt[1]==0)
					flag=1;
			}

		}
		ans += flag;
		if(cnt[1]==1)
			ans=1;
	}
	cout << ans << endl;
}

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

	solve();
	return 0;
}

Measured memory_bytes: 12644
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static class State{
		int x,y, cost;
		State(int x,int y, int cost){
			this.x=x;
			this.y=y;
			this.cost=cost;
		}
	}
	
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			while(sc.hasNext()) {
				int w=sc.nextInt();
				int h=sc.nextInt();
				if(w+h==0) break;
				int xs=sc.nextInt();
				int ys=sc.nextInt();
				int xg=sc.nextInt();
				int yg=sc.nextInt();
				int n=sc.nextInt();
				int[][] field=new int[h+1][w+1];
				int color=0;
				while(n-->0) {
					int c=sc.nextInt();
					int d=sc.nextInt();
					int x=sc.nextInt();
					int y=sc.nextInt();
					if(d==0) {
						for(int i=0; i<2; i++) {
							for(int j=0; j<4; j++) {
								field[y+i][x+j]=c;
								if(y+i==ys && x+j==xs) color=c;
							}
						}
					}else {
						for(int i=0; i<4; i++) {
							for(int j=0; j<2; j++) {
								field[y+i][x+j]=c;
								if(y+i==ys && x+j==xs) color=c;
							}
						}
					}
				}
				Queue<State> q=new LinkedList<>();
				int[][] minstep=new int[h+1][w+1];
				int INF=100000000;
				int[] dx= {1, 0, -1, 0};
				int[] dy= {0, 1, 0, -1};
				for(int i=1; i<=h; i++) {
					for(int j=1; j<=w; j++) {
						minstep[i][j]=INF;
					}
				}
				q.add(new State(xs, ys, 0));
				while(!q.isEmpty()) {
					State state=q.poll();
					if(minstep[state.y][state.x]<INF) continue;
					minstep[state.y][state.x]=state.cost;
					if(state.x==xg&&state.y==yg) break;
					for(int i=0; i<4; i++) {
						if(state.x+dx[i]<1 || state.x+dx[i]>w || state.y+dy[i]<1 || state.y+dy[i]>h) {
							continue;
						}
						if(field[state.y+dy[i]][state.x+dx[i]]==color) {
							q.add(new State(state.x+dx[i], state.y+dy[i], state.cost+1));
						}
					}
				}
				System.out.println(minstep[yg][xg]==INF? "NG":"OK");
				q.clear();
			}
		}

	}
}


Measured memory_bytes: 33984
N = gets.to_i
array = gets.split.map(&:to_i)

flag = true
count = 0

while flag
  flag = false

  (N - 1).downto(1) do |j|
    if array[j] < array[j - 1]
      array[j], array[j - 1] = array[j - 1], array[j]
      flag = true
      count += 1
    end
  end
end

puts array.join(' ')
puts count

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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k, x;
	cin >> n >> k;

	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		cin >> x;
		ans += min(abs(0-x), abs(k-x))*2;
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;
  if (S == "abc" || S == "acb" || S == "bac" || S == "bca" || S == "cab" || S == "cba") {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M = 1e8 + 100;
typedef long long ll;
pair<ll ,ll > a[M];
bool cmp(pair<ll ,ll> x,pair<ll ,ll> y){
	if(x.first!=y.first)
		return x.first<y.first;
	else if(x.second!=y.second)
		return x.second>y.second;
	else return x<y;
}
int main(){
	ll n,m;
	cin>>n>>m;
	for(ll i = 0 ; i < n; i++){
		cin>>a[i].first>>a[i].second;
	}
	sort(a,a+n,cmp);
//	for(ll i = 0 ; i < n; i++){
//		cout<<a[i].first<<a[i].second<<endl;
//	}
	long long sum = 0;
	ll st = 0;
	while(m>0 && st<n){
		if(a[st].second<=m){
			sum+=a[st].first*a[st].second;
			m-=a[st].second ;
			st++;
		}
		else{
			sum+=a[st++].first*m;
			m = 0;
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int main(void){
	int d;
	cout << "Christmas";
	cin >> d;
	while(d<25){
		++d;
		cout << " Eve";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
answ=[]
ansh=[]
for i in range(h):
  if not all([a=="." for a in A[i]]):
    answ.append(i)
for j in range(w):
  if not all([A[i][j]=="." for i in range(h)]):
    ansh.append(j)
for i in answ:
  for j in ansh:
    print(A[i][j],end="")
  print("\n")
    

Measured memory_bytes: 9296
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>


#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

using namespace std;

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

int main()   {
    cout.precision(17);
    ll modd = 1000 * 1000 * 1000 + 7;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no
    ll infinit = 10000000000000000;


//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readll(n);
        vector<ll> a;
        forr(i,0,n) {
            readint(kk); a.push_back(kk);
        }
        vector<ll> part_sum_even; part_sum_even.push_back(0);
        vector<ll> part_sum_odd; part_sum_odd.push_back(0);

        forr(i,0,a.size()) {
            ll ev = 0, od = 0;
            if (i%2==0) {ev=a[i];} else {od=a[i];}
            part_sum_even.push_back(part_sum_even.back() + ev);
            part_sum_odd.push_back(part_sum_odd.back() + od);
        }
        
        ll ret;
        if (n%2!=0) {
            ret = part_sum_odd.back();
            for(int i = 0; i < n-1; i+=2) {
                ret = max(ret, part_sum_even[i+1] + part_sum_odd.back() - part_sum_odd[i+3]);
            }
            for (int i = 1; i < n-2; i+=2) {
                ret = max(ret, part_sum_odd[i+1] + part_sum_even.back() - part_sum_even[i+3]);
            }
            ll min_total = a[0], min_local = a[0];
            for(int i = 2; i < n; i+=2) {
                min_local = min(a[i], a[i]-a[i-1]+min_local);
                min_total = min(min_total, min_local);
            }
            ret = max(ret, part_sum_even.back() - min_total);
        } else {
            ret = max(part_sum_even.back(), part_sum_odd.back());
            for(int i = 0; i < n-2; i+=2) {
                ret = max(ret, part_sum_even[i+1] + part_sum_odd.back() - part_sum_odd[i+3]);
            }
        }
        
        cout << ret << endl;
    }
    return 0;
}


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

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



Measured memory_bytes: 3104
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int res = mod;
    for (int i = 1; i * i <= n;i++){
        if(n%i==0){
            string s = to_string(i);
            string t = to_string(n / i);
            int a = max(s.size(), t.size());
            res = min(res, a);
        }
    }
    cout << res << endl;
}

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

int main() {

    char c;
    cin >> c;
    if (c == 'a') {
        cout << "vowel" << endl;
    }
    else if (c == 'i') {
        cout << "vowel" << endl;
    }
    else if (c == 'u') {
        cout << "vowel" << endl;
    }
    else if (c == 'e') {
        cout << "vowel" << endl;
    }
    else if (c == 'o') {
        cout << "vowel" << endl;
    }
    else {
        cout << "consonant" << endl;
    }

}


Measured memory_bytes: 256