akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

#include <tuple>
#include <queue>
using Info = tuple<ll, int, int, int, int>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int w, h;
    while (cin >> w >> h, w + h) {
        auto mp = make_v(h + 2, w + 2, 1);
        int sx, sy, ox, oy;
        REP(i, 1, h + 1) {
            REP(j, 1, w + 1) {
                cin >> mp[i][j];
                if (mp[i][j] == 4) {
                    sx = j;
                    sy = i;
                }
                if (mp[i][j] == 2) {
                    ox = j;
                    oy = i;
                }
            }
        }
        const int dx[4] = {0, -1, 0, 1};
        const int dy[4] = {1, 0, -1, 0};
        const ll inf = 1LL << 60;
        auto Cost = make_v(w + 2, h + 2, w + 2, h + 2, inf);
        priority_queue<Info, vector<Info>, greater<Info>> pq;
        pq.emplace(0, sx, sy, ox, oy);
        ll ans = -1;
        while (pq.size()) {
            ll cost;
            tie(cost, sx, sy, ox, oy) = pq.top();
            pq.pop();
            if (Cost[sx][sy][ox][oy] < cost) continue;
            Cost[sx][sy][ox][oy] = cost;
            //dump(cost, sx, sy, ox, oy);
            if (mp[oy][ox] == 3) {
                ans = cost;
                break;
            }
            if (abs(sx - ox) + abs(sy - oy) == 1) {
                int xdiff = ox - sx, ydiff = oy - sy;
                int nx = ox + xdiff, ny = oy + ydiff;
                if (mp[ny][nx] != 1) {
                    if (chmin(Cost[sx][sy][nx][ny], cost + 1)) {
                        pq.emplace(cost + 1, sx, sy, nx, ny);
                    }
                }
            }
            REP(k, 0, 4) {
                int nx = sx + dx[k], ny = sy + dy[k];
                if ((nx == ox && ny == oy) || (mp[ny][nx] == 1)) continue;
                if (chmin(Cost[nx][ny][ox][oy], cost)) {
                    pq.emplace(cost, nx, ny, ox, oy);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3236
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int x = sc.nextInt();
        if(k * 500 >= x){
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }


    }
}


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

#define ll long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define rep(i,l,r) for(int i = l;i<r;i++)

#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()

#define fastout  ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

const int INF = (int)1e9 + 7;
const long long LLINF = (long long)1e18 + 7;

void kekek()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    #ifdef EBUCHKA
        freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
    #endif
}

int main() {
	kekek();
	int n, k;
	cin >> n >> k;
	vector<int> h(n);
	vector<int> dp(n);
	if (n == 1) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		dp[i] = INF;
		for (int j = 1; j <= min(i, k); j++){
			dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
		}
	}
	cout << dp[n - 1];
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

int main(){
	ll N;
	cin >> N;
	vector<ll> count(5, 0);
	REP(i, N){
		string S;
		cin >> S;
		if(S[0]=='M') count[0]++;
		if(S[0]=='A') count[1]++;
		if(S[0]=='R') count[2]++;
		if(S[0]=='C') count[3]++;
		if(S[0]=='H') count[4]++;
	}
	ll res = 0;
	REP(mask, 1<<5){
		ll tmp = 0;
		REP(i, 5){
			tmp += (mask>>i & 1);
		}
		ll tmp2 = 1;
		if(tmp==3){
			REP(i, 5){
				if(mask>>i & 1){
					tmp2 *= count[i];
				}
			}
			res += tmp2;
		}
	}
	cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef complex < double > P;
typedef pair< P, P> L;
const double EPS = 1e-10;
const double INF = 1e8;
double cross( P a,  P b){ //OK
  return imag( conj(a) * b);
}
double dot( P a, P b){ //OK
  return real( conj(a) * b);
}
int ccw( P a, P b, P c){  //OK
  b -= a, c -= a;
  if(cross(b,c) > 0)    return +1;  // a → b で 反時計方向におれて c
  if(cross(b,c) < 0)    return -1; // a → b で 時計方向におれて c
  if(dot(b,c) < 0)      return +2;  // c -- a -- b
  if(norm(b) < norm(c)) return -2; // a -- b -- c
                        return 0;  // a -- c -- b
}
P projection( L l, P p) { //OK
  double t = dot( p - l.fr, l.fr - l.sc) / norm( l.fr - l.sc);
  return l.fr + t * ( l.fr - l.sc);
}
bool intersect( L a, P p){ //OK
   return abs( a.fr - p) + abs( a.sc - p) - abs( a.fr - a.sc) < EPS;
}
bool intersect( L a, L b){ //OK
  return ccw( a.fr, a.sc, b.fr) * ccw( a.fr, a.sc, b.sc) <= 0 &&
    ccw( b.fr, b.sc, a.fr) * ccw( b.fr, b.sc, a.sc) <= 0;
}
double distance( L s, P p){ //OK
  P r = projection(s, p);
  if ( intersect( s, r)) return abs( r - p);
  return min( abs( s.fr - p), abs( s.sc - p));
}
double distancion( L a, L b){ //OK
  if(intersect( a, b)) return 0;
  return min( min( distance( a, b.fr), distance( a, b.sc)),
              min( distance( b, a.fr), distance( b, a.sc)));
}
double Degree_to_Radian(double n){
  return n * M_PI / 180.0;
}
double Radian_to_Degree(double n){
  return n * 180.0 / M_PI;
}
/* ここまでテンプレート */

  int table[][5] = {{0,0,1,1,2},{2,3,3,4,4}};

void add( L* stars,double x, double y, double a, double r){
  P hosi[5];
  for(int i = 0 ; i < 5 ; i++ ){
    double theta = Degree_to_Radian(a + 72 * i);
    double nx = r * sin( theta ), ny = r * cos( theta );
    hosi[i] = P( x - nx, y + ny);
  }
  for(int i = 0 ; i < 5 ; i++ ){
    stars[i] = L( hosi[table[0][i]], hosi[table[1][i]]);
  }
}
int main(){ //vectorが重いかも
  double info[100][100];
  int n, m, l;
  L stars[100][5];
  while(scanf("%d%d%d", &n, &m, &l), n|m|l){
    m--, l--;
    for(int i = 0 ; i < n ; i++ ){
      double x, y, a, r;
      scanf("%lf%lf%lf%lf", &x, &y, &a, &r);
      add( stars[i], x, y, a, r);
    }
    for(int i = 0 ; i < n ; i++ ){
      for(int j = i + 1 ; j < n ; j++ ){
        double dist = INF;
        for(int a = 0 ; a < 5 ; a++ ){
          for(int b = 0 ; b < 5 ; b++ ){
            dist = min( dist, distancion( stars[i][a], stars[j][b]));
          }
        }
        info[i][j] = info[j][i] = dist;
      }
    }
    for(int k = 0; k < n; k++ ){
      for(int i = 0; i < n; i++ ){
        for(int j = 0; j < n; j++ ){
          info[i][j] = min( info[i][j], info[i][k] + info[k][j]);
        }
      }
    }
    printf("%.10f\n", info[m][l]);
  }
}

Measured memory_bytes: 1364
#include <bits/stdc++.h>
#define MOD 10000
#define tam 301024
#define F first
#define pb push_back

#define S second
#define INF 1E9 +7
#define ll long long 
#define offset tam/2
#define forr(i, b, e)     for(ll i = b; i < e; i++)
#define fore(i, b, e) forr(i,b,e)
using namespace std;
typedef pair<int,int> ii;
bool ac[tam];
int cant[tam];
int main()
{
    int n,m;
    cin>>n>>m;
    int totac=0,tot=0;
    int problem;
    string txt;
    forr(i,0,m)
    {
        cin>>problem>>txt;
        if (ac[problem]==0 && txt=="AC")
            totac++,tot+=cant[problem];
        ac[problem]|=(txt=="AC");
        if (ac[problem]==0)
            cant[problem]++;
    }
    cout<<totac<<" "<<tot<<endl;

}   

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    string o,e,s;
    cin>>o>>e;
    rep(i,e.size()){
        s+=o[i];
        s+=e[i];
    }
    if(e.size()!=o.size()){
        s+=o[o.size()-1];
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		long k = sc.nextLong();
		char ans = '0';
		for(int i=0; i<k; i++){
			if(s.charAt(i)!='1'){
				ans = s.charAt(i);
				break;
			}
		}
		if(ans=='0')ans = '1';
		System.out.println(ans);
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define ri register int
#define csi const int&
#define fi first
#define se second
#define pb push_back
using namespace std;
const int rlen=1<<18|1;
char buf[rlen],*ib=buf,*ob=buf;
#define gc() (((ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin)),ib==ob)?-1:*ib++)
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
inline int read(){
	int ans=0;
	char ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return ans;
}
inline ll readl(){
	ll ans=0;
	char ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return ans;
}
inline int Read(char*s){
	int top=0;
	char ch=gc();
	while(ch!='*'&&ch!='.')ch=gc();
	while(ch=='*'||ch=='.')s[++top]=ch,ch=gc();
	return top;
}
namespace modular{
	const int mod=1e9+7;
	inline int add(int a,int b){return (a+=b)<mod?a:a-mod;}
	inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
	inline int mul(int a,int b){return (ll)a*b%mod;}
	inline void Add(int&a,int b){a=add(a,b);}
	inline void Dec(int&a,int b){a=dec(a,b);}
	inline void Mul(int&a,int b){a=(ll)a*b%mod;}
	inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,Mul(a,a))(p&1)&&(Mul(ret,a),1);return ret;}
	inline int Inv(int x){return ksm(x,mod-2);}
	inline void fix(int&x){x=(x%mod+mod)%mod;}
}
using namespace modular;
template<typename T>inline void ckmin(T&a,const T&b){a>b?a=b:0;}
template<typename T>inline void ckmax(T&a,const T&b){a<b?a=b:0;}
const int N=2005;
int n,m,C[N][N],g[N][N],f[N][N];
inline void init(int up){
	for(ri i=0;i<=up;++i){
		C[i][0]=1;
		for(ri j=1;j<=i;++j)
		C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	}
	for(ri i=0;i<=up;++i){
		g[i][0]=C[i][0];
		for(ri j=1;j<=up;++j)g[i][j]=add(g[i][j-1],C[i][j]);
	}
	for(ri i=0;i<=up;++i){
		f[0][i]=g[i][0];
		for(ri j=1;j<=up;++j)f[j][i]=add(f[j-1][i],g[i][j]);
	}
}
int main(){
	#ifdef ldxcaicai
	freopen("lx.in","r",stdin);
	#endif
	n=read(),m=read();
	init(max(n,m));
	int res=0;
	for(ri t1,t2,x=0;x<=n;++x)for(ri a=0;a+x<=n;++a){
		t1=C[m-1][a];
		t2=a?f[n-a-x][a-1]:1;
		Add(res,mul(t1,t2));
	}
	cout<<res<<'\n';
	return 0;
}

Measured memory_bytes: 47360
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;

int main(){
    string S, T, U;
    cin >> S >> T;
    int A, B;
    cin >> A >> B >> U;
    if(S == U) cout << A-1 << " " << B << endl;
    else cout << A << " " << B-1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[15010][10010]; 
int main(){
	int H, N; 
	cin >> H >> N; 
	int A[1010], B[1010]; 
	for(int i = 1; i <= N; i++){
		cin >> A[i] >> B[i]; 
	}
	vector<int> P, Q; 
	for(int i = 1; i <= N; i++){
		int nowA = A[i]; int nowB = B[i]; 
		P.push_back(nowA); Q.push_back(nowB); 
		while(nowA < H){
			nowA <<= 1; P.push_back(nowA); 
			nowB <<= 1; Q.push_back(nowB);
		}
	}
	for(int i = 0; i <= P.size(); i++){
		for(int j = 0; j <= H; j++){
			dp[i][j] = 1e9 + 7; 
		}
	}
	dp[0][0] = 0;
	for(int i = 0; i < P.size(); i++){
		for(int j = 0; j <= H; j++){
		    if(dp[i][j] == 1e9+7) continue; 
			dp[i+1][min(j+P[i], H)] = min(dp[i+1][min(j+P[i], H)], dp[i][j] + Q[i]); 
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]); 
		}
	}
	cout << dp[P.size()][H] << endl;
}

Measured memory_bytes: 559616
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000000007;
const double PI = acos(-1);

int main()
{
	int h, w, k;
	cin >> h >> w >> k;
	int black = 0;
	vector<vector<char>> c(h, vector<char>(w));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> c[i][j];
			if (c[i][j] == '#') black++;
		}
	}

	int ans = 0;
	for (int bit = 0; bit < 1 << (h + w); bit++) {
		vector<int> height(h);
		vector<int> width(w);
		for (int i = 0; i < (h + w); i++) {
			if (bit & (1 << i)) {
				if (i <= h - 1) height[i] = 1;
				else width[i - h] = 1;
			}
		}
		int black_count = black;
		vector<vector<char>> tmp(c);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (height[i]) {
					if (tmp[i][j] == '#') {
						black_count--;
						tmp[i][j] = '+';
					}
				}
			}
		}
		for (int j = 0; j < w; j++) {
			for (int i = 0; i < h; i++) {
				if (width[j]) {
					if (tmp[i][j] == '#') {
						black_count--;
						tmp[i][j] = '+';
					}
				}
			}
		}
		if (black_count == k) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3600
a,b=map(int,input().split())
#a,b=map(int,input().split())
#a=list(map(int,input().split()))
ans=0
import math
for i in range(a):
    x,y=map(int,input().split())
    z=math.sqrt(x**2 + y**2)
    if z<=b:
        ans+=1

print(ans)


Measured memory_bytes: 9144
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll n, k; cin >> n >> k;
    ll s = 0;
    ll a[n + 10] = {0};
    for(ll i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    for(ll i = 0; i < k; i++)
        s += a[i];
    cout << s;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int n,a,b;scanf("%d %d %d",&n,&a,&b);
    printf("%d",min(n*a,b));
    return 0;
}

Measured memory_bytes: 504
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int MAX_N=1e5+2;
int a[MAX_N],b[MAX_N];
int x,n;
int main()
{     int i,j,k=0,maxn=-1;
      scanf("%d",&n);
      for(i=1;i<=n;i++){
         scanf("%d",&a[i]);
         b[a[i]+1]++;
         maxn=max(maxn,b[a[i]+1]); 
         b[a[i]]++;
         maxn=max(maxn,b[a[i]]);
         b[a[i]-1]++;
         maxn=max(maxn,b[a[i]-1]);
      }
      printf("%d",maxn);
	  return 0;
}


Measured memory_bytes: 1024
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if(n == 3 || n == 5 || n == 7){
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
const int inf = (int) 1e9;
int main(){
  string s;
  cin>>s;
  int a=0;
for(int i=0;i<s.size();i++){
  if(a==0 && s[i]=='C'){
    a++;
  }else if(a==1 && s[i]=='F'){
    a++;
  }
}
if(a==2){
  cout<<"Yes"<<endl;
}else{
  cout<<"No"<<endl;
}
  return 0;
}


Measured memory_bytes: 256
<?php
list($n) = ints();

$wf = new WarshallFloyd($n);
for ($i = 0; $i < $n; ++$i) {
    list($s) = strs();
    for ($j = 0; $j < $n; ++$j) {
        if ($s[$j] === '1') {
            $g[$i][] = $j;
            $wf->connect($i, $j, 1);
        }
    }
}
if (!isNipartite()) exit('-1');
$wf->solve();
$max = 0;
for ($i = 0; $i < $n - 1; ++$i)
    for ($j = $i + 1; $j < $n; ++$j)
        $max = max($max, $wf->dist($i, $j));
echo $max + 1;
function isNipartite()
{
    global $n, $g, $dist;
    // BFS：二部グラフ判定
    $is_nipartite = true; // 二部グラフかどうか
    $q = new SplQueue(); // キューを用意
    $dist = array_fill(0, $n, -1); // 距離を格納する配列（-1の場合はその頂点が未発見）

    for ($i = 0; $i < $n; $i++) {
        if ($dist[$i] !== -1) continue; // 発見済み
        $dist[$i] = 0; // 頂点$iからの距離格納配列
        $q->enqueue($i); // キューに$iを追加
        while (!$q->isEmpty()) {
            $v = $q->dequeue();

            foreach ($g[$v] as $next_v) {
                if ($dist[$next_v] === -1) {
                    $dist[$next_v] = $dist[$v] + 1;
                    $q->enqueue($next_v);
                } else {
                    if ($dist[$next_v] === $dist[$v]) { // 隣接する頂点の距離が同じ場合二部グラフにならない
                        $is_nipartite = false;
                        break 3;
                    }
                }
            }
        }
    }
    return $is_nipartite;
}
// 全てのノード間の最短距離を求める
// 0-indexed
class WarshallFloyd
{
    private $n;
    private $d;

    function __construct($n)
    {
        $this->n = $n;
        $this->d = array_fill(0, $this->n, array_fill(0, $this->n, INF));
        for ($i = 0; $i < $this->n; ++$i) $this->d[$i][$i] = 0;
    }

    function connect($x, $y, $w)
    {
        $this->d[$x][$y] = $w;
    }

    function solve()
    {
        $n = $this->n;
        $d = $this->d;
        for ($k = 0; $k < $n; ++$k) { // 経由点
            for ($i = 0; $i < $n; ++$i) { // 始点
                for ($j = 0; $j < $n; ++$j) { // 終点
                    $d[$i][$j] = min($d[$i][$j], $d[$i][$k] + $d[$k][$j]);
                }
            }
        }
        $this->d = $d;
    }

    function dist($x, $y)
    {
        return $this->d[$x][$y];
    }
}
function strs()
{
    return explode(' ', trim(fgets(STDIN)));
}
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


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

const int MAX_N = 100;

int main(){
	int n,m,x,left=0,right=0;
	cin>>n>>m>>x;
	int a[MAX_N];
	for (int i = 0; i < m; i++){
		cin>>a[i];
		if(x>a[i]){
			left++;
		}else{
			right++;
		}
	}

	cout<< min(left,right) <<endl;
}


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

const int MOD = (int)1e9+7;

int main(){
	char b;
	cin >> b;

	if(b=='A')	cout << "T" << endl;
	else if(b=='T')	cout << "A" << endl;
	else if(b=='C')	cout << "G" << endl;
	else if(b=='G')	cout << "C" << endl;

	return 0;
}


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

long long n,ans,mod=998244353ll,tmp,pos,cont,pot[200005];
int v[200005];
vector<pair<long long,long long> > opz;
vector<long long> divi;
string x,zer,s;

int calc(int siz){
	
	s.clear();
	
	for(int i=0;i<siz;i++){
		s.push_back(x[i]);
	}
	
	while(s.size()<x.size())s.push_back('0'+(s[s.size()%siz]-'0')^int((s.size()/siz)%2==1));
	
	if(s<=x)return n+1;
	
	for(int j=siz-1;j>=0;j--){
		if(x[j]=='1')return j;
	}
	
	return -1;
}

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

	cin>>n>>zer;
	
	pot[0]=1;
	
	for(int i=1;i<200005;i++)pot[i]=(pot[i-1]*2ll)%mod;
	
	for(int i=0;i<(n-zer.size());i++)x.push_back('0');
	
	for(int i=0;i<zer.size();i++)
	x.push_back(zer[i]);
	
	for(int i=1;i<=n;i++){
		if(n%i==0 && (n/i)%2==1)divi.push_back(i);
	}
	
	for(int i=0;i<divi.size();i++){
		
		//cout<<divi[i]<<endl;
		cont=divi[i];
		tmp=0;
		
		zer.clear();
		for(int j=0;j<x.size();j++)zer.push_back('0');
		
		pos=calc(divi[i]);
		
		if(pos==-1)continue;
		
		for(int j=0;j<divi[i];j++){
			cont--;
			if(j<pos){
				if(x[j]=='1')
				tmp+=pot[cont];
			}
			else{
				if(j>pos)tmp+=pot[cont];
			}
			
			tmp%=mod;
		}
		
		tmp++;
		//cout<<divi[i]<<" ha "<<tmp<<" numeri"<<endl;
		opz.push_back({tmp,divi[i]});
	}
	
	
	for(int i=0;i<opz.size();i++){
		for(int j=i-1;j>=0;j--){
			if(opz[i].second%opz[j].second==0){
				opz[i].first-=opz[j].first;
				opz[i].first%=mod;
			}
		}
		
		ans+=(opz[i].first*(opz[i].second*2ll%mod))%mod;
		ans%=mod;
	}
	
	cout<<(ans%mod+mod)%mod<<"\n";

return 0;
}


Measured memory_bytes: 2708
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll a,b,n;
    cin>>a>>b>>n;
    cout<<(a*min(b-1,n))/b<<endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  vector<ll> A(n), B(n), C(m), D(m);
  rep(i, n) cin >> A[i] >> B[i];
  rep(i, m) cin >> C[i] >> D[i];
  rep(i, n) {
    ll mn = longinf;
    int mni = -1;
    rep(j, m) {
      if(abs(C[j]-A[i])+abs(D[j]-B[i]) < mn) {
        mn = abs(C[j]-A[i])+abs(D[j]-B[i]);
        mni = j;
      }
    }
    cout << mni+1 << "\n";
  }
  return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

/*
9 -> ok
10 -> out
11 -> out
10^12 -> out

n
a1
..
an

n<100000
ai<1000000000

out: first, second
*/
typedef long long int ll;


int main(){
  ll n, p;
  cin >> n >> p;
  if(n == 1){
    cout << p << endl;
    return 0;
  }

  

  ll ans = 1;
  for(ll i = 2; i <= sqrt(p); i++){
    int cnt = 0;
    while(p % i == 0){
      p /= i;
      cnt++;
      if(cnt >= n){
        ans *= i;
        cnt = 0;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CompetitiveProgCsLib
{
	class MainProg
	{
		static string R => Console.ReadLine();
		static int RI => int.Parse(R);
		static double RD => double.Parse(R);
		static int[] RIs => R.Split(' ').Select(int.Parse).ToArray();
		static double[] RDs => R.Split(' ').Select(double.Parse).ToArray();
		static void Out(object obj) => Console.WriteLine(obj);
		static void OutLine<T>(IEnumerable<T> obj, string separateChar) => Out(String.Join(separateChar, obj));
		static void Outb(bool b) => Out(b ? "Yes" : "No");
		static void OutB(bool b) => Out(b ? "YES" : "NO");
		static bool IsIn(int y, int x, int h, int w) => 0 <= x && x < w && 0 <= y && y < h;
		static T MIN<T>(params T[] args) => args.Min();
		static T MAX<T>(params T[] args) => args.Max();

		static void Main(string[] args)
		{
			var ns = new List<int>(RIs);
			ns.Sort();
			OutB(ns[0] == 1 && ns[1] == 4 && ns[2] == 7 && ns[3] == 9);
		}
	}
}


Measured memory_bytes: 13396
using LIB;
using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int[] n = io.r<int>(' ');
        int[][] m = io.r<int>(n[0], ' ');
        int[] b = io.r<int>(n[1]);

        foreach (int[] buf in m)
        {
            int sum = 0;
            for (int i = 0; i < n[1]; i++)
            {
                sum += buf[i] * b[i];
            }
            io.w(sum);
        }
        io.wflush();
    }
}

namespace LIB
{
    public class io
    {
        private const int WMAX = 1000;
        private static StringBuilder S = new StringBuilder();
        public static T r<T>() { return util.parse<T>(r()); }
        public static T[] r<T>(char s = ' ') { return r().Split(s).Select(util.parse<T>).ToArray(); }
        public static T[] r<T>(int l) { T[] r = new T[l]; for (int i = 0; i < l; i++) { r[i] = r<T>(); } return r; }
        public static T[][] r<T>(int l, char s = ' ') { T[][] r = new T[l][]; for (int i = 0; i < l; i++) { r[i] = r<T>(s); } return r; }
        private static string r() { return Console.ReadLine(); }
        public static void w(object v, bool lf = true) { S.Append(util.parse<string>(v)); if (lf == true) { S.Append('\n'); } if (S.Length >= WMAX) { wflush(); } }
        public static void wflush() { Console.Write(S.ToString()); S.Length = 0; }
    }
    public class util
    {
        public static T parse<T>(object value) { return (T)(Convert.ChangeType(value, typeof(T))); }
    }
    public class memo<Key, Result>
    {
        private Dictionary<Key, Result> R;
        public memo() { R = new Dictionary<Key, Result>(); }
        public Result exec(Key k, Func<Key, Result> f) { Result r; if (R.ContainsKey(k)) { r = R[k]; } else { r = f(k); R.Add(k, r); } return r; }
    }
}

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

struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define MOD 1000000007



int main() {
    int H, W, h, w; cin >> H >> W >> h >> w;
    cout << (H - h)*(W - w) << endl;
}







Measured memory_bytes: 256
/*Learning is endless*/
#include <bits/stdc++.h>
#define endl "\n";
#define pii pair<int,int>;
using namespace std;
typedef long long ll;
const ll BIG=1000000007;
const double PI=3.141592653589793238;
template <typename T,typename Q>
T max(T a,Q b)
{
    if(a<b)
        return b;
    return a;
}
template <typename T,typename Q>
T min(T a,Q b)
{
    if(a>b)
        return b;
    return a;
}
long gcd(long a,long b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b,a%b);
}
void solve()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=max(max(max(a*c,a*d),b*c),b*d);
    cout<<ans;
}
int main() {
    int t;
  	t=1;
    while(t--)
        solve();
	return 0;
}


Measured memory_bytes: 3568
#include <stdio.h>
#define EPS 1e-10
int main() {
    int a,b,c,d,e,f,x,sign,sign2;double q,r;while (scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f)!=EOF) {
        x=a*e-b*d;if (x<0) sign=-1,x=-x; else sign=1;
        q=(c*e-f*b);if (q<0.00) sign2=-1,q=-q; else sign2=1;q=(q*sign*sign2)/(x+0.00);
        r=(a*f-c*d);if (r<0.00) sign2=-1,r=-r; else sign2=1;r=(r*sign*sign2)/(x+0.00);
        if (r<EPS && r>-EPS) r=0.00;if (q<EPS && q>-EPS) q=0.00;
        printf("%.3lf %.3lf\n",q,r);
    }
return 0;}

Measured memory_bytes: 0
<?php

ini_set('memory_limit', '512M');

$p = array_fill(0, 1000000, true);
$p[0] = $p[1] = false;

for($i = 2; $i * $i < 1000000; $i++){
    if(!$p[$i]) continue;
    for($j = $i * $i; $j < 1000000; $j += $i){
        $p[$j] = false;
    }
}

$sum = array_fill(0, 1000000, 0);

for($i = 1; $i < 1000000; $i++){
    $sum[$i] += $sum[$i - 1];
    if($p[$i]) $sum[$i]++;
}

while(fscanf(STDIN, "%d", $n)){
    echo $sum[$n] . "\n";
}

Measured memory_bytes: 285036
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		int[][] points = new int[n+1][3];
		for(int i=1;i<=n;i++){
		    points[i][0] =scn.nextInt();
		    points[i][1] =scn.nextInt();
		    points[i][2] =scn.nextInt();
		}
		// System.out.println(maxHappiness(1,points,-1));
		int[][] memo = new int[n+1][3];
		System.out.println(maxHappiness_memoized(1,points,-1,memo));

	}


    public static int maxHappiness_memoized(int day, int[][] points , int activityOnPrevDay,int[][] memo) {
    		if(day==points.length)return 0;
      		if(activityOnPrevDay!=-1 && memo[day][activityOnPrevDay]!=0)return memo[day][activityOnPrevDay];
    		int ans = Integer.MIN_VALUE;
    		for (int i = 0; i < 3; i++) {
    			if (i != activityOnPrevDay) {
    				int ca = points[day][i] + maxHappiness_memoized(day + 1, points, i,memo);
    				ans = Math.max(ans, ca);
    			}
    		}
    		if(activityOnPrevDay!=-1)
    		    memo[day][activityOnPrevDay]=ans;
    		return ans;
    }
}


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

int l[200010], n;
int act[300010];

bool incr(int poz, int base)
{
	if (poz == 0)
		return false;
	act[poz]++;
	if (act[poz] == base) {
		act[poz] = 0;
		return incr(poz - 1, base);
	}
	return true;
}

bool cbin(int nr)
{
	memset(act, 0, sizeof act);
	
	int lact = 0;
	for (int i = 1; i <= n; i++) {
		if (l[i] > lact)
			lact = l[i]; /// maresc
		else {
			for (int j = lact, c = 0; c < 20 && j > l[i]; j--, c++)
				act[j] = 0;
			lact = l[i];
			if (!incr(lact, nr))
				return false;
		}
	}
	return true;
}

int main()
{
	cin >> n;

	bool ok = 1;

	for (int i = 1; i <= n; i++) {
		cin >> l[i];
		ok &= (l[i] > l[i - 1]);
	}

	if (ok) {
		cout << 1 << '\n';
		return 0;
	}

	for (int i = 1; i <= n; i++)
		l[i] = min(l[i], 300000);

	int p = 0, q = (1 << 20);

	while (q >>= 1)
		if (!cbin(p + q))
			p += q;

	cout << p + 1 << '\n';

	return 0;
}


Measured memory_bytes: 2176
#include<iostream>
#include<math.h>
using namespace std;
int main(){
  int N, D, X[10][10];
  cin >> N >> D;
  for(int i=0; i<N; i++){
    for(int j=0; j<D; j++){
      cin >> X[i][j];
    }
  }
  int ans = 0;
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
      double dist = 0.0;
      for(int k=0; k<D; k++){
        dist += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
      }
      dist = sqrt(dist);
      if(dist == (int)dist) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
s = input()
n = len(s)
cnt = 0
alpha = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in range(n):
  if i == 0:
    if s[0] != 'A':
      print('WA')
      break
    s = 'a' + s[1:]
  if 2 <= i < n-1:
    if s[i] == 'C':
      cnt += 1
      if cnt == 2:
        print('WA')
        break
      s = s[:i] + 'c' + s[i+1:]
  if i == n-1:
    if cnt == 0:
      print('WA')
      break
  if s[i] in alpha:
    print('WA')
    break
else:
  print('AC')

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	private static final int NOT_FOUND = -1000;
	private static final int MIN = 2;
	private static final int MAX_NUM = 50500;
	public static void main(String[] args) throws IOException{
		//素数の算出
		int[] primeNumbers = getPrimeNumbers(MAX_NUM);
		boolean[] isPrime = new boolean[MAX_NUM + 1];
		for(int i : primeNumbers){
			isPrime[i] = true;
		}
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = null;
		while((input = br.readLine()) != null){
			int target = Integer.parseInt(input);
			System.out.println(
					getApproximateLowerPrime(isPrime, target)
					+ " " +
					getApproximateHigherPrime(isPrime, target)
					);
		}
		
	}
	private static int getApproximateLowerPrime(boolean[] isPrime, int n){
		for(int i = n - 1; i >= 0; i--){
			if(isPrime[i]) return i;
		}
		return NOT_FOUND;
	}
	private static int getApproximateHigherPrime(boolean[] isPrime, int n){
		for(int i = n + 1; i < isPrime.length; i++){
			if(isPrime[i]) return i;
		}
		return NOT_FOUND;
	}
    private static int[] getPrimeNumbers(int n){
    	ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = MIN; i < n + 1; i++){
            if(isPrimeNumber(i)){
            	list.add(i);
            }
        }
        Object[] arry = list.toArray();
        int[] primeNumbers = new int[arry.length];
        for(int i = 0; i < primeNumbers.length; i++){
        	primeNumbers[i] = (Integer)arry[i];
        }
        return primeNumbers;
    }
    private static boolean isPrimeNumber(int n){
    	if(n == 2){
    		return true;
    	}
    	else if(n % 2 == 0){
    		return false;
    	}
    	
    	for(int i = 3; i  * i < n + 1; i = i + 2){
    		if(n % i == 0){
    			return false;
    		}
    	}
    	return true;
    }
}

Measured memory_bytes: 20176
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""076-b"""


import sys


def main():
    """Main function."""
    N = int(input())
    K = int(input())

    res = 1

    for i in range(N):
        if res * 2 < res + K:
            res = res * 2
        else:
            res = res + K

    print(res)


if __name__ == '__main__':
    sys.exit(main())

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

string s[3] = {"ABC", "DEF", "GHI"}, pass;
int vx[4] = {-1, 0, 1, 0}, vy[4] = {0, -1, 0, 1};

bool search(int cnt, int n) {
	if (cnt == pass.size() - 1) return true;

	bool ret = false;

	for (int i = 0; i < 4; ++i) {
		int nx = n / 3 + vx[i], ny = n % 3 + vy[i];

		if (0 <= nx && nx <= 2 && 0 <= ny && ny <= 2) {
			if (pass[cnt + 1] == s[nx][ny]) {
				ret = search(cnt + 1, pass[cnt + 1] - 'A');
				if (ret) return ret;
			}
		}
	}

	return false;
}

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

	for (int i = 0; i < 1000; ++i) {
		cin >> pass;
		int num = pass[0] - 'A';
		if (search(0, num)) cout << pass << endl;
	}

	return 0;
}

Measured memory_bytes: 3204
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define eps 1e-6
#define mp make_pair
const long long INF=1e18+2;
const int MX=100353;
int N, M, k;
int arr[MX];
vector<int> v;
bool ch(int x)
{
    while(x )
    {
        int a=x%10, ok=0;
        for(int i=0;i<v.size();i++) if(a == v[i]) {
            ok=1;
            break;
        }
        if(!ok) return 0;
        x/=10;
    }
    return 1;
}
int main()
{
    scanf("%d%d", &N, &k);
    for(int i=0; i<k; i++)
    {
        int x;
        cin>>x;
        arr[x]=1;

    }

    for(int i= 0; i<10; i++) if(!arr[i]) v.pb(i);
    int n=N;
    while(1)
    {
        if(ch(n)){
            cout<<n;
            return 0;
        }
        ++n;
    }
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}

//座標圧縮
int cocomp(ll*a,int n){
	//0～cnt-1に値を圧縮
	ll*b=(ll*)malloc(sizeof(ll)*n);
	memcpy(b,a,sizeof(ll)*n);
	sortup(b,n);
	int cnt=1;
	rep(r,1,n)if(b[r]!=b[cnt-1])b[cnt++]=b[r];
	rep(i,0,n){
		int l=0,r=cnt;
		while(r-l>1){int m=(l+r)/2;if(b[m]>a[i])r=m;else l=m;}
		a[i]=l;
	}
	free(b);
	return cnt;
}

//seg木
int segNUM;
ll segN[1<<21],*seg;
void seguse(int n){segNUM=n;seg=segN+segNUM;}

//seg[]に値を与えてから初期化
void seginit(){
	for(int node=segNUM-1;node;node--)segN[node]=segN[node*2]+segN[node*2+1];//sum
}
void segupdate(int node,ll x){
	//seg[node]をxに更新
	node+=segNUM;
	segN[node]=x;
	while(node/=2){
		segN[node]=segN[node*2]+segN[node*2+1];//sum
	}
}

ll segcalcsub(int a,int b,int k,int l,int r){
	//segN[k]に[l,r)が対応する
	//disjointなとき
	if(r<=a||b<=l)return 0;//sum
	//完全に含むとき
	if(a<=l&&r<=b)return segN[k];
	//どちらもでもないとき
	int left=segcalcsub(a,b,k*2,l,(l+r)/2),right=segcalcsub(a,b,k*2+1,(l+r)/2,r);
	return left+right;//sum
}

//[a,b)に対して答える
ll segcalc(int a,int b){return segcalcsub(a,b,1,0,segNUM);}



ll n,nn;
ll a[100010],b[100010];
ll s[100010];
ll check(ll k){
	//aの連続部分列であって、k以上の要素をceil((長さ)/2)個含むものはいくつあるか
	//⇔k未満なら-1,k以上なら+1としたとき、総和が0以上になる連続部分列はいくつあるか
	//⇔累積和をとってseg木でえい
	s[0]=0;
	rep(i,0,n){
		s[i+1]=s[i];
		if(a[i]>=k)s[i+1]++;
		else s[i+1]--;
	}
	ll cnt=cocomp(s,n+1);
//	rep(i,0,n+1)printf("%lld ",s[i]);puts("");
	ll ans=0;
	rep(i,0,cnt+5)seg[i]=0;
	seginit();
	rep(i,0,n+1){
		ans+=segcalc(0,s[i]+1);
		segupdate(s[i],seg[s[i]]+1);
	}
	return ans;
}


int main(){
	scanf("%lld",&n);
	nn=n*(n+1)/2;
	rep(i,0,n){
		scanf("%lld",a+i);
		b[i]=a[i];
	}
	sortup(b,n);

	seguse(1<<17);
	//にぶたん
	ll l=0,r=n;//lはok,rはng
	while(r-l>1){
		ll m=(l+r)/2;
//		printf("%lld %lld\n",b[m],check(b[m]));
		if(check(b[m])>=(nn+1)/2)l=m;
		else r=m;
	}
	
	printf("%lld\n",b[l]);
	return 0;
}

Measured memory_bytes: 8220
def fib(num_steps):
    xb = 0
    xa = 1
    if num_steps == 0:
        return xa
    else:
        for i in range(num_steps):
            tmp = xa
            xa = xa + xb
            xb = tmp
    
    return xa

N, M = map(int, input().split())
ways = 1
now = 0

for i in range(M):
    hole = int(input())
    diff = (hole - 1) - now

    if diff < 0:
        ways *= 0
    else:
        ways *= fib(diff)

    now = hole + 1

if now < N:
    ways *= fib(N - now)

print(ways % 1000000007)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

int const N = 200001;

int main(){
    int a, b, c, d; 
    cin >> a >> b >> c >> d;
    for(int i = 0; i<100; ++i){
      if(i & 1 ^ 1){
         c -= b;
      }
      else a -= d;
      if(c <= 0 || a <= 0)break;
    }
    if(a > 0)puts("Yes");
    else puts("No");
}

Measured memory_bytes: 3120
import sys
def input():
    return sys.stdin.readline()[:-1]
L=int(input())
b=[0]*5
a=[0]*5
for i in range(L):
    n=int(input())
    a[0]=b[0]+n
    a[1]=min(b[0],b[1])+n%2
    a[2]=min(b[0],b[1],b[2])+(not n%2)
    a[3]=min(b[0],b[1],b[2],b[3])+n%2
    a[4]=min(b[0],b[1],b[2],b[3],b[4])+n
    if not n:
        a[1]+=2
        a[3]+=2
    b=a.copy()
print(min(a))

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

using namespace std;

int main(){
    string s;
    cin >> s;
    string s1 = s;
    string s2 = s;
    int count1 = 0;
    int count2 = 1;

    for(int i = 0; i < s1.size() - 1; i++){
        if(s1[i+1] == s1[i]){
            if(s1[i] == '0')s1[i+1] = '1';
            else s1[i+1] = '0';
            count1++;
        }
    }

    if(s2[0] == '0')s2[0] = '1';
    else s2[0] = '0';

    for(int i = 0; i < s2.size() - 1; i++){
        if(s2[i+1] == s2[i]){
            if(s2[i] == '0')s2[i+1] = '1';
            else s2[i+1] = '0';
            count2++;
        }
    }

    if(count1 > count2){
        cout << count2 << endl;
    }else{
        cout << count1 << endl;
    }
    
    return 0;
}

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

int top,s[100];

int pop() {
  
  top = top - 1;
  return s[top+1];
  
}

void push(int x) {
  
  top = top + 1;
  s[top] = x;
  
}

int main(){
  int a,b,x;
  char s[100];
  top=0;
  
  while( scanf("%s", s) != EOF ){
    
    if ( s[0] == '+' ){
      a=pop();
      b=pop();
      push(b+a);
      
      
    } else if ( s[0] == '-' ){
      a=pop();
      b=pop();
      push(b-a);
      
      
      
    } else if ( s[0] == '*' ){
      a=pop();
      b=pop();
      push(b*a);
      
    } else {
      x = atoi(s);
      push(x);
      
      
    }
    
  }
  
  printf("%d\n",pop());
  
  
  return 0;
}

 

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007;


int main(){
  ll n;
  cin >> n;
  vll a(n), b(n), c(n);
  vin(a);vin(b);vin(c);

  ll ans = 0;
  sort(all(a));sort(all(c));
  rep(i, 0, n){
    ans += distance(a.begin(), lower_bound(all(a), b.at(i))) * distance(lower_bound(all(c), b.at(i) + 1), c.end());
  }
  cout << ans << endl;
}

Measured memory_bytes: 2560
using namespace std;

//#define fileio

#ifndef fileio
#include <iostream>
#endif
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <functional>
#include <math.h>
#include <string>
#include <ctime>

typedef long long ll;

#ifdef fileio
ifstream cin;
ofstream cout;
#endif



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef fileio
    cin.open("Text.txt");
    cout.open("Output.txt");
#endif
    int n;
    cin >> n;

    vector<int> v;
    set<int> primes;
    set<int> primes2;
    bool ok = true;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v.push_back(x);
        if (i != 0) {
            for (auto prime : primes2) if (x % prime) primes2.erase(prime);
        }
        for (int j = 2; j * j <= x; j++) {
            if (x % j == 0) {
                if (primes.count(j)) ok = false;
                primes.insert(j);
                if (i == 0) primes2.insert(j);
                while (x % j == 0) x /= j;
            }

        }
        if (x > 1) {
            if (primes.count(x)) ok = false;
            if (i == 0) primes2.insert(x);
            primes.insert(x);
        }
        
    }
    if (ok) cout << "pairwise coprime" << endl;
    else if (!primes2.size()) cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;
    

}


Measured memory_bytes: 10544
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <stack>
#include <limits>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <numeric>
//#include <tuple>

constexpr long long mod = static_cast<long long>(1e9 + 7);

struct Edge {
    int to;
    int w;
};

using Edges = std::vector<std::vector<Edge>>;

int main() {
    int V, E, r;
    std::cin >> V >> E >> r;
    Edges edges(V, std::vector<Edge>());
    while(E--) {
        int s, t, w;
        std::cin >> s >> t >> w;
        edges[s].push_back(Edge{t, w});
    }

    std::vector<int> dist(V, std::numeric_limits<int>::max());
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pque;
    pque.push(std::make_pair(0, r));
    while(!pque.empty()) {
        auto now = pque.top();
        pque.pop();
        int v = now.second;
        int w = now.first;
        dist[v] = std::min(dist[v], w);
        for(auto val: edges[v]) {
            if(dist[val.to] == std::numeric_limits<int>::max()) {
                pque.push(std::make_pair(w + val.w, val.to));
            }
        }
    }

    for(auto val: dist) {
        if(val == std::numeric_limits<int>::max()) std::cout << "INF\n";
        else std::cout << val << '\n';
    }

    std::cout << std::flush;

    return 0;
}



Measured memory_bytes: 14008
sn = int(input())

S=[0 for i in range(sn)]

S=input().split()

tn = int(input())

T=[0 for i in range(tn)]

T=input().split()

cnt=0

A=[]

for i in range(len(T)):
	for j in range(len(S)):
		if T[i]==S[j]:
			if T[i] not in A:
				cnt+=1
			A.append(T[i])

print(cnt)


Measured memory_bytes: 6208
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e6;
const int INF=1e9;
int main(){
	long A,B,C,D;cin>>A>>B>>C>>D;
	long e=__gcd(C,D);e=C*D/e;
	long a,b;
	a=(A-1)/C+(A-1)/D-(A-1)/e;
	b=B/C+B/D-B/e;
	cout<<(B-b)-(A-1-a)<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#define MAX_N 200

using namespace std;
string A[20],B[20];
string C,D;
typedef pair<int,string> P;
int N,M;
int bfs(string s)
{
    priority_queue<P,vector<P>,greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
        P p=que.top();
        que.pop();
        string v=p.second;
        int n=v.length();
        int d=p.first;
        if(v==D)return d;
        if(n>=M)continue;
        for(int i=0;i<N;i++){
            string t=v;
            int m=t.length();
            int l=A[i].length(),nl=B[i].length();
            for(int j=0;j<m;j++){
                bool flag=true;
                for(int k=0;k<l;k++){
                    if(A[i][k]!=t[j+k]){
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    t.resize(m+nl-l);
                    for(int k=m-1;k>=l+j;k--){
                        t[k+nl-l]=t[k];
                    }
                    for(int k=0;k<nl;k++){
                        t[j+k]=B[i][k];
                    }
                    j=j+nl-1;
                    m+=nl-l;
                }
            }
            if(m>n){
                que.push(P(d+1,t));
            }
        }
    }
    return -1;
}
int main()
{
    while(cin>>N&&N){
        for(int i=0;i<N;i++){
            cin>>A[i]>>B[i];
        }
        cin>>C>>D;
        M=D.length();
        int ans=bfs(C);
        printf("%d\n",ans);
    }
}

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

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

// 降順ソート vector<int> v;
// sort(v.begin(),v.end(),greater<int>());

ll cnt[2001] = {};


ll calc( ll rest ) {
  if(rest<3) return 0;
  if(cnt[rest]>=0){
    return cnt[rest];
  }
  ll tmp = 1;
  for(int i=3;i<rest;i++){
    tmp += calc(rest-i);
    tmp %= MOD;
  }
  cnt[rest] = tmp%MOD;
  return tmp;
}

signed main() {
  ll s;
  cin >> s;

  for(int i=0;i<2001;i++){
    cnt[i] = -1;
  }
  
  cout << calc(s) << endl;

  
  // dp[n] = dp[n-3]
  
  // 5
  // 3,3  6    2
  // 3,4  4,3 7
  // 3,5  5,3 4,4 8
  // 3,(3,3) 3,(6)  (6),3   4,5 5,4   9 
  // 3,3,4 3,4,3 4,3,3 3,7 7,3 4,6 6,4 5,5 10
  // 3,3,3,3 3,(3,6) 3,(6,3) (3,6),3 (6,3),3  5
  
  return 0;
}



Measured memory_bytes: 3672
#include <bits/stdc++.h>
long long a[200007] = {0};
long long b[200007] = {0};
int n, m, t;
using namespace std;
int main(){
	cin >> n >> m >> t;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for(int i = 1; i <= m; i++){
		cin >> b[i];
		b[i] += b[i - 1];
	}
	int ans = 0, mb = m;
	for(int i = 0; i <= n; i++){
		while(a[i] + b[mb] > t){
			if(mb == 0) break;
			mb--;
		}
		if(a[i] + b[mb] > t) continue;
		ans = max(ans, i + mb);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6700