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

typedef vector<int> veci;
typedef pair<int, int> pii;
typedef vector<pii> vecii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vecl;
typedef vector<pll> vecll;
#define EPS (1e-9)
#define MOD (1e9 + 7)
#define fi first
#define se second
#define endl '\n'

void solve() {
    veci deg(4,0);
    int a, b;
    for (int i=0; i<3; ++i) {
        cin >> a >> b;
        a--, b--;
        deg[a] += 1;
        deg[b] += 1;
    }

    int odd = 0;
    for (int i=0; i<4; ++i) {
        if (deg[i]%2) {
            odd += 1;
        }
    }

    if (odd>2) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL_TEST
    (void)argc;
    const string strpath = string(argv[0]) + string("-test.in");
    freopen(strpath.c_str(), "r", stdin);
    int tcs;
    cin >> tcs;
    while (tcs-- > 0)
#endif
    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(), a.end());
    int amin = a[0];
    int amax;
    sort(a.rbegin(), a.rend());
    amax = a[0];
    cout << amax - amin << endl;
}

Measured memory_bytes: 256
(n,),*a=[[*map(int,i.split())]for i in open(0)]
d={}
for i,j in a:
    for x,y in a:
        if i!=x or j!=y:
            d[(i-x,j-y)]=d.get((i-x,j-y),0)+1
print(n-max(list(d.values())+[0]))

Measured memory_bytes: 9348
import bisect

X, Y, Z, K = list(map(int, input().split()))

x = sorted(list(map(int, input().split())), reverse=True)
y = sorted(list(map(int, input().split())), reverse=True)
z = sorted(list(map(int, input().split())), reverse=True)

x_i = 0
y_i = 0
z_i = 0

def cand_index(x_i, y_i, z_i):
    cs = [(x_i+1, y_i, z_i)] if x_i+1 < X else []
    cs += [(x_i, y_i+1, z_i)] if y_i+1 < Y else []
    cs += [(x_i, y_i, z_i+1)] if z_i+1 < Z else []
    return set(cs)

num_xyz = [[x[0]+ y[0]+ z[0], (0, 0, 0)]]
used = set()
ans = []
num = 0
for _ in range(K):
    num, xyz = num_xyz.pop(0)
    ans.append(num)

    new_cand = cand_index(*xyz)
    cand = new_cand - used
    used |= new_cand

    num_xyz += [[x[xyz[0]] + y[xyz[1]] + z[xyz[2]], xyz] for xyz in cand]
    num_xyz = sorted(num_xyz, key=lambda x: x[0], reverse=True)

for a in ans:
    print(a)


Measured memory_bytes: 4840
#include <iostream>
#include <stack>
#include <string>
using namespace std;
using ll = long long;

/* スタックの基礎：他のコンテナ型と同じ部分がある
 * Last In First Out: LIFO の原則
・要素を入れる．：stack.push(num)
・要素を取り出す．：stack.pop(num)(pop_back も同じ)：戻り値は void
・頂点の要素を返す：stack.top(num)：戻り値は頂点の num
・直接構築でスタックに要素を追加：stack.emplace_back()
stack.(), stack
*/

int stack_test() {
    stack<int> stk;
    
    // how to use stack
    cout << stk.size() << "\n";
    
    stk.push(3);
    stk.push(7);
    stk.push(1);
    
    cout << stk.size() << "\n";
    cout << stk.top() << "\n";
    // cout << stk.pop() << "\n"; pop(), pop_back() は戻り値がない
    
    stk.push(5);
    stk.push(100);
    stk.push(87);
    
    // 空になるまで取り出す
    while (!stk.empty()) {
        cout << stk.top() << "\n";
        stk.pop();
    }
    
}

int ctoi(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    }
    return 0;
}

int ALDS1_3_A() {
    string ope;
    stack<long> stk;
    // 1 2 + 3 4 - *
    // (1+2)*(3-4)
    long a, b;
    while (cin >> ope) {
        if (ope[0] == '+') {
            a = stk.top(); stk.pop();
            b = stk.top(); stk.pop();
            stk.push(b + a);  // 順序に注意
        } else if (ope[0] == '-') {
            a = stk.top(); stk.pop();
            b = stk.top(); stk.pop();
            stk.push(b - a);  // 順序に注意
        } else if (ope[0] == '*'){
            a = stk.top(); stk.pop();
            b = stk.top(); stk.pop();
            stk.push(b * a);
        } else {
            stk.push(stoi(ope));
        }
    }
    
    cout << stk.top() << "\n";
    
    return 0;
}

int main() {
    // stack_test();
    ALDS1_3_A();
    return 0;
}



Measured memory_bytes: 3172
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    k = int(input())
    keta = 1
    mod = 7%k
    if k % 7 == 0:
        max_k = 9*k//7
    else:
        max_k = 9*k
    if k %2 == 0 or k%5 == 0:
        print(-1)
    while keta < max_k:
        if mod == 0:
            print(keta)
            break
        mod = (mod*10 + 7)%k
        keta += 1


if __name__=='__main__':
    main()

Measured memory_bytes: 9164
#include<iostream>
#include<cmath>
#define MAX 1000000
using namespace std;
bool array[MAX];
void era(){
	array[1] = false;
	for(int i=2;i<MAX;i++)	array[i]=true;
	for(int i=2;i<sqrt(MAX);i++){
		if(array[i]){
			for(int j=i*2;j<MAX;j+=i){
				array[j]=false;
			}
		}
	}
}

 
int main(){
	era();
	while(1){
		int a,d,n,cnt=0;
		cin >> a >> d >> n;
		if(!a&&!d&&!n)	break;
		for(int i=a;;i+=d){
			if(array[i]){
					cnt++;
					if(cnt==n){
							cout << i << endl;
							break;
					}
			}
		}
	}
}


Measured memory_bytes: 4068
def main():
    n, k = map(int, input().split())
    d = set(list(map(str, input().split())))
    checker = 1
    while checker:
        if set(list(str(n))).isdisjoint(d):
            print(n)
            checker = 0
        else:
            n += 1

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
def main():
	N = int(input())
	S = input()
	K = int(input())
	non_change = S[K-1]
	ans = ""
	for c in S:
		if c != non_change:
			ans += "*"
		else:
			ans += c
	print(ans)

if __name__ == '__main__':
	main()

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


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

    rep(i,s.length())s[i]='x';

    cout<<s<<endl;

    return 0;
}


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

int main() {
    int n, m,a[10]={0,2,5,5,4,5,6,3,7,6};
    int d[10];
    bool c[10];
    string s[10001];
    cin>>n>>m;
    fill(c, c+10, false);
    fill(d, d+10, -1);
    for(int i=0;i<m;i++){
        int t;
        cin>>t;
        c[t]=true;
        d[a[t]]=max(d[a[t]], t);
    }
    
    s[0]="";
    for(int i=1;i<=n;i++){
        int b=0;
        for(int j=9;j>=1;j--){
            if(!c[j]||i-a[j]<0)continue;
            if(s[i-a[j]]!="0"){
                char t='0'+j;
                int u=s[i-a[j]].length();
                if(b==0||u+1>b){
                    s[i]=t+s[i-a[j]];
                    b=s[i].length();
                }
            }
        }
        if(b==0)s[i]="0";
    }
    cout<<s[n]<<endl;
	return 0;
}

Measured memory_bytes: 32896
s=gets.chomp.chars
z=s.size
(z-1).times do |i|
  if s[i]==s[i+1]
    puts [i+1,i+2].join(" ")
    exit
  end
end
(z-2).times do |i|
  if s[i]==s[i+2]
    puts [i+1,i+3].join(" ")
    exit
  end
end
puts "-1 -1"


Measured memory_bytes: 19064
S=input()
N=int(S)
n=len(S)


ans=0
p=[1,10,100,1000,10000,100000]

for i in range(N+1):#数iに対する相手を探す
    ii=str(i)
    a=int(ii[0])
    b=int(ii[-1])
    if a*b!=0:
        if a==b:#a**aの形なら1桁の答えaが存在
            ans+=1
        for j in range(2,n+1):#桁数
            if j<n:
                ans+=p[j-2]
                #print(i,j,n,ans)
            elif j==n:
                floor=b*p[j-1]+a
                if j==2:
                    ceil=floor
                else:
                    ceil=floor+p[j-1]-p[1]
                #print(i,j,floor,ceil)
                if N>=ceil:
                    ans+=p[j-2]
                    #print(i,j,n,ans)
                elif N<floor:
                    continue
                else:#floorとceilの間
                    ans+=(N-floor)//10+1
                    #print(i,j,n,ans)
    #print("i,ans:{},{}".format(i,ans))
                    
print(ans)

Measured memory_bytes: 42348
#include <stdio.h>

int main(){
  int n,k,c,p[200005],i,j,m;
  char s[200005];
  scanf("%d",&n);
  scanf("%d",&k);
  scanf("%d",&c);
  scanf("%s",&s);
  if(c==0){
    m=0;
    for(i=0;i<n;i++){
      if(s[i]=='o') m++;
    }
    if(k==m){
      for(i=0;i<n;i++){
        if(s[i]=='o'){
          printf("%d\n",i+1);
        }
      }
    }
  }else{
    j=k-1;
    for(i=n-1;j>=0;i--){
      if(s[i]=='o'){
        p[j]=i;
        j--;
        i-=c;
      }
    }
    j=0;
    for(i=0;j<k;i++){
      if(s[i]=='o'){
        if(p[j]==i){
          printf("%d\n",i+1);
        }
        j++;
        i+=c;
      }
    }
  }
  return(0);
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define LL long long
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	LL n,x;
	cin>>n>>x;
	LL d=0,k=1;
	for(LL i=0;i<n;i++){
		LL l;
		cin>>l;
		d+=l;
		if (d>x){
			cout<<k<<endl;
			return 0;
		}
		k++;
	}
	cout<<k<<endl;
}


Measured memory_bytes: 256
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include"bits/stdc++.h"
#define int ll
using namespace std;
using ll = long long ;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20)
//#define endl '\n'
///       Author
///        ::
///    (  NOBODY  )
///   No Copyright .....You can copy and paste it without my permission...................................
/// !!!!!!!!!!!!!!!
#define pb push_back
#define N 1000020
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
void scan(vector<int>&v,int siz)
{
    v.resize(siz);
    for(auto &c:v)
        cin>>c;
}
void print(vector<ll>v)
{
    for(auto c:v)
        cout<<c<<' ';
    cout<<endl;
}
void view(deque<int>v)
{
    for(auto c:v)
        cout<<c<<' ';
    cout<<endl;
}
int fenwik[N];
void update(int pos,int val)
{
    while(pos<N)
    {
        fenwik[pos]+=val;
        pos+=(pos&(-pos));
    }
}
int get(int pos)
{
    int ans=0;
    while(pos>0)
    {
        ans+=fenwik[pos];
        pos-=(pos&(-pos));
    }
    return ans;
}
int a[N],mod=1e9+7;
int goy(int base,int pow)
{
    base%=mod;
    if(pow==0)return 1;
    int x=goy(base,pow/2);
    x=(x*x)%mod;
    if(pow%2)x=(base*x)%mod;
    return x;
}
multimap<int,int>mp;
vector<pair<int,int>>Get_all(int key)
{
    vector<pair<int,int>>vv;
    typedef multimap<int, int>::iterator MMAPIterator;
    pair<MMAPIterator, MMAPIterator> result = mp.equal_range(1);
    for (MMAPIterator it = result.first; it != result.second; it++)vv.push_back({it->ff,it->ss});
    return vv;
}
int n,m;
int dp[21][1001];
int go(int pos,int bef)
{
    if(pos==m)return 1;
    if(dp[pos][bef]!=-1)return dp[pos][bef];
    int ans=0;
    for(int i=bef;i<=n;i++)
    {
        ans+=go(pos+1,i);
        ans%=mod;
    }
    return dp[pos][bef]=ans;
}
int32_t main()
{
    FAST_IO;
  int a,b;
  cin>>a>>b;
 int mn=min(a,b);
 if(a==mn){
    while(b--)cout<<a;
 }
 else {

    while(a--)cout<<b;
 }
 cout<<endl;
    return 0;
}


Measured memory_bytes: 256
import sys
x,n=map(int,input().split())
if n == 0:
  print(x)
  sys.exit()
  
a={int(i) for i in input().split()}
i=0
while True:
  if not (x-i) in a:
    print(x-i)
    sys.exit()
  
  if not (x+i) in a:
    print(x+i)
    sys.exit()
  i+= 1

Measured memory_bytes: 61848
#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= 50000; i++) {
		int x = i * 1.08;
		if (x == n) {
			cout << i << endl;
			return 0;
		}
	}
	cout << ":(" << endl;
	return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            line.pop();
            line
        }
    )
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    )
}

fn solve(a:i32, b:i32) -> Vec<Vec<char>> {
    use std::iter;

    let s1 = iter::repeat("#").take(100).collect::<String>().chars().collect::<Vec<_>>();
    let s2 = iter::repeat(".").take(100).collect::<String>().chars().collect::<Vec<_>>();

    let mut ss: Vec<Vec<char>> = Vec::new();
    ss.extend(iter::repeat(s1).take(50).collect::<Vec<Vec<_>>>());
    ss.extend(iter::repeat(s2).take(50).collect::<Vec<Vec<_>>>());

    for i in 0..a-1 {
        ss[(i / 50 * 2) as usize][(i % 50 * 2) as usize] = '.'
    }

    for i in 0..b-1 {
        ss[(i / 50 * 2 + 51) as usize][(i % 50 * 2) as usize] = '#'
    }

    ss
}

fn main() {
    let (a,b) = parse_line!(i32, i32);
    let ans = solve(a,b);
    println!("100 100");
    for l in ans {
        println!("{}", l.into_iter().collect::<String>());
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
inline void read (int &x) {
    char ch = getchar(); int f = 0; x = 0;
    while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar(); }
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); if (f) x = -x;
} int l;
signed main() {
    read (l);
    printf ("%.8lf\n", (double)(l / 3.0) * (l / 3.0) * (l / 3.0));
    return 0;
}


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

const int inf = 1e9;

std::vector<int> makeKmpTable(const std::string& key) {
	const int length = key.size();
	std::vector<int> ret(length + 1);

	ret[0] = -1;
	int matched = -1;
	for (int i = 0; i < length; ++i) {
		while (matched >= 0 && key[matched] != key[i]) {
			matched = ret[matched];
		}
		++matched;
		if (key[i + 1] == key[matched]) {
			ret[i + 1] = ret[matched];
		} else {
			ret[i + 1] = matched;
		}
	}
	return ret;
}

std::vector<int> findAllKmp(const std::string& str, const std::string& key) {
	const std::vector<int> table = makeKmpTable(key);
	std::vector<int> ret;

	int pos = 0;
	int i = 0;
	while (pos + key.size() <= str.size()) {
		while (str[pos + i] == key[i]) {
			++i;
			if (i == key.size()) {
				ret.push_back(pos);
				break;
			}
		}

		pos += i - table[i];
		i = std::max(table[i], 0);
	}
	return ret;
}

int n, k;
string s, t;
bool ok[4000000];
bool used[4000000];
int sub(int st) {
  string res;
  int i = st;
  while (!used[i]) {
    used[i] = true;
    res += '0' + ok[i];
    i += k;
    i %= n;
  }
  
  res += res;
  int mx = 0;
  int cnt = 0;
  for (char c : res) {
    if (c == '1') {
      ++cnt;
      mx = max(mx, cnt);
    } else {
      cnt = 0;
    }
  }
  return mx == res.size() ? inf : mx;
}

int main() {
  string s, t;
  cin >> s >> t;
  n = s.size();
  k = t.size();
  s += s;
  while (s.size() < 2 * k) s += s;
  auto v = findAllKmp(s, t);
  for (int i : v) ok[i] = true;
  
  int mx = 0;
  for (int i = 0; i < n; ++i) {
    if (used[i]) continue;
    mx = max(mx, sub(i));
  }
  cout << (mx == inf ? -1 : mx) << endl;
}

Measured memory_bytes: 15768
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
    int N;
    string S;
    cin >> N >> S;

    vector <int> E(N), W(N);
    
    int count = 0;
    for (int i = 0; i < N; i++){
        E[i] = count;
        if (S[i] == 'E'){
            count ++;
        }
    }

    count = 0;
    for (int i = N - 1; i >= 0; i--){
        W[i] = count;
        if (S[i] == 'W'){
            count ++;
        }
    }

    int ans = N - 1;
    for (int i = 0; i < N; i++){
        if ((N - 1)-(W[i] + E[i]) < ans){
            ans = (N - 1)-(W[i] + E[i]);
        }
    }

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

Measured memory_bytes: 3076
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		String x = new String();
		while(scan.hasNext()){
			String buf = scan.nextLine();
			x = x + buf;
		}
		String lx = x.toLowerCase();
		int[] b;
		b = new int[100];
		String xl[] = lx.split("");
		String al = "abcdefghijklmnopqrstuvwxyz";
		String alf[] = al.split("");
		int i,m;
		for(i = 0; i < x.length(); i++){
			for(m = 0; m < 26; m++){
				if(xl[i].equals(alf[m]))
					b[m]++;
			}
		}
		for(i = 0; i < 26; i++){
			System.out.println(alf[i]+" : "+b[i]);
		}
		
	}
}

Measured memory_bytes: 26864
#include <stdio.h>

int main(void){
  int n, k;
  int ans = 1;
  int i = 0;
  scanf("%d%d", &n, &k);
  
  for(i = 0; i < n; i++){
    if(ans + k <= ans * 2) ans += k;
    else ans *= 2;
  }
  
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			// 文字列の入力
			String s = sc.next();
			System.out.println(s.replaceAll(".", "x"));
		}
	}

	/**
	 * 最小公倍数
	 */
	static long lcm(long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while ((temp = a % b) != 0) {
			a = b;
			b = temp;
		}
		return c / b;
	}

	/**
	 * 最大公約数
	 */
	static long gcd(long a, long b) {
		long temp;
		while ((temp = a % b) != 0) {
			a = b;
			b = temp;
		}
		return b;
	}
}


Measured memory_bytes: 23252
using System;
using System.Linq;
using System.Collections.Generic;

namespace program
{
    class Program
    {
        static void Main()
        {
          string s = Input.ScanStr();
          Console.WriteLine(s[0]=='9' || s[1]=='9' ? "Yes" : "No");
        }
    }

    static class Input
    {
        static public int ScanInt() { return int.Parse(Console.ReadLine()); }
        static public uint ScanUint() { return uint.Parse(Console.ReadLine()); }
        static public long ScanLong() { return long.Parse(Console.ReadLine()); }
        static public ulong ScanUlong() { return ulong.Parse(Console.ReadLine()); }
        static public int[] ScanIntArray() { return Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray(); }
        static public uint[] ScanUintArray() { return Console.ReadLine().Split(' ').Select(x => uint.Parse(x)).ToArray(); }
        static public long[] ScanLongArray() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray(); }
        static public ulong[] ScanUlongArray() { return Console.ReadLine().Split(' ').Select(x => ulong.Parse(x)).ToArray(); }

        static public string ScanStr() { return Console.ReadLine(); }
        static public string[] ScanStrArray() { return ScanStr().Split(' '); }
    }

    static class MyMath
    {
        public static int GCD(int a, int b)
        {
            Func<int, int, int> gcd = null;
            gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
            return a > b ? gcd(a, b) : gcd(b, a);
        }
        public static ulong GCD(ulong a, ulong b)
        {
            Func<ulong, ulong, ulong> gcd = null;
            gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
            return a > b ? gcd(a, b) : gcd(b, a);
        }
        public static int LCM(int a, int b)
        {
            return a * b / GCD(a, b);
        }
        public static ulong LCM(ulong a, ulong b)
        {
            return a * b / GCD(a, b);
        }
    }
}


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


Measured memory_bytes: 2108
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner scan = new Scanner(System.in)) {
            int count = Integer.parseInt(scan.nextLine());
            String[] nums = scan.nextLine().split(" ");

            for (int i = (count - 1); i > 0; i--) {
                System.out.print(nums[i] + " ");
            }
            System.out.println(nums[0]);
        }
    }
}



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

int w,h,C[100][100];
int diff[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

void dfs(int x,int y){
    int i;
    C[x][y]=0;
    for(i=0;i<8;i++){
        if(x+diff[i][0]>=0 && x+diff[i][0]<h && y+diff[i][1]>=0 && y+diff[i][1]<w){
            if(C[x+diff[i][0]][y+diff[i][1]]==1){
                dfs(x+diff[i][0],y+diff[i][1]);
            }
        }
    }
}

int main(){
    int i,j,ans;
    while(cin>>w>>h,w!=0||h!=0){
        ans=0;
        for(i=0;i<h;i++)for(j=0;j<w;j++)cin>>C[i][j];
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                if(C[i][j]==1){
                    dfs(i,j);
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
}


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

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;

#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(),(x).end()
constexpr auto INF = 4000000000; //4*10^9
constexpr auto MOD = 1000000007; //10^9+7


int main() {

	int n;
	cin >> n;
	vi s(100);
	int keta = 0;

	while (n) {
		s[keta] = abs(n) % (-2);
		n =(n-s[keta])/(-2);
		keta++;
	}

	if (keta == 0) cout << "0" << endl;
	else {
		rep(i, keta)cout << s[keta - i - 1];
		cout << endl;
	}
}

Measured memory_bytes: 256
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.regex.*;


public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static long cnt=0;
	public static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args) throws Exception {
//		solveA(args);
		solveB(args);
//		solveC(args);
//		solveD(args);
//		solveE(args);
//		solveF(args);
		if(in!=null){
			in.close();
		}
		pw.flush();
		pw.close();
	}

	public static void solveA(String[] args) throws Exception{
		int N= nextInt();
		int X= nextInt();
		int T= nextInt();
		pw.println(((N+X-1)/X)*T);
	}
	public static void solveB(String[] args) throws Exception{
		String N = nextString();
		int sum =0;
		for(int i=0;i<N.length();i++) {
			sum+=N.charAt(i)-'0';
		}
		if(sum%9==00) {
			pw.println("Yes");
		}else {
			pw.println("No");
		}
	}
	public static void solveC(String[] args) throws Exception{

	}

	public static void solveD(String[] args) throws Exception{

	}


	public static void solveE(String[] args) throws Exception{

	}

	public static void solveF(String[] args) throws Exception{

	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}

}



Measured memory_bytes: 29428
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program{
	const int mod=1000000007;
	const long o=1;
	static void Main(){
		Sc sc=new Sc();
		int n=sc.I;
		int[] a=new int[n+1];
		long[,] dp=new long[n+1,5];
		for(int i=1;i<=n;i++){
			a[i]=sc.I;
			for(int j=0;j<5;j++){
				if(j==0){dp[i,j]=dp[i-1,j]+a[i];}
				else{
					if(j==1||j==3){dp[i,j]=dp[i-1,j]+(a[i]!=0?(a[i]%2):2);}
					else if(j==2){dp[i,j]=dp[i-1,j]+((a[i]%2)^1);}
					else{dp[i,j]=dp[i-1,j]+a[i];}
					dp[i,j]=Math.Min(dp[i,j],dp[i,j-1]);
				}
			}
		}
		Console.WriteLine("{0}",dp[n,4]);
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
}

Measured memory_bytes: 25692
import sys
input=sys.stdin.readline

def main():
    N,Q = map(int, input().split())

    edge = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a,b = map(int, input().split())
        edge[a].append(b)
        edge[b].append(a)

    P = []
    for i in range(Q):
        x,y = map(int, input().split())
        P.append((x,y))

    V = [0]*N
    for p in P:
        V[p[0]-1] += p[1]

    parent = {1}
    done = {1}
    while parent:
        children = set()
        for p in parent:
            for i in edge[p]:
                if i not in done:
                    V[i-1] += V[p-1]
                    children.add(i)
                    done.add(i)
        parent = children

    print(' '.join(map(str, V)))

if __name__ == '__main__':
    main()


Measured memory_bytes: 102448
n,l=map(int,input().split())

if l<0:
    if l+n-1>0:
        print(int(l*n+(n-1)*n/2))
    else:
        print(int(l*(n-1)+(n-2)*(n-1)/2))
else:
    print(int((l+1)*(n-1)+(n-2)*(n-1)/2))

Measured memory_bytes: 3060
a, b = map(int, input().split())
if a % 3 == 0 or b % 3 == 0:
  print(0)
  exit()

ds = min(a, b)

s0 = (a//3) * b
s1 = (a - (a//3)) * (b//2)
s2 = (a - (a//3)) * (b - (b//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

s0 = (a//3 + 1) * b
s1 = (a - (a//3) - 1) * (b//2)
s2 = (a - (a//3) - 1) * (b - (b//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

s0 = (b//3) * a
s1 = (b - (b//3)) * (a//2)
s2 = (b - (b//3)) * (a - (a//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

s0 = (b//3 + 1) * a
s1 = (b - (b//3) - 1) * (a//2)
s2 = (b - (b//3) - 1) * (a - (a//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

print(ds)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
//---------------------------------------------------------------------------

enum TSquareState
{
	ssPlaceable,
	ssAttacked,
	ssQueen
};

typedef std::vector<std::vector<TSquareState> > TBoard;
//---------------------------------------------------------------------------

TBoard PutQueen(const TBoard& PreBoard, int Row, int Col)
{
	TBoard Board = PreBoard;

	for(int i = 0; i < 8; ++i){
		Board[Row][i] = ssAttacked;
	}
	for(int i = 0; i < 8; ++i){
		Board[i][Col] = ssAttacked;
	}
	for(int i = Row, j = Col; i < 8 && j < 8; ++i, ++j){
		Board[i][j] = ssAttacked;
	}
	for(int i = Row, j = Col; i >= 0 && j >= 0; --i, --j){
		Board[i][j] = ssAttacked;
	}
	for(int i = Row, j = Col; i < 8 && j >= 0; ++i, --j){
		Board[i][j] = ssAttacked;
	}
	for(int i = Row, j = Col; i >= 0 && j < 8; --i, ++j){
		Board[i][j] = ssAttacked;
	}
	Board[Row][Col] = ssQueen;
	return Board;
}
//---------------------------------------------------------------------------

bool PutQueens(TBoard& Board, int QueenCount)
{
	if(QueenCount == 0) return true;
	for(int i = 0; i < 8; ++i){
		for(int j = 0; j < 8; ++j){
			TBoard TempBoard = PutQueen(Board, i, j);
			if(Board[i][j] == ssPlaceable && PutQueens(TempBoard, QueenCount - 1)){
				Board = TempBoard;
				return true;
			}
		}
	}
	return false;
}
//---------------------------------------------------------------------------

void OutputEightQueens(const TBoard& Board, std::ostream& Stream)
{
	for(int i = 0; i < 8; ++i){
		for(int j = 0; j < 8; ++j){
			char Square = Board[i][j] == ssQueen ? 'Q' : '.';
			Stream << Square;
		}
		Stream << std::endl;
	}
}
//---------------------------------------------------------------------------

int main()
{
	int Count;
	std::cin >> Count;
	
	TBoard Board(8, std::vector<TSquareState>(8, ssPlaceable));
	for(int i = 0; i < Count; ++i){
		int Row, Col;
		std::cin >> Row >> Col;
		Board = PutQueen(Board, Row, Col);
	}
	PutQueens(Board, 8 - Count);
	OutputEightQueens(Board, std::cout);
	return 0;
}

Measured memory_bytes: 3168
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    ll n,q; cin >> n >> q;
    string s;cin >> s;
    vector<ll> l(q), r(q);
    rep(i,q){
        cin >> l[i] >> r[i];
    }
    vector<int> sum(n+1,0);
    rep(i,n-1){
        if(s[i] == 'A' && s[i+1] == 'C')sum[i+1]++;
        sum[i+1] += sum[i];
    }

    rep(i,q){
        cout << sum[r[i]-1] - sum[l[i]-1] << "\n";
    }
    return 0;
}

Measured memory_bytes: 3072
#include <iostream>
#include <utility>
#include <tuple>
#include <string>
#include <cstdint>
#include <vector>
#include <array>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
using i64 = int64_t;
// ax + b
struct Line {
    double a, b;
    double intersection_x(Line l) {
        return (b - l.b) / (l.a - a);
    }
    double y(double x) {
        return a * x + b;
    }
};
struct Cht {
    vector<Line> lines;
    vector<double> ixs;
    void add(double a, double b) {
        add(Line { a, b });
    }
    void add(Line l) {
        assert(lines.empty() || lines.back().a >= l.a);
        while (!lines.empty() && l.a == lines.back().a) {
            if (l.b < lines.back().b) {
                lines.pop_back();
                ixs.pop_back();
            } else {
                return;
            }
        }
        while (lines.size() >= 2) {
            double x = lines.back().intersection_x(l);
            if (ixs.back() >= x) {
                lines.pop_back();
                ixs.pop_back();
            } else {
                break;
            }
        }
        if (!lines.empty()) {
            ixs.push_back(lines.back().intersection_x(l));
        }
        lines.push_back(l);
    }
    double min_y(double x) {
        int i = lower_bound(begin(ixs), end(ixs), x) - begin(ixs);
        return lines[i].y(x);
    }
};
int n;
double c;
vector<double> h, dp;
int main() {
    cin >> n >> c;
    h.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    dp.resize(n);
    Cht cht;
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            dp[i] = h[i] * h[i] + cht.min_y(h[i]) + c;
        }
        cht.add(-2.0 * h[i], dp[i] + h[i] * h[i]);
    }
    cout << i64(dp[n - 1]) << endl;
    return 0;
}

Measured memory_bytes: 11504
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <cmath>
#include <iomanip>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef int64_t Int;
typedef uint64_t uInt;
const double pi = M_PI;

int main() {
    Int n, ans = 0, yakusuu = 0;
    cin >> n;

    for (Int i = 1; i < n + 1; i = i + 2) {
        for (Int j = 1; j < i + 1; j++) {
            if (i % j == 0) {
                yakusuu++;
            }
        }
        if (yakusuu == 8) {
            ans++;
        }
        yakusuu = 0;
    }

    cout << ans << endl;
}


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

const int MAX = 401;
const int INF = 1e6;

int main() {
  int N, ma, mb; cin >> N >> ma >> mb;
  vector<int> a(N), b(N), c(N); for (int i = 0; i < N; ++i) cin >> a[i] >> b[i] >> c[i];
  vector<vector<int>> dp(MAX, vector<int>(MAX, INF));
  dp[0][0] = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = MAX - 1; j >= a[i]; --j) {
      for (int k = MAX - 1; k >= b[i]; --k) {
        dp[j][k] = min(dp[j][k], dp[j - a[i]][k - b[i]] + c[i]);
      }
    }
  }
  int ans = INF;
  for (int i = 1; i <= 40; ++i) ans = min(ans, dp[i * ma][i * mb]);
  cout << ( (ans < INF) ? ans : -1 ) << endl;
  return 0;
}


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

int A,B;
int main() {

    cin >> A >> B;
    if(B==A){
        cout << "Draw" << endl;
    }
    else if(A==1){
        cout << "Alice" << endl;
    }
    else if(B==1){
        cout << "Bob" << endl;
    }
    else if(A>B){
        cout << "Alice" << endl;
    }
    else{
        cout << "Bob" << endl;
    }
    

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    long long int n, m;
    cin >> n;
    vector<int>d(n);
    for(int i=0; i<n; i++){
        cin >> d[i];
    }
    cin >> m;
    vector<int>t(m);
    for(int i=0; i<m; i++){
        cin >> t[i];
    }
    sort(d.begin(),d.end());
    sort(t.begin(),t.end());
    int dcount = 0;
    int tcount = 0;
    while(dcount<n && tcount<m){
        if(d[dcount] == t[tcount]){
            dcount++;
            tcount++;
        }
        else{
            dcount++;
        }
        if((n-dcount)<(m-tcount)){
            goto NO;
        }
    }
    cout << "YES" << endl;
    return 0;

    NO:
    cout << "NO" << endl;
    return 0;
}    

Measured memory_bytes: 1792
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		Scanner sc = new Scanner(System.in);

		int X = sc.nextInt();
		int Y = sc.nextInt();
		int Z = sc.nextInt();

		int ans = (X - Z) / (Y + Z);

		System.out.println(ans);
	}
}


Measured memory_bytes: 23252
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = (int)sc.next().charAt(0);
		int Y = (int)sc.next().charAt(0);
		sc.close();
		
		if(X == Y)
			System.out.println("=");
		else if(X < Y)
			System.out.println("<");
		else
			System.out.println(">");
	}
}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define MAX 200005
using namespace std;
char s[MAX];
int qzb[MAX],qzw[MAX];
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    for(int i=1; i<=n; i++)
    {
        if(s[i]=='#')
        {
            qzb[i]=qzb[i-1]+1;
            qzw[i]=qzw[i-1];
        }
        else
        {
            qzb[i]=qzb[i-1];
            qzw[i]=qzw[i-1]+1;
        }
    }
    int res=MAX;
    for(int i=1;i<=n+1;i++)//枚举分界点，右侧以及本点全为黑，左侧全为白
    {
        int ans=0;
        ans+=qzb[i-1];//左侧全为白，统计需要改的黑色点数
        ans+=qzw[n]-qzw[i-1];//右侧全为黑，统计需要改的白色节点数
        res=min(res,ans);
    }
    printf("%d\n",res);
}


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

string S;
int K;

int main() {
  cin >> S >> K;
  vector<string> vec;
  for (int i = 0; i < S.size(); ++i) {
	for (int j = 1; j <= K; ++j) {
	  string tmp = S.substr(i, j);
	  vec.push_back(tmp);
	}
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  cout << vec[K-1] << endl;
}


Measured memory_bytes: 1660
package main

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

func read (reader *bufio.Reader, n int) ([]uint32) {
	a := make([]uint32, n)
	for i:=0; i < n; i++ {
		fmt.Fscan(reader, &a[i])
	}
	return a
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var a int
	fmt.Fscan(reader, &a)
	b := read(reader, a)

	var x float64
	for i:=0; i < a; i++ {
		x = x + float64(1)/float64(b[i])
	}

	fmt.Println(1/x)
}


Measured memory_bytes: 640
n=int(input())
l=list(map(int,input().split()))
n4=sum([i%4==0 for i in l])
n2=sum([i%2==0 for i in l])-n4
if n4>=max(n//2,1):
    print("Yes")
else:
    if (n//2)*2-n4*2<=n2:
        print("Yes")
    else:print("No")

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

int main() {
	int N, M, X;
	cin >> N >> M >> X;
	int L = 0, R = 0;
	for (int i = 0; i < M; i++) {
		int A;
		cin >> A;
		(A < X ? L : R)++;
	}
	cout << min(L, R) << endl;
}

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

int main(){
  long long a,b,k;
  cin>>a>>b>>k;
  if(k>=(a+b)) cout<<"0"<<" "<<"0"<<endl;
  else if(k<=a) cout<<a-k<<" "<<b<<endl;
  else cout<<"0"<<" "<<b-k+a<<endl;
  return 0;
}


Measured memory_bytes: 256
using System;

    class Program
    {
        static void Main(string[] args)
        {
            string _strinput=Console.ReadLine();
        if (_strinput.IndexOf("A") + _strinput.IndexOf("B") == -1)
        {
            Console.WriteLine("No");
        }
        else {
            Console.WriteLine("Yes");
        }
            
        }
    }



Measured memory_bytes: 13396
import heapq
N,M=map(int,input().split())
arr=list(map(int,input().split()))
hq=[]
for i in arr:
    heapq.heappush(hq,-i)

while M>0:
    a=heapq.heappop(hq)    
    heapq.heappush(hq,a/2)
    M-=1
    #print(hq)
ans=0
for i in hq:    
    ans+=int(-i)
    
print(ans)

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

const int MOD = 1e9 + 7; int pot[26];

int main(){
	int N; string str; cin >> N >> str;
	for(auto t : str) pot[t - 'a']++;
	int tms = 1; for(int i = 0 ; i < 26 ; ++i) tms = 1ll * tms * (pot[i] + 1) % MOD;
	cout << tms - 1; return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
int main(){
	int a,n=0;
	for(int i=0;i<4;i++){
		scanf("%d",&a);
		n+=a;
	}
	a=n%60;
	n/=60;
	printf("%d\n%d\n",n,a);
	return 0;
}

Measured memory_bytes: 1028
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
 
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(20);

  int w, h, x, y;
  cin >> w >> h >> x >> y;

  cout << w * h / 2.0 SP (x + x == w && y + y == h) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int n,i,j;
  int gu=0;
  int wari=0;
  scanf("%d",&n);
  int a[n];
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  for(j=0;j<n;j++){
    if(a[j]%2==0){
      gu += 1;
      if(a[j]%3==0||a[j]%5==0)
        wari += 1;
    } 
  }
    if(gu == wari)
      printf("APPROVED");
    else
      printf("DENIED");  
  return 0;
}
    

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

int N;

int main() {
  cin >> N;

  cout << N * N * N << endl;
  return 0;
}


Measured memory_bytes: 256
// AOJ 2351 Closest Segment Pair
// 2018.3.17 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define INF     1e7
#define EPS     1e-5
#define RANGE	30
#define SIN     0.70710678118654752440084436210485    // Sin(45)
#define COS     0.70710678118654752440084436210485    // Cos(45)
#define SINCOS  SIN

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

typedef struct { double x1, y1, x2, y2; } S;
S seg[5105];

typedef struct { double x, y; } PP;
PP vsub(PP p1, PP p2) { PP r; r.x = p1.x - p2.x, r.y = p1.y - p2.y; return r; }
double dot(PP a, PP b) { return a.x * b.x + a.y * b.y; }
double cross(PP a, PP b) { return a.x * b.y - a.y * b.x; }
double norm(PP a) { return a.x * a.x + a.y * a.y; }
double vabs(PP a) { return hypot(a.x, a.y); }
int ccw(PP p0, PP p1, PP p2) { PP a, b;	double t;
	a = vsub(p1, p0), b = vsub(p2, p0), t = cross(a, b);
	if (t >  EPS) return 1;	if (t < -EPS) return -1;
	if (dot(a, b) < -EPS) return 2;	if (norm(a) < norm(b)) return -2;
	return 0;
}
int is_intersectSS(PP s1s, PP s1e, PP s2s, PP s2e)
{
	return ccw(s1s, s1e, s2s) * ccw(s1s, s1e, s2e) <= 0 &&
		   ccw(s2s, s2e, s1s) * ccw(s2s, s2e, s1e) <= 0;
}
double distanceLP(PP ss, PP se, PP p) {
	return fabs(cross(vsub(se, ss), vsub(p, ss)) / vabs(vsub(se, ss))); }
double distanceSP(PP ss, PP se, PP p)
{
	if (dot(vsub(se, ss), vsub(p, ss)) < 0) return vabs(vsub(p, ss));
	if (dot(vsub(ss, se), vsub(p, se)) < 0) return vabs(vsub(p, se));
	return distanceLP(ss, se, p);
}
double distanceSS(PP s1s, PP s1e, PP s2s, PP s2e)
{
	double res, x;
	if (is_intersectSS(s1s, s1e, s2s, s2e)) return 0;
	res = distanceSP(s1s, s1e, s2s);
	x = distanceSP(s1s, s1e, s2e); if (x < res) res = x;
	x = distanceSP(s2s, s2e, s1s); if (x < res) res = x;
	x = distanceSP(s2s, s2e, s1e); if (x < res) res = x;
	return res;
}

int cmp(S *a, S *b)
{
	if (fabs(a->x1 - b->x1) < EPS) {
		if (fabs(a->y1 - b->y1) < EPS) return 0;
		if (a->y1 < b->y1) return -1; return 1;
	}
	if (a->x1 < b->x1) return -1; return 1;
}

int main()
{
	int N, i, j, lim;
	int x1, y1, x2, y2;
	double x, ans;
	PP s1s, s1e, s2s, s2e;

	N = in();
	if (N > 5100) { puts("0"); return 0; }
	for (i = 0; i < N; i++) {
		x1 = in(), y1 = in(), x2 = in(), y2 = in();
		seg[i].x1 = (x1 - y1) * SINCOS, seg[i].y1 = (x1 + y1) * SINCOS;
		seg[i].x2 = (x2 - y2) * SINCOS, seg[i].y2 = (x2 + y2) * SINCOS;
	}
	qsort(seg, N, sizeof(S), cmp);

	ans = INF;
	for (i = 0; i < N; i++) {
		s1s.x = seg[i].x1, s1s.y = seg[i].y1, s1e.x = seg[i].x2, s1e.y = seg[i].y2;
		lim = i+RANGE; if (lim > N) lim = N; 
		for (j = i+1; j < lim; j++) {
			s2s.x = seg[j].x1, s2s.y = seg[j].y1, s2e.x = seg[j].x2, s2e.y = seg[j].y2;
			x = distanceSS(s1s, s1e, s2s, s2e);
			if (x == 0) { ans = 0; goto done; }
			if (x < ans) ans = x;
		}
	}
done:
	printf("%.8lf\n", ans);
	return 0;
}


Measured memory_bytes: 2092
#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

const int kNil = -1;

enum class Color {
  kWhite,
  kGrey,
  kBlack,
};

template <class T>
struct Edge {
  using w_type = T;
  Edge(int u, int v, w_type w): u(u), v(v), w(w) { }
  int u, v;
  w_type w;
  bool operator<(const Edge<T> & rhs) const {
    if (w != rhs.w) { return w < rhs.w; }
    if (u != rhs.u) { return u < rhs.u; }
    return v < rhs.v;
  }
};

template <class Edge>
void GetOrder(const typename vector<Edge>::size_type node_now,
       const vector<vector<Edge>> & adjacency_list,
       vector<Color> & color,
       stack<typename vector<Edge>::size_type> & order) {

  color[node_now] = Color::kGrey;
  for (const auto & e: adjacency_list[node_now]) {
    if (color[e.v] == Color::kWhite) {
      GetOrder(e.v, adjacency_list, color, order);
    }
  }
  color[node_now] = Color::kBlack;
  order.push(node_now);
}

template <class Edge>
void DFSVisit(const typename vector<Edge>::size_type node_now,
       const vector<vector<Edge>> & adjacency_list,
       vector<Color> & color,
       vector<typename vector<Edge>::size_type> & component,
       unsigned & component_num) {
  color[node_now] = Color::kGrey;
  for (const auto & e: adjacency_list[node_now]) {
    if (color[e.v] == Color::kWhite) {
      DFSVisit(e.v, adjacency_list, color, component, component_num);
    }
  }
  color[node_now] = Color::kBlack;
  component[node_now] = component_num;
}

template <class Edge>
decltype(auto) StronglyConnectedComponent(const vector<Edge> & edges,
                 typename vector<Edge>::size_type node_num) {
  using size_type = typename vector<Edge>::size_type;

  vector<vector<Edge>> adjacency_list(node_num, vector<Edge>());
  for (const auto & e: edges) {
    adjacency_list[e.u].push_back(e);
  }

  vector<Color> color(node_num, Color::kWhite);
  stack<size_type> order;
  for (unsigned i = 0; i < node_num; ++i) {
    if (color[i] == Color::kWhite) {
      GetOrder(i, adjacency_list, color, order);
    }
  }

  vector<vector<Edge>> adjacency_list_reversed(node_num, vector<Edge>());
  for (const auto & e: edges) {
    adjacency_list_reversed[e.v].emplace_back(e.v, e.u, e.w);
  }
  color = vector<Color>(node_num, Color::kWhite);
  unsigned component_num = 0;
  vector<size_type> component(node_num);
  while (!order.empty()) {
    auto u = order.top();
    order.pop();
    if (color[u] == Color::kWhite) {
      DFSVisit(u, adjacency_list_reversed, color, component, component_num);
      ++component_num;
    }
  }

  return component;
}

int main(int argc, char const *argv[]) {
  using w_type = unsigned;

  vector<Edge<w_type>> edges;
  unsigned V, E;
  cin >> V >> E;
  for (unsigned i = 0; i < E; ++i) {
    unsigned u, v;
    w_type w;
    cin >> u >> v;
    edges.emplace_back(u, v, 1);
  }

  auto component = StronglyConnectedComponent(edges, V);
  unsigned q, u, v;
  cin >> q;
  for (unsigned i = 0; i < q; ++i) {
    cin >> u >> v;
    if (component[u] == component[v]) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 5128