akhauriyash/Code-Regression huggingface dataset:
#include <cmath>
#include <complex>
#include <vector>
#include <cstdio>
using namespace std;


#define EPS 1e-7


typedef complex<double> point;
typedef vector<point> polygon;


bool contains(const polygon &plg, const point &pt){
	int cnt = 0;
	double y = imag(pt);

	for(int i = 1; i < plg.size(); ++i){
		double dyi = imag(plg[i]) - y;
		double dyj = y - imag(plg[i-1]);
		double tx = (dyi * real(plg[i-1]) + dyj * real(plg[i])) / (dyi + dyj);

		if(imag(plg[i]) >= y && imag(plg[i-1]) < y){
			if( tx < real(pt) ) ++cnt;
		}
		else if(imag(plg[i]) < y && imag(plg[i-1]) >= y){
			if( tx < real(pt) ) ++cnt;
		}
	}
	
	return (cnt % 2 != 0);
}


int main(){
	int n;
	int x, y;
	vector<point> tri(4);
	
	for(scanf("%d", &n); n--; ){
		for(int i = 0; i < 3; ++i){
			scanf("%d%d", &x, &y);
			tri[i] = point(x, y);
		}
		tri[3] = tri[0];

		scanf("%d%d", &x, &y);
		point pk(x, y);
		scanf("%d%d", &x, &y);
		point ps(x, y);
		
		if( contains(tri, pk) != contains(tri, ps) ){
			puts("OK");
		}
		else{
			puts("NG");
		}
	}
}

Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3001;
int dp[maxn][maxn][2];
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int>a(n + 1);
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j < maxn; j++) {
			dp[i][j][0] = LLONG_MIN;
			dp[i][j][1] = LLONG_MAX;
		}
	}
	for (int i = 1; i <= n; i++) {
		dp[i][i][0] = a[i];
		dp[i][i][1] = -a[i];
	}
	for (int len = 1; len <= n - 1; len++) {
		for (int l = 1; l <= n; l++) {
			int r = l + len;
			if (r > n)continue;
			dp[l][r][0] = max(dp[l][r][0], dp[l + 1][r][1] + a[l]);
			dp[l][r][0] = max(dp[l][r][0], dp[l][r - 1][1] + a[r]);
			dp[l][r][1] = min(dp[l][r][1], dp[l + 1][r][0] - a[l]);
			dp[l][r][1] = min(dp[l][r][1], dp[l][r - 1][0] - a[r]);
		}
	}
	cout << dp[1][n][0];
	return 0;
}

Measured memory_bytes: 141056
#!python3

# input
N, K = list(map(int, input().split()))
D = [None] * K
A = []
for i in range(K):
    D[i] = int(input())
    A.append(list(map(int, input().split())))


def main():
    s = {i for i in range(1, N + 1)}
    for l in A:
        for a in l:
            if a in s:
                s.remove(a)

    ans = len(s)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define all(ppp) ppp.begin(),ppp.end()
#define out(ppp) cout<<(ppp)<<endl
#define out1(ppp) cout<<(ppp) 
#define MAX_CHAR 256

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define pb push_back

typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<vpi> vvpi;

typedef set<pi> spi;

const int INF=INT_MAX;


int main(){
    int n;
    cin>>n;
    vi vt(n);
    F0R(i,n) cin>>vt[i];

    int count=0;
    FOR(i,1,n-1){
        if(vt[i]!=min({vt[i-1],vt[i],vt[i+1]})&&vt[i]!=max({vt[i],vt[i-1],vt[i+1]})){
            count++;
        }
    }
    out(count);
}


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

using namespace std;

const int N = 4e5 + 5;
const int mod = 1e9 + 7;

long long f[N], fc[N], dp[N], ans;
int h, w, n;
pair <int, int> a[N];

int bp(int a, int n){
    long long ret = 1;
    while(n){
        if(n & 1){
            ret = (ret * a) % mod;
        }
        a = (a * 1ll * a) % mod;
        n >>= 1;
    }
    return ret;
}

int cnk(int n, int m){
    return (((f[n + m - 2] * fc[n - 1]) % mod) * fc[m - 1]) % mod;
}

int main(){
    f[0] = fc[0] = 1;

    for(int i = 1; i < N; i ++){
        f[i] = (f[i - 1] * i) % mod;
        fc[i] = bp(f[i], mod - 2);
    }

    cin >> h >> w >> n;

    ans = cnk(h, w);

    for(int i = 1; i <= n; i ++){
        cin >> a[i].first >> a[i].second;
    }

    sort(a + 1, a + n + 1);

    for(int i = 1; i <= n; i ++){
        dp[i] = cnk(a[i].first, a[i].second);
        for(int j = 1; j <= n; j ++){
            if(i == j)
                continue;
            if(a[j].first <= a[i].first && a[j].second <= a[i].second){
                dp[i] -= (dp[j] * cnk(a[i].first - a[j].first + 1, a[i].second - a[j].second + 1)) % mod;
                dp[i] = (dp[i] + mod) % mod;
            }
        }
        long long ret = (dp[i] * cnk(h - a[i].first + 1, w - a[i].second + 1)) % mod;
        ans = (ans - ret + mod) % mod;
    }

    cout << ans << endl;
}


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

#define REP(i, a, b) for(int i = a; i < b; i++)

typedef long long llint;

const int mod = 998244353;
const int maxn = 300100;

llint  n, a, b;
llint k;

llint y;

llint rj = 0;

llint fakt[maxn];

llint pot(llint baza, llint eks)
{
    llint ret = 1;
    llint trbaza = baza;
    while(eks)
    {
        if(eks & 1)
        {
            ret *= trbaza;
            ret %= mod;
        }
        trbaza *= trbaza;
        trbaza %= mod;
        eks >>= 1;
    }
    return ret;
}

llint pov(llint apov, llint bpov)
{
    return fakt[apov] * pot(fakt[bpov] * fakt[apov - bpov] % mod, mod - 2) % mod;
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &a, &b, &k);
    fakt[0] = 1;
    REP(i, 1, maxn)
    {
        fakt[i] = fakt[i - 1] * i % mod;
    }
    REP(x, 0, n + 1)
    {
        if((k - x * a) % b == 0 && (k - x * a) / b >= 0)
        {
            y = (k - x * a) / b;
            if(x > n || y > n || y < 0) continue;
            rj += pov(n, x) * pov(n, y);
            rj %= mod;
        }
    }
    printf("%lld\n", rj);
    return 0;
}


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

int main()
{
		int W,H,x,y,r;

		cin >> W >> H >> x >> y >> r;

		//?°´??????????????????
		if (x - r < 0)
				cout << "No\n";
		else if (x + r > W)
				cout << "No\n";
		else {
				//?????´???????????????
				if (y - r < 0)
						cout << "No\n";
				else if (y + r > H)
						cout << "No\n";
				else 
						cout << "Yes\n";
		}

		return 0;
}

Measured memory_bytes: 3068
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

printList :: Show a => [a] -> IO ()
printList = putStrLn.unwords.(map show)

main :: IO ()
main = do
    n   <- getLine >>= \n -> return (read n :: Int)
    lst <- getLine >>= return.(map (\m -> read m :: Int)).words
    printList $ reverse' lst


Measured memory_bytes: 4132
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <bitset>

using ll = long long int;
using ul = unsigned long long int;

namespace lamlib
{
	// Absolute
	template<class T> inline T abs(const T &a){ return (a>0) ? a : -a; }
	// GCD: a > b
	ul gcd(ul a,ul b) { return (!b) ? a : gcd(b,a%b); }
}

int main(int argc,char *argv[])
{
	int n;
	std::cin >> n;

	ll ans = 0;
	ll ans_num = 1;
	for(int i = 2;i <= n;i+=2)
	{
		ll tmp = 0;
		for(int j = i;j > 1;j/=2)
		{
			if(j%2 != 0) break;
			++tmp;
		}
		if(tmp > ans) ans = tmp, ans_num = i;
	}

	std::cout << ans_num << std::endl;

	return 0;
}

Measured memory_bytes: 256
module MakeBinaryHeap (M : sig type t val compare : t -> t -> int end) = struct

  type t = { node : M.t array; mutable size : int }

  let make n (init : M.t) = { node = Array.make n init; size = 0 }

  let empty_p t = if t.size = 0 then true else false

  let pop t =
    if t.size <= 0 then failwith "out of size" else
    let rec max_heapify i =
      let l = 2*i in
      let r = 2*i + 1 in
      let m = if l <= t.size && M.compare t.node.(l) t.node.(i) > 0 then l else i in
      let m = if r <= t.size && M.compare t.node.(r) t.node.(m) > 0 then r else m in
      if m = i then ()
      else begin
        let tmp = t.node.(i) in
        t.node.(i) <- t.node.(m);
        t.node.(m) <- tmp;
        max_heapify m
      end in
    let ret = t.node.(1) in
    t.node.(1) <- t.node.(t.size);
    t.size <- t.size - 1;
    max_heapify 1;
    ret

  let push x t =
    let parent i = int_of_float (floor (float_of_int i) /. 2.) in
    let rec doit i =
      let p = parent i in
      if i <= 1 || M.compare t.node.(p) t.node.(i) >= 0 then ()
      else begin
        let tmp = t.node.(i) in
        t.node.(i) <- t.node.(p);
        t.node.(p) <- tmp;
        doit p
      end in
    t.size <- t.size + 1;
    t.node.(t.size) <- x;
    doit t.size

end

module H = MakeBinaryHeap(struct type t = (int * int) let compare (_, x) (_, y) = y - x end)

let dijkstra g n =
  let reached_p = Array.make n false in
  let d = Array.make n max_int in
  d.(0) <- 0;
  let h = H.make 100000 (0, 0) in (* ??£?¢???????500000???????±????????????§??¢??????????¨??????????????????? *)
  H.push (0, 0) h;
  while not (H.empty_p h) do
    let (u, x) = H.pop h in
    if x > d.(u) then ()
    else begin
      reached_p.(u) <- true;
      List.iter (fun (v, c) ->
        let x = d.(u) + c in
        if not reached_p.(v) && x < d.(v) then begin
          d.(v) <- x;
          H.push (v, x) h;
        end) g.(u)
    end
  done;
  d

let rec make_pair acc = function
  | [] -> acc
  | v :: c :: tl -> make_pair ((v, c) :: acc) tl
  | _ -> assert false

let make_pair lst = make_pair [] lst

let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let n = read_int () in
  let g = Array.make n [] in
  for _ = 0 to n - 1 do
    match read_line () |> split_on_char ' ' |> List.map int_of_string with
    | u :: _ :: l -> g.(u) <- make_pair l
    | _ -> assert false
  done;
  dijkstra g n |> Array.iteri (fun i e -> Printf.printf "%d %d\n" i e)

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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;

vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != -1) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find algo with array
// Find()
int findpar(int curr, int arr[])
{
  while(arr[curr] != curr) curr = arr[curr];
  return curr;
}
// Union()
void Union(int b, int spa, int arr[])
{
  while(arr[b] != b)
  {
    int c = arr[b];
    arr[b] = spa;
    b = c;
  }
  arr[b] = spa;
}

// Main Code

int main()
{
  ll n, m;
  cin>>n>>m;
  ll ans = 0;
  ll total = n*2;
  if(total >= m)
  {
    cout<<m/2<<endl;
  }
  else
  {
    ll ans = n;
    m = m - n*2;
    ans += m / 4;
    cout<<ans<<endl;
  }
  return 0;
}


Measured memory_bytes: 12160
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <iomanip>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")

#define DEBUG(x) cout << ">> " << #x << ": " << x << endl;
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
typedef long long ll;
typedef long double ld;

ld dp[310][310][310];

int main() { _
  int n; cin >> n;
  vector<int> v(3, 0);
  for (int i = 0; i < n; i++) {
    int tmp; cin >> tmp;
    v[tmp-1]++;
  }

  for (int c = 0; c <= v[2]; c++) {
    for (int b = 0; b <= v[1]+v[2]; b++) {
      for (int a = 0; a <= v[0]+v[1]+v[2]; a++) {
        if (a == 0 && b == 0 && c == 0) continue;
        ld move = (ld)n/(ld)(a+b+c);
        
        dp[a][b][c] = (a == 0 ? 0 : a * (dp[a-1][b][c] + move) / (ld)(a+b+c))
                    + (b == 0 || a == v[0]+v[1]+v[2] ? 0 : b * (dp[a+1][b-1][c] + move) / (ld)(a+b+c))
                    + (c == 0 || b == v[1]+v[2] ? 0 : c * (dp[a][b+1][c-1] + move) / (ld)(a+b+c));
      }
    }
  }
  cout << fixed << setprecision(16) << dp[v[0]][v[1]][v[2]] << endl;
  return 0;
}

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

int ball[10];

int  bunbetu(int i, int left, int right) {
	if (i == 10) {
		cout << "YES" << "\n";
		return 0;
	}
	if (ball[i] < left) {
		if (ball[i] < right) {
			cout << "NO" << "\n";
			return 0;
		}
		bunbetu(i + 1, left, ball[i]);
	}
	else bunbetu(i + 1, ball[i], right);
}

int main() {
	int set;
	cin >> set;
	for (int i = 0; i < set; i++) {
		for (int j = 0; j < 10; j++){
			cin >> ball[j];
		}
		bunbetu(0, 0, 0);
	}
	return 0;
}

Measured memory_bytes: 2928
#include <iostream>
using namespace std;
 
int n, a;
 
int main(){
  // 支払いn円、1円硬貨a枚
  cin >> n >> a;
  int oturi = n % 500;
  if(oturi <= a) cout << "Yes" <<endl;
  else cout << "No" << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
typedef long long ll;
const int MAX=1e5+55;
ll x[MAX];
ll dp[MAX];
 ll n;

 int cho2=0;
 ll k;
ll solve(ll i,ll ind)
{
    //cout<<'1'<<" "<<cho1<<" "<<x[i]<<" "<<i<<" "<<last<<endl;

    if(i==n){
        return 0;
    }
    if(i==n-ind)
    return abs(x[i]-x[n]);
    ll &ret=dp[i];
    if(ret!=-1)
        return ret;
        ll cho1=1e12;
    for(ll j=1;j<=k&&(i+j<=n);j++)
    cho1=min(cho1,(abs(x[i]-x[i+j])+solve(i+j,j)));
  //  cho2=abs(x[i]-x[i+2])+solve(i+2);
      //  ret=min(cho1,cho2);
      ret=cho1;
        return ret;




}
int main()
{
 cin>>n>>k;
 memset(dp,-1,sizeof dp);
 for(ll i=1;i<=n;i++)
    cin>>x[i];
 cout<<solve(1,0);

return 0;
}

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

int main() {
  int n,x;
  cin>>n>>x;
  vector<int>a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a.begin(),a.end());
  int ans=0;
  while(x>0 && ans<=n-1){
    if(x-a[ans]==0){
      ans++;
      break;
    }
    else if(x-a[ans]>0 && ans==n-1) break;
    else if(x-a[ans]>0){
      x-=a[ans];
      ans++;
    }
    else break;
  }
  cout<<ans<<endl;
}

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

#define rep(i, k, n) for(int i = (k); i < (n); i++)
#define irep(i, k, n) for(int i = (k); i > (n); i--)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

int main(void){
  int n, m;
  cin >> n >> m;
  priority_queue<int> q;
  rep(i, 0, n){
    int a;
    cin >> a;
    q.push(a);
  };
  

  while(m != 0){
    int t = q.top();
    q.pop();

    t /= 2;
    m--;
    q.push(t);
  }

  ll ans = 0;
  while(!q.empty()){
    ans += q.top();
    q.pop();
  }

  cout << ans << endl;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int n;
    cin>>n;
    double ans = 0.0;
    double val ;
    string s;
    while(n--){
       cin>>val>>s;
       if(s[0] == 'J') ans += val;
       else ans += val * 380000;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <set>

#define int long long

using namespace std;

class Solver {
};

bool dfs(int left, int right, set<int> my, set<int> other) {
	if (other.size() == 0)return false;

	bool win = false;
	if (my.find(left - 1) == my.end() && my.find(right + 1) == my.end()) {
		win |= !dfs(left, right, other, my);
	}
	if (my.find(left - 1) != my.end()) {
		my.erase(left - 1);
		win |= !dfs(left - 1, right, other, my);
		my.emplace(left - 1);
	}
	if (my.find(right + 1) != my.end()) {
		my.erase(right + 1);
		win |= !dfs(left, right + 1, other, my);
		my.emplace(right + 1);
	}

	return win;
}

signed main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		set<int> me;
		for (int j = 0; j < 6; j++) {
			int val;
			cin >> val;
			me.emplace(val);
		}

		set<int> other;
		for (int j = 1; j <= 13; j++) {
			if (j == 7)continue;
			if (me.find(j) == me.end())other.emplace(j);
		}

		if (dfs(7, 7, me, other)) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}
}


Measured memory_bytes: 3112
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int sz=1e5+7;
int a[110][110];
int main()
{
	int H,W,n,i,j,x,y;
	scanf("%d%d",&H,&W); scanf("%d",&n);
	for(i=x=y=1;i<=n;i++)
	{	int c; scanf("%d",&c);
		while(c--)
		{	a[x][y]=i;
			if(x%2)
			{
				if(++y>W){x++; y=W;}
			}
			else
			{
				if(--y<1){x++; y=1;}
			}
		}
	}
	for(i=1;i<=H;i++)
		for(j=1;j<=W;j++)
			printf("%d%c",a[i][j],j<W?' ':'\n');
	return 0;
}


Measured memory_bytes: 384
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

c=0
pb=0
for i in range(n):
    if a[i]>=b[i]+pb:
        c += b[i]+pb
        pb=0
    else :
        c += a[i]
        pb = b[i] + min(pb-a[i],0)
c += min(a[-1],pb)
print(c)

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M;
int A[202020];
int X[202020],Y[202020];

int num[202020];

int buf[404040];
int* cover=&buf[202020];
int ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,N) {
		cin>>A[i];
		num[A[i]]++;
	}
	for(i=1;i<=N;i++) {
		cover[i+1]--;
		cover[i+1-num[i]]++;
	}
	
	for(i=-200000;i<=N;i++) {
		cover[i]+=cover[i-1];
		if(i>=1 && cover[i]==0) ret++;
	}
	
	
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		x=A[X[i]-1];
		cover[x+1-num[x]]--;
		if(cover[x+1-num[x]]==0 && x+1-num[x]>=1) ret++;
		num[x]--;
		
		x=Y[i];
		A[X[i]-1]=x;
		num[x]++;
		cover[x+1-num[x]]++;
		if(cover[x+1-num[x]]==1 && x+1-num[x]>=1) ret--;
		
		cout<<ret<<endl;
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

int string_compar(const void *a, const void *b)
{
    return(strcmp(*(char**)a, *(char**)b));
}
int asc(const void *a, const void *b) {
  return *(int *)a - *(int *)b;
}
int main()
{
    int i,j,n,count[200000] = {0},max = 0;
    char **s;
    s = malloc(sizeof(char*) * 200000);
    for (i = 0; i < 200000; i++)
    {
        s[i] = malloc(sizeof(char) * 11);
    }
    
    scanf("%d",&n);
    for (i = 0; i < n; i++)
    {
        scanf("%s",s[i]);
    }
    qsort((void*)s,n,sizeof(char*),string_compar);

    count[0] = 0;
    int arr_cnt = 1,num_cum = 0;
    for (i = 0; i < n - 1; i++)
    {
        
        if(strcmp(s[i],s[i + 1]) != 0){
            count[arr_cnt] = i + 1;
            arr_cnt++;
        }
    }
    count[arr_cnt] = i + 1;
    arr_cnt++;
    
    for (i = 0; i < arr_cnt; i++)
    {
        if(max < count[i + 1] - count[i])max = count[i + 1] - count[i];
    }
    
    for (i = 0; i < arr_cnt; i++)
    {
        if(count[i + 1] - count[i] == max){printf("%s\n",s[count[i]]);}
    }
    
    //メモリ
    for (i = 0; i < 200000; i++)
    {
        free(s[i]);
    }
    free(s);
}


Measured memory_bytes: 10476
#include<bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i = 0;i < (n);i++)
#define MAX_K 333333
using namespace std;
const int INF = 1e9;
const ll MOD=998244353;
ll n,a,b,k,ans,j,g[300005],ff[300005];

long long mod_div(long long a,long long b){
	if(a % b == 0)return a/b;
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}
vector<long long> kaijo(MAX_K);
long long combination(long long n, long long r){
  if(n < r || n < 0 || r < 0)
    return 0;
	if(kaijo[0] != 1){
		kaijo[0] = 1;
		for(long long i = 1;i < MAX_K;i++)kaijo[i] = (kaijo[i-1] * i) % MOD;
	}
  long long ret = kaijo[n];
	long long tmp = (kaijo[r] * kaijo[n-r]) % MOD;
  return mod_div(ret,tmp);
}

int main(){
  cin>>n>>a>>b>>k;
  if(k==0){cout<<1<<endl;return 0;}
  
  for(ll i=0;i<=n;i++){
    g[i]=combination(n,i);
  }
  for(ll i=0;i<=n;i++){
    if(k>=0 && k%b==0){
      j=(k/b);
      if(j<=n){
	ans=(ans+(g[i]%MOD * g[j]%MOD)%MOD)%MOD;
      }
    }
    k-=a;
  }
  
  cout<<ans%MOD<<endl;
  return 0;
}



Measured memory_bytes: 5504
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        for(int i = 1;;i++){
            int x = sc.nextInt();

            if(x == 0){
                break;
            }

            System.out.println("Case "+ i + ": " + x);
        }
    }
}


Measured memory_bytes: 41676
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Practice
{
    class Program
    {
        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);


        }

        private struct Node
        {
            public int v;
            public int w;
        }
        private const int kWhite = 0;
        private const int kGray = 1;
        private const int kBlack = 2;
        private static int[] color;
        private static int[] d;
        private static Queue<int> Q = new Queue<int>();
        private static void SolveA(string[] args)
        {
            int n = ReadAndParseInt();

            List<Node>[] graph = new List<Node>[n];
            // 初期化
            for (int i = 0; i < n; ++i)
            {
                var list = new List<Node>();

                graph[i] = list;
            }

            for (int i = 0; i < n-1; ++i)
            {
                int[] stw = ReadAndParseIntArr();
                int s = stw[0];
                int t = stw[1];
                int w = stw[2];
                graph[s].Add(new Node() { v = t, w = w });
                graph[t].Add(new Node() { v = s, w = w });
            }
            color = new int[n];
            d = new int[n];
            bfs(0, graph);

            int maxD = d.Max();
            int x = System.Array.FindIndex(d, i => i == maxD);
            bfs(x, graph);
            maxD = d.Max();
            int y = System.Array.FindIndex(d, i => i == maxD);
            Console.WriteLine(maxD);
        }
        private static void bfs(int s,  List<Node>[] graph)
        {
            for(int i = 0; i < color.Length; ++i) { color[i] = kWhite; }
            for (int i = 0; i < d.Length; ++i) { d[i] = int.MaxValue; }
            color[s] = kGray;
            d[s] = 0;
            Q.Enqueue(s);
            while(Q.Count >= 1)
            {
                int u = Q.Dequeue();
                List<Node> list =graph[u];
                foreach(Node node in list)
                {
                    if(color[node.v] == kWhite)
                    {
                        color[node.v] = kGray;
                        d[node.v] = d[u] + node.w;
                        Q.Enqueue(node.v);
                    }
                }
                color[u] = kBlack;
            }
        }
    }
}



Measured memory_bytes: 36424
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

//Provident Housewife
public class Main{

	int[][] dist, wf;
	
	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			Map<String, Integer> ref = new HashMap<String, Integer>();
			int[][] s = new int[n+1][];
			int[][] p = new int[n+1][1000];
			int[] num = new int[n+1];
			int ID = 0;
			for(int i=1;i<=n;i++){
				num[i] = sc.nextInt();
				s[i] = new int[num[i]];
				Arrays.fill(p[i], 1<<29);
				for(int j=0;j<num[i];j++){
					String item = sc.next();
					int id = -1;
					if(ref.containsKey(item))id = ref.get(item);
					else{
						id = ID;
						ref.put(item, ID++);
					}
					p[i][id] = sc.nextInt();
				}
			}
			int q = sc.nextInt();
			int[] need = new int[q];
			boolean enable = true;
			for(int i=0;i<q;i++){
				String item = sc.next();
				if(!ref.containsKey(item)){
					enable = false;
				}
				if(!enable)continue;
				need[i] = ref.get(item);
			}
			wf = new int[n+1][n+1];
			for(int i=0;i<=n;i++)Arrays.fill(wf[i], 1<<29);
			for(int i=0;i<=n;i++)wf[i][i] = 0;
			int m = sc.nextInt();
			for(int i=0;i<m;i++){
				int a = sc.nextInt();
				int b = sc.nextInt();
				int dist = sc.nextInt();
				wf[a][b] = wf[b][a] = dist;
			}
			if(!enable){
				System.out.println("impossible");continue;
			}
			int[] has = new int[n+1];
			for(int i=1;i<=n;i++){
				for(int j=0;j<q;j++){
					if(p[i][need[j]]!=1<<29)has[i]|=1<<j;
				}
			}
			int[] price = new int[1<<(n+1)];
			int Q = (1<<q)-1;
			int opt = 1<<29;
			for(int i=0;i<1<<(n+1);i++){
				int state = 0;
				for(int j=0;j<=n;j++)if((i>>j&1)>0)state|=has[j];
				if(state!=Q){
					price[i] = 1<<29;
					continue;
				}
				int sum = 0;
				for(int j=0;j<q;j++){
					int mm = 1<<24;
					for(int k=1;k<=n;k++){
						if((i>>k&1)==0)continue;
						mm = Math.min(mm, p[k][need[j]]);
					}
					sum += mm;
				}
				price[i] = sum;
				opt = Math.min(opt, price[i]);
			}
			for(int k=0;k<=n;k++){
				for(int i=0;i<=n;i++){
					for(int j=0;j<=n;j++){
						wf[i][j] = Math.min(wf[i][j], wf[i][k]+wf[k][j]);
					}
				}
			}
			dist = new int[1<<(n+1)][n+1];
			for(int i=0;i<1<<n+1;i++)Arrays.fill(dist[i], 1<<29);
			dist[1][0] = 0;
			PriorityQueue<int[]> que = new PriorityQueue<int[]>(n, new Comparator<int[]>() {
				public int compare(int[] o1, int[] o2) {
					return dist[o1[0]][o1[1]]+wf[o1[1]][0]-dist[o2[0]][o2[1]]-wf[o2[1]][0];
				}
			});
			que.add(new int[]{1, 0});
			int min = 1<<29;
			while(!que.isEmpty()){
				int[] a = que.poll();
				int state = a[0];
				int last = a[1];
				if(price[state]==opt){
					min = Math.min(min, dist[state][last]+wf[last][0]);
				}
				for(int i=0;i<=n;i++){
					if(wf[last][i]==1<<29||(state>>i&1)>0)continue;
					int ns = state | 1<<i;
					int v = dist[state][last] + wf[last][i];
					if(v<dist[ns][i]){
						dist[ns][i] = v;
						que.add(new int[]{ns, i});
					}
				}
			}
			System.out.println(opt+" "+min);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,sum=0;
    cin>>a>>b>>c;
    if(a<b)
    {
        sum+=a;
        if(c<b) sum+=c;
        else sum+=b;
    }
    else
    {
        sum+=b;
        if(c<a) sum+=c;
        else sum+=a;
    }
    cout<<sum;
}


Measured memory_bytes: 256
n = int(input())
a = [int(x) for x in input().split()]

ans = 1
up = None

for i in range(n-1):
    if up == None:
        if a[i] == a[i+1]:
            continue
        elif a[i] < a[i+1]:
            up = True
        else:
            up = False
    elif up and a[i] > a[i+1]:
        up = None
        ans += 1
    elif not up and a[i] < a[i+1]:
        up = None
        ans += 1
print(ans)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>
#define Pll pair<ll,ll>

template <class T> void chmin(T&a,const T&b) { a = min(a,b); }
template <class T> void chmax(T&a,const T&b) { a = max(a,b); }
 
void print(){cout<<endl;}
template <class Head, class... Tail>
void print(Head&& h,Tail&&... t){ 
	if(sizeof...(t)==0)
		cout<<h;
	else
		cout<<h<<' ';
	print(move(t)...);
}
 
const double EPS =1e-9;
const int INF =2e+9;
const ll INFL =9e+18;
const long MOD =1e+9+7;
#define PI 3.14159265258979

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

int main(void){
	int N,p,tem;
	cin>>N>>p;

	REP(i,N){
		cin>>tem;
		if(tem%2){
			cout<<(ll)pow(2.0,N-1)<<endl;
			return 0;
		}
	}
	if(p==1) print(0);
	else cout<<(ll)pow(2.0,N)<<endl;
	return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int a, b, c;
    cin >> a >> b >> c;

    int ans = abs(a * b * (c/2) - a * b * ((c + 1)/2));
    ans = min(ans, abs(b * c * (a/2) - b * c * ((a + 1)/2)));
    ans = min(ans, abs(a * c * (b/2) - a * c * ((b + 1)/2)));
    cout << ans << endl;

}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

ch-=1; cw-=1; dh-=1; dw-=1

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-2, -2),(-2, -1),(-2, 0),(-2, 1),(-2, 2),
 (-1, -2),(-1, -1),(-1, 1),(-1, 2),
 (0, -2),(0, 2),
 (1, -2),(1, -1),(1, 1),(1, 2),
 (2, -2),(2, -1),(2, 0),(2, 1),(2, 2)]

for i in range(h):
    m[i] = ['#']*2 + m[i] + ['#']*2
    
m = [['#']*(w+4)]*2 + m + [['#']*(w+4)]*2
ch+=2; cw+=2; dh+=2; dw+=2

def bfs4():
    '''
    bfs3とほぼ同じ. 迷路の上下左右に2列ずつ壁追加
    '''
    que1=[]
    que2=[] # queueというよりはメモリ
    m[ch][cw]=str(0)
    que1.append((ch,cw))

    while que1!=[]:
        l1=len(que1)
        r1=0 # que1における使用済みindex

        # que1の要素(座標)から歩いていけるマス
        while r1<l1:
            i, j=que1[r1]
            r1+=1
            # 隣接したマスへの移動
            for si, sj in ad:
                if m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    l1+=1

        # 歩いていけないマス
        for i,j in que1:
            for si, sj in warp:
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    que2.append((i+si, j+sj))

        que1=que2
        que2=[]
###---------------------------------------

bfs4()


if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Measured memory_bytes: 29336
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define mod 1000000007
#define FT() int t; scanf("%d",&t); while(t--)
#define pb push_back
#define nl printf("\n")
#define fi(i,start,end) for(int i=start; i < (int)end ; ++i)
#define ip(n)   scanf("%d",&n)
#define mz(a)   memset(a,0,sizeof(a))
#define inpArr(A,n) fi(i,0,n)   ip(A[i]);
#define print(a)  for(auto i : a)   cout<<i<<" "; nl;
#define Fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
ll max(ll a,ll b)   {return a>b?a:b;}
ll min(ll a,ll b)   {return a<b?a:b;}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("D:/Sublime/Rough/input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #endif
    //std::cout << std::fixed;
    //std::cout << std::setprecision(6);
    Fastio;
    int testcase = 1;
    string s;
    cin>>s;
    int t = (s[0] == 'R');
    int mx = max(0,t);
    for(int i=1;i<s.length();i++)
        {  
            if(s[i] == 'R' && s[i] == s[i-1])
                t++;
            else if(s[i] == 'R')
                t = 1;
            else
                t = 0;
                
            mx = max(mx,t);
        }
    cout<<mx;

    #ifndef ONLINE_JUDGE
    cout<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s";
    #endif
    
    return 0;
}

Measured memory_bytes: 3644
N,x = map(int,input().split())
if x==1 or x==2*N-1:
    print("No")
else:
    print("Yes")
    l = [i for i in range(1,2*N)]
    l.remove(x-1)
    l.remove(x)
    l.remove(x+1)
    for i in range(N-2):
        print(l[i])
    print(x-1)
    print(x)
    print(x+1)
    for i in range(N-2):
        print(l[N-2+i])

Measured memory_bytes: 52464
N = int(input())

def ryuca_memo(n):
    memo = [0]*(n+1)
    def _ryuca(n):
        if n == 1:
            return 1
        elif n == 0:
            return 2
        if memo[n] != 0:
            return memo[n]
        memo[n] = _ryuca(n-1) + _ryuca(n-2)
        return memo[n]
    return _ryuca(n)

print(ryuca_memo(N))


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

ll gcd(ll a,ll b){
	return b ?gcd(b,a%b) :a;
}

bool isp(ll x){
	for(ll i = 2;i <= sqrt(x);++i){
		if(x % i == 0) return 0;
	}
	return 1;
}

int main()
{
	ll a,b,ans = 0;
	scanf("%lld%lld",&a,&b);
	ll k = gcd(a,b);
	for(ll i = 1;i <= sqrt(k);++i){
		if(k % i == 0){
			if(isp(i)) ans++;
			if(isp(k/i)) ans++;
		}
	}
	printf("%lld",k == 1 ?1 :ans);
	return 0;
}

Measured memory_bytes: 256
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define  mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------
ll c[110][110];
int n;
void warshall_floyd(){
  for (int k = 0; k < n; k++){       // 経由する頂点
    for (int i = 0; i < n; i++) {    // 始点
        if(c[i][k]==INF)continue;
      for (int j = 0; j < n; j++) {  // 終点
          if(c[k][j]==INF)continue;
        chmin(c[i][j], c[i][k] + c[k][j]);
      }
    }
  }
}

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int m;cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(i==j)
                c[i][j]=0;
            else
                c[i][j]=INF;
        }
            
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        ll cd;
        cin>>cd;
        c[a][b]=cd;
        
    }
    warshall_floyd();
    for(int i=0;i<n;i++){
        if(c[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            return 0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(c[i][j]!=INF)
                cout<<c[i][j];
            else
                cout<<"INF";
            if(j<n-1)cout<<" ";
        }
        cout<<endl;
    }
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------







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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    string s; cin >> s;
    int res1 = 0;
    rep(i, s.size()){
        if(i%2 == s[i]-'0'){
            res1++;
        }
    }
    
    int res2 = 0;
    rep(i, s.size()){
        if(i%2 != s[i]-'0'){
            res2++;
        }
    }

    cout << min(res1, res2) << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

using namespace std;
int main(void){
    // Your code here!
    int n;
    int a;
    int b;
    
    cin >> n;
    cin >> a;
    cin >> b;
    
    int n1 = 0;
    int n2 = 0;
    int n3 = 0;
    
    for (int i=0; i<n; i++) {
        int t;
        cin >> t;
        if (t <= a) {
            n1++;
        } else if (t <= b) {
            n2++;
        } else {
            n3++;
        }
    }
    
    int ans = n1;
    if (ans > n2) {
        ans = n2;
    }
    if (ans > n3) {
        ans = n3;
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
<?php
//error_reporting(0);
//$X = explode(" ",trim(fgets(STDIN)));
$A = trim(fgets(STDIN));
$B = trim(fgets(STDIN));
$C = trim(fgets(STDIN));
$X = trim(fgets(STDIN));
//list($r,$c) =  explode(" ",trim(fgets(STDIN)));
$r = array();
for($i=0;$i<=$A;$i++) {
  for($j=0;$j<=$B;$j++) {
    for($k=0;$k<=$C;$k++) {
      if (($i*500+$j*100+$k*50)==$X) {
        $r[]=$i.",".$j.",".$k;
      }
    }
  }
}
printf("%d\n",count($r));


Measured memory_bytes: 3700
import numpy as np
n = int(input())

status = np.zeros((n + 1, 3), dtype=np.int)
for i in range(n):
    status[i + 1, :] = list(map(int, input().split()))

diff = np.diff(status, axis=0)
time = diff[:, 0]
step = np.sum(diff[:, 1:], axis=1)

if all(step <= time) and all(step % 2 == time % 2):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 19612
import sys
from itertools import combinations
def input():
	return sys.stdin.readline()[:-1]
n, m = map(int, input().split())
keys = []
for _ in range(m):
	a, b = map(int, input().split())
	c = list(map(int, input().split()))
	keys.append([a, sum([1<<(x-1) for x in c])])
dp = [10**30 for _ in range(1<<n)]
dp[0] = 0

for c, v in keys:
	dp[v] = dp[0]+c

for j in range(1<<n):
	for c, v in keys:
		dp[j|v] = min(dp[j|v], dp[j]+c)

if dp[(1<<n)-1] > 10**20:
	print(-1)
else:
	print(dp[(1<<n)-1])

Measured memory_bytes: 42476
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 100;
int n,m,tot;
int a[N],b[N];
int ans[N];
int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    for (int i = n; i >= 1; --i)
    {
        int s = 0;
        for (int j = i + i; j <= n; j += i)
            s += b[j];
        if (s % 2 != a[i])
            b[i] = 1,ans[tot++]= i;
    }
    if (!tot)
    {
        puts("0");
        return 0;
    }
    printf("%d\n", tot);
    printf("%d", ans[0]);
    for (int i = 1; i < tot; ++i)
        printf(" %d", ans[i]);
    puts("");
    return 0;
}

Measured memory_bytes: 9728
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <cstdlib>
#include <stack>
#include <queue>
#include <list>
#include <vector>

using namespace std;

class c_counting
{
private:

public:
    c_counting();
    void f_input();
};

c_counting::c_counting()
{

}

void c_counting::f_input()
{
    int n;
    int i;
    int j;
    int m;
    int d_max;
    static int a[2000000];
    static int c[2000000];
    
    cin >> n;
    
    d_max = 0;
    
    for ( i = 0; i < n; ++i){
        cin >> a[i];
        if (d_max < a[i])d_max =a[i];
    }
    
    for ( i = 0; i < d_max + 1; ++i){
        c[i] = 0;
    }
    
    for ( i = 0; i < n; ++i){
        c[a[i]] = c[a[i]] + 1;
    }
    
    /*
    cout << endl;
    
    for ( i = 0; i < d_max + 1; ++i){
        cout << c[i] << endl;
    }
    
    cout << endl;
    */
    m = 0;
    for ( i = 0; i <= d_max + 1; ++i){
        
        for ( j = 0; j < c[i]; ++j){
            if ( c[i] > 0 ){
                if ( m == n-1 ){
                    cout << i << endl;
                }else{
                    cout << i << " ";
                    ++m;
                }
            }
        }
    }
}

int main(){
    
    c_counting counting01;
    counting01.f_input();
    
    return 0;
}

Measured memory_bytes: 10908
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
long long n,tmp,tmp2,a[1311];
int main(){
    cin>>n;
    tmp=1;tmp2=0;
    if(n==0){
    	cout<<0;
    	return 0;
	}
    while(n){
    	if(n%abs(tmp*2)==0)a[++tmp2]=0,tmp*=-2;
    	else {
    		a[++tmp2]=1;
    		n-=tmp;tmp*=-2;
		}
		//cout<<n<<" "<<tmp<<endl;
	}
	for(int i=tmp2;i>=1;i--)cout<<a[i];
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int a,b,c,re=0,rh=0;
    for(;scanf("%d,%d,%d",&a,&b,&c)!=EOF;){
        if(a==b)
            rh++;
        else if(a*a+b*b == c*c)
            re++;
    }
    printf("%d\n%d\n",re,rh);
    return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int N,a;
  cin>>N;
  a=N%1000;
  if (N%1110<10|N%1111==0|a%111==0){
    cout<<"Yes"<<endl;
  }
  else {
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))

mod = 10**9 + 7
total = 0
for i in range(60):
  cnt = sum([1 for a in A if (a>>i & 1)])
  total += cnt * (n-cnt) * (1 << i)
  total %= mod
print(total)


Measured memory_bytes: 44204
#include <bits/stdc++.h>
using namespace std;
long long a , b , h;
string s;
int main()
{

    /*cin >> s;
    n =s.size();
    for (int i= 0; i< n ; i++)
    {
       for (int j = i + 1 ; )
    }
    */
    cin >> a >> b >> h;
    cout << ((a + b) * h) / 2;
}




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

//{{{
#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef LOCAL
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

int T;

const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int a[N];
int n;

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif

    while (cin >> n)
    {
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + 1 + n, greater<int>());

        LL ans = 0;
        for (int i = 2; i <= n; ++i)
        {
            ans += a[(i + 1) / 2];
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 4440