akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main()
{
	int i,n,s[1024],p[1024],q[1024],r[1024],Q,R,P,C,m;
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		for(i=0;i<n;i++){
			scanf("%d%d%d%d",&s[i],&p[i],&q[i],&r[i]);
		}
		scanf("%d%d%d%d",&P,&Q,&R,&C);
		m=1;
		for(i=0;i<n;i++){
			if(p[i]<=P&&q[i]<=Q&&r[i]<=R&&4*p[i]+9*q[i]+4*r[i]<=C){
				printf("%d\n",s[i]);
				m=0;
			}
		}
		if(m){
			printf("NA\n");
		}
	}
	return 0;
}

Measured memory_bytes: 2704
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<map>
#include<set>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<30
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
int counter[140],sum[140];
//this behaves as if this were counting sort

int calc(int c,int n){
  int cnt = 0;
  n--;
  for(int i=c;i>=1;i--){
    cnt += n;
    n--;
  }
  return cnt;
}

int main(){
  int n,S,r,mex;
  while(true){
    cin >> n >> S;
    if(n+S == 0)break;
    mex = 0;
    for(int i=0;i<140;i++){
      counter[i] = sum[i] = 0;
    }
    for(int i=0;i<n;i++){
      cin >> r;
      mex = mex<r?r:mex;
      counter[r]++; 
    }

    for(int i=mex;i>=0;i--){
      sum[i] = counter[i]+sum[i+1];
    }



    int cnt = 0;
    for(int i=0;i<=mex;i++){
      if(counter[i] == 0)continue;
      cnt += S-i+1<=i?calc(counter[i],sum[i]):counter[i]*sum[1+S-i];
    }
    cout << cnt << endl;

  }
return 0;
}

Measured memory_bytes: 1160
import sys
sys.setrecursionlimit(10 ** 7)


def resolve():
    class Node:
        def __init__(self, parent, left, right):
            self.parent = parent
            self.left = left
            self.right = right
            self.height = None

        def get_type(self):
            if self.parent == -1:
                return "root"
            elif self.left == -1 and self.right == -1:
                return "leaf"
            else:
                return "internal node"

        def get_depth(self):
            if self.parent == -1:
                return 0
            else:
                depth = 1
                t = Nodes[self.parent]
                while t.parent != -1:
                    t = Nodes[t.parent]
                    depth += 1
                return depth

        def get_height(self):
            h_left = 0
            h_right = 0
            if self.left != -1:
                h_left = Nodes[self.left].get_height() + 1
            if self.right != -1:
                h_right = Nodes[self.right].get_height() + 1
            self.height = max(h_left, h_right)
            return self.height

        def get_degree(self):
            degree = 0
            if self.left != -1:
                degree += 1
            if self.right != -1:
                degree += 1
            return degree

        def get_sigling(self):
            if self. parent == -1:
                return -1
            p = Nodes[self.parent]
            if Nodes[p.left] != self and Nodes[p.left] != -1:
                return p.left
            if Nodes[p.right] != self and Nodes[p.right] != -1:
                return p.right


    N = int(input())
    Nodes = [Node(-1, None, None) for _ in range(25)]

    for _ in range(N):
        id, left, right = map(int, input().split())
        Nodes[id].left = left
        Nodes[id].right = right
        if left != -1:
            Nodes[left].parent = id
        if right != -1:
            Nodes[right].parent = id

    for i in range(N):
        node = Nodes[i]
        print("node %d: " % i, end="")
        print("parent = %d, " % node.parent, end="")
        print("sibling = %d, " % node.get_sigling(), end="")
        print("degree = %d, " % node.get_degree(), end="")
        print("depth = %d, " % node.get_depth(), end="")
        print("height = %d, " % node.get_height(), end="")
        print(node.get_type())

if __name__ == '__main__':
    resolve()



Measured memory_bytes: 5636
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,T,ans=1001; cin >> N >> T;
  vector<int> c(110),t(110);
  for(int i=1; i<=N; i++) {
    cin >> c[i] >> t[i];
  }
  
  for(int i=1; i<=N; i++) {
    if(t[i]<=T) ans= min(ans,c[i]);
  }
  if(ans==1001) cout << "TLE" << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << ": " << a << endl

int main() {
    int n; cin>>n;
    int answer = 0;
    for(int i = 1; i <=n; i++){
		string s = to_string(i);
		if(s.size() % 2 != 0){
			answer++;
		}
	}
    cout<<answer<<endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long MOD = 998244353;
const long long INF = 1LL << 60;
const int inf = pow(10, 9) + 7;
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  long long a, b;
  cin >> a >> b;

  string ans;
  if (a * b <= 0) ans = "Zero";
  else if (a > 0 && b > 0) ans = "Positive";
  else if ((b - a) % 2 == 0) ans = "Negative";
  else ans = "Positive";
  
  cout << ans << endl;
}

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

typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;

const int INF = 1000000007;
const LL INFLL = 1000000000000000007;

#define st first
#define nd second
#define pb push_back
#define _boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// ***************************** CODE ***************************** //

const int MAX = 3e3 + 7;

LD dp[MAX][MAX];
LD p[MAX];

int main() {
    _boost;

    int n;  cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> p[i];

    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= i; j++)
        {
            if(j == 0)
                dp[i][j] = dp[i-1][j]*(1-p[i]);
            else
                dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i];
        }

    LD ans = 0;
    for(int i = n/2+1; i <= n; i++)
        ans += dp[n][i];

    cout << setprecision(10) << fixed << ans;

    return 0;
}


Measured memory_bytes: 139776
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	int a,b;
	cin>>n>>a>>b;
	for(int i=a;i<=b;i++)
	{
	   if(i%n==0)
	   {
	      cout<<"OK";
		  return 0;	
	   }	
	} 
	cout<<"NG";
}

Measured memory_bytes: 3632
N = int(raw_input())                                                                        
s = raw_input()                                                                             
t = raw_input()                                                                             
                                                                                            
count = 0                                                                                   
for i in xrange(N):                                                                         
    if s[i] == t[count]:                                                                    
        count += 1                                                                          
print 2*N - count 

Measured memory_bytes: 2568
#include <stdio.h>
int binarySearch(int A[],int n,int key){
  int left,mid,right;
  left=0;
  right=n;
  while(left<right){
    mid=(left+right)/2;
    if(A[mid]==key){
      return 1;
    }
    else if(key<A[mid]){
      right=mid;
    }
    else 
      left=mid+1;
  }
  return 0;
}
int main(){
  int i,n,q,S[100000],key,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(binarySearch(S,n,key)==1)
      sum++;
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 2176
#include <stdio.h>
#include <stdlib.h>

#define MAX(A,B) \
  ( (B) > (A) ? (B) : (A) )

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

  scanf ( "%d", &dsn );
  while ( dsn-- )
  {
    int init, years, wn;
    int res = 0;

    scanf ( "%d%d%d", &init, &years, &wn );
    while ( wn-- )
    {
      int type, reqs;
      double mag;

      scanf ( "%d%lf%d", &type, &mag, &reqs );
      if ( type == 0 )
      { /* 単利の場合 */
        int cur = init, adx = 0;

        for ( i = 0; i < years; ++i )
        {
          adx += (int)( cur * mag );
          cur -= reqs;
        }
        res = MAX( res, cur + adx );
      }
      else
      { /* 複利の場合 */
        int cur = init;

        for ( i = 0; i < years; ++i )
        {
          cur = (int)( cur + cur * mag - reqs );
        }
        res = MAX( res, cur );
      }
    }

    printf ( "%d\n", res );
  }

  return ( EXIT_SUCCESS );
}

Measured memory_bytes: 632
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function main()
  n = readint()[1]
  A = Vector{int}(undef,n)
  B = Vector{int}(undef,n)

  for i in 1:n
    A[i], B[i] = readint()
  end
  
  sort!(A)
  sort!(B)

  if n%2 == 1
    println(B[n÷2 + 1] - A[n÷2 + 1] + 1)
  else
    println(B[n÷2] + B[n÷2 + 1] - A[n÷2] - A[n÷2 + 1]+1)
  end
  #println()
end

main()

Measured memory_bytes: 208296
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF (1e9)
typedef long long unsigned int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

template<typename T>
T gcd(T a,T b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

template<typename T>
T lcm(T a,T b){
	T g = gcd(a, b);
	return a * b / g;
}

void clear( std::queue<pair<int,int> > &q )
{
   std::queue<pair<int,int> > empty;
   std::swap( q, empty );
}

int N,M;

int main()
{
	int K;
	cin>>N>>K;
	long long x[N],y[N];
	REP(i,0,N){
		cin>>x[i]>>y[i];
	}

	ll ans=0;

	REP(xi,0,N){
		REP(xj,0,N){
			if(x[xi]<x[xj]){
				REP(yi,0,N){
					REP(yj,0,N){
						if(y[yi]<y[yj]){
							int c=0;
							REP(k,0,N){
								if(x[xi]<=x[k]&&x[k]<=x[xj]&&y[yi]<=y[k]&&y[k]<=y[yj]){
									c++;
								}
							}
							if(c>=K){
								ll area=(x[xj]-x[xi])*(y[yj]-y[yi]);
								if(ans==0){
									ans=area;
								}else{
									ans=min(ans,area);
								}
							}
						}
					}
				}
			}
		}
	}

	cout<<ans<<endl;
	
	

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
	int a, numero, blz=0;
	int cont=0;
	scanf("%d", &a);
	while(cont < a){
		scanf("%d", &numero);
		if(numero%2==0){
			if((numero %3 != 0) && (numero%5 !=0)){
				blz=1;
				break;
			}
		}
		++cont;
	}
	if(blz) {
		printf("DENIED\n");
	} else {
		printf("APPROVED\n");
	}

	return 0;
}

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

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	string s; cin >> s;
	int ans = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == 'A') {
			for (int j = i + 1; j < s.length(); j++) {
				if (s[j] == 'Z') {
					ans = max(ans, j - i + 1);
				}
			}
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 768
#include<iostream>
using namespace std;
int N,M,A[100][100],B[1000],C[1000],t;
int main() {
	cin>>N>>M;
	for(int i=0; i<N; i++)for(int j=0; j<M; j++) {cin>>t,A[i][j]=t;}
	for(int j=0; j<M; j++) {cin>>t,B[j]=t;}
	for(int i=0; i<N; i++)for(int j=0; j<M; j++) {	C[i]+=A[i][j]*B[j];}
	for(int j=0; j<N; j++) {	cout<<C[j]<<endl;	}
	return 0;
}


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

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N = 200010;
int _w;

int n, a, b, c, d;
char s[N];
vector<pii> stone, interval;

void solve_stone() {
	for( int i = 1; i <= n; ++i )
		if( s[i] == '#' ) {
			int j;
			for( j = i; j <= n && s[j] == '#'; ++j );
			--j;
			if( j-i+1 >= 2 ) {
				stone.push_back( pii(i, j) );
			}
			i = j;
		}
}

void solve_interval() {
	stone.push_back( pii(0, 0) );
	stone.push_back( pii(n+1, n+1) );
	sort(stone.begin(), stone.end());
	for( int i = 1; i < (int)stone.size(); ++i ) {
		int L = stone[i-1].second + 1;
		int R = stone[i].first - 1;
		if( L <= R )
			interval.push_back( pii(L, R) );
	}
}

int main() {
	_w = scanf( "%d%d%d%d%d", &n, &a, &b, &c, &d );
	_w = scanf( "%s", s+1 );
	solve_stone();
	solve_interval();
	if( c > d ) {
		pii now(-1, -1);
		for( pii inter : interval ) {
			if( a >= inter.first && c <= inter.second )
				now = inter;
		}
		if( now == pii(-1, -1) ) {
			puts("No");
		} else {
			bool flag = false;
			for( int i = b; i <= d; ++i )
				if( s[i] == '.' && s[i-1] == '.' && s[i+1] == '.' )
					flag = true;
			puts( flag ? "Yes" : "No" );
		}
	} else {
		bool flag1 = false, flag2 = false;
		for( pii inter : interval ) {
			if( a >= inter.first && c <= inter.second )
				flag1 = true;
			if( b >= inter.first && d <= inter.second )
				flag2 = true;
		}
		if( flag1 && flag2 ) puts("Yes");
		else puts("No");
	}
	return 0;
}


Measured memory_bytes: 3852
N=int(input())
A = list(map(int, input().split()))
eflag = 0

for i in range(N):
    if A[i]%2==0:
        if A[i]%3!=0 and A[i]%5!=0:
            eflag =1
            
    if eflag ==1:
        break
if eflag ==1:
    print("DENIED")
else:
    print("APPROVED")

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

// a-b, c-d
int solve(int a, int b, int c, int d) {
  if (c < a) { swap(a,c); swap(b,d); }
  // a <= c d
  // abcd, acbd, acdb

  if (b <= c) return 0; // abcd
  if (d <= b) return d-c; // acdb
  return b-c; // acbd
}

int main(){
  int a,b,c,d; cin >> a >> b >> c >> d;
  int ans = solve(a,b,c,d);
  cout << ans << endl;
  return 0;
}


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

 // Combination Table
long long C[51][51]; // C[n][k] -> nCk
void comb_table(int N){
 for(int i=0;i<=N;++i){
 for(int j=0;j<=i;++j){
 if(j==0 or j==i){
 C[i][j]=1LL;
 }else{
 C[i][j]=(C[i-1][j-1]+C[i-1][j]);
}}}}
int main(){
cout << fixed << setprecision(8);
int N,A;
long long counter=0;
int B;
cin>>N>>A>>B;
comb_table(N);
double AA=A;
int counter1=0;
int counter2=0;
long long answer=0;
long long counter3=1;
vector<long long>vec(N);
for(int i=0;i<N;i++){
cin>>vec.at(i);}
sort(vec.begin(),vec.end());
reverse(vec.begin(), vec.end());
for(int i=0;i<A;i++){
counter+=vec.at(i);}
double a=counter/AA;
cout<<a<<endl;
for(int i=0;i<N;i++){
if(vec.at(i)==vec.at(A-1))
counter1++;
else if(vec.at(i)>vec.at(A-1))
counter2++;}
int d=min(counter1,B);
if(counter2>0){
answer+=C[counter1][A-counter2];
cout<<answer<<endl;}
else{
for(int j=A-counter2;j<=d;j++){
answer+=C[counter1][j];}
cout<<answer<<endl;}}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
int x,y, temp;
while(1)
{
scanf("%d %d", &x, &y);
if(x==0 && y==0)break;
else if(x>y)
{
temp=x;
x=y;
y=temp;
}
printf("%d %d\n", x, y);
}
return 0;
}


Measured memory_bytes: 2584
//↓見なくていいよ！ここから--------------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error("\n");
  var start = Date.now();
  Main();
  var end = Date.now() - start;
  myerr("time : " + (end) + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function makeClone(obj){return JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}

//↑見なくていいよ！ここまで--------------------------------------------------
function Main(){
	var one = nextIntArray();
	var A = one[0];
	var B = one[1];
	var C = one[2];
	var K = nextInt();
	var output = "No";
	dfs(one, 0);
	myout(output);
	function dfs(list, count){
		if(list[0] < list[1] && list[1] < list[2]){
			output = "Yes";
			return;
		}
		if(count == K){
			return;
		}
		var tmp = makeClone(list);
		tmp[0] *= 2;
		dfs(tmp, count + 1);
		var tmp = makeClone(list);
		tmp[1] *= 2;
		dfs(tmp, count + 1);
		var tmp = makeClone(list);
		tmp[2] *= 2;
		dfs(tmp, count + 1);
	}
}


Measured memory_bytes: 30988
#include<cstdio>
#include<iostream>
#include<climits>
using namespace std;
int n,w[101],m;
long long v[101],a[100001];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%lld",&w[i],&v[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			a[j]=max(a[j],a[j-w[i]]+v[i]);
		}
	}
	printf("%lld",a[m]);
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>

int main() {
    std::string str;
    std::cin >> str;

    int cnt = 0;
    for (int i = 0; i < str.size(); i++) {
        cnt += str[i] - '0';
    }

    std::printf("%s\n", cnt % 9 == 0 ? "Yes" : "No");

    return 0;
}


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

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

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

  int cur_length = 0;
  for (int i = 0; i < n - 1; i++) {
    if (h[i] >= h[i + 1]) {
      cur_length += 1;
      ans = max(cur_length, ans);
    } else {
      cur_length = 0;
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k=1;
string s;
int main() {
    cin>>n>>s;
    for(ll i=1;i<n;i++)
    {
    	if(s[i]!=s[i-1])
    		k++;
    }
    cout<<k;
}

Measured memory_bytes: 512
h,w,n = map(int,input().split())
y,x = map(int,input().split())
s = input()[::-1]
t = input()[::-1]

r = w
l = 1
d = h
u = 1

for i in range(n):
    
    if t[i] == "R":
        l = max(1,l-1)
    elif t[i] == "L":
        r = min(w,r+1)
    elif t[i] == "D":
        u = max(1,u-1)
    else:
        d = min(h,d+1)
    if s[i] == "R":
        r -= 1
    elif s[i] == "L":
        l += 1
    elif s[i] == "D":
        d -= 1
    else:
        u += 1
    if r < l or d < u:
        print("NO")
        exit()

if l <= x <= r and u <= y <= d:
    print("YES")
else:
    print("NO")     


Measured memory_bytes: 9704
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB push_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
using namespace std;
int d[1005][1005],la[1005][1005];
int n;bool vis[1005];
V<int> v[1005],ans;
queue<int> q;
void bfs(int p){
	while(!q.empty())q.pop();FILL(vis,0);
	rep(i,0,v[p].size())q.push(v[p][i]),vis[v[p][i]]=1;
	int cur,u;
	while(!q.empty()){
		cur=q.front();q.pop();
		if(cur==p)RE;
		rep(i,0,v[cur].size()){
			u=v[cur][i];
			if(!vis[u]){
				vis[u]=1;
				la[p][u]=cur;d[p][u]=d[p][cur]+1;q.push(u);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	FILL(d,0x3f);
	int m,x,y;
	cin>>n>>m;
	FOR(i,1,m){
		cin>>x>>y;d[x][y]=1;
		v[x].PB(y);
	}
	FOR(i,1,n){
		bfs(i);
	}
	int mini=0;
	FOR(i,1,n){
		if(d[i][i]<d[mini][mini])mini=i;
	}
	if(!mini){
		cout<<-1;RE 0;
	}
	int t=mini;
	while(t){
		ans.PB(t);t=la[mini][t];
	}
	cout<<ans.size()<<'\n';
	rep(i,0,ans.size())cout<<ans[i]<<'\n';
	RE 0;
}





Measured memory_bytes: 8192
#include <stdio.h>
#include <string.h>
char* myfgets(char *buf,int n,FILE *fp){ //accepts LF/CRLF
	char *ret=fgets(buf,n,fp);
	if(!ret)return NULL;
	if(strlen(buf)&&buf[strlen(buf)-1]=='\n')buf[strlen(buf)-1]=0;
	if(strlen(buf)&&buf[strlen(buf)-1]=='\r')buf[strlen(buf)-1]=0;
	return ret;
}

char Q[99999];
char *q[999];
char L[99999];
int ind[9999];
int n;
dfs(depth){
	int cur_ind=0;
	if(!myfgets(L,sizeof(L),stdin)){puts("no such property");exit(0);}
	if(depth){
		for(;L[cur_ind]==' ';cur_ind++);
		if(ind[depth-1]>=cur_ind){puts("no such property");exit(0);}
	}
	char *name=strtok(L+cur_ind,":"),*value=name+strlen(name)+1;
	if(!strcmp(name,q[depth])){
		if(depth==n-1){
			if(*value)
				printf("string \"%s\"\n",value+1),exit(0);
			else
				puts("object"),exit(0);
		}
		ind[depth]=cur_ind;
		dfs(depth+1);
	}
	dfs(depth);
}

main(depth){
	myfgets(Q,sizeof(Q),stdin);
	q[0]=strtok(Q+1,".");
	for(n=1;;n++)if(!(q[n]=strtok(NULL,".")))break;
	dfs(0);
}

Measured memory_bytes: 584
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <stack>
#include <deque>
#include <ctime>
#include <random>
#include <cassert>
#include <cmath>
#include <climits>
#include <queue>
#include <cstring>
#include <bitset>
#include <iomanip>
#include <chrono>

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2")
*/


#ifdef LOCAL
	#define dbg(x) cout << #x << " : " << x << endl;
#else 
	#define dbg(x)
#endif

#define int long long
#define fi(a,b) for (int i=a;i<b;i++)
#define fj(a,b) for (int j=a;j<b;j++)
#define fk(a,b) for (int k=a;k<b;k++)
#define fi1(a,b) for (int i=a-1;i>=b;i--)
#define fj1(a,b) for (int j=a-1;j>=b;j--)
#define fk1(a,b) for (int k=a-1;k>=b;k--)
#define fx(x,a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, T2 y) { if (x < y) x = y; }

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << ' ';
    return a;
}


typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 20;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int c[MX];
int a[MX][MX];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, x;
    cin >> n >> m >> x;
    fi(0, n) {
    	cin >> c[i];
    	fj(0, m)
    		cin >> a[i][j];
    }
    int ans = INF;
    rep(mask, 0, 1 << n) {
    	vi cur(m, 0);
    	int sum = 0;
    	fi(0, n) {
    		if (mask & (1 << i)) {
	    		sum += c[i];
	    		fj(0, m) {
	    			cur[j] += a[i][j];
	    		}
	    	}
    	}
    	bool done = true;
    	fi(0, m) {
    		done &= cur[i] >= x;
    	}
    	if (done) {
    		mine(ans, sum);
    	}
    } 
    cout << (ans == INF ? -1 : ans) << '\n';
}

Measured memory_bytes: 3672
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	a,b = MI()
	if b == 1:
		print(0)
	else:
		ans = 0
		tap = 1
		while True:
			tap += a - 1
			ans += 1
			if b <= tap:
				print(ans)
				break


if __name__ == '__main__':
	main()

Measured memory_bytes: 3064
from copy import deepcopy
from collections import deque

# 最短にする
# 0回以上でたどり着けるのでスタート=ゴールのことがある ふざけんな
h, w = map(int, input().split())
table = [[] for _ in range(h)]
for i in range(h):
    table[i] = list(input())


def bfs(y, x, t):
    steps = [0, 1, 0, -1, 0]
    queue = deque([[y, x]])
    ret = 0
    while len(queue) > 0:
        cur_y, cur_x = queue.popleft()
        for i in range(4):
            next_y, next_x = cur_y + steps[i], cur_x + steps[i + 1]
            if 0 <= next_y < h and 0 <= next_x < w:
                if t[next_y][next_x] == ".":
                    t[next_y][next_x] = t[cur_y][cur_x] + 1
                    ret = max(ret, t[next_y][next_x])
                    queue.append([next_y, next_x])

    return ret


ans = 0
for sy in range(h):
    for sx in range(w):
        # table[sy][sx]をスタート地点とする
        if table[sy][sx] != ".":
            continue
        mytable = deepcopy(table)
        mytable[sy][sx] = 0
        ret = bfs(sy, sx, mytable)
        ans = max(ans, ret)

print(ans)


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

using namespace std;
typedef long long ll;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define each(i,mp) for(auto& i:mp)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const lb pi=acos(-1);
const ll mod=1e9+7;
const ll INF = 1LL<<60;
const ll m=1LL<<32;

int main(){

  string t;cin>>t;
  rep(i,0,t.size()){
    if(t[i]=='?')t[i]='D';
  }

  out(t);

  return 0;
}


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

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

int main(){
	int a, b;
	cin >> a >> b;
	
	cout << a * b;
	return 0;
}

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

int main(){

  cin.tie(0); //cin高速化
  ios::sync_with_stdio(false); //cin高速化
  
  int n;
  cin >> n;
  int ans = 0;
  string str = to_string(n);
  int m = str.size();
  rep(i,m){
    string s = str.substr(i,1);
    int num = atoi(s.c_str());
    ans += num;
    }
  if(n%ans==0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}
    

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

int main(){
    long long n;
    std::cin >> n;

    long long i = 1;
    std::vector<long long> manhattans;
    while(i <= std::sqrt(n)){
        if(0 == n % i){
            manhattans.push_back(i + n / i);
        }
        ++i;
    }

    std::cout << *std::min_element(manhattans.begin(), manhattans.end()) - 2 << std::endl;

    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
int main(){
    ll N;
    cin >> N;
    map<ll, ll> m;
    m[0]++;
    ll sum = 0;
    ll ans = 0;
    for(ll i = 0; i < N; i++){
        ll a;
        cin >> a;
        sum += a;
        auto po = m.find(sum);
        if(po != m.end()) ans += po->second;
        m[sum]++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
vector < vector<int> > adj;
vector < pair<int, int> > edges;
int n;
int vis[55];

void buildgraph(int exclude){
    adj = vector< vector<int> >(n);
    memset(vis, 0, sizeof vis);
    for(int i=0; i<edges.size(); i++){
        if(i == exclude)
            continue;
        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }
}

int dfs(int ind){
    if(vis[ind]++)
        return 0;
    int res = 0;
    for(auto x : adj[ind])
        res += dfs(x);
    return 1 + res;
}
int main()
{
    int m;
    cin >> n >> m;
    edges = vector< pair<int, int> >(m);
    for(int i=0; i<m; i++){
        cin >> edges[i].first >> edges[i].second;
        edges[i].first--, edges[i].second--;
    }
    int res = 0;
    for(int i=0; i<edges.size(); i++){
        buildgraph(i);
        int nodes = dfs(!i);
        if(nodes != n)
            res++;
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;

int main()
{
    double a, b;
    cin >> a >> b;

    int aMin = ceil(a * 12.5);
    double aMax = (a + 1) * 12.5;
    int bMin = ceil(b * 10);
    double bMax = (b + 1) * 10;

    if (bMin < aMax && aMin < bMax)
    {
        cout << max(aMin, bMin);
        return 0;
    }
    cout << -1;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Node{
  public:
    int cost;
    int from;

    Node(int cost, int from){
      this -> cost = cost;
      this -> from = from;
    }
};

struct Comparator{
  bool operator()(const Node& a, const Node& b){
    return a.cost > b.cost;
  }
};

typedef pair<int, int> pii;
typedef vector<pii> ad;

void make_ad_list(ad* ad_list, pii* material, int n){
  for(int i = 1; i < n; i++){
    pii from = material[i - 1];
    pii to = material[i];
    ad_list[from.second].push_back(make_pair(abs(from.first - to.first), to.second));
    ad_list[to.second].push_back(make_pair(abs(from.first - to.first), from.second));
  }
}

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


  pii xs[n];
  pii ys[n];

  int x, y;
  for(int i = 0; i < n; i++){
    cin >> x >> y;
    xs[i] = make_pair(x, i);
    ys[i] = make_pair(y, i);
  }

  sort(xs, xs + n, [](const pii& a, const pii& b){ return a.first < b.first; });
  sort(ys, ys + n, [](const pii& a, const pii& b){ return a.first < b.first; });

  ad ads[n];
  make_ad_list(ads, xs, n);
  make_ad_list(ads, ys, n);

  priority_queue<Node, vector<Node>, Comparator> pque;

  int sum = 0;
  bool visited[n] = { false };

  int target = 0;
  visited[0] = true;

  while(true){
    for(pii edge: ads[target]){
      pque.push(Node(edge.first, edge.second));
    }
    Node n(0, 0);

    while(!pque.empty()){
      n = pque.top();
      pque.pop();
      if(not visited[n.from]){
        goto WHILELSE;
      }
    }
    cout << sum << endl;
    return 0;

WHILELSE:
    target = n.from;
    visited[target] = true;
    sum += n.cost;
  }
}


Measured memory_bytes: 12024
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, D[55];
int num[13];

int res(int bit)
{
	int last = 0;
	int ret = 24;
	for (int i = 1; i < 24; ++i) {
		if ((bit >> i) & 1) {
			int dif = i - last;
			last = i;
			ret = min(ret, min(dif, 24 - dif));
		}
	}
	ret = min(ret, min(last, 24 - last));
	return ret;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", D + i);

	for (int i = 0; i < N; ++i) {
		++num[D[i]];
	}
	int mask = 0;
	int tg = 0;
	for (int i = 0; i <= 12; ++i) {
		if (num[i] >= 3 || (i == 12 && num[i] == 2) || (i == 0 && num[i] == 1)) {
			puts("0");
			return 0;
		}
		if (num[i] == 2) {
			mask |= 1 << i;
			mask |= 1 << (24 - i);
		} else if (num[i] == 1) {
			tg |= 1 << i;
		}
	}
	int ret = 0;
	for (int b = 0; b < (1 << 13); ++b) {
		int m2 = mask;
		for (int i = 0; i <= 12; ++i) {
			if (tg & (1 << i)) {
				if (b & (1 << i)) m2 |= 1 << (24 - i);
				else m2 |= 1 << i;
			}
		}
		ret = max(ret, res(m2));
	}
	printf("%d\n", ret);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  map<ll, ll> mp;
  rep(i, n) {
    ll a;
    cin >> a;
    mp[a]++;
  }
  ll ans = 0;
  for(auto v : mp) {
    ll x = v.first;
    ll k = v.second;
    if(x > k)
      ans += k;
    else
      ans += k - x;
  }
  cout << ans << endl;
}

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

int sum[310][310];
int N;

int get(int x1,int y1,int x2,int y2){
    return sum[y2+1][x2+1]-sum[y2+1][x1]-sum[y1][x2+1]+sum[y1][x1];
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&sum[i+1][j+1]);
            sum[i+1][j+1]+=sum[i][j+1]+sum[i+1][j]-sum[i][j];
        }
    }

    int ma=INT_MIN;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            int prev=get(0,i,0,j);
            ma=max(ma,prev);
            for(int k=1;k<N;k++){
                ma=max(ma,max(0,prev)+get(k,i,k,j));
                prev=max(prev+get(k,i,k,i)+get(k,j,k,j),get(k,i,k,j));
            }
        }
    }

    for(int i=0;i<N;i++){
        int prev=get(0,i,0,i);
        ma=max(prev,ma);
        for(int j=1;j<N;j++){
            prev=max(get(j,i,j,i),prev+get(j,i,j,i));
            ma=max(ma,prev);
        }
    }

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

Measured memory_bytes: 1556
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

void	solve()
{
	int a, b;
	cin >> a >> b;
	if (a > 8 || b > 8)
		cout << ":(" << endl;
	else
		cout << "Yay!" << endl;
}

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

	solve();
}


Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        int[] a = new int[num];
        for (int i = 0; i < num; i++) {
            a[i] = sc.nextInt();
        }

        int pair = 0;
        for (int i = 0; i < num; i++) {
            if (a[a[i] - 1] - 1 == i) {
                pair++;
            }
        }

        System.out.println(pair/2);
    }
}

Measured memory_bytes: 32372
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <array>
#include <tuple>
#include <random>

using namespace std;
typedef long long int ll;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()

#define const INF 10000000000

ll a, b, c, n, x, y, z, w, h, ans = 0, cnt = 0, mx = 0;
string s;

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

    cin >> n;
    ll list[n];
    rep(i, n){
        cin >> list[i];
        if(i){
            rep(j, i){
                mx = max(mx, abs(list[i] - list[j]));
            }
        }
    }
    cout << mx << endl;
}



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

void addEdge(vector<ll> adj[], ll u, ll v){
  adj[u].push_back(v);
}

void dfs(vector<ll> adj[], ll node, bool vis[], ll dp[]){
  vis[node]=true;
  for(ll i=0; i<adj[node].size(); i++){
    if(!vis[adj[node][i]]){
      dfs(adj,adj[node][i], vis, dp);
    }
    dp[node] = max(dp[node], 1+dp[adj[node][i]]);
  }
}

ll longestPath(vector<ll> adj[], ll n){
  ll dp[n+1];
  memset(dp, 0, sizeof(dp));
  bool vis[n+1];
  memset(vis, false, sizeof(vis));
  for(ll i=1; i<=n; i++){
    if(!vis[i]){
      dfs(adj,i,vis,dp);
    }
  }
  ll ans=0;
  for(ll i=0; i<=n; i++){
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  ll n,m;
  cin>>n>>m;
  vector<ll> adj[n+1];
  while(m--){
    ll u,v;
    cin>>u>>v;
    addEdge(adj,u,v);
  }
  ll ans = longestPath(adj, n);
  cout<<ans<<"\n";
  
  return 0;
}


Measured memory_bytes: 13164
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>

using namespace std;

int n,k,x,sm=0;

int main(){
    scanf("%d",&n);
    scanf("%d",&k);
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        sm+=min(abs(x-k),x)*2;
    }
    
    
    printf("%d\n",sm);
    
}


Measured memory_bytes: 256
// Code by H~$~C
#include <bits/stdc++.h>
using namespace std;

static const int Maxn = 20005;

int n;
int x[Maxn], y[Maxn];
vector<pair<int, int> > pos;

namespace two_sat {
  int n;
  vector<vector<int> > g;
  vector<int> dfn, scc, low;
  vector<bool> instk;
  int scc_size, indx;
  stack<int> stk;
  void tarjan(int u) {
    dfn[u] = low[u] = ++indx;
    stk.push(u);
    instk[u] = true;
    for (int &v: g[u]) {
      if (!dfn[v]) {
        tarjan(v);
        low[u] = min(low[u], low[v]);
      }
      else if (instk[v]) {
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (dfn[u] == low[u]) {
      scc_size++;
      do {
        int v = stk.top(); stk.pop();
        scc[v] = scc_size;
        instk[v] = false;
        if (v == u) break;
      } while (1);
    }
  }
  inline int inv(int x) { return x ^ 1; }
  inline void clear() {
    n = 0, g.clear();
    while (!stk.empty()) stk.pop();
    scc_size = indx = 0;
    instk.clear();
  }
  inline int newnode() {
    g.push_back(vector<int>());
    g.push_back(vector<int>());
    return 2 * n++;
  }
  inline void init(int x) {
    clear();
    while (n < x) newnode();
  }
  inline void imply(int a, int b) {
    g[a].push_back(b);
    g[inv(b)].push_back(inv(a));
  }
  bool solve() {
    dfn.assign(n * 2, 0);
    low.assign(n * 2, 0);
    scc.assign(n * 2, 0);
    instk.assign(n * 2, false);
    scc_size = indx = 0;
    for (int i = 0; i < n * 2; ++i) {
      if (!dfn[i]) {
        tarjan(i);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (scc[2 * i] == scc[2 * i + 1])
        return false;
    }
    return true;
  }
}

#define ls (p * 2 + 1)
#define rs (p * 2 + 2)
#define mid (l + r >> 1)
int tr[Maxn << 2];
void build(int p, int l, int r) {
  tr[p] = two_sat::newnode();
  if (l == r) {
    two_sat::imply(tr[p], two_sat::inv(pos[l].second));
    return ;
  }
  build(ls, l, mid);
  build(rs, mid + 1, r);
  two_sat::imply(tr[p], tr[ls]);
  two_sat::imply(tr[p], tr[rs]);
}
void link_edge(int p, int l, int r, int L, int R, int id) {
  if (L > r || l > R) return ;
  if (L <= l && r <= R) {
    two_sat::imply(id, tr[p]);
    return ;
  }
  link_edge(ls, l, mid, L, R, id);
  link_edge(rs, mid + 1, r, L, R, id);
}
#undef ls
#undef rs
#undef mid

bool check(int d) {
  two_sat::init(n);
  build(0, 0, n * 2 - 1);
  for (int i = 0; i < n * 2; ++i) {
    int st = lower_bound(pos.begin(), pos.end(), make_pair(pos[i].first - d + 1, 0)) - pos.begin();
    int ed = lower_bound(pos.begin(), pos.end(), make_pair(pos[i].first + d, 0)) - pos.begin();
    if (i > st) link_edge(0, 0, n * 2 - 1, st, i - 1, pos[i].second);
    if (i < ed - 1) link_edge(0, 0, n * 2 - 1, i + 1, ed - 1, pos[i].second);
  }
  return two_sat::solve();
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", x + i, y + i);
    pos.push_back({x[i], i * 2});
    pos.push_back({y[i], i * 2 + 1});
  }
  sort(pos.begin(), pos.end());
  int l = 0, r = 1000000000, ans = 0;
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid)) l = mid + 1, ans = mid;
    else r = mid - 1;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 20136
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second

ll n, a[maxn], s;
string st[2] = {"First", "Second"};

int main(){
    fast_io;

    cin >> n;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }
    if(n % 2 == 0){
        for(ll i = 0; i < n; i++){
            s += a[i];
        }
        if(s & 1) cout << "First";
        else cout << "Second";
        return 0;
    }
    ll t = 0;
    while(true){
        s = 0;
        for(ll i = 0; i < n; i++){
            s += a[i];
        }
        if(s % 2 == 0){
            cout << st[t];
            return 0;
        }
        ll x = -1;
        for(ll i = 0; i < n; i++){
            if((a[i] & 1) == 1 && a[i] > 1) x = i;
        }
        if(x == -1){
            cout << st[1 - t];
            return 0;
        }
        a[x]--;
        ll g = 0;
        for(ll i = 0; i < n; i++){
            g = __gcd(g, a[i]);
        }
        for(ll i = 0; i < n; i++){
            a[i] /= g;
        }
        t = 1 - t;
    }

    return 0;
}

Measured memory_bytes: 4428
#include <stdio.h>
int main(void)
{
    int a, b, c;
 
    scanf("%d %d %d", &a, &b, &c);
 
    if(a<=b && b<=c)
        printf("%d %d %d\n", a, b, c);
    else if(a<=c && c<=b)
        printf("%d %d %d\n", a, c, b);
    else if(b<=a && a<=c)
        printf("%d %d %d\n", b, a, c);
    else if(b<=c && c<=a)
        printf("%d %d %d\n", b, c, a);
    else if(c<=a && a<=b)
        printf("%d %d %d\n", c, a, b);
    else
        printf("%d %d %d\n", c, b, a);
 
    return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  int N,T,ans=1001;
  cin>>N>>T;
  int c[N],t[N];
  for(int i=0;i<N;i++) cin>>c[i]>>t[i];
  for(int i=0;i<N;i++){
    if(t[i]<=T) ans=min(ans,c[i]);
  }
  if(ans!=1001) cout<<ans<<endl;
  else cout<<"TLE"<<endl;
}	


Measured memory_bytes: 256
#[test]
fn test_solve() {
    assert_eq!(solve("7\nbeat\nvet\nbeet\nbed\nvet\nbet\nbeet\n"), "beet\nvet\n");
    assert_eq!(solve("8\nbuffalo\nbuffalo\nbuffalo\nbuffalo\nbuffalo\nbuffalo\nbuffalo\nbuffalo\n"), "buffalo\n");
    assert_eq!(solve("7\nbass\nbass\nkick\nkick\nbass\nkick\nkick\n"), "kick\n");
    assert_eq!(solve("4\nushi\ntapu\nnichia\nkun\n"), "kun\nnichia\ntapu\nushi\n");
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let mut s: Vec<Vec<char>> = (0..n).map(|_| sc.chars()).collect();

    s.sort();

    let mut mct = 0;
    let mut cnt = 1;
    for i in 0..n-1 {
        if s[i] == s[i+1] {
            cnt += 1;
        } else {
            cnt = 1;
        }
        if cnt > mct {
            mct = cnt;
        }
    }

    let mut ret = String::new();
    use std::fmt::Write;

    cnt = 1;
    if cnt == mct {
        for &c in &s[0] {
            write!(&mut ret, "{}", c).unwrap();
        }
        writeln!(&mut ret, "").unwrap();
    }
    for i in 0..n-1 {
        if s[i] == s[i+1] {
            cnt += 1;
        } else {
            cnt = 1;
        }
        if cnt == mct {
            for &c in &s[i+1] {
                write!(&mut ret, "{}", c).unwrap();
            }
            writeln!(&mut ret, "").unwrap();
        }
    }

    ret
}

fn main() {
    let mut buf = String::new();
    use std::io;
    use std::io::{Read, Write};
    io::stdin().read_to_string(&mut buf).unwrap();
    io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}

struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.get().chars().collect()
    }
}

Measured memory_bytes: 24828