akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define int long long
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
int x,xx,k,d,mn;
signed main(){
	cin>>x>>k>>d;
	xx=abs(x);
	int mn,mna,mnb;
	mna=xx-xx/d*d;
	if(xx/d>k){
		cout<<xx-d*k<<endl;
	}else{
		int rem=k-xx/d;
//		cout<<rem<<endl;
		mnb=mna-d;
		if(rem%2)cout<<abs(mnb)<<endl;
		else cout<<abs(mna)<<endl;
//		cout<<min(abs(mna),abs(mnb))<<endl;
	}
	return 0;
}
/*
1000000000000000 1000000000000000 1000000000000000
*/


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef pair<int, int> P;

int n, m;
P pa[100000];

signed main() {
	int i;
	
	cin >> n >> m;
	rep(i, n) {
		int a, b;
		cin >> a >> b;
		pa[i] = P(m - a + 1, b);
	}
	sort(pa, pa + n);
	
	priority_queue<int, vector<int>, greater<int>> que;
	rep(i, n) {
		if (pa[i].first <= 0) continue;
		que.push(pa[i].second);
		while (que.size() > pa[i].first) {
			que.pop();
		}
	}
	
	int ans = 0;
	while (!que.empty()) {
		ans += que.top();
		que.pop();
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1660
require 'pp'
     
h, w, k = gets.chomp!.split(" ").map(&:to_i)
cake = []
pos_x = {}
pos_y = {}
h.times do |i|
    chs = gets.chomp!.chars
    cake << chs
    chs.each_with_index do |ch, j|
        if ch == "#"
            pos_x[j] ||= {}
            pos_y[i] ||= {}
            pos_y[i][j] = 1
            pos_x[j][i] = 1
        end
    end
end
 
ans = []
pass_rows = []
index = 1
h.times do |j|
    w.times do |i|
        ans[j] ||= []
        next if ans[j][i] && cake[j][i] == "."
        
        if pos_y[j].nil?
            pass_rows << j
            ans[j] = Array.new(w, -1)
            break
        end
        ans[j][i] = index
        # 今自分がいちご
        if cake[j][i] == "#"
            # みぎの次のいちごまで全部ぬりきう
            if cake[j]
                tmp = i + 1
                while cake[j][tmp] == "."
                    ans[j][tmp] = index
                    tmp += 1
                end
            end
            index += 1
        # 自分はいちごでないが→にいちごがある
        elsif cake[j]
            tmp = i + 1
            while cake[j][tmp] != "#" && cake[j][tmp] != nil
                ans[j][tmp] = index
                tmp += 1
            end
            ans[j][tmp] = index
        end
    end
end

pass_rows.chunk_while {|i, j| i+1 == j }.to_a.each do |x|
    merge_index = x[0] == 0 ? x[-1] + 1 : x[0] - 1

    x.each do |y|
        ans[y] = ans[merge_index]
    end
end
 
ans.each do |x|
    puts x.join(" ")
end


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;
const int MOD = 1e9 + 7;

int main()
{
    int k, s;
    cin >> k >> s;

    int ans = 0;
    rep(i, k + 1)
    {
        rep(j,k+1){
            if(0<=s-i-j && s-i-j<=k){
                ans++;
            }
        }
    }

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


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


map<int, int> f;
void factorize(ll n) {
    for (ll i = 2; i*i <= n; ++i) {
        if (n%i) continue;
        while (n%i == 0) {
            n /= i;
            f[i]++;
        }
    }
    if (n != 1) f[n]++;
}

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

    rep(i, n) factorize(i+1);
    ll ans = 1;
    for (auto x : f) {
        ans *= (x.se+1);
        ans %= MOD;
    }

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

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

int n;
vector<string> A;

void f(int digitNum, string s, int lim){
    bool a = false, b = false, c = false;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '3') a = true;
        if(s[i] == '5') b = true;
        if(s[i] == '7') c = true;
    }
    if(a && b && c){
        A.push_back(s);
    }
    if(digitNum == lim){
        return;
    }
    f(digitNum + 1, s + '3', lim);
    f(digitNum + 1, s + '5', lim);
    f(digitNum + 1, s + '7', lim);
    return;
}

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

    cin >> n;

    int lim = to_string(n).length();

    if(lim < 3){
        cout << 0 << endl;
        return 0;
    }

    f(0, "", lim);

    vector<int> B;
    for(auto &x : A){
        B.push_back(stoi(x));
    }

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

    int idx = upper_bound(B.begin(), B.end(), n) - B.begin();

    cout << idx << endl;

    /*
    int ans = 0;
    for(auto &x : B){
        if(x <= n){
            ans++;
        }
    }
    */

    //cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1916
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>

using namespace std;

#define ll long long int
#define pii pair<int,int>
#define ti3 tuple<ll,ll,ll>

map<int, int> primes(int k)
{
    map<int,int> v;
    for(int i = 2;i <= k;i++)
    {
        while(k % i == 0)
        {
            v[i]++;
            k /= i;
        }
        if(k == 1)
        {
            return v;
        }
    }
    return v;
}

int main()
{
    int n;
    cin >> n;
    map<int,int> m;
    for(int i = 2;i <= n;i++)
    {
        auto v = primes(i);
        for(auto e : v)
        {
            m[e.first] += e.second;
        }
    }
    ll a = 1;
    const ll mod = (ll)(1e9+7);
    for(auto e : m)
    {
        a *= (e.second + 1);
        a %= mod;
    }
    cout << a << endl;
    
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WvNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n;
int heights[N];
int dp[N];
int solve(int i = 0) {
    if (i == n - 1) return 0;
    if (~dp[i])return dp[i];
    int ans = abs(heights[i + 1] - heights[i]) + solve(i + 1);
    if (i < n - 2) {
        ans = min(ans, abs(heights[i + 2] - heights[i]) + solve(i + 2));
    }
    return dp[i] = ans;
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> heights[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << solve();
    return 0;
}


Measured memory_bytes: 4224
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

//累乗 O(log N)
long long power(long long x, long long N){
	if(N == 0) return 1LL;
	if(N == 1) return x;
	long long tmp = power(x, N/2);
	if(N%2 == 0) return tmp * tmp % MOD;
	else return tmp * tmp % MOD * x % MOD;
}

//逆元 O(log x)
long long inverse(long long x){
	return power(x, MOD-2);
}

//コンビネーション
struct Combination{
private:
	int N;
	vector<long long> factorial, inv;
public:
	void init(int n){ //初期化する O(N)
		N = n;
		factorial.push_back(1);
		inv.push_back(1);
		for(long long i=1; i<=N; i++){
			factorial.push_back(factorial.back()*i%MOD);
			inv.push_back(inverse(factorial.back()));
		}
	}
	long long fact(int n){
		return factorial[n];
	}
	long long comb(int n, int k){ //nCkを求める O(1)
		return factorial[n] * inv[k] % MOD * inv[n-k] % MOD;
	}
};

ll N, K;
// K は人がいない部屋の個数の最大値
// K >= 2 だから，同じ部屋への移動を行っても良い

Combination C;

signed main(){
	cin >> N >> K;
	K = min(N-1, K);
	C.init(N);

	ll ans = 0;
	for(ll i=0; i<=K; i++){ // 空き部屋数
		ll tmp1 = C.comb(N, i); // どこを空きにする？
		ll tmp2 = C.comb(i+N-i-1, i); // 余剰の i 人をどうやって N-i 個の部屋に割り振る？
		// 〇が i 個，｜が N-i-1 個
		ans += tmp1*tmp2;
		ans %= MOD;
	}
	cout << ans << endl;
}

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

int main(void)
{
	int n, i, j, score1 = 0, score2 = 0;
	string name_animal1, name_animal2;

	// cout << "何枚，何ターン？" << endl;
	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> name_animal1 >> name_animal2;
		for (j = 0; j < 100; j++) {
			if (name_animal1[j] == '\0' && name_animal2[j] == '\0') {
				score1 += 1;
				score2 += 1;
				break;
			}
			else if (name_animal1[j] == '\0') {
				score2 += 3;
				break;
			}
			else if (name_animal2[j] == '\0') {
				score1 += 3;
				break;
			}
			else if (name_animal1[j] > name_animal2[j]) {
				score1 += 3;
				break;
			}
			else if (name_animal1[j] < name_animal2[j]) {
				score2 += 3;
				break;
			}
		}
	}

	cout << score1 << " " << score2 << endl;

}


Measured memory_bytes: 3144
#include <iostream>
#include <vector>
#include <string>

typedef long long ll;
using namespace std;

int n;

int main()
{
    int k, s;
    cin >> k >> s;
    int ans = 0;

    for (int x = 0; x <= k; x++){
        for (int y = 0; y <= k; y++){
            int z = s - x - y;
            if (z <= k && z >= 0) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
r = gets.to_i
 a = gets.split(" ").map(&:to_i)
 b = gets.split(" ").map(&:to_i)
 sum = 0
r.times do |n|
    if a[n]- b[n] > 0
        sum += a[n]- b[n]
    end
end
puts sum

Measured memory_bytes: 1788
function Main(input){
	var N = parseInt(input,10);
  	var sum = 0;
  	for(var i = 1; i<N+1;i++){
    	if(i%3 == 0 || i%5 == 0){
        }else{
        	sum+=i;
        }
    }
  	console.log(sum);
}
Main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 36216
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <functional>
#include <typeinfo>
#include <utility>
#include <tuple>
#include <queue>

using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define reprrev(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define reprev(i, n) reprrev(i, 0, n)
#define all(arr) (arr).begin(), (arr).end()
#define yn(formula) (formula) ? (cout << "Yes" << endl) : (cout << "No" << endl)
#define YN(formula) (formula) ? (cout << "YES" << endl) : (cout << "NO" << endl)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vp;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vp> vvp;

constexpr double PI = 3.14159265358979323846;
constexpr ll INF = 1ll << 59;
constexpr ll MOD = 1e9 + 7;
constexpr double EPS = 1e-7;
constexpr int dy[4] = { 0, 1, 0, -1 };
constexpr int dx[4] = { 1, 0, -1, 0 };

/*<ここから>***********************************************************/



void dfs(vvi &tree, vi &cost, int v = 0) {

	rep(i, tree[v].size()) {
		if (cost[tree[v][i]] != -1) continue;
		cost[tree[v][i]] = cost[v] + 1;
		dfs(tree, cost, tree[v][i]);
	}
}

int main()
{
	int n;
	cin >> n;
	vvi tree(n);
	vi cost(n, -1);
	vi cost1(n, -1);

	rep(i, n - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	cost[0] = 0;
	dfs(tree, cost);

	cost1[n - 1] = 0;
	dfs(tree, cost1, n - 1);


	int s = 0;
	rep(i, n) {
		if (cost[i] <= cost1[i]) {
			s++;
		}
	}

	if (s > n - s) cout << "Fennec" << endl;
	else cout << "Snuke" << endl;


}


Measured memory_bytes: 11136
// Lec09-C Card Game
#include<iostream>
#include<string>
int main(){
  std::string p1, p2;
  int n, scr1=0, scr2=0;
  for(std::cin >> n; n; n--){
    std::cin >> p1 >> p2;
    if(p1 == p2){
      scr1++, scr2++;
      continue;
    }
    p1.compare(0,p1.length(),p2,0,p2.length())>0 ? scr1+=3 : scr2+=3;
  }
  std::cout << scr1 << " " << scr2 << std::endl;
  return 0;
}

Measured memory_bytes: 3136
/**
 *    author:  tourist
 *    created: 21.01.2020 23:50:28       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, c, k;
  cin >> n >> c >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int ans = 0;
  int t = 0;
  int places = 0;
  for (int x : a) {
    if (x > t || places == 0) {
      t = x + k;
      ans += 1;
      places = c - 1;
    } else {
      places -= 1;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main() { 
    int h, n;
    cin >> h >> n;
    int A[n], B[n];
    long long dp[n+1][h+1];
    for(int i = 0; i < n; ++i) cin >> A[i] >> B[i];

    // 初期化
    for(int i = 0; i < n+1; ++i) for(int j = 0; j < h+1; ++j) dp[i][j] = INF;
    dp[0][0] = 0;

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= h; ++j) {
            chmin(dp[i+1][j], dp[i][j]);
            chmin(dp[i+1][min(A[i]+j, h)], dp[i+1][j] + B[i]);
        }
    }

    cout << dp[n][h] << '\n';

    return 0;
}


Measured memory_bytes: 78464
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define _GLIBCXX_DEBUG

signed main() {
  int N; cin >> N;
  vector<int> vec(N);

  int ans = 0;
  
  rep(i, N) {
    if((i+1) < 10) ans++;
    else if((i+1) >= 100 && (i+1) < 1000) ans++;
    else if((i+1) >=10000 && (i+1) <100000) ans++;
  }

  cout << ans << endl;

}

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

int main()
{
    long long N, M;
    cin >> N >> M;
    vector<pair<long long, long long>> p(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> (p[i]).first >> (p[i]).second;
    }
    sort(p.begin(), p.end());
    long long nokori = M;
    long long keihi = 0;
    for (long long i = 0; i < N; i++)
    {
        if (nokori > (p[i]).second)
        {
            nokori -= (p[i]).second;
            keihi += (p[i]).first * (p[i]).second;
        }
        else
        {
            keihi += (p[i]).first * nokori;
            nokori = 0;
        }
    }
    cout << keihi << endl;
}

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

#define endl '\n'

using namespace std;

const int MAXN=16;
long long points[MAXN][MAXN],dp[(1<<MAXN)+3],total[(1<<MAXN)+3];

void calc_dp(int mask, int curr, int ind, const vector<int>& missing){
    if(ind==(int)missing.size()){
        int new_mask=(mask | curr);
        dp[new_mask]=max(dp[new_mask],dp[mask]+total[curr]);
        return;
    }
    calc_dp(mask,curr,ind+1,missing);
    calc_dp(mask,(curr | (1<<missing[ind])),ind+1,missing);
}

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

    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        for(int i2=0;i2<n;++i2){
            cin>>points[i][i2];
        }
    }

    for(int mask=0;mask<(1<<n);++mask){
        for(int i=0;i<n;++i){
            for(int i2=i+1;i2<n;++i2){
                if((mask & (1<<i)) and (mask & (1<<i2))){
                    total[mask]+=points[i][i2];
                }
            }
        }
    }

    for(int mask=0;mask<(1<<n);++mask){
        vector<int> missing;
        for(int i=0;i<n;++i){
            if(!(mask & (1<<i))){
                missing.push_back(i);
            }
        }
        calc_dp(mask,0,0,missing);
    }

    cout<<dp[(1<<n)-1]<<endl;
return 0;
}

Measured memory_bytes: 1280
// AOJ 0623: Zombie Island
// 2017.11.18 bal4u@uu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define QMAX 100000
typedef struct { int node; long long t; } QUE;
QUE que[QMAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i)
{
	int l, r, min;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t < que[i].t) min = l; else min = i;
	if (r < qsize && que[r].t < que[min].t) min = r;
	if (min != i) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
//	if (qsize == 0) return 0;
//	*n = que[0].node, *t = que[0].t, *c = que[0].c;
	que[0] = que[--qsize];
	min_heapify(0);
//	return 1;
}

void enq(int n, long long t)
{
	int i, min;
	QUE qt;

	i = qsize++;
	que[i].node = n, que[i].t = t;
	while (i > 0 && que[min = PARENT(i)].t > que[i].t) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		i = min;
	}
}

#define MAX QMAX
typedef struct { int len, to[15]; } TBL;
TBL tbl[MAX+1];
int len[MAX+1];
int zombie[MAX+1];
char visited[MAX+1];
char done[MAX+1];
int N, S, P, Q;

void dijkstra1()
{
	int i, s, e, d;

	while (qsize) {
		s = que[0].node, d = (int)que[0].t, deq();
		if (visited[s]) continue;
		visited[s] = 1;
		zombie[s] = d;
		for (i = 0; i < len[s]; i++) {
			e = tbl[s].to[i];
			if (visited[e]) continue;
			enq(e, d+1);
		}
	}
}

long long dijkstra2(int start, int goal)
{
	int i, s, e;
	long long d = 0;

	qsize = 0;
	enq(start, 0);
	while (qsize) {
		s = que[0].node, d = que[0].t, deq();
		if (s == goal) break;
		if (done[s]) continue;
		done[s] = 1;
		for (i = 0; i < len[s]; i++) {
			e = tbl[s].to[i];
			if (done[e]) continue;
			if (zombie[e] <= S) enq(e, d+Q);
			else enq(e, d+P);
		}
	}
	return d-((zombie[goal] <= S) ? Q : P);
}

char buf[40], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int M, K, i, a, b, c;

	fgets(p=buf, 40, stdin);
	N = getint(), p++, M = getint(), p++, K = getint(), p++, S = getint();
	fgets(p=buf, 40, stdin);
	P = getint(), p++, Q = getint();
	qsize = 0;
	for (i = 0; i < K; i++) {
		fgets(p=buf, 40, stdin);
		c = getint()-1, enq(c, 0);
		done[c] = 1;
	}
	for (i = 0; i < M; i++) {
		fgets(p=buf, 40, stdin);
		a = getint()-1, p++, b = getint()-1;
		tbl[a].to[len[a]++] = b;
		tbl[b].to[len[b]++] = a;
	}
	dijkstra1();
	printf("%lld\n", dijkstra2(0, N-1));
	return 0;
}

Measured memory_bytes: 9328
from string import ascii_lowercase as alps

n = int(input())

def solve(x=n, c=0, l=[]):
    if x == 0:
        print(''.join(alps[i-1] for i in l))
        return

    x -= 1

    for nc in range(1, c + 1):
        solve(x, c, l + [nc])

    solve(x, c+1, l + [c+1])

solve()


Measured memory_bytes: 59352
import sys
from collections import deque
input = sys.stdin.readline
S=deque(input()[:-1])
Q=int(input())
r = False
for _ in range(Q):
  qs = input()[:-1].split(' ')
  if len(qs) == 1:
    r = not r
  else:
    if (qs[1] == '1' and (not r)) or (qs[1] == '2' and r):
      S.appendleft(qs[2])
    else:
      S.append(qs[2])
if r:
  print(''.join(reversed(S)))
else:
  print(''.join(S))

Measured memory_bytes: 70704
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
size = 2*10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, size + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
L1 = [1]
L2 = [1]
for _ in range(10 ** 6):
    L1.append(L1[-1] * 25 % mod)
    L2.append(L2[-1] * 26 % mod)

ans = 0
for i in range(K+1):
    ans += L1[K-i] * L2[i] * cmb(K - i + len(S) - 1, len(S) - 1, mod)
    ans %= mod

print(ans)

Measured memory_bytes: 244708
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mem(a) memset(a,0,sizeof(a))
#define lb(x) (x&(-x))
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); 
    std::cout.tie(0);
    int n;cin>>n;
    int a,b,c,d;
    a=b=c=d=0;
    string s1="AC";
    string s2="WA";
    string s3="TLE";
	string s4="RE"; 
	string s;
    for(int i=1;i<=n;i++){
    	cin>>s;
    	if(s==s1) a++;
    	else if(s==s2) b++;
    	else if(s==s3) c++;
    	else if(s==s4) d++;
	}
	cout<<"AC x "<<a<<endl;
	cout<<"WA x "<<b<<endl;
	cout<<"TLE x "<<c<<endl;
	cout<<"RE x "<<d<<endl;
    return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  int n;
  cin >> n;
  if (n >= 195) P(5);
  else if (n >= 189) P(4);
  else if (n >= 165) P(3);
  else if (n >= 135) P(2);
  else if (n >= 105) P(1);
  else P(0);
  return 0;
}



Measured memory_bytes: 256
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<random>
#include<unordered_set>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const int big=1e9+1e8;
const llint red=0xE869120;
const llint pro=1002001;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
int solve(string const& str,const char& c){
	int gen=0,now=0;
	for(int i=0;i<str.size();i++){
		if(str[i]!=c){now++;}else{now=0;}
		maxeq(gen,now);
	}
	maxeq(gen,now);
	return gen;
}
int main(void){
	int ans=big;
	string str;cin>>str;
	for(char c='a';c<='z';c++){mineq(ans,solve(str,c));}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
int i,b,f,r,v,j,k,count;
int room[4][3][10]={0};
scanf("%d",&count);
for(i=0;i<count;i++){
scanf("%d %d %d %d",&b,&f,&r,&v);
room[b-1][f-1][r-1]+=v;
}
for(i=0;i<4;i++){
for(j=0;j<3;j++){
for(k=0;k<10;k++)
printf(" %d",room[i][j][k]);
printf("\n");
}
if(i!=3) printf("####################\n") ;
}
return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    for (int i = 0; i < N; i++) {
        if (A[i] == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = 1;
    for (int i = 0; i < N; i++) {
        if (ans * A[i] < ans) {
            cout << -1 << endl;
            return 0;
        }
        ans *= A[i];
    }
    if ((ll)1e18 < ans) {
        cout << -1 << endl;
        return 0;
    } else {
        cout << ans << endl;
        return 0;
    }
}


Measured memory_bytes: 4052
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <iomanip>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<double, int>;    // (時間, 頂点)

const int MAXN = 1010;

double dist[MAXN];

ll sq(ll x) {
    return x * x;
}

int main() {
    ll xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;

    int N;
    cin >> N;

    vector<ll> x(N + 2, 0), y(N + 2, 0), r(N + 2, 0);
    for (int i = 1; i <= N; i++) {
        cin >> x[i] >> y[i] >> r[i];
    }
    x[0] = xs; y[0] = ys;
    x[N + 1] = xt; y[N + 1] = yt;

    for (int i = 0; i < MAXN; i++) dist[i] = 1e18;

    priority_queue<P, vector<P>, greater<P>> que;

    dist[0] = 0;
    que.push(make_pair(0, 0));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        double cost = p.first;

        if (cost > dist[v]) continue;

        for (int to = 0; to <= N + 1; to++) {
            double ncost = cost + max(0.0, sqrt(sq(x[v] - x[to]) + sq(y[v] - y[to])) - r[v] - r[to]);

            if (dist[to] > ncost) {
                dist[to] = ncost;
                que.push(make_pair(dist[to], to));
            }
        }
    }
    cout << fixed << setprecision(10) << dist[N + 1] << endl;

    return 0;
}

Measured memory_bytes: 6516
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
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(){
  ll a, b;
  cin >> a >> b;
  string s = to_string(a);
  string t = to_string(b);
  string u = s + t;
  ll x = stoi(u);
  bool ans = false;
  for (ll i = 1; i * i <= x;i++){
    if (x % i == 0&&x/i==i){
      ans = true;
    }
  }
  if(ans){
    print("Yes");
  }
  else{
    print("No");
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10

vector<int> A;

int main() {
	int N;
	cin >> N;
	A.assign(N, 0);

	int maxim1 = 0;
	int maxim2 = 0;
	//maxim1 > maxim2
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		if (maxim1 < A[i]) {
			maxim2 = maxim1;
			maxim1 = A[i];
		}
		else if (maxim2 < A[i]) {
			maxim2 = A[i];
		}
	}

	for (int i = 0; i < N; i++) {
		if (A[i] == maxim1) {
			cout << maxim2 << endl;
		}
		else cout << maxim1 << endl;
	}





	return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

const int MAX = 100005;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  // 前処理
  COMinit();

  int n; cin >> n;
  vector<int> a(n+1),idx(n,-1);
  int c;
  rep(i,n+1){
    cin >> a[i];
    a[i]--;
    if(idx[a[i]] == -1) idx[a[i]] = i;
    else c = i - idx[a[i]];
  }
  
  for(int k = 1;k <= n+1; k++){
    cout << (COM(n+1,k) - COM(n-c,k-1)+MOD)%MOD << endl;
  }
}

Measured memory_bytes: 4352
N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
pre_num = 0

for a in As:
    if a == pre_num+1:
        pre_num += 1
    else:
        result += 1

if pre_num == 0:
    result = -1

print(result)


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

int main(int argc, char const *argv[])
{
	int n;
	while(1)
	{
		cin >> n;
		if(n==0) break;
		string s[n];
		for (int i = 0; i < n; ++i) cin >> s[i];
		string code[n];
		int ma=0;
		for (int i = 0; i < n; ++i)
		{
			string tmp;
			tmp.push_back(s[i].at(0));
			for (int j = 0; j < s[i].size()-1; ++j)
			{
				if(s[i].at(j)=='a'||s[i].at(j)=='e'||s[i].at(j)=='i'||s[i].at(j)=='o'||s[i].at(j)=='u')
				{
					tmp.push_back(s[i].at(j+1));
				}
			}
			ma = max(ma, (int)tmp.size());
			code[i]=tmp;
		}

		bool f=1;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if(i==j) continue;
				if(code[i]==code[j]) f=0;
			}
		}
		if (f)
		{
			int ans=0;
			for (int i = 0; i < n; ++i)
			{
				for (int j = 0; j < n; ++j)
				{
					if(i==j) continue;
					int k=0;
					while(k<code[i].size()&&k<code[j].size()&&code[i].at(k)==code[j].at(k)) ++k;
					ans = max(ans, k);
				}
			}
			++ans;
			cout << ans << endl;
		}
		else cout << -1 << endl;
	}
	return 0;
}


Measured memory_bytes: 3156
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int a,b,c,d;
    int ans;
    cin >> a >> b >> c >> d;

    ans = min(b,d) - max(a,c);
    if(ans<0) ans = 0;

    cout << ans << endl;
    return 0;


}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long y = sc.nextLong();
        long next = x ;
        int count = 0;
        while (next <= y) {
            next *= 2;
            count++;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 35668
#include <stdio.h>

int main(void)
{
	int W,H;
	int x, y, r;
	int f;
	scanf("%d %d %d %d %d", &W, &H, &x,&y,&r);

	if (r > x || r > y || 
		x + r > W || y + r > H)
			printf("No\n");
		else
			printf("Yes\n");

	return 0;
}

Measured memory_bytes: 584
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
int n;
while(cin>>n,n){
int masu[20][20]={0};
int x=(n+3)/2,y=(n+1)/2;
int num=1;
masu[x][y]=num;
while(num!=n*n){
if(x+1>n&&y+1>n){
  for(int i=1;;i++){
	if(masu[i][y]==0){num++;masu[i][y]=num;x=i;break;}
  }
}
else if(x+1>n){y++;num++;masu[1][y]=num;x=1;}
else if(y+1>n){x++;num++;masu[x][1]=num;y=1;}
else if(masu[x+1][y+1]==0){x++;y++;num++;masu[x][y]=num;}
else if(x+2>n){num++;masu[1][y]=num;x=1;}
else {x+=2;num++;masu[x][y]=num;}
//cout<<num<<endl;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%4d",masu[i][j]);
}
cout<<endl;
}
}
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define INF 1e9

int main(void){
    string s;
    cin>>s;
    int N = s.size();
    vector<int> dp(1<<26,INF);
    dp[0] = 0;
    int bit = 0;
    rep(i,N){
        bit ^= (1<<(s[i]-'a'));
        rep(j,26) {
            dp[bit] = min(dp[bit], dp[bit^(1<<j)]+1);            
        }
    }
    cout<<max(1,dp[bit])<<endl;
}


Measured memory_bytes: 262912
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,ans=0;
  cin>>n;
  vector<int> l(n);
  for(int i=0;i<n;i++){
    cin>>l[i];
  }for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        vector<int> a={l[i],l[j],l[k]};
        sort(a.begin(),a.end());
        if(a[0]!=a[1]&&a[1]!=a[2]&&a[0]+a[1]>a[2]){
          ans++;
        }
      }
    }
  }cout<<ans<<endl;
}

Measured memory_bytes: 3600
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) p[i] = sc.nextInt();
        int cnt = 0;
        for (int i = 1; i < n-1; i++) {
            if (p[i]>p[i-1] && p[i+1] > p[i] || p[i]<p[i-1] && p[i+1]<p[i])
                    cnt++;
        } System.out.println(cnt);
    }
}

Measured memory_bytes: 23892
#include<stdio.h>
#include<string.h>
    
int LCS(char *X, char *Y){
  int i,j,m,n,c[1001][1001];
  m = strlen(X);
  n = strlen(Y);
      
  for(i=0; i<m; i++){
    c[i][0] = 0;
  }
  for(j=0; j<n; j++){
    c[0][j] = 0;
  }
    
  for(i=1;i<m+1;i++){
    for(j=1;j<n+1;j++){
      if (X[i-1]==Y[j-1]) c[i][j]=c[i-1][j-1]+1;
      else if (c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];
      else c[i][j]=c[i][j-1];
    }
  }
  return c[i-1][j-1];
}
    
int main(){
  int i, q;
  char X[1001], Y[1001];
      
  scanf("%d", &q);
  for(i=0; i<q; i++){
    scanf("%s", X);
    scanf("%s", Y);
    printf("%d\n", LCS(X, Y));
    
  }
  return 0;
}

Measured memory_bytes: 6632
#include<bits/stdc++.h>
#define cal(a,b) ((a+=b)%=mo)
using namespace std;
const int N=3e4,mo=1e9+7;
inline int gi() {
  char ch=getchar(); int q=0,x=0;
  while(ch<'0'||ch>'9') q=(ch=='-'?1:q),ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
int fap(int a,int b){
  int s=1;
  for (; b; b>>=1,a=1ll*a*a%mo)
    if (b&1) s=1ll*s*a%mo;
  return s;
}
int f[N][405],g[N][405],las[N],a[N];
int main(){
  int n=gi(),k=gi(),m=gi(),mx=0,x=0;
  for (int i=1; i<=m; ++i) a[i]=gi();
  for (int i=1; i<=m; ++i)
    x=min(x+1,i-las[a[i]]),las[a[i]]=i,mx=max(mx,x);
  int ans=1ll*(n-m+1)*fap(k,n-m)%mo;
  if (mx==k) return cout<<ans,0;
  if (mx==m){
    f[0][0]=1;
    for (int i=1; i<=n; ++i)
      for (int j=k-1,s1=0,s2=0; j>=1; --j){
	cal(s1,f[i-1][j]),cal(s2,g[i-1][j]);
	cal(f[i][j],1ll*f[i-1][j-1]*(k-j+1)%mo);
	cal(g[i][j],1ll*g[i-1][j-1]*(k-j+1)%mo);
	cal(f[i][j],s1),cal(g[i][j],s2);
	if (j>=m) cal(g[i][j],f[i][j]);
      }
    int sum=0;
    for (int i=1; i<k; ++i)
      cal(sum,g[n][i]);
    for (int i=k-m+1; i<=k; ++i)
      sum=1ll*sum*fap(i,mo-2)%mo;
    cal(ans,mo-sum);
  }
  else{
    int u=0,v=0;
    memset(las,0,sizeof(las));
    for (int i=1; i<=m; ++i)
      if (!las[a[i]]) ++u,las[a[i]]=u;
      else break;
    memset(las,0,sizeof(las));
    for (int i=m; i>=1; --i)
      if (!las[a[i]]) ++v,las[a[i]]=v;
      else break;
    f[0][u]=1,g[0][v]=1;
    for (int i=1; i<=n; ++i)
      for (int j=k-1,s1=0,s2=0; j>=1; --j){
	cal(s1,f[i-1][j]),cal(s2,g[i-1][j]);
	cal(f[i][j],1ll*f[i-1][j-1]*(k-j+1)%mo);
	cal(g[i][j],1ll*g[i-1][j-1]*(k-j+1)%mo);
	cal(f[i][j],s1),cal(g[i][j],s2);
      }
    for (int i=0; i+m<=n; ++i){
      int s=0,t=0;
      for (int j=1; j<k; ++j)
	cal(s,f[i][j]),cal(t,g[n-m-i][j]);
      cal(ans,mo-1ll*s*t%mo);
    }
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 82176
// AOJ 0322: Slates
// 2019.2.24 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

int ins(char *s, char *r)
{
	char *ss = s;
	int n;

	do *s = gc();
	while (*s++ > ' ');
	*--s = 0;
	n = s - ss;
	while (--s >= ss) *r++ = *s;
	*r = 0;
	return n;
}

int N;
char W[50003][205], R[50003][205];
char *w[50003], *r[50003];
char slate[205], res[205];

int cmp(const void *a, const void *b)
{
	return strcmp(*(char **)a, *(char **)b);
}

// Binary Search
int search(char *s, int n, int idx, int part)
{
	int k, mid, low, high;

	low = 0, high = N;
	if (part) {
		while (low < high) {
			mid = (low + high) >> 1;
			if (strncmp(idx ? r[mid] : w[mid], s, n) <= 0) low = mid + 1; else high = mid;
		}
		k = low - 1;
		low = 0, high = N;
		while (low < high) {
			mid = (low + high) >> 1;
			if (strncmp(idx ? r[mid] : w[mid], s, n) < 0) low = mid + 1; else high = mid;
		}
		return k - low + 1;
	}
	else {
		while (low < high) {
			mid = (low + high) >> 1;
			k = strcmp(idx ? r[mid] : w[mid], s);
			if (!k) return 1;
			if (k < 0) low = mid + 1; else high = mid;
		}
	}
	return 0;
}

int main()
{
	int M, i, k, n, one, ans, part, f_res;
	char *s;

	N = in(), M = in(), one = 0;
	for (i = 0; i < N; i++)
		if (ins(w[i] = W[i], r[i] = R[i]) == 1) one++;
	qsort(w, N, sizeof(char *), cmp);
	qsort(r, N, sizeof(char *), cmp);

	while (M--) {
		n = ins(slate, res);
		for (k = 0; k < n; k++) if (slate[k] == '?') break;
		part = f_res = 0, s = slate;
		if (res[0] == '*') {
			slate[--n] = 0, part = 1;
			if (k >= n) k = -1;
		}
		else if (slate[0] == '*') {
			res[--n] = 0, part = 1, s = res, f_res = 1;
			if (k >= n+1) k = -1;
			else k = n - k;
		}
		else if (k >= n) k = -1;

		if (k >= 0) {
			if (n == 1) ans = part ? N : one;
			else {
				ans = 0; for (i = 'a'; i <= 'z'; i++) {
					s[k] = i;
					ans += search(s, n, f_res, part);
				}
			}
		} else ans = search(s, n, f_res, part);
		printf("%d\n", ans);
	}
	return 0;
}



Measured memory_bytes: 22984
#include <algorithm>
#include <iostream>

int main() {
  int a, b, c, d;
  std::cin >> a >> b >> c >> d;

  const int lower = std::max(a, c);
  const int upper = std::min(b, d);

  std::cout << std::max(0, upper - lower) << std::endl;
}
	


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pII;
#define pb push_back
#define mp make_pair
#define clr(x,y) memset(x,y,sizeof(x))
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1e6+5;
//ll fmod(ll x,ll y){ll res=1;while(y){if(y&1)res=res*x%mod;y>>=1;x=x*x%mod;}return res;}
//ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
char s[maxn];
int main()
{
   while(~scanf("%s",s))
   {
       if(s[0] != 'A')
       {
           cout<<"WA"<<endl;
           continue;
       }
       int have = 0;
       int pp = 0;
       int n = strlen(s);
       for(int i = 1; i < n; ++i)
       {
           if(s[i] != 'C'&&(s[i] >= 'B'&&s[i] <= 'Z'))
           {
               have = 1;
               break;
           }
           if(i >= 2&&i <= n-2)
           {
               if(s[i] == 'C')
                pp++;
           }

       }
       if(have||pp != 1)
        cout<<"WA"<<endl;
       else
        cout<<"AC"<<endl;
   }

}















Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		string[] str = Console.ReadLine().Split();
		long[]A = new long[N];
		long[]B = new long[N];
		long[]C = new long[N];
		for(var i=0;i<N;i++){
			A[i] = long.Parse(str[i]);
		}
		B[0] = A[0];
		for(var i=1;i<N-1;i++){
			B[i] = Gcd(B[i-1],A[i]);
		}
		C[N-1] = A[N-1];
		for(var i=N-2;i>=1;i--){
			C[i] = Gcd(C[i+1],A[i]);
		}
		long ans = C[1];
		for(var i=1;i<=N-2;i++){
			ans = Math.Max(ans,Gcd(B[i-1],C[i+1]));
		}
		ans = Math.Max(ans,B[N-2]);
		Console.WriteLine(ans);
	}
	
	public static long Gcd(long a, long b) {
		if (a < b)
			return Gcd(b, a);
		while (b != 0) {
			var r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}

Measured memory_bytes: 26972
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 123;
int n, a[N], b[N], p[N], f[N];

void upd(int x, int y) {
	for (; x <= 2 * n; x |= (x + 1))
		f[x] += y;
}

int getsum(int x) {
	int res = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		res += f[x];
	return res;
}

ll get(int x) {
	for (int i = 1; i <= n; i++) {
		if (a[i] <= x) b[i] = 1;
		else b[i] = -1;
	}
	upd(n, 1);
	ll res = 0;
	for (int i = 1; i <= n; i++) {
		p[i] = p[i - 1] + b[i];
		res += getsum(p[i] + n - 1);
		upd(p[i] + n, 1);
	}
	upd(n, -1);
	for (int i = 1; i <= n; i++)
		upd(p[i] + n, -1);
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int l = 0, r = 1e9 + 123;
	ll k = ((ll)n * (n + 1)) / 2;
	while (l < r - 1) {
		int mid = l + r >> 1;
		if (get(mid) >= k / 2 + 1)
			r = mid;
		else
			l = mid;
	}
	cout << r;
}


Measured memory_bytes: 5588
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	vector<int> a(n);
	for( auto &k : a ) cin >> k;
	int g = set<int>( a.begin(), a.end() ).size();
	bool flag;
	if( g == 1 ){
		flag = ( n >= 2*a[0] || a[0] == n-1 ) ? true : false;	
	} else if ( g >= 3 ){
		flag = false;
	} else {
		sort( a.begin(), a.end() );
		int x = a.front(), y = a.back();
		if( y-x != 1 ) flag = false;
		else {
			int s = upper_bound( a.begin(), a.end(), y ) - lower_bound( a.begin(), a.end(), y);
			flag = ( s >= 2 && n-s < y && (y-n+s)*2 <= s ) ? true : false;
		}
	}
	cout << ( flag ? "Yes" : "No" ) << endl;
	return 0;
}

Measured memory_bytes: 5376
#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;

int main() {
    int n;
    cin >> n;
    int m = n/2;

    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());  // aを降順ソート

    ll ans = 0;
    if(n%2 == 0) {  // nが偶数のとき(n = 2m)
        
        rep(i, m-1) {
            ans += 2*a[i];
        }
        ans += a[m-1];
        ans -= a[m];
        for(int i = m+1; i < n; i++) {
            ans -= 2*a[i];
        }

    }
    else {  // nが奇数のとき(n = 2m+1)
        
        // p_1 >= p_2 <= p_3 >= … =< p_2m >= p_(2m+1) のとき
        ll ans1 = 0;
        rep(i, m-1) {
            ans1 += 2*a[i];
        }
        ans1 += a[m-1];
        ans1 += a[m];
        for(int i = m+1; i < n; i++) {
            ans1 -= 2*a[i];
        }

        // p_1 <= p_2 >= p_3 <= … => p_2m <= p_(2m+1) のとき
        ll ans2 = 0;
        rep(i, m) {
            ans2 += 2*a[i];
        }
        ans2 -= a[m];
        ans2 -= a[m+1];
        for(int i = m+2; i < n; i++) {
            ans2 -= 2*a[i];
        }

        ans = max(ans1, ans2);
    }

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

Measured memory_bytes: 1024
# オイラーツアーのテスト

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def eular_tour(G, root):
    # G は破壊的に有向木にされる
    # グラフは 1-indexed が良い
    n = len(G)
    stack = [root]
    tour = [0] * 0
    first = np.full(n, -100, dtype=np.int64)
    last = np.full(n, -100, dtype=np.int64)
    while stack:
        v = stack.pop()
        if first[v] >= 0:
            last[v] = len(tour)
            tour.append(-v)  # 帰りがけの辺の表現をマイナス以外にしたい場合ここを変える
            continue
        first[v] = len(tour)
        tour.append(v)
        stack.append(v)
        for u in G[v]:
            G[u].remove(v)
            stack.append(u)
    tour = np.array(tour, dtype=np.int64)
    return tour, first, last

def dfs1(v, G, Siz):
    tour, first, last = eular_tour(G, 0)
    Siz[:] = last - first + 1 >> 1
    return 0

# def dfs1(v, G, Siz):
#     siz = 1
#     for u in G[v]:
#         G[u].remove(v)
#         siz += dfs1(u, G, Siz)
#     Siz[v] = siz
#     return siz

def dfs(v, N, C, G, Cnt, Siz, Ans):
    color = C[v]
    cnt_old = Cnt[color]
    siz = 1
    siz_up = N
    for u in G[v]:
        Cnt[color] = N - Siz[u]  # 上を塞ぐ
        s = dfs(u, N, C, G, Cnt, Siz, Ans)
        siz += s
        siz_up -= s
        Ans[color] += s * (siz_up - cnt_old)
    Ans[color] += siz_up - cnt_old
    Cnt[color] = cnt_old + siz
    return siz

def solve(N, C, AB):
    G = [[0]*0 for _ in range(N)]
    for i in range(N-1):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    Cnt = np.zeros(N, dtype=np.int64)
    Ans = np.zeros(N, dtype=np.int64)
    Siz = np.zeros(N, dtype=np.int64)
    dfs1(0, G, Siz)
    dfs(0, N, C, G, Cnt, Siz, Ans)
    return Ans

numba_compile([
    [eular_tour, "Tuple((i8[:],i8[:],i8[:]))(List(List(i8)),i8)"],
    [dfs1, "i8(i8,List(List(i8)),i8[:])"],
    [dfs, "i8(i8,i8,i8[:],List(List(i8)),i8[:],i8[:],i8[:])"],
    [solve, "i8[:](i8,i8[:],i8[:,:])"],
])

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(505050)
N = int(input())
C = np.array(input().split(), dtype=np.int64) - 1
AB = np.array([list(map(int, input().split())) for _ in range(N-1)], dtype=np.int64) - 1
Ans = solve(N, C, AB)
print("\n".join(map(str, Ans)))


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

//Made with <3 by MinumCoklatPanas
typedef long long ll;
const int INF = 1e9;
const ll INFF = 1e18;
const int MAXN = 510;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double INFD = 1E9;
const double EPS = 1e-9;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int l,r,d;
    cin >> l >> r >> d;
    int ans = 0;
    for (int i = l ; i <= r ; i++)
        ans += (i % d == 0);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608