akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <iomanip>

using namespace std;
vector<pair<int,int> > edge[100000];
bool arrived[100000];
int pos[100000];

bool dfs(int n, int d){
    bool ok = true;
    arrived[n]=true;
    pos[n]=d;
    for(int i =0; i<edge[n].size(); i++){
        pair<int,int> p=edge[n][i];
        int m = p.first;
        int d2 = p.second;
        if( arrived[m]==false ){
            if(dfs(m, d+d2)==false) return false;;
        }
        else{
            if(d+d2 != pos[m]){
                return false;
            }
        }
    }
    return true;
}
int main(){
    int N, M;
    cin >> N >> M;
    int pos[N];
    memset(pos,-1,sizeof(pos));
    for(int i = 0 ; i < M; i++){
        int L, R, D;
        cin >> L >> R >> D;
        L--;
        R--;
        edge[L].push_back(make_pair(R,D));
        edge[R].push_back(make_pair(L,-D));
    }
    for(int i=0; i<N; i++){
        if(arrived[i]==false){
            pos[i]=0;
            if(dfs(i,0)==false){
                cout << "No"<< endl;
                return 0;
            }
        }
    }
    cout<< "Yes"<< endl;
    return 0;
}

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

using namespace std;
map<int , int> mp;
int main()
{
    int n , k , m;
    cin >> n >> m;
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= m; i ++){
        int x;
        string s;
        cin >> x >> s;
        if(mp[x] == -1) continue;
        if(s == "AC") {
            cnt2 += mp[x];
            cnt1 ++;
            mp[x] = -1;
        }
        else {
            mp[x] ++;
        }
    }
    cout << cnt1 << ' ' << cnt2;
    return 0;
}


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

int N;

int main() {
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    int befor = A.size();

    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    int after = A.size();

    string ans = "NO";
    if (befor == after) ans = "YES";

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

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <map>
using namespace std;

int N, Q;
vector<int64_t> A, X, aSum1, aSum2;

bool IsFree(int turn, int64_t x, int aoki_index) {
  int t_move = (turn + 1) / 2,
      a_move = turn / 2;

  int dup = max(0, aoki_index + a_move - (N - t_move));

  if (dup == 0) return true;
  if (N - t_move <= aoki_index) return false;
  if (t_move + a_move > N) return false;

  int target = aoki_index - dup;

  if (dup < 0) return false;

  if (abs(x - A[N - t_move]) >= abs(x - A[target])) return true;
  else return false;
}

int64_t ComputeCardSum(int64_t x) {
  int index = lower_bound(begin(A), end(A), x) - begin(A);

  if (index == N - 1 or (index > 0 and abs(A[index] - x) >= abs(A[index - 1] - x))) {
    index--;
  }
  int lb = 0, ub = N + 1;
  while (ub - lb > 1) {
    int mid = (lb + ub) / 2;

    if (IsFree(mid, x, index)) lb = mid;
    else ub = mid;
  }
  int turn = lb;

  int t_move = (turn + 1) / 2,
      a_move = turn / 2;
  int64_t sum = aSum1[N - t_move];

  /*
  cerr << "turn " << turn << endl;
  ce-rr << "t_move " << t_move << endl;
  */

  if (N - 1 - turn >= 0 and turn % 2 == 0) {
    sum += aSum2[N - 1 - turn];
    return sum;
  }

  if (N - 1 - (turn + 1) >= 0) {
    sum += aSum2[N - 1 - (turn + 1)];
    return sum;
  }
  return sum;
}

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

  cin >> N >> Q;

  A.resize(N);
  X.resize(Q);
  aSum1.resize(N);
  aSum2.resize(N);

  for (int i = 0; i < N; i++) {
    cin >> A[i];
    aSum2[i] = A[i];
    if (i - 2 >= 0) {
      aSum2[i] += aSum2[i - 2];
    }
  }

  for (int i = N - 1; i >= 0; i--) {
    aSum1[i] = A[i];
    if (i + 1 < N) {
      aSum1[i] += aSum1[i + 1];
    }
  }

  for (int i = 0; i < Q; i++) {
    cin >> X[i];

    cout << ComputeCardSum(X[i]) << endl;
  }

  return 0;
}

Measured memory_bytes: 4864
N,K,Q = map(int,input().split())

A = [0]*Q
for q in range(Q):
  A[q] = int(input())-1

P = [0]*N

for q in range(Q):
  P[A[q]]+=1

for n in range(N):
  if P[n] + K -Q <=0:
    print('No')
  else:
    print('Yes')

Measured memory_bytes: 51032
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
a  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ans = 0
for a_ in a:
    ans += a_ -1

print(ans)



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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)

using ll = long long;
using P = std::tuple<int,int>;

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

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

    int N, K;
    std::cin >> N >> K;

    int res = K;
    for(int i=1;i<N;++i){
        res *= K - 1;
    }

    std::cout << res << std::endl;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [0] * (N + 1)
e = dd(list)
inc = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  inc[v] += 1
def topologically(n, e, inc):
  res = []
  s = []
  c = 0
  many = 0
  for i in range(1, n + 1):
    if inc[i] == 0:
      s.append(i)
      c += 1
  many = c > 1
  while len(s):
    p = s.pop()
    res.append(p)
    for q in e[p]:
      inc[q] -= 1
      if inc[q] == 0:
        s.append(q)
    many = many or ((len(s) - c) > 0)
    c = len(s)
  return res + [many]
res = topologically(N, e, inc)
for x in range(N):
  i = res[x]
  for q in e[i]:
    dp[q] = max(dp[q], dp[i] + 1)
print(max(dp))

Measured memory_bytes: 73692
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(ll i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
constexpr char ln = '\n';

const int mx=200010;
const ll mod=1e9+7;



int main(){
  ll n;
  cin >> n;
  vector<ll> f(n+2,0);
  REP(i,1,n+1){
    for(int j=i; j<=n; j+=i){
      f[j]++;
    }
  }
  ll ans = 0;
  REP(i,1,n+1){
    ans += i*f[i];
  }
  cout << ans << ln;
  return 0;
}

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

int main(){
	int n,m;
	char sky[101][101];
	cin >> n >> m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> sky[i][j];
		}
	}
	for(int i=0;i<n;i++){
		bool flg = true;
		int now=0;
		for(int j=0;j<m;j++){
			if(flg && sky[i][j] == '.'){
				cout << "-1";
			}
			else if(sky[i][j] == 'c'){
				flg = false;
				now = 0;
				cout << now;
			}
			else {
				now++;
				cout << now;
			}
			if(j != m-1) cout << " ";
		}
		cout << endl;
	}
}

Measured memory_bytes: 1168
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 1; i <=(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const int INF=1000100010;
int main(){
    int k;cin>>k;
    int sum=0;
    rep(a,k){
        rep(b,k){
            rep(c,k){
                int AB=__gcd(a,b);
                int ABC=__gcd(AB,c);
                sum+=ABC;
            }
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;

int main() {
  ll n;
  cin >> n;
  map<ll,ll> count;
  for(ll i=0;i<n;i++) {
    ll temp;
    cin >> temp;
    count[temp]++;
  }
  ll ans=0;
  for(auto p:count) {
    if(p.second>=p.first) {
      ans+=p.second-p.first;
    }
    else {
      ans+=p.second;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 6272
n=gets.to_i
t,a=gets.split.map &:to_i
h=gets.split.map &:to_i
mi=[10**8,1]
for i in 0 ... h.size
  v = h[i]
  d = (1000 * t - 6 * v - 1000 * a).abs
  mi = [mi, [d, i]].min
end
puts mi[1]+1


Measured memory_bytes: 1788
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
S = ""


def set_inputs():
    global N, S
    N = get_int()
    S = get_str()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    turn_e = [0] + list(itertools.accumulate([s == "W" for s in S[:-1]]))
    turn_w = list(reversed(list(itertools.accumulate(
        [s == "E" for s in reversed(S[1:])]
    )))) + [0]
    print(min(itertools.starmap(operator.add, zip(turn_e, turn_w))))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()


Measured memory_bytes: 32280
// https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
const int MOD = 998244353;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, maxv = 0;
    cin >> N;
    vector<int> v(N);
    REP(i, N) {
        int t;
        cin >> t;
        if (i == 0 ^ t == 0) {
            cout << "0\n";
            return 0;
        }
        v[t]++;
        maxv = max(maxv, t);
    }
    int ans = 1;
    REP(i, maxv) REP(j, v[i + 1]) ans = (ans * v[i]) % MOD;
    cout << ans << endl;
    return 0;
}


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

#define HIGH 1000000;

int main(void) {
	double h;
	double max = 0;
	double min = HIGH;
	
	while(cin >> h) {
		if(h > max) {
			max = h;
		}
		if(h < min) {
			min = h;
		}
	}
	
	printf("%.1lf\n", max - min);
	
	return 0;
}


Measured memory_bytes: 3184
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<algorithm>
#include<math.h>
using namespace std;

int main() {

	unsigned long long H;
	unsigned long long N;
	cin >> H;
	cin >> N;

	unsigned long long A;
	unsigned long long sum = 0;

	for (unsigned long long i = 1; i <= N;  i++) {
		cin >> A;
		sum += A;
	}

	if (sum >= H) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
# DPをつかった解放を全然思いつけなかった
# 解説動画がわかりやすい

mod = 1000000007
N = int(input())

dp = [ [[[0 for c3 in range(4)]  for c2 in range(4)]  for c1 in range(4)] for n in range(N+1)]

# 全部TのときはOK
dp[0][3][3][3] = 1

# 文字の数
for n in range(N):
  # 後ろから1文字目
  for c1 in range(4):
    # 後ろから2文字目
    for c2 in range(4):
      # 後ろから3文字目
      for c3 in range(4):
        # 該当するものがないとき
        if dp[n][c1][c2][c3] == 0: continue

        # 新しく追加する文字
        for a in range(4):
          # AGCに当てはまる文字
          if(c2 == 0 and c1 == 1 and a == 2): continue
          if(c2 == 0 and c1 == 2 and a == 1): continue
          if(c2 == 1 and c1 == 0 and a == 2): continue
          if(c3 == 0 and c1 == 1 and a == 2): continue
          if(c3 == 0 and c2 == 1 and a == 2): continue

          dp[n+1][a][c1][c2] += dp[n][c1][c2][c3]

ans = 0
# 後ろから1文字目
for c1 in range(4):
  # 後ろから2文字目
  for c2 in range(4):
    # 後ろから3文字目
    for c3 in range(4):
      ans += dp[N][c1][c2][c3]

print(ans % mod)

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


int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  cout << max(c - (a - b), 0) << endl;
  return 0;
}

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

#%%
A.sort(reverse=True)
ans = A[0]
res = N - 2
q, m = divmod(res, 2)
for i in range(1, q+1):
    ans += 2 * A[i]
if m != 0:
    ans += A[i+1]

print(ans)


Measured memory_bytes: 31440
#include <cstdio>
#include <stack>
#define FOR(variable,a,b) for(variable=(a);variable<(b);variable++)

using namespace std;

int main() {
    // import phase
    int target;
    stack<int> map;
    
    // calculate phase
    while(scanf("%d", &target) != EOF) {
        if(target != 0) {
            map.push(target);
        } else {
            printf("%d\n", map.top());
            map.pop();
        }
    }

    return 0;
}

Measured memory_bytes: 1036
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
money = 1000
for i in range(1, N):
    if As[i]>As[i-1]:
        money += (money//As[i-1])*(As[i]-As[i-1])
print(money)

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

using ll=long long;

int main(){
  string S;
  cin >> S;
  int l=S.size();
  if(l==1)
    cout << stoi(S) << endl;
  if(l==2)
    cout << 9 << endl;
  if(l==3)
    cout << 9+stoi(S)-99 << endl;
  if(l==4)
    cout << 9+900 << endl;
  if(l==5)
    cout <<9+900+stoi(S)-9999 << endl;
  if(l==6)
    cout <<9+900+90000 << endl;
  
  
}

Measured memory_bytes: 256
//is there any case of -1 or any special corner cases ?
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define zeros(arr) memset(arr,0,sizeof(arr));
#define precise(num)  cout<<fixed; cout << std::setprecision(num)
#define nl cout<<"\n";
#define test int t;cin>>t;while(t--) 
const int maxx  = 3*1e5 , limit = 9*1e18 , MOD=1e9+7;
string binary(int n){bitset<60>b(n) ;string p =b.to_string();return p;}
int decimal(string n) { int dec_value = 0;  int base = 1;  for (int i = n.size() - 1; i >= 0; i--) { if (n[i] == '1') 
dec_value += base; base = base * 2; } return dec_value; } 
bool isPrime(int n){if (n <= 1) return false; if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
int pow (int x, int n,int mod) {if (n == 0) return 1; int res = pow (x, n / 2,mod);res = (res * res) % mod;if (n % 2) res = (res * x ) % mod;return res;}
#define boost  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n';
int count(int num){
    int pc =0;
    while(num){
        if(num%2)pc++;
        num/=2;
    }
    return pc;
}
int find(int n1,int n2){
    
    int res = 0;
    while(1){
        res++;
        int val = n1%n2;
        n1 = val;
        n2 = count(n1);
        if(val == 0)break;
    }
    return res;
}
int32_t main(){
    boost;
        int n;
        cin>>n;
        string s;
        cin>>s;
        
        
        int one =0 ;
        for(int i = 0; i < n; i++ ){
            if(s[i] == '1')one++;
        }
    vector<int>v1;
    vector<int>v2;
    vector<int>v3;
    int sum1= 0;
    int sum2=0;
    int sum3 = 0;
    
    for(int i =0 ; i < n ; i ++ ){
        
        
        //  int num1 = pow(2,n-i-1 , one);
         int num2 = pow(2,n-i-1,one+1);
         
         
       
         v2.pb(num2);
         
       
       if(s[i]=='1'){
          sum2+=num2;
        //   sum3+=num3;
        //   sum1%=one;
          sum2%=(one+1);
         
       }
       
      if(one-1 >0){ 
       int num3 = pow(2,n-i-1,one-1);
       v3.pb(num3);
       if(s[i]=='1'){
           sum3+=num3;
           sum3%=(one-1);
       }
      }
       
       
    }    
    for(int i =0 ; i < s.size() ; i++ ){
        
        if(s[i] == '1'){
            
            if(one - 1 == 0){
                cout<<"0\n";
                continue;
            }
            int val = sum3 - v3[i];
            while(val<0)
            val = val + (one-1);
            cout<<find(val,one-1)<<endl;
        }else{
            int val = sum2 + v2[i];
            cout<<find(val,one+1)<<endl;
        }
        
    }
    
        
        
    
}

Measured memory_bytes: 6848
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>

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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
	string s, t;
	cin >> s >> t;
	vector<char> sv, tv;
	REP(i, s.size()) sv.push_back(s[i]);
	REP(i, t.size()) tv.push_back(t[i]);

	sort(sv.begin(), sv.end());
	sort(tv.begin(), tv.end());
	reverse(tv.begin(), tv.end());

	//REP(i, s.size()) cout << sv[i] << " ";
	//cout << endl;
	//REP(i, t.size()) cout << tv[i] << " ";
	//cout << endl;

	int ix = 0;
	while (1) {
		if (ix > sv.size() || ix > tv.size()) {
			if (s.size() < t.size()) {
				cout << "Yes";
			}
			else cout << "No";
			break;
		}
		if (tv[ix] - sv[ix] > 0) {
			cout << "Yes";
			break;
		}
		else if (tv[ix] - sv[ix] < 0) {
			cout << "No";
			break;
		}
		ix++;
	}

	system("pause");
	return 0;
}

Measured memory_bytes: 504
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

VI v[100010];
int l[100010], c[100010], w[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m, C;
  cin >> n >> m >> C;
  REP(i, C) cin >> l[i];
  REP(i, n) {
    cin >> c[i] >> w[i];
    c[i]--;
    v[c[i]].PB(w[i]);
  }

  VI vec;
  REP(i, C) {
    sort(ALL(v[i]), greater<>());
    REP(j, min(l[i], (int)v[i].size())) vec.PB(v[i][j]);
  }

  sort(ALL(vec), greater<>());
  int ans = 0;
  REP(i, min((int)vec.size(),m)) ans += vec[i];
  cout << ans << endl;

  return 0;
}



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

const int N=100005;
int n,dep[N],siz[N],fa[N],h[N],to[N+N],las[N+N],cnt;

int lca(int a,int b)
{
	if(dep[a]<dep[b])swap(a,b);
	while(dep[a]>dep[b])a=fa[a];
	while(a!=b)a=fa[a],b=fa[b];
	return a;
}

void dfs(int x)
{
	siz[x]=1;
	for(int i=h[x];i;i=las[i])
	    if(to[i]!=fa[x])
	    	fa[to[i]]=x,dep[to[i]]=dep[x]+1,dfs(to[i]),siz[x]+=siz[to[i]];
}

int getfa(int x,int y)
{
	while(y--)x=fa[x];
	return x;
}

int main()
{
	scanf("%d",&n);
	int i,u,v;
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		las[++cnt]=h[u],h[u]=cnt,to[cnt]=v;
		las[++cnt]=h[v],h[v]=cnt,to[cnt]=u;
	}
	dfs(n);
	u=lca(1,n);
	v=(dep[1]+dep[n]-2*dep[u])/2;
	v=getfa(1,v);
	if(siz[v]>siz[n]-siz[v])printf("Fennec\n");
	else printf("Snuke\n");
	return 0;
}


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

#define rep(i,l,n) for(int (i)=(l);(i)<(n);(i)++)
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)

int main(){
	char s[10]; scanf("%s",s);
	if( s[2]==s[3] && s[4]==s[5] ){
		printf("Yes");
	}else{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 128
def Search2(data, value):
    left = 0
    right = len(data) - 1
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == value:
            return mid
        elif data[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1

x = []
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))

for j in range(q):
    if Search2(S, T[j])  > -1:
        x.append(Search2(S, T[j]))
print(len(x))


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int n, q;
string s;
char t[252521], d[252521];

bool is_ok1(int mid){
	REP(i, q){
		if(mid==0 && s[mid]==t[i] && d[i]=='L'){
			return true;
		}
		if(s[mid]==t[i]){
			if(d[i]=='L'){
				--mid;
			}
			else{
				++mid;
			}
		}
	}
	return false;
}

bool is_ok2(int mid){
	REP(i, q){
		if(mid==n-1 && s[mid]==t[i] && d[i]=='R'){
			return true;
		}
		if(s[mid]==t[i]){
			if(d[i]=='L'){
				--mid;
			}
			else{
				++mid;
			}
		}
	}
	return false;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	cin>>n>>q>>s;
	REP(i, q){
		cin>>t[i]>>d[i];
	}
	int lb1=-1, ub1=n+1;
	while(ub1-lb1>1){
		int mid=(lb1+ub1)/2;
		if(is_ok1(mid)){
			lb1=mid;
		}
		else{
			ub1=mid;
		}
	}
	int lb2=-1, ub2=n;
	while(ub2-lb2>1){
		int mid=(lb2+ub2)/2;
		if(is_ok2(mid)){
			ub2=mid;
		}
		else{
			lb2=mid;
		}
	}
	// DEBUG(lb1);
	// DEBUG(ub1);
	// DEBUG(lb2);
	// DEBUG(ub2);
	cout<<n-min(n, lb1+1+n-ub2)<<'\n';
	return 0;
}


Measured memory_bytes: 976
n = int(input())
a = []
for i in range(n):
    new = list(input())
    if a == []: 
        a.append(new)
    elif (new in a) | (a[-1][-1] != new[0]):
        print("No")
        exit()
    else:
        a.append(new)
print("Yes")

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

#define rep(i,l,n) for(int (i)=(l);(i)<(n);(i)++)
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)

int main(){
	int X; scanf("%d",&X);
	printf("%d",(X/500)*1000 + ((X%500)/5)*5);
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main(){

  int i, j, n, result=0;

  scanf("%d", &n);

  int a[n];

  for(i=0;i<n;i++) scanf("%d",&a[i]);

  int min=a[0];
  
  result=a[1]-min;

  for(i=1;i<n;i++){

    if(a[i]-min>result) result=a[i]-min;

    if(a[i]<min) min=a[i];

  }

  printf("%d\n",result);

  return 0;

}

    



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

int main()
{
    int N, x; cin>>N>>x;
    vector<int> a(N); for(auto& e: a) cin>>e;

    long res=0;
    for(int i=0; i<N; ++i) {
        if (a[i]>x) {
            res+=a[i]-x;
            a[i]=x; 
        }
        if (i && a[i]+a[i-1]>x) {
            res+=a[i]+a[i-1]-x;
            a[i]-=a[i]+a[i-1]-x;
        }
    }
    cout<<res<<endl;
}

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

signed
main(){
	ll N;
	cin >> N;
	vector<ll> d(N);
	for(int i=0;i<N;i++) cin >> d[i];
	sort(d.begin(), d.end());

	ll ans = d[N/2] - d[N/2-1];
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j,key;
  int A[N+1];
  scanf("%d", &n);

  for (i = 1;i <= n;i++) scanf("%d", &A[i]);
  
  trace(A, n);

  for(j = 2;j <= n;j++){
    key = A[j];
    i = j - 1;
    while(i > 0 && A[i] > key){
      A[i+1] = A[i];
      i = i - 1;
      A[i+1] = key;
    }
    trace(A,n);
  }    
  
  return 0;
}

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

int main(){
  string S,T;
  cin >> S >> T;
  S.push_back(T.at(T.size()-1));
  if(S==T){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3632
<?php
// Here your code !
$input = explode(" ",trim(fgets(STDIN)));
$W = $input[0];
$H = $input[1];
$x = $input[2];
$y = $input[3];
$r = $input[4];
if(0 <= ($x - $r) && ($x + $r) <= $W && 0 <= ($y - $r) && ($y + $r) <= $H){
    echo "Yes";
} else {
    echo "No";
}
?>

Measured memory_bytes: 15392
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<list>
using namespace std;

#define INF 100000

int main(){
  int h,w;
  cin >> h >> w;
  string s;
  int p[h][w];
  queue<pair<int,int> > q;
  for(int i=0;i<h;i++){
    cin >> s;
    for(int j=0;j<w;j++){
      if(s[j] == '.'){
        p[i][j] = 0;
      }
      if(s[j] == '#'){
        p[i][j] = 1;
        q.push(make_pair(i,j));
      }
    }
  }
  int ans = 0;
  while(!q.empty()){
    pair<int,int> now;
    now = q.front();
    q.pop();
    bool flag = false;
    int x,y;
    x = now.first;
    y = now.second;
    if(0 <= x-1){
      if(p[x-1][y] == 0){
        p[x-1][y] = p[x][y]+1;
        flag = true;
        q.push(make_pair(x-1,y));
      }
    }
    if(0 <= y-1){
      if(p[x][y-1] == 0){
        p[x][y-1] = p[x][y]+1;
        flag = true;
        q.push(make_pair(x,y-1));
      }
    }
    if(x+1 < h){
      if(p[x+1][y] == 0){
        p[x+1][y] = p[x][y]+1;
        flag = true;
        q.push(make_pair(x+1,y));
      }
    }
    if(y+1 < w){
      if(p[x][y+1] == 0){
        p[x][y+1] = p[x][y]+1;
        flag = true;
        q.push(make_pair(x,y+1));
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      ans = max(ans,p[i][j]);
    }
  }

  cout << ans-1 << endl;

  return 0;
}


Measured memory_bytes: 12304
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
#define LL long long
using namespace std;
int len;
char ss[12];
LL dfs(int st,LL sum,LL now)
{
	if(st==len)  return sum;
	return dfs(st+1,sum+ss[st+1]-'0',ss[st+1]-'0')+dfs(st+1,sum+now*10+ss[st+1]-'0'-now,now*10+ss[st+1]-'0');
}
int main()
{
//	freopen("Many Formulas.in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",ss+1);
	len=strlen(ss+1);
	printf("%lld\n",dfs(1,ss[1]-'0',ss[1]-'0'));
	//fclose(stdin); fclose(stdout);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
ll n, fa[N], sg[N], num, mx = -1e18, mn = 1e18;
bool vis[N], onc[N], h[N];
vector<int> g[N];

void dfs(int x) {
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (onc[y]) continue;
        dfs(y);
    }
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (onc[y]) continue;
        h[sg[y]] = 1;
    }
    for (; h[sg[x]]; ++sg[x]);
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (onc[y]) continue;
        h[sg[y]] = 0;
    }
}

int main() {
    cin >> n;
    rep(i, 1, n) scanf("%lld", &fa[i]), g[fa[i]].push_back(i);
    int cur = 1;
    for (; !vis[cur]; cur = fa[cur]) vis[cur] = 1;
    for (; !onc[cur]; cur = fa[cur]) onc[cur] = 1;
    rep(i, 1, n) if (onc[i]) {
        dfs(i);
        ++num; mx = max(mx, sg[i]), mn = min(mn, sg[i]);
    }
    puts((num & 1) && mx == mn ? "IMPOSSIBLE" : "POSSIBLE");
    return 0;
}

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

int main (void){
	double n,m,d;
	cin >> n >> m >> d;
	if(d != 0){
		printf("%.10lf\n", (n-d) * 2.0 / n / n * (m-1));
	}else{
		printf("%.10lf\n", (n-d) / n / n * (m-1));
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main(void)
{
	int R[MAX], n;
	
	cin >> n;
	for (int i = 0; i < n; i++) cin >> R[i];
	
	int maxv = -2000000000;
	int minv = R[0];
	
	for (int i = 1; i < n; i++){
		maxv = max(maxv, R[i] - minv);
		minv = min(minv, R[i]);
	}
	
	cout << maxv << endl;
	
	return 0;
}




Measured memory_bytes: 3860
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

const int MAX = 310;

int main() {
    int h, w, k;
	cin >> h >> w >> k;

    vector<string> board(h);
	rep(i, h) {
        cin >> board[i]; 
    } 
    
    vector<bool> empty(MAX, true);
	rep(i, h) {
		rep(j, w) {
            if(board[i][j] == '#') {
                empty[i] = false;
            } 
        } 
	}

    vector<vector<int>> ans(MAX, vector<int>(MAX));
	int cnt = 0;
	rep(i, h) {
		if(empty[i]) {
            continue;
        } 
		rep(j, w) {
			if(board[i][j] == '#') {
                ans[i][j] = ++cnt;
            } 
		}
		rep(j, w) {
			if(ans[i][j] == 0 && j > 0 && ans[i][j-1] != 0) {
                ans[i][j] = ans[i][j-1];
            } 
		}
		for(int j = w-2; j >= 0; j--) {
			if(ans[i][j] == 0 && ans[i][j+1] != 0) {
                ans[i][j] = ans[i][j+1];
            } 
		}
	}
	for(int i = 1; i < h; i++) {
		if(empty[i] && !empty[i-1]) {
			empty[i] = false;
			rep(j, w) {
                ans[i][j] = ans[i-1][j];
            } 
		}
	}
	for(int i = h-2; i >= 0; i--) {
		if(empty[i] && !empty[i+1]) {
			empty[i] = false;
			rep(j, w) {
                ans[i][j] = ans[i+1][j];
            } 
		}
	}

	rep(i, h) {
		rep(j, w) {
            cout << ans[i][j];
            if(j < w-1) {
                cout << " ";
            }
		}
        cout << "\n";
	}

	return 0;
}

Measured memory_bytes: 1280
def solve():
    n = int(input())
    A = list(map(int, input().split()))
    ruiseki = [0]*(n+1)
    cnt_map = {0: 1}

    for i, a in enumerate(A):
        t = ruiseki[i] + a
        ruiseki[i+1] = t
        if t in cnt_map:
            cnt_map[t] += 1
        else:
            cnt_map[t] = 1
    ans = 0
    for cnt in cnt_map.values():
        ans += cnt * (cnt-1) // 2
    print(ans)

solve()

Measured memory_bytes: 40256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int S = 100010;

struct UnionFind {
    vector<int> node;
    vector<ll> weight;
    UnionFind() : node(S, -1), weight(S, 0) {}
    void unite(int u, int v, ll w) {
      int ov = v, ou = u;
      u = find(u), v = find(v);
      int wa = weight[ov], wb = weight[ou];
      if(u == v) return;

        // (v テ」ツ?ョティツヲツェ) テ」ツつ?(u テ」ツ?ョティツヲツェ) テ」ツ?ォテ」ツ?、テ」ツ?ェテ」ツ?津」ツつ?
        node[u] += node[v];
        node[v] = u;
        weight[v] += w + wb - wa;
    }

    ll get_weight(int u) {
        ll ret = 0;
        while(node[u] >= 0) {
            ret += weight[u];
            u = node[u];
        }
        return ret;
    }

    int find(int u) {
      if(node[u] < 0) return u;
      int par = node[u], root = find(node[u]);
      weight[u] += weight[par];
      return node[u] = root;
    }
};

int main() {
    int N, M;
    while(cin >> N >> M, N) {
        UnionFind uf;
        for(int i=0; i<M; i++) {
            char c; cin >> c;
            if(c == '!') {
                int a, b, d; cin >> a >> b >> d;
                a--; b--;
                uf.unite(a, b, d);
            }
            else {
                int a, b; cin >> a >> b;
                a--; b--;
                if(uf.find(a) != uf.find(b)) cout << "UNKNOWN" << endl;
                else {
                    ll wa = uf.get_weight(a);
                    ll wb = uf.get_weight(b);
                    // printf("wa = %d, wb = %d\n", wa, wb);
                    cout << wb - wa << endl;
                }
            }
        }

	/*
	for(int i=0; i<N; i++) {
	  printf("%d: parent = %d, weight = %lld, value = %lld\n", i, uf.node[i], uf.weight[i], uf.get_weight(i));
	}
	*/
    }
    return 0;
}

Measured memory_bytes: 5640
def HMW(n,x):

    answer = 0

    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            for k in range(j + 1, n + 1):
                if i + j + k == x:
                    answer += 1
                else:
                    pass

    print(answer)

while True:
    NX = input().split()
    n = int(NX[0])
    x = int(NX[1])
    if n==0 and x==0:
        break
    else:

        HMW(n, x)



Measured memory_bytes: 5596
#define _USE_MATH_DEFINES
#include <sstream> //string stream its useful!
#include<string>
#include<iostream>
#include<utility> //pair
#include <vector> // vector
#include <algorithm>    // swap,sort,binary_search
#include <functional>   // std::greater
#include <map> //map
#include<set> //set
#include<queue> //queue
#include<list> //list
#include<cmath>
#include<numeric>
#include<cassert>
#include <iomanip> //cout<<setprecision
#include <regex>
#include <ctype.h> //toupper case
#include <tuple>

typedef long long ll;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
ll W = 1000000007;


using namespace std;
void omajinai() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(15);
}

class Main{
public:
    string S;
    Main(){
        std::cin>>S;
    }
    
    void run(){
        const bool adopted = (S.size() >= 4 && S.substr(0,4) == "YAKI");
        std::cout<<(adopted ? "Yes" : "No")<<endl;
    }
};

#ifndef gtest
int main(){
    omajinai();
    Main().run();
    return 0;
}
#endif

Measured memory_bytes: 256
from collections import deque
INF = 10000

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]

dist = [[INF] * W for _ in range(H)]

vx = [-1,1,0,0]
vy = [0,0,1,-1]

def bfs():
    while(q):
        x,y = q.popleft()
        for i in range(4):
            nx = x + vx[i]
            ny = y + vy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] == '.' and dist[nx][ny] == INF:
                q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1
                if (nx, ny) == (gx, gy): return

q = deque()
q.append((0,0))
gx = H-1
gy = W-1
dist[0][0] = 1
bfs()
if dist[gx][gy] == INF: print(-1)
else:
    tmp = 0
    for h in range(H):
        tmp += S[h].count('#')
    print(H*W - dist[gx][gy] - tmp)

Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <functional>
#include <cmath>
using namespace std;

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

	int n, l[3000];
	int cnt = 0;
	int i, j, k;

	cin >> n;
	for (i = 0; i < n; i++)
		cin >> l[i];

	sort(l, l + n);

	for (i = 0; i < n - 2; i++)
	{
		for (j = i + 1; j < n - 1; j++)
		{
			for (k = j + 1; k < n; k++)
			{
				if (l[i] < l[j] + l[k] && l[j] < l[i] + l[k] && l[k] < l[j] + l[i])
					cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  string S;
  cin >> S;
  
  int N = S.size();
  int count, total = 0;
  
  for(int i = 0; i < N; i++){
    if(S.at(0) == S.at(i)){
      count++;
    }
    if(S.at(1) == S.at(i)){
      count++;
    }
    if(S.at(2) == S.at(i)){
      count++;
    }
    if(S.at(3) == S.at(i)){
      count++;
    }
    if(count == 2){
      total++;
    }
    
    count = 0;
  }
  
  if(total == 4){
    cout << "Yes" << endl;
  }
  
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<map>
#include<iomanip>
#include<functional>

using namespace std;
using  ull = unsigned long long int;

#define rep(i,n,m) for(long long int i=n;i<(long long int)(m);i++)


int main() {

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

	if (a < b)cout << "0" << endl;
	else cout << a - b << endl;


	

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

template <typename T>
class FenwickTree {
  const int n;
  vector<T> data;
public:
  FenwickTree(int n) : n(n), data(n, 0) {}
  void add(int i, T value) {
    for (; i < n; i |= i + 1) data[i] += value;
  }
  T sum(int i) const {
    T res = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) res += data[i];
    return res;
  }
  T sum(int l, int r) const { return sum(r - 1) - sum(l - 1); }
};

void solve(ll N, ll K, vector<ll> a) {
  for (ll &i: a) i -= K;
  FenwickTree<ll> bit(N + 1);
  ll sum = 0;
  vector<pair<ll,int>> vec;
  vec.emplace_back(sum, 0);
  REP(i,N) {
    sum += a[i];
    vec.emplace_back(sum, i + 1);
  }
  sort(ALL(vec));
  ll res = 0;
  for (auto p: vec) {
    int i = p.second;
    res += bit.sum(i);
    bit.add(i, 1);
  }
  cout << res << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll K;
	ll N;
	scanf("%lld", &N);
	vector<ll> a(N-1+1);
	scanf("%lld", &K);
	for (int i = 0 ; i <= N-1 ; i++) {
	  scanf("%lld", &a[i]);
	}
	solve(N, K, a);
	return 0;
}


Measured memory_bytes: 11120
fn input_one<T: std::str::FromStr> () -> Result<T, T::Err> {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).unwrap();
    n.trim().parse()
}

fn input_arr<T: std::str::FromStr> () -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().flat_map(str::parse).collect()
}

fn main() {
    let n: usize = input_one().unwrap();
    let a: Vec<usize> = input_arr();
    let mut c = 0;
    for i in a.into_iter() {
        if i == c + 1 {
            c += 1;
        }
    }
    println!("{}", if 0 < c { (n - c) as isize } else { -1 });
}


Measured memory_bytes: 5036
#include <bits/stdc++.h>
using namespace std;
bool d[51][51];
int a,b,s,_x,_y,dx[8]={0,-1,-1,-1,0,1,1,1},dy[8]={1,1,0,-1,-1,-1,0,1};
#define r(z,x) for(int z=0;z<x;z++)
void dfs(int x,int y){
	if(0>x||x>=b||0>y||y>=a)return;
	d[x][y]=0;
	r(i,8)if(d[_x=x+dx[i]][_y=y+dy[i]])dfs(_x,_y);
}
int main(){
	while(cin>>a>>b,a||b){
		s=0;
		r(i,b)r(j,a)cin>>d[i][j];
		r(i,b)r(j,a)if(d[i][j])dfs(i,j),s++;
		cout<<s<<endl;
	}
}

Measured memory_bytes: 3048
A=[]
B=[]
for i in range(3):
    A.append(list(map(int,input().split())))
N=int(input())
for i in range(N):
    B.append(int(input()))
for i in range(3):
    for j in range(3):
        for k in range(N):
            if A[i][j]==B[k]:
                A[i][j]=-1
C=[]
for i in range(3):
    if A[0][0]==A[1][1] and A[1][1]==A[2][2] and A[2][2]==-1:
        C.append('Yes')
    elif A[0][2]==A[1][1] and A[1][1]==A[2][0] and A[2][0]==-1:
        C.append('Yes')
    elif A[i][0]==A[i][1] and A[i][1]==A[i][2]:
        C.append('Yes')
    elif A[0][i]==A[1][i] and A[1][i]==A[2][i]:
        C.append('Yes')
    else:
        C.append('No')
if 'Yes' in C:
    print('Yes')
else:
    print('No')

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

string s;

int main() {
    cin>>s;
    int cnt = 0;
    for(int i=1;i<s.size();++i) {
        if(s[i]==s[i-1]) {
            if(s[i]=='1') s[i]='0';
            else s[i]='1';
            cnt++;
        }
    }
    cout<<cnt;
}

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

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        int marbles = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) == '1')marbles++;
        }
        System.out.println(marbles);
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <stack>
using namespace std;
   
  
   
int main(){
   
    int n; 
    int r[1000],w[1000];
    int sum_r=0,sum_w=0,idx=0;
	
    while(scanf("%d",&n),n){
         
        sum_r=sum_w=idx=0;
        for(int i=0;i<n;i++){
            scanf("%d %d",&r[i],&w[i]);
            sum_r+=r[i];
            sum_w+=w[i];
            if(r[idx]<r[i]) idx=i;
        }
  
        int r0=r[idx],r=sum_r-r0;
        w[idx]=0;
 
        if(r0 <= r){
            cout<<sum_r+sum_w<<endl;
        }else{
  
            int res=2*r0;
            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));
  
//			bool cur[1001]={};
			bool *cur = (bool*)malloc( sizeof(bool)*(1000+2) );
            cur[0]=true;
            for(int i=0;i<n;i++){
				bool *next = (bool*)malloc( sizeof(bool)*(1000+2) );
                for(int j=0;j<=r0-r;j++){
                    if(cur[j]){
                        next[j]=true; 
                        if(j+w[i]<=r0-r)
                            next[j+w[i]]=true; 
                    }
                }
				swap(cur,next);
            }
  
            int opt=r0-r;
            while(!cur[opt]) opt--;
  
            res+=sum_w-opt;
            printf("%d\n",res);
  
  
  
        }
          
          
    }
}

Measured memory_bytes: 7416
N=int(input())
dp=[float('inf') for i in range(100001)]
dp[0]=0

for i in range(1,N+1):
    power=1
    while(power<=i):
        dp[i]=min(dp[i],dp[i-power]+1)
        power*=6
    
    power=1
    while(power<=i):
        dp[i]=min(dp[i],dp[i-power]+1)
        power*=9
print(dp[N])


Measured memory_bytes: 6296
import sys
sys.setrecursionlimit(10 ** 6)

def create_li(li):
  if len(li) >= n:
    lis.append(li)
    return
  p = max(li)
  for i in range(1, p + 2):
    cp = li[:]
    cp.append(i)
 #   print(cp)
    create_li(cp)

lis = []
  
n = int(input())
pre = [1]
create_li(pre)
lis.sort()
al = ["a","b","c","d","e","f","g","h","i","j"]
ans = set(["".join([al[id-1] for id in i]) for i in lis])
ans = list(ans)
ans.sort()
for i in ans:
  print(i)

Measured memory_bytes: 42092
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

def main():
    L = input().strip()
    N = len(L)
    dp = [[0] * (N + 1) for _ in range(2)]
    dp[0][0] = 1
    for i, a in enumerate(L):
        if a == "0":
            dp[0][i + 1] = dp[0][i]
            dp[1][i + 1] = (3 * dp[1][i]) % mod
        else:
            dp[0][i + 1] = (2 * dp[0][i]) % mod
            dp[1][i + 1] = (dp[0][i] + 3 * dp[1][i]) % mod

    # print(dp) 
    print((dp[0][N] + dp[1][N]) % mod)


if __name__ == "__main__":
    main()



Measured memory_bytes: 75924
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

class Stream{
public:
    Stream(){

    }
    //配列以外の入力を受け取る
    void read(){

    }
    template<typename First, typename... Rest>
    void read(First& first, Rest&... rest){
        cin >> first;
        read(rest...);
    }
    //配列を区切って出力する
    template<typename T>
    void write_vec(vector<T>& v, char divider){
        for(size_t i = 0; i < v.size(); i++){
            cout << v[i] << divider;
        }
    }
};

struct UF{
    const int node_num;
    vector<int> parent;
    vector<int> size;

    UF(int N) : node_num(N), parent(N), size(N, 1) {
        for(int i = 0; i < N; ++i) parent[i] = i;
    }

    //xの根を得る
    int root(int x){
        if(parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }

    //xが属する木とyが属する木を一つに合わせる
    void unite(int x, int y){
        int root_x = root(x);
        int root_y = root(y);
        if(root_x == root_y) return;
        parent[root_y] = root_x;
        size[root_x] += size[root_y];
    }

    //xとyが属する木が同じならtrueを返す
    bool same(int x, int y){
        int root_x = root(x);
        int root_y = root(y);
        return root_x == root_y;
    }

    //xと同じ木に属する要素の数を返す
    int same_size(int x){
        int root_x = root(x);
        return size[root_x];
    }
};

int main(){
    Stream io;
    
    int N;
    io.read(N);
    vector<int> A(N);
    for(int i = 0; i < N; i++){
        io.read(A[i]);
    }
    priority_queue<int> q;
    for(int i = 0; i < N; i++){
        q.push(A[i]);
    }
    int m = q.top(); q.pop();
    int mm = q.top();
    for(int i = 0; i < N; i++){
        if(A[i] == m) cout << mm << '\n';
        else cout << m << '\n';
    }

    return 0;
}

Measured memory_bytes: 3316