akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
#include<fstream>

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
using namespace std;

const LL MOD = 1000000007;// 10^9+7
const int INF = (1 << 30);


//変数
int Q;
vector<pair<LL, LL>> ab;






//サブ関数
//入力
void input()
{
}


//計算
void calc(pair<LL,LL> now)
{
	LL A = now.first;
	LL B = now.second;
	LL score = A * B - 1;
	LL ans;
	LL base = score;

	base = sqrtl(base) - 10;
	if (base < 0)base = 0;
	while (base*(base + 1) <= score)base++;
	ans = (base - 1) * 2;
	//cerr << "first:" << ans << endl;
	/*
	while (true) {
		LL l = floor(1.*score / base);
		LL r = floor(1.*score / (base + 1));
		if (l > r)break;
		if (l == r) {
			ans++;
			break;
		}
		ans += 2;
		base++;
	}
	*/
	//cerr << "now" << ans << endl;
	//解がほぼ同じなら、そもそもない？
	
	LL l = min(A, B);
	LL r = max(A, B);
	LL see = floor(1.*score / l);

	//cerr << "score" << score << endl;
	//cerr << "l    " << l << endl;
	//cerr << "see" << see << endl;
	ans--;
	if (base*base <= score)ans++;
	if (A == B)ans++;
	//cerr << "second:";
	cout << ans << endl;
}


//出力
void output()
{

}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	cin >> Q;
	REP(i, Q) {
		LL l, r;
		cin >> l >> r;
		ab.push_back(make_pair(l, r));
	}
	for (auto now : ab) {
		calc(now);
	}
	debug();
	
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
	ll a,b,c;
	cin >> a >> b >> c;
	ll cnt = 0;
	map<P, int> mp;
	while(true){
		if(a % 2 == 1 || b % 2 == 1 || c % 2 == 1) break;
		int pre_a = a,pre_b = b,pre_c = c;
		a = (pre_b + pre_c) / 2;
		b = (pre_c + pre_a) / 2;
		c = (pre_a + pre_b) / 2;
		if(mp[P(a, b)] > 0){
			cnt = -1;
			break;
		}
		mp[P(a, b)]++;
		cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
from collections import deque
n, q = map(int, input().split())
l=[0]*n
links = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  links[a-1].append(b-1)
  links[b-1].append(a-1)
for _ in range(q):
  p, x = map(int, input().split())
  l[p-1] += x
d = deque()
d.append((0, -1))
while len(d) != 0:
  i, p = d.popleft()
  for j in links[i]:
    if j==p:
      continue
    l[j] += l[i]
    d.append((j, i))
print(*l)


Measured memory_bytes: 62232
/* B */

#include <iostream>
using namespace std;

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

	int counter = 0;

	int* b = new int[m];

	for(int k = 0; k < m; k++){
		cin >> b[k];
	}

	int a;

	for(int i = 0; i < n; i++){
		int sum = 0;
		for(int j = 0; j < m; j++){
			cin >> a;
			sum += a * b[j];
		}

		if(sum + c > 0){
			counter++;
		}

	}

	cout << counter << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define int long long
const int INF = 1e18, MOD = 1e9 + 7;
signed main() {
    int n, a;
    cin>>n;
    map<int, int> cnt1, cnt2;
    for (int i = 1; i <= n; i++) {
        cin>>a;
        cnt1[i + a]++;
        cnt2[i - a]++;
    }
    int ans = 0;
    for (pair<int, int> p: cnt1) {
        ans += p.second * cnt2[p.first];
    }
    cout<<ans<<endl;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

int main() {
    const int MAX_V = 1000000;
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    vector<int> cnt(MAX_V + 10, 0);
    sort(A.begin(), A.end());
    rep(i, A.size()) {
        if (i > 0 && A[i - 1] == A[i]) {
            cnt[A[i]]++;
            continue;
        }

        for (int b = A[i]; b <= MAX_V; b += A[i]) cnt[b]++;
    }

    int ans = 0;
    for(auto a: A) if (cnt[a] == 1) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 7948
//bismillahir rahmanir rahim            //Author:Fayed Anik
 
#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         ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define         ll                          long  long
#define         lf                          double
#define         pb(x)                       push_back(x)
#define         ull                         unsigned long long
#define         sfl(a)                      scanf("%lld",&a)
#define         sf(a)                       scanf("%d",&a)
#define         pf(a)                       printf("%d\n",a)
#define         pfl(a)                      printf("%lld\n",a)
#define         FOR(x,n)                    for(ll x=1;x<=n;++x)
#define         pii                         pair< ll , ll >
#define         mp(a,b)                     make_pair(a,b)
#define         UNIQUE(v)                   v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define         mod                         1000000007
#define         INF                         2e18
#define         EPS                         1e-15
#define         f1                          first
#define         f2                          second
#define         all(v)                      v.begin(),v.end()
#define         PI                          acos(-1)
#define         printminusone               printf("-1\n")
#define         bug                         printf("bug")
#define         FILEIN                      freopen("in.txt","r",stdin)
#define         FILEOUT                     freopen("out.txt","w",stdout)
 
//ll SET(ll mask,ll pos){ return mask = (mask | (1ll<<pos)); }
//ll RESET(ll mask,ll pos){ return mask = mask & ~(1ll<<pos); }
//bool CHECK(ll mask,ll pos) { return (bool) (mask & (1ll<<pos)); }
//priority_queue <ll, vector<ll>, greater<ll> > pq;
//int dx[]={0,0,1,-1,1,1,-1,-1};
//int dy[]={1,-1,0,0,1,-1,1,-1};


int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);  
    ll k,m;
    sfl(k);
    if(k%7==0) k /= 7;
    m = 9*k;
    if(__gcd(m,(ll)10)!=1){
        printminusone;
        return 0;
    }
    if(k==1){
        printf("1\n");
        return 0;
    }
    ll cnt=1,n=10;
    while(n!=1){
        n = (n * 10)%m;
        cnt++;
    }
    pfl(cnt);
    return 0;
}

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

int main()
{
	int n;
	cin >> n;
	vector<int> ans(n);
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		ans.at(a - 1) = i;
	}

	for (int i = 0; i < n; i++) {
		cout << ans.at(i) << " ";
	}
}


Measured memory_bytes: 1152
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

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

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
ll N,K;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>N>>K;
  ll ans = 1;
  while(N--){
    if(ans < K) ans*=2;
    else ans+=K;
  }

  cout<<ans<<endl;

}

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define lamsort(v,p) sort(v.begin(),v.end(),[](p a, p b){return a.num < b.num;});
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> v(n);
    rep(i,n) cin >> v[i];
    ll x = 0;
    rep(i,n) {
        if(i%2) x -= v[i];
        else x+= v[i];
    }
    vector<int> ans(n);
    ans[0] = x/2;
    rep(i,n-1) {
        ans[i+1] = v[i] - ans[i];
    }
    rep(i,n) ans[i] *= 2;
    rep(i,n) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <math.h>

using namespace std;

#define x first
#define y second
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define SZ(x) int(x.size())
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b-1; i >= a; i--)
#define DBG(x) cerr << (#x) << "=" << x << "\n";
#define ll long long
#define inf 1000000007
#define mod 998244353//1000000007
#define N 200005

template<typename U, typename V> void Min(U &a, const V & b){if(a > b)a = b;}
template<typename U, typename V> void Max(U &a, const V & b){if(a < b)a = b;}
template<typename U, typename V> void add(U &a, const V & b){a = (a + b) % mod;}
template<typename U> U gcd(U a, U b){
    if(a == 0)return b;
    if(b == 0)return a;
    if(a >= b)return gcd(a % b, b);
    else return gcd(a, b % a);
}
int pow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return ans;
}

char s[105];
const ll INF = 1e15;
const int M = 26;
int dp[2][M][M];
ll a[M][M], b[M][M], c[M][M];
void mul(ll a[M][M], ll b[M][M]){
    rep(i, 0, M)rep(j, 0, M)c[i][j] = INF;
    rep(i, 0, M)rep(j, 0, M)rep(k, 0, M)Min(c[i][j], a[i][k] + b[k][j]);
    rep(i, 0, M)rep(j, 0, M)a[i][j] = c[i][j];
}
int main(){
    int T, n, m, i, j, k, ca = 0, K;
    scanf("%s%d", s, &m);
    n = strlen(s);
    memset(dp, 63, sizeof(dp));
    rep(i, 0, 26)dp[0][i][i] = (s[0] - 'a') == i ? 0 : 1;
    int now = 0;
    rep(i, 1, n){
        memset(dp[1-now], 63, sizeof(dp[0]));
        rep(j, 0, 26){
            rep(k, 0, 26)if(dp[now][j][k] < inf){
                rep(l, 0, 26)if(l != k){
                    K = dp[now][j][k] + (l != (s[i] - 'a'));
                    Min(dp[1-now][j][l], K);
                }
            }
        }
        now = 1 - now;
    }
    rep(i, 0, 26){
        rep(j, 0, 26){
            a[i][j] = INF;
            rep(k, 0, 26)if(k != i){
                Min(a[i][j], dp[now][k][j]);
            }
        }

    }
    while(m){
        if(m & 1)mul(b, a);
        mul(a, a); m >>= 1;
    }
    ll ans = INF;
    rep(i, 0, 26)rep(j, 0, 26)Min(ans, b[i][j]);
    printf("%lld\n", ans);
}


Measured memory_bytes: 256
n,m=map(int,input().split())
l=list()
for i in range(m):
    l.append(list(map(int,input().split())))
p=0
for o in range(m):
    d={i:[] for i in range(1,n+1)}
    for i in range(m):
        if i==o:
            continue
        a,b=l[i]
        d[a].append(b)
        d[b].append(a)
    q=[1]
    s={i:1 for i in range(1,n+1)}
    while len(q)>0:
        for i in d[q.pop()]:
            if s[i]:
                s[i]=0
                q.append(i)
    #print(s)
    if 1 in s.values():
        p+=1
print(p)

Measured memory_bytes: 9168
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
#define MAX 1000000000000000
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ll>
ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a)%mod;  a = (a * a)%mod;  b/=2;  }  return res; }
#define rs resize
typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

const ll N = 100009;
ll a,b,t,tem,s;
int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>a>>b>>t;
    tem = a;
    while(tem <= t){
        s += b;
        tem += a;
    }
    cout<<s;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int n=3;
	int a[n];
	int i,j,k;
	for(i=0; i<n; i++)
		cin>>a[i];
	int sum=0;
	int xmin=99999999999999;
	int xmax=-1;
	int b[3]={};
	int imin,imax;
	for(i=0; i<n; i++)
	{
		if(a[i]<xmin) {xmin=a[i];imin=i;}
		if(a[i]>=xmax) {xmax=a[i];imax=i;}
	}
	int another=3-imin-imax;
	sum+=a[another]-a[imin];
	sum+=a[imax]-a[another];
	cout<<sum;
}


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

const int b[7] = {0,9,12,15,18,21,30};
inline bool check(const vector<int> &c){
  for(int x=0;x<6;x++){
    for(int i=b[x];i<b[x+1]-1;i++)if(c[i]!=c[i+1])return false;
  }
  return true;
}

inline void rot(vector<int> &c, int d){
  switch(d){
  case 0:
    swap(c[0],c[23]); swap(c[3],c[26]); swap(c[6],c[29]);
    swap(c[15],c[17]); swap(c[9],c[20]); break;
  case 1:
    swap(c[6],c[21]); swap(c[7],c[22]); swap(c[8],c[23]);
    swap(c[9],c[11]); swap(c[12],c[17]); break;
  case 2:
    swap(c[2],c[21]); swap(c[5],c[24]); swap(c[8],c[27]);
    swap(c[12],c[14]); swap(c[11],c[18]); break;
  case 3:
    swap(c[0],c[27]); swap(c[1],c[28]); swap(c[2],c[29]);
    swap(c[18],c[20]); swap(c[14],c[15]); break;
  }
}

int rec(int d, vector<int> &c){
  if(check(c))return d;
  if(d>=8)return 8;

  int res = 8;
  for(int i=0;i<4;i++){
    rot(c,i);
    res = min(res, rec(d+1,c));
    if(res==d)break;
    rot(c,i);
  }
  return res;
}

int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    vector<int> p(30);
    for(int i=0;i<30;i++)scanf("%d\n",&p[i]);
    printf("%d\n",rec(0,p));
  }
}

Measured memory_bytes: 1032
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 3e5+10;
const ll mod =   1e9+7;
ll n,x;
ll arr[N],ans[N];
int main()
{  fast
  cin>>n;
  for(ll i=1;i<=n;i++){
  	cin>>arr[i];
  	x^=arr[i];
  }
  for(ll i=1;i<=n;i++){
  	ans[i]=x^arr[i];
  }
  for(ll i=1;i<=n;i++)
  cout<<ans[i]<<" ";

}

Measured memory_bytes: 6668
import copy
N, P = map(int, input().split())

x=[i+1 for i in range(int(P**(1/2))) if P%(i+1)==0]
for i in range(len(x)):
    if P%x[i]==0:
        x.append(int(P/x[i]))
x.sort(reverse=True)

for i in range(len(x)):
    tmp=round(x[i]**(1/N),10)
    if tmp%int(tmp)==0:
            break

print(int(tmp))

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

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 (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m;
vector<vi> g;
int visited[100001];

void dfs(int u, vector<int> &ans){
	visited[u] = 1;
	ans.pb(u);
	for(int v : g[u])if(!visited[v]){
		dfs(v, ans); break;
	}
}
int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	g.resize(n);
	int s, t;
	REP(i, m){
		int u, v;
		cin >> u >> v; u--; v--;
		g[u].pb(v);
		g[v].pb(u);
		s = u; t = v;
	}
	visited[s] = 1;
	visited[t] = 1;
	vi ans1, ans2;
	dfs(t, ans1);
	dfs(s, ans2);
	reverse(ALL(ans1));
	for(int x : ans2) ans1.pb(x);
	cout << ans1.size() << endl;
	REP(i, ans1.size()) cout << ans1[i] + 1 << " \n"[i + 1 == ans1.size()];
	return 0;
}


Measured memory_bytes: 9848
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N) cin >> A[i];
  vector<ll> minus(N), plus(N);
  minus[0] = -A[0], plus[0] = A[0];
  REP(i, N - 1) {
    int j = i + 1;
    if (j % 2 == 0) {
      minus[j] = minus[i] - A[j];
      plus[j] = plus[i] + A[j];
    } else {
      minus[j] = minus[i] + A[j];
      plus[j] = plus[i] - A[j];
    }
  }
  cout << plus[N-1] << endl;
  for (int i = 1; i < N; i++) {
    if (i % 2 == 0) {
      ll t1 = plus[N - 1] - plus[i-1];
      ll t2 = minus[i - 1];
      cout << t1 + t2 << endl;
    } else {
      ll t1 = minus[N - 1] - minus[i-1];
      ll t2 = plus[i - 1];
      cout << t1 + t2 << endl;
    }
  }
}

Measured memory_bytes: 3712
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

typedef complex<double> P;
double cross(P a, P b) {
    return imag(conj(a)*b);
}
double dot(P a, P b) {
    return real(conj(a)*b);
}

void solve() {
    int N;
    cin >> N;
    vector<P> ps;
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        ps.emplace_back(x, y);
    }
    double ng = 0, ok = 1000;
    rep(ITER, 60) {
        double rad = (ng + ok) / 2;
        bool flag = [&]{
            rep(i, N)FOR(j, i + 1, N) {
                P M = (ps[i] + ps[j]) *0.5;
                P ij = ps[j] - ps[i];

                double d = abs(ij)*0.5;
                if (rad <= d) {
                    continue;
                }
                double h = sqrt(rad*rad - d * d);

                for (int a : {1, -1}) {
                    P nor = ij * P(0, a) / abs(ij);
                    P C = M + nor * h;
                    bool included = true;
                    rep(k, N) {
                        double dist = abs(C - ps[k]);
                        if (dist > rad + 1e-8) {
                            included = false;
                            break;
                        }
                    }
                    if (included) {
                        return true;
                    }
                }
            }
            return false;
        }();
        (flag ? ok : ng) = rad;
    }

    cout << ok << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

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

int main(void) {
  int a, n, k;
  a = 1;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    if (a * 2 <= a + k) {
      a *= 2;
    } else {
      a += k;
    }
  }
  cout << a << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll n,k;
ll ans=1;
ll l_neg=-1,l_pos=-1,r_neg=-1,r_pos=-1;
const ll M = 1000000007;

bool cmp(ll a,ll b) {return abs(a)<abs(b);}

ll calc(vector<ll> a)
{
    ll temp = 1;
    for(ll i = n - k; i < n; i++)
        temp = (temp * a[i]) % M;
    return (temp+M)%M;
}
int main()
{
    cin >> n >> k;
    vector<ll> a(n, 0);
    for(ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), cmp);
    for(ll i = n - k; i < n; i++)
    {
        ans = (ans * a[i]) % M;
        if(r_pos == -1 && a[i] > 0) r_pos = i;
        if(r_neg == -1 && a[i] < 0) r_neg = i;
    }
    for(ll i = n - k - 1; i >= 0; i--)
    {
        if(l_pos == -1 && a[i] > 0)l_pos = i;
        if(l_neg == -1 && a[i] < 0) l_neg = i;
    }

    if(ans < 0 && n != k)
    {
        if(r_pos == -1)
        {
            if(l_pos == -1)
            {
                ans = 1;
                for(ll i = 0; i < k; i++)
                    ans = (ans * a[i]) % M;
            }
            else
            {
                swap(a[l_pos], a[r_neg]);
                ans = calc(a);
            }
        }
        else
        {
            if(l_neg == -1)
            {
                swap(a[l_pos], a[r_neg]);
                ans = calc(a);
            }
            else if(l_pos == -1)
            {
                swap(a[l_neg], a[r_pos]);
                ans = calc(a);
            }
            else
            {
                vector<ll> c1 = a;
                vector<ll> c2 = a;
                swap(c1[l_neg], c1[r_pos]);
                swap(c2[l_pos], c2[r_neg]);
                ans=(abs(a[l_neg]*a[r_neg])>abs(a[l_pos]*a[r_pos]))?calc(c1):calc(c2);//判断交换之后哪一个比较大
            }
        }
    }
    cout << (ans+M)%M << endl;
    return 0;
}



Measured memory_bytes: 9396
// ABC078_B
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <tuple>  // std::tuple std::get
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define REPN(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0LL)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
#define zero_pad(num) setfill('0') << std::right << setw(num)
#define space_pad(num) setfill(' ') << std::right << setw(num)

typedef long long ll;

const ll MOD7 = 1000000007;  // 1 000 000 007
const ll MOD9 = 1000000009;  // 1 000 000 009

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

    // input
    ll N, M, O;
    cin >> N >> M >> O;
    
    // calculation
    ll num = N/(M+O), amari = N%(M+O);
    if (amari < O) {
        cout << num - 1 << "\n";
    } else if (amari >= O){
        cout << num << "\n";
    }
    
    return 0;
}


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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  int n;
  cin >> n;
  vector<ll> va(n);

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

  deque<ll> ans;
  for (int i = 0; i < va.size(); ++i) {
    if (i % 2 == 0) {
      ans.push_back(va[i]);
    } else {
      ans.push_front(va[i]);
    }
  }

  bool rev = n % 2 != 0;
  if (rev) {
    for (auto it = ans.rbegin(); it != ans.rend(); it++) {
      cout << *it;
      if (it == ans.rend() - 1) {
        cout << '\n';
      } else {
        cout << ' ';
      }
    }
  } else {
    for (auto it = ans.begin(); it != ans.end(); it++) {
      cout << *it;
      if (it == ans.end() - 1) {
        cout << '\n';
      } else {
        cout << ' ';
      }
    }
  }

  return 0;
}

Measured memory_bytes: 6360
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

int main(int argc, char const *argv[]) {
    int n;cin>>n;
    vector<int> d(n);
    rep(i,n) cin>>d[i];
    sort(d.begin(), d.end());
    if (n%2==1) {
        cout << 0 << endl;
        return 0;
    }

    int x = n/2;
    cout << d[x]-d[x-1] << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#define llint long long

using namespace std;

llint n;
llint a[100005];

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

bool calc()
{
	llint cnt = 0, sum = 0;
	for(int i = 1; i <= n; i++) if(a[i] % 2) cnt++;
	for(int i = 1; i <= n; i++) sum += a[i] - 1;
	
	if(cnt == 1 && sum % 2 == 0){
		llint d = 0;
		for(int i = 1; i <= n; i++){
			if(a[i] % 2){
				if(a[i] == 1) return false;
				a[i]--;
				break;
			}
		}
		for(int i = 1; i <= n; i++) d = gcd(d, a[i]);
		if(d > 1){
			for(int i = 1; i <= n; i++) a[i] /= d;
			return !calc();
		}
	}
	return sum % 2;
}

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	if(calc()) cout << "First" << endl;
	else cout << "Second" << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  long a, b, c=0, d=0, e, f, g, h, n;
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  int sa, sb, sc;
  sa=s1.size();
  sb=s2.size();
  sc=s3.size();
  char x='a';
  int na=sa, nb=sb, nc=sc;
  
  while(1){
    if(x=='a'){
      if(na==0) break;
      x=s1[sa-na]; na--;
    }
    if(x=='b'){
      if(nb==0) break;
      x=s2[sb-nb]; nb--;
    }
    if(x=='c'){
      if(nc==0) break;
      x=s3[sc-nc]; nc--;
    }
  }
  if(x=='a') co("A");
  if(x=='b') co("B");
  if(x=='c') co("C");
      
  
  return 0;
}

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

#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(),(x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;

int main(int argc, char *argv[]) {
    ll x;
    cin >> x;
    
    if (x < 1200) MSG("ABC")
    else MSG("ARC")
    
    return 0;
}


Measured memory_bytes: 256
n, y = map(int, input().split())
for i in range(n+1):
    for j in range(n+1-i):
        k = n - i - j
        if k < 0:
            continue
        elif i * 10000 + j * 5000 + k * 1000 == y:
            print(i,j,k)
            exit()
print(-1,-1,-1)

Measured memory_bytes: 3060
import java.util.*;

public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    Arrays.sort(A);
    int last = -1;
    boolean[] dp = new boolean[K + 1];
    dp[0] = true;
    for (int i = N - 1; i >= 0 ; i--) {
      for (int j = K; j >= 0; j--) {
        if (dp[j]) {
          if (j + A[i] >= K) {
            last = i;
          } else {
            dp[j + A[i]] = true;
          }
        }
      }
    }
    System.out.println(last == -1 ? N : last);
  }

}


Measured memory_bytes: 29308
//#include <bits/stdc++.h>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)//初期値a,i<bの範囲でループ
#define REP(i,n) FOR(i,0,n)//初期値0,i<nの範囲でループ
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;



int main(){

    int n,a,b;
    cin>>n>>a>>b;
    if((b-a)%2==0){
        cout<<"Alice"<<endl;
        return 0;
    }
    cout<<"Borys"<<endl;
    

    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(long long &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
long long N;
long long A;
long long B;
int main(){
  rd(N);
  rd(A);
  rd(B);
  if(N==1){
    if(A==B){
      wt_L(1);
      wt_L('\n');
    }
    else{
      wt_L(0);
      wt_L('\n');
    }
    return 0;
  }
  if(A>B){
    wt_L(0);
    wt_L('\n');
    return 0;
  }
  wt_L((N-2) * (B-A) + 1);
  wt_L('\n');
  return 0;
}
// cLay varsion 20191125-1

// --- original code ---
// ll N, A, B;
// {
//   rd(N,A,B);
//   if(N==1) wt(if[A==B, 1, 0]), return 0;
//   if(A>B) wt(0), return 0;
//   wt((N-2) * (B-A) + 1);
// }


Measured memory_bytes: 256
function Main(input) {
	input = input.split("\n");
	input1 = input[0].split(" ")
	const A = parseInt(input1[0])
	const B = parseInt(input1[1])
	if((A+B) % 2 == 1){
		console.log("IMPOSSIBLE")
	}else{
		console.log((A+B)/2)
	}
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
import functools
import math

N, X = [int(i) for i in input().split()]
x_list = [int(i) for i in input().split()]

x_list.append(X)
num_list = sorted(x_list)
 
tmp = map(lambda x: abs(x[0] - x[1]),
          zip(num_list[:-1],num_list[1:]))

D = functools.reduce(lambda acc, x: math.gcd(acc, x), tmp, 0)

print(D)


Measured memory_bytes: 20824
#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 n, k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i, n) cin >> p.at(i);
  sort(p.begin(), p.end());
  int ans = 0;
  rep(i, k) ans += p.at(i);
  
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3632
C = []
for _ in range(3):
    c = list(map(int,input().split()))
    C.append(c)

if((C[0][0]-C[1][0]==C[0][1]-C[1][1])and(C[0][0]-C[1][0]==C[0][2]-C[1][2])
        and(C[0][0]-C[2][0]==C[0][1]-C[2][1])and(C[0][0]-C[2][0]==C[0][2]-C[2][2])
        and(C[0][0]-C[0][1]==C[1][0]-C[1][1])and(C[0][0]-C[0][1]==C[2][0]-C[2][1])
        and(C[0][0]-C[0][2]==C[1][0]-C[1][2])and(C[0][0]-C[0][2]==C[2][0]-C[2][2])):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <stdio.h>
#include <algorithm>
using namespace std;

int read()
{
	char c;
	while((c = getchar()) < 48 || c > 57);
	int x = c - 48;
	while((c = getchar()) > 47 && c < 58) x = x * 10 + c - 48;
	return x;
}

int a[200002];

int main()
{		
	int n, i, x, t;
	long long s = 0;
	
	n = read();
	for(i = 1; i <= n; i++){
		a[i] = read() - i;
	}
	sort(a + 1, a + n + 1);
	x = a[(n + 1) >> 1];
	for(i = 1; i <= n; i++){
		t = a[i] - x;
		if(t < 0) t = -t;
		s += t;
	}
	printf("%lld\n", s);
				
	return 0;
}

Measured memory_bytes: 2380
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define mod 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=200050;
//ここまでテンプレ
int main(){
	int N;
	cin>>N;
	for(int i=N;;i++){
		if(i%111==0){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

ll dp[1000010][2]={};

signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  string s;cin>>s;
  int n=siz(s);

  rep(i,0,1000010){
    dp[i][0]=INF;
    dp[i][1]=INF;
  }

  dp[0][0]=0;
  dp[0][1]=1;

  rep(i,0,siz(s)){
    int num=s[i]-'0';

    if(num<9)chmin(dp[i+1][1],dp[i][0]+num+1);

    chmin(dp[i+1][0],dp[i][0]+num);//
    
    chmin(dp[i+1][0],dp[i][1]+min(10-num,num+1));
    chmin(dp[i+1][1],dp[i][1]+9-num);

  }
  cout<<dp[n][0]<<ENDL;
}
//( ・ __ ・ ) KEEP BEING ORGANIZED
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 17052
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  int N,x;
  cin>>N>>x;
  int a[N];
  REP(i,N)cin>>a[i];
  sort(a,a+N);
  int ans=0;
  REP(i,N-1){
    if(x<a[i])break;
    if(x>=a[i])ans++;
    x-=a[i];
  }
  if(x==a[N-1])ans++;
  cout<<ans<<endl;
  return 0;
}


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

#define REP(i, s, e) for(int i = (int)(s); i < (int)(e); ++i)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

int main() {
  int n, m;
  cin >> n >> m;
  using P = pair<int, int>;
  vector<P> v(m);
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    --y;
    v[i] = {x, y};
  }
  sort(v.begin(), v.end());

  vector<P> ans(n);
  rep(i, n) ans[i] = {i, i+1};
  rep(i, m) {
    int x = v[i].second;
    int y = x + 1;
    ans[x].first = min(ans[x].first, ans[y].first);
    ans[x].second = max(ans[x].second, ans[y].second);
    ans[y].first = min(ans[x].first, ans[y].first);
    ans[y].second = max(ans[x].second, ans[y].second);
  }
  rep(i, n) {
    cout << ans[i].second-ans[i].first << (i+1 == n ? '\n' : ' ');
  }
  return 0;
}



Measured memory_bytes: 5196
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);};};
const int MOD = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<62;

vector<ll> enum_div(ll n){
    vector<ll> ret;
    for(ll i = 1 ; i*i <= n ; ++i){
        if(n%i == 0){
            ret.push_back(i);
            if(i != 1 && i*i != n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}



int main(void) {

    ll n;
    cin>>n;
    
    vector<ll> v = enum_div(n);
    v.push_back(1);
    ll ans=LLINF;
    for(int i=0;i<v.size();i++){
        ans=min(ans,n/v[i] + v[i] -2 );
    }
    
    fin(ans);



}



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

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

    int red_count = 0, blue_count = 0;

    rep(i, s.size())
    {
        if (s[i] == '0')
        {
            red_count++;
        }
        else
        {
            blue_count++;
        }
    }

    cout << min(red_count, blue_count) * 2 << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	int N;
	cin >> N;
	vector<pair<int, int>> R;
	for (auto i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;
		R.push_back({ a, b });
	}
	vector<pair<int, int>> B;
	for (auto i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;
		B.push_back({ a, b });
	}

	sort(R.begin(), R.end());
	sort(B.begin(), B.end());
	
	auto ans = 0;
	vector<bool> used(N);
	for (auto i = N - 1; i >= 0; --i)
	{
		auto x = R[i].first;
		auto y = R[i].second;
		auto use = -1;
		auto minY = 2 * N;
		for (auto j = 0; j < N; ++j)
		{
			auto nx = B[j].first;
			auto ny = B[j].second;
			if (x < nx
				&& y < ny
				&& !used[j]
				&& ny < minY)
			{
				minY = ny;
				use = j;
			}
		}

		if (use >= 0)
		{
			used[use] = true;
			++ans;
		}
	}

	cout << ans << endl;

	return 0;
}

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

int main(){
  int n,i,j,k,num;
  int cards[4][14] = {0};
  char mark;

  cin >> n;

  for(k = 0; k < n; k++){
    cin >> mark >> num;

    if(mark == 'S') cards[0][num] = 1;
    if(mark == 'H') cards[1][num] = 1;
    if(mark == 'C') cards[2][num] = 1;
    if(mark == 'D') cards[3][num] = 1;
  }

  for(i = 0; i < 4; i++){
    for(j = 1; j <= 13; j++){
      if(cards[i][j] == 0){
        if(i == 0) cout << 'S' << " " << j << endl;
        if(i == 1) cout << 'H' << " " << j << endl;
        if(i == 2) cout << 'C' << " " << j << endl;
        if(i == 3) cout << 'D' << " " << j << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1160
n = int(input())
a = [0]+list(map(int, input().split()))
boxi=[0]*(n+1)
box=[]
for i in range(n,0,-1):
  t=0
  for j in range(2,n//i+1):
    if boxi[j*i] == 1:
      t+=1
  if t%2 != a[i]:
    box.append(i)
    boxi[i]=1
else:
  print(len(box))
  box=[str(i) for i in box]
  print(" ".join(box))
#print(-1)

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

using namespace std;

int main(){
	int n,m;
	cin >> n >> m;
	vector<int> v(m);
	vector<vector<int> > mx(n,vector<int>(m));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> mx[i][j];
		}
	}
	for(int i=0;i<m;i++){
		cin >> v[i];
	}
	for(int i=0;i<n;i++){
		int ans=0;
		for(int j=0;j<m;j++){
			ans+=mx[i][j]*v[j];
		}
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 3144
#include<iostream>

using namespace std;
int main()
{
  string s;
  int a=0,x=0;
  for(;cin>>s;)
    {
      for(int i=0;i<s.size();i++)
	{
	  if(s[i]>='0' && s[i]<='9')
	    x*=10,x+=s[i]-'0';
	  else
	    a+=x,x=0;
	}
      a+=x;
      x=0;
    } 
  cout<<a<<endl;
}

Measured memory_bytes: 1184
// Copyright 2020 yaito3014
#include <bits/stdc++.h>

int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (auto& e : A) cin >> e;
  sort(begin(A), end(A));
  cout << accumulate(cbegin(A), next(cbegin(A), K), 0) << '\n';
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main() {
  int m, n;

  while(cin >> m, m) {
    PII field[m];
    REP(i, m) {
      int x, y;
      cin >> x >> y;
      field[i] = MP(x, y);
    }

    cin >> n;
    PII star[n];
    REP(i, n) {
      int x, y;
      cin >> x >> y;
      star[i] = MP(x, y);
    } 
  
    int x, y;
    REP(i, n) {
      x = star[i].first - field[0].first;
      y = star[i].second - field[0].second;

      int cnt = 0;
      REP(j, m) {
	REP(k, n) {
	  if(field[j].first + x == star[k].first && field[j].second + y == star[k].second) cnt++;
	}
      }
      if(cnt == m) break;
    }
    cout << x << ' ' << y << endl;
  }
}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
using namespace std;
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 long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    priority_queue<ll> que;
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
        que.push(a[i]);
    }

    for (ll i = 0; i < m; i++)
    {
        ll p = que.top();
        que.pop();
        p /= 2;
        que.push(p);
    }

    ll ans = 0;
    while (que.size())
    {
        ans += que.top();
        que.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 2168