akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <random>
#include <fstream>
#include <string>
#include <tuple>
#include <deque>
#include <set>
#include <map>

#define REP(i, N) for(int i = 0; i< N; i++)
using namespace std;
#define ll long long
const int INF = 1 << 29;
const ll llINF = 10000000000000000;

const int MOD = 1000000007;


#define MAX_N 200200
class UnionFindTree{
private:
    int par[MAX_N];
    int urank[MAX_N];
public:
    int init(int n);
    int find(int x);
    int unite(int x, int y);
    int same(int x, int y);
    int parnum(int x){return par[x];}
    int ranknum(int x){return urank[x];}
};

int UnionFindTree::init(int n){
    REP(i, n){
        par[i] = i;
        urank[i] = 0;
    }
    return 0;
}

int UnionFindTree::find(int x){
    if(par[x] == x)return x;
    else return par[x] = find(par[x]);
}

int UnionFindTree::unite(int x, int y){
    x = find(x);
    y = find(y);
    
    if(x == y)return 0;
    if(urank[x] < urank[y]){
        par[x] = y;
    }else{
        par[y] = x;
        if(urank[x] == urank[y])urank[x] ++;
    }
    return 0;
}

int UnionFindTree::same(int x, int y){
    return find(x) == find(y);
}

int equals(){
    int N, M;
    cin >> N >> M;
    int p[100100];
    REP(i, N){
        cin >> p[i];
        p[i]--;
    }
    UnionFindTree junretu;
    junretu.init(N);
    REP(i, M){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        junretu.unite(p[x], p[y]);
    }
    int onajidayo = 0;
    
    REP(i, N){
        if(junretu.same(i, p[i])) onajidayo++;
    }
    
    return onajidayo;
}

int main(){
	printf("%d\n", equals());
}

Measured memory_bytes: 1408
n = int(input())
list1 = list(map(int,input().split()))
list2 = list(map(int,input().split()))
list3 = []
for i in range(n):
  list3.append(list1[i]-list2[i])
sum = 0
for j in range(n):
  if list3[j] > 0:
    sum += list3[j]
print(sum)

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

int main() {
	bool d[101];
	for (int i = 0; i < 101; i++) d[i] = false;
	int n,ans=0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int di;
		cin >> di;
		d[di]= true;
	}
	for (int i = 0; i < 101; i++) {
		if (d[i] == true) ans++;
	}
	cout << ans << endl;
	return 0;
}

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

int main(int argc, const char * argv[]) {
    long long n;
    
    long long x;
    vector<long long> a, b;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        a.push_back(x);
    }
    
    //出力
    if (a.size() == 1) {
        cout << a[0] << endl;
    }else if (a.size() % 2 == 0) {
        for (long long i = n-1; i >= 0; i-=2) {
            cout << a[i] << ' ';
        }
        for (long long i = 0; i < n; i+=2) {
            cout << a[i];
            if (i < n-1-1) {
                cout << ' ';
            }else{
                cout << endl;
            }
        }
    }else{
        for (long long i = n-1; i >= 0; i-=2) {
            cout << a[i] << ' ';
        }
        for (long long i = 1; i < n; i+=2) {
            cout << a[i];
            if (i < n-1-1) {
                cout << ' ';
            }else{
                cout << endl;
            }
        }
    }
    
    
    return 0;
}

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

using namespace std;

int main() {
    int H, W;
    cin >> H >> W;

    for (int i = 0; i < W+2; ++i) cout << '#';
    cout << endl;

    for (int i = 0; i < H; ++i) {
        string s;
        cin >> s;
        cout << '#' << s << '#' << endl;
    }

    for (int i = 0; i < W+2; ++i) cout << '#';
    cout << endl;

    return 0;
}

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

int main(){
	int n;
	double sum, x;
	string u;
	sum = 0;
	cin >> n;

	for(int i=0; i<n; i++){
		cin >> x >> u;
		if(u == "JPY"){
			sum += x;
		}else{
			sum += x*380000;
		}
	}
	cout << sum << endl;
}


Measured memory_bytes: 256
using System;

class Program
{
    static void Main(string[] args)
    {
        string str = Console.ReadLine();
        int second = int.Parse(str);

        int h, m, s;
        h = second / 3600;
        second %= 3600;

        m = second / 60;
        second %= 60;

        s = second;

        Console.WriteLine(h + ":" + m + ":" + s);
    }
}




Measured memory_bytes: 9160
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int r;
    cin >> r;
    cout << 1LL *r*r;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

typedef vector<vector<lli> > matrix ;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{

    lli a, b, c, k;
    cin>>a>>b>>c>>k;
    lli ans = 0;
    lli x = min(a, k);
    ans += x;
    k -= x;
    x = min(k, b);
    k -= x;
    x = min(k, c);
    ans -= x;
    cout<<ans;
    cout<<"\n";
    return ;
}

/*
*/

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

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}


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

using namespace std;
typedef long long ll;
const ll inf = 1LL<<61;

typedef vector<ll> vertices;
struct arc{
    int s;
    int t;
    ll w;
};
typedef vector<arc> arcs;



int main(){
    int n, m;
    cin >> n >> m;
    
    vertices vs(n+1);
    arcs as(m);
    vector<vector<int> > to(n+1);
    vector<vector<int> > from(n+1);
    for(int i=0; i<m; i++) {
        int s, t;
        ll w;
        cin >> s >> t >> w;
        as[i].s = s;
        as[i].t = t;
        as[i].w = -w;
        to[s].push_back(t);
        from[t].push_back(s);

    }
    vs[1] = 0;
    for(int i=2; i<=n; i++) {
        vs[i] = inf;
    }
    for(int i=1; i<=n; i++) {
        for(auto a : as) {
            if(vs[a.t] > vs[a.s] + a.w) {
                vs[a.t] = vs[a.s] + a.w;
            }
        }
    }
    
    vector<bool> loop(n+1);
    for(auto a : as) {
        if(vs[a.t] > vs[a.s] + a.w) {
            loop[a.s] = true;
        }
    }

    vector<bool> from1(n+1);
    vector<bool> toN(n+1);
    from1[1] = true;
    toN[n] = true;
    deque<int> que;
    que.push_back(1);
    while(!que.empty()) {
        int v = que.front();
        que.pop_front();
        for(auto r : to[v]) {
            if(!from1[r]) {
                from1[r] = true;
                que.push_back(r);
            }
        }
    }
    que.push_back(n);
    while(!que.empty()) {
        int v = que.front();
        que.pop_front();
        for(auto r : from[v]) {
            if(!toN[r]) {
                toN[r] = true;
                que.push_back(r);
            }
        }
    }
    
    bool is_inf = false;
    for(int i=1; i<=n; i++) {
        if(from1[i] && toN[i] && loop[i]) {
            is_inf = true;
            break;
        }
    }
    if(is_inf) {
        cout << "inf" << endl;
    } else {
        cout << -vs[n] << endl;
    }


    return 0;
}

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

const int N=200010;
char s[N];
int sum[N];

int main()
{
    scanf("%s",s);
    int n=strlen(s);
    for(int i=n-1;i>=0;i--)
        sum[i]=sum[i+1]+(s[i]=='W');
    long long ans=0;
    for(int i=0;i<n;i++)
        if(s[i]=='B') ans+=sum[i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define speedhack ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define fromfile freopen("input.txt", "r", stdin);  freopen("output.txt", "w", stdout); 
#define mod int (1e9+7)
#define MAXN int (1e9)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;


int n,x,l;



int main() {

    //fromfile;
    speedhack;
    cin >> n >> x;
    vector<int> dp(n+1,MAXN);
    vector<int> h;
    h.pb(0); // shifting index
    for (int j = 0; j<n; j++){
        cin >> l;
        h.pb(l);
    }
    dp[1] = 0;
    for (int k = 2; k<=n; k++){
        for (int j = 1; j<=x; j++){
            if (k-j > 0){
                dp[k] = min(dp[k], dp[k-j] + abs(h[k] - h[k-j]) );
            }
        }
    }
    cout << dp[n];

    }

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

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

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

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

uint64_t lcm(uint64_t m, uint64_t n) {
  uint64_t g = gcd(m,n);
  if(m%g==0) return (m/g)*n;
  if(n%g==0) return (n/g)*m;
  return (m*n)/gcd(m,n);
}

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

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

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

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

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

/* 
  //エラトステネスのふるい
  int maxNum = 100000;
  char isNotPrime[maxNum+1] = {};
  isNotPrime[0]=isNotPrime[1]=1;
  for(int i=2;i<maxNum;i++){
    if(isNotPrime[i]==1) continue;
    int num = i+i;
    while(num<=maxNum){
      isNotPrime[num]=1;
      num += i;
    }
  }
*/
// 円周率
// M_PI

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

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

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

// keyが降順ソートされるmap
// map<int, int, std::greater<int>> edges;

signed main() {
  int n,m;
  cin >> n >> m;

  vector< vector<int> > ship(n);
  int a,b;
  for(int i=0;i<m;i++){
    cin >> a >> b; a--; b--;
    ship[a].push_back(b);
    ship[b].push_back(a);
  }
  
  for(auto nI:ship[0]){
    for(auto nnI:ship[nI]){
      if(nnI==n-1){
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }
  cout << "IMPOSSIBLE" << endl;
  
  return 0;
}



Measured memory_bytes: 15128
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    for(ll k = 1; n != 0; k *= -2) {
        s.push_back(n % (k * -2) == 0 ? '0' : '1');
        n -= s.back() == '1' ? k : 0;
    }
    if(s.empty()) {
        s.push_back('0');
    }
    while(s.size() > 1 and s.back() == '0') {
        s.pop_back();
    }
    reverse(s.begin(), s.end());
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

vector<pair<char,int>> BubbleSort(vector<pair<char,int>> C,int  N){
    for(int i = 0;i < N;i++){
        for(int j = N-1;j > i;j--){
            if(C[j].second < C[j-1].second){
                //C[j] と C[j-1] を交換
                swap(C[j],C[j-1]);
            }
        }
    }
    return C;
}

vector<pair<char,int>> SelectionSort(vector<pair<char,int>> C, int N){
    for(int i = 0;i < N;i++){
        int minj = i;
        for(int j = i;j < N;j++){
            if (C[j].second < C[minj].second){
                minj = j;
                
            }
        }
        //C[i] と C[minj] を交換
        swap(C[i],C[minj]);
    }
    return C;
}

//ミョ(-ω- ?)
int main() {
    int n;
    cin >> n;
    vector<pair<char,int>> vp(n);
    rep(i,n){
        string s;
        cin >> s;
        char c = s[0];
        int num = s[1] - '0';
        vp[i] = make_pair(c,num);
    }
    auto bubble = BubbleSort(vp,n);
    auto selection = SelectionSort(vp,n);
    
    rep(i,n)cout << (i?" ":"") << bubble[i].first << bubble[i].second;
    cout << endl;
    cout << "Stable\n";

    rep(i,n)cout << (i?" ":"") <<selection[i].first <<selection[i].second;
    cout << endl;
    if(bubble == selection)cout << "Stable\n";
    else cout << "Not stable\n";

    return 0;
}


Measured memory_bytes: 3168
#include <stdio.h>
 
int main()
{
  int n, i, x4=0, x2=0, xn=0;
  int a;
 
  scanf("%d", &n);
  for (i=0; i<n; i++){
    scanf("%d", &a);
    if (a % 4 == 0) x4++;
    else if (a % 2 == 0) x2++;
    else xn++;
  }
 
  if (x2 == 0){
    if (xn <= x4 + 1) puts("Yes");
    else puts("No");
  } else{
    if (xn <= x4) puts("Yes");
    else puts("No");
  }
 
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;
 
int main() {
  int n, m=0;
  cin >> n;
  vector<int> a(n), ans(n, 0);
  rep(i, n) cin >> a.at(i);
  for(int i = n; i > 0; i--) {
    if(i > (n / 2)) {
      ans.at(i-1) = a.at(i-1);
    }else{
      int sum = 0;
      for(int j = 2 * i; j <= n; j += i) sum += ans.at(j-1);
      if((sum % 2) != a.at(i-1)){ ans.at(i-1) = 1;
      }else{ ans.at(i-1) = 0;}
    }
    if(ans.at(i-1) == 1) m++;
  }
  cout << m << endl;
  for(int i = 0; i < n; i++){
    if(ans.at(i) == 1) cout << i+1 << " ";
  }
}

Measured memory_bytes: 2432
import collections
n = int(input())
a = list(map(int, input().split()))

d = collections.defaultdict(int)
for i in range(n):
    d[i + 1 + a[i]] += 1

ans = 0
for j in range(n):
    ans += d[j + 1 - a[j]]

print (ans)

Measured memory_bytes: 61580
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

int N;
int H[100000];

int main(){
    cin>>N;
    rep(i,N) cin>>H[i];

    int ans=0;
    int sum=0;
    rep(i,N-1){
        if(H[i]>=H[i+1]){
            sum++;
        }else{
            ans=max(ans,sum);
            sum=0;
        }
    }
    ans=max(ans,sum);

    cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
#include <typeinfo>
#include <tuple>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define INF_LONG 1e18
#define rep(i, n) for(int i=0; i<n; ++i)
#define rep1(i, n) for(int i=1; i<=n; ++i)
#define rrep(i, m, n) for(int i=m; i<n; ++i)
#define countof(array) (sizeof(array) / sizeof(array[0]))
typedef long long ll;

#define MAX_N 100000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100
#define MAX_Q 100000

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

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

string ab = {"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
string as = {"abcdefghijklmnopqrstuvwxyz"};

ll gcd(ll x, ll y) {
  if(y==0) return x;
  else return gcd(y, x%y);
}

ll lcm(ll x, ll y) {
  return (x*y)/gcd(x, y);
}

void yes() {
  cout << "Yes" << endl;
}

void no() {
  cout << "No" << endl;
}

void print_array(int array[], int len) {

  for(int i=0; i<len; ++i) {
    cout << array[i] << endl;
  }

}

ll absolute(ll x) {
  return (x<0)? (-1)*x : x;
}

//g++ AtCoder.cpp -o AtCoder
//AtCoder

//--------------------------



int main() {

  ll n, m;
  cin >> n >> m;

  ll res;

  if(n==1&&m==1) {
    res = 1;
  }else if(n==1) {
    res = m-2;
  }else if(m==1) {
    res = n-2;
  }else {
    res = (n-2)*(m-2);
  }

  cout << res << endl;

  return 0;
}


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

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int ame = sc.nextInt();
		int[] arr = new int[N];

		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		Arrays.sort(arr);

		int cnt = 0;
		for (int i = 0; i < arr.length; i++) {
			ame -= arr[i];
			if (ame >= 0) {
				cnt++;
			} else {
				break;
			}
		}

		if (ame > 0) {
			cnt--;
		}
		System.out.println(cnt);
	}
}

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

#define ll long long;
#define pi acos(-1);

int main(){
 //  cout << pi;
   int n;
   cin>>n;
   int arr[n];
   for(int i = 0;i<n;i++){cin>>arr[i];}
   	for(int k = 0;k < n; k++){
		if(k != n-1){
			printf("%d ",arr[k]);
		}else{
			printf("%d\n",arr[k]);
		}
	}

   int size = sizeof(arr)/sizeof(arr[0]);
   for (int i = 1; i < size; i++)
   {
      
      int key = arr[i];
      int j = i-1;
      while (key < arr[j] && j >= 0)
      {
         swap(arr[j+1],arr[j]);
         
         j--;
      }
    // key = arr[j+1];
    	for(int k = 0;k < n; k++){
		if(k != n-1){
			printf("%d ",arr[k]);
		}else{
			printf("%d\n",arr[k]);
		}
	}

    
}
   

   
   return 0;
}


Measured memory_bytes: 3196
# AOJ 1126: The Secret Number
# Python3 2018.7.16 bal4u

while True:
	W, H = map(int, input().split())
	if W == 0: break
	d = [list(input()) for r in range(H)]
	a = [[0 for c in range(W)] for r in range(H)]
	ans = 0
	for r in range(H):
		for c in range(W):
			if d[r][c] >= '0' and d[r][c] <= '9':
				k = int(d[r][c])
				k1 = k2 = 0
				if c > 0: k1 = a[r][c-1]*10 + k
				if r > 0: k2 = a[r-1][c]*10 + k
				a[r][c] = max(k, k1, k2)
				ans = max(ans, a[r][c])
	print(ans);



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

int main(){
	string s; cin>>s;
	set<char> st;
	rep(i,3) st.insert(s[i]);
	cout<<(st.size()==3?"Yes":"No")<<endl;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
int a,b,sum[100002],j,k;
int main()
{
    sum[10000-1]=0;
    for(int i=10000; i<=99999; i++)
    {
        stringstream ss;
        ss << i;
        string s = ss.str();
        int f=0;
        for(j=0,k=s.size()-1;j<s.size(),k>=0;j++,k--)
        {
            if(s[j]!=s[k])
            {
                f=1;
                break;
            }
        }
        if(f==0)
            sum[i]=sum[i-1]+1;
        else
            sum[i]=sum[i-1];
    }
    cin>>a>>b;
if(sum[a]-sum[a-1]==0)
    cout<<sum[b]-sum[a]<<endl;
else
 cout<<sum[b]-sum[a]+1<<endl;
  //  main();
    return 0;
}

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

ans = 0
for i in range(1, N+1):
    tmp = float(1/N)
    now = i
    if now <= K-1:
        for k in range(100):
            now *= 2
            tmp *= float(1/2)
            if now >= K:
                break
    ans += tmp
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll w[MAXN], v[MAXN];
ll dp[MAXN];
int main()
{
    int N, W;
    cin >> N >> W;
    for (int i = 1; i <= N; i++)
        cin >> w[i] >> v[i];
    for (int i = 1; i <= N; i++)
    {
        for (int j = W - w[i]; j >= 0; j--)
            dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
    }


    cout << dp[W];

    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <cctype>

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i,l,n) for(int (i)=(int)(l);(i)<(int)(n);(i)++)
#define d_arr(arr, h, w) rep(i,(h) ){ cout << "["; rep(j,(w) ) { cout << (arr)[i][j] << ", "; } cout << "]" << endl;}
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x);
#define fs first
#define sc second
#define all(n) n.begin(),n.end()

int main()
{
    int ndata;
    set<string> garage;
    int ntrain;
    cin >> ndata;
    rep(i,ndata){
        garage.clear();
        string train;
        cin >> train;
        int ntrain = train.size();
        repi(k,1,ntrain){
            string former = train.substr(0,k);
            string latter = train.substr(k,ntrain);
            garage.insert(former+latter);
            //cout << former+latter << endl;
            garage.insert(latter+former);
            //cout << latter+former << endl;

            reverse( all(former) );
            garage.insert(former+latter);
            //cout << former+latter << endl;
            garage.insert(latter+former);
            //cout << latter+former << endl;

            reverse( all(former) );
            reverse( all(latter) );
            garage.insert(former+latter);
            //cout << former+latter << endl;
            garage.insert(latter+former);
            //cout << latter+former << endl;

            reverse( all(former) );
            garage.insert(former+latter);
            //cout << former+latter << endl;
            garage.insert(latter+former);
            //cout << latter+former << endl;
        }
        cout << garage.size() << endl;
    }
}

Measured memory_bytes: 1292
import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    g[u].append((v, w))
    g[v].append((u, w))

from collections import deque
s = deque()
s.append(0)
visit = [-1]*n
visit[0] = 0
while s:
    u = s.pop()
    for v, w in g[u]:
        if visit[v] == -1:
            if w%2 == 0:
                visit[v] = visit[u]
            else:
                visit[v] = 1 - visit[u]
            s.append(v)
for i in range(n):
    print(visit[i])

Measured memory_bytes: 67888
#include <iostream>
#include <bitset>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
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; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

int main(){
  ll A,B,C,D,N;
  cin >> A >> B >> C >> D;
  cin >> N;
  ll X=N/2,Y=N%2;
  ll T=min(min(D,C*2),min(B*4,A*8)),S=min(min(C,B*2),A*4);
  cout << X*T+Y*S << endl;
}

Measured memory_bytes: 256
s=input()
u=int(s[0]+s[1])
d=int(s[2]+s[3])
if 0<u<=12 and 0<d<=12:
  print('AMBIGUOUS')
elif 0<u<=12 and (d>12 or d==0):
  print('MMYY')
elif (u>12 or u==0) and 0<d<=12:
  print('YYMM')
else:
  print('NA')

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

double count(int m, int k);

int main() {
  int n, k;
  cin >> n >> k;
  double p = 0.0;

  for ( int i = 1; i <= n; i++ ) {
    p += (1.0/n) * count(i, k);
  }

  printf("%.12f\n", p);
  return 0;
}

double count(int m, int k) {
  double p = 1.0;
  while ( m < k ) {
    p /= 2.0;
    m *= 2;
  }
  return p;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>

int main(void) {
    u_int N;
    std::array<std::array<unsigned long long, 21>, 100> dp = {{}};
    std::vector<u_int> seq;

    std::cin >> N;
    seq.reserve(N);
    for (u_int i = 0; i < N; ++i) {
        u_int tmp;
        std::cin >> tmp;
        seq.push_back(std::move(tmp));
    }

    dp[0][seq[0]] = 1;
    for (u_int i = 1; i < N - 1; ++i) {
        for (u_int j = 0; j < 21; ++j) {
            if (dp[i - 1][j] > 0) {
                if (j + seq[i] <= 20) {
                    dp[i][j + seq[i]] += dp[i - 1][j];
                }
                if (j >= seq[i]) {
                    dp[i][j - seq[i]] += dp[i  -1][j];
                }
            }
        }
    }
    std::cout << dp[N - 2][seq[N - 1]] << std::endl;

    return 0;
}

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

int32_t main()
{
    int n,i;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)cin>>a[i];

    int curmin=a[0],ans=0;
    for(i=0;i<n;i++)
    {
        if(a[i]<=curmin)ans++;
        curmin=min(curmin,a[i]);
    }
    cout<<ans<<"\n";
    
    return 0;
}

Measured memory_bytes: 1792
n=int(input())
if n<105:
  print(0)
  exit()
else:
  c=0
  for i in range(105,n+1,2):
    p=0
    for j in range(1,i//2+1,2):
      if i%j==0:
        p+=1
    if p==7:
      c+=1
print(c)

Measured memory_bytes: 38512
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int hok;
        int n = sc.nextInt();
        int num[] = new int[n];
        for(int i = 1;i <= n; i++){
            num[i-1] = sc.nextInt();
        }
        for(int j = 0; j <= n; j++){
            for(int i = 0; i < n - 1; i++){
                if(num[i] < num[i + 1]){
                    hok = num[i];
                    num[i] = num[i + 1];
                    num[i + 1] = hok;
                }
            }
        }
        int a = 0,b = 0,s;
        for(int i = 1;i <= n/2; i++){
        a = a + num[2 * i - 2];
        b = b + num[2 * i - 1];
        }
        if(n % 2 == 1){
            a = a + num[n-1];
        }
        s = a - b;
        if(s < 0){
            s = -s;
        }
        System.out.println(s);
        sc.close();
    }
}

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

int main() {
string s,t;
cin >> s;
cin >> t;
if(s.at(0) == t.at(2)&&s.at(1) == t.at(1)&&s.at(2) == t.at(0)){
    cout << "YES" <<endl;
}
else{
    cout << "NO" <<endl;
}
}

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

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi; 
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef priority_queue<int> pqi;
typedef priority_queue<int, vi, greater<int>> mpqi;

#define IOS std::ios::sync_with_stdio(false); cin.tie(0);
#define F0R(i,a) for(int i = 0; i < a; i++)
#define R0F(i,a) for(int i = a - 1; i >= 0; i--)
#define pb push_back
#define mp make_pair
#define ins insert
#define ft front()
#define bk back()
#define f first
#define s second
#define trav(a,x) for(auto& a : x)
#define ALL(x) (x).begin(), (x).end()

const int MOD = 1000000007;
const int MX = 2e5+2;
const ll INF = 1000000000000000000;
const ld PI = 4*atan((ld)1);
const pi dir[4] = {{1,0}, {0,1}, {-1,0}, {0,-1}};

// -----------

int n;
int a[100001];

int main(){
    IOS;
    cin >> n;
    F0R(i,n){
        cin >> a[i];
    }
    sort(a,a+n);
    cout << a[n/2] - a[(n/2)-1];
    return 0;
    // You should actually read the notes to self.
}

/* NOTES TO SELF:
    Int overflow? Array bounds?
    Edge cases? (n = 1, n = 0)
    Don't be dumbosity please pace yourself.
*/

Measured memory_bytes: 640
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
ll H, W;
vll dx{-1, 1, 0, 0} , dy{0, 0, 1, -1};
ll cntW = 0, cntB=0;

void dfs(vector<string> &S, vector<vll> &checked, ll x, ll y){
    if(checked[x][y])
        return;
    checked[x][y]=true; 
    if(S[x][y] == '#')
        cntB ++;
    else
        cntW ++;

    REP(k, 4){
        ll xto = x + dx[k], yto = y + dy[k];
        if(0<= xto && xto < H && 0<= yto && yto < W && !checked[xto][yto]){
            if(S[x][y] != S[xto][yto])
                dfs(S, checked, xto, yto);
        }
    }
    return;
}

void solve(long long H, long long W, std::vector<std::string> S){
    vector<vll> checked(H, vll(W, false));
    ll ans = 0;
    REP(x, H){
        REP(y, W){
            if(!checked[x][y]){
                cntW = cntB = 0;
                dfs(S, checked, x, y);
                ans += cntW * cntB;
            }
        }
    }
    cout << ans << endl;
}

int main(){
    scanf("%lld",&H);
    scanf("%lld",&W);
    std::vector<std::string> S(H);
    for(int i = 0 ; i < H ; i++){
        std::cin >> S[i];
    }
    solve(H, W, std::move(S));
    return 0;
}


Measured memory_bytes: 16768
#include<iostream>
#include<string>
using namespace std;
int main (void)
{
	string S;
	cin >> S;
	int length = S.length ();
	if (S [length - 1] == 's')
	{
		cout << S << "es";
		return 0;
	}
	cout << S << "s";
	return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>

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

using namespace std;

int a[222000];

int main() {
  ios::sync_with_stdio(false);
  int n, t;
  while (cin >> n >> t) {
    long long res = 0, next = 0;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) {
      if (i < n && a[i] + t > a[i+1]) next = a[i+1];
       else next = a[i] + t;
      res += (next - a[i]);
    }
    cout << res << endl;
  }
  return 0;
}


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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

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

    if (A >= 6 && A <= 12) B /= 2;
    else if (A <= 5) B = 0;

    cout << B << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
S = [input() for i in range(n)]
a = 0
b = 0
c = 0
d = 0
e = 0
for s in S:
    if s[0]=='M':
        a += 1
    elif s[0]=='A':
        b += 1
    elif s[0]=='R':
        c += 1
    elif s[0]=='C':
        d += 1
    elif s[0]=='H':
        e += 1
print(a*b*c+a*b*d+a*b*e+b*c*d+b*c*e+c*d*e+a*c*d+a*c*e+a*d*e+b*d*e)

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

int main() {
    int n;
    while (cin >> n, n) {
        vector<int> s(n);
        for (int i = 0; i < n; ++i) cin >> s[i];
        sort(s.begin(), s.end());

        int sum = 0;
        for (int i=1; i<n-1; ++i) {
            sum += s[i];
        }
        cout << sum / (n - 2) << endl;
    }
    return 0;
}


Measured memory_bytes: 3164
def f(num):
    s = 0
    while num != 0:
        s += num % 10
        num //= 10 
    return s

n, a, b = map(int,raw_input().split()) 
c = 0
for i in range(1,n+1):
    if b >= f(i) and f(i) >= a:
        c += i
    
print c

Measured memory_bytes: 2948
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int A, B, C, D, E, F;
	cin >> A >> B >> C >> D >> E >> F;
	double ans = 0.0;
	int ans_w = 0, ans_s = 0;
	for (int a = 0; a <= F / 100 / A; a++) {
		for (int b = 0; b <= F / 100 / B; b++) {
			int water = a * 100 * A + b * 100 * B;
			for (int c = 0; c <= (water / 100)* E / C; c++) {
				for (int d = 0; d <= (water / 100) * E / D; d++) {
					int sugar = c * C + d * D;
					//cout << water << " " << sugar << endl;
					if (water + sugar > F || sugar > E * water / 100) continue;
					if ((double)sugar / (water + sugar) > ans) {
						ans = (double)sugar / (water + sugar);
						ans_w = water;
						ans_s = sugar;
					}
				}
			}
		}
	}
	if (ans_w == 0) ans_w = 100 * A;
	cout << ans_w + ans_s << " " << ans_s << endl;
}


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

#define N 2000000

struct node{
  unsigned int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch(int key);
void deleteNode(NodePointer t);
void deleteFirst();
void deleteLast();
void delete(int key);
void insert(int key);

int main(){
  int key, n, i;
  int size = 0, np = 0, nd = 0;
  char com[20];
  scanf("%d", &n);
  
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
  
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if(!( 0 <= key && key <= 2000000000)){
        printf("error");
    }
    if ( com[0] == 'i' ) {
        insert(key);
        np++;
        size++;
    } else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
	if ( com[6] == 'F' ) deleteFirst();
	else if ( com[6] == 'L' ) deleteLast();
      } else {
	delete(key); nd++; 
      }
      size--;
    }
    if ( size > N ) { printf("error"); }
  }

  
  if(!( np+nd <= N)){printf("error") ;}
  if(!( nd <= 20)){printf("error") ;}
  
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");


  return 0;
}

NodePointer listSearch(int key){
  NodePointer cur = nil->next;
  while( cur != nil && cur->key != key ){
    cur = cur->next;
  }
  return cur;
}

void deleteNode(NodePointer t){
  t->prev->next = t->next;
  t->next->prev = t->prev;
  //  free(t);
}

void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
}

void deleteLast(){
  NodePointer t = nil->prev;
  if ( t == nil ) return;
  deleteNode(t);
}

void delete(int key){
  NodePointer t = listSearch(key);
  if ( t == nil ) return;
  deleteNode(t);
}

void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}


Measured memory_bytes: 36232
S = input()
if S == 'SSS':
    print(0)
elif S == 'RSR' or S == 'SRS' or S =='SSR' or S == 'RSS':
    print(1)
elif S == 'RRS' or S == 'SRR':
    print(2)
elif S == 'RRR':
    print(3)

Measured memory_bytes: 9036
def main():
    n = int(input())
    mod = 10 ** 9 + 7

    n1_8 = pow(8, n, mod)
    n0 = (pow(9, n, mod) - n1_8) % mod

    ans = pow(10, n, mod) - n1_8 - n0 * 2
    ans %= mod

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61700
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val p1 = Pair(sc.nextInt(), sc.nextInt())
    val p2 = Pair(sc.nextInt(), sc.nextInt())
    val p3 = nextP(p1, p2)
    val p4 = nextP(p2, p3)
    println("${p3.first} ${p3.second} ${p4.first} ${p4.second}")
}

fun nextP(p1: Pair<Int, Int>, p2: Pair<Int, Int>): Pair<Int,Int> {
    val diffX = p2.first - p1.first
    val diffY = p2.second - p1.second
    return Pair(p2.first - diffY, p2.second + diffX)
}


Measured memory_bytes: 31388
from math import sqrt


def is_prime(n):
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0:
            return False

    return True


def make_divisors(a, b):
    lower_divisors = []
    upper_divisors = []

    i = 1
    n = min(a, b)
    m = max(a, b)

    while i*i <= n:
        if n % i == 0:
            # 大きい方の数が割れるか確認
            if m % i == 0:
                # 素数であるか確認
                if is_prime(i):
                    lower_divisors.append(i)

            # 割り切れる場合 i で割った数も約数
            if i != n // i:

                # i で割った数で大きいほうが割り切れるか
                if m % (n // i) == 0:

                    # 素数であるか
                    if is_prime(n//i):
                        upper_divisors.append(n//i)
        i += 1

    return lower_divisors + upper_divisors[::-1]


def main():
    A, B = [int(x) for x in input().split()]
    divisors = make_divisors(A, B)
    print(len(divisors))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9132
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int SIZEN = 100010;
const LL mod = 1e9+7;
const LL bit = 100001;
int f[SIZEN] = {0};
int g[SIZEN] = {0};
LL pw[SIZEN];
deque<int> q;
int N,M;
char str[SIZEN];    
void Print(int x){
    if(x == 0)return;
    Print(x-g[x]);
    printf("%d ",g[x]);
}
struct Node{
    int lch,rch;
    LL hash;
}t[SIZEN * 30];
int root[SIZEN] = {0};
int node = 0;
void updata(int &rt,int prt,int l,int r,int x,int y){
    rt = ++node;
    t[rt] = t[prt];
    if(l == r){
        t[rt].hash = y;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid)updata(t[rt].lch,t[prt].lch,l,mid,x,y);
    else updata(t[rt].rch,t[prt].rch,mid+1,r,x,y);
    int lch = t[rt].lch,rch = t[rt].rch;
    t[rt].hash = (t[lch].hash * pw[r-mid] % mod + t[rch].hash) % mod;
}
bool get(int rt,int prt,int l,int r){
    if(l == r)return t[rt].hash <= t[prt].hash;
    int mid = (l+r)/2;
    int lch = t[rt].lch,rch = t[rt].rch;
    int plch = t[prt].lch,prch = t[prt].rch;
    if(t[lch].hash != t[plch].hash)return get(lch,plch,l,mid);
    else return get(rch,prch,mid+1,r);
}
int main(){
    pw[0] = 1;
    for(int i = 1;i <= 100000;i++)pw[i] = pw[i-1] * bit % mod;
    scanf("%d%d",&N,&M);
    scanf("%s",str);
    memset(f,0x3f,sizeof f);
    f[0] = 0;
    q.push_front(0);
    for(int i = 1;i <= N;i++){
        if(str[i] == '0' && !q.empty()){
            f[i] = f[q.front()] + 1;
            g[i] = i - q.front();
            updata(root[i],root[q.front()],1,N,f[i],g[i]);
        }
        while(!q.empty() && i+1 - q.front() > M)q.pop_front();
        while(!q.empty() && i+1 - q.back()  > M)q.pop_back();
        if(str[i] == '0'){
            while(!q.empty() && ( f[i] < f[q.front()] || (f[i]==f[q.front()]&&get(root[i],root[q.front()],1,N)) ) )q.pop_front();
            while(!q.empty() && ( f[i] < f[q.back()] || (f[i]==f[q.back()]&&get(root[i],root[q.back()],1,N)) ))q.pop_back();
            q.push_back(i);
        }
    }
    // printf("N = %d\n",N);
    // for(int i = 1;i <= N;i++){
    //     printf("f[%d]=%d,g[%d]=%d\n",i,f[i],i,g[i]);
    // }
    if(f[N] >= 0x3f3f3f3f)puts("-1");
    else Print(N);
    return 0;
}

Measured memory_bytes: 35980
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto & in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;
int32_t A[100000];
int32_t output[100000][2];

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	for (size_t i = 0; i < N; i++)
	{
		in >> A[i];
	}
	std::sort(A, A + N);

	size_t COUNT = 0;
	{
		int32_t i = 1;
		while (A[i] <= 0 && i < N - 1)
		{
			output[COUNT][0] = A[N - 1];
			output[COUNT][1] = A[i];
			++COUNT;
			A[N - 1] -= A[i];
			++i;
		}
		while (i < N - 1)
		{
			output[COUNT][0] = A[0];
			output[COUNT][1] = A[i];
			++COUNT;
			A[0] -= A[i];
			++i;
		}

		output[COUNT][0] = A[N - 1];
		output[COUNT][1] = A[0];
		++COUNT;
		A[N - 1] -= A[0];
		++i;
	}
	
	out << A[N - 1] << endl;
	for (size_t i = 0; i < COUNT; i++)
	{
		out << output[i][0] << ' ' << output[i][1] << '\n';
	}

	return 0;
}
#endif


Measured memory_bytes: 3072
#include <stdio.h>
	
	/*?????????????´???????????????????????????¢??°*/
	void trace( int A[], int N ){	//????????¨????´???°
		int i;
		for ( i = 0; i < N; i++ ){
			if( i > 0 )printf(" ");//????????\??????????´????????????????????¨???????
			printf("%d", A[i]);
		}
		printf("\n");
	}
	/*?????\?????????*/
	void insertionSort( int A[], int N ){
		int i, v, j;
		for ( i = 1; i < N; i++ ){
			v = A[i];
			j = i - 1;
			
			while ( j >= 0 && A[j] > v ){
				A[j+1] = A[j];
				j--;
			}
			A[j + 1] = v;
			trace(A, N);
		}
	}
	
	int main(void){
		int N, i, j;
		int A[100];
		
		scanf("%d", &N);
		for ( i = 0; i < N; i++ ) scanf("%d",&A[i]);
		
		trace(A, N);
		insertionSort(A, N);
				
		return 0;
	}

Measured memory_bytes: 604
#include<bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define zero(v) memset(v,0,sizeof(v))
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
typedef long long ll;
typedef unsigned uint;
const int INF=0x3f3f3f3f;
const double EPS=1e-10;
typedef pair<int,int>P;
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
int main(){
	int k;
	cin>>k;
	string s;
	cin>>s;
	if(SZ(s)<=k){
		cout<<s<<endl;
		return 0;
	}
	rep(i,k)cout<<s[i];
	cout<<"..."<<endl;
	return 0;
}


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

using namespace std;

int SumDigits(int i) {
  int sum = 0;
  while (i) {
    sum += i % 10;
    i /= 10;
  }
  return sum;
}

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int answer = 0;
  for (int i = 1; i <= N; i++) {
    int sum = SumDigits(i);
    if (A <= sum && sum <= B) {
      answer += i;
    }
  }
  cout << answer;

  return 0;
}


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

int main() {
	int n,ans=0;
	cin>>n;
	while(n>0){
	    int res=n%10;
	    if(res==7) ans=1;
	    n=n/10;
	}
	if(ans) cout<<"Yes";
	else cout<<"No";}


Measured memory_bytes: 3596
n = gets.to_i

b = gets.split(' ').map(&:to_i)
a = b.sort
#puts a
carry1 = Array.new(n+1,0)
#line = gets.split(' ').map(&:to_i)
carry2 = Array.new(n+1,0)
ans = 0
count = 1
count2 = 0
for i in 0..n-2
  if a[i] == a[i+1]
    count +=1
  #  count2 = count if i == n-2
  else
    if count > 1
      carry1[a[i]] = count * (count-1) /2
      carry2[a[i]] = (count-1) * (count-2) /2

    end
    count = 1
  end
end

if count > 1
  carry1[a[i]] = count * (count-1) /2
  carry2[a[i]] = (count-1) * (count-2) /2
end

ans = 0

for i in 0..n
  ans += carry1[i]
end

for i in 0..n-1
  puts ans - carry1[b[i]] + carry2[b[i]]
end

Measured memory_bytes: 26348
n,k=map(int,input().split())
kashi = [0] * n
cnt = 0
M = 0
for s in range(k):
	i=int(input())
	li=list(map(int,input().split()))
	if i > 0:
		for m in li:
			kashi[m-1] +=1

for i in kashi:
	if i == 0:
		cnt += 1

print(cnt)
    

Measured memory_bytes: 9188
#include <iostream>
#include <vector>

using namespace std;

using ll = long long int;

template<typename T>
void printv(const vector<T>& v) {
    cout << "{";
    for(auto&& x : v) cout << x << ", ";
    cout << "}" << endl;
}

int main() {
    string s;
    cin >> s;
    vector<ll> arr(13);
    arr[0] = 1;
    for(auto&& c : s) {
        int l = (c=='?') ? 0 : (c - '0');
        int r = (c=='?') ? 9 : (c - '0');
        vector<ll> nxt(13);
        for(int i=l; i<=r; i++) {
            for(int j=0; j<13; j++) {
                nxt[(j*10+13+i)%13] += arr[j];
            }
        }
        for(int j=0; j<13; j++) arr[j] = nxt[j] % 1000000007;
    }
    cout << arr[5] << endl;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	int ans = 0;
	rep(i,n){
		if(i%2 == 0){
			if(s[i] == 'p') --ans;
		}
		else{
			if(s[i] == 'g') ++ans;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3780
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9


int main(){
	int n,k;
	cin>>n>>k;
	double res = 0.0;
	for(int i=n;i>0;i--){
		int cnt = 0;
		int tmp = 1;
		while(i*tmp<k){
			cnt++;
			tmp *=2;
		}
		res +=1.0/(double)tmp;
		//cout<<i<<endl;
	}
	res /= n;
	printf("%0.20lf\n",res);

	return 0;
}


Measured memory_bytes: 256