akhauriyash/Code-Regression huggingface dataset:
//四則演算 #pragma GCC target("avx")
//並列計算 #pragma GCC optimize("O3")
//条件分岐を減らす #pragma GCC optimize("unroll-loops")
//浮動小数点演算 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define each(i, a) for(auto &i : a)
#define SORT(i) sort(i.begin(),i.end())
#define rSORT(i) sort(i.rbegin(),i.rend())
#define fSORT(i,a) sort(i.begin(),i.end(),a)
#define all(i) i.begin(),i.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
inline void print() { cout << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }

void dfs(string s, int a) {

}

int main() {
    init();

    int n; cin >> n;
    n %= 10;
    if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9)print("hon");
    else if (n == 0 || n == 1 || n == 6 || n == 8)print("pon");
    else print("bon");





    return 0;
}

Measured memory_bytes: 3652
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A, B = [None] * M, [None] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


uf = UnionFind(N)
ans = [None] * M
ans[M - 1] = N * (N - 1) // 2
for i in range(M - 1, 0, -1):
    x, y = A[i] - 1, B[i] - 1
    if uf.is_same(x, y):
        ans[i - 1] = ans[i]
    else:
        ans[i - 1] = ans[i] - (uf.get_size(x) * uf.get_size(y))
    uf.union(x, y)
for a in ans:
    print(a)


Measured memory_bytes: 19868
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,(n)-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,(n)-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
const int MAX=1000000000;
using ll = long long;
using P = pair<ll,ll>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

/*---最大公約数 from 20190929---*/
long long gcd(long long x, long long y) { return y ? gcd(y,x%y) : x;}

struct HashPair {

    static size_t m_hash_pair_random;

    template<class T1, class T2>
    size_t operator()(const pair<T1, T2> &p) const {

        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);

        size_t seed = 0;
        seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= m_hash_pair_random + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

size_t HashPair::m_hash_pair_random = (size_t) random_device()();

int main(){
    int n;
    cin >> n;
    vector<double> a(n);
    rep(i,n)cin >> a[i];

    // vector<vector<int>> mp(1e9+1,vector<int>(1e13+1,0));
    unordered_map<P, int, HashPair> mp;

    vector<ll> y;
    for(ll x = 1;x*x<=MAX;x++){
        if(MAX%x == 0){
            y.push_back(x);
            if(x*x != MAX)y.push_back(MAX/x);
        }
    }
    

    ll ans = 0;

    rep(i,n){
        double ep = 0.001;
        ll s = a[i]*1e9+ep;
        ll b = 1e9;
        ll g = gcd(s,b);
        s /= g;
        b /= g;
        // for(ll x = 1;x*x <= min(s,(ll)MAX);x++){
        for(auto x : y){
            if(x > s)continue;
            if(s%x == 0){
                ans += mp[make_pair(x,b)];
                // if(x*x != s)ans += mp[make_pair(s/x,b)];
                // ans += mp[x][b];
                // if(x*x != s)ans += mp[s/x][b];
            }
        }
        
        // for(ll x = 1;x*x <= min(s,(ll)MAX);x++){
        for(auto x : y){
            if(x > s)continue;
            if(s%x == 0){
                mp[make_pair(b,x)]++;
                // if(x*x != s)mp[make_pair(b,s/x)]++;
                // mp[b][x]++;
                // if(x*x != s) mp[b][s/x]++;
            }
        }

        // cout << s  << " " << b << endl;
        // cout << i << " " << ans << endl;
    }

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 4672
#include <iostream>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)
const int N = 1e2 + 5;
int f[N], g[N];
char a[N][N];
int main()
{
    ll h, w;
    cin >> h >> w;
    rep(i, h) cin >> a[i];
    rep(i, h) rep(j, w) if (a[i][j] == '#') f[i] = g[j] = 1;
    rep(i, h)
    {
        if (f[i])
        {
            rep(j, w)
            {
                if (g[j])
                {
                    cout << a[i][j];
                }
            }
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){

  int m,f,r,sum;

  while(scanf("%d %d %d",&m,&f,&r),m+f+r!=-3){
    sum=0;
    sum=m+f;

    if(m==-1 || f==-1 || sum<30){
      printf("F\n");
    }else if(sum>=80){
      printf("A\n");
    }else if(65<=sum && sum<80){
      printf("B\n");
    }else if(50<=sum && sum<65){
      printf("C\n");
    }else if(30<=sum && sum<50){
      if(r>=50){
        printf("C\n");
      }else{
        printf("D\n");
      }
    }
  }
  return 0;
}


Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
int n, a, b;
int h[100005];
bool check(int x) {
    long long t = 0;
    for(int i = 1; i <= n; ++i)
        if (1ll*h[i] > 1LL*x*b) {
            t += (1ll*h[i]-1LL*x*b-1)/(a-b)+1;
        }
    return t <= x;
}
int main() {
    cin >> n >> a >> b;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    sort(h+1, h+1+n);
    reverse(h+1, h+1+n);
    int inf = 0, sup = 1000000000, mid, ans = 0;
    while (inf <= sup) {
        mid = inf + sup >> 1;
        if (check(mid)) {
            ans = mid;
            sup = mid - 1;
        } else inf = mid + 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

int main(){
  ll N , x; cin >> N >> x;
  vector<ll> a(N + 1); rep(i,N) cin >> a[i];
  a.pb(0);

  ll ans = 0;
  rep(i,N){
    if(a[i] > x){
      ans += a[i] - x;
      a[i] = x;
    }
    if(a[i] + a[i + 1] > x){
      ans += a[i] + a[i + 1] - x;
      a[i + 1] = x - a[i];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n,k;cin>>n>>k;
    int h[n],ans=0;
    
    for(int i=0;i<n;++i){
        cin>>h[i];
        if(h[i]>=k)ans++;
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main() {
	ll h, w; cin >> h >> w;
	ll n; cin >> n;
	ll a[100001] = {};
	repe(i, 1, n)cin >> a[i];

	ll b[100][100] = {};
	bool r = true;

	ll k = 0, l = 0, t = 1;
	repe(i, 1, n) {
		ll t = i;
		while (a[i]--) {
			b[k][l] = t;

			if (l == w - 1 && r) {
				k++;
				r = false;
			}
			else if (l == 0 && !r) {
				k++;
				r = true;
			}
			else {
				l = r ? l + 1 : l - 1;
			}
		}
	}

	rep(i, 0, h) {
		rep(j, 0, w) {
			cout << b[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include<stdio.h>

void insertionSort(int A[], int N){
	int i = 0, j = 0;
	int v = 0;
	printf("%d", A[0]);
	for( j = 1; j < N; j++ ){
		printf(" %d", A[j]);
	}
	printf("\n");
	for( i = 1; i < N; i++ ){
		v = A[i];
		for( j = i-1; j >= 0 && A[j] > v; j-- ){
			A[j+1] = A[j];
		}
		A[j+1] = v;
		printf("%d", A[0]);
		for( j = 1; j < N; j++ ){
			printf(" %d", A[j]);
		}
		printf("\n");
	}
}


int main(){
	int N = 0;;
	int A[1000];
	int i = 0;
	scanf("%d", &N);
	for( i = 0; i < N; i++ ){ scanf("%d", &A[i]); }
	insertionSort(A, N);
	return 0;
}

Measured memory_bytes: 608
import sys
import re
import queue
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []



def main():
	N = i_input()
	a = []
	a.append(1)
	a.append(19)
	for i in range(2,N):
		a.append((a[i-1]*19-90*a[i-2])%MOD)

	b = []
	b.append(0)
	b.append(2)
	for i in range(2,N):
		b.append((b[i-1]*8+2*a[i-1])%MOD)


	print(b[N-1])
	
	return


if __name__ == '__main__':
	main()

Measured memory_bytes: 89740
n = int(input())

if n < 10:
    print(n)
elif 10 <= n and n < 10**2:
    print(9)
elif 10**2 <= n and n < 10**3:
    print(9+n-99)
elif 10**3 <= n and n < 10**4:
    print(9+900)
elif 10**4 <= n and n < 10**5:
    print(9+900+n-9999)
elif n == 10 ** 5:
    print(9+900+90000)


Measured memory_bytes: 2940
// abc114_b
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    string S;
    cin >> S;

    int ans = INF;
    REP(i, S.size()-2){
        int n = stoi(S.substr(i, 3));
        ans = min(ans, abs(n - 753));
    }
    print(ans);

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];

  auto check=
    [&](Int x)->Int{
      using P = pair<Int, Int>;
      vector<P> vp;
      vp.emplace_back(0,0);
      vp.emplace_back(0,a[0]);
      
      for(Int i=1;i<n;i++){
        if(a[i-1]<a[i]){
          vp.emplace_back(0,a[i]);
        }else{
          while(a[i]<vp.back().second){
            P p=vp.back();
            vp.pop_back();
            if(a[i]>vp.back().second)          
              vp.emplace_back(p.first,a[i]);
          }
          while(vp.size()>1u&&vp.back().first+1>=x)
            vp.pop_back();
          
          if(vp.size()==1u) return 0;

          Int y=vp.back().first,z=vp.back().second;
          vp.back().second--;

          Int m=vp.size();
          if(vp[m-2].second==vp.back().second) vp.pop_back();
          vp.emplace_back(y+1,z);
          
          if(vp.back().second<a[i])
            vp.emplace_back(0,a[i]);
        }
      }
      return 1;
    };

  Int l=0,r=n;
  while(l+1<r){
    Int m=(l+r)>>1;
    if(check(m)) r=m;
    else l=m;
  }
  cout<<r<<endl;
  return 0;
}


Measured memory_bytes: 9088
#include <iostream>
#include <algorithm>
#include <string>

int main() {
    std::string s;
    std::cin >> s;

    sort(s.begin(), s.end());

    if(s == "abc") {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
}

Measured memory_bytes: 256
s = input()
cnt = 0
pre_word = [""]
ra = len(s)
i = 0
while True:
  j = 1
  if i+j > ra:
    break
  while True:
    if i+j > ra:
      i+=j
      break
    if pre_word[-1] != s[i:i+j]:
      pre_word.append(s[i:i+j])
      i += j
      j = 0
      cnt += 1
    j+=1
print(cnt)



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

int main(){
  string str;
  cin >> str;

  bool s,c,n;
  s = c = n = false;
  for(int i=0; i<(int)str.length(); i++){
    if(str[i]>='a' && str[i]<='z') s = true;
    if(str[i]>='A' && str[i]<='Z') c = true;
    if(str[i]>='0' && str[i]<='9') n = true;
  }
  if(s && c && n && str.length()>=6) cout << "VALID" << endl;
  else cout << "INVALID" << endl;
  return 0;
}

Measured memory_bytes: 3112
M = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [(N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
print(dp[3] % M)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    ll a, b, x;
    cin >> a >> b >> x;

    ll sum = (b / x) - (a / x);
    if (a % x == 0)
    {
        sum++;
    }
    cout << sum << endl;
    return (0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = a; i < (b); ++i)
#define vl vector<ll>

int main() {

    ll N;
    cin >> N;

    vl A(N);
    vl B(N);
    vl a(N+1, 0);
    vl b(N+1, 0);

    rep(i, N) {
        cin >> A[i];
        a[A[i]]++;
    }

    rep(i, N) {
        cin >> B[i];
        b[B[i]]++;
    }

    FOR(i, 1, N+1) {
        if (a[i] + b[i] > N) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    FOR(i, 1, N+1) {
        a[i] += a[i-1];
        b[i] += b[i-1];
    }

    ll k = 0;
    FOR(i, 1, N+1) {
        k = max(k, a[i]-b[i-1]);
    }

    rep(i, N) {
        cout << B[(i+N-k)%N] << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 9568
#include <iostream>
#include <map>
#include <tuple>

using namespace std;

int main()
{
	long long n, x, m;
	cin >> n >> x >> m;
	long long ans = 0;
	map<long long, tuple<long long, long long, int>> mp; //xが出てきた数, sum, i
	bool f = true;
	for (long long i = 1; i <= n; i++) {
		ans += x;
		if (f) {
			if (get<0>(mp[x]) == 1) {
				f = false;
				
				long long t = ans - get<1>(mp[x]);
				ans += (n - i) / (i - get<2>(mp[x])) * t;
				n -= (n - i) / (i - get<2>(mp[x])) * (i - get<2>(mp[x]));
			}
			else {
				get<0>(mp[x])++;
				get<1>(mp[x]) = ans;
				get<2>(mp[x]) = i;
			}
		}
		x = x * x % m;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7524
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define sz(a) (int)a.size()
#define de(x) cout << #x << " = " << x << endl
#define dd(x) cout << #x << " = " << x << " "
#define endl "\n"
#define all(a) a.begin(), a.end()
#define pw(a) (1ll << (a))
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
typedef vector<int> vi;

struct P {
	db x, y;
	P() {}
	P(db x, db y) : x(x), y(y) {}
	void read() {
		cin >> x >> y;
	}
	P operator + (const P &c) const {
		return P(x + c.x, y + c.y);
	}
	P operator - (const P &c) const {
		return P(x - c.x, y - c.y);
	}
	P operator * (const db &c) const {
		return P(x * c, y * c);
	}
	P operator / (const db &c) const {
		return P(x / c, y / c);
	}
};
struct L {
	P a, b;
	L() {}
	L(P a, P b) : a(a), b(b) {}
	void read() {
		a.read();
		b.read();
	}
};
db det(P a, P b) {
	return a.x * b.y - a.y * b.x;
}
P isLL(const L &l1, const L &l2) {
	db s1 =  det(l2.b - l2.a, l1.a - l2.a);
	db s2 = -det(l2.b - l2.a, l1.b - l2.a);
	return (l1.a * s2 + l1.b * s1) / (s1 + s2);
}

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int q;
	cin >> q;
	cout << setiosflags(ios::fixed);
	cout << setprecision(10);
	while(q--) {
		L l1, l2;
		l1.read();
		l2.read();
		P res = isLL(l1, l2);
		cout << res.x << " " << res.y << endl;
	}
	return 0;
}


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

ll l1[10];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a=n,b=0;
    while(n>0){
        b+=n%10;
        n/=10;
    }
    if(a%b==0)cout<<"Yes";
    else cout<<"No";
}


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

using namespace std;
int main() {
  string s;
  cin >> s;
  bool isGood = false;
  if (s[0] == s[1] && s[1] == s[2]) isGood = true;
  if (s[1] == s[2] && s[2] == s[3]) isGood = true;

  cout << (isGood ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>

using namespace std;
static const int M = 1046527;

vector<string> H(M);

int convertChartoNum(char c)
{
	if (c == 'A')
	{
		return(1);
	}
	else if (c == 'C')
	{
		return(2);
	}
	else if (c == 'G')
	{
		return(3);
	}
	else if (c == 'T')
	{
		return(4);
	}
	else
	{
		return(0);
	}
}

long long int getKey(string s)
{
	long long int sum = 0;
	long long int p = 1;
	for (int i = 0; i < s.size(); ++i)
	{
		sum += p * convertChartoNum(s[i]);
		p *= 5;
	}
	return(sum);
}

int h1(int key)
{
	return(key % M);
}

int h2(int key)
{
	return(1 + (key % (M - 1)));
}

int find(string s)
{
	long long int key = 0;
	int h = 0;
	key = getKey(s);
	for (long long int i = 0;; ++i)
	{
		h = (h1(key) + i * h2(key)) % M;
		if (H[h] == s)
		{
			return(1);
		}
		else if (H[h].size() == 0)
		{
			return(0);
		}
	}
	return(0);
}

void insert(string s)
{
	long long key = getKey(s);
	long long h = 0;
	for (long long int i = 0;; ++i)
	{
		h = (h1(key) + i * h2(key)) % M;
		if (H[h] == s)
		{
			return;
		}
		if (H[h].size() == 0)
		{
			H[h] = s;
			return;
		}
	}
}

void solve()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		string command, str;
		cin >> command >> str;
		if (command[0] == 'i')
		{
			insert(str);
		}
		else
		{
			if (find(str) == 1)
			{
				cout << "yes" << endl;
			}
			else
			{
				cout << "no" << endl;
			}
		}
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 25356
while True:
    m,f,r=map(int,input().split())
    if m==-1 and f==-1 and r==-1:
        break

    if m==-1 or f==-1:
        print("F")
    elif m+f>=80:
        print("A")
    elif m+f>=65:
        print("B")
    elif m+f>=50:
        print("C")
    elif m+f>=30:
        if r>=50:
            print("C")
        else:
            print("D")
    else:
        print("F")


Measured memory_bytes: 5592
//Keep pluggin',this is your only outlet.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cctype>
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define mp make_pair
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int quickmul(int x,int y,int mod){return (x*y-(int)((long double)x/mod*y)*mod+mod)%mod;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}

const int Mod = 1e9 + 7;
const int MAXN = 1e5 + 100;
int n,a[MAXN],ans = 0,fac = 1,inv[MAXN];

///------------------head------------------
signed main(signed argc, char *argv[]){
    n = read();
    rep(i,1,n) a[i] = read();
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) fac = fac * i % Mod,inv[i] = (Mod - Mod/i) * inv[Mod % i] % Mod;
    for (int i = 2; i <= n; ++i) (inv[i] += inv[i-1]) %= Mod;
    for (int i = 1; i <= n; ++i) (ans += 1ll * a[i] * (inv[i] + inv[n-i+1] - 1) % Mod) %= Mod;
    ans = 1ll * ans * fac % Mod;
    printf("%lld\n",ans);
    return 0;
}

/* Examples: */
/*

*/

/*

*/


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
using namespace std;
int main(){
  double res=0.0;
  long long N,K; cin>>N>>K;
  for (long long i=1;i<=N;++i){
    long long cnt=i;
    double tmp=1.0;
    while (cnt<K){
      cnt*=2;
      tmp/=2.0;
    }
    res+=tmp;
  }
  res/=N;
  cout<<fixed<<setprecision(10)<<res<<endl;
}
      
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 550
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000000;
const int MOD = 1000000007;
ll dp[MAX][4];
int main(){
    string s;
    cin>>s;
    char c[3]={'A','B','C'};
    dp[0][0]=1;
    REP(i,SZ(s)){
        REP(j,4){
            if(s[i]=='?'){
                dp[i+1][j]+=3*dp[i][j];
                dp[i+1][j]%=MOD;
                if(j!=3){
                    dp[i+1][j+1]+=dp[i][j];
                    dp[i+1][j+1]%=MOD;
                }
            }else if(j<3&&s[i]==c[j]){
                dp[i+1][j+1]+=dp[i][j];
                dp[i+1][j+1]%=MOD;
                dp[i+1][j]+=dp[i][j];
                dp[i+1][j]%=MOD;
            }else{
                dp[i+1][j]+=dp[i][j];
                dp[i+1][j]%=MOD;
            }
        }
    }
    OUT(dp[SZ(s)][3]);
    return 0;
}

Measured memory_bytes: 4608
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vii vector<vi>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  int c=1,nw=s[0];
  FOR(i,1,n){
    if(nw!=s[i]){
      c++;
    }
    nw=s[i];
  }
  cout<<c<<endl;
}


Measured memory_bytes: 512
#pragma GCC optimize ("O3")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <stack>
#include <unordered_map>
#define lld long long int
#define dbg1(vari1) cerr<<#vari1<<" = "<<(vari1)<<endl;
#define dbg2(vari1,vari2) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<endl;
#define dbg3(vari1,vari2,vari3) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<" "<<#vari3<<" = "<<(vari3)<<endl;
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	string s;
	cin >> n >> s;
	vector <int> v;
	for(int i=0;i<s.size();i++)
	{
		v.push_back(((s[i]-'A'+n)%26));
	}
	string ans="";
	for(int i=0;i<s.size();i++)
	{
		// dbg1(v[i]);
		ans+=(v[i]+65);
	}
	cout << ans;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101

int n, H[N][N], Lim[N][N];

int main()
{
	scanf("%d", &n);
	memset(Lim, 0x3f, sizeof(Lim));
	for (int t = 1, x, y, h; t <= n; t ++)
	{
		scanf("%d%d%d", &x, &y, &h);
		for (int i = 0; i < N; i ++)
			for (int j = 0; j < N; j ++)
			{
				int t = h + abs(i - x) + abs(j - y);
				if (h == 0)
					Lim[i][j] = min(Lim[i][j], t);
				else
				{
					if (!H[i][j] || H[i][j] == t)
						H[i][j] = t;
					else H[i][j] = -1;
				}
			}
	}
	for (int i = 0; i < N; i ++)
		for (int j = 0; j < N; j ++)
			if (H[i][j] > 0 && H[i][j] <= Lim[i][j])
				printf("%d %d %d\n", i, j, H[i][j]);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        int n = Integer.parseInt(line);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        String s3 = in.nextLine();
        in.close();

        int ans = 0;
        for (int i = 0 ; i < n ; i++) {
        	if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == s3.charAt(i)) {
        		;
        	} else if (s1.charAt(i) == s2.charAt(i)) {
        		ans = ans + 1;
        	} else if (s1.charAt(i) == s3.charAt(i)) {
        		ans = ans + 1;
        	} else if (s3.charAt(i) == s2.charAt(i)) {
        		ans = ans + 1;
        	} else {
        		ans = ans + 2;
        	}
        }
        System.out.println(ans);
    }
}

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

typedef long long ll;

const int INF = 101234567;

int main() {
    string s, t;
    ll ans, cnt;
    cin >> s;
    for (int i = 0; i < s.size()-1; i++) {
        if (s.substr(i, 2) == "BC") {
            t += 'D';
            i++;
        } else {
            t += s[i];
        }
    }

    ans = cnt = 0;
    for (int i = t.size(); i >= 0; i--) {
        if (t[i] == 'A') {
            ans += cnt;
        } else if (t[i] == 'D') {
            cnt++;
        } else {
            cnt = 0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 776
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cctype>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpi;
#define mp make_pair
#define pb push_back

int a[200200],n,s[200200];
int k;
map<int,int> m;
vi b[200200];

int main(){
	scanf("%d%d",&n,&k);
	s[0]=0;
	int cnt=1;
	m.clear();
	m[0]=1;
	b[1].pb(0);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i]--;
		a[i]%=k;
		s[i]=(s[i-1]+a[i])%k;
		if (m.find(s[i])==m.end()) m[s[i]]=++cnt;
		b[m[s[i]]].pb(i);
	}
	ll ans=0;
	for (map<int,int>::iterator it=m.begin();it!=m.end();it++){
		int p=it->second;
		int sz=b[p].size();
		if (sz==1) continue;
		int i=0,j=1;
		while (j<sz){
			if (b[p][j]-b[p][i]>=k) i++;
			else{
				ans+=(ll)j-i;
				j++;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 22144
b0=input().split()
book=int(b0[0])
pro=int(b0[1])
norma=int(b0[2])

bl=[]
for x in range(book):
  bl.append([int(y) for y in input().split()])
  
mn=-1
for x in range(2**book):
  if book>9:
    k=str(book)+"b"
  else:
    k="0"+str(book)+"b"
  x2=format(x, k)
  m=0
  exl=[0 for i in range(pro)]
  for y in range(book):
    if x2[y]=="1":
      m+=bl[y][0]
      for j in range(pro):
        exl[j]+=bl[y][j+1]
  if min(exl)>=norma and (mn==-1 or mn>m):
    mn=m

print(mn)

Measured memory_bytes: 9140
import collections

n=int(input())
arr=list(map(int,input().split()))
# 辞書型で値をint型にする
cnt=collections.defaultdict(int)
for val in arr: #あらかじめ各Aiの個数をカウントアップ
 cnt[val]+=1
# cntの出力結果　入力例2
# defaultdict(<class 'int'>, {1: 4})
sums=sum(arr) #あらかじめAiの総和を求めておく
q=int(input())
for _ in range(q):
 b,c=map(int,input().split())
 #差は(Ci-Bi)*(値がBiである要素の個数)
 diff=(c-b)*(cnt[b]) 
 #差分合計値を更新
 sums+=diff
 print(sums) 
 #クエリごとに値bをcに更新してbを消す
 cnt[c]+=cnt[b] 
 cnt[b]=0
#  defaultdict(<class 'int'>, 
# {1: 0, 2: 2, 3: 1, 4: 1})1回目
#  defaultdict(<class 'int'>, 
# {1: 0, 2: 2, 3: 0, 4: 2})2回目

Measured memory_bytes: 24112
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
typedef long long ll;
#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define max(l,r) ((l)>(r)?l:r)
#define min(l,r) ((l)<(r)?l:r)
#define swap(l,r) {ll tp=l;l=r;r=tp;}
const ll MOD = 1000000007;

ll scr[5050][5050];
int cnt[5050];
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    int p[5050];
    ll c[5050];
    rep(i, n) scanf("%d", &p[i]);
    rep(i, n) p[i]--;
    rep(i, n) scanf("%lld", &c[i]);
    rep(i, n+1) rep(j, n+1) scr[i][j] = -(MOD*MOD);
    
    rep(i, n){
        int idx = i;
        cnt[i] = 0;
        scr[idx][cnt[i]] = c[p[idx]];
        while(p[idx] != i) {
            idx = p[idx];
            cnt[i]++;
            scr[i][cnt[i]] = c[p[idx]];
            scr[i][cnt[i]] += scr[i][cnt[i]-1];
        }
    }
    ll ans = -(MOD*MOD);
    rep(i, n){
        if(cnt[i]+1 >= k){
            rep(j, k){
                ans = max(ans, scr[i][j]);
            }
        }else{
            if(scr[i][cnt[i]] <= 0){
                rep(j, cnt[i]+1){
                    ans = max(ans, scr[i][j]);
                }
            }else{
                ll tmp = scr[i][cnt[i]] * (k/(cnt[i]+1));
                ans = max(ans, tmp);
                int tmpk = k % (cnt[i]+1);
                rep(j, cnt[i]){
                    ans = max(ans, tmp - scr[i][cnt[i]] + scr[i][j]);
                }
                rep(j, tmpk){
                    ans = max(ans, tmp + scr[i][j]);
                }
            }
        }
    }

    printf("%lld\n", ans);
    /*rep(i,n){
        rep(j, cnt[i]+1){
            printf("%d ", scr[i][j]);
        }
        puts("");
    }*/
}

Measured memory_bytes: 199116
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

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; }

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll ,ll );
ll mod_add(ll ,ll );
ll mod_mul(ll ,ll );
ll mod_div(ll ,ll );
void make_fact(ll );
void make_invfact(ll );



int main(void){

  ll n;
  cin>>n;

  cout << n*(n-1)/2 << endl;

  return 0;

}

ll mod_pow(ll x,ll r){
  if(r==0) return 1;
  else if(r==1) return x%mod;
  else if(r%2==0){
    ll t=mod_pow(x,r/2)%mod;
    return t*t %mod;
  } 
  else{
    ll t=mod_pow(x,r/2)%mod;
    ll k= t*t %mod;
    return k*x%mod;
  } 
}
ll mod_add(ll a,ll b){
  return (a+b)%mod;
}

ll mod_mul(ll a,ll b){
  return (a*b)%mod;
}

ll mod_div(ll a,ll b){
  return mod_mul(a,mod_pow(b,mod-2));
}

void make_fact(ll n){
  fac[0]=1;
  rep(i,n){
    fac[i+1]=mod_mul(fac[i],i+1);
  }  
}

void make_invfact(ll n){
  invfac[n]= mod_pow( fac[n] ,mod-2);
  for(int i=n-1;i>=0;i--){
    invfac[i]=mod_mul(invfac[i+1],i+1);
  }

}

Measured memory_bytes: 256
#include <cstdio>
char str[10];
int main()
{
scanf("%s",str);
int i;
for (i = 0; i < 4; i++)
if (str[i] == 'A' && str[i+1]=='C')
break;
if (i == 4)
printf("No\n");
else
printf("Yes\n");
return 0;}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace AtCoder {
    class Practice {
        static void Main() => CustomMain();

        static void Solve() {
            var a = ReadIntArray();

            WriteAnswer(a[2] <= a[0] + a[1] ? "Yes" : "No");
        }


        static void CustomMain() {
#if DEBUG
            // ファイルからテストケースを読み込む
            global::Common.ChangeStdIn();
            // 時間計測
            var stopwatch = new Stopwatch();
            stopwatch.Start();
#endif
            // 出力高速化
            var streamWriter = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            Console.SetOut(streamWriter);
            // 回答
            Solve();
#if DEBUG
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
#endif
            Console.Out.Flush();
        }

        static string ReadString() => Console.ReadLine().Trim();
        static int ReadInt() => int.Parse(ReadString());
        static long ReadLong() => long.Parse(ReadString());
        static float ReadFloat() => float.Parse(ReadString());
        static double ReadDouble => double.Parse(ReadString());

        static string[] ReadStringArray() => ReadString().Split(' ');
        static int[] ReadIntArray() => Array.ConvertAll(ReadString().Split(' '), int.Parse);
        static long[] ReadLongArray() => Array.ConvertAll(ReadString().Split(' '), long.Parse);
        static float[] ReadFloatArray() => Array.ConvertAll(ReadString().Split(' '), float.Parse);
        static double[] ReadDoubleArray() => Array.ConvertAll(ReadString().Split(' '), double.Parse);

        static T TypeConversion<T>(string s) {
            if (typeof(T) == typeof(int)) {
                return (T) Convert.ChangeType(int.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(long)) {
                return (T) Convert.ChangeType(long.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(double)) {
                return (T) Convert.ChangeType(double.Parse(s), typeof(T));
            } else {
                return (T) Convert.ChangeType(s, typeof(T));
            }
        }

        static void ReadMulti<T, U>(out T a, out U b) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
        }

        static void ReadMulti<T, U, V>(out T a, out U b, out V c) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
            c = TypeConversion<V>(str[2]);
        }

        static void WriteAnswer(object ans) => Console.WriteLine(ans);

        static bool IsOdd(long num) {
            return (num & 1) == 1;
        }

        static bool IsEven(long num) {
            return (num & 1) == 0;
        }

        static long GCD(long a, long b) {
            return b != 0 ? GCD(b, a % b) : a;
        }
    }
}

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

using namespace std;

const int N = 1e6 + 5;
int _w;

char str[N];
int n , l , r , mid , res , L , R;

int main( void ) {
  _w = scanf("%s",str+1);
  n = strlen( str + 1 );
  l = 0 , r = n , res = n;
  bool flag , _f;
  while( l <= r ) {
    mid = ( l + r ) >> 1;
    flag = 0;
    for( int _ = 0 ; _ < 2 ; ++_ ) {
      L = _ , R = mid , _f = 1;
      if( (_^R) & 1 ) --R;
      if( L > R ) {
        _f = 0;
      } else 
      for( int i = 1 ; i <= n ; ++i ) {
        if( str[i] == '1' ) ++L , ++R;
        if( str[i] == '0' ) --L , --R;
        if( str[i] == '?' ) --L , ++R;
        if( L < 0 ) L += 2;
        if( R > mid ) R -= 2;
        if( L > R ) {
          _f = 0;
          break;
        }
      }
      flag |= _f;
    }
    if( flag ) res = mid , r = mid - 1;
    else l = mid + 1;
  }
  cout << res;
  return 0;
}


Measured memory_bytes: 4712
/*
 * 16-7-31_AGC002_B.cpp
 *
 *  Created on: 2016/07/31
 *      Author: ryoma
 */


#include <iostream>

using namespace std;

int  N,M;
int size[100001],ans;
bool red[100001];
int main(){
	cin >> N >> M;
	red[0] = true;
	for (int i=0;i<M;i++){
		int x,y;
		cin >> x >> y;
		x--;
		y--;
		size[x]--;
		size[y]++;
		if (red[x])
			red[y] = true;
		if (size[x]==-1){
			red[x] = false;
		}
	}
	for (int i=0;i<N;i++){
		if (red[i])
			ans++;
	}
	cout << ans << endl;
	return 0;
}




Measured memory_bytes: 768
#include <stdio.h>

int main(){
  int a,i,j,k,n,q,ans=0;
  scanf("%d",&n);
  int S[n];
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  int T[n];
  for(i=0;i<q;i++){
    scanf("%d",&T[i]);
  }
  for(i=0;i<q;i++){
    for(j=0;j<n;j++){
      if(T[i]==S[j]){
	ans++;
	break;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}



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

using namespace std;

double p[42], q[42];

int main() {
  for (int i = 0; i < 6; i++) {
    int foo;
    scanf("%d", &foo);
    p[i] = 0.01 * foo;
  }
  for (int i = 0; i < 6; i++) {
    int foo;
    scanf("%d", &foo);
    q[i] = 0.01 * foo;
  }
  vector <double> pts;
  pts.push_back(0.0);
  pts.push_back(1.0);
  for (int i = 0; i < 6; i++) {
    if (p[i] + q[i] > 1e-14) {
      pts.push_back(q[i] / (p[i] + q[i]));
    }
  }
  double ans = 42.0;
  for (int id = 0; id < (int) pts.size(); id++) {
    double pA = pts[id];
    double total = 0.0;
    for (int i = 0; i < 6; i++) {
      total += max(pA * p[i], (1.0 - pA) * q[i]);
    }
    ans = min(ans, total);
  }
  printf("%.15f\n", ans);
  return 0;
}


Measured memory_bytes: 3800
a, b = input().split()
if a == b:
  print("Draw")
else:
  if a == '1':
    print("Alice")
  elif b == '1':
    print("Bob")
  else:
    a = int(a); b = int(b)
    if a > b:
      print("Alice")
    else:
      print("Bob")


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

using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int> data(N);
  int sum=0;
  for(int i=0; i<N; i++)
  {
    cin >> data.at(i);
  }
  
  for(int i=0; i<N; i++)
  {
    for(int k=i+1; k<N; k++)
    {
      sum += data[i] * data[k];
      //cout << sum << endl;
    }
  }
  
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    int A[n];
    
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    for(int i = n - 1; i > 0; i--){
        cout << A[i] << " ";
    }
    cout << A[0];
    cout << endl;
}



Measured memory_bytes: 3116
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}

enum MOD = (10 ^^ 9) + 7;

void main()
{
    long N, M;
    scan(N, M);
    auto A = new string[](N);
    auto B = new string[](M);
    foreach (i; 0 .. N)
        scan(A[i]);
    foreach (i; 0 .. M)
        scan(B[i]);
    foreach (i; 0 .. N - M + 1)
        foreach (j; 0 .. N - M + 1)
        {
            bool b = true;
            foreach (k; 0 .. M)
                b = b && (A[i + k][j .. j + M] == B[k]);
            if (b)
            {
                writeln("Yes");
                return;
            }
        }
    writeln("No");
}


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

using namespace std;

int main(void) {

	int group[3][7] = { { 1, 3, 5, 7, 8, 10, 12},
						{4, 6, 9, 11, 0, 0, 0}, 
						{2, 0, 0, 0, 0, 0, 0}
	};
	int x, y, xx, yy;

	cin >> x >> y;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 7; j++) {
			if (x == group[i][j]) xx = i;
			else if (y == group[i][j]) yy = i;
		}
	}
	if (xx == yy) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <limits>
#include <cmath>
#include <numeric>
#include <string>

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
#define rep(i, a, b) for(int i = (a); i < (b); ++i )
#define rrep(i, a, b) for(int i = (a); i > (b); --i )
#define REP(i, a, b) for(int i = (a); i <= (b); ++i )
#define RREP(i, a, b) for(int i = (a); i >= (b); --i )
#define llrep(i, a, b) for(ll i = (a); i < (b); ++i )
#define llrrep(i, a, b) for(ll i = (a); i > (b); --i )
#define llREP(i, a, b) for(ll i = (a); i <= (b); ++i )
#define llRREP(i, a, b) for(ll i = (a); i >= (b); --i )
#define ullrep(i, a, b) for(ull i = (a); i < (b); ++i )
#define ullrrep(i, a, b) for(ull i = (a); i > (b); --i )
#define ullREP(i, a, b) for(ull i = (a); i <= (b); ++i )
#define ullRREP(i, a, b) for(ull i = (a); i >= (b); --i )



int D, N;
int A[200010];

int main() {
    cin >> N;
    rep(i, 0, N) {
        cin >> A[i];
        A[i] -= i+1;
    }
    sort(A, A + N);
    int b0 = A[N/2];
    int b1 = A[N/2-1];
    ull sum0 = 0;
    ull sum1 = 0;
    rep(i, 0, N) {
        sum0 += abs(A[i]-b0);
        sum1 += abs(A[i]-b1);
    }
    cout << (sum0 < sum1? sum0: sum1) << endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define MOD 1000000007

bool erase(string &s,const string t);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin >> s;
    while(erase(s,"erase")||erase(s,"eraser")||erase(s,"dream")||erase(s,"dreamer"));
    cout << (s.length()==0?"YES":"NO") << endl;
    return 0;
}

bool erase(string &s,const string t) {
    int p;
    if((p=s.find(t,s.length()-t.length()))>=0) {
        s.erase(p,p+t.length());
        return true;
    }
    return false;
}

Measured memory_bytes: 512
#include<cstdio>
#include<queue>
using namespace std;
struct node{
    int pos, val;
    node(int a,int b):pos(a),val(b){}
    bool operator <(const node &B)const{
        return val<B.val;        
    }
};
priority_queue<node> q;
const int maxn=200005;
int a[maxn],b[maxn],n;
int prev(int x){
    return (x-1+n)%n;
}
int succ(int x){
    return (x+1)%n;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",a+i);
    }
    for(int i=0;i<n;++i){
        scanf("%d",b+i);
    }
    for(int i=0;i<n;++i){
        q.push(node(i,b[i]));
    }
    long long cnt=0;
    while(!q.empty()){
        node tmp=q.top();q.pop();
        if(a[tmp.pos]==b[tmp.pos])continue;
        else{
            int sum=b[prev(tmp.pos)]+b[succ(tmp.pos)];
            if((b[tmp.pos]-a[tmp.pos])/sum <= 0){
                printf("-1\n");
                return 0;
            }
            cnt+=(b[tmp.pos]-a[tmp.pos])/sum;
            b[tmp.pos]-=(b[tmp.pos]-a[tmp.pos])/sum*sum;//注意不能一步一步做, 否则会超时
            q.push(node(tmp.pos,b[tmp.pos]));
        }
    }
    printf("%lld\n",cnt);
    return 0;
}

Measured memory_bytes: 3956
n = int(input())
ans = 0
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.reverse()
for i in range(n):
    a, b = data[i]
    if (a + ans) % b != 0:
        ans += (b - ((a + ans) % b))
print(ans)



Measured memory_bytes: 27380