akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define mod 1000000007

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

using namespace std;
typedef long long ll;
const long long INF = 1LL << 60;
 
int main(void){
	
	int N;
    vector<pair<double, double>> xy;
    cin >> N;
    xy.resize(N);
    rep(i, N)
        cin >> xy[i].first >> xy[i].second;

    vector<int> order(N);
    rep(i, N)
        order[i] = i;
    double sum = 0;
    double count = 0;
    do{
        double s = 0;
        for(int i = 0; i < N - 1; i++){
            s += sqrt((xy[order[i + 1]].first - xy[order[i]].first) * (xy[order[i + 1]].first - xy[order[i]].first) + (xy[order[i + 1]].second - xy[order[i]].second) * (xy[order[i + 1]].second - xy[order[i]].second));
        }
        sum += s;
        count++;
    }while(next_permutation(order.begin(), order.end()));

    printf("%.8f", sum / count);
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

bool myComp(PII x, PII y){
  return x.second < y.second;
}

int main(void){
  vector<PII> queries;
  int n, qnum;
  int ans,t;

  cin >> n >> qnum;
  for (int i=0; i<qnum; i++){
    int a,b;
    cin >> a >> b;
    queries.push_back(make_pair(a, b));
  }
  sort(queries.begin(), queries.end(), myComp);

  //for (int i=0; i<qnum; i++){
  //  cout << queries[i].first << ", " << queries[i].second << endl;
  //}

  t = queries[0].second;
  ans = 1;
  for (int i=1; i<qnum; i++){
    if (queries[i].first >= t){
      ans++;
      t = queries[i].second;
      //cout << "(" << i << ")," << t << endl;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for(int i = 0; i <= 1e5; i++) {
        if((int)(i * 1.08) == N) {
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100

int M[MAX][MAX];
int disc[MAX];
int t;
int finish[MAX];

void df(int id, int n){
  int i;
  
  if (finish[id]!=0){
    return;
  }
  else if(disc[id]==0){
    disc[id]=(++t);
  }

  for(i=0;i<n;i++){
    if(M[id][i]==1 && disc[i]==0){
      disc[i] = (++t);
      df(i, n);
    }
  }
  finish[id]=(++t);
}

int main(){
  int i,j,n,a,k,b;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=0;
    }
    disc[i]=0;
    finish[i]=0;
  }
  
  for(i=0;i<n;i++){
    scanf("%d%d",&a,&k);
    for(j=0;j<k;j++){
      scanf("%d",&b);
      M[a-1][b-1]=1;
    }
  }

  t=0;
  for(i=0;i<n;i++){
    df(i,n);
  }
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,disc[i],finish[i]);
  }
  return 0;
}



Measured memory_bytes: 2148
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)
//#define rep(i, n) for(int (i) = 0, TmP = (n); (i) < (int)TmP ; ++(i))
#define asort(v, n) sort((v), (v + n)) //Using array
#define vsort(v) sort((v).begin(), (v).end()) // Using vector
#define vint vector<int>
typedef long long ll;

using namespace std;

signed main(){
  ll x;
  cin >> x;

  ll ans = 0;
  ans += (x / 500) * 1000;
  x -= (x / 500) * 500;
  ans += (x / 5) * 5;
  cout << ans << endl;
}


Measured memory_bytes: 256
S = input()
if "C" in S and "F" in S:
    C_ind = S.index("C")
    S_inv = S[::-1]
    S_ind = S_inv.find("F")
    S_ind = len(S) - S_ind - 1
    if C_ind < S_ind:
        print("Yes")
    else:
        print("No")
else:
    print("No")


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,id[6010],a[6010],b[6010],p[2];
char s[6010];
string f[6010],g[6010];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	int numa=0,numb=0;
	for (int i=1;i<=n+n;i++)
		if (s[i]=='a') id[i]=++numa,a[numa]=i;
			else id[i]=++numb,b[numb]=i;
	int now=0;
	f[0]="";
	for (int i=n+n,j;i>=1;i=j-1)
	{
		j=i;
		p[0]=p[1]=0;
		p[s[j]-'a']=1;
		while (p[0]!=p[1]) p[s[--j]-'a']++;
		f[++now]="";
		if (s[j]=='a')
		{
			int k=j;
			while (k<=i)
			{
				if (s[k]=='b') { k++;continue;}
				f[now]=f[now]+"ab";
				k=b[id[k]]+1;
			}
		}else
		{
			int S=id[j],T=id[i];
			for (int k=T;k>=S;k--)
			{
				int x=k;
				g[k]="";
				while (x<T&&b[x+1]<a[x]) x++;
				for (int l=j;l<=i;l++)
					if (id[l]>=k&&id[l]<=x) g[k]=g[k]+s[l];
				if (x+1<=T) g[k]=g[k]+g[x+1];
				if (k+1<+T) g[k]=max(g[k],g[k+1]);
			}
			f[now]=g[S];

		}
		f[now]=max(f[now]+f[now-1],f[now-1]);
	}
	printf("%s\n",f[now].c_str());
	return 0;
}


Measured memory_bytes: 10752
N, T = gets.chomp.split.map(&:to_i)
t = gets.chomp.split.map(&:to_i)

ans = 0
N.times do |i|
  if i == N-1
    ans += T
  else
    ans +=[t[i+1] - t[i], T].min
  end
end
p ans


Measured memory_bytes: 21892
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<iomanip>
#include<set>
#include<unordered_map>
using namespace std ;

#define MAXN 100007

int n , m ;
int a[ MAXN ] ;

long long add[ MAXN ] ;
long long cnt[ MAXN ] ;

void input ( ) {
    scanf ( "%d%d" , &n , &m ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
}

void solve ( ) {
    long long ans = 0 ;
    for ( int i = 1 ; i < n ; ++ i ) {
        if ( a[ i ] < a[ i + 1 ] ) {
            ans += a[ i + 1 ] - a[ i ] ;
            add[ a[ i ] + 1 ] += a[ i ] + 1 ;
            add[ a[ i + 1 ] + 1 ] -= a[ i ] + 1 ;

            ++ cnt[ a[ i ] + 1 ] ;
            -- cnt[ a[ i + 1 ] + 1 ] ;
        }
        else {
            ans += a[ i + 1 ] + m - a[ i ] ;
            
            add[ a[ i ] + 1 ] += a[ i ] + 1 ;
            add[ m + 1 ] -= a[ i ] + 1 ;

            ++ cnt[ a[ i ] + 1 ] ;
            -- cnt[ m + 1 ] ;

            add[ 1 ] += a[ i ] - m + 1 ;
            add[ a[ i + 1 ] + 1 ] -= a[ i ] - m + 1 ;

            ++ cnt[ 1 ] ;
            -- cnt[ a[ i + 1 ] + 1 ] ;
        }
    }
    long long sm = 0 ;
    long long p = 0 ;
    long long mx = 0 ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        sm += add[ i ] ;
        p += cnt[ i ] ;
        if ( mx < p * i - sm ) { mx = p * i - sm ; }
    }
    printf ( "%lld\n" , ans - mx ) ;
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    input ( ) ;
    solve ( ) ;
    return 0 ;
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int n,m,x,y,mx=-INT_MAX,my=INT_MAX;
    cin>>n>>m>>x>>y;
    vector<int>a,b;
    for(int i=0;i<n;i++){
        int c;
        cin>>c;
        a.push_back(c);
        mx=max(mx,c);
    }
    for(int i=0;i<m;i++){
        int c;
        cin>>c;
        b.push_back(c);
        my=min(my,c);
    }
    for(int i=x+1;i<=y;i++){
      if(i>mx && i<=my)
      {
          cout<<"No War"<<endl;
          return 0;
      }

    }



   cout<<"War"<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include<iostream>

using namespace std;

int main() {
	int n, c[500], s[500], f[500], t[500];

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		cin >> c[i] >> s[i] >> f[i]; //開通式s[i]秒後に出発、i駅からi+1駅間がc[i]秒、i駅からf[i]秒ごとに発車
	}

	for (int i = n - 1; i < 500; i++) {
		c[i] = 0;
	}

	for (int i = 0; i < n; i++) { //i駅からスタートしてj駅目の処理
		t[i] = s[i];
		for (int j = i; j < n - 1; j++) {
			if (t[i] < s[j]) {
				t[i] = s[j];
			}
			else if (t[i]%f[j] == 0) {
				t[i];
			}
			else {
				t[i] = t[i] + f[j] - t[i] % f[j];
			}
			t[i] += c[j];
		}
	}

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

	cout << 0 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>

int main(void) {
  int h, w;

  std::string str;
  std::cin >> str;
  h = std::stoi(str);
  std::cin >> str;
  w = std::stoi(str);

  const char* a[h]/*[w]*/ = {0};
  std::string s[h];
  for (size_t i = 0; i < h; i++) {
    std::cin >> s[i];
    a[i] = s[i].c_str();
  }

  for (size_t i = 0; i < h; i++) {
    for (size_t j = 0; j < w; j++) {
      if (a[i][j] == '#') {
        if (i >= 1 && a[i - 1][j] == '#') {
          continue;
        }
        if (i + 1 < h && a[i + 1][j] == '#') {
          continue;
        }
        if (j >= 1 && a[i][j - 1] == '#') {
          continue;
        }
        if (j + 1  < w && a[i][j + 1] == '#') {
          continue;
        }
        std::cout << "No" << std::endl;
        return 0;
      }
    }
  }

  std::cout << "Yes" << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define forn(i,n1, n2) for (ll i = n1; i < n2; i++)
#define w(t) ll t;cin>>t;while(t--)
#define en "\n"
#define f first
#define s second
const ll mod = 1000000007;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,d,x,y,ans=0;
    cin>>n>>d;
    while(n--)
    {
        cin>>x>>y;
        if(x*x+y*y<=d*d)
        ans++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3604
// 解説後
#include <iostream>
#include <set>
#include <vector>

// $l < i$として$P_i$より大きい値$P_l$が現れるとき、その$l$を大きな順に$L_1, L_2, \dots$とおく
// 同様に、$r > i$として$P_i$より大きい値$P_r$が現れるとき、その$r$を小さな順に$R_1, R_2, \dots$とおく
// すると、$\dots < L_2 < L_1 < i < R_1 < R_2 < \dots$となる
//
// $X_{L,R} = P_i$となるには、$L$から$R$までの間に$P_i$より大きい値が1つだけ含まれていれば良い
// つまり、$L_2 < L \le L_1$かつ$i \le R < R_1$の場合と$L_1 < L \le i$かつ$R_1 \le R < R_2$の場合である
// すると、$X_{L,R} = P_i$となる$L$と$R$の組み合わせの数は$C_i = (L_1 - L_2) \times (R_1 - i) + (i - L_1) \times (R_2 - R_1)$となる
//
// $\sum_{L=1}^{N-1} \sum_{R=L+1}^N X_{L,R}$は$1 \le L < R \le N$のときのすべての$L$と$R$の組み合わせを1つだけ含む
// よって、$\sum_{L=1}^{N-1} \sum_{R=L+1}^N X_{L,R} = \sum_{i=1}^N P_i \times C_i$である
//
// また、Pは${1, 2, \dots, N}$の順列なので、$\sum_{i=1}^N P_i \times C_i = \sum_{p \in P} p \times C_i$（ここで、$i$は$P[i] = p$）である
int solve_E() {
  size_t N = 0;  // Pの大きさ
  std::cin >> N;

  std::vector<uint64_t> P(N + 1);
  for (size_t i = 1; i <= N; ++i) {
    std::cin >> P[i];
  }

  // Pの値からインデックスを探すためのリストを作る
  std::vector<size_t> indexes(N + 1);
  for (size_t i = 1; i <= N; ++i) {
    indexes[static_cast<size_t>(P[i])] = i;
  }

  // X_{L,R}の総和を求める
  uint64_t result = 0;
  std::multiset<size_t> set{0, 0, N + 1, N + 1};  // pより大きな値のインデックスを格納するset。初期値として両端を指すインデックスを含む
  for (size_t p = N - 1; p > 0; --p) {
    const size_t i = indexes[p];

    // pより大きな値を持つインデックスのsetを累積的に構築する
    set.insert(indexes[p + 1]);

    // 境界のインデックスを取得する
    auto l2_iter = ++set.lower_bound(i);
    auto r2_iter = l2_iter--;
    auto r1_iter = l2_iter--;
    auto l1_iter = l2_iter--;

    // C_iを求める
    const size_t c = (*l1_iter - *l2_iter) * (*r1_iter - i) +
                     (i - *l1_iter) * (*r2_iter - *r1_iter);

    // 総数を求める
    result += p * c;
  }

  // 結果発表
  std::cout << result;
  return 0;
}

int main() {
  return solve_E();
}


Measured memory_bytes: 6528
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    string s;
    cin>>s;
    ll sum=0;
    for(auto ch:s)
        sum+=(ch-'0');   
    if(sum%9==0)
        cout<<"Yes\n";
    else
        cout<<"No\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    //cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 1000000000 + 7;
template<typename T>
map<T, ll> prime_factorize(T x){
  map<T, ll> res;
  while(x%2==0){
    x/=2;
    res[2]++;
  }
  for(ll i=3;i*i<=x;i+=2){
    while(x%i==0){
      x/=i;
      res[i]++;
    }
  }
  if(x!=1) res[x]++;
  return res;
}

int main(){
  cout << setprecision(10);
  ll X;
  cin >> X;
  
  ll A,B;
  ll ans_a;
  bool minus_flg = false;
  for(B = -200; B <= 200; B++){
    A = X + B*B*B*B*B;
    ans_a = 1;
    // cerr << "A: " << A << " B: " << B  << endl;

    if(A < 0){
      minus_flg = true;
      A = -A;
    } else {
      minus_flg = false;
    }

    if(A == 0){
      ans_a = 0;
      break;
    } else if(A==1){
      ans_a = 1;
      break;
    } else { 
      // Aが5乗数かどうか判定する
      auto a = prime_factorize(A);
      bool flg = true;
      for(auto x: a){
        if(x.second % 5 != 0){
          flg = false;
          break;
        } else { 
          ll tmp = x.second / 5;
          ans_a *= pow(x.first, tmp);
        }
      }

      if(flg){
        break;
      } 
    }
  }

  if(minus_flg){
    ans_a = -ans_a;
  }
  cout << ans_a << " " << B << endl;
}


Measured memory_bytes: 3920
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace c
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] nl = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long n = nl[0];
            long l = nl[1];
            long[] a = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long fin = -1;
            for (long i = 0; i < n - 1; i++)
            {
                if (a[i] + a[i + 1] >= l)
                {
                    fin = i + 1;
                    break;
                }
            }
            if (fin < 0)
            {
                Console.WriteLine("Impossible");
                return;
            }
            Console.WriteLine("Possible");

            for (long i = 1; i < fin; i++)
            {
                    Console.WriteLine(i);
            }
            for (long i = n - 1; i >= fin; i--)
            {
                Console.WriteLine(i);
            }
        }
    }
}


Measured memory_bytes: 19800
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define _GLIBCXX_DEBUG
#define V vector<ll>
using namespace std;
using ll = long long;


int main(){
    int n; cin >> n;
    int ans = 0;
    rep(i,1,n+1){
        if(i%2 == 0) continue;
        int N = i;
        int y = 0;
        rep(j,1,N+1){
            if(N%j == 0) y++;
        }
        if(y == 8) ans++;
    }
    cout << ans <<"\n";
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define what_is(x) cerr << #x << " is " << x << endl;
#define MT make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FOR(i,n) for (int i=0;i < n ; i++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

ll INF=1e15+7;
ll *dist;
//bool *visited;				// 4--2 -- 0-- 1-- 3
int n;
int k=1;
void bfs(std::vector<pair<int,ll>> edges[]){
	//visited[k-1]=true;
	dist[k-1]=0;
	queue<int >q;
	q.push(k-1);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(auto x : edges[v]){
			if(dist[x.first] > dist[v]+x.second){ 
				dist[x.first]=dist[v]+x.second;
				q.push(x.first);
			}
		}
	}
}

int main(){
	//int n;
	int a,b;
	ll c;
	cin >> n;
	std::vector<pair<int,ll>> edges[n];
	FOR(i,n-1){
		cin >> a >> b>> c;
		edges[a-1].eb(make_pair(b-1,c));
		edges[b-1].eb(make_pair(a-1,c));
	}
	int q,x,y;
	cin >> q >> k;
	dist=new ll[n];
	//visited=new bool[n];
	FOR(i,n){
		dist[i]=INF;
		//visited[i]=false;
	} 
	
	//dist[k-1]=0;
	//visited[k-1]=true;
	bfs(edges);
	/*FOR(i,n)
		cout <<  dist[i] << "\n";*/

	FOR(i,q){
		cin >> x >> y;
		cout << dist[x-1]+dist[y-1] <<"\n";
	}


	return 0;
}

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

using namespace std;

void solve(long N, long M, vector<long> A) {
  long rest = N - accumulate(A.cbegin(), A.cend(), 0);
  cout << (rest >= 0 ? rest : -1) << endl;
}

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

  long N, M;
  cin >> N >> M;
  vector<long> A(M);
  for(int i = 0 ; i < M ; i++){
    cin >> A[i];
  }
  solve(N, M, move(A));
  return 0;
}


Measured memory_bytes: 3724
import sys
atn = []
for i in range(5):
    atn.append(int(input()))

k = int(input())

for i in range(5):
    for j in range(i+1,5):
        if abs(atn[i]-atn[j]) >k:
            print(":(")
            sys.exit(0)
else:
    print("Yay!")

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

int n;
int par(int x) {
    if (x % n == 0) return x / n - 1;
    return x / n;
}

int main() {
    int q;
    cin >> n >> q;
    if (n == 1) {
        while (q--) {
            int u, v;
            cin >> u >> v;
            cout << min(u, v) << '\n';
        }
        return 0;
    }
    while (q--) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        while (u != v) {
            while (u < v) {
                v = par(v);
            }
            while (u > v) {
                u = par(u);
            }
        }
        cout << u + 1 << '\n';
    }
}

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

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define endl '\n'
#define MAX

typedef long long ll;
typedef pair<int,int> pii;
//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;


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

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	string s;
	cin >> s;
	int ans = 1111111;
	
	for(int i = 0; i + 2 < s.size(); i++){
		int num = (s[i] - '0') * 100 + (s[i + 1] - '0') * 10 + (s[i + 2] - '0');
		ans = min(ans, abs(num - 753));
	}
	
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
// ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
// ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
// [███████████████████].░░░░░░░░░░░░░░
// ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░

//PointBlank's code (⌐■_■)
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define repp(i, a, b) for(ll i = a; i <= b; i++)
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define rrep(i, b, a) for(ll i = b; i >= a; i--)
#define pb emplace_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define mem(a, b) memset(a, b, sizeof(a));
#define mem0(a) memset(a, 0, sizeof(a));
#define quickio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define in_edges(m) repp(i, 1, m){ll a, b; cin >> a >> b; v[a].pb(b), v[b].pb(a);}
#define debug(this) cerr<<"> "<<#this<<" : "<<this<<"\n"
#define endl "\n"
ll power(ll x, ll y); 

const ll MOD = 1000000007;
ll inp[5][100005], mx[4][100005];

int main() //PointBlank's code ¯\_(ツ)_/¯
{
    quickio
    ll n;
    cin >> n;
    repp(i, 1, n) cin >> inp[1][i] >> inp[2][i] >> inp[3][i];
    repp(i, 1, n) repp(j, 1, 3) repp(k, 1, 3) if(j != k)
        mx[j][i] = max(mx[k][i - 1] + inp[j][i], mx[j][i]);
    cout << max(max(mx[1][n], mx[2][n]), mx[3][n]);
}

ll power(ll x, ll y)
{ 
    ll res = 1; x %= MOD;
    while(y > 0){if(y & 1) res = (res*x) % MOD; y = y>>1, x = (x*x) % MOD;} 
    return res; 
}

Measured memory_bytes: 5760
#include <iostream>

using namespace std;
int main()
{
  int N,count = 0,seq = 0,j;
  cin >> N;
  int a[N];
  for(int i = 0;i < N;i++)
  {
    cin >> a[i];
  }
  for(int i = 0;i < N;)
  {
    j = i;
    while(a[i] == a[j])
    {
      seq++;
      j++;
      if(j == N)break;
    }
    count += seq/2;
    seq = 0;
    i = j;
  }
  cout << count;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
        public static void main(String args[])
        {
int x;
int y;
int ans;
Scanner scanner = new Scanner(System.in);
String sx = scanner.next();
String sy = scanner.next();
x = Integer.parseInt(sx);
y = Integer.parseInt(sy);
ans = x + y/2;
System.out.println(ans);
}
}

Measured memory_bytes: 21844
// abc134d: Preparing Boxes
#include <stdio.h>

int main(){
  int n;scanf("%d",&n);
  int a[n+1],b[n+1];
  for(int i=1;i<=n;i++){
    scanf("%d",a+i);
    b[i]=0;
  }

  int m=0;
  for(int i=n;i>0;i--){
    int c=0;for(int j=i+i;j<=n;j+=i) c^=b[j];// 排他的論理和で剰余処理
    b[i]=c^a[i];
    if(b[i]) m++;
  }

  printf("%d\n",m);
  for(int i=1;i<=n;i++)
    if(b[i]) printf("%d%c",i,--m?' ':'\n');

  return 0;
}

Measured memory_bytes: 2432
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN=2005;
const int MOD=1e9+7;

int n,m,k;
int d[MAXN*2][MAXN],pre[MAXN*2][MAXN];

int main(){
    //freopen("average.in","r",stdin);
    //freopen("average.out","w",stdout);

    scanf("%d%d%d",&n,&m,&k);
    d[0][0]=1;
    for(int i=1;i<n+m;i++){
        for(int j=0;j<=m;j++){
            pre[i][j]=((j?pre[i][j-1]:0)+d[i-1][j])%MOD;
            d[i][j]=(pre[i][j]-(j>=k?pre[i][j-k]:0)+MOD)%MOD;
        }
    }
    int ans=0;
    while(m>0){
        (ans+=d[(n+m-1)/(k-1)][m])%=MOD;
        m-=k-1;
    }
    printf("%d",ans);

    fclose(stdin);
    fclose(stdout);
}


Measured memory_bytes: 62976
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

using namespace std;

#define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

template <typename T>
T gcd(T m, T n) { return n == 0 ? m : gcd(n, m % n); }
template <typename T>
T lcm(T m, T n) { return n * m / gcd(n, m); }

signed main(void)
{
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; ++i)
    cin >> h[i];

  vector<int> dp(n);
  dp[n - 1] = 0;
  for (int i = n - 2; i >= 0; --i)
  {
    if (h[i] >= h[i + 1])
      dp[i] = dp[i + 1] + 1;
    else
      dp[i] = 0;
  }
  cout << *max_element(dp.begin(), dp.end()) << endl;
}


Measured memory_bytes: 1920
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,M,V,P = MI()
A = [0] + LI()
A.sort()


def f(i):  # i番目の問題が採用されうるか
    a = A[i]
    v = V-i  # 下位i人に全員が投票
    if A[-P] > a+M:
        return False
    v -= P-1  # 上位P-1人に全員が投票
    if sum(a+M-A[j] for j in range(i+1,N-P+2)) >= M*v:
        return True
    return False


left = 0
right = N
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(N+1-right)


Measured memory_bytes: 86620
N,M = list(map(int,input().split()))

e_list = [[] for i in range(N)]
es = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    es.append((a,b))
    e_list[a].append(b)

from collections import deque
flag=False
min_d = 10**27
for vg,vi in es:
    Q = deque([vi])
    checked_list = [False for i in range(N)]
    checked_list[vi]=True
    min_path_list = [10**27 for i in range(N)] #問題によりここを変える
    min_path_list[vi] = 0
    prev_list = [-1]*N
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if v!=vg or v1!=vi:
                if not checked_list[v1]:
                    checked_list[v1]=True
                    Q.appendleft(v1)
                    prev_list[v1]=v
                    min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
    if min_path_list[vg]<min_d:
        flag=True
        min_vi = vi
        min_vg = vg
        min_d = min_path_list[vg]
        min_prev = prev_list
            
#print(min_d_list)
if flag:
    ans = []
    v = min_vg
    while v!=min_vi:
        ans.append(v+1)
        v=min_prev[v]
    ans.append(min_vi+1)
    ans = ans[::-1]
    
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Measured memory_bytes: 59352
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>
#include <vector>
#include <map>
#include <unordered_map>
#include <cstdlib>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
using ll = long long;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    int N, i, r=0, b=0;
    string s;

    cin >> N >> s;

    for(i=0; i<N; i++){
        if(s.at(i)=='R') r++;
        else b++;
    }

    if(r>b) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int main()
{
    int K;
    cin >> K;
    if (K % 2 == 0)
    {
        cout << (K / 2) * (K / 2) << endl;
    }
    else
    {
        cout << (K / 2) * ((K / 2) + 1) << endl;
    }
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)
	arr1, arr2 := make([]int, n), make([]int, n)
	sum1, sum2 :=  make([]int, n), make([]int, n)
	scan(n, arr1); scan(n, arr2)

	sum := 0
	for i := 0; i < n; i++ {
		sum += arr1[i]
		sum1[i] = sum
	}

	sum = 0
	for i := n - 1; i >= 0; i-- {
		sum += arr2[i]
		sum2[i] = sum
	}

	mx := math.MinInt32
	for i := 0; i < n; i++ {
		cur := sum1[i] + sum2[i]
		if cur > mx {
			mx = cur
		}
	}

	fmt.Println(mx)
}

func scan(n int, arr []int)  {
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
}

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

vector<bool> prime_table(int n) {
	vector<bool> prime(n + 1, true);
	if(n >= 0) prime[0] = false;
	if(n >= 1) prime[1] = false;
	for(int i = 2; i * i <= n; i++) {
		if(!prime[i]) continue;
		for(int j = i + i; j <= n; j += i) {
			prime[j] = false;
		}
	}
	return prime;
}

int main() {
	const int n = 100000;
	auto p = prime_table(n);
	set<int> prime;
	rep(i, n){
		if(p[i]) prime.insert(i);
	}
	vector<int> ans;
	for(auto t: prime){
		int tmp = (t+1)/2;
		if(prime.count(tmp)){
			ans.push_back(t);
		}
	}
	sort(all(ans));
	int q;
	cin >> q;
	vector<int> l(q), r(q);
	rep(i, q){
		cin >> l[i] >> r[i];
	}
	rep(i, q){
		int cnt = upper_bound(all(ans), r[i]) - lower_bound(all(ans), l[i]);
		cout << cnt << endl;
	}
	// for(auto t: ans){
	// 	cout << t << endl;
	// }
	return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {
	int n;
	cin >> n;
	vector<pair<long long, int>> v(2*n);
	for(int i = 0; i < n; ++i){
		long long tmp;
		cin >> tmp;
		v[i] = make_pair(tmp, 1);
	}
	for(int i = 0; i < n; ++i){
		long long tmp;
		cin >> tmp;
		v[n+i] = make_pair(tmp, -1);
	}
	
	sort(v.begin(), v.end());
	
	long long ans = 1;
	long long sum = 0;
	for(int i = 0; i < 2*n; ++i){
		if(v[i].second == 1 && sum < 0) ans = (ans * (-sum)) % MOD;
		if(v[i].second == -1 && sum > 0) ans = (ans * sum) % MOD;
		sum += v[i].second;
	}
	
	assert(sum == 0);
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3328
#pragma GCC optimize("Ofast")
  
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <random>
#include <regex>

using namespace std;
  
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(14)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;
constexpr int dy[] = {0,1,0,-1,1,-1,-1,1};
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
 
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class A, class B> inline A updiv(const A a,const B b){ return (a + b - 1) / b; }
template <class A, class B> inline A gcd(const A a,const B b){ return b ? gcd(b,a % b) : a; }
template <class A, class B> inline A lcm(const A a,const B b){ return a / gcd(a,b) * b; }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A,class B> using umap = unordered_map<A,B>;


signed main(void){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;

    vector<int> p(a), q(b), r(c);

    rep(i,a){
        cin >> p[i];
    }

    rep(i,b){
        cin >> q[i];
    }

    rep(i,c){
        cin >> r[i];
    }

    sort(all(p), greater<>());
    sort(all(q), greater<>());

    min_heap<int> pq;

    rep(i,x){
        pq.emplace(p[i]);
    }

    rep(i,y){
        pq.emplace(q[i]);
    }

    rep(i,c){
        if(pq.top() < r[i]){
            pq.pop();
            pq.emplace(r[i]);
        }
    }

    int res = 0;
    while(!pq.empty()){
        res += pq.top();
        pq.pop();
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 4852
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> p;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
 
int main(){
    ll n;
    ll k;
    cin >> n>>k;
    vector<ll> a(n),b(n,1e9);
    rep(i,n){
        cin >> a[i];
    }
    ll des=1;
 
    if(k<1e6){
        rep(i,k){
            des=a[des-1];
        }
        cout << des << endl;
        return 0;
    }
 
    ll dev,offset;
    ll rest;
    for(ll i=1; i<=k; ++i){
        if(b[des-1]==1e9){
            b[des-1]=i;
        }
        else{
            dev= i-b[des-1];
            offset = b[des-1]-1;
            rest = k+1-offset;
            break;
        }
        des=a[des-1];
    }
    int index;
    if(rest%dev==0){
        auto itr=find(b.begin(),b.end(),dev+offset);
        index=distance(b.begin(),itr);
    }
    else{
        auto itr=find(b.begin(),b.end(),rest%dev+offset);
        index=distance(b.begin(),itr);
    }
    cout << index+1 << endl;
    
 
    return 0;
}

Measured memory_bytes: 6424
#include<bits/stdc++.h>
using namespace std;
int main(){
  int S,A,B,C,D;
  cin>>S;
  A=S/1000,B=S/100%10,C=S/10%10,D=S%10;
  char op1,op2,op3;
  if(A+B+C+D==7)op1='+',op2='+',op3='+';
  if(A+B+C-D==7)op1='+',op2='+',op3='-';
  if(A+B-C+D==7)op1='+',op2='-',op3='+';
  if(A+B-C-D==7)op1='+',op2='-',op3='-';
  if(A-B+C+D==7)op1='-',op2='+',op3='+';
  if(A-B+C-D==7)op1='-',op2='+',op3='-';
  if(A-B-C+D==7)op1='-',op2='-',op3='+';
  if(A-B-C-D==7)op1='-',op2='-',op3='-';
  cout<<A<<op1<<B<<op2<<C<<op3<<D<<"=7"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define print(a) cout << (a) << endl; 
typedef long long ll;
const int MOD = 1000000007; 


int main() {
    int x;
    cin >> x;
    int ret = 1000*(x/500) + 5 * ((x%500)/5);
    cout << ret << endl; 
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int64_t i=0; i<(int64_t)(n); i++)
#define all(v) v.begin(), v.end()
//a
int main(){
  string S, T; cin >> S >> T;
  if(S.size()+1 == T.size()){
    rep(i, S.size()){
      if(S[i] != T[i]){
        cout << "No" << endl;
        return 0;
      }
    }
    cout << "Yes" << endl;
    return 0;
  }
  else cout << "No" << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n; cin >> n;
  ll ma = 0;
  ll sum = 0;
  REP(i,n){
      ll tmp ;
      cin >> tmp;
      sum += tmp;
      ma = max(ma, tmp);
  }
  sum -= ma/2;
  cout << sum << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<long long>> vvll;
typedef long double ld;
typedef std::vector<long double> vld;
typedef std::vector<std::vector<long double>> vvld;
using namespace std;
void yesno(bool state);

void Main(){
    ll N;
    cin >> N;
    vll A(N);
    rep(i,N) cin >> A[i];
    ll money = 1000;
    ll kabu = 0;
    for (ll i = 0; i < N-1; i++)
    {
        if(A[i] < A[i+1]){
            ll newkabu = std::floor(money / A[i]);
            kabu += newkabu;
            money -= newkabu * A[i];
        }
        else
        {
            ll loskabu = kabu;
            kabu = 0;
            money += loskabu * A[i];
        }
    }
    money += kabu * A[N-1];
    cout << money << endl;
}

int main(int argc, char const *argv[])
{
    Main();
    return 0;
}

void yesno(bool state){
    if(state)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

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

cur_coin_count = 0
cur_probability = 1

tmp = N
while True:
    if tmp >= K:
        break
    tmp *= 2
    cur_coin_count += 1
    cur_probability /= 2
ret = cur_probability

num = N-1
while num > 0:
    if num * (2 ** cur_coin_count) < K:
        cur_coin_count += 1
        cur_probability /= 2

    ret += cur_probability
    num -= 1
ret /= N
print(ret)    

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

using namespace std;

#define rep(i,n) for(long long int i=0;i<n;i++)
#define rep1(i,n) for(long long int i=1;i<=n;i++)
#define repU(i,bottom,ceiling) for(long long int (i)=(bottom);(i)<=(ceiling);(i)++)
#define repD(i,ceiling,bottom) for(long long int (i)=(ceiling);(i)>=(bottom);(i)--)
#define pub push_back
#define pob pop_back
#define pf printf
#define sf scanf
#define ci(a) cin>>a
#define lco(a) cout<<a<<endl
#define co(a) cout<<a
#define vci(v) for(long long int i=0;i<v.size();i++) cin>>v[i]
#define vco(v) for(long long int i=0;i<v.size();i++){ cout<<v[i]<<' '; } cout<<endl
#define mp make_pair
#define fir first
#define sec second
#define clr(arr) memset((arr),0,sizeof(arr))

typedef long long int ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<double> vb;
typedef vector<vector<double>> vvd;
typedef vector<long long int> vll;
typedef vector<vector<long long int>> vvll;
typedef pair<int,int> pii;

const string alphabet("abcdefghijklmnopqrstuvwxyz");
const vector<pair<int,int>> dir={{0,0},{1,0},{1,1},{0,1},{-1,1},{0,-1},{-1,-1},{0,-1},{1,-1}};
const long double Pi=3.141592653589793238462643383279502884197;
const long double Napier=2.71828182845904523536;
const int Inf=(int)2e9+1e8;
const int Mod=(int)1e9+7;

template<typename T,typename U>                                                   
inline pair<T,U> operator+(const pair<T,U> & l,const pair<T,U> & r) {   
    return {l.fir+r.fir,l.sec+r.sec};                                    
} 

template<typename T,typename U> 
inline pair<T,U> operator-(const pair<T,U> & l,const pair<T,U> & r) {   
    return {l.fir-r.fir,l.sec-r.sec};                                    
} 

template<typename T,typename U>                                                   
inline pair<T,U> operator*(const pair<T,U> & l,const pair<T,U> & r) {   
    return {l.fir*r.fir,l.sec*r.sec};                                    
}

template<typename T,typename U>                                                   
inline pair<T,U> operator/(const pair<T,U> & l,const pair<T,U> & r) {   
    return {l.fir/r.fir,l.sec/r.sec};                                    
}

template<typename T> inline void Swap(T *x,T *y){ T tem=*x; *x=*y; *y=tem; }

inline long long int rem(long long int n,long long int m){
	if(!m) return 0;
	return (n<0?(n%m)+m:(n%m));
}
  
             
/*The main code follows below*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b,c; ci(a>>b>>c);
	int d1=a-b,d2=b-c;
	ci(a>>b>>c);
	if(a-b!=d1||b-c!=d2){ lco("No"); return 0; }
	ci(a>>b>>c);
	if(a-b!=d1||b-c!=d2){ lco("No"); return 0; }
	lco("Yes");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int n;
    cin >> n;
    vector<int> p;
    rep(i, n){
        int x;
        cin >> x;
        p.push_back(x);
    }
    int cnt=0, minim=INT32_MAX;
    rep(i, n){
        int tmp=min(minim, p[i]);
        if(tmp!=minim){
            cnt++;
            minim = tmp;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 4316
import java.text.DecimalFormat;
import java.util.stream.LongStream;
import java.util.stream.IntStream;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        AtCoder problem = new AtCoder(sc);
        problem.solve(out);

        out.flush();
    }

}

class AtCoder {

    int X, Y;

    AtCoder(FastScanner sc) {
        X = sc.nextInt();
        Y = sc.nextInt();
    }

    void solve(PrintWriter out) {
        out.println(X + Y / 2);
    }

}

// https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4
class FastScanner {

    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
            ptr++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 21332
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n; cin>>n;
    vector<int> a(n,0);
    rep(i,n) cin>>a[i];
    rep(i,(n+1)/2){
        if(n==1){
            cout<<a[0]<<endl;
            continue;
        }
        cout<<a[n-1-2*i]<<" ";
    }
    rep(i,n/2){
        if(n%2) cout<<a[1+2*i];
        else cout<<a[2*i];
        if(i!=n/2-1) cout<<" ";
        else cout<<endl;
    }
}

Measured memory_bytes: 2944
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

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

	int A, B, C;
	cin >> A >> B >> C;

	if (A <= C && C <= B)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}

	return 0;
}


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

int main() {
  int n, k;
  cin >> n >> k;
  int m = (n - 1) * (n - 2) / 2;
  if (m < k) {
    cout << -1 << endl;
    return 0;
  }

  vector<pair<int, int>> v;
  for (int i = 0; i < n - 1; i++) v.push_back({i, n - 1});
  int d = m - k;
  for (int i = 0; d > 0 && i < n - 1; i++) {
    for (int j = i + 1; d > 0 && j < n - 1; j++) {
      v.push_back({i, j});
      d--;
    }
  }

  cout << v.size() << endl;
  for (auto e : v) cout << e.first + 1 << ' ' << e.second + 1 << endl;
}


Measured memory_bytes: 384
K = input()
A,B = input().split()
K,A,B = int(K),int(A),int(B)
count = "NG"
box = int(A / K)
for i in range(box,A+1):
    if i * K >= A and i * K <= B:
        count = "OK"
        print("OK")
        break
    i += 1
if count == "OK":
    pass
else:
    print("NG")

Measured memory_bytes: 9136
#!python3

from collections import deque

iim = lambda: map(int, input().rstrip().split())

def calc(dp):
    ans = 0
    dq = deque([[0, 0]])
    #print(dp)
    for i, hi in enumerate(dp):
        j = i
        while dq[-1][1] > hi:
            j, h1 = dq.pop()
            ans = max(ans, (i - j) * h1)

        if dq[-1][1] < hi:
            dq.append([j, hi])

    i = len(dp)
    for j, hi in dq:
        ans = max(ans, (i - j) * hi)
    #print(i, dq, ans)
    return ans

def resolve():
    H, W = iim()

    dp = [0] * W
    dp0 = dp[:]
    ans = 0
    for i in range(H):
        C = list(iim())

        for i, ci in enumerate(C):
            dp[i] = 0 if ci else dp0[i] + 1

        ans = max(ans, calc(dp))
        dp, dp0 = dp0, dp

    print(ans)

if __name__ == "__main__":
    resolve()



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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
	int H, W; cin >> H >> W;
	vector<string> S(H);
	for(int i = 0; i < H; i++) cin >> S[i];
	vector<vector<int>> mapping(H, vector<int>(W));
	for(int i = 0; i < H; i++) {
		int start = 0, goal = 0;
		for(int j = 0; j < W; j++) {
			if(S[i][j] == '#') {
				for(int k = start; k < goal; k++) mapping[i][k] += goal - start;
				start = j + 1; goal = j + 1;
				continue;
			}
			goal++;
			if(j == W - 1) {
				for(int k = start; k < goal; k++) mapping[i][k] += goal - start;
			}
		}
	}
	for(int j = 0; j < W; j++) {
		int start = 0, goal = 0;
		for(int i = 0; i < H; i++) {
			if(S[i][j] == '#') {
				for(int k = start; k < goal; k++) mapping[k][j] += goal - start;
				start = i + 1; goal = i + 1;
				continue;
			}
			goal++;
			if(i == H - 1) {
				for(int k = start; k < goal; k++) mapping[k][j] += goal - start;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) ans = max(ans, mapping[i][j]);
	/*for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			cout << mapping[i][j] << " ";
		}
		cout << endl;
	}*/
	ans--;
	cout << ans << endl;
	return 0;
}

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

int num;
int a[21][21];

int retcost(int Island){
	int x=0;
	for(int i=1;i<=num;i++){
		if(a[Island][i]){
			a[i][Island]=0;
			x=max(x,a[Island][i]+retcost(i));
		}
	}
	return x;
}

int main(void){
	while(cin>>num,num){
		int I1,I2,t,ans,I[num+1]={},Cost=0;
		memset(a,0,sizeof(a));
		for(int i=1;i<num;i++){
			cin>>I1>>I2>>t;
			a[I1][I2]=a[I2][I1]=t;
			I[I1]++,I[I2]++;
			Cost+=t*2;
		}
		for(int i=1;i<=num;i++){
			for(int j=1;j<=num;j++){
				if((I[i]==1||I[j]==1)&&!((i==1&&I[i]==1)||(j==1&&I[j]==1))){
					Cost-=a[i][j]*2;
					a[i][j]=a[j][i]=0;
				}
			}
		}
		ans=Cost-retcost(1);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3016