akhauriyash/Code-Regression huggingface dataset:
/**
	优先走第一个动作，如果第一个动作走完了，还是没达到终点
	再走第二个动作。这就需要用双端队列进行操作 
*/
#include<cstdio>
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
#define IOS ios::sync_with_stdio(false)
#define x first
#define y second 
const int maxn = 1e3 + 5;
char mp[maxn][maxn];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int path[maxn][maxn], n, m;
bool vis[maxn][maxn];
pii st, en;
int bfs(){
	deque<pii>	q;
	memset(path, -1, sizeof(path));
	q.push_front(st);
	path[st.x][st.y] = 0;
	while (!q.empty()){
		pii now = q.front(); q.pop_front();
		if (now.x == en.x && now.y == en.y)	return path[now.x][now.y];
		for (int i = 0; i < 4; ++i){
			int dx = now.x + dir[i][0];
			int dy = now.y + dir[i][1];
			if (mp[dx][dy] == '.' && (path[dx][dy] == -1 || path[dx][dy] > path[now.x][now.y])){
				path[dx][dy] = path[now.x][now.y];
				q.push_front(pii(dx, dy));
			}
		}
		// 以当前坐标为中心的3个方块为圆内的路 
		for (int dx = now.x - 2; dx <= now.x + 2; ++dx){
			for (int dy = now.y - 2; dy <= now.y + 2; ++dy){
				if (dx < 1 || dy < 1 || dx > n || dy > m)	continue;
				if (mp[dx][dy] == '.' && path[dx][dy] == -1){
					path[dx][dy] = path[now.x][now.y] + 1;
					q.push_back(pii(dx, dy));
				}
			}
		}
	}
	return -1;
}
void solve(){
	cin >> n >> m;
	cin >> st.x >> st.y;
	cin >> en.x >> en.y;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			cin >> mp[i][j];
		}
	}
	cout << bfs() << endl;
}
int main(){
	IOS;
	solve();
	return 0;
}


Measured memory_bytes: 8612
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)      x.begin(), x.end()
#define rep(i,n)    for (i64 i = 0; i < (n); ++i)
#define reps(i,s,t) for (i64 i = (s); i <= (t); ++i)
#define repr(i,s,t) for (i64 i = (s); i >= (t); --i)

#ifdef DBG
#define trace(...) _trace(#__VA_ARGS__, __VA_ARGS__);
#else
#define trace(...)
#endif

using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a ? (a=b,1) : 0;}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a ? (a=b,1) : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
ostream& operator<< (ostream &os, const vector<T> &vec) {
    rep(i, vec.size()) os << vec[i] << (i+1 == vec.size() ? "" : " ");
    return os;
}

template<class T, class U>
ostream& operator<< (ostream &os, const pair<T, U> &p) {
    return os << p.first << ' ' << p.second;
}

template <class T>
void _trace(const char *s, T&& x)
{
    clog << '{';
    while(*s != '0' && *s != ',') clog << *(s++);
    clog << ":" << setw(3) << x << '}' << endl;
}

template <class Head, class... Tail>
void _trace(const char *s, Head&& head, Tail&&... tail)
{
    clog << '{';
    while(*s != ',') clog << *(s++);
    clog << ":" << setw(3) << head << "}, ";
    for (++s; !isgraph(*s); ++s);
    _trace(s, std::forward<Tail>(tail)...);
}
// }}} End Header

signed main()
{
    // ios::sync_with_stdio(false); cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;

    cout << ((b-a == c-b) ? "YES" : "NO") << "\n";

    return 0;
}


Measured memory_bytes: 256
a, b, c = map(int, input().split())
k = int(input())
flag = 0


def map(now_a, now_b, now_c, now_k):
    if now_a < now_b and now_b < now_c:
        return 1
    elif now_k == 0:
        return 0
    else:
        r1 = map(now_a*2, now_b, now_c, now_k-1)
        r2 = map(now_a, now_b*2, now_c, now_k-1)
        r3 = map(now_a, now_b, now_c*2, now_k-1)
        if r1+r2+r3 == 0:
            return 0
        else:
            return 1


if map(a, b, c, k) == 0:
    print("No")
else:
    print("Yes")



Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read(){
	LL x=0;
	char ch=getchar();
	while (!isdigit(ch))
		ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int N=100005;
int n,a[N],b[N];
LL calc(){
	LL ans=0;
	for (int i=1;i<n;i++)
		ans+=abs(a[b[i]]-a[b[i+1]]);
	return ans;
}
int main(){
	n=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	sort(a+1,a+n+1);
	int t=0;
	for (int i=1;i<=n;i+=2)
		b[i]=++t;
	for (int i=(n|1)^1;i>=1;i-=2)
		b[i]=++t;
	if (n&1)
		swap(b[1],b[n-2]);
	else
		swap(b[1],b[n-1]);
	LL ans=calc();
	reverse(a+1,a+n+1);
	ans=max(ans,calc());
	cout << ans;
	return 0;
}
/*
4 1 9 1 5 3 
3 + 8 + 8 + 4 + 2
4 1 5 1 9 3
1 4 1 5 3 9
*/

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x, n) bitset<n>(x)
#define PI 3.14159265358979323846

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

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

const int MOD = 10000;
string A, B;
int M;
int dp[510][10][510][3][2];

// inc = 0:前回増今回減, 1:前回減今回増, 2:未定
int DP(string S, int dgt, int num, int rem, int inc, int ok) {
	if (dgt == S.size()) return rem == 0;
	if (dp[dgt][num][rem][inc][ok] != -1) return dp[dgt][num][rem][inc][ok];
	int sum = 0, cur = S[dgt] - '0';
	for (int i = 0; i <= (ok ? 9 : cur); i++) {
		if (inc == 0 && i >= num) continue;
		if (inc == 1 && i <= num) continue;
		if (inc == 2 && num != 0 && num == i) continue;
		int nxt_inc;
		if (inc == 2) {
			if (num == 0) nxt_inc = 2;
			else if (num > i) nxt_inc = 1;
			else nxt_inc = 0;
		}
		else nxt_inc = 1 - inc;
		sum += DP(S, dgt + 1, i, (rem * 10 + i) % M, nxt_inc, (ok || i != cur));
		sum %= MOD;
	}
	//cout << dgt << "," << num << "," << rem << "," << inc << "," << ok << " = " << sum << endl;
	return dp[dgt][num][rem][inc][ok] = sum % MOD;
}

int init() {
	REP(i, 510) REP(j, 10) REP(k, 510) REP(l, 3) REP(m, 2) dp[i][j][k][l][m] = -1;
}

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

	cin >> A >> B >> M;
	int i = 0;
	while(A[A.size() - i - 1] == '0') {
		A[A.size() - i - 1] = '9';
		i++;
	}
	A[A.size() - i - 1]--;
    if (A[0] == '0') {
		string C;
		FOR(j, 1, (int)A.size()) {
			C += A[j];
		}
		A = C;
	}

	init();
    int a_ans = DP(A, 0, 0, 0, 2, 0);
	//cout << endl;
	init();
	int b_ans = DP(B, 0, 0, 0, 2, 0);
	//cout << a_ans << ',' << b_ans << endl;
	cout << (b_ans - a_ans + MOD) % MOD << endl;

	return 0;
}




Measured memory_bytes: 64416
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);

//const ll INFL = LLONG_MAX;//10^18 = 2^60
const ll INFL = 1LL<<60;
//const int INF = INT_MAX;
const ll INF = 1 << 30;//10^9
ll MOD = 1000000007;
//ll MOD = 998244353;

vector<ll> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};

void pres(double A){printf("%.9lf\n", A);}
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}
ll cnt_bit(ll x){return __builtin_popcountll(x);}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x; k /= 2;
  }
  return res;
}

ll pow_mod(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

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

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


//コンビネーション
const int MAXcomb = 2000010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; 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;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

const int MAXkai = 200010;
ll kai_memo[MAXkai];
ll kai(ll N){
  if(kai_memo[N] != 0) return kai_memo[N];
  if(N <= 1) return 1;
  return kai_memo[N] = N * kai(N-1) % MOD;
}
ll N;
vector<pair<ll, pair<ll, ll>>> HP;
ll dp[5010][5010];
void solve(){
  cin >> N;
  HP.resize(N);
  rep(i, N){
    cin >> HP[i].s.f >> HP[i].s.s;
    HP[i].f = HP[i].s.f + HP[i].s.s;
  }
  sort(HP.begin(), HP.end());
  rep(i, 5010)rep(j, 5010) dp[i][j] = INFL;
  dp[0][0] = 0;
  rep(i, N)rep(j, N){
    dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
    if(dp[i][j] <= HP[i].s.f){
      dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + HP[i].s.s);
    }
  }
  ll ans = 0;
  rep(j, N+1)if(dp[N][j] != INFL) ans = j;
  cout << ans << endl;
}


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


Measured memory_bytes: 196992
# 32:35
n = int(input())

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

values = dict()

for ii, h in enumerate(heights):
    c1 = ii - h
    if (c1) in values:
        values[c1].append((ii, h))
    else:
        values[c1] = [(ii, h)]

count = 0
for j, h in enumerate(heights):
    if (j + h) in values:
        count += len(values[j + h])
        # for i, ai in values[j + h]:
        #     if i > 0 and i > j and not (j, i) in count:
        #         count[(j, i)] = True


print(count)

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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << 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; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

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

int main(){

  string s;cin>>s;
  string ans="CODEFESTIVAL2016";

  ll count=0;
  rep(i,0,ans.size()){
    if(s[i]!=ans[i])count++;
  }
  out(count);


  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  ll a,b,n;
  cin >> a >> b >> n;
  if(a==1)cout << 0 << endl;
  else if(n>=b-1){
    cout << a*(b-1)/b-a*((b-1)/b) << endl;
  }
  else cout << a*n/b-a*(n/b) << endl;
    
  return 0;     
}


Measured memory_bytes: 3640
import java.util.*;

class Main{
	public static void main(String[] args){
		Solve s = new Solve();
		s.solve();
	}	
}

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	void solve(){
		while(in.hasNext()){
			int n = in.nextInt();
			if(n == 0) return;
			int  ai = 10000000;
			double ab = -2000.0;
			for(int i = 0; i < n; i++){
				int j = in.nextInt(), h = in.nextInt(), w =in.nextInt();
				if(Math.abs(22.0 - ab) > Math.abs(22.0 - calcBMI(h, w))){
					ab = calcBMI(h, w);
					ai = j;
				}
				if(Math.abs(22.0 - ab) == Math.abs(22.0 - calcBMI(h, w))){
					if(ai > j) ai = j;
				}
			}
			System.out.println(ai);
		}
	}

	double calcBMI(int h, int w){
		return (double) w * 10000 / h / h;
	}

}

Measured memory_bytes: 37652
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
int main()
{
  long long int N;
  cin >> N;
  long long ans = 1e18;
  for (long long int i = 1; i * i <= N; i++)
  {
    if (N % i != 0)
    {
      continue;
    }
    long long int j = N / i;
    ans = min(ans, i + j - 2);
  }
  cout << ans << endl;
  return 0;
}

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

const int N = 60;
const int BIT = 18;
using ll = long long;

int a[N];
ll comb[N][N];
ll precomb[N][N];
std::map <int, int> map[1 << BIT];

int main(){
    for (int i = 0; i < N; ++ i){
        comb[i][0] = 1;
        for (int j = 1; j <= i; ++ j){
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
    int n, k, s, t;
    scanf("%d%d%d%d", &n, &k, &s, &t);
    for (int i = 0; i < n; ++ i){
        scanf("%d", &a[i]);
    }
    if ((s & t) != s){
        puts("0");
        return 0;
    }
    std::vector <int> valid;
    for (int i = 0; i < n; ++ i){
        bool flag = true;
        for (int j = 0; j < BIT; ++ j){
            if ((a[i] >> j & 1) && !(s >> j & 1) && !(t >> j & 1)){
                flag = false;
                break;
            }
            if (!(a[i] >> j & 1) && (s >> j & 1) && (t >> j & 1)){
                flag = false;
                break;
            }
        }
        if (flag){
            valid.emplace_back(a[i]);
        }
    }
    int bit = 0;
    for (int i = 0; i < BIT; ++ i){
        if (!(s >> i & 1) && (t >> i & 1)){
            ++ bit;
        }
    }
    n = 0;
    for (auto u : valid){
        a[n] = 0;
        for (int i = BIT - 1; i >= 0; -- i){
            if (!(s >> i & 1) && (t >> i & 1)){
                a[n] = (a[n] << 1) | (u >> i & 1);
            }
        }
        ++ n;
    }
    for (int i = 0; i < n; ++ i){
        map[(1 << bit) - 1][a[i]] = 1;
    }
    for (int i = (1 << bit) - 2; i >= 0; -- i){
        int lb = (~i) & -(~i);
        for (auto p : map[i ^ lb]){
            map[i][p.first & (~lb)] += p.second;
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; ++ i){
        for (int j = 1; j <= k; ++ j){
            precomb[i][j] = precomb[i][j - 1] + comb[i][j];
        }
    }
    for (int i = 0; i < 1 << bit; ++ i){
        for (auto p : map[i]){
            ans += (__builtin_popcount(i) & 1 ? -1 : 1) * precomb[p.second][k];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 559436
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

#define MAX_V 300010
struct edge{int to,cost;};
typedef pair<int,int> pii;
int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii>> que;
    fill(d,d+V,INF);
    d[s] = 0;
    que.push(pii(0,s));
    while(!que.empty()){
        pii p = que.top();que.pop();
        int v = p.se;
        if(d[v] < p.fi) continue;
        rep(i,G[v].size()){
            edge e = G[v][i];
            if(d[e.to] > d[v]+e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(pii(d[e.to],e.to));
            }
        }
    }
}

signed main(){
    int n,m;
    cin >> n >> m;
    //こんな感じに入力
    V = 3*n;
    rep(i,m){//m は edge数
        int u,v;
        cin >> u >> v;
      	u--;
      	v--;
      	edge e2 = {v,1};
      	edge e4 = {n+v,1};
      	edge e6 = {2*n+v,1};
        G[u].pb(e4);
        G[n+u].pb(e6);
        G[2*n+u].pb(e2);
    }
    int s,t;
    cin >> s >> t;

    dijkstra(s-1);

    if(d[t-1] == INF)cout << -1 << endl;
    else cout << d[t-1]/3 << endl;

    // rep(i,n){
    //   if(d[i] == INF)cerr << -1 << " ";
    //   else cerr << d[i] << " ";
    // }cerr << endl;
    // for(int i = n;i < 2*n;i++){
    //   if(d[i] == INF)cerr << -1 << " ";
    //   else cerr << d[i] << " ";
    // }cerr << endl;
    // for(int i = 2*n;i < 3*n;i++){
    //   if(d[i] == INF)cerr << -1 << " ";
    //   else cerr << d[i] << " ";
    // }

    

    


    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc132.contest.atcoder.jp/tasks/abc132_e


Measured memory_bytes: 18944
#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

int color[maxn], p[maxn], vis[maxn];
int head[maxn], cnt;
vector<int> r, b;

int n;

struct node {
    int v, next;
} e[maxn << 1];

void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v) {
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void dfs(int u, int c) {
    color[u] = c;
    if (c == 1) r.push_back(u);
    else b.push_back(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].v;
        if (!color[v]) dfs(v, -c);
    }
}

void solve() {
    int pos = 1;
    for (int i = 1; i <= n; i++) {
        if (!p[i]) {
            while (vis[pos]) {
                pos++;
            }
            p[i] = pos;
            vis[pos] = 1;
        }
    }
}

int main(void) {
    FAST_IO;
    init();
    
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    if (r.size() > b.size()) {
        swap(r, b);
    }
    if (r.size() <= n / 3) {
        int k = 0;
        for (auto &x : r) {
            k++;
            if (k * 3 > n) break;
            p[x] = k * 3;
            vis[k * 3] = 1;
        }
        solve();
    } else {
        int k = -1;
        for (auto &x : r) {
            k++;
            if (k * 3 + 1 > n) break;
            p[x] = k * 3 + 1;
            vis[k * 3 + 1] = 1;
        }
        k = -1;
        for (auto &x : b) {
            k++;
            if (k * 3 + 2 > n) break;
            p[x] = k * 3 + 2;
            vis[k * 3 + 2] = 1;
        }
        solve();
    }
    for (int i = 1; i <= n; i++) {
        cout << p[i] << " ";
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 10484
N = int(input())

a_array = []
b_array = []

for i in range(N):
    a, b = map(int, input().split())
    a_array.append(a)
    b_array.append(b)

a_array.sort()
b_array.sort()

if N % 2 != 0:
    mid_min = a_array[(N - 1) // 2]
    mid_max = b_array[(N - 1) // 2]
    print(mid_max - mid_min + 1)

else:
    mid_min = (a_array[N // 2 - 1] + a_array[N // 2]) / 2
    mid_max = (b_array[N // 2 - 1] + b_array[N // 2]) / 2
    print(int((mid_max - mid_min) * 2) + 1)


Measured memory_bytes: 98872
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <sstream>
using namespace std;
const int maxn = 1e5+10;
int pre[2*maxn];
int vis[2*maxn];
int find(int x){
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
void join(int a,int b){
    pre[find(b)]=find(a);
}
int main(){
    int i,j,a,b;
    long long n,m;
    while(~scanf("%lld%lld",&n,&m)){
        for(i=1;i<=2*n;i++){
            pre[i] = i;
        }
        bool flag = true;
        for(i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            if(find(a) == find(b)){
                flag = false;
            }else{
                join(a, b+n);
                join(b, a+n);
            }
        }
        memset(vis, 0, sizeof(vis));
        if(flag){
            for(i=1;i<=2*n;i++){
                find(i);
                //cout<<i<<" "<<pre[i]<<endl;
                ++vis[pre[i]];
            }
            long long now;
            /*for(i=1;i<=2*n;i++){
                if(vis[i]>0){
                    now = vis[i];
                    break;
                }
            }*/
            
            //now /= 2;
            long long b = 1, w = 0;
            for(i=2;i<=n;i++){
                if(find(i)==find(1)){
                    ++b;
                }else{
                    ++w;
                }
            }
            //printf("%lld\n", now * (n-now) - m);
            printf("%lld\n",b*w-m);
        }else{
            printf("%lld\n",n*(n-1)/2 - m);
        }
    }
    
    return 0;
}


Measured memory_bytes: 1792
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    int[][] f;
    int count;
    int i, j, k, l, score, h, tmp;

    for(;;){
      h = sc.nextInt();
      if(h == 0)break;
      f = new int[h][5];
      for(i = 0;i < h;i++)for(j = 0;j < 5;j++)f[i][j] = sc.nextInt();
      score = 0;

      for(k = 0;k < h;k++){
        for(i = 0;i < h;i++){
          count = 0;
          for(j = 0;j < 5;j++)if(f[i][j] == f[i][2] && f[i][2] != 0)count++;
          if(count == 5){
            score += 5 * f[i][2];
            for(j = 0;j < 5;j++)f[i][j] = 0;
          }else if(count >= 3){
            if(f[i][2] != f[i][0] && f[i][2] == f[i][1] && count == 4){
              score += 4 * f[i][2];
              for(j = 1;j < 5;j++)f[i][j] = 0;
            }else if(f[i][2] != f[i][4] && f[i][2] == f[i][1] && count == 4){
              score += 4 * f[i][2];
              for(j = 0;j < 4;j++)f[i][j] = 0;
            }else if(f[i][2] == f[i][3] && f[i][2] == f[i][4]){
              score += 3 * f[i][2];
              for(j = 2;j < 5;j++)f[i][j] = 0;
            }else if(f[i][2] == f[i][1] && f[i][2] == f[i][3]){
              score += 3 * f[i][2];
              for(j = 1;j < 4;j++)f[i][j] = 0;
            }else if(f[i][2] == f[i][0] && f[i][2] == f[i][1]){
              score += 3 * f[i][2];
              for(j = 0;j < 3;j++)f[i][j] = 0;
            }
          }
        }

        for(j = 0;j < 5;j++){
          for(i = 1;i < h;i++){
            if(f[i][j] == 0){
              tmp = f[i][j];
              for(l = i;l > 0;l--)f[l][j] = f[l - 1][j];
              f[l][j] = 0;
            }
          }
        }
      }

      out.println(score);
    }


    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 49720
n = int(input())
b = list(map(int, input().split()))

al = [0]*n
al[0] = b[0]
for i in range(1, n - 1):
    al[i] = min(b[i - 1], b[i])
al[n - 1] = b[n - 2]

ans = 0
for i in range(n):
    ans = ans + al[i]

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string A;
  cin >> A;
  if(A.at(0) != A.at(1) && A.at(1) != A.at(2) 
     && A.at(2) != A.at(0))
    cout << "Yes" << endl; 
  else
    cout << "No" << endl; 
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cfenv>
#include <cmath>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main(void){
	cin.tie(0);
   	ios::sync_with_stdio(false);

	int n,x,swapped=-1;
	cin >> n;
	int p[n];
	for(int i = 0; i < n; i++){
		cin >> p[i];
		if(i!=0 && p[i-1]>p[i] && swapped==0){
		    swapped=1;
		    swap(p[x],p[i]);
		}
		if(i!=0 && p[i-1]>p[i] && swapped<0){
		    x=i-1;
		    swapped=0;
		}

        
	}	
	for(int i = 0; i < n; i++){
        if(i!=0 && p[i-1]>p[i]){
		    cout << "NO"<<"\n";
		    return 0;
		}
	}	

	cout << "YES"<<"\n";


}


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

int main() {
  int x = 0;
  rep(i, 5) {
    cin >> x;
    if (x == 0) {
      cout << i + 1 << endl;
      break;
    }
  }
}


Measured memory_bytes: 3632
// C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 

// Function to find the number of divisors 
// of all numbers in the range [1, n] 
void findDivisors(long long  n) 
{ 

	// Array to store the count 
	// of divisors 
	long long  div[n + 1]; 
	memset(div, 0, sizeof div); 

	// For every number from 1 to n 
	for (int i = 1; i <= n; i++) { 

		// Increase divisors count for 
		// every number divisible by i 
		for (int j = 1; j * i <= n; j++) 
			div[i * j]++; 
	} 
    long long int ans=0;
	// Print the divisors 
	for (int i = 1; i <= n; i++) 
		ans=ans+ i*div[i];
   cout<<ans<<endl;     
} 

// Driver code 
int main() 
{ 
	long long n ;
    cin>>n;

	findDivisors(n); 

	return 0; 
} 


Measured memory_bytes: 81708
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>

using namespace std;

const double eps=1e-10;

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

	for(int i=0;i<n;i++){
		double xa,ya,ra,xb,yb,rb;
		cin>>xa>>ya>>ra>>xb>>yb>>rb;
		double d=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
		double r=(ra+rb);

		if(d>r) cout<<0<<endl;
		else if(d+rb<ra) cout<<2<<endl;
		else if(d+ra<rb) cout<<-2<<endl;
		else cout<<1<<endl;
	}


	return 0;
}

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

int main(void){
   
   int a,b,c,d=0,e=0;
   cin >> a >> b >> c;
   
   if(a == 5){
       d++;
   }
   else if(a == 7){
       e++;
   }
   
   if(b == 5){
       d++;
   }
   else if(b == 7){
       e++;
   }
   
   if(c == 5){
       d++;
   }
   else if(c == 7){
       e++;
   }
   
   
   if(d == 2 && e == 1){
        cout << "YES" <<endl;   
   }
   else{
       cout << "NO" <<endl;
   }
}

Measured memory_bytes: 3548
package main

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

var ReadString func() string

func init() {
	ReadString = newReadString()
}

/*------ scan ------*/

func newReadString() func() string {
	var sc = bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, 1024), 2048)
	sc.Split(bufio.ScanWords)
	return func() string {
		if !sc.Scan() {
			panic("scanできなかった")
		}
		return sc.Text()
	}
}

func ReadInt64() int64 {
	i, err := strconv.ParseInt(ReadString(), 0, 64)
	if err != nil {
		fmt.Println("scanできなかった")
		panic(err.Error())
	}
	return int64(i)
}

func ReadInt() int {
	i := ReadInt64()
	return int(i)
}

func ReadIntSlice(n int) []int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = ReadInt()
	}
	return arr
}

func ReadInt64Slice(n int) []int64 {
	arr := make([]int64, n)
	for i := 0; i < n; i++ {
		arr[i] = ReadInt64()
	}
	return arr
}

/*------ number util ------*/

func GetIntAbs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func Atoi(a string) int {
	i, err := strconv.Atoi(a)
	if err != nil {
		panic(err.Error())
	}
	return i
}


func main() {
	x := ReadInt()
	a := ReadInt()
	if x < a {
		fmt.Println(0)
	} else {
		fmt.Println(10)
	}
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
const int MOD=1000000007;

int main() {
	int n;
	cin >> n;
	vector<int> r(n);
	rep(i, n) {
		cin>>r[i];
	}
	vector<int>s = r;
	int maxv = -MOD;
  int minv=r[0];
	rep2(i,1,n) {
		maxv=max(maxv,r[i]-minv);
      minv=min(minv,r[i]);
	}
	cout << maxv<<endl;
	}

	


Measured memory_bytes: 4436
#include <iostream>
#include <set>
#include <vector>

int main() {
  std::set<int> groupA{1, 3, 5, 7, 8, 10, 12};
  std::set<int> groupB{4, 6, 9, 11};
  std::set<int> groupC{2};

  std::vector<std::set<int>> tmp{groupA, groupB, groupC};

  int x;
  int y;

  std::cin >> x >> y;

  for (const auto &group : tmp) {
    std::size_t countX = group.count(x);
    std::size_t countY = group.count(y);
    if (countX == 1 && countY == 1) {
      std::cout << "Yes" << std::endl;
      return 0;
      ;
    }
  }
  std::cout << "No" << std::endl;
  return 0;
}

Measured memory_bytes: 256
//Name: Speed Skating Badge Test
//Level: 1
//Category: やるだけ
//Note: 

/**
 * 問題文の通りに処理する。
 *
 * オーダーは O(R)。
 * ただしRはランクの数。
 */
#include <iostream>

using namespace std;

bool solve() {
    double A, B;
    if(!(cin >> A >> B)) return false;

    string judge = "NA";
    if(A < 35.5 && B < 71.0) judge = "AAA";
    else if(A < 37.5 && B < 77.0) judge = "AA";
    else if(A < 40.0 && B < 83.0) judge = "A";
    else if(A < 43.0 && B < 89.0) judge = "B";
    else if(A < 50.0 && B < 105.0) judge = "C";
    else if(A < 55.0 && B < 116.0) judge = "D";
    else if(A < 70.0 && B < 148.0) judge = "E";
    cout << judge << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);

    while(solve()) ;
    return 0;
}

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


void solve(long long N, std::vector<std::string> s, long long M, std::vector<std::string> t, std::vector<std::string> st){
    sort(st.begin(), st.end());
    st.erase(unique(st.begin(), st.end()), st.end());
    int snum, tnum;
    int ans = 0;
    for(auto stg : st){
        snum = count(s.begin(), s.end(), stg);
        tnum = count(t.begin(), t.end(), stg);
        ans = max(ans, snum - tnum);
    }
    cout << ans << endl;
}

int main(){
    long long N, M;
    scanf("%lld",&N);
    std::vector<std::string> s(N);
    std::vector<std::string> st;
    for(int i = 0 ; i < N ; i++){
        std::cin >> s[i];
        st.push_back(s[i]);
    }
    scanf("%lld",&M);
    std::vector<std::string> t(M);
    for(int i = 0 ; i < M ; i++){
        std::cin >> t[i];
        st.push_back(t[i]);
    }
    solve(N, std::move(s), M, std::move(t), std::move(st));
    return 0;
}


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

using namespace std;

typedef long long ll;

const ll mod=1e9+7;
const ll maxn=2e5+5;


ll inv[maxn];
void getInv(){
	inv[1]=1;
	for(ll i=2;i<maxn;i++){
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
}

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

ll C(ll x,ll y){
	ll ans=1;
	for(int i=0;i<y;i++)
	{
		ans=(ans*(x-i)%mod*inv[i+1])%mod;
	}
	return ans;
}

int main(){
	getInv();
	ll n,a,b;
	scanf("%lld%lld%lld",&n,&a,&b);	
	ll ans=(qPow(2,n)+mod-1)%mod;
	ans=(ans+mod-C(n,a))%mod;
	ans=(ans+mod-C(n,b))%mod;
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1792
// ref: https://competitive-kivantium.hateblo.jp/entry/2019/04/27/001317
// ref: https://img.atcoder.jp/abc122/editorial.pdf

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;
using namespace std;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

bool ok(const string& s){
    if(             s[1]=='A' && s[2]=='G' && s[3]=='C'){ return false; } // ?AGC
    if(s[0]=='A' &&              s[2]=='G' && s[3]=='C'){ return false; } // A?GC
    if(s[0]=='A' && s[1]=='G' &&              s[3]=='C'){ return false; } // AG?C
    if(s[0]=='A' && s[1]=='G' && s[2]=='C'             ){ return false; } // AGC?
    
    if(             s[1]=='G' && s[2]=='A' && s[3]=='C'){ return false; } // ?GAC
    if(s[0]=='G' && s[1]=='A' && s[2]=='C'             ){ return false; } // GAC?
    
    if(             s[1]=='A' && s[2]=='C' && s[3]=='G'){ return false; } // ?ACG
    if(s[0]=='A' && s[1]=='C' && s[2]=='G'             ){ return false; } // ACG?
    return true;
}

int64 dfs(const int N, vector<unordered_map<string,int>>& memo, const int cur, const string last3){ // depth-first search
    if(memo[cur][last3]!=0){ return memo[cur][last3]; }
    if(cur==N){ return 1; }
    
    int ret=0;
    const int MOD = 1e9+7;
    const char base[] = {'A', 'C', 'G', 'T'};
    for(uint i=0; i<4; ++i){
        if(!ok(last3+base[i])){ continue; }
        string s = last3.substr(1) + base[i];
        ret += dfs(N, memo, cur+1, s);
        ret %= MOD;
    }
    memo[cur][last3] = ret;
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N; cin >> N;
    vector<unordered_map<string,int>> memo(N+1);
    
    cout << dfs(N, memo, 0, "TTT") << endl;
    
    return 0;
}

Measured memory_bytes: 896
#include<stdio.h>
#define N 101

int main(){

  int i, j, a, n, u, k, v[N][N] = {};

  scanf("%d", &n);
  for(i = 1 ; i <= n ; i++){
    scanf("%d%d", &u, &k);
    for(j = 1 ; j <= k ; j++){
      scanf("%d", &a);
      v[u][a] = 1;
    }
  }

  for(i = 1 ; i <= n ; i++){
    for(j = 1 ; j <= n ; j++){
      printf("%d",v[i][j]);
      if(j != n){
	printf(" ");
      }
    }
    printf("\n");
  }

  return 0;
}

Measured memory_bytes: 652
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const long double PI = (acos(-1));
#define rep(i, x, n) for (int i = x; i < (int)(n); i++)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
static const int mod = 1e9+7;
int main(){
    int n, tmp; sc(n);
    ll ans = 0;
    vector<ll> a(n);
    vector<int> zero(61,0), one(61,0);
    rep(i, 0, n) scll(a[i]);
    rep(i, 0, n){
        rep(j, 0, 61){
            if (a[i] & (1ll<<j)) one[j] += 1;
            else zero[j] += 1;
        }
    }
    rep(i, 0, zero.size()){
        ans = (ans + (1ll<<i)%mod*zero[i]%mod*one[i]%mod)%mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<stdio.h>

int main(void)

{  

int a,b,d,r;  

double f;

 scanf("%d %d",&a,&b);

 d=a/b;

 r=a%b;

 f=(double)a/b;  

 printf("%d %d %lf\n",d,r,f);  

 return 0;

}

Measured memory_bytes: 636
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  cout << (n + 1) / 2 << '\n';
  return (0);
}


Measured memory_bytes: 256
l,r = (int(i) for i in input().split())
mod = 2019
if r-l >=2019:
    print(0)
else:
    ans = float('inf')
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            ans = min(ans,i*j%mod)
    print(ans)


Measured memory_bytes: 40812
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
         
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
 
        int temp;
         
        if (a > b){
            temp = b;
            b = a;
            a = temp;
        }
         
        if (b > c){
            temp = c;
            c = b;
            b = temp;
        }
         
        if (a > b){
            temp = b;
            b = a;
            a = temp;
        }
         
         
        System.out.println(a + " " + b + " "  + c);
 
    }
}

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

const int MAX_N = 100005;
int N, Q;
lint A[MAX_N], X[MAX_N], S[MAX_N], odd[MAX_N], even[MAX_N];

bool check(int q, int i){
    int j = distance(A, lower_bound(A, A+N, 2*X[q]-A[i]));
    int cnt = i - j;
    if(A[i]+A[j]>=2*X[q]) cnt++;
    if(cnt>N-i-1) return false;
    return true;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=0;i<N;i++) cin >> A[i];
    for(int i=0;i<Q;i++) cin >> X[i];

    for(int i=1;i<=N;i++){
        S[i] += S[i-1] + A[i-1];
        odd[i] = odd[i-1], even[i] = even[i-1];
        if(i%2) even[i] += A[i-1];
        else odd[i] += A[i-1];
    }

    for(int i=0;i<Q;i++){
        int left = -1, right = N + 1;
        while(1<right-left){
            int mid = (left+right) / 2;
            if(check(i, mid)) left = mid;
            else right = mid;
        }

        int lb = max(2*left - N + 2, 0);
        lint ans = S[N] - S[left+1];
        if(lb%2) ans += even[lb];
        else ans += odd[lb];
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 5632
#include <bits/stdc++.h>
using namespace std;
long long n,a[1003],x;
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>a[i];
    sort (a,a+n);
    cout<<a[n-1]-a[0];
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
  int A, B;
  cin >> A >> B;
  if(A==B)
    cout << "Draw";
  else if(A==1 || (B!=1 && A>B))
    cout << "Alice";
  else
    cout << "Bob";
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;

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

int main(){
    int n, t; cin>>n>>t;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin>>v[i];

    ll ans=t;
    for(int i=0; i<n-1; i++){
        if(v[i+1]-v[i]<=t) ans+=v[i+1]-v[i];
        else ans+=t; 
    }
    cout << ans << endl;
}

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

int main() 
{
    int L,R,d;
    cin>>L>>R>>d;

    const int kmax=R-L;
    int cnt=0;

    for (int i = L; i < R+1; i++)
    {
        if(i%d==0)
        {
            ++cnt;
        }
    }
    
    cout<<cnt<<endl;
    return 0;   
}


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

using namespace std;

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

    char s[300010];
    char c;
    int q, t, f;

    cin >> s >> q;

    deque <char> dq;

    for (int i = 0; i < strlen(s); i++)
        dq.push_back(s[i]);

    bool front = false;

    while (q--)
    {
        cin >> t;

        if (t == 1)
        {
            front = !front;
            continue;
        }

        cin >> f >> c;

        if (f == 1)
        {
            if (!front)
            {
                dq.push_front(c);
            }
            else
            {
                dq.push_back(c);
            }
        }
        else
        {
            if (!front)
            {
                dq.push_back(c);
            }
            else
            {
                dq.push_front(c);
            }
        }
    }

    int i = 0;

    while (!dq.empty())
    {
        if (front)
        {
            c = dq.back();
            dq.pop_back();
        }
        else
        {
            c = dq.front();
            dq.pop_front();
        }

        cout << c;
    }

    cout << "\n";

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;
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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


int main() {
	init();

	int N; cin >> N;
	vector<int>A(N);
	rep(i, 0, N)cin >> A[i];
	int ans = 0;
	rep(i, 0, N) {
		++i;
		bool inc = false, dec = false;
		while (i < N) {
			if (A[i-1] < A[i]) {
				if (dec) {
					--i;
					break;
				}
				else if (!inc)inc = true;
			}
			else if (A[i-1] > A[i]) {
				if (inc) {
					--i;
					break;
				}
				else if (!dec)dec = true;
			}
			++i;
		}
		++ans;
	}
	cout << ans << "\n";

	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<ll>a(3*n);
  ll ans = 0;
  for(int i = 0;i < 3*n;i++) cin >> a[i];
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for(int i = 1;i < 2*n;i += 2){
    ans += a[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
#include <stdio.h>
int main(){
  
  int x, y, tmp;

  while(1){
    scanf("%d%d", &x, &y);

    if(x == 0 && y == 0){
      break;
    } else if (x > y){
      tmp = x; x = y; y = tmp;
    }

     printf("%d %d\n", x, y);
    }
  return 0;
}



Measured memory_bytes: 1856
#include<stdio.h>
#include<string.h>
int main(void){
  int num;
  scanf("%d",&num);
  
  char str[100];
  scanf("%s",str);
  
  int i;
  if(strlen(str)<num){
   for(i=0;i<strlen(str);i++){
    printf("%c",str[i]); 
   }
  }else{
   for(i=0;i<num;i++){
    printf("%c",str[i]); 
   }
  }
  
  if(strlen(str)>num){
    printf("...");
  }
 return 0; 
}

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

using namespace std;
using ll = long long;

int main() {
	const ll MOD = 1e9 + 7;
	int N;
	cin >> N;
	vector<ll> T(N + 2, 0);
	vector<ll> A(N + 2, 0);
	for (int i = 1; i <= N; ++i) { cin >> T[i]; }
	for (int i = 1; i <= N; ++i) { cin >> A[i]; }

	vector<ll> d(N + 2, 0);
	for (int i = 1; i <= N; ++i) {
		if (T[i] == T[i - 1]) {
			d[i] = T[i];
		} else {
			d[i] = -T[i];
		}
	}
	bool exist = true;
	for (int i = N; i >= 1; --i) {
		if (A[i] == A[i + 1]) {
			if (d[i] < 0) {
				if (abs(d[i]) > A[i]) { exist = false; }
			} else {
				d[i] = min(d[i], A[i]);
			}
		} else {
			if (d[i] < 0) {
				if (abs(d[i]) != A[i]) { exist = false; }
			} else {
				if (d[i] < A[i]) { exist = false; }
				else { d[i] = -A[i]; }
			}
		}
	}

	if (!exist) {
		cout << 0 << endl;
	} else {
		ll res = 1;
		for (int i = 1; i <= N; ++i) {
			if (d[i] > 0) {
				res = (res * d[i]) % MOD;
			}
		}
		cout << res % MOD << endl;
	}

	return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

int main() {
  ll A, B, V, W, T;
  cin >> A >> V >> B >> W >> T;
  ll d = abs(A - B);
  cout << ((V - W) * T >= d ? "YES" : "NO");
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::string a;
	long long r = 0, g = 0, b = 0;
	std::cin >> n;
	std::cin >> a;
	for (auto p : a) {
		if (p == 'R') r++;
		else if (p == 'G') g++;
		else b++;
	}
	long long ans = (long long)r * g * b;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] == a[j]) continue;
 
			int k = 2 * j - i;
 
			if (k < n && a[i] != a[k] && a[j] != a[k]) ans--;
		}
	}
	std::cout << ans <<  "\n";
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	vector<int> vec(n);

	for (auto& e : vec) {
		cin >> e;
	}

	int min = 200001;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (min >= vec.at(i)) {
			min = vec.at(i);
				ans++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
n = int(input())
b = list(map(int, input().split()))
for i in range(n):
  if b[i] > i+1:
    print(-1)
    break
else:
  ans = []
  while len(b) > 1:
#    print(ans,b)
    c = len(ans)
    f = b[0]
    for i in range(1, len(b))[::-1]:
      if b[i] == i + 1:
#        print("check", b[i:])
        ans.append(b.pop(i))
        break
    else:
      for i in range(1, len(b)):
#      print(f, i, b, n - c, ans)
        if f >= b[i]:
          ans.append(b.pop(i-1))
          break
        elif n - c == b[i]:
          ans.append(b.pop(i))
          break
        elif i == len(b) - 1:
          ans.append(b.pop(-1))
          break
        else:
          f = b[i]
  ans.append(1)
  for i in range(n)[::-1]:
    print(ans[i])

Measured memory_bytes: 38640
N = int(input())
gcdlst = []
for i in range(1, int(N ** 0.5) + 1):
    if N % i == 0:
        gcdlst.append(i)
        if i != N // i:
            gcdlst.append(N // i)
gcdlst.sort()
tmplen = len(gcdlst)
if tmplen % 2 == 0:
    tmplen = tmplen // 2
    ans = gcdlst[tmplen] + gcdlst[tmplen - 1] - 2
else:
    tmplen = tmplen // 2
    ans = (2 * gcdlst[tmplen]) - 2
print(ans)

Measured memory_bytes: 3264
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
Arr.shift();
 
var bfr=[];
for(var i=0;i<4;i++){
bfr.push([]);
for(var j=0;j<3;j++){
bfr[i].push([]);
for(var k=0;k<10;k++){
bfr[i][j].push(0);
}
}
}
 
for(var i=0;i<Arr.length;i++){
var arr=Arr[i].split(" ").map(Number);
var b=arr[0]-1;
var f=arr[1]-1;
var r=arr[2]-1;
var v=arr[3]-0;
 
bfr[b][f][r]=bfr[b][f][r]+v;
if(bfr[b][f][r]>9)bfr[b][f][r]=9;
if(bfr[b][f][r]<0)bfr[b][f][r]=0;
 
}
 
for(var i=0;i<4;i++){
for(var j=0;j<3;j++){
console.log(" "+bfr[i][j].join(" "));
}
if(i!==3)console.log("####################");
}

Measured memory_bytes: 8680
N, K = map(int, input().split())
A = list( map(int, input().split()) ) #ここでN個受け取る

var = [0] * (N+1)


for i in A:
    var[i] += 1
    
var = sorted(var,  reverse = True )


count = 0
for j in range( K, N+1 ):
    if var[j] == 0:
        break
    
    if var[j] != 0:
        count += var[j]
        
print(count)

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

using namespace std;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    for (auto c : s) {
        if (c == '7') {
            cout << "Yes" << '\n';
            exit(0);
        }
    }
    cout << "No";
    return 0;
}


Measured memory_bytes: 3652