akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		ArrayList<Edge>[] list = new ArrayList[n+1];
		for(int i = 1; i <= n; i++){
		    list[i] = new ArrayList<Edge>();
		}
		for(int i = 1; i < n; i++){
		    int u = sc.nextInt();
		    int v = sc.nextInt();
		    int w = sc.nextInt();
		    if(w%2 == 0){
		        w = 1;
		    }else{
		        w = -1;
		    }
		    /*if(u > v){
		        int temp = u;
		        u = v;
		        v = temp;
		    }*/
		    list[u].add(new Edge(u, v, w));
		    list[v].add(new Edge(v, u, w));
		}
		
		// 計算
		int[] result = new int[n+1];
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		q.add(1);
		while(!q.isEmpty()){
		    int now = q.poll();
		    if(result[now] == 0) result[now] = 1;
		    for(Edge e : list[now]){
		        int i = e.v;
		        if(result[i] != 0) continue;
		        result[i] = result[now]*e.w;
		        q.add(i);
		    }
		}
		
		// 出力
        for(int i = 1; i <= n; i++){
		    System.out.println(max(0, result[i]));
		}
		//System.out.println(result);
	}

}

class Edge {
    int u;
    int v;
    int w;
    
    Edge(int u, int v, int w){
        this.u = u;
        this.v = v;
        this.w = w;
    }
    
    
    public String toString(){
        return "u:" + u + " v:" + v + " w:" + w;
    }
    
}

Measured memory_bytes: 113532
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int main(){
  string s;
  bool x = false;
  cin >> s;
  int n=(int)s.size(),ret = n+100;
  for(int i=0;i<n-1;i++){
    if(s[i]!=s[i+1]){
      ret=min(ret,max(i+1,n-i-1));
      x = true;
    }
  }
  if(!x)cout << n << endl;
  else cout << ret << endl;
  return 0;
}

Measured memory_bytes: 512
n = int(input())
a = list(list(map(int, input().split())) for _ in range(2))
ans = 0
for x in range(n):
    buf = 0
    for i in range(x + 1):
        buf += a[0][i]
    for j in range(x, n):
        buf += a[1][j]
    ans = max(ans, buf)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using vs=vector<string>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.141592653589793

template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}



int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int n;
	cin>>n;
    vi pr(100,1);
    range(i,1,n+1){
        int p=i;
        range(j,2,101){
            if(p%j==0){
                pr[j]++;
                p/=j;
                j--;
            }
        }
    }
    int ans=0;
    rep(i,100){
        if(pr[i]>74)ans++;
        range(j,i+1,100){
            if(pr[i]>4 and pr[j]>14) ans++;
            if(pr[i]>14 and pr[j]>4) ans++;
            if(pr[i]>2 and pr[j]>24) ans++;
            if(pr[i]>24 and pr[j]>2) ans++;
            range(k,j+1,100){
                if(pr[i]>2 and pr[j]>4 and pr[k]>4)ans++;
                if(pr[i]>4 and pr[j]>2 and pr[k]>4)ans++;
                if(pr[i]>4 and pr[j]>4 and pr[k]>2)ans++;
            }
        }
    }
    cout<<ans<<endl;
	return 0;
}


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

int main(){
  string a;
  cin >> a;
  int n = a.size();

  for(int i = 0;i < n-1;i++){
    if(a[i] == a[i+1]){
      i++;
      cout << i << " " << i+1 << endl;
      return 0;
    }
    if(i != n-2 && a[i] == a[i+2]){
      i++;
      cout << i << " " << i+2 << endl;
      return 0;
    }
  }

  cout << -1 << " " << -1 << endl;

  return 0;
}

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

string str;
int n;

map<string, vector<int> > dict;

int main(){
    while(cin >> str >> n){
	dict[str].push_back(n);
    }
    map<string, vector<int> >::iterator it = dict.begin();
    while(it != dict.end()){
	cout << it->first << endl;
	sort(it->second.begin(), it->second.end());
	for(int i = 0;i < it->second.size();i++){
	    if(i != 0)cout << " ";
	    cout << it->second.at(i);
	}
	cout << endl;
	it++;
    }
    return 0;
}

Measured memory_bytes: 1244
#[allow(unused_imports)] use proconio::{input, marker::{Bytes, Chars, Usize1, Isize1}};
#[allow(unused_imports)] use std::cmp::{min, max};
#[allow(unused_imports)] use superslice::Ext as _;

#[proconio::fastout]
fn main() {
	input! {
		n: usize,
		s: Chars,
	}

	// Eの累積和
	let mut esum = vec![0usize; n];

	if s[0] == 'E' {
		esum[0] = 1;
	}
	for i in 1..n {
		if s[i] == 'E' {
			esum[i] = esum[i-1] + 1;
		}
		else {
			esum[i] = esum[i-1];
		}
	}

	let mut ans = 99999999999usize;
	for i in 0..n {
		let  mut count = 0;
		// リーダーより東にいるEの数
		count += esum[n-1] - esum[i];
		// リーダーより西にいるWの数
		if i != 0 {
			count += i-esum[i-1];
		}

		ans = min(ans, count);
	}

	println!("{}", ans);
}


Measured memory_bytes: 6024
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
//#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)


#define huge 1000000007
typedef long long ll;

int main(void) {

	ll N = 0;
	//ll A = 0;
	//ll B = 0;
	ll K = 0;
	ll Y = 0;
	ll Q = 0;
	//ll x[10000] = {};
	//ll c[10000] = {};
	//ll d[10000] = {};
	ll *x, *c, *d;
	//string w;
	ll count = 0;
	ll sum = 0;
	ll i = 0;
	string A,B,S;

	cin >> A >>S >>B;
	x = (ll *)malloc(Q * sizeof(ll));
	c = (ll *)malloc(Q * sizeof(ll));
	d = (ll *)malloc(Q * sizeof(ll));

	cout << "A" << S[0] << "C" << endl;

	
	return 0;

}



Measured memory_bytes: 256
n = int(input())
ln = list(map(int, input().split()))

ln.sort()

def binary_search(x, r):
    left = r + 1
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if ln[mid] >= x:
            right = mid - 1
        else:
            left = mid + 1
    if ln[mid] >= x:
        return mid - 1
    else:
        return mid


ans = 0
for a in range(n-2):
    for b  in range(a+1, n-1):
        cmax = ln[b] + ln[a]
        ans += max(0, binary_search(cmax, b) - b)

print(ans)

Measured memory_bytes: 46112
import math
import string


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N = int(input())
s = []
for _ in range(N):
    s.append(input())
# print(s)
M = int(input())
t = []
for _ in range(M):
    t.append(input())
# print(t)
x = 0
y = 0
ma = 0
for i in range(len(s)):
    x = s.count(s[i])
    y = t.count(s[i])
    ma = max(ma, (x-y))
print(ma)


Measured memory_bytes: 3832
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;
constexpr char newl = '\n';

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define F first
#define S second
#define debug(x) cout << #x << ": " << x << '\n';

#if 1

template<typename F>
struct FixPoint : F {
  FixPoint(F&& f) :F(forward<F>(f)) {}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f) {
  return FixPoint<F>{forward<F>(f)};
}

constexpr int MOD = 1e9 + 7; // 1e9 + 7

// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;

  vector<double> p(N);
  F0R(i, N) {
    cin >> p[i];
  }

  vector<double> r1(1, 1.0), r2(2);
  cout << std::fixed << std::setprecision(10);

  FOR(i, 1, N + 1) {
    // 表の数が 0 ～ i の確率を全て計算する

    r2.resize(i + 1);

    // 裏の確率
    auto ip = 1.0 - p[i-1];

    r2[0] = r1[0] * ip;
    FOR(j, 1, i) {
      r2[j] = r1[j - 1] * p[i - 1] + r1[j] * ip;
    }
    r2[i] = r1[i - 1] * p[i - 1];

    r1 = move(r2);
  }

  //cout << r1[0] << ' ' << r1[1] << newl;
  double result = 0;
  RFO(i, (N + 1) / 2, N + 1) {
    result += r1[i];
  }

  cout << result;
}
#endif


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	ll ans = 0;
	int n, a, b;
	cin >> n >> a >> b;
	if(a > b || n == 1 && a != b){
		cout << ans << endl;
		return 0;
	}
	ll temp_b = (ll)a + (ll)b*(ll)(n-1);
	ll temp_a = (ll)a*(ll)(n-1) + (ll)b;
	ans = temp_b - temp_a + 1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		String[] str = new String[3];
		
		for(int i = 0 ; i < str.length ; i ++ ){
			str[i] = sc.next();
		}
		
		System.out.println("" + str[0].charAt(0) + str[1].charAt(1) + str[2].charAt(2));
	}
}


Measured memory_bytes: 22868
#include<stdio.h>
#define n 3

int main(){
	int i, j;
	char c[n+1][n+1];
	
	for(i=0; i<n; i++){
//		for(j=0; j<n; j++){
			scanf("%c%c%c%*c", &c[i][0], &c[i][1], &c[i][2], &c[i][3]);
//		}
	}
	
	printf("%c%c%c", c[0][0], c[1][1], c[2][2]);
	
	return 0;
}



Measured memory_bytes: 128
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<stack>
#include<set>
using namespace std;
long long n,ans;
int main()
{
	scanf("%lld",&n);
	for (long long i=2;i*i<=n;++i)
	{
		if (n%i) continue;
		for (long long j=i;j<=n;j*=i)
		{
			if(n%j==0)
			{
				n/=j;
				ans++;
			}
		}
		while (n%i==0) n/=i;
	}
	if (n>1) ++ans;
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 3828
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

#define max 100001

int main(void){
	bool isprime[max],changer[max]={false};
	int nearby[max];
	for(int i=0;i<max;++i){
		if(i != 1 && i != 0){
			isprime[i] = true;
		}else{
			isprime[i] = false;
		}
	}
	int k = (int)sqrt(max);
	for(int i=2;i<k;++i){
		if(isprime[i]){
			for(int j=i*2;j<max;j+=i){
				isprime[j] = false;
			}
		}
	}
	int c = 0;
	for(int i=1;i<max;i++){
		if(isprime[i] && isprime[(i+1)/2]){
			c++;
		}
		nearby[i] = c;
	}
	int m;
	cin >> m;
	for(int i=0;i<m;++i){
		int l,r,res=0;
		cin >> l >> r;
		cout << nearby[r] - nearby[l-1] << endl;
	}
}

Measured memory_bytes: 1152
/*
author: Apoorv Singh
*/

#include <bits/stdc++.h>
using namespace std;

typedef vector <int> vi;
typedef vector <long long> vl;
typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
#define ll long long
#define pb push_back   
#define all(c) c.begin(), c.end()
#define watch(x) cout << (#x) << " " << (x) << endl;
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second

ll modulo = 1e9 + 7;

template <class X>

void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

ll fpow(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a);
        a = (a*a);
        n = n >> 1;
    }
    return ans;
}

const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    sieve();
    ll n,p;
    cin >> n >> p;
    ll ans = 1;
    bool flag = false;
    FOR(i,2,int(1e6) + 1)
    {
    	if (!composite[i])
    	{
    		int count = 0; ll temp = p;
    		while (temp)
    		{
    			if (temp%i != 0)
    				break;
    			++count;
    			flag = true;
    			temp /= i;
    		}
    		ans *= fpow(i,count/n);
    	}
    }
    if (n == 1)
    	ans = p;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4224
#include <iostream>

using namespace std;

string str[8] = {
	"41412121",
	"41212141",
	"21414121",
	"21214141",
	"14141212",
	"14121214",
	"12141412",
	"12121414"
};

int main(){
	
	int p[8], c[8], ans, min, sum;
	
	while(true){
		
		cin >> p[0];
		
		if(cin.eof()){
			break;
		}
		
		cin >> p[1] >> p[2] >> p[3] >> p[4] >> p[5] >> p[6] >> p[7];
		
		min = 1 << 30;
		
		for(int i = 0; i < 8; i++){
			sum = 0;
			for(int j = 0; j < 8; j++){
				if(p[j] - (str[i][j] - '0') < 0){
					sum += 0;
				}else{
					sum += (p[j] - (str[i][j] - '0'));
				}
			}
			//cout << sum << endl;
			if(sum <= min){
				min = sum;
				ans = i;
			}
		}
		
		for(int i = 0; i < 7; i++){
			cout << str[ans][i] << " ";
		}
		
		cout << str[ans][7] << endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007;
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,1,-1,1,-1};
void chmin(long long &a, long long b) { if (a > b) a = b; }
const long long INF = 1LL<<60;
int main() {
    int n;
    cin >> n;
    vector<ll> a(n+1);
    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    a[0] = 2,a[1] = 1;
    for (int i = 2; i <= n; ++i) {
        a[i] = a[i-1]+a[i-2];
    }
    cout << a[n] << endl;
    return 0;
}

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

int n, m, l, r, sum[100005];
bool valid=true;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        cin >> l >> r;
        int a, b;
        a = min(l, r);
        b = max(l, r);
        sum[a]++; sum[b]--;
    }
    for(int i=1; i<n; i++) {
        sum[i] += sum[i-1];
        if(sum[i]%2!=0) valid=false;
    }
    if(valid) cout << "YES";
    else cout << "NO";

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include <math.h>
#include <cmath>
using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];

const int mod = 1000000007;
const int INF = 2000000015;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}


int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res=res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}


signed main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << max(a, max(b, c)) - min(a, min(b, c)) << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define EPS 1e-9
#define MOD 1000000007

// for using in pairs
#define F first
#define S second

// Macros
#define all(x) begin(x), end(x)

// aliases
using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ld = long double;

#define int long long

///////////////////////////////////////////////////////////////////////

void solve(int tc)
{
	int n, x, t;
	cin >> n >> x >> t;
	int ans = 0;
	while (n > 0)
	{
		n -= x;
		ans += t;
	}

	cout << ans << "\n";

}

int32_t main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

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

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++)
	{
		solve(i);
	}

	return 0;
}


Measured memory_bytes: 3636
results = {"01234567": 0}


def main():
    while True:
        try:
            tmp = input().replace(' ', '')
            print(results[tmp])
        except EOFError:
            break


def swap(field, a, b):
    tmp = list(field)
    tmp[b], tmp[a] = tmp[a], tmp[b]
    return "".join(tmp)


def convert_matrix_index(index):
    return index % 4, int(index / 4)


def convert_array_index(x, y):
    return x + y * 4


def bfs(results):
    q = [["01234567", 0]]

    while len(q) is not 0:
        field, res = q.pop(0)
        x, y = convert_matrix_index(field.find('0'))
        for dx, dy in zip([0, 0, -1, 1], [1, -1, 0, 0]):
            nx = x + dx
            ny = y + dy
            if nx < 0 or ny < 0 or nx >= 4 or ny >= 2:
                continue

            next_field = swap(field, convert_array_index(x, y), convert_array_index(nx, ny))
            if next_field not in results:
                results[next_field] = res + 1
                q.append([next_field, res + 1])

    return results


if __name__ == '__main__':
    results = bfs(results)
    main()

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

using ll = long long;
using P = pair<ll, ll>;

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define DEBUG(x) ;
#define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl;

int dx[4]{0, 1, 0, -1};
int dy[4]{1, 0, -1, 0};



int main(int argc, char **argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll N; cin >> N;
	vector<ll> V(N); REP(i, N) cin >> V[i];
	ll ma{V[0]};
	ll res{0};
	for (ll i = 1; i < N; ++i)
	{
		if (ma <= V[i])
		{
			ma = V[i];
		}
		else
		{
			res += (ma - V[i]);
		}
	}
	
	std::cout << res << std::endl;
	return 0;
}









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


int main() {
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);

    ll q, h, s, d, n;
    cin >> q >> h >> s >> d >> n;

    h = min(h, 2 * q);
    s = min(s, 2 * h);
    d = min(d, 2 * s);
    ll ans = n / 2 * d + (n & 1) * s;
    cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
int main()
{
	ll k;
	cin>>k;
	queue<ll> mp;
	if(k<=10)
	{
		cout<<k<<endl;
		return 0;
	}
	for(ll i=1;i<=9;i++)
	{
		mp.push(i);
	}
	ll s =9;
	while(1)
	{
		ll b = mp.front();
		ll y = b%10;
		mp.pop();
		if(y>0)
		{
			mp.push(b*10+y-1);
			s++;
			if(s == k)
			{
				cout<<b*10+y-1<<endl;
				return 0;
			}
		}
		mp.push(b*10+y);
		s++;
		if(s == k)
		{
			cout<<b*10+y<<endl;
			return 0;
		}
		if(y<9)
		{
			mp.push(b*10+y+1);
			s++;
			if(s == k)
			{
				cout<<b*10+y+1<<endl;
				return 0;
			}
		}
	}
	return 0;
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll h, k;
  cin >> h >> k;
  
  /*
  vector<int> a(n);
  rep(i, n) cin >> a.at(i);
  */
  
  cout << (h+k-1)/k << "\n";

}


Measured memory_bytes: 256
from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i in range(a+1)]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
res=''
while a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)
"""))
"""
from subprocess import*
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    # sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass

"""


Measured memory_bytes: 144596
use proconio::input;

#[proconio::fastout]
pub fn main() {
    input! {
    n:usize,
    mut a:[i64;n],
    }
    a.sort_by_key(|&x|std::cmp::Reverse(x));
    let mut ans = 0;
    for i in 1..n {
        ans += a[i / 2];
    }
    println!("{}", ans);
}


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

int main() {
  int H, W, K;
  cin >> H >> W >> K;
  vector<vector<char>> C(H, vector<char>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> C.at(i).at(j);
    }
  }
  int ans = 0;
  for (int bit = 0; bit < (1 << (H + W)); bit++) {
    int B = 0;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if ((bit & (1 << i)) && (bit & (1 << (H + j))) && C.at(i).at(j) == '#') B++;
      }
    }
    if (B == K) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <complex>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define EQ(a,b) (abs((a)-(b))<eps)

using namespace std;

typedef long double ld;
typedef complex<ld> P;
typedef vector<P> VP;
const ld eps = 1e-10, pi = acos(-1.0);

ld dot (P a, P b) { return real(conj(a) * b); }
ld cross (P a, P b) { return imag(conj(a) * b); }


// Line
class L{
public:
  P a, b;
  L (P aa, P bb) { a = aa; b = bb; }
  L (ld ax, ld ay, ld bx, ld by) { a = P(ax, ay); b = P(bx, by); }
};

// Circle
class C {
  public:
  P p; ld r;
  C(P p_,ld r_):p(p_),r(r_){}
};

int ccw (P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > eps) return 1;   // counter clockwise
  if (cross(b, c) < -eps) return -1; // clockwise
  if (dot(b, c) < 0) return 2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;  // a--b--c on line
  return 0;                          // a--c--b on line
}

bool isis_ss(L s, L t) {
  return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
    ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

VP is_cc(C c1, C c2){
  VP res;
  ld d = abs(c1.p - c2.p);
  ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
  ld dfr = c1.r * c1.r - rc * rc;
  if (abs(dfr) < eps) dfr = 0.0;
  else if (dfr < 0.0) return res; // no intersection
  ld rs = sqrt(dfr);
  P diff = (c2.p-c1.p)/d;
  res.push_back(c1.p + diff * P(rc, rs));
  if (dfr != 0.0) res.push_back(c1.p + diff * P(rc, -rs));
  return res;
}

// 直線sと直線lの交点
VP is_ll(L s, L t){
  VP v;
  P sv = s.b - s.a, tv = t.b - t.a;
  if (abs(cross(sv,tv)) > 0)
    v.push_back(s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv));
  return v;
}

bool isis_ccc(C c1,C c2,C c3){
  VP crs;
  for(P p:is_cc(c1,c2))crs.push_back(p);
  for(P p:is_cc(c2,c3))crs.push_back(p);
  for(P p:is_cc(c3,c1))crs.push_back(p);
  crs.push_back(c1.p);
  crs.push_back(c2.p);
  crs.push_back(c3.p);
  for(P p:crs){
    if(abs(p-c1.p)<=c1.r+eps&&abs(p-c2.p)<=c2.r+eps&&abs(p-c3.p)<=c3.r+eps){
      return true;
    }
  }
  return false;
}

int main() {
  while(1){
    int n;
    cin>>n;
    if(!n)break;
    vector<P> p(n);
    vector<ld> l(n);
    REP(i,n){
      ld x,y;
      cin>>x>>y>>l[i];
      p[i] = P(x,y);
    }
    ld maxh=300.0;
    REP(i,n){
      maxh=min(maxh,l[i]);
    }
    REP(i,n){
      REP(j,i){
        ld d=abs(p[i]-p[j]);
        vector<ld> t={l[i],l[j],d};
        sort(begin(t),end(t));
        if(t[0]+t[1]<t[2])continue;
        ld al=(l[i]*l[i]+d*d-l[j]*l[j])/(2.0*d);
        if(al<eps||al-d>eps)continue;
        ld h=sqrt(l[i]*l[i]-al*al);
        maxh=min(maxh,h);
      }
    }
    REP(i,n){
      REP(j,i){
        REP(k,j){
          ld m=maxh;
          ld h=0.0;
          while(m>eps){
            ld sqh=(m+h)*(m+h);
            if(isis_ccc(C(p[i],sqrt(l[i]*l[i]-sqh)),C(p[j],sqrt(l[j]*l[j]-sqh)),C(p[k],sqrt(l[k]*l[k]-sqh)))){
              h+=m;
            }
            m/=2.0;
          }
          maxh=min(maxh,h);
        }
      }
    }
    cout<<fixed<<setprecision(7)<<maxh<<endl;
  }
  return 0;
}

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

int main()
{
  int n;cin>>n;
  vector<int> a(n);
  int d[N];
  for (int i=0;i<N;i++)
    d[i]=0;
  
  for (int i=0;i<n;i++)
  {
    cin>>a[i];
    d[a[i]]++;
  }
  
  int max=0;
  for (int i=0;i<N-2;i++)
  {
    if (d[i+2]+d[i+1]+d[i]> max)
      max = d[i+2]+d[i+1]+d[i];
  }
  cout<<max<<endl;
}

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

int main() {
  vector<int> c(3);
  for (int i = 0; i < 3; i++) {
    cin >> c[i];
  }
  sort(c.begin(), c.end());
  string ans = (c[0] + c[1] == c[2]) ? "Yes" : "No";
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main()
{
	int n, a, b;
	cin >> n >> a >> b;
	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}

	int n1 = 0, n2 = 0, n3 = 0;
	for (int i = 0; i < n; i++) {
		if (p[i] <= a) {
			n1++;
		}
		else if (p[i] <= b) {
			n2++;
		}
		else {
			n3++;
		}
	}
	cout << min(n1, min(n2, n3)) << endl;

	return 0;
}

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

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 410;
const int H = 201;

bool use[N];
ve<pii> a[N];
int st[N];
bool is[100100];

void dfs(int v) {
	use[v] = 1;
	forn(i, sz(a[v])) {
		int to = a[v][i].fs;
		is[a[v][i].sc] = 1;
		if (!use[to])
			dfs(to);
	}
}

int main () {
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	int n, h;
	cin >> n >> h;
	forn(i, n) {
		int a1, b1, c1, d1;
		scanf("%d%d%d%d", &a1, &b1, &c1, &d1);
		//debug(mt(a1, b1, c1, d1));
		int u, v;
		if (c1 == 0) {
			u = a1;
		} else {
			u = c1 + H;
		}
		if (d1 == 0) {
			v = b1 + H;
		} else {
			v = d1;
		}
		a[u].pb(mp(v, i));
		a[v].pb(mp(u, i));
		st[u]++;
		st[v]--;
	}
	forn(i, H) {
		if (st[i] < 0 || st[i + H] > 0) {
			puts("NO");
			return 0;
		}
	}
	forn(i, H) {
		if (st[i] > 0 && !use[i]) {
			dfs(i);
		}
	}
	int cnt = 0;
	forn(i, n)
		cnt += is[i];
	if (cnt == n) {
		puts("YES");
		return 0;
 	}
 	puts("NO");
	return 0;
}


Measured memory_bytes: 3200
#include <stdio.h>


int main(void){
    int n, k;
    char order[50];
    char s[20];
    
    fgets(order, 49, stdin);
    sscanf(order, "%d", &n);
    fgets(order, 49, stdin);
    sscanf(order, "%s", s);
    fgets(order, 49, stdin);
    sscanf(order, "%d", &k);
    //printf("%d %s %d\n", n, s, k);
    
    for(int i = 0; i < n; i++){
        if(s[k-1] == s[i]){
            continue;
        }else{
            s[i] = '*';
        }
    }
    printf("%s\n", s);
    
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

int calc(int N)
{
    int res=0;
    while(N>0){
        res+=N%10;
        N/=10;
    }
    return res;
}

signed main()
{   
    int N; cin>>N;
    int ans=calc(N);
    string s=to_string(N);
    int t=(s[0]-'1')+9*(s.size()-1);
    cout<<max(ans,t)<<endl;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
s = input()
if s == 'Sunny':
  print('Cloudy')
elif s == 'Cloudy':
  print('Rainy')
else:
  print('Sunny')

Measured memory_bytes: 38256
import Control.Applicative
import Data.List(nub)

main = do
  n <- readLn
  if n == 0
     then return ()
     else do
--       print $ factors n primes [[1]]
       syori n
       main

syori n = do
  putStrLn $ hantei n

hantei :: Int -> [Char]
hantei n
  | length (factors n primes [[1]]) == 2 = "deficient number"
  | n*2 > product (map sum (factors n primes [[1]])) = "deficient number"
  | n*2 < product (map sum (factors n primes [[1]])) = "abundant number"
  | otherwise           = "perfect number"

factors :: Int -> [Int] -> [[Int]] -> [[Int]]
factors n (x:xs) ys
  | x * x > n   = (nub[1,n]:ys)
  | reM == 0 = factors' quoT (x:xs) [1,x] ys 2
  | otherwise    = factors n xs ys
  where
    (quoT,reM) = quotRem n x

factors' n (x:xs) zs ys m
  | reM == 0 = factors' quoT (x:xs) ((x^m):zs) ys (m+1)
  | otherwise = factors n xs (zs:ys)
  where
    (quoT,reM) = quotRem n x

primes :: [Int]
primes = takeWhile (<10000) $ 2:3:5:7: filter (null . tail . primeFactors) [11,13..]

primeFactors :: Int -> [Int]
primeFactors n = factor n primes
  where
    factor n (x:xs)
      | x * x > n   = [n]
      | reM == 0 = x : factor quoT (x:xs)
      | otherwise    = factor n xs
      where
        (quoT,reM) = quotRem n x

Measured memory_bytes: 4256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define mod 1000000007 //10^9+7
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
int n;
string s;
signed main(){
    int n;
    cin>>n;
    cout<<n*n<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
#define sz(x) x.size()
#define EPS (1e-10)
// aよりbの方が小さかったら、aの値をbの値に置き換える。(swapではない！)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
// aよりbの方が大きかったら、aの値をbの値に置き換える。
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
// 素数かどうか判定
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))


// 二分累乗法
inline int modpow(int x, int pow) {
	if (pow == 0)return 1;
	int a = modpow(x, pow / 2);
	a = a * a%MOD;
	if (pow % 2 == 1)a *= x;
	return a % MOD;
}

int fact[200010];
inline int factorial_mod(int x) {
	if (x == 0)return 1;
	if (fact[x] != 0)return fact[x];
	return fact[x] = (x*factorial_mod(x - 1)) % MOD;
}

inline int modnCr(int n, int r) {
	return factorial_mod(n)*modpow(factorial_mod(r)*factorial_mod(n - r) % MOD, MOD-2)%MOD;
}



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	vector<int>vec(w - b, 0);
	for (int i = b + 1; i <= w; i++) {
		vec[i - b - 1] = modnCr(h - a + i - 2, h - a - 1);
	}
	int ans = 0;
	rep(i, vec.size()) {
		int tmp = modnCr(a + w - b - i - 2, a - 1);
		ans = (ans + (vec[i] * tmp) % MOD) % MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4352
n, h, w = list(map(int, input().split()))
hl = []
wl = []
for i in range(n):
    a,b = list(map(int, input().split()))
    hl.append(a)
    wl.append(b)
#print()
ct = 0
for j in range(n):
    if hl[j]>=h and wl[j]>=w:
        ct +=1
print(ct)

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
 
using namespace std;
 
#define PB push_back
#define MP make_pairA
#define REP(i,n) for(int i=0;i<(n);i++)
int main()
{
    string t="snuke";
    string s;
    int h,w;
    cin>>h>>w;
    REP(i,h)REP(j,w){
        cin>>s;
        if(s==t){
            // cout<<j<<endl;
            cout<<(char)(j+'A')<<i+1<<endl;
        }
    }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

struct Point { double x,y;};

void koch(int n, Point a,Point b){
	if(n==0)return;
	
	Point s,t,u;
	double th=M_PI*60.0/180.0;
	
	s.x=(2.0*a.x+1.0*b.x)/3.0;
	s.y=(2.0*a.y+1.0*b.y)/3.0;
	t.x=(1.0*a.x+2.0*b.x)/3.0;
	t.y=(1.0*a.y+2.0*b.y)/3.0;
	u.x=(t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
	u.y=(t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;
	
	koch(n-1,a,s);
	printf("%.8f %.8f\n",s.x,s.y);
	koch(n-1,s,u);
	printf("%.8f %.8f\n",u.x,u.y);
	koch(n-1,u,t);
	printf("%.8f %.8f\n",t.x,t.y);
	koch(n-1,t,b);
}

int main(){
	Point a,b;
	int n;
	scanf("%d",&n);
	
	a.x=0;
	a.y=0;
	b.x=100;
	b.y=0;
	
	printf("%.8f %.8f\n",a.x,a.y);
	koch(n,a,b);
	printf("%.8f %.8f\n",b.x,b.y);
	
	return 0;
}

Measured memory_bytes: 2708
import java.util.*;
public class Main {
    public static void main(String[] args){

        long NUM=1000000007;
        Scanner sc = new Scanner(System.in);
        // 整数の入力
        int N=sc.nextInt();
        int A=sc.nextInt();
        int B=sc.nextInt();
        System.out.println(Math.min(N*A,B));
        return;


    }
}


Measured memory_bytes: 21844
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	class Node {
		int parent;
		public Node(int x) {
			this.parent = x;
		}
	}
	
	class DisjointSet {
		Node[] p;
		int[] rank;
		
		public DisjointSet(int size) {
			p = new Node[size];
			rank = new int[size];
			for (int i = 0; i < size; i++) {
				makeSet(i);
			}
		}

		private void makeSet(int x) {
			p[x] = new Node(x);
			rank[x] = 0;
		}
		
		private int findSet(int x) {
			while (x != p[x].parent) {
				x = p[x].parent;
			}
			return x;
		}
		
		public boolean same(int x, int y) {
			return findSet(x) == findSet(y);
		}
		
		public void unite(int x, int y) {
			link(findSet(x), findSet(y));
		}

		private void link(int x, int y) {
			if (rank[x] > rank[y]) {
				p[x].parent = y;
			} else {
				p[y].parent = x;
				if (rank[x] == rank[y]) {
					rank[y]++;
				}
			}
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(reader.readLine());
		int n = Integer.parseInt(st.nextToken());
		DisjointSet ds = new DisjointSet(n);
		int q = Integer.parseInt(st.nextToken());
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(reader.readLine());
			int c = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			if (c == 0) {
				ds.unite(x, y);
			} else {
				System.out.println(ds.same(x, y)?"1":"0");
			}
		}
		reader.close();
	}
}



Measured memory_bytes: 61308
//DinamicProgramming Fibonacci Number

#include<stdio.h>


int dp[45];

int fib(int n){
    if(n == 0 || n == 1) dp[n] = 1;
    if(dp[n]) return dp[n];
    if(dp[n-1] && dp[n-2]) dp[n] = dp[n-1] + dp[n-2];
    else dp[n] = fib(n-1) + fib(n-2);
    
    return dp[n];
}

int main(void){
    int n;
    int res;
    scanf("%d", &n);
    
    res = fib(n);
     
    printf("%d\n", res);
    
    return 0; 
}

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

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REP(i, n) for(int i=0; i<(int)(n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SQ(n) (n) * (n)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
  ll a, b;
  while(cin >> a >> b) {
    cout << to_string(a + b).length() << endl;
  }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    vector<int> dp(n, 1e9);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= 2; j++) {
            if (i - j >= 0) dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
        }
    }
    // for (int val : dp) {
    //     cout << val << " ";
    // }
    // cout << endl;
    cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1024
#include <iostream>

#define u unsigned
#define s short
#define ll long long
#define REP(i, a, b) for (auto i = (a); i < (b); i++)
#define REPR(i, a, b) for (auto i = (a-1); i >= (b); i--)

using namespace std;

int main()
{
    u int H[2], M[2], K;

    cin >> H[0] >> M[0] >> H[1] >> M[1] >> K;

    cout << (H[1] * 60 + M[1]) - (H[0] * 60 + M[0]) - K << "\n";

    return 0;
}

Measured memory_bytes: 3644
#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 pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long



using namespace std;

void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
const int N=5e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;

const int MSQ = sqrt(N) + 5;


int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();

	int n,m;

	scanf("%d %d",&n,&m);
	std::vector<int> wa(m);
	for(int i=0,k;i<m;i++){
		scanf("%d",&k);
		for(int j=0,x;j<k;j++)scanf("%d",&x),wa[i]|=(1<<(x-1));
	}
	std::vector<int> p(m);
	for(int i=0;i<m;i++)scanf("%d",&p[i]);
	int ans = 0;
	for(int msk=0;msk<(1<<n);msk++){
		int curr = 0;
		for(int i=0;i<m;i++){
			if(__builtin_popcount(msk&wa[i])%2 == p[i]%2)
				curr++;
		}
		if(curr == m)
			ans ++;
	}

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



Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
const long long md=1e9+7;
long long n,m,dp[1010][1010];
char c;
bool ok1=true,ok2=true;
int main()
{
	cin>>n>>m;
	dp[0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>c;
			if(i==0)
			{
				if(c=='.' && ok1)
				{
					dp[i][j]=1;
				}
				else
				{
					ok1=false;
				}
			}
			else if(j==0)
			{
				if(c=='.' && ok2)
				{
					dp[i][j]=1;
				}
				else
				{
					ok2=false;
				}
			}
			else if(c=='.')
			{
				dp[i][j]=(dp[i-1][j]%md+dp[i][j-1]%md)%md;
			}
		}
	}
	cout<<dp[n-1][m-1]%md<<endl;
	return 0;
}

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

int main() {
	int a[5];
	for(int i=0;i<5;i++) cin >> a[i];
	for(int i=0;i<5;i++){
		if(a[i]==0){
			cout << i+1 << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 3596
#include <cstdio>
#include <algorithm>

using namespace std;

#define chmin(a,b) a=min(a,b)
#define rep(i,x) for(int i=0;i<(x);++i)

const int inf = 1e9;

int d[100][100];

signed main()
{
	int N, K;
	
	while (scanf("%d %d", &N, &K), N || K) {
		rep(i, N) rep(j, N) d[i][j] = i == j ? 0 : inf;

		rep(i, K) {
			int t; scanf("%d", &t);
			if (t) {
				int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--;
				chmin(d[a][b], c);
				chmin(d[b][a], c);
				rep(j, N) rep(k, N) {
					chmin(d[j][k], min(d[j][a] + d[a][b] + d[b][k], d[j][b] + d[b][a] + d[a][k]));
				}
			} else {
				int a, b; scanf("%d %d", &a, &b); a--; b--;
				printf("%d\n", d[a][b] == inf ? -1 : d[a][b]);
			}
		}
	}
}

Measured memory_bytes: 1064
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(input) {
    var a = input.split("\n").slice(0,-1);
    var n = parseInt(a[0]);
    var w = a.slice(1);
    
    var ans = 'Yes';

    //console.log(a,n,w);
    for(var i=0; i < w.length; i++){
      for(var j=0; j < w.length-i; j++){
        //console.log(w[i],w[i+j+1])
        if( w[i] == w[i+j+1]) { ans = 'No'}
      }
    }

    for(var i=0; i < w.length-1; i++){
      if (w[i].slice(-1) != w[i+1].slice(0,1) ) {ans = 'No'}
      //console.log(w[i].slice(-1), w[i+1].slice(0,1))
    }
    console.log(ans);
} );
process.stdin.on('end', function() {
});

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    string s, t;
    cin >> s >> t;
    int c = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] != t[i]) c++;
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 3916
import java.util.*;

public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	String A = sc.next();
      	String B = sc.next();
      	String C = sc.next();
      	
      	if(A.charAt(A.length() - 1) == B.charAt(0) &&
          B.charAt(B.length() - 1) == C.charAt(0)){
          	System.out.println("YES");
        }else{
        	System.out.println("NO");
        }
    }
}

Measured memory_bytes: 23124
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
int c[110000];
int d[110000];
long long segtree[262144];
long long query(int a){
	long long ret=0;
	a+=131072;
	while(a){
		ret=max(ret,segtree[a]);
		a/=2;
	}
	return ret;
}
void update(int a,int b,int c,int d,int e,long long f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		segtree[e]=max(segtree[e],f);
		return;
	}
	update(a,(a+b)/2,c,d,e*2,f);
	update((a+b)/2+1,b,c,d,e*2+1,f);
}
long long dp[110000];
long long x[110000];
long long z[110000];
 
long long ans[2][110000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d%d",c+i,d+i);
		c[i]*=2;
		if(d[i]==1&&c[i]>b){
			printf("-1\n");return 0;
		}
	}
	for(int t=0;t<2;t++){
		for(int i=0;i<a;i++){
			x[i+1]=x[i]+c[i];
		}
		for(int i=0;i<=a;i++){
			z[i]=x[i]%b;
		}
		std::sort(z,z+a+1);
		for(int i=0;i<262144;i++)segtree[i]=0;
		for(int i=0;i<110000;i++)ans[t][i]=inf;
		ans[t][0]=0;
		for(int i=0;i<a;i++){
			int at=lower_bound(z,z+a+1,x[i+1]%b)-z;
			int la=query(at);
			if(la==0){
				ans[t][i+1]=x[i+1];
			}else{
				ans[t][i+1]=ans[t][la]+(long long)((x[i+1]-x[la]+b-1)/b)*b;
			}
 
			if(d[i]==1){
				long long L=(x[i]+1)%b;
				long long R=x[i+1]%b;
				int l=lower_bound(z,z+a+1,L)-z;
				int r=lower_bound(z,z+a+1,R)-z;
				if(L>R){
					update(0,131071,0,r,1,i+1);
					update(0,131071,l,131071,1,i+1);
				}else{
					update(0,131071,l,r,1,i+1);
				}
			}
		//	printf("%d: %lld\n",i+1,ans[t][i+1]);
		}
 
		reverse(c,c+a);
		reverse(d,d+a);
	}
	long long ret=inf;
	for(int i=0;i<=a;i++){
		ret=min(ret,ans[0][i]+ans[1][a-i]);
	}
 
	printf("%lld\n",ret);
}

Measured memory_bytes: 7424