akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
 ll n;
 cin >>n;
 ll x[n],k[n];
 for(ll i=0;i<n;i++) {
   cin >>x[i];
   k[i]=x[i];
 }
 sort(x,x+n);
 ll s=x[(n/2)-1],p=x[n/2];
 for(ll i=0;i<n;i++){
   if(k[i]<=s) cout <<p<<endl;
   else cout <<s<<endl;
 }
}


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

int main() {
    int N, M; cin >> N >> M;
    auto mp = vector<int>((1<<8) + 1, 0);
    for (int i = 0; i < M; ++i) {
        int a; cin >> a;
        ++mp[a];
    }
    vector<int> v;
    for (int i = 0; i < N; ++i) if (!mp[i]) v.push_back(i);
    int ans = 0;
    while (v.size() > 1) {
        for (int i = 0; i < v.size(); ++i) v[i] >>= 1;
        for (int i = 0; i <= 1<<8; ++i) {
            int sz = upper_bound(begin(v), end(v), i) - lower_bound(begin(v), end(v), i);
            ans += max(0, sz - 1);
        } 
        v.erase(unique(begin(v), end(v)), end(v));
    }
    cout << ans << endl;
}


Measured memory_bytes: 3120
n, k = map(int, input().split())
T = [[] for _ in range(n)]
E = []
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  E.append((a, b))
d = k//2
def dfs(vs):
  dist = [-1]*n
  stack = []
  cnt = 0
  for v in vs:
    stack.append(v)
    dist[v] = 0
  while stack:
    v = stack.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        if dist[nv] > d:
          cnt += 1
        stack.append(nv)
  return cnt
ans = n
if k%2 == 0:
  for i in range(n):
    ans = min(ans, dfs([i]))
else:
  for l in E:
    ans = min(ans, dfs(l))
print(ans)

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

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

	ll a, b, c;cin >> a >> b >> c;
	cout << (a + b + c < 22 ? "win" : "bust") << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[][] c = new char[H+ 2][W + 2];
		for (int i = 0; i < H; i++) {
			String s = sc.next();
			for (int j = 0; j < W; j++) {
				c[i + 1][j + 1] = s.charAt(j);
			}
		}
		int count = 0;
		for (int i = 0; i < H ; i++) {
			for (int j = 0 ; j < W ; j++) {
				if (c[i + 1][j + 1] == '#' && c[i][j + 1]  != '#' && c[i + 1][j] != '#' && c[i+2][j + 1] != '#' && c[i + 1][j+2] != '#') {
					count++;
				}
			}
		}

		if (count > 0) {
			System.out.println("No");
		} else {
			System.out.println("Yes");
		}

	}

}

Measured memory_bytes: 22868
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int hamming[] = new int[1000001];
		int count;
		
		int index = 1;
		hamming[1] = 1;
		while (index < 1000001) {
			if (index * 2 < 1000001) {
				hamming[index * 2] = 1;
			}
			if (index * 3 < 1000001) {
				hamming[index * 3] = 1;
			}
			if (index * 5 < 1000001) {
				hamming[index * 5] = 1;
			}
			index++;
			while (index < 1000001 && hamming[index] == 0) {
				index++;
			}
		}

		while (true) {
			int x = sc.nextInt();
			if (x == 0) {
				break;
			}
			int y = sc.nextInt();
			count = 0;
			for (int i = x; i <= y; i++) {
				count += hamming[i];
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 16000
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
#include <bitset>
#include<math.h>
#include<queue>
using namespace std;
#define MAX 300000
#define INF 2000000
typedef long long ll;
typedef pair<int,int> P;

int c[1000][1000];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
queue<P> Q;
int dis[1000][1000];


int main(){
  for(int i=0;i<1000;i++){
    for(int j=0;j<1000;j++) dis[i][j]=INF;
  }
  int H,W;
  char temp;
  cin>>H>>W;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>temp;
      if(temp=='#') {
        Q.push(P(i,j));
        dis[i][j]=0;
      }
    }
  }

  while(!Q.empty()){
    P p=Q.front(); Q.pop();
    for(int i=0;i<4;i++){
      int ny=p.first+dy[i]; int nx=p.second+dx[i];

      if(0<=ny && 0<=nx && nx<W && ny<H && dis[ny][nx]==INF){
        Q.push(P(ny,nx));
        dis[ny][nx]=dis[p.first][p.second]+1;
      }
    }
  }
  int ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++)ans=max(ans,dis[i][j]);
  }
  cout<<ans<<endl;

}


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

const int inf = 1e9;
const ll linf = 1e18;

int main()
{
    int n; cin >> n;
    int a[2][105];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j <= i; j++) sum += a[0][j];
        for (int j = i; j <  n; j++) sum += a[1][j];
        ans = max(ans, sum);
    }

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

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

int main() {
	long long X; cin >> X;
	long long g = 100;
	long long st = (long long)(X / g);
	long long pr = X - st * g;
	bool flg = false;

	for (long long k = 5; k > 0; --k) {
		long long n, m;
		n = pr / k;
		if (n > (long long)(X / g)) break;
		st -= n;
		m = pr % k;
		if (!m) {
			flg = true;
			break;
		}
	}
	
	if (flg) cout << "1" << endl;
	else cout << "0" << endl;
}

Measured memory_bytes: 256
inp = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')
l = inp.shift().split(' ')
x = l[0] * 1
y = l[1] * 1
ans = 0
if (x == 1) {
    ans += 300000 
} else if (x == 2) {
    ans += 200000
} else if (x == 3) {
    ans += 100000
}
if (y == 1) {
    ans += 300000 
} else if (y == 2) {
    ans += 200000
} else if (y == 3) {
    ans += 100000
}
if (x == 1 && y == 1) {
    ans += 400000
}
console.log(ans)


Measured memory_bytes: 22332
#include <stdio.h>
#include <math.h>
#define PI 3.14159265
int main(void){
    double a,b,C,S,L,h;
    scanf("%lf %lf %lf",&a,&b,&C);
    S = 1.0/2.0*a*b*sin(C*PI/180.0);
    L = a+b+sqrt(a*a+b*b-2*a*b*cos(C*PI/180.0));
    h = 2.0*S/a;
    printf("%lf\n%lf\n%lf\n",S,L,h);
    return 0;
}


Measured memory_bytes: 2104
/*
 * 	Heart beats fast
 * 		Colors and promises
 * 			How to be brave
 * 				How can I love when I am afraid to fall...
*/
#include<bits/stdc++.h>
// #include<boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
using namespace std;
#define int long long
#define mod 1000000007
#define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define f(i,n) for(int i=0;i<n;i++)
#define fp(i,k,n) for(int i=k;i<=n;i++)
#define fr(i,k,n) for(int i=k;i>=n;i--)
#define pb push_back
#define F first
#define S second

int modExponentiation(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=((res%mod) * (a%mod))%mod;
		b/=2;
		a=((a%mod)*(a%mod))%mod;
	}
	return res;
}
int sumXOR(int arr[], int n) 
{ 
    int sum = 0; 
    for (int i = 0; i < 64; i++)  
    { 
        int zc = 0, oc = 0;  
          
       int idsum = 0;  
        for (int j = 0; j < n; j++) 
        { 
            if (arr[j] % 2 == 0) 
                zc++; 
            else
                oc++; 
            arr[j] /= 2; 
        } 
          
        idsum = ((((oc%mod) * (zc%mod))%mod) * ((modExponentiation(2,i))%mod))%mod;  
  
        sum =((sum%mod)+(idsum%mod))%mod;  
    } 
    return sum; 
} 
void solve()
{
  int n;
  cin >> n;
  int a[n];
  f(i,n)
	cin >>a[i];
  cout << sumXOR(a,n)%mod;
  return;
}
signed main()
{
  FAST;
	int T=1;
	// cin >> T;
	while(T--)
	{
		solve();
	}
    return 0;
}

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

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

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

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

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input! {
        n: usize,
        m: usize,
        p: i64,
        edge: [(usize1, usize1, i64); m],
    }

    let mut dist: Vec<Option<i64>> = vec![None; n];
    dist[0] = Some(0);

    for i in 0..(2 * n + 1) {
        for &(from, to, cost) in &edge {
            if dist[from].is_none() {
                continue;
            }
            if dist[to].is_none() {
                dist[to] = Some(dist[from].unwrap() + cost - p);
            } else {
                let next = std::cmp::max(dist[from].unwrap() + cost - p, dist[to].unwrap());
                if to == n - 1 && i > n && next > dist[to].unwrap() {
                    println!("{}", -1);
                    return;
                }
                dist[to] = Some(next);
            }
        }
    }
    if dist[n - 1].is_some() {
        println!("{}", std::cmp::max(dist[n - 1].unwrap(), 0));
    } else {
        println!("-1");
    }
}


Measured memory_bytes: 4352
N=int(input())
a=map(int,input().split())
a=list(a) 
import numpy as np
count_list=[0]*N
def gcd(a,b):
    c=np.floor(a/b)
    return a-b*c
for i in range(len(a)):
    while gcd(a[i],2)==0:
        count_list[i]+=1
        a[i]=a[i]/2

print(sum(count_list))

Measured memory_bytes: 22016
#include "bits/stdc++.h"
using namespace std;

int main() {
    int A, B, C,D;
    cin >> A >> B >> C >> D;

    if (A + B == C + D) {
        cout << "Balanced" << endl;

    }
    else if (A + B > C + D) {
        cout << "Left" << endl;

    }
    else {
        cout << "Right" << endl;
    }
}



Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
bool us[1000010]={false};
bool p[1000010] = {0};
int main(){
    /*Eratosthenes*/
    p[2] = true;
    for(int i = 0; i <= 50010; i+=2){
        us[i] = true;
    }
     
    int cnt = 1;
    for(int i = 3; i <= 50010; i+=2){
        int q = 0;
        if(us[i] == true)continue;
        else if(us[i] == false){
            p[i] = true;
            us[i] = true;
            q = i;
            for(int j = q+q; j <= 50010; j += q){
                us[j] = true;
            }
        }
    }
     
    int n;
    while(scanf("%d",&n),n){
        int x = 0;
        for(int i = 2; i <= n/2; i++){
            if(p[i] && p[n-i]){
                x++;
            }
        }
        printf("%d\n",x);
    }
    return 0;
}

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

int main(){
        
    int n;
    double hist[6]={0};
    double h;
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> h;
        if(h<165)hist[0]++;
        else if(h<170)hist[1]++;
        else if(h<175)hist[2]++;
        else if(h<180)hist[3]++;
        else if(h<185)hist[4]++;
        else    hist[5]++;
    }

    for(int i=0; i<6; i++){
        cout << i+1 << ":";    
        for(int j=0; j<hist[i]; j++)cout<<"*";
        cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3136
// -*- coding:utf-8-unix -*-

use num::Float;
use proconio::input;
use std::cmp::Ordering;
use std::collections::VecDeque;
use std::collections::{BTreeSet, HashSet};
use std::io::*;
use std::str::FromStr;
// ABC086C - Traveling
// https://atcoder.jp/contests/abs/fasks/arc089_a

fn switch<T>(flag: bool, t: T, f: T) -> T {
    if flag {
        t
    } else {
        f
    }
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
#[allow(dead_code)]
fn read_string() -> Vec<char> {
    read::<String>().chars().collect()
}
#[allow(dead_code)]
fn read_vector<T: FromStr>(number: usize) -> Vec<T> {
    (0..number).map(|_| read()).collect()
}

fn main() {
    let (x, n): (i32, usize) = (read(), read());
    let ps: Vec<i32> = read_vector(n);

    let value: i32 = (0..102)
        .into_iter()
        .filter(|&y| !ps.contains(&y))
        .min_by(|a: &i32, b: &i32| {
            let a2 = (a - x) * (a - x);
            let b2 = (b - x) * (b - x);
            if a2 == b2 {
                a.cmp(b)
            } else if a2 < b2 {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        })
        .unwrap();

    println!("{}", value);
}


Measured memory_bytes: 2116
#include <bits/stdc++.h>
                using namespace std;
                typedef long long ll;
                #define INPUT()              freopen("input.txt", "r", stdin)
                #define OUTPUT()             freopen("output.txt", "w", stdout)
                #define F                    first
                #define S                    second
            //Templatefunctions
                template<typename T>T gcd(T x, T y) { if (y == 0)return x; else return gcd(y, x%y);}
                template <class T> T euclideanDistance(T x1 , T x2 , T y1 , T y2){return sqrt(( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 ));}
                template <class T> T digitSum(T n){T sum = 0;while(n > 0)sum += n % 10,n /= 10;return sum;}
            //datatypes
                typedef long long int ll;
                typedef unsigned long long int ull;
                typedef long double ld;
            //constants
                const double INF = 1e+9;
                const double INFLL = 1e+18;
                const double EPS = 1e-9;
                const double PI = acos(-1);
                const int knightDir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2}};
                       //const int dx[]={0,0,0,1,1,1,-1,-1,-1};
                       //const int dy[]={-1,0,1,-1,0,1,-1,0,1};
                const int dx[] = {0 , 1 , 0 , -1};
                const int dy[] = {1 , 0 , -1 , 0};
            //helpers
                //#define MOD         1000000007LL
                #define MAX         1000005
                const ll MOD = 1000000000 + 7;
                int arr[MAX];
                char str[MAX+10];
            //Global Variables
                int price[MAX] = {0 , 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 , 24 , 30};
                int dp[MAX],n;
                int main()
                {
                   ll a;
                   scanf("%lld",&a);

                    if(a % 11 == 0)
                    {
                        printf("%lld\n",(a/11)*2);
                    }
                    else if(a % 11 > 6) printf("%lld\n",(a/11)*2+2);
                    else printf("%lld\n",(a/11)*2+1);


                }


Measured memory_bytes: 256
import sys

def solve():
      input = sys.stdin.readline
      N, M = map(int, input().split())
      A = [int(a) for a in input().split()]
      A.sort(reverse = True)
      total = sum(A)
      for i in range(M):
            if A[i] * 4 * M < total:
                  print("No")
                  break
      else: print("Yes")

      return 0

if __name__ == "__main__":
      solve()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
    #define REP(i,n) for(int i=0;i<n;i++)
    #define LOOP(i,x,n) for(int i=x;i<n;i++)
    #define ALL(v) (v).begin(),(v).end()
    #define PB push_back
    #define MP make_pair
    #define FIR first
    #define SEC second
    #define int long long
    using namespace std;
    const int MOD=1000000007;
    const int INF=1000000009;
     
    signed main(){
      int n;
      cin>>n;
      vector<int> v(1000000);
      v[0]=2;
      v[1]=1;
      LOOP(i,2,1000000){
        v[i]  =v[i-1]+v[i-2];
      }
      cout<<v[n]<<endl;
      return 0;
    }

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

int main() {  
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,W;
	cin>>n>>W;
	vector<int> w(n),v(n);
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	vector<vector<ll>> dp(n+1, vector<ll>(W+1, 0));
	for(int i=0;i<n;i++){
		for(int cur_w=0;cur_w<=W;cur_w++){
			dp[i+1][cur_w] = max(dp[i+1][cur_w], dp[i][cur_w]);
			int nxt_w = cur_w + w[i];
			if(nxt_w<=W){
				dp[i+1][nxt_w] = max(dp[i+1][nxt_w], dp[i][cur_w] + v[i]);
			}
		}
	}
	cout<<*max_element(dp[n].begin(),dp[n].end());
	return 0;  
}


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

int main()
{
	int m, f, r;
	while (true) {
		cin >> m >> f >> r;
		if (m == -1 && f == -1 & r == -1) break;
		if ((m == -1 || f == -1) || (m + f < 30)) cout << "F" << "\n";
		else if (m + f >= 80) cout << "A" << "\n";
		else if (m + f >= 65) cout << "B" << "\n";
		else if (m + f >= 50) cout << "C" << "\n";
		else if (r < 50) cout << "D" << "\n";
		else cout << "C" << "\n";
	}
}


Measured memory_bytes: 3104
using System;

namespace M_solutions2020
{
    class Program
    {
        static void Main(string[] args)
        {
            a();
        }

        public static void a()
        {
            int x = int.Parse(Console.ReadLine());
            if(x >= 1800)
            { 
                Console.WriteLine("1");
            }
            else if(x >= 1600)
            {
                Console.WriteLine("2");
            }
            else if(x >= 1400)
            {
                Console.WriteLine("3");
            }
            else if(x >= 1200)
            {
                Console.WriteLine("4");
            }
            else if(x >= 1000)
            {
                Console.WriteLine("5");
            }
            else if(x >= 800)
            {
                Console.WriteLine("6");
            }
            else if(x >= 600)
            {
                Console.WriteLine("7");
            }
            else 
            { Console.WriteLine("8"); }
        }
    }
}


Measured memory_bytes: 27476
#include <bits/stdc++.h>
using namespace std;
char s[107], t[107], p[107];

int main() {
	scanf("%s %s %s", s, t, p);
	int tmp = 'a' - 'A';
	printf("%c%c%c\n", s[0] - tmp, t[0] - tmp, p[0] - tmp);
}

Measured memory_bytes: 384
import java.io.PrintWriter

val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val n = nextInt()
    println(n/3)
}

fun next() = readLine()!!
fun nextInt() = next().toInt()

fun println(value : Any) {
    pw.println(value)
}

Measured memory_bytes: 31696
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = map(int, input().split())
    X[i], Y[i] = sorted([x, y])

ans = (max(X)-min(X)) * (max(Y)-min(Y))


L = []
for i, x in enumerate(X):
    L.append((x, i))
for i, y in enumerate(Y):
    L.append((y, i))
L.sort()

checker = [0]*N
cnt = 0
mi = float("inf")
j = 0
for xy, n in L:
    if checker[n] == 0:
        cnt += 1
        checker[n] = 1
    else:
        checker[n] = 2
    if cnt!=N:
        continue
    else:
        while True:
            xy2, n2 = L[j]
            if checker[n2] == 2:
                checker[n2] = 1
                j += 1
            else:
                break
        mi = min(mi, xy-xy2)

print(min(ans, mi*(max(Y)-min(X))))


Measured memory_bytes: 62940
#include <algorithm>
#include <cstring>
#include <cstdio>
int lst[200005], to[800005], pre[800005], cap[800005], tot;
int dep[200005], fst[200005], que[200005];
inline void add_edge(int u, int v, int _cap)
{
	to[tot] = v;
	pre[tot] = lst[u];
	cap[tot] = _cap;
	lst[u] = tot++;
	to[tot] = u;
	pre[tot] = lst[v];
	cap[tot] = 0;
	lst[v] = tot++;
}
inline bool bfs(int s, int t)
{
	int he = 0, ta = 1;
	que[0] = s;
	memset(dep, -1, sizeof(dep));
	dep[s] = 0;
	while (he < ta)
	{
		int u = que[he++];
		for (int i = lst[u]; ~i; i = pre[i])
		{
			if (cap[i] && dep[to[i]] == -1)
			{
				dep[to[i]] = dep[u] + 1;
				que[ta++] = to[i];
			}
		}
	}
	return dep[t] != -1;
}
int dfs(int u, int t, int mx)
{
	if (u == t)
		return mx;
	int ans = 0;
	for (int &i = fst[u]; ~i && ans < mx; i = pre[i])
	{
		if (cap[i] && dep[to[i]] == dep[u] + 1)
		{
			int res = dfs(to[i], t, std::min(mx - ans, cap[i]));
			cap[i] -= res;
			cap[i ^ 1] += res;
			ans += res;
		}
	}
	if (!ans)
		dep[u] = -1;
	return ans;
}
inline int dinic(int s, int t)
{
	int ans = 0;
	while (bfs(s, t))
	{
		memcpy(fst, lst, sizeof(lst));
		ans += dfs(s, t, 1e9);
	}
	return ans;
}
int a[100005], b[100005], bel_l[100005], bel_r[100005];
bool vis[100005];
int main()
{
	// freopen("AGC038-F.in", "r", stdin);
	memset(lst, -1, sizeof(lst));
	int n, L = 0, R = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	for (int i = 0; i < n; i++)
	{
		if (vis[i])
			continue;
		for (int x = i; !vis[x]; x = a[x])
		{
			bel_l[x] = L;
			vis[x] = true;
		}
		L++;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", b + i);
		vis[i] = false;
	}
	for (int i = 0; i < n; i++)
	{
		if (vis[i])
			continue;
		for (int x = i; !vis[x]; x = b[x])
		{
			bel_r[x] = R;
			vis[x] = true;
		}
		R++;
	}
	int base = n;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == i && b[i] == i)
			base--;
		else if (a[i] == i)
			add_edge(bel_r[i] + L + 1, L + R + 1, 1);
		else if (b[i] == i)
			add_edge(0, bel_l[i] + 1, 1);
		else
		{
			add_edge(bel_r[i] + L + 1, bel_l[i] + 1, 1);
			if (a[i] == b[i])
				add_edge(bel_l[i] + 1, bel_r[i] + L + 1, 1);
		}
	}
	printf("%d\n", base - dinic(0, L + R + 1));
	return 0;
}


Measured memory_bytes: 14208
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(ReadLine());
        var xy = new (int x, int y)[N];
        for (int i = 0; i < N; i++)
        {
            var _xy = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            xy[i] = (_xy[0], _xy[1]);
        }

        IEnumerable<IEnumerable<int>> GetPermutation(int n)
        {
            var stack = new Stack<List<int>>();
            stack.Push(new List<int>());
            while (0 < stack.Count)
            {
                var l = stack.Pop();

                if (l.Count == n)
                {
                    yield return l;
                    continue;
                }

                for (int i = 0; i < n; i++)
                {
                    if (l.Contains(i))
                        continue;

                    var _l = l.ToList();
                    _l.Add(i);
                    stack.Push(_l);
                }
            }
        }

        double GetDistance((int x, int y) s, (int x, int y) e) => Math.Sqrt(Math.Pow(s.x - e.x, 2) + Math.Pow(s.y - e.y, 2));

        var allDistSum = 0.0;
        var allDistCount = 0;

        foreach (var l in GetPermutation(N))
        {
            var distSum = 0.0;
            (int, int)? prev = null;

            foreach (var n in l)
            {
                var curr = xy[n];

                if (prev == null)
                {
                    prev = curr;
                    continue;
                }

                var dist = GetDistance(prev.Value, curr);
                distSum += dist;
            }

            allDistSum += distSum;
            allDistCount++;
        }

        var allDistAve = allDistSum / allDistCount;

        WriteLine(allDistAve);
    }
}


Measured memory_bytes: 46668
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def main():
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    for a in A:
        ans += a - 1
    print(ans)

if __name__ == '__main__':
    main()


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

using namespace std;

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

  int n;
  cin >> n;
  deque<int> a;
  for (int i = 0; i < n; ++i) {
    int t;
    cin >> t; 
    if (i % 2 ^ (n % 2 == 0)) {
      a.push_back(t);
    } else {
      a.push_front(t);
    }
  }

  for (size_t i = 0; i < a.size(); ++i) {
    if (0 < i) cout << " ";
    cout << a[i];
  }
  cout << "\n";
}


Measured memory_bytes: 3072
#include <iostream>

using namespace std;

#define YES(n) cout << (n?"YES":"NO")<<endl;
#define Yes(n) cout << (n?"Yes":"No")<<endl;

int main() {
    int A, B;
    cin >> A >> B;
    if (A + B < 10)cout << A + B << endl;
    else cout << "error" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h;
    cin >> h;
    int n;
    cin >> n;

    vector<int> offensive_powers(n);
    for (int i = 0; i < n; i++)
    {
        cin >> offensive_powers.at(i);
    }
    int attack_sum = 0;
    for (auto point : offensive_powers)
    {
        attack_sum += point;
    }

    if (attack_sum >= h)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int main(void){
    ll n,m;
    cin>>n>>m;
    P c[100000];
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        c[i]=P(a,b);
    }
    sort(c,c+n);
    ll ans=0,honsu=0,z=0;
    while(honsu!=m){
        ans+=c[z].first;
        honsu++;
        c[z].second--;
        if(c[z].second==0) z++;
    }
    cout<<ans<<endl;
}

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

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

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(i,0,n)
#define RREP(i,n)   RFOR(i,0,n)
#define SORT(s) sort(s.begin(), s.end())
#define P pair<int, int>
#define mp make_pair

const double INF = 1e+09;
const int MOD = 1e9+7;

using namespace std;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {if (v.empty()) {ostr << "{ }"; return ostr;}
    ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) {ostr << ", " << *itr;}
    ostr << "}";
    return ostr;}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

int lcm(int a, int b)
{return a * b / gcd(a, b);}

vector<int> uniq(vector<int> vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return vec;}

vector<ll> divisor(ll n) {
vector<ll> ret;
for(int64_t i = 1; i * i <= n; i++) {
  if(n % i == 0) {
    ret.push_back(i);
    if(i * i != n) ret.push_back(n / i);
  }
}
  sort(begin(ret), end(ret));
  return (ret);
}
void permu(int n){
  vector<int> perm(n);
  REP(i, n) perm[i] = i;
do{
  cout << perm  << endl;
}
while (next_permutation(perm.begin(), perm.end()));
return;}



int main(void){
  ios::sync_with_stdio(false);
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> cost(n);
  vector<vector<int>> a(n, vector<int>(m));
  REP(i, n){
    cin >> cost[i];
    REP(j, m) cin >> a[i][j];
  }
  int ans = INF;

  REP(i, 1<<n){
    vector<int> d(m, 0);
    bool flag = true;
    int val = 0;
    REP(j, n){
      if (i>>j & 1){
        REP(k, m){
          d[k] += a[j][k];
        }
      val += cost[j];
      }
    }
    REP(j, m){
      if (d[j] < x) flag = false;
    }
    if (flag) ans = min(ans, val);
  }
  if (ans == INF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}


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

int main() {
  string str;
  cin >> str;
  for (int i=0 ; i<3 ; i++) {
    if (str[i] == '1') str[i] = '9';
    else if (str[i] == '9') str[i] = '1';
  }
  cout << str << endl;
}

Measured memory_bytes: 256
N = int(input())
A= [int(x) for x in input().split()]
A.append(0)
count = N
s = 0
t = 1
xor = A[0]
while s < N - 1:
  while t < N:
    if not A[t] or not (xor & A[t]):
      xor ^= A[t]
      t += 1
    else:
      break
  count += t - s - 1
  while s < t:
    xor ^= A[s]
    s += 1
    if xor & A[t]:
      count += t - s - 1
      continue
    else:
      break
  if s == t:
    xor = A[s]
    t += 1
print(count)

Measured memory_bytes: 23560
#include "bits/stdc++.h"
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(ll i=0;i<n;++i)
#define END(x) (*(x.end()-1))
#define INF (INT_MAX)

using namespace std;
typedef long long ll;


template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T>
T gcd(T a, T b){
   if (a%b == 0){
       return(b);
   }
   else{
       return(gcd(b, a%b));
   }
}

template<typename T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}

int main(void){
    int n;
    cin>>n;
    vector<vector<double>>dp(n+1,vector<double>(n+1,0));
    vector<double>p(n);
    rep(i,n){
        cin>>p[i];
    }
    dp[0][0]=1.0;
    rep(i,n){
        rep(j,i+1){
            dp[i+1][j+1]+=dp[i][j]*p[i];
            dp[i+1][j]+=dp[i][j]*(1-p[i]);
        }
    }
    
    double ans=0;
    for(int i=n/2+1;i<=n;++i){
        ans+=dp[n][i];
    }
    cout<<setprecision(10)<<ans;
}
/*
*/

Measured memory_bytes: 74124
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;

int main()
{
    ll N, M = 0;
    cin >> N;
    vll a(N + 1), b(N + 1), ans;
    rep(i, N)
    {
        cin >> a[i + 1];
    }

    for (ll i = N; i > 0; i--)
    {
        ll tmp = 0;
        for (ll j = 2; j * i <= N; j++)
        {
            tmp += b[j * i];
        }
        if ((tmp % 2) != a[i])
        {
            b[i] = 1;
            M++;
        }
    }
    cout << M << endl;
    for (ll i = 0; i <= N; i++)
    {
        if(b[i]==1)
        {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3968
package main

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

var sc = bufio.NewScanner(os.Stdin)

func readInt() int {
	sc.Scan()
	ans, _ := strconv.Atoi(sc.Text())
	return ans
}

func main() {
	sc.Split(bufio.ScanWords)
	n := readInt()
	al := make(map[int]bool)
	for i := 0; i < n; i++ {
		al[readInt()] = true
	}
	fmt.Println(len(al))
}


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

ll a[200001];
ll b[200001];

int main(){
  int n;

  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(a[i]<0){
      b[i]+=(-1*a[i]);
      a[i]=0;
    }
  }
  ll ans = 1e15;
  for(int i=1;i<=n;i++){
    a[i]+=a[i-1];
    b[i]+=b[i-1];
  }
  for(int i=0;i<n-1;i++)
    ans = min(ans,abs(2*a[i]-(2*b[i])-a[n-1]+b[n-1]));
  
  
  cout << ans <<endl;
  
  return 0;
}


Measured memory_bytes: 3328
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ


int main(){
	int a;scanf("%d",&a);
	printf("%d\n",a*a*3);
}

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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

string s;
int i;
int idx;
char ans;

int getNum()
{
  string ret = "";
  while(idx < s.size() && isdigit(s[idx])) ret += s[idx++];
  return stoi(ret);
}

// ()????????????/?????¨?????????
int solve(int len)
{
  int ret = 0;
  if(idx == s.size()) return 0;
  if(s[idx] == ')') return 0;
  if(s[idx] == '(') {
    idx++; // skip '('
    ret = solve(len);
    if(ret == -1) return -1;
    idx++; // skip ')'
    return ret;
  } else if(isalpha(s[idx])) {
    if(len == i) {
      ans = s[idx];
      return -1;
    }
    idx++;
    ret = solve(len+1);
    if(ret == -1) return -1;
    return ret + 1;
  } else {
    int k = getNum(), l = 1;
    int re = idx;
    if(isalpha(s[idx])) idx++;
    else if(s[idx] == '(') {
      l = solve(len);
      if(l == -1) return -1;
    }
    if(i < len + k*l) { // ??¶????????????
      idx = re;
      i = (i - len) % l;
      return solve(0); // -1
    }
    ret = solve(len + k*l);
    if(ret == -1) return -1;
    return ret + k*l;
  }
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(cin >> s >> i, s != "0") {
    idx = 0;
    ans = '0';
    solve(0);
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 3148
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <numeric>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int N, M, a[102], b[102];

void solve() {
  int ptr = 0, cnt = 0;
  while (ptr != N) {
    // 左が ptr + 1 以下の教授でかつ 右が最も大きな教授をさがす
    int mostRight, idx = -1;
    rep(i,M) {
      if (a[i] <= ptr + 1 && ptr + 1 <= b[i]) {
        if (idx == -1 || mostRight < b[i])
          idx = i, mostRight = b[i];
      }
    }
    // 対象の教授が発見出来なかった場合
    if (idx == -1) {
      puts("Impossible");
      return;
    }
    ++cnt;
    ptr = b[idx];
  }
  printf("%d\n", cnt);
}

int main() {
  while (scanf("%d%d", &N, &M) != -1) {
    rep(i,M) {
      scanf("%d%d", a+i, b+i);
    }
    solve();
  }
  return 0;
}

Measured memory_bytes: 1192
#include "bits/stdc++.h"
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const long long mod = 1e9 + 7;

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

ll powMod(ll n, ll k, ll m) {
	if (k == 0) {
		return 1;
	} else if (k % 2 == 1) {
		return powMod(n, k - 1, m) * n % m;
	} else {
		ll t = powMod(n, k / 2, m);
		return t * t % m;
	}
}

int main() {
	double n;
	cin >> n;

	double ans=n*2*3.14;
	
	cout << ans << endl;
}


Measured memory_bytes: 3784
N = int(input())
data = [[] for _ in range(N)]

for i in range(N):
    Ai = int(input())
    
    for _ in range(Ai):
        xi, yi = map(int, input().split())
        data[i].append((xi-1, yi))
    
ans = 0

for i in range(2**N):
    flag = [False]*N
    ans_cand = 0
    
    for j in range(N):
        if (i>>j)&1:
            flag[j] = True
            ans_cand += 1
    
    F = True
    
    for j in range(N):
        if flag[j]:
            for xi, yi in data[j]:
                if (yi==0 and flag[xi]) or (yi==1 and not flag[xi]):
                    F = False
                    
    if F:
        ans = max(ans, ans_cand)

print(ans)

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

int main() {
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  for(int i = 0; i < n; ++i) {
    cin >> p[i];
  }
  
  for(int i = 0; i < n; ++i) {
    cin >> q[i];
  }
  
  vector<int> v;
  for(int i = 0; i < n; ++i) {
  	v.push_back(i+1);
  }
  
  int t = 0;
  
  int a = 0, b = 0;
  
  do {
    ++t;
    if(v == p) {
      a = t;
    }
    if(v == q) {
      b = t;
    }
  }while(next_permutation(v.begin(), v.end()));
  cout << abs(a-b);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int beki(int b, int p) {
	int result = 1;
	for(int i = 0; i < p; i++) {
		result *= b;
	}
	return result;
}

int main() {
	int x,max,tmp;
	cin >> x;
	max = 1;
	if (x == 1) {
		cout << 1 << endl;
		return 0;
	}

	for (int i = 2; i < x; i++) {
		int p = 2;
		while(1){
			if (beki(i, p) > x)
				break;
			p++;
		}
		if (p != 2) {
			if (max <= beki(i, p - 1))
				max = beki(i, p - 1);
		}
	}
	cout << max;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define MAX 100020
#define inf 1<<22
using namespace std;

int main()
{
  int n,m,hp[101],p,d;
  string name,s;

  while(1){
    cin>>n;
    if(n==0)break;
    for(int i=0;i<n;i++)cin>>hp[i];
    vector<pair<int,int> > all,single; 
    cin>>m;
    for(int i=0;i<m;i++){
      cin>>name>>p>>s>>d;
      if(s=="Single")single.push_back(mp(p,d));
      else all.push_back(mp(p,d));
    }
    
    int All[MAX],Single[MAX];
    for(int i=0;i<MAX;i++){
      All[i]=inf;
      Single[i]=inf;
    }
    All[0]=0;
    Single[0]=0;

    for(int i=0;i<all.size();i++){
      for(int j=0;j<MAX;j++){
	All[min(j+all[i].s,MAX-1)]=min(All[min(j+all[i].s,MAX-1)],
				       All[j]+all[i].f);
      }
    }
   
    for(int i=0;i<single.size();i++){
      for(int j=0;j<MAX;j++){
	Single[min(j+single[i].s,MAX-1)]=min(Single[min(j+single[i].s,MAX-1)],
					     Single[j]+single[i].f);
      }
    }

    int mina=inf,minb=inf;
    for(int i=MAX-1;i>0;i--){
      All[i]=min(mina,All[i]);
      mina=min(All[i],mina);
      Single[i]=min(minb,Single[i]);
      minb=min(minb,Single[i]);
    }

    int ans=inf;
    for(int i=0;i<MAX;i++){
      if(All[i]==inf)continue;
      int sum=All[i];
      for(int j=0;j<n;j++){
	sum+=Single[max(hp[j]-i,0)];
      }
      ans=min(ans,sum);
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1992
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

int const N = 200000;
char s[N + 1];
bool y[N];

int main(){
	scanf("%s", s);
	int o = 0, n = strlen(s);
	ll an = 0;
	f(i, 0, n)if (s[i] == '1'){
		++o;
		an += o + 1 >> 1;
	}
	bool z = false;
	f(i, 0, n)if (s[i] == '0'){
		if ((i & 1 ^ z)){
			++o;
			an += o + 1 >> 1;
			y[i] = true;
		}else z ^= 1;
	}
	
	int a = 0, b = 0;
	for (int i = n - 1; i >= 0; --i)if (s[i] == '0'){
		if (y[i])++a;
		else {
			swap(a, b);
			++b;
			++o;
			an += (o + 1 >> 1) - b;
		}
	}
	
	printf("%lld\n", an);
}

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

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007
#define INF (1 << 30)
#define REP(i, m, n) for(int i = (int)m; i < (int)n; ++i)
#define rep(i, n) REP(i, 0, n)


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

    int n, a, b; cin >> n >> a >> b;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    rep(i, n) {
        int p; cin >> p;
        if(p <= a) cnt1++;
        else if(p <= b) cnt2++;
        else cnt3++;
    }
    cout << min({cnt1, cnt2, cnt3}) << '\n';
    return 0;
}

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

typedef long long ll;

int main() {
	int K, T;
	cin >> K >> T;
	vector<int> a(T);
	for(int i=0; i<T; i++) cin >> a[i];

	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());

	int sum=0;
	for(int i=1; i<T; i++) sum += a[i];

	int ans = a[0] - sum;

	cout << (ans<=0?0:ans-1) << endl;


}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >>a[i];
    bool ok = true;
    rep(i,n) {
        if (a[i]%2==0) {
            if (a[i]%3!=0 && a[i]%5!=0) {
                ok = false;
            }
        }
    }
    if (ok) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
    return 0;
}

Measured memory_bytes: 256
/* ex3_4
   moka223711 */

#include <stdio.h>

int main(void){
	int num, d = 0;
	scanf("%d", &num);

	// numを1から9で割って、余りが0かつ商が9以下になっているものを探す
	// 割れるものが見つかったらdを1に変える
	for(int i = 1; i <= 9; i++){
    	if(num % i == 0 && num / i <= 9){
        	d = 1;
			break;
		}
	}
	
	// 上のfor文で1から9で割り切れるものが見つかったときd == 1となっているため
	// if文が実行される、なかったときはelse文の実行
	if(d){
		printf("Yes");
	}
	else{
		printf("No");
	}
  
	return 0;
}


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

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

    int ans;
    if(0<L) ans=(2*L+N)*(N-1)/2;
    else if(0<=(L+N-1)) ans=(2*L+N-1)*N/2;
    else ans=(2*L+N-2)*(N-1)/2;

    cout<<ans<<endl;
}

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

list = list(map(int, input().split()))

dis = []
for i in range(len(list)):
  if i ==0:
    dis.append(list[i] + (k - list[i-1]))
  else:
    dis.append(list[i] - list[i-1])

print(sum(dis)- max(dis))

Measured memory_bytes: 26444
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

class Main {

	static class Comb implements Comparable<Comb> {
		private int[] array;
		private int dec; //十進数

		//コンストラクタ
		public Comb(int[] a) {
			array = new int[a.length];
			for (int i = 0; i < array.length; i++) {
				array[i] = a[i];
				dec += Math.pow(2, array[i]); //十進数にする
			}
		}

		public int[] getArray() { return array; }

		public int getDec() { return dec;	}

		@Override
		public int compareTo(Comb c) { //比較の標準を作る
			return this.dec - c.getDec();
		}
	}

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			//入力と配列準備
			sc.nextInt();
			int tLen = sc.nextInt();
			ArrayList<Integer> list = new ArrayList<Integer>();
			for (int i = 0; i < tLen; i++) {
				list.add(sc.nextInt());
			}
			System.out.println("0:");
			//--------------------------------------------------------
			ArrayList<Comb> arrayC = new ArrayList<Comb>();
			ArrayList<int[]> array = combination(tLen - 1);
			for (int[] arrayi : array) {
				int[] arrayNum = new int[arrayi.length];
				for (int i=0; i<arrayi.length; i++) arrayNum[i]=list.get(arrayi[i]);
				arrayC.add(new Comb(arrayNum));
			}
			Collections.sort(arrayC);
			for (Comb c : arrayC) {
				System.out.print(c.getDec() + ":");
				for (int i : c.getArray()) {
					System.out.print(" " + i);
				}
				System.out.print('\n');
			}
		}
	}

	static ArrayList<int[]> combination(int numbers) {
		ArrayList<int[]> a = new ArrayList<int[]>();
		for (int i = 1; i <= numbers + 1; i++) 	a.addAll(nCr(numbers, i));
		return a;
	}

	//組み合わせを配列に保存
	static ArrayList<int[]> nCr(int numbers, int target){  //0～numbersから選べる、何個取る
		ArrayList<int[]> list = new ArrayList<int[]>();
		int[] keep = new int[target];
		int[] finalt = new int[target];
		for (int i=0; i<target; i++) {
			keep[i] = 0 + i;  //最初の組み合わせを作成
			finalt[i] = numbers + (i - target) + 1;  //最後の組み合わせを作成
		}
		int[] k = new int[target];
		System.arraycopy(keep,0,k,0,target);
		list.add(k);
		while (!Arrays.equals(keep, finalt)) { //最後の組み合わせではない場合
			if (keep[target-1] != numbers) {  //最後の桁がnumbersではない場合
				keep[target-1]++;
				k = new int[target];
				System.arraycopy(keep,0,k,0,target);
				list.add(k);
			} else {
				int now = target-2;
				while (now > 0) {
					if (keep[now+1] - keep[now] == 1) now--; //右の桁-1はnowの最大値
					else break;
				}
				keep[now]++;
								for (int i=now+1; i<target; i++) {
									keep[i] = keep[i-1]+1;
								}
				k = new int[target];
				System.arraycopy(keep,0,k,0,target);
				list.add(k);
			}
		}
		return list;
	}
}


Measured memory_bytes: 205684
//Code is like humor. When you have to explain it, it’s bad.
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long
using namespace std;
#define ss second
#define ff first
int32_t main()
{
    fastio;
    int T,n,m,i,j,k,a,b,c;
    T=1;
    while(T --> 0)
    {
        cin>>n>>m;
        int ans = (n*n-n)/2;
        ans += (m*m-m)/2;
        cout<<ans;
    }
    return 0;
}

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

int main() {
    string str;
    cin >> str;
    int count=0;
    for(int i=0;i<4;i++){
        for(int j=i+1;j<4;j++){
            char a=str.at(i);
            char b=str.at(j);
            if(a==b) count++;
        }
    }
    if(count==2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256