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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/

// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
	os << "(" << pair_var.first << ", " << pair_var.second << ")";
	return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
	os << "{";
	for (int i = 0; i < vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
	}
	os << "}";
	return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
	os << "{";
	repi(itr, map_var) {
		os << *itr;
		itr++;
		if (itr != map_var.end()) os << ", ";
		itr--;
	}
	os << "}";
	return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
	os << "{";
	repi(itr, set_var) {
		os << *itr;
		itr++;
		if (itr != set_var.end()) os << ", ";
		itr--;
	}
	os << "}";
	return os;
}

#define DUMPOUT cerr

void dump_func() {
	DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
	DUMPOUT << head;
	if (sizeof...(Tail) > 0) {
		DUMPOUT << ", ";
	}
	dump_func(std::move(tail)...);
}
#ifdef _DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif


signed main() {

	int N;
	cin >> N;
	vector<int> A(N), B(N);
	rep(i, N) cin >> A[i];
	rep(i, N) cin >> B[i];

	// 操作回数
	int ope = 0;
	rep(i, N) ope += B[i] - A[i];

	// 項ごとに必要な操作回数
	int opeA = 0, opeB = 0;
	rep(i, N) {
		if (A[i] > B[i]) opeB += A[i] - B[i];
		else
			opeA += (B[i] - A[i] + 1) / 2;
	}

	bool ans;
	if (opeA > ope || opeB > ope) ans = false;
	else ans = true;
	
	if (ans) Yes;
	else No;


	return 0;
}


Measured memory_bytes: 384
/// Solution No.:

/// Approach:

/// Comment:

/// Verdict:

/// Report:


#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <string>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <string.h>
#include <climits>
#include <set>
#include <cassert>
#include <cfloat>
#include <stack>

///using namespace std;         /// Recommended not to use

#define p(x) std::cout<<#x<<" = "<<x<<"\n"
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
#define absolute(x) (((x)<0)?(-(x)):(x))
/// #define _DEBUG

typedef long long int ll;
typedef unsigned long long llu;
typedef long double lld;

/// lld pi = 2 * acos(0.0);   /// precision error
lld pi = 2 * acosl(0.0);

int test_case_number, test_case=1;

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
/// Direction Array
/// int dx[]={0, 0, 1, -1, -1, 1, -1, 1};
/// int dy[]={-1, 1, 0, 0, 1, 1, -1, -1};

///place for problem specific functions


void function_name()
{
    int element_number;
    scanf("%d", &element_number);
    std::vector<int>main_array(element_number), dp(element_number, INT_MAX);

    for(int &x:main_array)
    {
        scanf("%d",&x);
    }


    dp[0]=0;
    for(int i=0; i<element_number;i++)
    {
        for(int j:{i+1, i+2})
        {
            if(j<element_number)
            {
                dp[j]=std::min(dp[j], dp[i]+absolute(main_array[i]-main_array[j]));
            }
        }
    }

    printf("%d\n", dp[element_number-1]);
}
void function_name(int v1, int v2, int v3)
{

}
void function_name(std::string line)
{

}
class initial_works
{
public:

    void with_test_case_number()
    {
        scanf("%d", &test_case_number);
        ///getchar();
        while(test_case <= test_case_number)
        {
            function_name();
            test_case++;
        }
    }

    void single_iteration()
    {
        function_name();
    }

    void without_test_case_number()
    {
        int v1, v2, v3;
        while(scanf("%d %d %d", &v1, &v2, &v3)==3 && v1!=0)
        {
            function_name(v1, v2, v3);
            test_case++;
        }
    }

    void eoof()
    {
        char dummy_char_array[100];
        while(scanf("%[^\n]", dummy_char_array)!=EOF)
        {
            ///it only takes the absence of one getchar to ruin your life. Don't understand remove the getchar below and then input the sample input
            getchar();
            ///if not given getchar. the dummu_char_array will not take new input as there is newline after the first input is taken. It will continue with the previous value.
            /// So, the function will run with same argument.
            std::string line = dummy_char_array;
            function_name(line);
            test_case++;
        }
    }
};


int main()
{
    //std::ios_base::sync_with_stdio(false);
    initial_works a;
    a.single_iteration();

    return 0;
}


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

#define pb  push_back
#define ll  long long
#define INF 0x3f3f3f3f
#define pii pair<int, int>
#define ull unsigned long long int

const int t = 1005;
const int mod = 1e9 + 7;
char mat[t][t];
int memo[t][t];
int n, m;

int solve(int i, int j) {
    if (i == n - 1 && j == m - 1)
        return 1;
    if (i == n || j == m)
        return 0;
    int &ret = memo[i][j];
    if (ret != -1) return ret;
    int ans = 0;
    if (mat[i + 1][j] == '.')
        ans += solve(i + 1, j);
    if (mat[i][j + 1] == '.')
        ans += solve(i, j + 1);
    return ret = ans % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mat[i][j];
    memset(memo, -1, sizeof memo);
    cout << solve(0, 0) << "\n";
    
    //cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

Measured memory_bytes: 5248
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <cstdlib>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {

	ll a;
	cin >> a;
	cout << a + a * a + a * a * a << endl;

}


Measured memory_bytes: 3616
// g++ -std=c++11 temp.cpp
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define EACH(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3

#define MAX_N 1000

int n;
bool is_prime[1000000];

int main(){
	while(scanf("%d", &n)!=EOF){
		for(int i = 0; i <= n; i++) is_prime[i]=true;
		int res = 0;
		for(int i = 2; i <= n; i++){
			if(is_prime[i]){
				res++;
				for(int j = 2*i; j <= n; j+=i) is_prime[j]=false;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 2184
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int X = in.nextInt();

            if (N == 2) {
                if (X == 2) {
                    out.println("Yes");
                    for (int i = 1; i <= 3; i++) out.println(i);
                } else {
                    out.println("No");
                }
                return;
            }

            if (X == 1 || X == 2 * N - 1) {
                out.println("No");
                return;
            }


            out.println("Yes");
            int ans[] = new int[2 * N];

            ans[N - 1] = X + 1;
            ans[N] = X;
            ans[N + 1] = X - 1;
            int tmp = 0;
            if (X == 2 * N - 2) {
                ans[N + 2] = X - 2;
                tmp = ans[N + 2];
            } else {
                ans[N - 2] = X + 2;
                tmp = ans[N - 2];
            }
            TreeSet<Integer> all = new TreeSet<>();
            for (int i = 1; i <= 2 * N - 1; i++) {
                if (i != X - 1 && i != X && i != X + 1 && i != tmp) {
                    all.add(i);
                }
            }


            for (int i = 1; i < 2 * N; i++) {
                if (ans[i] == 0) {
                    ans[i] = all.pollFirst();
                }
            }

            for (int i = 1; i < 2 * N; i++) {
                out.println(ans[i]);
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}


Measured memory_bytes: 33768
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a;
  int b[1000000],dp[1000000]={};
  cin>>a;
  for(int i=0;i<a;i++) cin>>b[i];
  //dp[1]=abs(b[0]-b[1]);
  for(int i=1;i<a;i++){
    if(i==1) dp[i]=abs(b[i]-b[i-1]);
    else dp[i]=min(abs(b[i]-b[i-1])+dp[i-1],abs(b[i]-b[i-2])+dp[i-2]);
  }
  cout<<dp[a-1]<<"\n";
  }

Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
      string a,b;
      int ctn=0;
      cin>>a;
      while(cin>>b&&b!="END_OF_TEXT"){
            transform(b.begin(),b.end(),b.begin(),::tolower);
            if(a==b)ctn++;
      }
      cout<<ctn<<endl;
}

Measured memory_bytes: 1192
// 1100
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n, sg[N];
int tot, fir[N], nxt[N << 1], to[N << 1];

inline void add(int u, int v) {
    nxt[++tot] = fir[u], fir[u] = tot, to[tot] = v;
}

void dfs(int u, int p = 0) {
    for (int i = fir[u], v; i; i = nxt[i]) {
        v = to[i];
        if (v == p) continue;
        dfs(v, u);
        sg[u] xor_eq sg[v] + 1;
    }
}

int main() {
    cin >> n;
    for (int i = 1, u, v; i < n; ++i)
        scanf("%d%d", &u, &v), add(u, v), add(v, u);
    dfs(1);
    cout << (sg[1] ? "Alice" : "Bob") << endl;
    return 0;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int a, b; cin >> a >> b;
	string A, B;
	rep(i,b) {
		A += (a + '0');
	}
	rep(i,a) {
		B += (b + '0');
	}
	cout << min(A, B) << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0)
    return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1; // 分母
  ll numerator = 1;   // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

class UnionFind {
private:
  vector<ll> parents;

public:
  UnionFind(ll n) : parents(n, -1) {}

  bool issame(ll x, ll y) {
    return root(x) == root(y);
  }

  bool merge(ll x, ll y) {
    if (issame(x, y))
      return false;

    ll rx = root(x);
    ll ry = root(y);
    if (parents[rx] > parents[ry])
      swap(rx, ry);
    // サイズ情報を更新
    parents[rx] += parents[ry];
    // yの親を更新
    parents[ry] = rx;

    return true;
  }

  ll size(ll x) {
    return -parents[root(x)];
  }

private:
  ll root(ll x) {
    if (parents[x] < 0)
      return x;
    // 根の親の値に木の(-)サイズの情報を入れる
    return parents[x] = root(parents[x]);
  }
};

int main() {
  ll N, M;
  cin >> N >> M;

  vector<vector<ll>> P(N, vector<ll>());
  vector<pair<ll, ll>> q(M);
  for (ll i = 0; i < M; i++) {
    ll p, y;
    cin >> p >> y;
    P[p - 1].push_back(y);
    q[i] = make_pair(p - 1, y);
  }

  for (ll i = 0; i < N; i++) {
    sort(P[i].begin(), P[i].end());
    P[i].erase(unique(P[i].begin(), P[i].end()), P[i].end());
  }

  for (ll i = 0; i < M; i++) {
    ll p = q[i].first;
    ll y = q[i].second;
    auto index = lower_bound(P[p].begin(), P[p].end(), y) - P[p].begin();
    cout << setfill('0') << right << setw(6) << p + 1 << setfill('0') << right << setw(6) << index + 1 << endl;
    ;
  }

  return 0;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef set<ll> sl;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

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

int h, w;
int brd[505][505];
bool vis[505][505];

bool inRange(int y, int x) {
	return y >= 0 && y < h && x >= 0 && x < w;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	cin >> h >> w;
	rep(i,0,h) rep(j,0,w) {
		cin >> brd[i][j];
		brd[i][j] %= 2;
	}
	memset(vis, false, sizeof(vis));
	vector<pair<pii, pii> > ret;
	int y = 0;
	int x = 0;
	int dir = 0;
	while(true) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if(inRange(ny,nx) && !vis[ny][nx]) {
			if(brd[y][x]%2) {
				ret.pb(mp(mp(y,x), mp(ny,nx)));
				brd[ny][nx]++;
				brd[y][x]--;
			}
			vis[y][x] = true;
			y = ny;
			x = nx;
		} else {
			dir = (dir+1)%4;
			ny = y + dy[dir];
			nx = x + dx[dir];
			if(!inRange(ny,nx) || vis[ny][nx]) {
				break;
			}
			if(brd[y][x]%2) {
				ret.pb(mp(mp(y,x), mp(ny,nx)));
				brd[ny][nx]++;
				brd[y][x]--;
			}
			vis[y][x] = true;
			y = ny;
			x = nx;
		}
	}

	cout << ret.size() << '\n';
	rep(i,0,sz(ret)) {
		cout << ret[i].F.F+1 << ' ' << ret[i].F.S+1 << ' ';
		cout << ret[i].S.F+1 << ' ' << ret[i].S.S+1 << '\n';
	}
	return 0;
}


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

int main(){
  int N;
  cin >> N;
  int k=0;
  for (int i=1; i<=N; i++){
    k+=i;
    if (k==N){
      k=i;
      break;
    }
    if (k>N){
      cout << "No" << endl;
      return 0;
    }
  }
  vector<vector<int>> ans(k+1);
  int num = k;
  int ind = 0;
  for (int i=1; i<=N; i++){
    ans[ind].push_back(i);
    if(ans[ind].size()==num){
      num--;
      ind++;
    }
  }
  int lst = 1;
  int hoge = 1;
  int i=1;
  while(i<=N){
    ans[hoge].push_back(i);
    hoge++;
    i++;
    if (hoge==k+1){
      lst++;
      hoge=lst;
    }
  }
  cout << "Yes" << endl;
  cout << k+1 << endl;
  for (auto vec: ans){
    cout << k;
    for (auto j: vec){
      cout << ' ' << j;
    }
    cout << endl;
  }
}


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

int main()
{
  vector<vector<char>> vec(3, vector<char>(3));
  for(int i = 0; i < 3; i++)
  {
    for(int j = 0; j < 3; j++)
    {
      cin >> vec.at(i).at(j);
    }
  }
  
  cout << vec.at(0).at(0) << vec.at(1).at(1) << vec.at(2).at(2) << endl;
}

Measured memory_bytes: 256
n, m = gets.chomp.split(" ").map(&:to_i);
arr = n.times.map{gets.split.map(&:to_i)}
arr = arr.sort
ans = 0
index = 0
while m > 0 do
	tmp = [m, arr[index][1]].min
	m -= tmp
	ans += arr[index][0] * tmp
	index += 1
end
puts ans

Measured memory_bytes: 22388
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a;
  cin >> a;
  if (a[0]!=a[1]&&a[1]!=a[2]&&a[2]!=a[0]){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
def ma():return map(int,input().split())
def nli(x):return [int(input()) for _ in range(x)]
def hukusuu():
  listA=[] #appendのために宣言が必要
  while True:
    try:listA.append(list(map(int,input().split())))
    except:break #または、quit(),os.exit()をして止める。
  return listA

def ifif(s):
  if s:print("Yes")
  else:print("No")

n,k,q=ma()

b=[0]*n
for i in range(q):
  ai=int(input())-1
  b[ai]+=1 

for i in range(n):
  ifif(k-q+b[i]>0)

Measured memory_bytes: 4680
import sys
from itertools import accumulate
from bisect import bisect_left as bi_l

n, *a = map(int, sys.stdin.read().split())

def main():
    s = list(accumulate(a))

    ans = float('inf')
    for center in range(1, n-2):
        pq = s[center]
        left = bi_l(s, pq / 2)
        if left == 0:
            p = s[0]
        else:
            if pq - s[left] < s[left-1]:
                left -= 1
            p = s[left]
        q = pq - p

        rt = s[-1] - pq
        right = bi_l(s, pq + rt / 2)
        if right == center + 1:
            r = s[center+1] - pq
        else:
            if rt - (s[right] - pq) < s[right-1] - pq:
                right -= 1
            r = s[right] - pq
        t = rt - r

        res = sorted([p, q, r, t])
        ans = min(ans, res[-1] - res[0])

    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 24996
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>

//#include<bits/stdc++.h>



using namespace std;




int main() {
	
	int n;
	cin>>n;
	vector<vector<int>>t(n,vector<int>(0));
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		for(int j=0;j<b;j++){
			int x;
			cin>>x;x--;t[i].push_back(x);
		}
	}
	queue<int>r;
	r.push(0);
	int g[105]={1000000};
	for(int i=0;i<n;i++){
		g[i]=10000000;
	}
	g[0]=0;
	set<int>p;
	p.insert(0);
	bool f[105]={};
	while(r.size()||p.size()<n){
		if(!r.size()){
			for(int i=0;i<n;i++){
				if(g[i]==10000000){
					g[i]=-1;
					p.insert(i);
					//r.push(i);
				}
			}
		}
		else{
		int v=r.front();
		for(int i=0;i<t[v].size();i++){
			if(!f[t[v][i]]){
				f[t[v][i]]=1;
			r.push(t[v][i]);
			p.insert(t[v][i]);
			g[t[v][i]]=min(g[t[v][i]],g[v]+1);
			}
			
		}
		r.pop();
		
		}
	}
	for(int i=0;i<n;i++)
		cout<<i+1<<" "<<g[i]<<endl;

	
	return 0;
}


	

Measured memory_bytes: 3156
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let x: usize = read();
    let y: usize = read();
    println!("{}", y / 2 + x);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin>>N;
  bool a=true;
  for(int i=0; i<50000; i++){
    if(floor(i*1.08)==N){
      cout<<i<<endl;
      a=false;
      break;
    }
  }
  if(a){
    cout<<":("<<endl;
  }
}


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

int main()
{
  ll n;
  cin >> n;
  vector<ll> x(n, 0);
  vector<ll> y(n, 0);

  ll c = n / 2;

  for (ll i = 0; i < n; i++)
  {
    cin >> x[i];
    y[i] = x[i];
  }
  sort(y.begin(), y.end());

  for (ll i = 0; i < n; i++)
  {
    if (x[i] <= y[(n / 2) - 1])
    {
      cout << y[n / 2] << endl;
    }
    else
    {
      cout << y[(n / 2) - 1] << endl;
    }
  }
}


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



int main(){
	int n;
	cin >> n;
	vector<long long>a(n),b(n),v(n);
	rep(i,n)cin >> a[i];
	rep(i,n)v[a[i]-1]++;
	rep(i,n){
		if(v[i]>=2){
			b[i]=v[i]*(v[i]-1)/2;
		}
	}
	long long sum=0;
	rep(i,n)sum+=b[i];
	rep(i,n)cout << sum-(v[a[i]-1]-1) << endl;
		

		
}


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

int main()
{
	string a[3];
	for (int i = 0; i < 3; ++i)
	{
		cin >> a[i];
	}
	sort(a, a + 3, greater<string>());
	cout << stoi(a[0] + a[1]) + stoi(a[2]) << endl;
	return 0;
}

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

int main()
{
    string s;
    cin >> s;
    int ans = 1 << 20;
    int n = s.size();
    for (int i = 0; i <= n - 3; i++)
    {
        int x = 0;
        int base = 1;
        for (int j = 2; - 1 < j; j--)
        {
            x += base * (s[i + j] - '0');
            base *= 10;
        }
        ans = min(ans, abs(x - 753));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
typedef vector<long long> V;
typedef vector<V> VV;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<28;
void solve(int a){cout<<( a?"Yes":"No")<<endl;}
int main(){
	int n;
	double ans=0.0;
	pair<int,int>d(0,0);
	cin >>n;
	int fact=1;
	vector<pair<int,int>>p(n,pair<int,int>(0,0));
	rep(i,n){
		cin>>p[i].F>>p[i].S;
		fact*=(i+1);
	}
	sort(all(p));
	do{
		for(auto itr=p.begin();itr!=p.end();itr++){
			if(itr!=p.begin()){
			
			ans += hypot((itr->F )-(d.F), (itr->S) -(d.S) );
			}
			d.F=itr->F;
			d.S=itr->S;
		}
	}while(next_permutation(all(p)));
	printf("%.9lf\n",ans/(double)fact);
	//cout<<fact<<endl;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long H, long long W, long long h, long long w){
    int ans = H * W - (h * W) - (H * w) + (h * w);
    cout << ans << endl;
}

int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    long long h;
    scanf("%lld",&h);
    long long w;
    scanf("%lld",&w);
    solve(H, W, h, w);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,Q,s[300010],top;
long long t[300010],sum[300010],f[300010],g[300010],h[300010];
double slope(long long a,long long b)
{
	return 1.0*(1.0*(f[a]+sum[a]+(a*a-a)/2ll)-1.0*(f[b]+sum[b]+(b*b-b)/2ll))/(1.0*a-1.0*b);
}
double slope1(long long a,long long b)
{
	return 1.0*(1.0*(g[a]+sum[a]+(a*a-a)/2ll)-1.0*(g[b]+sum[b]+(b*b-b)/2ll))/(1.0*a-1.0*b);
}
double slope2(long long a,long long b)
{
	return 1.0*(1.0*(g[a+1]-sum[a]+(a*a+a)/2ll)-1.0*(g[b+1]-sum[b]+(b*b+b)/2ll))/(1.0*a-1.0*b);
}
void solve(int l,int r)
{
	if(l==r)
	{
		h[l]=f[l-1]+g[l+1]+1ll-t[l];
		return ;
	}
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	top=0;
	for(int i=l-1;i<mid;i++)
	{
		while(top>1&&slope(s[top],s[top-1])<=slope(i,s[top]))
			top--;
		s[++top]=i;	
	}
	int now=1;
	long long maxn=-(1ll<<62);
	for(int i=r;i>mid;i--)
	{
		while(now<top&&slope(s[now],s[now+1])>=i)
			now++;
		maxn=max(maxn,f[s[now]]+(long long)(i-s[now])*(i-s[now]+1)/2ll-sum[i]+sum[s[now]]+g[i+1]);
		h[i]=max(maxn,h[i]);
	}
	top=0;
	for(int i=mid+1;i<=r;i++)
	{
		if(top>1&&slope2(s[top],s[top-1])<=slope2(i,s[top]))	
			top--;
		s[++top]=i;
	}	
	now=top;maxn=-(1ll<<62);
	for(int i=l-1;i<mid;i++)
	{
		while(now>1&&slope2(s[now],s[now-1])<=i)
			now--;
		maxn=max(maxn,f[i]+(long long)(s[now]-i)*(s[now]-i+1)/2ll+sum[i]-sum[s[now]]+g[s[now]+1]);	
		h[i+1]=max(maxn,h[i+1]);
	}
}
int main()
{
	//freopen("f1.out","w",stdout);
	//memset(h,-63,sizeof(h));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t[i]);
		sum[i]=sum[i-1]+t[i];	
	}
	top=1;
	s[top]=0;
	for(int i=1;i<=n;i++)
	{
		while(top>1&&slope(s[top],s[top-1])<=i)
			top--;
		f[i]=f[s[top]]-sum[i]+sum[s[top]]+(long long)(i-s[top])*(i-s[top]+1)/2ll;
		f[i]=max(f[i],f[i-1]);
		while(top>1&&slope(s[top],s[top-1])<=slope(i,s[top]))
			top--;
		s[++top]=i;
	}
	reverse(t+1,t+n+1);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	top=1;
	s[top]=0;
	for(int i=1;i<=n;i++)
	{
		while(top>1&&slope1(s[top],s[top-1])<=i)
			top--;
		g[i]=g[s[top]]-sum[i]+sum[s[top]]+(long long)(i-s[top])*(i-s[top]+1)/2ll;
		g[i]=max(g[i],g[i-1]);
		while(top>1&&slope1(s[top],s[top-1])<=slope1(i,s[top]))
			top--;
		s[++top]=i;
	}
	g[n+1]=0; 
	reverse(g+1,g+n+1);
	reverse(t+1,t+n+1);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	/*for(int i=1;i<=n;i++)
		printf("%lld ",f[i]);
	cout<<endl;
	for(int i=1;i<=n;i++)
		printf("%lld ",g[i]);
	cout<<endl;*/
	solve(1,n);
	/*for(int i=1;i<=n;i++)
		printf("%lld\n",h[i]);*/
	//cout<<endl;
	scanf("%d",&Q);
	while(Q--)
	{
		int p;
		long long x;
		scanf("%d%lld",&p,&x);
		printf("%lld\n",max(f[p-1]+g[p+1],h[p]+t[p]-x));
	}
	return 0;
}

Measured memory_bytes: 14848
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9 + 7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4] ={ 1,0,-1,0 };
int dy[4] ={ 0,1,0,-1 };

int N, K;
string S;

signed main() {
	cin >> S;
	int ans = 0;
	rep(i, S.size()){
		if(S[i] == '2') ans++;
	}
	cout << ans << endl;
}

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

int main()
{
  int n;
  int64_t ans = 1;
  vector<int64_t> a(100000);
  bool flag = true;

  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i < n; i++)
  {
    if (a[i] == 0)
    {
      flag = true;
      ans = 0;
      break;
    }
    if (a[i] < (int64_t)pow(10, 9) * (int64_t)pow(10, 9) / ans + 1)
      ans *= a[i];
    else
      flag = false;
  }
  cout << (flag ? ans : -1) << endl;
}

Measured memory_bytes: 3876
S = input()[::-1]

s = S[::]
a = 'dream'[::-1]
b = 'dreamer'[::-1]
c = 'erase'[::-1]
d = 'eraser'[::-1]

# print(S)
idx = 1
for i in range(1, len(S)):
    if s[:idx] in [a, b, c, d]:
        # print('sだよ')
        # print('カット')
        # print(s[:idx])
        # print(i)
        # print('s[idx:]だよ', s[idx:])
        s = s[idx:]
        # print('カット後のsだよ', s)
        # print()
        idx = 0
    idx += 1
    # print('ほげ', s[:idx])
if s[:idx] in [a, b, c, d]:
    s = []

if len(s) == 0:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 3316
n,m = map(int,input().split())
onof = []
for i in range(m):
    lst1 = list(map(int,input().split()))
    lst1 = lst1[1:]
    onof.append(tuple(lst1))

p = list(map(int,input().split())) #0or1

#ビット全探索
def bit_search(lst):
    keta = len(lst)
    bit_lst = []
    for i in range(2**keta):
        sub = []
        for j in range(keta):
            if ((i>>j) &1):
                sub.append(lst[j])
        bit_lst.append(sub)

    return bit_lst

bit_lst = []
for i in range(1,n+1):
    bit_lst.append(i)

bit_lst = bit_search(bit_lst)

ans = 0
for i in bit_lst:
    flag = 1
    for j in range(m): #m個の電球について
        res = 0
        for k in onof[j]: #それぞれのbitについて
            if k in i:
                res += 1
        if res%2!=p[j]:
            flag = 0
            break
    if flag:
        ans += 1

print(ans)

Measured memory_bytes: 41328
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};

int N;
ll L, T;
vector<ll> X;
vector<int> W;

int main(){
    cin >> N >> L >> T;
    X.resize(N);  W.resize(N);
    rep(i,N) cin >> X[i] >> W[i];
//-------------------------------------------
    vector<ll> tmp(N);
    rep(i,N){
        if(W[i]==1) tmp[i] = (X[i]+T)%L;
        else /*tmp[i] = ((X[i]-T)%L+L)%L;*/ tmp[i] = (X[i]-T)%L;
    }

    int cnt = 0;
    rep(i,N){
        if(W[i]==1) cnt += (X[i]+T)/L;
        else{
            //if(T > X[i])
              //  cnt -= 1+(T-X[i])/L;
            cnt += (X[i]-T)/L;
            if((X[i]-T)%L<0) tmp[i]+=L, cnt--;
        }
    }
    int flag = (cnt%N+N)%N;
    sort(tmp.begin(), tmp.end());
//-------------------------------------------
    for(int i = flag; i < N; i++) cout << tmp[i] << endl;
    for(int i = 0; i < flag; i++) cout << tmp[i] << endl;
}

Measured memory_bytes: 3200
N,M = list(map(int,input().split()))
X = sorted(list(map(int,input().split())))
A = []
if N >= M:
    print(0)
    exit()
for i in range(M-1):
    A.append(X[i+1]-X[i])
print(X[-1]-X[0]-sum(sorted(A,key=lambda x: -x)[:N-1]))

Measured memory_bytes: 13968
#include "math.h"
#include <algorithm>
#include <iostream>
#include <list>
#include <map> //連想配列
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector> //動的配列

#define rep(i, N) for (int i = 0; i < N; i++)

using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int max = 0;
  if (max < a) {
    max = a;
  }
  if (max < b) {
    max = b;
  }
  if (max < c) {
    max = c;
  }

  a = max - a;
  b = max - b;
  c = max - c;

  int count = 0;
  count = count + a / 2 + b / 2 + c / 2;
  int tmp = a % 2 + b % 2 + c % 2;
  if (tmp == 2) {
    count++;
  } else if (tmp == 1) {
    count = count + 2;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
def dfs(v, time_, d, f, dp):
    if d[v] == 0:
        d[v] = time_
    for i in range(len(dp[v])):
        if d[dp[v][i]] == 0:
            time_ = dfs(dp[v][i], time_ + 1, d, f, dp)
    f[v] = time_ + 1
    return time_ +  1


def main():
    N = int(input())
    dp = [[] for i in range(N)]
    for i in range(N):
        line = [int(k) for k in input().split()]
        for j in range(len(line)):
            if j == 0 or j == 1:
                continue
            dp[line[0] - 1].append(line[j] - 1)

    d = [0] * N
    f = [0] * N
    time_ = 1
    for i in range(N):
        if d[i] == 0:
            time_ = dfs(i, time_, d, f, dp)
            time_ += 1
    for i in range(N):
        print(i + 1, d[i], f[i])

if __name__ == '__main__':
    main()



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

using namespace std;

int Q;
int x[100005],cnt[100005];

bool prime(int n){

  if(n==1) return 0;

  for(int i=2; i*i<=n; i++){
    if(n%i==0){
      return 0;
    }
  }

  return 1;

}

int main() {

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

cin>>Q;

for(int i=1; i<=100000; i++){
  if(i%2==0) continue;
  if(prime(i)&&prime((i+1)/2)) x[i]=1;
}

for(int i=1; i<=100000; i++){
  cnt[i]=cnt[i-1]+x[i];
}

for(int i=0; i<Q; i++){
  int l,r;
  cin>>l>>r; 
  cout<<endl;
  int ans=cnt[r]-cnt[l-1];
  cout<<ans<<endl;
}

}


Measured memory_bytes: 1536
#include<cstdio>
main(){int a,b,d=0,c;while(scanf("%d%d",&a,&b),a){d++&&puts("");c=0;for(;a<=b;a++)if(a%4<1&&a%25||a%16<1)c++,printf("%d\n",a);if(!c)puts("NA");}}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n, d;
    cin >> n >> d;
    
    int x, y, ans = 0;
    for(int i = 0;i < n;i++){
        cin >> x >> y;
        if( pow(pow(x, 2) + pow(y, 2), 0.5) <= d){
            ans++;
        }
    }
    
    cout << ans;
    
    return 0;
}


Measured memory_bytes: 4292
import math
N, D = map(int, input().split())
P = []
for _ in range(N):
    P.append(list(map(int, input().split())))

ans = 0
for i in range(N+1):
    for j in range(i+1, N):
        distance = 0
        for d in range(D):
            distance += (P[i][d]-P[j][d]) ** 2
        distance = math.sqrt(distance)
        if distance.is_integer():
            ans += 1
print(ans)

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

int n;
int a[210];

int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 0;

    while(true) {
        bool odd = false;
        for (int i = 0; i < n; i++){
            if (a[i] % 2 != 0) odd = true;  
        }
        if (odd) break;

        for (int i = 0; i<n; i++){
            a[i] /= 2;
        }
        ans++;
    } 
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
#include <set>
using namespace std;


int main() {
  int a, b;
  cin >> a >> b;
  if (a <= 8 && b <= 8) {
	  cout << "Yay!" << endl;
	} else {
	  cout << ":(" << endl;
	}
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>

using namespace std;

int color[100];
int d[100];
int f[100];
int G[100][100];
int nt[100];
int n;

int WHITE = 1;
int GRAY = 2;
int BLACK = 3;

int _time = 0;

int next(int u) {
  for (int v = nt[u]; v < n; v++) {
    nt[u] = v + 1;
    if (G[u][v]) return v;
  }

  return -1;
}

void dfs(int r) {
  for (int i = 0; i < n; i++) nt[i] = 0;

  queue<int> S;

  S.push(r);
  color[r] = GRAY;

  while(!S.empty()){
    int u = S.front();

    while(1) {
      int v = next(u);

      if(v != -1) {
        if(color[v] == WHITE) {
          color[v] = GRAY;

          S.push(v);

          d[v] = d[u] + 1;
        }
      } else {
        break;
      }
    }

    S.pop();
  }
}

void dfs_init() {
  for(int i = 0; i < n; i++) {
    color[i] = WHITE;
  }

  dfs(0);

  for(int i = 0; i < n; i++) {
    if(color[i] == WHITE) {
      d[i] = -1;
    }
  }
}

int main() {
  int m, k, l;
  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> k;
    cin >> m;

    for (int j = 0; j < m; j++) {
      int l;
      cin >> l;

      G[k-1][l-1] = 1;
    }
  }

  for (int i = 0; i < n; i++) {
    dfs_init();
  }

  for (int i = 0; i < n; i++) {
    cout << i+1 << " " << d[i] << endl;
  }
}



Measured memory_bytes: 3112
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] height = new int[10];
		for(int i=0;i<10;i++) {
			height[i] = sc.nextInt();
		}
		Arrays.sort(height);
		for(int i=0;i<3;i++) {
			System.out.println(height[9-i]);
		}
	}

}

Measured memory_bytes: 17280
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vs = vector<string>;
using vvs = vector<vs>;
using pli = pair<long long, int>;
using vpli = vector<pli>;

int main() {
  ll r;
  cin >> r;
  
  cout << r * r << endl;
  
}

Measured memory_bytes: 256
n = int(input())
s = input()

count_R = [0]
count_G = [0]
count_B = [0]
d = {'R': count_R, 'G': count_G, 'B': count_B}
for c in s:
    count_R.append(count_R[-1]+1) if c == 'R' else count_R.append(count_R[-1])
    count_G.append(count_G[-1]+1) if c == 'G' else count_G.append(count_G[-1])
    count_B.append(count_B[-1]+1) if c == 'B' else count_B.append(count_B[-1])

res = 0
for i in range(n-2):
    for k in range(i+1, n-1):
        if s[i] == s[k]:
            continue
        st = {'R', 'G', 'B'}
        st.discard(s[i])
        st.discard(s[k])
        c = st.pop()
        cnt = d[c]
        res += cnt[-1] - cnt[k]
        if k+k-i < n and s[k+k-i] == c:
            res -= 1

print(res)


Measured memory_bytes: 68748
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        self.link(self.find_set(u), self.find_set(v))

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def link(self, u, v):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]

    def comb(self, u):
        sz = self.get_size(u)
        return sz * (sz - 1) // 2


uf = UnionFind(n)

ans = [0]
sm = 0
for a, b in ab[-1:0:-1]:
    a -= 1
    b -= 1
    if not uf.same(a, b):
        sm -= uf.comb(a) + uf.comb(b)
        uf.unite(a, b)
        sm += uf.comb(a)
    ans.append(sm)

ans = [n * (n - 1) // 2 - e for e in ans[::-1]]
print(*ans, sep="\n")


Measured memory_bytes: 40940
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[]srgs) {
	Scanner scan=new Scanner(System.in);
	List<Integer> list=new ArrayList<Integer>();
	int a=scan.nextInt();
	for(int i=0;i!=a;i++) {
		int b=scan.nextInt();
		if(!list.contains(b)) {
			list.add(b);
		}
	}
	System.out.println(list.size());
	scan.close();
}
}

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
struct UnionFind {
  vector<int> parent;
  UnionFind (int n) { parent.assign(n, -1); }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (parent[y] < parent[x]) swap(x, y);
    if (parent[x] == parent[y]) --parent[x];
    parent[y] = x;
    return true;
  }
};
typedef long double ld;
typedef ld Weight;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;

// Kruskal
// N, operator <
Edges kruskal(int V, Edges &es) {
  sort(es.rbegin(), es.rend());
  UnionFind uf(V);
  Edges res;
  REP(i, es.size()) {
    Edge e = es[i];
    if(uf.root(e.src) != uf.root(e.dest)) {
      uf.merge(e.src, e.dest);
      res.push_back(e);
    }
  }
  return res;
}

int main() {
  while(1){
    int n;
    cin>>n;
    if(!n)break;
    vector<tuple<ld,ld,ld,ld>> vp;
    REP(i,n){
      ld x,y,z,r;
      cin>>x>>y>>z>>r;
      vp.emplace_back(x,y,z,r);
    }
    Edges es;
    REP(i,n)REP(j,i) {
      ld x1,y1,z1,r1,x2,y2,z2,r2;
      tie(x1,y1,z1,r1) = vp[i];
      tie(x2,y2,z2,r2) = vp[j];
      ld d = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) + (z2-z1)*(z2-z1));
      es.push_back((Edge){i,j,max((ld)0,d-r1-r2)});
    }
    auto res = kruskal(n, es);
    ld sum = 0;
    for(auto e:res) sum += e.weight;
    cout<<setprecision(3)<<fixed<<sum<<endl;
  }
  return 0;
}

Measured memory_bytes: 1712
import math
n = int(input())

def factors(a):
    b = int(math.sqrt(a))
    f = []
    for i in range(1, b+1):
        if a % i == 0:
            f.append(i)
            f.append(a//i)
    return len(f)

def solve():
    if n < 105:
        print(0)
        return
    ans = 0
    for i in range(105, n+1, 2):
        if factors(i) == 8:
           ans += 1
    print(ans)
solve()


Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>

using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}


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

Measured memory_bytes: 1024
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
using namespace std;
typedef long long int LL;
typedef unsigned long long int ULL;

int main() {
    string str;
    cin >> str;
    int n = str.length();
    LL res = 0;
    for (unsigned bit = 0; bit < (1 << (n - 1)); bit++) {
        int left = 0;
        for (int i = 0; i < n - 1; i++) {
            if (bit & (1 << i)) {
                res += stoll(str.substr(left, i + 1 - left));
                left = i + 1;
                // cout << res << endl
                    ;
            }
        }
        if (left < n) {
            res += stoll(str.substr(left, n - left + 1));
            // cout << res << endl;
        }
    }

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


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second

Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

int main() {
    string s;
    cin >> s;
    string t[7] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    for (Int i = 0; i < 7; i++) {
        if (s == t[i]) {
            dump(7 - i);
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[N][N];

void dijkstra(){
  int d[N],color[N];
 int i,j,v,sum=0,min,u;
  for(i=0;i<n;i++){
    d[i]=INFTY;
    color[i]=WHITE;
  }
  d[0]=0;
  //color[0]=GRAY;
  
  while(1){
    min=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(min>d[i] && color[i]!=BLACK){
	u=i;
	min=d[i];//????°????????????¨??\??????
      }
    }
    if(u==-1)break;
    color[u]=BLACK;
    for(v=0;v<n;v++){//u?????????v???????????§
      if(color[v]!=BLACK && M[u][v]!=INFTY){
	if(d[v]>M[u][v]+d[u]){//???????????£??\??????????????????????????????????????????????±???????
	  d[v]=d[u]+M[u][v];
	  
	  // p[v]=u;//???
	  color[v]=GRAY;//?¨????
	}
      }
    }
  }

  for(i=0;i<n;i++){
    printf("%d %d\n",i,d[i]);
  }
  
}

int main(){
  int i,j;
  int k,u,c,v;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=INFTY;
    }
  }

  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d %d",&v,&c);
      M[u][v]=c;
    }
  }

  dijkstra();

  return 0;
}

Measured memory_bytes: 636
// Last Change: 06/13/2019 17:38:31.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

const ll MOD = 1e9 + 7;

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

  const ll size = L.size();
  // 0が同じ、1が小さい
  vector<vector<ll>> bitDP(size, vector<ll>(2, 0));

  // L != 0
  bitDP[0][0] = 2;
  bitDP[0][1] = 1;

  /*
  if (size > 1) {
    if (L[1] == '0') {
      bitDP[1][0] = 2;
      bitDP[1][1] = 3;
    } else {
      bitDP[1][0] = 4;
      bitDP[1][1] = 2;
    }
  }*/

  for (ll i = 0; i < size - 1; ++i) {
    if (L[i + 1] == '0') {
      bitDP[i + 1][0] = bitDP[i][0];
      bitDP[i + 1][1] = (3 * bitDP[i][1]) % MOD;
    } else {
      bitDP[i + 1][0] = (2 * bitDP[i][0]) % MOD;
      bitDP[i + 1][1] = (3 * bitDP[i][1] + bitDP[i][0]) % MOD;
    }
  }

  // cout << bitDP[size - 1][0] << ' ' << bitDP[size - 1][1] << endl;
  cout << (bitDP[size - 1][0] + bitDP[size - 1][1]) % MOD << endl;

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 6456