akhauriyash/Code-Regression huggingface dataset:
//Be Name Khorgraph, Besmellah Rahmane Rahim, In The Name Of God;
//#include<bits/stweight++.h>
#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric>
#include <stdio.h>
#include <string.h>
#include<iomanip>
#include<unordered_map>
#include<unordered_set>
#include <iostream>
#include <fstream>


using namespace std;

const long long N = 1e5 + 5;
long long x[N];
long long ind[N];
long long a[N];
long long d[N];
long long per[N];
long long n, m, k;
vector<long long> graph[N];
vector<long long> cycle[N];
bool mark[N];
long long w[N];
long long cnt_cycle = 0;


struct matrix
{
	long long a[N];
	matrix() 
	{
		for (long long i = 0 ; i < N ; i ++) 
		{
			a[i] = i ;	
		}
	}
	long long& operator [] (long long x)
	{
		return a[x];
	}
	friend matrix operator *(matrix a, matrix b)
	{
		matrix ans;
		for (long long i = 0; i < n; i++) 
		{
			ans[i] = a[b[i]] ;
		}
		return ans;
	}
	void change(long long i, long long j)
	{
		swap(a[i], a[j]);
	}
};

matrix st;

matrix power(matrix a, long long b)
{
	matrix ans;
	while (b) 
	{
		if (b & 1) 
		{
			ans = ans * a;
		}
		a = a * a ;
		b >>= 1 ;
	}
	return ans;
}

void dfs(long long v, long long c)
{
	cycle[c].push_back(v);
	w[v] = c;
	mark[v] = true;
	for (auto u: graph[v])
	{
		if (!mark[u])
		{
			dfs(u, c);
		}
	}
}


int main()
{
	cin >> n;
	for (long long i = 0; i < n; i++)
	{
		cin >> x[i];
		ind[i] = i;
	}
	cin >> m >> k;
	for (long long i = 0; i < m; i++)
	{
		cin >> a[i];
	}
	for (long long i = 0; i < n - 1; i++)
	{
		d[i] = x[i + 1] - x[i];
	}
	// each operation on the ith rabbit means to swap d[i] with d[i + 1]
	for (long long i = 0; i < m; i++)
	{
		graph[a[i] - 2].push_back(a[i] - 1);
		graph[a[i] - 1].push_back(a[i] - 2);
		st.change(a[i] - 1, a[i] - 2);
	}
	for (long long i = 0; i < n - 1; i++)
	{
		if (!mark[i])
		{
			dfs(i, cnt_cycle++);
		}
	}
	st = power(st, k);
	cout << x[0] << endl;
	for (long long i = 0 ; i < n - 1; i++)
	{
		x[i + 1] = x[i] + d[st[i]];
		cout << x[i + 1]  << endl;
	}


}




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

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
    // double a, b, h, m; cin >> a >> b >> h >> m;
    // double x_l, y_l, x_s, y_s;
    // double rad_l, rad_s;
    // double ans;
    // rad_l = (90 - 30 * h + m / 2) * M_PI / 180;
    // rad_s = (90 - 6 * m) * M_PI / 180;
    // x_l = a * cos(rad_l);
    // y_l = a * sin(rad_l);
    // x_s = b * cos(rad_s);
    // y_s = b * sin(rad_s);
    // cout << x_l << "|" << y_l << endl;
    // cout << x_s << "|" << y_s << endl;
    // ans = sqrt(pow(x_l - x_s, 2.0) + pow(y_l - y_s, 2.0));
    // cout << ans << endl;

    int a, b, h, m; cin >> a >> b >> h >> m;
    long double rad = M_PI * 2 * ((long double)h / 12 + (long double)m / 60 / 12 - (long double)m / 60);
    long double rsq = (long double)(a * a + b * b) - (long double)(2 * a * b) * cos(rad);
    printf("%.10Lf\n", sqrt(rsq));
}

Measured memory_bytes: 4060
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] line1 = br.readLine().split(" ");
    int n = Integer.parseInt(line1[0]);
    long d = Long.parseLong(line1[1]);
    long d2 = d * d;
    int answer = 0;
    for(int i = 0; i < n; i++){
      String[] line2 = br.readLine().split(" ");
      long x = Long.parseLong(line2[0]);
      long y = Long.parseLong(line2[1]);
      long distance2 = (x * x) + (y * y);
      if(d2 >= distance2) answer++;
    }
    System.out.println(answer);
  }
}

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

int main() {
    string s, t;
    cin >> s >> t;
    for (int i=s.length()-t.length(); i>=0; i--) {
        int j;
        string tmp;
        for (j=0; j<t.length(); j++)
            if (s[i+j] != t[j] && s[i+j] != '?')
                break;
        if (j == t.length()) {
            for (j=0; j<s.length(); j++)
                if (s[j] == '?')
                    s[j] = 'a';
            for (j=0; j<i; j++)
                cout << s[j];
            for (; j<i+t.length(); j++)
                cout << t[j-i];
            for (; j<s.length(); j++)
                cout << s[j];
            cout << endl;
            return 0;
        }
    }
    cout << "UNRESTORABLE" << endl;
}

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

bool isSquareNumber(int num) {
  for (int i=1; i<=sqrt(num); i++) {
    if (i*i==num) return true;
  }
  return false;
}

int atoi(char s[])
{
    int i, n;
    n = 0;
    for (i = 0; s[i] >= '0' && s[i] <= '9'; ++i)
        n = 10 * n + (s[i] - '0');
    return n;
}

int main() {
  string a, b; cin >> a >> b;
  string s = a + b;
  int x = atoi(s.c_str());
  if (isSquareNumber(x)) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

int main () {
    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    vector<int> alpha_count(alphabet.size());
    string s;
    // while(flag) {
    //     if(getline(cin, s)){
    //         for (int i = 0; i < s.size(); i++) {
    //             for (int j = 0; j < alphabet.size(); j++) {
    //                 if (tolower(s[i]) == alphabet[j]) {
    //                     alpha_count[j] += 1;
    //                 }
    //             }
    //         }
    //     }
    // }
    while(true) {
        cin >> s;
        if (cin.eof()) break;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < alphabet.size(); j++) {
                if (tolower(s[i]) == alphabet[j]) {
                    alpha_count[j] += 1;
                }
            }
        }
    }

    for (int i = 0; i < alphabet.size(); i++) {
        printf("%c : %d\n", alphabet[i],alpha_count[i]);
    }
    return 0;
}


Measured memory_bytes: 3228
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;

int main(){
  int n, m;cin>>n>>m;
  string s;cin>>s;
  s[m-1] += 'a' - 'A';
  cout << s << endl;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
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; }
 
ll MOD = 1000000007;
ll INF =1<<30;
ll dp[110][100100];
 
 
int main(){
    int n ;
    cin >> n;
    if ( n%1000==0){
        cout<<0 <<endl;
        return 0;
    }
    cout << 1000-n%1000 <<endl;
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(void){
  int X;
  int cake,donatu;
  int amari;
  int i;

  scanf("%d",&X);
  scanf("%d",&cake);
  scanf("%d",&donatu);

  amari = X - cake;

  for(i=0;i<1000;i++){
    amari -= donatu;
    if(amari<0){printf("%d",amari+donatu);break;}
  }

  return 0;
}


Measured memory_bytes: 128
//Sum of Integers
#include<bits/stdc++.h>
using namespace std;

int depth, s, n;

void solve(int d, int x, int sum){
  if(d==0 && sum==s){n++; return;}
  for(int i=x+1; i<10; i++){
    solve(d-1, i, sum+i);
  }
}

int main(){

  while(cin>>depth>>s){
    if(depth==0 && s==0)break;
    n=0;
    solve(depth, -1, 0);
    cout<<n<<endl;
  }
  return 0;
}

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

int main() {
	// your code goes here
	int n,m,cans,ans;
	string s,t;
	cin>>s>>t;
	n=s.length(),m=t.length();
	for(int i=0;i<=n-m;i++){
		cans=0;
		for(int j=i;j<i+m;j++){
			if(s[j]!=t[j-i])
				cans++;
		}
		if(!i||ans>cans)
			ans=cans;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3624
import sys
sys.setrecursionlimit(10**9)

def dfs(i):
    if distance[i] != -1:
        return distance[i]
    ans = 0
    for node in graph[i]:
        ans = max(ans, dfs(node) + 1)
    distance[i] = ans
    return ans

n, m = map(int, input().split())

graph = [[] for i in range(n)]
distance = [-1 for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)

ans = 0
for i in range(n):
    ans = max(ans, dfs(i))

print(ans)

Measured memory_bytes: 152924
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
        checked {
#if DEBUG
            MyDebugger.Test(process, "../TextFile1.txt");
            //TestCaseMaker.MakeTestCase1("../TextFile2.txt");
            //MyDebugger.Test(process, "../TextFile2.txt");
#else
            object ret = process(new StreamReader(Console.OpenStandardInput()));
            Console.WriteLine(ret);
#endif
        }
    }

    static object process(TextReader input) {
        var n = int.Parse(input.ReadLine());
        var ll = ToIntArray(input.ReadLine(), n);

        long x = 0;

        for(int i=0; i<n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    long a = ll[i];
                    long b = ll[j];
                    long c = ll[k];

                    if(a==b || b==c || a==c) continue;

                    long z;

                    if(a < b) {
                        z = a;
                        a = b;
                        b = z;
                    }

                    if(a < c) {
                        z = a;
                        a = c;
                        c = z;
                    }

                    if(b+c > a) {
                        x++;
                    }
                }
            }
        }

        return x;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 27448
#include <iostream>
using namespace std;
string str;
signed main() {
	cin >> str;
	for (int i = 1; i < str.length(); ++i)
		if (str[i - 1] == 'A' && str[i] == 'C')
			return puts("Yes"), 0;
	return puts("No"), 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int n;
    cin >> n;

    constexpr ll M = (ll)1e+18;
    ll r = 1;
    int b = 0;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;

        if (a == 0) {
            cout << 0 << endl;
            exit(0);
        }
        if (!b && a > (M + r - 1) / r) b = 1;
        r *= a;
        if (r > M) b = 1;
    }

    if (b) {
        cout << -1 << endl;
    } else {
        cout << r << endl;
    }

    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
string s;
cin >> s;
bool f=true;
if(s[0]==s[1] && s[1]==s[2]) cout << "No" << endl;
else cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
s = input()
t = input()

if s[0] == t[0] and s[1] == t[1] and s[2] == t[2]:
  print(3)
elif (s[0] == t[0] and s[1] == t[1]) or (s[1] == t[1] and s[2] == t[2]) or (s[2] == t[2] and s[0] == t[0]):
  print(2)
elif s[0] == t[0] or s[1] == t[1] or s[2] == t[2]:
  print(1)
else:
  print(0)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define dbg(x) cout << #x << " = " << x << endl
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl

#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define gap cout<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())



int main(){
    int val[4];
    int n,m;
    bool flag=false;
    cin>>n>>m;
    fo(i,4) val[i]=-1;
    int s,c;
    fo(i,m){
        cin>>s>>c;
        
        if(s==1&&c==0&&n!=1) flag=true;
        else if(val[s]>=0&&c!=val[s]) flag=true;
        else val[s]=c;


    }
    int ans=0;
    int tmp=2;
    if(flag) cout<<-1<<endl;
    else{
        if(n==1){
            if(val[1]==-1) ans=0;
            else ans=val[1];
        }
        else if(n==2){
            if(val[1]==-1) ans=ans+10;
            else ans+=val[1]*10;
            if(val[2]==-1) ans+=0;
            else ans+=val[2];

        }
        else if(n==3){
            if(val[1]==-1) ans=ans+100;
            else ans+=val[1]*100;
            if(val[2]==-1) ans+=0;
            else ans+=val[2]*10;
            if(val[3]==-1) ans+=0;
            else ans+=val[3];
            
        }
        cout<<ans<<endl;
    }
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define null NULL
#define mp make_pair
#define pb(a) push_back(a)
#define sz(a) ((int)(a).size())
#define all(a) a.begin() , a.end()
#define fi first
#define se second
#define relaxMin(a , b) (a) = min((a),(b))
#define relaxMax(a , b) (a) = max((a),(b))
#define SQR(a) ((a)*(a))
#define PI 3.14159265358979323846
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

const int MAX = 20000000;

int main(){
  ll a, b, c;
  ll step = 0;

  cin >> a >> b >> c;

  while(true){
    if(step > MAX) break;
    if((a & 1) || (b & 1) || (c & 1)) break;
    ll na = (b + c) >> 1,
       nb = (a + c) >> 1,
       nc = (a + b) >> 1;
    a = na, b = nb, c = nc;
    ++step;
  }

  if(step > MAX) cout << "-1\n";
  else cout << step << '\n';

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define N 2000000

int A[N], B[N], C[10001];

void counting_sort(int k, int n){
  int i;
  for(i=0;i<=k;i++) C[i] = 0;
  for(i=0;i<n;i++) C[A[i]]++;
  for(i=1;i<=k;i++) C[i] += C[i-1];
  for(i=n-1;i>=0;i--){
    B[C[A[i]]-1] = A[i];
    C[A[i]]--;
  }
}

main(){
  int n, k = 0, i;
  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf("%d", &A[i]);
    if(k < A[i]) k = A[i];
  }
  counting_sort(k, n);
  printf("%d", B[0]);
  for(i=1;i<n;i++) printf(" %d", B[i]);
  printf("\n");
  return 0;
}

Measured memory_bytes: 15000
import Control.Monad
import Control.Applicative
import Data.List
import qualified Data.Map as Map
import Data.Array
import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import qualified Data.Set as Set
import qualified Data.Sequence as Sq
import qualified Data.IntMap as IMap
import Data.Sequence (ViewL(..),ViewR(..),(><),(<|),(|>),Seq)

bsreadInt :: BC.ByteString -> Int
bsreadInt = fst . fromJust . BC.readInt

main = do
    n <- readLn :: IO Int
    s <- getLine
    
    if elem 'Y' s then putStrLn "Four"
                  else putStrLn "Three"

Measured memory_bytes: 508
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <bitset>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using lint = long long;
using namespace std;

const int MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    lint H[100010];
    for (int i = 0; i < N; i++) {
        cin >> H[i];
    }

    int res = 0;
    int c = 0;

    for (int i = 1; i < N; i++) {
        if (H[i-1] >= H[i]) {
            c++;
        }
        else {
            res = max(res, c);
            c = 0;
        }
    }
    res = max(res, c);

    cout << res << endl;
    return 0;
}


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

int X[ 30 ];
char S[ 30 ];

int main( int argc, char *argv[] )
{
int i;
char C;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> S;

	i = 0;
	C = S[ i ];
	while( C != '\0' )
	{
		X[ C - 'a' ]++;
		if( X[ C - 'a' ] > 1 )
		{
			cout << "no" << endl;

			return 0;
		}

		i++;
		C = S[ i ];
	}

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




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define fcout cout << fixed << setprecision(10)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acos(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<PII>;
using VTIII = vector<TIII>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a == b)){ a=b; return true; } return false; }
template<typename T> bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a == b)){ a=b; return true; } return false; }


int N;
VI P, Q, v;


signed main(){
    cin >> N;
    P = Q = VI(N);
    rep(i, 0, N) cin >> P[i];
    rep(i, 0, N) cin >> Q[i];

    v = VI(N);
    iota(ALL(v), 1LL);

    int a = -1, b = -1;
    int i = 0;
    do {
        if(P == v) a = i;
        if(Q == v) b = i;
        i++;
    } while(next_permutation(ALL(v)));

    cout << abs(a-b) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
constexpr auto mod = 1000000007;
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}

//combination(Nが小さい時はこれを使う)
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
int COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}

//繰り返し二乗法（Nが大きい時の場合のcombination)
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= (i % mod); res %= mod;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

//debug処理
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//UnionFind
class UnionFind {
protected:
	int* par, * rank, * size;
public:
	UnionFind(unsigned int size) {
		par = new int[size];
		rank = new int[size];
		this->size = new int[size];
		rep(i, size) {
			par[i] = i;
			rank[i] = 0;
			this->size[i] = 1;
		}
	}
	int find(int n) {
		if (par[n] == n)return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m)return;
		if (rank[n] < rank[m]) {
			par[n] = m;
			size[m] += size[n];
		}
		else {
			par[m] = n;
			size[n] += size[m];
			if (rank[n] == rank[m])rank[n]++;
		}
	}
	bool same(int n, int m) {
		return find(n) == find(m);
	}
	int getsize(int n) {
		return size[find(n)];
	}
};
int d[2222][2222];
int ans[2222];
signed main() {
	int n, x, y;
	cin >> n >> x >> y;
	x--, y--;
	rep(i, n - 1) {
		for (int j = i + 1; j < n; j++) {
			d[i][j] = min(j - i, abs(i - x) + abs(j - y) + 1);
			ans[d[i][j]]++;
		}
	}
	for (int i = 1; i <= n - 1; i++)cout << ans[i] << endl;
	ggr
}


Measured memory_bytes: 35072
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    vector<int> x(N);
    for (auto& i : x) cin >> i;
    vector<int> v;
    for (int l = 0; l <= N - K; l++) {
        int r = K - 1 + l;
        v.push_back(min(abs(x[l]) + abs(x[r] - x[l]), abs(x[r]) + abs(x[l] - x[r])));
    }
    cout << *min_element(v.begin(), v.end()) << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define rush() int T;scanf("%d",&T);while(T--)
#define mm(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define pf(a) printf("%d\n",a)
#define pf2(a,b) printf("%d %d\n",a,b)
#define p_f(a) printf("%d ",a)
#define fi first
#define se second
#define db double
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const db eps=1e-9;
int b[5];
int main()
{
	int x;
	rep(i,1,2)cin>>x,b[x]=1;
	rep(i,1,3)if(!b[i])pf(i);
    return 0;
}


Measured memory_bytes: 256
use std::cmp;
use std::io;

#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

const SPLIT_DELIMITER: char = ' ';
#[allow(dead_code)]
fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}

fn main() {
    let s1 = str2vec(&input_line_str());
    let s2 = str2vec(&input_line_str());

    let mut dp: Vec<Vec<usize>> = vec![vec![0; s2.len() + 1]; s1.len() + 1];

    for i in 0..s1.len() {
        for j in 0..s2.len() {
            if s1[i] == s2[j] {
                dp[i + 1][j + 1] = cmp::max(cmp::max(dp[i][j] + 1, dp[i + 1][j]), dp[i][j + 1]);
            } else {
                dp[i + 1][j + 1] = cmp::max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }
    let mut out = String::new();

    let (mut x, mut y): (usize, usize) = (s1.len(), s2.len());
    while dp[x][y] != 0 {
        if dp[x][y - 1] == dp[x][y] {
            y -= 1;
        } else if dp[x - 1][y] == dp[x][y] {
            x -= 1;
        } else {
            out.push_str(&s1[x - 1].to_string());
            x -= 1;
            y -= 1;
        }
    }
    println!("{}", out.chars().rev().collect::<String>());
}

Measured memory_bytes: 90364
#include<bits/stdc++.h>
#include <iomanip>
#include <math.h>
#define M 10000001
#define MAX 10000000000000010
#define mod 1000000007
#define ss second
#define ff first
#define ll long long int
#define pb push_back
#define ld double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

int main()
{
	ll n;
	cin>>n;
	ll x[n];
	for(int i=0;i<n;i++)
		cin>>x[i];
	ll ans = -1,mn = 0;
	for(int i=0;i<=100;i++)
	{
		ll temp = 0;
		for(int j=0;j<n;j++)
		{
			temp += (x[j]-i)*(x[j]-i);
		}
		if(ans == -1)
		{
			ans = i;
			mn = temp;
		}
		else if(mn>temp)
		{
			mn = temp;
			ans = i;
		}
	}
	cout<<mn<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<assert.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;
const int mod=1e9+7;

const int N=2e5+100;

int qpow(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=1LL*ans*x%mod;
		x=1LL*x*x%mod;y>>=1;
	}
	return ans;
}

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

namespace io {
	const int L=(1<<21)+1;
	char ibuf[L],*iS,*iT,obuf[L],*oS=obuf,*oT=obuf+L-1,c,st[55];int f,tp;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline void flush() {
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	inline void putc(char x) { *oS++=x; if (oS==oT) flush(); }
	template<class I> inline void gi(I&x) {
		for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
		for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15); x*=f;
	}
	template<class I> inline void print(I x) {
		if (!x) putc('0');
		if (x<0) putc('-'),x=-x;
		while (x) st[++tp]=x%10+'0',x/=10;
		while (tp) putc(st[tp--]);
	}
	inline void gs(char*s, int&l) {
		for (c=gc();c<'a'||c>'z';c=gc());
		for (l=0;c<='z'&&c>='a';c=gc()) s[l++]=c;
		s[l]=0;
	}
	inline void ps(const char*s) { for (int i=0,n=strlen(s);i<n;i++) putc(s[i]); }
	struct IOFLUSHER{ ~IOFLUSHER() { flush(); } } _ioflusher_;
};
using io::putc;
using io::gi;
using io::gs;
using io::ps;
using io::print;

int f[N];
int main()
{
	int n,i,x,ans=0;
	gi(n);
	for (i=1;i<=n;i++) {
		gi(x);
		upmax(ans,f[x]=f[x-1]+1);
	}
	print(n-ans);
	return 0;
}


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


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> pref(n);
    vector<int> suf(n);
    for (int i = 0; i < n; ++i) {
        pref[i] ^= a[i];
        if (i) {
            pref[i] ^= pref[i - 1];
        }
    }
    for (int i = 0; i < n; ++i) {
        suf[n - i - 1] ^= a[n - i - 1];
        if (i) {
            suf[n - i - 1] ^= suf[n - i];
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i && i + 1 < n) {
            cout << (pref[i - 1] ^ suf[i + 1]);
        }
        else if (i && i == n - 1) {
            cout << pref[i - 1];
        }
        else {
            cout << suf[i + 1];
        }
        cout << " \n"[i == n - 1];
    }
    return 0;
}



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

int main(void){
  int n; cin >> n;
  int a[n+1],b[n];
  rep(i,n+1) cin >> a[i];
  rep(i,n) cin >> b[i];
  ll sum = 0;
  int rest;
  if(a[0] <= b[0]){
    sum += a[0];
    rest = b[0] - a[0];
  }
  else{
    sum += b[0];
    rest = 0;
  }
  for(int i = 1; i < n+1; i++){
    if(i == n){
      if(rest >= a[i]){
        sum += a[i];
      }
      else{
        sum += rest;
      }
    }
    else if(rest>= a[i]){
      sum += a[i];
      rest = b[i];
    }
    else if(rest + b[i] >= a[i]){
      sum += a[i];
      rest = rest + b[i] - a[i];
    }
    else{
      sum += rest + b[i];
      rest = 0;
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main()
{
	ll H, W; cin >> H >> W;
	char a[100][100] = {};

	rep(i, 0, H) {
		rep(j, 0, W) {
			cin >> a[i][j];
		}
	}
	rep(j, 0, W + 2) {
		cout << "#";
	}
	cout << endl;

	rep(i, 0, H) {
		rep(j, 0, W) {
			if (j == 0)cout << "#";
			cout << a[i][j];
			if (j == W - 1)cout << "#";
		}
		cout << endl;
	}

	rep(j, 0, W + 2) {
		cout << "#";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

class B
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		var h = Read();
		var a = Read();
		var b = Read();
		Console.WriteLine(new int[h[2]].Select(_ => Read()).Select(v => a[v[0] - 1] + b[v[1] - 1] - v[2]).Append(a.Min() + b.Min()).Min());
	}
}


Measured memory_bytes: 57016
#include<iostream>
#include<algorithm>
#include<string>
#include<numeric>
#include<vector>
#include<map>
using namespace std;

int n;
long long m;
map<int,int> mp;

int main(){
  cin >> n >> m;
  pair<long long, int> yp[m];
  pair<long long, int> yi[m];
  pair<int, string> ia[m];
  for (int i=0;i<m;i++){
    cin >> yp[i].second >> yp[i].first;
    yi[i].first = yp[i].first;
    yi[i].second = i;
  }
  sort(yp,yp+m);
  sort(yi,yi+m);
  long long ans;
  string ansstr;
  for (int i=0;i<m;i++){
    auto itr = mp.find(yp[i].second);
    if(itr != mp.end()) {
      mp[yp[i].second] += 1;
    } else {
      mp[yp[i].second] = 1;
    }
    ans = yp[i].second*1e6+mp[yp[i].second];
    ansstr = to_string(ans);
    while(ansstr.size() != 12){
      ansstr = "0"+ansstr;
    }
    ia[i].first = yi[i].second;
    ia[i].second = ansstr;
  }
  sort(ia,ia+m);
  for (int i=0;i<m;i++){
    cout << ia[i].second << endl;
  }
  return 0;
}


Measured memory_bytes: 15488
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

class LCA {
  vector<vector<int>> par;
  vector<int> dep;
  void dfs(int now, int prev, vector<vector<int>> &to) {
    if (prev < 0)
      dep[now] = 0;
    else {
      par[now][0] = prev;
      dep[now] = dep[prev] + 1;
    }
    for (auto next : to[now]) {
      if (next == prev)
        continue;
      dfs(next, now, to);
    }
  }
public:
  LCA(vector<vector<int>> &to, int root = 0) {
    int n = to.size(), lg = 1;
    while (1 << lg < n) lg++;
    par.resize(n, vector<int>(lg, -1));
    dep.resize(n);
    dfs(root, -1, to);
    for (int i = 1; i < lg; i++) {
      for (int j = 0; j < n; j++) {
        if (par[j][i-1] < 0)
          par[j][i] = -1;
        else
          par[j][i] = par[par[j][i - 1]][i - 1];
      }
    }
  }
  int query(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int diff = dep[x] - dep[y], lg = par[x].size();
    for (int i = 0; i < lg; i++) {
      if (diff >> i & 1)
        x = par[x][i];
    }
    if (x == y) return x;
    for (int i = lg-1; i >= 0; i--) {
      if (par[x][i] != par[y][i]) {
        x = par[x][i];
        y = par[y][i];
      }
    }
    return par[x][0];
  }
};

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> to(n);
  rep(i, n) {
    int k;
    cin >> k;
    rep(j, k) {
      int c;
      cin >> c;
      to[i].push_back(c);
      to[c].push_back(i);
    }
  }
  LCA lca(to);
  int q;
  cin >> q;
  rep(query, q) {
    int u, v;
    cin >> u >> v;
    cout << lca.query(u, v) << '\n';
  }
  return 0;
}


Measured memory_bytes: 22136
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e5+5;
int n, p[N], s[N], top, f[N], g[N];
int64 ans;
int main()
{
    n = read(); 
    for(int i = 1; i <= n; ++i) p[i] = read();
    top = 0;
    for(int i = 1; i <= n; ++i) 
    {
        while(top&&p[s[top]] > p[i]) --top;
        f[i] = i-s[top], s[++top] = i;
    }
    top = 0; s[0] = n+1;
    for(int i = n; i; --i)
    {
        while(top&&p[s[top]] > p[i]) --top;
        g[i] = s[top]-i, s[++top] = i;
    }
    for(int i = 1; i <= n; ++i) ans += 1ll*f[i]*g[i]*p[i];
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 3328
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>
#include <string>
#include <complex>
using namespace std;

#define INT_max 2147483647


typedef long long ll;
typedef long double ld;


char change(char x){
	if(x == '9') return '1';
	return x+1;
}


int main(){
	int mod = 998244353;
	int N,S;
	cin>>N>>S;
	vector<ll> num(S+1,0);
	num[0] = 1;
	ll ans = 0;
	for(int i = 0;i < N;i++){
		int t;
		cin>>t;
		for(int j = S;j >= t;j--){
			num[j] += num[j-t];
			num[j] %= mod;
		}
		num[0]++;//这个表示的是另一个起点
		ans += num[S];
		ans %= mod;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int h, w;
  cin >> h >> w;
  char c[h + 1][w + 1];
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> c[i][j];
    }
  }

  for (int i = 1; i <= 2 * h; i++) {
    for (int j = 1; j <= w; j++) {
      cout << c[(i + 1) / 2][j];
    }
    cout << endl;
  }
  return 0;
}

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

int main(void)
{
	int S, a, b;
	cin >> S;

	a = S / 100;
	b = S % 100;

	if (12 < a && a < 100 || a == 0) {
		if (0 < b && b < 13) cout << "YYMM" << endl;
		else cout << "NA" << endl;
	} else if (0 < a && a < 13) {
		if (0 == b || 12 < b && b < 100) cout << "MMYY" << endl;
		else cout << "AMBIGUOUS" << endl;
	}

	return 0;
}

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

const int MAX_N = 1e5 + 10;
int N, bit[MAX_N + 10];

// 1 < x <= i
int sum (int i){
    int s = 0;
    while(i > 0){
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add (int i, int x){
    while(i <= N){
        bit[i] += x;
        i += i & -i;
    }
}

int main(){
    int Q;
    cin >> N >> Q;
    for (int i = 0; i < Q; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 0){
            add(b, c);
        }else{
            cout << sum(c) - sum(b-1) << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3492
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>

using namespace std;
long long MOD = 1000000007LL;
template<class T>
T gcd(T x, T y) {
	return y ? gcd(y, x % y) : x;
}

template<class T>
vector<T> enum_div(T n) {
	vector<T> ret;
	for (T 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;
}

template<class T>
map<T, int> prime_factorization(T n) {
	map<T, int> ret;

	for (long long i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}

	if (n != 1)ret[n] = 1;
	return ret;
}

template<class T>
long long C(T n, T r) {
	static map<pair<T, T>, long long> _map;
	if (n < r) return 0;

	if (n == r || r == 0) {
		_map[make_pair(n, r)] = 1ll;
	}
	else if (_map[make_pair(n, r)] == 0) {
		_map[make_pair(n, r)] = (C(n - 1, r) + C(n - 1, r - 1));
	}

	_map[make_pair(n, r)] %= MOD;
	return _map[make_pair(n, r)];
}

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

	return 0;
}

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

#define For(i, j, k) for (register int i = j; i <= k; ++ i)
#define Forr(i, j, k) for (register int i = j; i >= k; -- i)

using namespace std;

inline int read() {
	int x = 0, p = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') p = -1;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x * p;
}

inline void File() {
	freopen("pyramid.in", "r", stdin);
	freopen("pyramid.out", "w", stdout);
}

const int N = 2e6 + 10;
int a[N], t[N], n, ans, tt;

inline bool check(int x) {
	For(i, 1, n) t[i] = a[i] <= x;

	for (register int i = 0, x, y; i < tt - 1; ++ i) {
		x = tt - i, y = x + 1;
		if (t[x] == 1 && t[y] == 1) return true;
		if (t[x] == 0 && t[y] == 0) return false;

		x = tt + i, y = tt + i + 1;
		if (t[x] == 1 && t[y] == 1) return true;
		if (t[x] == 0 && t[y] == 0) return false;
	}

	return t[1];
}

int main() {

	n = read(), tt = n, n = 2 * n - 1;
	For(i, 1, n) a[i] = read();

	for (int l = 1, r = n; l <= r; ) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}

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


Measured memory_bytes: 5120
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i = 0; i , (n); ++i)
using ll = long long;
using namespace std;
int sum(int n) {
    if (n == 0) {
        return 0;
    }

    int s = sum(n - 1);
    return s + n;
}
int main() {
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D;
    E = max(A, C);
    F = min(B, D);
  if(F-E>0){
    cout << F - E;
  }
  else{
 	cout<<0;
  }
}


Measured memory_bytes: 3532
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

template<class T>
struct Vec2
{
	Vec2(){}
	Vec2(T _x, T _y) : x(_x), y(_y) {}

	Vec2 operator+(const Vec2& rhs) const { return Vec2(x + rhs.x, y + rhs.y); }
	Vec2 operator-(const Vec2& rhs) const { return Vec2(x - rhs.x, y - rhs.y); }
	Vec2 operator*(T s) const { return Vec2(x*s, y*s); }
	T dot(const Vec2& rhs) const { return x*rhs.x + y*rhs.y; }
	T cross(const Vec2& rhs) const { return x*rhs.y - y*rhs.x; }
	T sqlength() const { return x*x + y*y; }
	bool operator<(const Vec2& rhs) const
	{
		if (x != rhs.x) return x < rhs.x;
		return y < rhs.y;
	}

	T x;
	T y;
};

typedef Vec2<double> VecD;

template<class T>
T cross(const Vec2<T> &O, const Vec2<T> &A, const Vec2<T> &B)
{
	return (A - O).cross(B - O);
}

int main()
{
	int N;
	scanf("%d", &N);

	static VecD P[80000];
	int iMinY = 0, iMaxY = 0;
	for (int i = 0; i < N; i++) {
		scanf("%lf%lf", &P[i].x, &P[i].y);
		if (P[i].y > P[iMaxY].y) {
			iMaxY = i;
		}
		if (P[i].y < P[iMinY].y) {
			iMinY = i;
		}
	}

	int i = iMaxY, j = iMinY;
	double diameter = (P[iMaxY] - P[iMinY]).sqlength();
	do {
		int i2 = (i + 1) % N, j2 = (j + 1) % N;
		double aadVecDir[2][2] = { 0 };
		VecD dir0 = P[i2] - P[i];
		VecD dir1 = P[j2] - P[j];
		if (dir0.cross(dir1) > 0) {
			j = j2;
		}
		else {
			i = i2;
		}

		double dDist = (P[i] - P[j]).sqlength();
		if (dDist > diameter) {
			diameter = dDist;
		}
	} while (i != iMaxY || j != iMinY);

	printf("%.10lf\n", sqrt(diameter));
	return 0;
}


Measured memory_bytes: 3972
# -*- coding: utf-8 -*-

# そのまま入力文字列の入力
# 2つの入力を空白で分割し、数値化
n, k = map(int, input().split())

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

count = 0
h_sorted = sorted(hn)
h_sorted.reverse()

for h in h_sorted:
    if k <= h:
        count = count + 1
    else:
        break

print(count)

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

signed main() {
    ll N,M;
    cin>>N>>M;
    vector<ll> L(M),R(M),D(M);
    vector<vector<PLL>> edges(N+1); // {next index, cost}
    rep(i,0,M){
        cin>>L[i]>>R[i]>>D[i];
        edges[L[i]].push_back(PLL(R[i], D[i]));
        edges[R[i]].push_back(PLL(L[i], -D[i]));
    }
    vector<bool> used(N+1, false);
    vector<ll> v(N+1, 0);
    rep(i,1,N+1){
        if (used[i])
            continue;
        queue<PLL> q;
        q.push(PLL(i, 0)); // {next index, value}
        while(q.size()>0){
            ll id = q.front().first;
            ll val = q.front().second;
            q.pop();
            if (!used[id]){
                v[id] = val;
                used[id] = true;
                for (auto e: edges[id]) {
                    // printf("i=%d id=%d next id=%d val=%d\n",i,id,e.first, val + e.second);
                    q.push(PLL(e.first, val + e.second));
                }
            } else {
                if (v[id] != val){
                    cout<<"No"<<endl;
                    // printf("i=%d v[%d]=%d, val=%d\n", i, id, v[id], val);
                    return 0;
                }
            }
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 22384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    rep(i, 0, s.size()) {
        int x = s[i] - 'A' + n;
        x %= 26;
        s[i] = (char)('A' + x);
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int H = sc.nextInt();
            int W = sc.nextInt();
            if (H == 0 && W == 0) {
                break;
            }
            for (int k = 0; k < W; k++) {
                System.out.printf("#");
            }
            System.out.printf("\n");
            for (int i = 0; i < H - 2; i++) {
                System.out.printf("#");
                for (int j = 0; j < W - 2; j++) {
                    System.out.printf(".");
                }
                System.out.printf("#\n");
            }
            for (int k = 0; k < W; k++) {
                System.out.printf("#");
            }
            System.out.printf("\n\n");
        }
    }
}


Measured memory_bytes: 56108
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
#define fori(s,n) for(ll i=s;i<=n;i++)
#define ford(s,n) for(int i=n;i>=s;i--)
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define TEST(t) for(int T=1;T<=t;T++)
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,i;
    ll f=0;
    cin>>n;
    for(i=1;i<=n;i++){
       if((i%3==0)||(i%5==0))
         continue;
       else f+=i;
    }
 	 cout<<f;
    return 0;
}


Measured memory_bytes: 3640
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>
#include <cassert>

using namespace std;
typedef long long ll;

int main(){
   int N;
   cin >> N;
   int a[N];
   for (int i = 0; i < N; i++)
   {
      cin >> a[i];
   }
   sort(a,a+N);
   if(a[N-1]-a[0]>=2){
      cout << "No" << endl;
   }
   else{
      int n=0;
      int m=N;
      for(int i = 0 ; i< N; i++){
         if(a[i]==a[0]){
            n++;
            m--;
         }
      }
      if(m==0){
         if(N/2>=a[0]){
            cout <<"Yes"<< endl;
         }
         else if(a[0]==N-1){
            cout <<"Yes"<< endl;
         }
         else{
            cout <<"No"<< endl;
         }
      }
      else if(m==1){
         cout <<"No" << endl;
      }
      else{
         if(n-1+m/2>=a[0]&&a[0]>=n){
            cout << "Yes"<<endl;
         }
         else{
            cout <<"No"<<endl;
         }
      }
   }
   
   return 0;
}


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

signed main(){
    int N;cin>>N;
    vector<int> A(N);
    for(int i=0;i<N;i++)cin>>A[i];
    for(int k=0;k<N;k++){
        if(k)cout<<" ";cout<<A[k];
    }
    cout<<endl;
    for(int i=1;i<N;i++){
        int v=A[i];
        int j=i-1;
        while(j>=0&&A[j]>v){
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=v;
        for(int k=0;k<N;k++){
            if(k)cout<<" ";cout<<A[k];
        }
        cout<<endl;
    }
}



Measured memory_bytes: 3076