akhauriyash/Code-Regression huggingface dataset:
/* BISMILLAHIR RAHMANIR RAHIM */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s; cin >> s;
    int n = s.length();
    auto isPal = [](string s) {
        for(int i = 0, n = s.length(); i < n / 2; i++) {
            if( s[i] != s[n - i - 1] ) return false;
        }
        return true;
    };
    if( !isPal(s) ) {
        cout << "No";
        exit(0);
    }
    string s1 = s.substr(0, (n - 1) / 2);
    if( !isPal(s1) ) {
        cout << "No";
        exit(0);
    }
    cout << "Yes";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
using namespace std;
struct UnionFind {
  ll size,*par,*rk;
  UnionFind(ll sz){
    size=sz;
    par=new ll[size]; REP(i,size) par[i]=i;
    rk=new ll[size]; REP(i,size) rk[i]=0;
  }
  ll find(ll x){
    if(par[x]==x) return x;
    else return par[x]=find(par[x]);
  }
  void unite(ll x,ll y){
    x=find(x); y=find(y);
    if(rk[x]>rk[y]) par[y]=x;
    else if(rk[x]<rk[y]) par[x]=y;
    else {par[x]=y;rk[y]++;}
  }
  bool same(ll x,ll y) {
    return find(x)==find(y);
  }
};

int main() {
  int n, q; cin >> n >> q;
  UnionFind uf(n);
  for(int i = 0; i < q; i++) {
    int com, x, y; cin >> com >> x >> y;
    if(com == 0) uf.unite(x, y);
    else cout << (uf.same(x, y) ? 1 : 0) << endl;
  }

}

// verified

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

using namespace std;
using ll = long long;
using ld = long double;

//#define int long long
//signed main(){
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b;
    cin >> a >> b;
    cout << max({a+b,a-b,a*b}) << "\n";

    return 0;
}

Measured memory_bytes: 3560
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<stack>
#include<sstream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<list>
#include<numeric>
typedef long long ll;

#define pi 3.14159265358979323846
#define VI vector<int>
#define VLL vector<long long>
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
using namespace std;
template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}

template<typename T>
T binarysearch(vector<T> A, T key) {
	ll left = 0;ll right = 4;ll mid;
	while (left < right) {
		mid = (left + right) / 2;
		if (key == A[mid]) return 1;
		if (key > A[mid]) left = mid + 1;
		else if (key < A[mid]) right = mid;
	}
	return 0;
}

template<typename T>
T finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}
ll frac(ll n)//階乗
{
	if (n == 0) {
		return 1;
	}
	return (n * frac(n - 1)) % MOD;
}

template<typename T>
T keta(T a) {
	ll kazu = 1;
	while (1) {
		if (a / 10 != 0) { a /= 10;kazu++; }
		else break;
	}
	return kazu;
}//桁数


template<typename T>
T nCr(ll n, T r) {
	ll ans = 1;
	for (int i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (int i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
/*char r[4];
int yaju[4];
char op[3];
int sum = 0;
scanf("%s", r);
for (int i = 0;i < 4;i++) {
	yaju[i] = r[i] - '0';
}
*/
int main() {
	ll X,Y,Z;cin >> X>>Y>>Z;
	bool ok = true;
	cout << Z<<" " << X<<" " << Y;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
template <class T> void cumulative_sum( T array, size_t N );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;

typedef struct {
	vector <int> to;
	int cost;
	bool is_visited;
} edge;

int main( void ){
	int N; cin >> N;
	int hoge = 0;
	rep( i, 0, N ){
		char c; cin >> c;
		if (c == 'P')
			hoge |= 1;
		else if (c == 'G')
			hoge |= 2;
		else if (c == 'W')
			hoge |= 4;
		else
			hoge |= 8;
	}
	int cnt = 0;
	rep(i,0,4){
		cnt+= (bool)(hoge & 1<<i);
	}
	if (cnt == 4 )
		cout << "Four\n";
	else
		cout << "Three\n";
}

int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
template <class T> void cumulative_sum( T array, size_t N ) {
	rep( i, 1, N + 1 ){
		array[ i ] += array[ i - 1 ];
	}
}
template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String[] list = new String[s.length()];
        int[] l = new int[s.length()+1];
        list = s.split("");
        int count =0;
        for( int i =0; i <s.length(); i++){
         if(list[i].equals("A") ||list[i].equals("G")||list[i].equals("C")||list[i].equals("T") ){
             count++;
         }else{
             l[i] = count;
             count =0;
         }

        }
        l[s.length()] = count;
        Arrays.sort(l);
        System.out.println(l[s.length()]);
    }
}

Measured memory_bytes: 22100
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(ll i=a;i<b;i++)
inline constexpr int intpow(ll a,ll b){
    if(b==0) return 1;
    ll ans=intpow(a,b/2);
    return ans*ans*(b&1?a:1);
}
int main(){
    string s;
    cin>>s;
    int k;
    cin>>k;
    int i=0,cnt=0;
    while(s[i]=='1') {
        cnt++;
        i=i+1;
    }
    if(cnt<k) cout<<s[cnt];
    else cout<<1;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define N 1003
int Q[N*N],HEAD[N*N],Ne[N*N],E[N*N],V[N*N];
int To[N*N],b,n,Num[N][N],A[N],cnt,t,h,q;
void ADD(int s,int e) {
	Ne[++b]=HEAD[s],HEAD[s]=b,E[b]=e,To[e]++;
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			Num[i][j]=Num[j][i]=i*n+j;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<n; j++) {
			scanf("%d",&A[j]);
			if(j^1)ADD(Num[i][A[j-1]],Num[i][A[j]]);
		}
	}
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++) {
			cnt++;
			if(To[Num[i][j]]==0)Q[++t]=Num[i][j],V[Num[i][j]]=1;
		}
	while(h<t) {
		q=Q[++h];
		for(int z=HEAD[q]; z; z=Ne[z]) {
			To[E[z]]--;
			if(!To[E[z]])V[E[z]]=V[q]+1,Q[++t]=E[z];
		}
	}
	if(t!=cnt)puts("-1");
	else printf("%d\n",V[Q[t]]);
	return 0;
}


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

using i64 = int64_t;

template <typename T, typename E> class SegmentTree {
  private:
    int n;
    std::vector<T> node;
    const std::function<T(T, T)> query_func;
    const std::function<T(T, E)> update_func;
    const T identity;

  public:
    SegmentTree() = default;

    SegmentTree(int size, std::function<T(T, T)> query_func,
                std::function<T(T, E)> update_func, T identity,
                std::vector<T> v = std::vector<T>())
        : query_func(query_func), update_func(update_func), identity(identity) {
        n = 1;
        while (n < size)
            n *= 2;
        node.resize(2 * n - 1, identity);
        if (size == v.size())
            build(size, v);
    }

    void build(int size, std::vector<T> v) {
        for (int i = 0; i < size; ++i)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; --i)
            node[i] = query_func(node[2 * i + 1], node[2 * i + 2]);
    }

    void update(int x, E val) {
        x += n - 1;

        node[x] = update_func(node[x], val);
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = query_func(node[2 * x + 1], node[2 * x + 2]);
        }
    }

    T query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0)
            r = n;

        if (r <= a || b <= l)
            return identity;

        if (a <= l && r <= b)
            return node[k];

        T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return query_func(vl, vr);
    }
};

int pop_count(int n){
    int res = 0;
    while(n > 0){
        res += (n&1);
        n >>= 1;
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    SegmentTree<int, int> sgt(
        n,
        [](int x, int y){return (x|y);},
        [](int x, int y){return y;},
        0
    );
    string s;
    cin >> s;
    for(int i=0;i<n;++i){
        sgt.update(i, (1<<((int)(s[i]-'a'))));
    }
    int Q;
    cin >> Q;
    for(int q=0;q<Q;++q){
        int type;
        cin >> type;
        if(type == 1){
            int i;
            char c;
            cin >> i >> c;
            i--;
            sgt.update(i, (1<<((int)(c-'a'))));
        }else{
            int l, r;
            cin >> l >> r;
            l--; r--;
            cout << pop_count(sgt.query(l, r+1)) << endl;
        }
    }

    return 0;
}

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

int main(){
    int N,M;
    cin >> N >> M;
    int L[M];
    int R[M];

    int A = 0;
    int B = 100010;
    for(int i=0; i<M; i++){
        cin >> L[i] >> R[i];
        if(A<L[i]) A=L[i];
        if(R[i]<B) B=R[i];
    }

    if(B-A+1<0){cout << '0' << endl;
    }else{
    cout << B-A+1 << endl;}
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz size()
#define pb push_back 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;
const ll INF=1000000000000000;

vector<ll> pw2(51,1); vector<ll> pw10(19,1);
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll mid(ll x,ll y,ll z){return x>y?y>=z?y:min(z,x):x>=z?x:min(y,z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll myceil(ll x,ll y){if(x<=y) return 1;else if(x%y==0) return x/y;else return x/y+1;}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> divisor(ll x){vector<ll> div;
	for(ll i=1;i*i<=x;i++){if(x%i==0){div.pb(i);if(i*i!=x)div.pb(x/i);}}
	sort(div.bg,div.ed);return div;}

int main(){
	//rep1(i,50) pw2[i]=2*pw2[i-1];
	//rep1(i,18) pw10[i]=10*pw10[i-1];
  ll A; cin>>A;
    string s; cin>>s;
    if(A>=3200) cout<<s;
    else cout<<"red";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[3][3],x,i;
	cin>>a[0][0]>>a[0][1]>>a[1][1];
	x=a[1][1]*3;
	a[0][2]=x-a[0][0]-a[0][1];
	a[2][1]=x-a[0][1]-a[1][1];
	a[2][2]=x-a[0][0]-a[1][1];
	a[2][0]=x-a[1][1]-a[0][2];
	a[1][0]=x-a[0][0]-a[2][0];
	a[1][2]=x-a[0][2]-a[2][2];
	for(i=0;i<3;i++){
		cout<<a[i][0]<<" "<<a[i][1]<<" "<<a[i][2]<<endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  string str;
  while(getline(cin,str)){
    while(str.find("the")==-1&&
	  str.find("this")==-1&&
	  str.find("that")==-1){
      int i;
      for(i=0;i<str.size();i++){
	if('a'<=str[i]&&str[i]<'z') str[i]++;
	else if(str[i]=='z') str[i]='a';
      }
    }
    cout << str << endl;
  }
  return 0;
}



Measured memory_bytes: 3152
N = int(input())
D, X = list(map(int, input().split()))
A = []
for _ in range(N):
    A += [int(input())]

ate_amount = []
for i in range(N):
    ate_amount += [int((D - 1) // A[i]) + 1]

print(X + sum(ate_amount))

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    int n = 0, l = 0;
    std::cin >> n >> l;
    std::cin.ignore();
    std::vector<std::string> v;
    while (n--) {
        std::string s;
        std::getline(std::cin, s);
        v.emplace_back(s);
    }

    std::sort(v.begin(), v.end());
    for (const std::string& s : v)
        std::cout << s;
    std::cout << std::endl;

    return 0;
}


Measured memory_bytes: 3612
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int a = scan.nextInt();
    int b = scan.nextInt();
    int c = scan.nextInt();
    int k = scan.nextInt();

    int count = 0;
    while (a >= b){
      b*=2;
      count += 1;
    }

    while (b>=c){
      c*=2;
      count+=1;
    }

    if (count <= k){
      System.out.println("Yes");
    }
    else{
      System.out.println("No");
    }

  }
}


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

int main(void){
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int x3 = x2 - (y2-y1);
    int y3 = y2 + (x2-x1);;

    int x4 = x1 + (x3-x2);
    int y4 = y1 + (y3-y2);

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;

    return 0;
}

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

using namespace std;
typedef unsigned long ul;
typedef pair<ul, ul> P;

int main(){
    int A[3];

    rep(i, 3) cin >> A[i];

    sort(A, A + 3);
    
    cout << A[0] + A[1] + 10 * A[2] << endl;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<int> A(N + 2);
    A[0] = 0;
    FOR(i, 1, N + 1) cin >> A[i];
    A[N + 1] = 0;
    int all = 0;
    rep(i, N + 1) {
        all += abs(A[i] - A[i + 1]);
    }
    FOR(i, 1, N + 1) {
        cout << all - abs(A[i] - A[i - 1]) - abs(A[i] - A[i + 1]) + abs(A[i - 1] - A[i + 1]) << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#define ll int64_t
#define REP(i, n) for (ll i=0; i<n; i++)
using namespace std;

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

    int H, W;
    cin >> H >> W;
    vector<vector<char>> A(H, vector<char>(W));
    REP (i, H) {
        REP (j, W) {
            cin >> A[i][j];
        }
    }

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    queue<pair<int, int>> Q;
    vector<vector<ll>> dist(H, vector<ll>(W, -1));

    REP (i, H) {
        REP (j, W) {
            if (A[i][j] == '#') {
                dist[i][j] = 0;
                Q.push(make_pair(i, j));
            }
        }
    }

    while (!Q.empty()) {
        auto a = Q.front();
        Q.pop();
        REP (i, 4) {
            int y = a.first + dy[i];
            int x = a.second + dx[i];
            if ((y<0) || (y>H-1) || (x<0) || (x>W-1)) continue;
            if (dist[y][x] == -1) {
                Q.push(make_pair(y, x));
                dist[y][x] = dist[a.first][a.second] + 1;
            }
        }
    }

    ll ans = 0;
    REP (i, H) {
        REP (j, W) {
            ans = max(ans, dist[i][j]);
        }
    }

    cout << ans << "\n";

}

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

ll INF = 1e18;

int main()
{
  int n;
  cin >> n;
  
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  
  if(a[0] == 0)
  {
    cout << 0 << endl;
    return 0;
  }
  
  ll res = 1;
  rep(i,n)
  {
    ll t = a[i];
    
    if(t > INF / res)
    {
      cout << -1 << endl;
      return 0;
    }
    res *= t;
    //cout << t << " " << res << endl;
  }
  
  cout << res << endl;
  
  
  return 0;
}

Measured memory_bytes: 4056
n = int(input())
l = list(map(int, input().split()))
l.sort()

cnt = 0
for i in range(n):
    for j in range(i + 1 , n):
        for k in range(j + 1, n):
            if len(set([l[i], l[j], l[k]])) == 3:
                if l[i] + l[j] > l[k]:
                    cnt += 1
print(cnt)


Measured memory_bytes: 9180
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top,s[1000];

int main(){
  int a,b;
  top=0;
  char s[100];

  while(scanf("%s",s)!=EOF){
    if(s[0]=='+'){
      a=pop();
      b=pop();
      push(a+b);
    }else if(s[0]=='-'){
      b=pop();
      a=pop();
      push(a-b);
    }else if(s[0]=='*'){
      a=pop();
      b=pop();
      push(a*b);
    }else{
      push(atoi(s));
    }
  }

  printf("%d\n",pop());

  return 0;
}

void push(int x){
  s[++top]=x;
}

int pop(){
  top--;
  return s[top+1];
}

Measured memory_bytes: 548
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	const maxWord = (1 << 30)
	buf := []byte{}
	sc.Buffer(buf, maxWord)
	sc.Split(bufio.ScanWords)
}

func input() string {
	sc.Scan()
	return sc.Text()
}

func min(x []int) int {
	minv := x[0]
	for _, v := range x {
		if v < minv {
			minv = v
		}
	}
	return minv
}

func main() {
	n, _ := strconv.Atoi(input())
	a, _ := strconv.Atoi(input())
	b, _ := strconv.Atoi(input())
	c, _ := strconv.Atoi(input())
	d, _ := strconv.Atoi(input())
	e, _ := strconv.Atoi(input())
	limitStep := min([]int{a, b, c, d, e})
	ans := (n-1)/limitStep + 5
	fmt.Println(ans)
}


Measured memory_bytes: 640
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <cassert>
#include <tuple>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll INF = 1e15;


class UnionFind {
public:
	vector<int> rank;
	UnionFind(int N) : rank(N, -1) {}
	int root(int x) {
		if (rank[x] < 0)
			return x;
		else
			return rank[x] = root(rank[x]);
	}

	bool find(int a, int b) {
		return root(a) == root(b);
	}

	void uni(int a, int b) {
		a = root(a); b = root(b);
		if (a < b)
			rank[b] = a;
		else if (b < a)
			rank[a] = b;
		else {
			rank[b] = a;
			rank[a]--;
		}
	}
};

using Weight = ll;
class Edge {
public:
	int s, d;
	Weight w;
	Edge() : s(0), d(0), w(0) {}
	Edge(int s, int d, Weight w) : s(s), d(d), w(w) {}
	bool operator < (const Edge &e) const {
		return w != e.w ? w < e.w :
			   s != e.s ? s < e.s :
			   d < e.d;
	}
};
using Graph = vector<vector<Edge>>;

// 最小全域森とそのコストを返す O(ElogE)
pair<Weight, Graph> kruskal(Graph& g) {
	UnionFind uf(g.size());
	Weight cost = 0;
	Graph f(g.size());
	vector<Edge> es;
	for (auto&& ee : g)
		for (auto&& e : ee)
			es.push_back(e);
	sort(es.begin(), es.end());
	for (auto&& e : es) {
		if (uf.find(e.s, e.d))
			continue;
		uf.uni(e.s, e.d);
		cost += e.w;
		f[e.s].push_back(e);
	}
	return make_pair(cost, f);
}

using P = pair<ll, ll>;
int main() {
	ll N;
	cin >> N;
	Graph g(N);
	vector<P> xv(N);
	vector<P> yv(N);
	for (int i = 0;i < N;i++) {
		ll x, y;
		cin >> x >> y;
		xv[i] = P(x, i);
		yv[i] = P(y, i);
	}
	sort(xv.begin(), xv.end());
	sort(yv.begin(), yv.end());
	for (int i = 0;i < N;i++) {
		if (i > 0) {
			g[xv[i].second].push_back(Edge(xv[i].second, xv[i - 1].second, abs(xv[i].first - xv[i - 1].first)));
			g[yv[i].second].push_back(Edge(yv[i].second, yv[i - 1].second, abs(yv[i].first - yv[i - 1].first)));
		}
		if (i < N - 1) {
			g[xv[i].second].push_back(Edge(xv[i].second, xv[i + 1].second, abs(xv[i].first - xv[i + 1].first)));
			g[yv[i].second].push_back(Edge(yv[i].second, yv[i + 1].second, abs(yv[i].first - yv[i + 1].first)));
		}
	}
	Weight cost;
	Graph f;
	tie(cost, f) = kruskal(g);
	cout << cost << endl;
	return 0;
}


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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	int n;
	cin >> n;
	vector<long long> sum(n + 1);
	for(int i = 1; i <= n; i++) {
		long long a;
		cin >> a;
		sum[i] = sum[i - 1] + a;
	}
	long long ans = 1e18;
	for(int i = 1; i < n; i++) {
		ans = min(ans, abs(sum[i] - (sum[n] - sum[i])));
	}
	cout << ans << endl;
	return 0;	
}


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

int a[501];
int main(){
    int n;
    cin>>n;
    rep(i,n) cin>>a[i];
    rep(i,n){
        int l=i*2+1,r=i*2+2;
        cout<<"node "<<i+1<<": key = "<<a[i]<<", ";
        if(i!=0) cout<<"parent key = "<<a[(i-1)/2]<<", ";
        if(l<n) cout<<"left key = "<<a[l]<<", ";
        if(r<n) cout<<"right key = "<<a[r]<<", ";
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <iostream>

using namespace std;

int n , m , k;
char c[10][10];
int main(){
	cin >> n >> m >> k;
	for(int i = 0 ; i < n ; ++ i)
		for(int j = 0 ; j < m ; ++ j)
			cin >> c[i][j];
	int ans = 0;
	for(int i = 0 ; i < (1 << n) ; ++ i)
		for(int j = 0 ; j < (1 << m) ; ++ j){
			int cnt = 0;
			for(int x = 0 ; x < n ; ++ x)
				for(int y = 0 ; y < m ; ++ y)
					if(c[x][y] == '#' && ((1 << x) & i) && ((1 << y) & j))
						cnt ++;
			if(cnt == k)
				ans ++;
		}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
c = 3.times.map { gets.split.map(&:to_i) }

if (c[0].map {|ci| ci - c[0][0]} == c[1].map {|ci| ci - c[1][0]}) && (c[0].map {|ci| ci - c[0][0]} == c[2].map {|ci| ci - c[2][0]}) \
  && (c.transpose[0].map {|ci| ci - c.transpose[0][0]} == c.transpose[1].map {|ci| ci - c.transpose[1][0]}) && (c.transpose[0].map {|ci| ci - c.transpose[0][0]} == c.transpose[2].map {|ci| ci - c.transpose[2][0]})
    puts 'Yes'
else
  puts 'No'
end

Measured memory_bytes: 3836
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]

# 白から黒に来るときだけ+1すればOK
dp = [[INF] * W for _ in range(H)]
dp[0][0] = 1 if S[0][0] == '#' else 0
for h, w in itertools.product(range(H), range(W)):
    for ph, pw in [(h - 1, w), (h, w - 1)]:
        if 0 <= ph < H and 0 <= pw < W:
            d = int(S[ph][pw] == '.' and S[h][w] == '#')
            dp[h][w] = min(dp[h][w], dp[ph][pw] + d)
print(dp[-1][-1])


Measured memory_bytes: 3188
import java.util.*;class Main{public static void main(String[]z){double[]d=new double[10];d[0]=1;for(int i=0;i<9;i++)d[0]+=d[i+1]=i%2<1?d[i]*2:d[i]/3;for(Scanner s=new Scanner(System.in);s.hasNext();)System.out.println(s.nextDouble()*d[0]);}}

Measured memory_bytes: 12000
ABC = [int(x) for x in input().split()]
#複数の整数を入力する場合はこうでABCという名のリストにしてる
ABC.sort()
#ABCリストを昇順で書き換える
answer = ABC[-1]*10 + sum(ABC[:2])
#昇順の時、一番後ろに来るのが最大値なのでそれを10倍。残り二つ(前二つ)を足す。
print(answer)


Measured memory_bytes: 2940
s = str(input())
l = []
for char in s:
  l.append(char)
l.sort()
if len(l)%2 == 1:
  print('No')
else:
  flag = True
  for i in range(0,len(l),2):
    if l[i] != l[i+1]:
      flag = False
      break
  if flag:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] sheet = new int[3][3];
        boolean[][] result = new boolean[3][3];

        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 3; i++) {
            Integer[] vals = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
            for (int j = 0; j < 3; j++) {
                sheet[i][j] = vals[j];
            }
        }
        int N = Integer.parseInt(sc.nextLine());

        for (int i = 0; i < N; i++) {
            int val = Integer.parseInt(sc.nextLine());
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    int sheetVal = sheet[j][k];
                    if (sheetVal == val) {
                        result[j][k] = true;
                    }
                }
            }
        }

        sc.close();

        if ((result[0][0] == true && result[0][1] == true && result[0][2] == true)
                || (result[1][0] == true && result[1][1] == true && result[1][2] == true)
                || (result[2][0] == true && result[2][1] == true && result[2][2] == true)
                || (result[0][0] == true && result[1][0] == true && result[2][0] == true)
                || (result[0][1] == true && result[1][1] == true && result[2][1] == true)
                || (result[0][2] == true && result[1][2] == true && result[2][2] == true)
                || (result[0][0] == true && result[1][1] == true && result[2][2] == true)
                || (result[0][2] == true && result[1][1] == true && result[2][0] == true)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 28500
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("fma,avx")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    cout << (n % 1000 == 0 ? 0 : (1000 - (n % 1000))) << "\n";

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define all(x) x.begin(),x.end()
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}

const int INF=INT_MAX;
const ld PI=acos(-1);//3.1415926535897932384626433
const ld E=2.71828183;
const int MOD=1e9+7;

vi bfs(vector<vi>adj,int src){
    //adjacency list, not-weighted, possibly directed ,src is 1-indexed, adj[0].size()=0!!!
    //for n vertices, adj.size()=n+1. (constructed via push_back() ).

    queue<int>q;
    q.push(src);
    vi dst(adj.size(),INF);
    dst[src]=0;
    while(!q.empty()){
        int c=q.front();
        q.pop();
        for(int nbr:adj[c]){
            if(dst[nbr]==INF){
                dst[nbr]=dst[c]+1;
                q.push(nbr);
            }
        }
    }
    return dst;
}
vi bfsParents(vector<vi>adj,int src){
    vi parents=vi(adj.size(),INF);
    parents[src]=-1;
    queue<int>q;
    q.push(src);
    vi dst(adj.size(),INF);
    dst[src]=0;
    while(!q.empty()){
        int c=q.front();
        q.pop();
        for(int nbr:adj[c]){
            if(dst[nbr]==INF){
                parents[nbr]=c;
                dst[nbr]=dst[c]+1;
                q.push(nbr);
            }
        }
    }
    return parents;
}
vi shortestPath(vector<vi>adj,int src,int dst){
    vi bfsParetns=bfsParents(adj,src);
    vi ans;
    while(src!=dst){
        if(bfsParetns[src]==INF)
            return {};
        ans.push_back(src);
        src=bfsParetns[src];
    }
    return ans;
}
int powMod(int base,int exp,int mod){
    //(base^exp) %mod
    int ans=1;
    for(int i=0; i<exp; i++)
        ans=((ans%mod)*(base%mod))%mod;
    return ans;
}
vi divisorsOf(int n){
    //vector of divisors of n (inc. 1 , excl.n)
    vi ans;
    for(int i=1; i*i<=n; i++){
        if(n%i==0)
            ans.push_back(i);
        if(i*i!=n && i!=1)
            ans.push_back(n/i);
    }
    return ans;
}
int gcd(int a,int b){
    if(a%b==0)
        return b;
    else
        return gcd(b,a%b);
}

ld log (ld a,ld b){return log(b)/log(a);}
ll power(ll base, ll exp){
    ll res=1;
    while(exp){
        exp--;
        res*=base;
    }
    return res;
}
void solve();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}
void solve (){
    int a,b;
    cin >> a >> b;
    vi v(3);
    v[a-1]=1;
    v[b-1]=1;
    for(int i=0; i<3; i++)
        if(v[i]==0)
            cout << i+1 << "\n";
}

Measured memory_bytes: 3628
from collections import deque
h,w = map(int,input().split())
l = [list(input()) for i in range(h)]
h1,w1= 0,0
#"."のかず
cou = 0
for i in l:
  for j in i:
    if j=='.':
      cou += 1
k = [[-1]*w for i in range(h)]
def bfs(a,b):
  d = deque()
  d.append([a,b])
  k[a][b]=0
  while d:
    c,e = d.popleft()
    m = [1,0,-1,0]
    n = [0,1,0,-1]
    for i in range(4):
      c1 = c+m[i]
      e1 = e+n[i]
      if 0<=c1 and 0<=e1 and c1<h and e1<w:
        if l[c1][e1]=="." and k[c1][e1]==-1:
          k[c1][e1]  =k[c][e] +1
          d.append([c1,e1])
  return k
bfs(h1,w1)        
if k[-1][-1]!=-1:
  print(cou-k[-1][-1]-1)
else:
  print(-1)

Measured memory_bytes: 9348
import numpy as np

k,n = map(int,input().split())
A = list(map(int, input().split()))
A = np.array(A)
B = np.diff(A, n=1)

B_ = (A[0])+(k-A[n-1])
B_ans = np.append(B,B_)
ans = np.argmax(B_ans)

print(k - B_ans[ans])

Measured memory_bytes: 34140
#include<iostream>
using namespace std;
int main() {
	int a,b,c,x,ans=0;
	cin>>a>>b>>c>>x;
	for(int i=0;i<=a;i++)
	    for(int j=0;j<=b;j++)
	        for(int k=0;k<=c;k++){
	            if(500*i+j*100+k*50==x)
	                ans++;
	            if(500*i+j*100+k*50>x)
	                break;
	        }
	cout<<ans;       
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner io = new Scanner(System.in);
		int a = io.nextInt();
		int b = io.nextInt();
		if(a==1) a=14;
		if(b==1) b=14;
		System.out.println((a==b)?"Draw":
							(a>b)?"Alice":"Bob");
	}
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
template<class T> bool isIn(T a,vector<T> v){ for(T x:v){ if(a==x){return true;}} return false;}
string strReplace(string s,string target, string replacement){
    if (!target.empty()) {
      std::string::size_type pos = 0;
      while ((pos = s.find(target, pos)) != std::string::npos) {
        s.replace(pos, target.length(), replacement);
        pos += replacement.length();
      }
    }
    return s;
}
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair

bool DEBUG = 0;

template<class T> void dprint(T s){
  if(DEBUG){ cout << s << "\n"; }
}

// a1^a4 = a3
// a2^a5 = a4
// a3^a1 = a5
// a4^a2 = a1     a3^a5 = a3^a5^a4^a1 -> a4^a1 = 0
// a5^a3 = a2     a4^a1 = a4^a1^a2^a5 -> a5^a2 = 0

int N;
vector<int> a;

bool check1(){ // 全部ゼロ
  return (a[N-1]==0);
}

bool check2(){ // x 0 x x 0 x
  if(N%3>0){ return false;}
  return (a[0]==0 && a[N/3-1]==0 && a[N/3]==a[N-1]);
}

bool check3(){ // x y z x y z
  if(N%3>0){ return false;}
  if( a[0]==a[N/3-1] && a[N/3]==a[N/3*2-1] && a[N/3*2]==a[N-1]){
    return (a[0]^a[N/3]^a[N/3*2])==0;
  }else{
    return false;
  }
}

int main(){
  cin >> N;
  REP(i,N){
    int x; cin >> x;
    a.push_back(x);
  }
  sort(ALL(a));
  bool ok = 0;
  ok += check1();
  ok += check2();
  ok += check3();
  cout << (ok?Liny:Linn);
}

Measured memory_bytes: 3800
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(c) c.begin(),c.end()
#define PB push_back

using namespace std;
typedef long long ll;

int main()
{
  ll X, Y;
  cin >> X >> Y;

  ll ans = 0;
  while (X <= Y) {
    ans++;
    X *= 2;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String answer = "Good";
        for (int i = 0; i < 3; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                answer = "Bad";
                break;
            }
        }
        System.out.println(answer);
        sc.close();
    }
}

Measured memory_bytes: 35548
var input = require('fs').readFileSync('/dev/stdin', 'utf8').trim();
//var input = 999993031;
var n = parseInt(input);
var on = n;

var primes = [];
while (n % 2 == 0) {
    primes.push(2);
    n = n / 2;
}
for (var i = 3; i * i <= n; i += 2) {
    while (n % i == 0) {
        primes.push(i);
        n /= i;
    }
}
if (n > 1) primes.push(n);

console.log(on + ': ' + primes.join(' '));


Measured memory_bytes: 15388
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int dp[3][100005];
vector<int> g[100005];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
    }
    int s, t;
    scanf("%d%d", &s, &t);
    memset(dp, -1, sizeof(dp));
    dp[0][s] = 0;

    queue<pii> q;
    q.push(pii(0, s));
    while(!q.empty()){
        int u = q.front().second, x = q.front().first;
        q.pop();
        for(int i=0;i<g[u].size();i++){
            int v = g[u][i];
            int xx = (x+1)%3;
            if(dp[xx][v] == -1 || dp[xx][v] > dp[x][u] + 1){
                int add = 0;
                if(x == 0) add = 1;
                dp[xx][v] = dp[x][u] + add;
                q.push(pii(xx, v));
            }
        }
    }
    printf("%d\n", dp[0][t]);
}

Measured memory_bytes: 6912
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(),a.end()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forr(i,n) for(int i=int(n-1);i>=0;i--)
#define fora(i,a,b) for(int i=int(a);i<=int(b);i++)
#define forb(i,a,b) for(int i=int(a);i>=int(b);i--)
#define mod 1000000007
using namespace std;
using ll=long long int;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vii;
typedef pair<ll ,ll> pii;
ll get(ll a,ll k)
{
	ll x=abs(a-k);
	return x*x;
}
void solve()
{
	int n;
	cin>>n;
	int arr[n];
	forn(i,n)cin>>arr[i];
	int ans=1e9;
	fora(j,-1000,1000)
	{
		int cur=0;
		forn(i,n)
		{
			cur+=get(arr[i],j);
		}
		ans=min(ans,cur);
	}
	
	cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    int t=1;
   // cin>>t;
    while(t--)
	solve();
    return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main(){
	int H,W;
	cin>>H>>W;
	int N=10;
	// Floyd-Warshall の初期化: dist[i][i] = 0 に注意
	int dist[N][N];
	rep(i,N){
		rep(j,N){
			if(i!=j) dist[i][j]=INF;
			else dist[i][j]=0;
		}
	}
	
	// 入力と Floyd-Warshall
	rep(i,10){
		rep(j,10){
			int c;
			cin>>c;
			if(dist[i][j]>c) dist[i][j]=c;
		}
	}
	rep(k,N){
		rep(i,N){
			rep(j,N){
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	ll ans=0;
	rep(i,H){
		rep(j,W){
			int a;
			cin>>a;
			if(a==-1 || a==1) continue;
			ans+=dist[a][1];
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll N,K,a;
    cin >> N >> K;
    vector<ll> A(N);
    vector<ll> A_1(0);
    vector<ll> A_2(0);
    for (ll i = 0; i < N; i++){
        cin >> a;
        A.at(i) = a;
    }
    map<ll, ll> tel;
    ll machi = 1;
    ll cnt = 0;
    while(!tel.count(machi)){
        tel[machi] = A.at(machi-1);
        machi = A.at(machi-1);
        cnt++;
    }
    ll machi_1 = 1;
    ll cnt_1 = 0;
    while(machi_1 != machi){
        A_1.push_back(machi_1);
        machi_1 = A.at(machi_1-1);
        cnt_1++;
    }
    ll cnt_2 = cnt - cnt_1;
    ll machi_2 = machi;
    for(ll i = 0; i < cnt_2; i++){
        A_2.push_back(machi_2);
        machi_2 = A.at(machi_2-1);
    }
    //cout << "cnt_1 = " << cnt_1 << endl;
    //cout << "cnt_2 = " << cnt_2 << endl;

    // for(int i = 0;i < A_1.size(); i++){
    //     cout << "A_1(" << i << ") = " << A_1.at(i) << endl;
    // }

    // for(int i = 0;i < A_2.size(); i++){
    //     cout << "A_2(" << i << ") = " << A_2.at(i) << endl;
    // }

    if(K < cnt_1){
        cout << A_1.at(K) << endl;
    }else{
        K = (K-cnt_1)%cnt_2;
        cout << A_2.at(K) << endl;
    }
}


Measured memory_bytes: 19104
#include <iostream>
#include <queue>
#include <map>
using namespace std;

char get(char a,char b){
	bool c[128]={0};
	c[a] = c[b] = true;
	if(!c['r'])return 'r';
	if(!c['g'])return 'g';
	if(!c['b'])return 'b';
}
bool same(string t){
	for(int i=0;i<t.size();i++)
		if(t[i] != t[0])return false;
	return true;
}
int main(){
	string str;
	while(cin >> str , str != "0"){
		queue<string> Q;
		map<string,int> done;
		done[str] = 0;
		Q.push(str);
		int ans = -1;
		while(Q.size()){
			string q = Q.front(); Q.pop();
			if(same(q)){ans = done[q];break;};
			for(int i=0;i<q.size()-1;i++){
				if(q[i] != q[i+1]){
					string t = q;
					t[i] = t[i+1] = get(q[i],q[i+1]);
					if(done.find(t) == done.end()){
						done[t] = done[q]+1;
						Q.push(t);
					}
				}
			}
		}
		if(~ans)cout << ans << endl;
		else cout << "NA" << endl;
	}
}

Measured memory_bytes: 1876
import java.util.*
import kotlin.math.*

fun str() = readLine()!!
fun int() = str().toInt()
fun long() = str().toLong()

fun read(d:String = " ") = str().split(d)
fun <T> list(d:String = " ",f:String.()->T) = read(d).map {f(it)}
fun list() = list {toInt()}

const val mod = 1000000007L

fun main() {
	abc000X()
}

fun abc000X() {
	val (n,k) = list()
	val a = list {toLong()}
	val b = a.groupBy {
		when {
			it>0->1
			it==0L->0
			else->-1
		}
	}
	val pos = (b[1]?.sorted() ?: emptyList()).toMutableList()
	val neg = (b[-1]?.sortedDescending() ?: emptyList()).toMutableList()

	if(k-min(neg.size/2*2,k/2*2)>pos.size) {
		a.sortedBy {abs(it)}
				.take(k)
				.reduce {o,p-> ((o+mod)%mod)*((p+mod)%mod)%mod}
				.let {println(it)}

	} else {
		var r = if(k%2==1) pos.removeAt(pos.lastIndex) else 1L
		for(i in 1..k/2) {
			val p = if(pos.size<2) 0 else pos[pos.lastIndex]*pos[pos.lastIndex-1]
			val q = if(neg.size<2) 0 else neg[neg.lastIndex]*neg[neg.lastIndex-1]
			if(p>q) {
				r = p%mod*r%mod
				pos.removeAt(pos.lastIndex)
				pos.removeAt(pos.lastIndex)
			} else {
				r = q%mod*r%mod
				neg.removeAt(neg.lastIndex)
				neg.removeAt(neg.lastIndex)
			}
		}
		println(r)
	}
}


Measured memory_bytes: 78052
#include <stdio.h>

int main()
{
	long long int a,b;
	scanf("%lld%lld",&a,&b);
	
	int count = 0;
	for(int i=1;i<=a;i++)
	{
		long long int c,d;
		scanf("%lld%lld",&c,&d);
		if(c*c+d*d<=b*b) count++;
	}
	printf("%d",count);
}

Measured memory_bytes: 1716
/* 解答時間→ : */
#include <cmath>
#include <iostream>
using namespace std;

bool isPrime(int n){
	if(n == 2)
		return true;
	if(n % 2 == 0)
		return false;
	for(int i = 3; i <= static_cast<int>(sqrt(static_cast<double>(n))); i+=2){
		if(n % i == 0)
			return false;
	}
	return true;
}

int main(){
	int n, sum;
	while(1){
		cin >> n;
		if(n == 0)
			break;
		sum = 0;
		for(int i = n + 1; i <= 2 * n; i++){
			if(isPrime(i) == true){
				++sum;
			}
		}
		cout << sum << "\n";
	}
	cout << flush;
	return 0;
}

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

#define pb push_back
#define ff first
#define ss second
#define N 1503
#define mod 1000000007
#define fo(n) for(int i=1;i<=n;i++)
typedef pair<int,int> pii;
typedef long long int ll;
typedef long int li;
int mod1 = 998244353;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n,k;
    cin>>k>>n;
    int a[n+2];
    for(int i=1;i<=n;i++) cin>>a[i];
    int sum = k - a[n] + a[1];
    int m = sum;
    for(int i=2;i<=n;i++) {
        sum += (a[i] - a[i-1]);
        m = max(m,a[i] - a[i-1]);
    }
    cout<<(sum - m);
}


Measured memory_bytes: 1152
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long int ll;
void swap(ll *x, ll *y) {
    ll temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
ll asc(const void *a, const void *b) { return *(ll *)a - *(ll *)b; }
ll desc(const void *a, const void *b) { return *(ll *)b - *(ll *)a; }
ll max(ll x, ll y) { return x > y ? x : y; }
ll min(ll x, ll y) { return x > y ? y : x; }
/*void qsort(配列のアドレス,配列のサイズ,sizeof(配列の型),比較関数(昇順or降順))
 */

int main(){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    int start,end;
    start=a<c?c:a;
    end=b<d?b:d;
    if (end - start > 0) printf("%d\n", end - start);
    else printf("0\n");

    return 0;
}

Measured memory_bytes: 128
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func max(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v > ret {
			ret = v
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	h, w := nextInt(), nextInt()
	s := make([]string, h)
	for i := range s {
		s[i] = next()
	}

	// 前処理
	yoko, tate := make([][]int, h), make([][]int, h)
	for i := 0; i < h; i++ {
		yoko[i], tate[i] = make([]int, w), make([]int, w)
	}
	// yoko
	for i := 0; i < h; i++ {
		for l := 0; l < w; {
			for l < w && s[i][l] == '#' {
				l++
			}
			r := l
			for r+1 < w && s[i][r+1] == '.' {
				r++
			}
			dist := r - l + 1
			for j := l; j <= r && j < w; j++ {
				yoko[i][j] = dist
			}
			l = r + 1
		}
	}
	// tate
	for i := 0; i < w; i++ {
		for u := 0; u < h; {
			for u < h && s[u][i] == '#' {
				u++
			}
			d := u
			for d+1 < h && s[d+1][i] == '.' {
				d++
			}
			dist := d - u + 1
			for j := u; j <= d && j < h; j++ {
				tate[j][i] = dist
			}
			u = d + 1
		}
	}

	ans := 0
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			if s[i][j] == '.' {
				ans = max(ans, yoko[i][j]+tate[i][j]-1)
			}
		}
	}

	puts(ans)
}


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

bool uruu(int n, vector<int> &a, int x){
    rep(i,n){
        if(x % a[i] == 0) return (i%2 == 0);
    }
    return (n%2 == 0);
}

int main(void){
    int n,l,r;
    while(cin>>n>>l>>r, n|l|r){
        vector<int> a(n);
        rep(i,n) cin>>a[i];
        int cnt = 0;
        for(int x = l; x<=r; x++){
            if(uruu(n,a,x)) cnt++;
        }
        cout<<cnt<<endl;
    }
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
//#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;
template <typename T>
void vecin(vector<T> &v, int n = 0)
{
    if (n == 0)
        n = v.size();
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
}
template <typename T>
void vecout(vector<T> &v, int n = 0)
{
    if (n == 0)
        n = v.size();
    for (int i = 0; i < n - 1; ++i)
    {
        cout << v[i] << " ";
    }
    cout << v[n - 1] << endl;
}

int main()
{
    ciosup;
    int n;
    cin >> n;
    vector<ll> a(3 * n), mav(n + 1), smv(n + 1);
    vecin(a);
    ll tot = 0;
    multiset<ll> ma;
    REP(i, n)
    {
        ma.emplace(a[i]);
        tot += a[i];
    }
    mav[0] = tot;
    REP(i, n)
    {
        tot += a[i + n];
        ma.emplace(a[i + n]);
        auto ite = ma.begin();
        tot -= *ite;
        ma.erase(ite);
        mav[i + 1] = tot;
    }
    multiset<ll> ma2;
    tot = 0;
    REP(i, n)
    {
        ma2.emplace(a[3 * n - 1 - i]);
        tot += a[3 * n - 1 - i];
    }
    smv[n] = tot;
    REP(i, n)
    {
        tot += a[2 * n - 1 - i];
        ma2.emplace(a[2*n - 1 - i]);
        auto ite = ma2.end();
        --ite;
        tot -= *ite;
        ma2.erase(ite);
        smv[n - 1 - i] = tot;
    }
    ll ans = mav[0] - smv[0];
    REP(i, n + 1)
    {
        ans = max(ans, mav[i] - smv[i]);
    }
    cout << ans << endl;
}

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

int main(void){
    int a,b;
    cin >> a >> b;
    int kuchi=1, ans=0;
    while (kuchi<b)
    {
        kuchi -= 1;
        kuchi += a;
        ans += 1;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> Vec<T> {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    buf.split_whitespace()
        .map(|x| x.parse().ok().unwrap())
        .collect()
}

fn main() {
    let n: i64 = read()[0];
    let a: Vec<i64> = read();
    let ans = (0..n)
        .map(|i| {
            let j = std::cmp::max(n - i * 2 - 1, i * 2 - n);
            a[j as usize].to_string()
        })
        .collect::<Vec<String>>()
        .join(" ");
    println!("{}", ans);
}


Measured memory_bytes: 16620
#include<bits/stdc++.h>
typedef  long long int ll;
typedef  long double ld;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define mod 1000000007
#define F first
#define S second 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
//recursions\
#pragma comment(linker, "/stack:200000000")
//loops\
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
using namespace std;

const int N = 1e6 + 5;
int main()
{
	sync;
	ll n;
	cin >> n;
	ll a[n], b[n], c[n];
	input(a, n);
	input(b, n);
	sort(b, b + n, greater<ll>());
	ll l = 1e9, r = -1;
	for(ll i = 0 ; i < n; i++)
	{
		if(a[i] == b[i])
		{
			l = min(l, i);
			r = max(r, i);
		}
	}
	if(r != -1)
	{
		for(ll i = 0; i < n; i++)
		{
			if(l > r)
				break;
			if(a[i] != a[r] && b[i] != a[r])
			{
				swap(b[l], b[i]);
				l++;
			}
		}
	}
	if(l <= r)
		cout << "No";
	else
	{
		cout << "Yes\n";
		for(ll i = 0; i < n; i++)
			cout << b[i] << " ";
	}
}

Measured memory_bytes: 6720
#include<cstdio>

using namespace std;

int a,b,c;

int main()
{
	scanf("%d%d%d",&a,&b,&c);
	for(int i=1;i<=b;i++)
	{
		if(a*i%b==c)
		{
			puts("YES");
			return 0;
		}
	}
	puts("NO");
	return 0;
}

Measured memory_bytes: 128