akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main(void)
{
	int i,j;
	int n;
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
	{
		if(i%3==0)
		{
			printf(" %d",i);
		}
		else
		{
			for(j=i;j>0;)
			{
				if(j%10==3)
				{
					printf(" %d",i);
					break;
				}
				j/=10;
			}
		}
	}
	printf("\n");
	
	return 0;
}


Measured memory_bytes: 2132
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    int a, b, c, d, e, k; cin >> a >> b >> c>> d >> e >> k;

    if(e-a > k) dunk(":(");
    else dunk("Yay!");
}
    

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
template<typename T> void chadd(T& a, T b) { a = a + b; }

namespace {  // 名前なし名前空間
	// gcd, lcm は C++17 でstdに標準入りしたので言語のバージョンに注意
	// 最大公約数
	ll gcd(ll a, ll b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

	// 最小公倍数
	ll lcm(ll a, ll b) {
		return a / gcd(a, b) * b;
	}
}

int main() {

	string s;
	cin >> s;

	char odd[] = { 'R', 'U', 'D' };
	char even[] = { 'L', 'U', 'D' };

	bool ok = true;

	rep(i, (int)s.size()) {
		bool can = false;
		if (i % 2 == 0) {
			rep(j, 3) {
				if (s[i] == odd[j]) {
					can = true;
					break;
				}
			}
		}
		else {
			rep(j, 3) {
				if (s[i] == even[j]) {
					can = true;
					break;
				}
			}
		}
		if (!can) {
			ok = false;
			break;
		}
	}

	if (ok) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


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

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

  vector<bool> a(26);
  for (int i = 0; i < s.size(); i ++) {
    a.at(s.at(i) - 'a') = true;
  }

  for (int i = 0; i < 26; i ++) {
    if (!a.at(i)) {
      char ans = i + 'a';
      cout << ans << endl;
      return 0;
    }
  }

  cout << "None" << endl;
}


Measured memory_bytes: 512
import java.util.*;
class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  int n=sc.nextInt(),k=sc.nextInt();
  int po[]=new int[n];
  for(int i=0;i<k;i++){
      int d=sc.nextInt();
      for(int j=0;j<d;j++){
          po[sc.nextInt()-1]++;
      }
  }
  int sum=0;
  for(int i=0;i<n;i++){
    if(po[i]==0)sum++;
  }
  System.out.println(sum);
}
}

Measured memory_bytes: 45952
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		if(N==1) {
			System.out.println("Hello World");
		}else {
			int A=sc.nextInt();
			int B=sc.nextInt();
			System.out.println(A+B);
		}
	}
}

Measured memory_bytes: 35444
#include <stdio.h>
int main (void){

  int k = 0;
  int a = 0;

  scanf("%d", &k);

  if(k%2 == 0){
    a = ((k/2) * (k/2));
  }else{
    a = ((k-1)/2) * ((k + 1)/2);
  }

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


Measured memory_bytes: 128
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

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

    let mut ans = 0;
    for i in 0..s+1 {
        for j in i..s+1 {
            let x = i;
            let y = j-i;
            let z = s-j;
            if x>k || y>k || z>k {
                continue;
            } else {
                ans += 1;
            }
        }
    }

    println!("{}", ans);

}


Measured memory_bytes: 2204
/* ***********************************************
Author        :taciturnity
Created Time  :2020/2/21 8:23:51
File Name     :TEST.cpp
************************************************ */

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <cmath>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <unordered_map>
#define ll long long
#define INF 0x3f3f3f3f
#define rep(i,x,y) for(int i = x;i <= y;++i)
#define fori(i,x,y) for(int i = x;i >= y; -- i)
#define bug puts("--------------")
#define out(x) cout<<x<<'\n';
inline char gc(){char op[2];scanf("%s",op);return op[0];}
const int N =5e5+10;
const double eps = 0.00000001;
const ll mod = 1e9 ;
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    int n = read();
    ll sum = 0;
    rep(i,1,n){
        rep(j,1,n){
            rep(k,1,n){
                int tmp = __gcd(i,j);
                tmp = __gcd(tmp,k);
                sum += tmp;
            }
        }
    }
    cout <<sum;
}

Measured memory_bytes: 3652
# coding:utf-8
import fractions


def main():
    N = int(input())
    # N = 10 ** 5
    num = list(map(int, input().split()))
    # num = list(range(1, 10**5 + 1))
    # num.sort()
    gcd = 0
    gcd_list_front = []
    gcd_list_back = []
    gcd_list_front.append(num[0])
    gcd_list_back.append(num[-1])

    for i in range(1, N-1):
        gcd_list_front.append(fractions.gcd(gcd_list_front[i-1], num[i]))
        gcd_list_back.append(fractions.gcd(gcd_list_back[i-1], num[-i-1]))

    gcd_list_back.reverse()
    # print(gcd_list_front)
    # print(gcd_list_back)

    gcd = max(gcd_list_back[0], gcd_list_front[-1])

    for i in range(0, N-2):
        # print(gcd_list_front[i], gcd_list_back[i+1])
        temp_gcd = fractions.gcd(gcd_list_front[i], gcd_list_back[i+1])
        if temp_gcd > gcd:
            gcd = temp_gcd

    print(gcd)
    # ans = 0
    # print()


if __name__ == "__main__":
    main()


Measured memory_bytes: 16124
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
using namespace std;
vector<ll> v;
vector<string> vs;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(110, vector<ll>(50, 0));
vector<tuple<ll, ll, ll>> vt;
map<ll, ll> mp;

typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

int main()
{
	ll n, m;
	cin >> n >> m;
	vector<pair<ll, ll>> va, vb;
	REP(i, n + m)
	{
		ll a, b;
		cin >> a >> b;
		if (i < n) va.emplace_back(a, b);
		else vb.emplace_back(a, b);
	}
	REP(i, n)
	{
		ll cost = INF, ans = -1;
		REP(j, m)
		{
			ll tmp = abs(va[i].first - vb[j].first) + abs(va[i].second - vb[j].second);
			if (cost > tmp) {
				cost = tmp;
				ans = j;
			}
		}
		cout << ans + 1 << endl;
	}
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

typedef tuple<ll,ll,ll,ll> e; //to,cost,hour,company
typedef tuple<ll,ll,ll,ll> V; //cost,where,hour,pass

#define MT make_tuple


int main(){
    ll n,m,h,k;
    while(cin>>n>>m>>h>>k){
        if(n==0){break;}
    vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(h+1,vector<ll>(1LL<<k,E)));
    vector<vector<e>> edge(n);
    for(int i=0;i<m;i++){
        ll a,b,c,h,r;
        cin>>a>>b>>c>>h>>r;
        a--; b--; r--;
        edge[a].push_back(MT(b,c,h,r));
        edge[b].push_back(MT(a,c,h,r));
    }
    ll s,T;
    cin>>s>>T;
    s--; T--;
    priority_queue<V,vector<V>,greater<V>> Q;
    for(ll i=0;i<1LL<<k;i++){
        dp[s][0][i]=0;
        Q.push(MT(0,s,0,i));
    }
    while(!Q.empty()){
        V w=Q.top(); Q.pop();
        if(dp[get<1>(w)][get<2>(w)][get<3>(w)]!=get<0>(w)){continue;}
        //cout<<get<0>(w)<<" "<<get<1>(w)<<" "<<get<2>(w)<<" "<<get<3>(w)<<endl;
        for(auto &i:edge[get<1>(w)]){
            if(get<2>(w)+get<2>(i)>h){continue;}
            if(get<3>(w)>>get<3>(i)&1){
                if(dp[get<0>(i)][get<2>(w)+get<2>(i)][get<3>(w)]>get<0>(w)){
                    dp[get<0>(i)][get<2>(w)+get<2>(i)][get<3>(w)]=get<0>(w);
                    Q.push(MT(get<0>(w),get<0>(i),get<2>(w)+get<2>(i),get<3>(w)));
                }
            }
            else{
                if(dp[get<0>(i)][get<2>(w)+get<2>(i)][get<3>(w)]>get<0>(w)+get<1>(i)){
                    dp[get<0>(i)][get<2>(w)+get<2>(i)][get<3>(w)]=get<0>(w)+get<1>(i);
                    Q.push(MT(get<0>(w)+get<1>(i),get<0>(i),get<2>(w)+get<2>(i),get<3>(w)));
                }
            }
        }
    }
    ll P;
    cin>>P;
    vector<ll> dp2(1LL<<k,E);
    dp2[0]=0;
    for(int i=0;i<P;i++){
        ll l,d;
        cin>>l>>d;
        ll K=0;
        for(int t=0;t<l;t++){
            ll k;
            cin>>k;
            k--;
            K|=1LL<<k;
        }
        dp2[K]=min(dp2[K],d);
    }
    for(int i=1;i<dp2.size();i++){
        for(ll t=i;t>0;t=(t-1)&i){
            dp2[t]=min(dp2[t],dp2[i]);
        }
    }
    for(int i=1;i<dp2.size();i++){
        for(ll t=i;t>0;t=(t-1)&i){
            dp2[i]=min(dp2[i],dp2[i^t]+dp2[t]);
        }
    }
    ll ans=E;
    for(int i=0;i<1LL<<k;i++){
        for(int t=0;t<=h;t++){
            ans=min(ans,dp[T][t][i]+dp2[i]);
        }
    }
    cout<<(ans==E?-1LL:ans)<<endl;
    }
    
    return 0;
}



Measured memory_bytes: 29092
import java.util.Scanner;

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

            int max = Math.max(a, Math.max(b, c));
            System.out.println((a + b + c) - max == max ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 26996
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <string>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue() {
  int a;
  cin >> a;
  return a;
};
void inputVector(vector<int>* v) {
  //cin.tie(0);
  //ios::sync_with_stdio(false);
  int a;
  while (cin >> a) {
    if (a == -1)break;
    v->push_back(a);
  }
};

void inputVector(vector<int> * p, int a) {
  rep(i, a) {
    int input;
    cin >> input;
    p->push_back(input);
  }
}

void inputVector2(vector<vector<int>>& v, int r, int c) {
  int temp;
  for (size_t i = 0; i < r; i++)
  {
    for (size_t j = 0; j < c; j++)
    {
      scanf("%d", &temp);
      v[i][j] = temp;
    }
  }
}
void inputVector3(vector<int>* v0, vector<int>* v1) {
  int a;
  unsigned short count = 0b0;
  while (cin >> a) {
    if (a == -1)break;
    if(count)v0->push_back(a); else v1->push_back(a);
    count = count ^ 1;
  }
};

template <typename T>
void output(T a, int precision) {
  if (precision > 0) {
    cout << setprecision(precision) << a << "\n";
  }
  else {
    cout << a << "\n";
  }
}

int manySearch(vector<int>& v, int& many2, int& primary, int& secondary) {
  vector<int>::iterator prev = v.begin();
  vector<int>::iterator now;
  int prev_val = v[0];
  int many = 0;
  int manyTmp = 0;
  do {
    now = lower_bound(v.begin(), v.end(), prev_val+1);
    manyTmp = now - prev;
    if (manyTmp >= many) {
      many2 = many;
      secondary = primary;
      many = manyTmp;
      primary = prev_val;
    }
    else if (manyTmp >= many2) {
      many2 = manyTmp;
      secondary = prev_val;
    }
    if (now - v.begin() == v.size())break;
    prev = now;
    prev_val = *now;
  } while (1);
  return many;
}

int main(int argc, const char * argv[]) {
  int n;
  int many0 = 0;
  int many1 = 0;
  int many20 = 0;
  int many21 = 0;
  int primary0;
  int primary1;
  int secondary0;
  int secondary1;
  int out;
  vector<int> v0;
  vector<int> v1;

  scanf("%d", &n);
  inputVector3(&v0, &v1);
  std::sort(v0.begin(), v0.end());
  std::sort(v1.begin(), v1.end());
  many0 = manySearch(v0, many20, primary0, secondary0);
  many1 = manySearch(v1, many21, primary1, secondary1);

  if (primary0 != primary1)out = n - many0 - many1;
  else if (many20 + many1 >= many21 + many0)out = n - many20 - many1;
  else out = n - many21 - many0;

  printf("%d", out);
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

int		main(void)
{
	int N, M;
	cin >> N >> M;
	vector<pair<bool, int>> score(N, pair<bool, int>(false, 0));
	for (int i = 0; i < M; i++)
	{
		int P;
		string S;
		cin >> P >> S;
		P--;
		if (score[P].first == false && S == "WA")
			score[P].second++;
		if (S == "AC")
			score[P].first = true;
	}
	int ac = 0, sum = 0;
	for (auto p : score)
	{
		if (p.first)
		{
			ac++;
			sum += p.second;
		}
	}
	cout << ac << " " << sum << endl;
}



Measured memory_bytes: 1024
// 教訓:自分が定義した変数の意味を勘違いしないこと

#include<bits/stdc++.h>

using namespace std;

int A, B, C, D, E, F, water, sugar;
int x, y;

int main(){
	cin >> A >> B >> C >> D >> E >> F;

	for(int a = 0; a <= F; a += 100*A){
		for(int b = 0; a+b <= F; b += 100*B){
			for(int c = 0; a+b+c <= F; c += C){
				for(int d = 0; a+b+c+d <= F; d += D){
					water = a + b;
					sugar = c + d;
					if(E*water >= 100*sugar && x*sugar >= y*(water+sugar)){
						x = water+sugar;
						y = sugar;
					}
				}
			}
		}
	}
	cout << x << " " << y << endl;
}


Measured memory_bytes: 256
hitachi = input()

j = 0
tmp = 0

def check_hit(a,b):
    if a == b:
        return 1
    return 0


for i in hitachi:
    if j % 2 == 0:
        tmp += int(check_hit(i,"h"))
    else:
        tmp += int(check_hit(i,"i"))
    j+=1

if tmp == len(hitachi) and j%2==0 and tmp > 0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <cstdio>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

int n;
map<string,int> id;
vector<int> G[51];
int p[51];
int ng[51];
int ng2[51];
int dp[1<<21];
int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		id.clear();
		for(int i=0;i<n;i++){
			G[i].clear();
		}
		memset(ng,0,sizeof(ng));
		memset(ng2,0,sizeof(ng2));
		for(int i=0;i<n;i++){
			string a;
			int b,c;
			cin >> a >> b >> c;
			if(id.find(a)==id.end())id[a]=(int)id.size()-1;
			p[id[a]]=b;
			for(int i=0;i<c;i++){
				string d;
				cin >> d;
				if(id.find(d)==id.end())id[d]=(int)id.size()-1;
				G[id[a]].push_back(id[d]);
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<G[i].size();j++){
				if(G[i][j]<(n/2)){
					ng[i]+=(1<<G[i][j]);
				}else{
					ng2[i]+=1<<(G[i][j]-n/2);
				}
			}
		}
		int rest=n-n/2;
		memset(dp,-1,sizeof(dp));
		for(int i=0;i<(1<<(n/2));i++){
			int flag2=0,sum=0;
			bool ok=true;
			if(!(i&1))continue;
			for(int j=0;j<n/2;j++){
				if(i>>j & 1){
					if(i & ng[j])ok=false;
					flag2|=ng2[j];
					sum+=p[j];
				}
			}
			if(ok){
				dp[flag2]=max(dp[flag2],sum);
			}
		}
		for(int i=0;i<(1<<rest);i++){
			for(int j=0;j<rest;j++){
				if(i>>j & 1)dp[i]=max(dp[i-(1<<j)],dp[i]);
			}
		}
		int res=0;
		for(int i=0;i<(1<<rest);i++){
			int flag=0,sum=0;
			bool ok=true;
			for(int j=0;j<rest;j++){
				if(i>>j & 1){
					if(i & ng2[n/2+j])ok=false;
					flag|=ng2[n/2+j];
					sum+=p[n/2+j];
				}
			}
			if(ok && dp[(1<<rest)-1-i]>=0)res=max(res,sum+dp[(1<<rest)-1-i]);
		}
		printf("%d\n",res);
	}
	return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] m = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            m[i] = sc.nextInt();
            sum += m[i];
        }
        Arrays.sort(m);
        int rest = x - sum;
        int donatsu = rest / m[0];
        System.out.println(n + donatsu);

    }
}

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

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

  vector<int> x(n);
  vector<int> y(n);

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

  sort(x.begin(),x.end());
  int ans1 = x[n/2-1];
  int ans2 = x[n/2];

  for (int i = 0; i < n; i++)
  {
    if(y[i]<=ans1) cout << ans2 << endl;
    else cout << ans1 << endl;
  }  
}

Measured memory_bytes: 3712
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = "";
		try {
			s = br.readLine().trim();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		if(9 < s.length()) {
			System.out.println("NO");
			return;
		}
		
		final char[] WORD = {'A', 'K', 'I', 'H', 'A', 'B', 'A', 'R', 'A'};
		char[] str = s.toCharArray();
		char[] r = new char[WORD.length];
		
		for (int i = 0, j = 0; i < WORD.length; i++) {
			if (str.length <= j) r[i] = 'A';
			else if (WORD[i] == str[j]) r[i] = str[j];
			else {
				r[i] = 'A';
				if (i < WORD.length - 1)r[++i] = str[j];
			}
			j++;
		}
		System.out.println((Arrays.equals(r, WORD)) ? "YES":"NO");		
	}
}

Measured memory_bytes: 23380
import heapq
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    G[u-1].add(v-1)
#print(G)
S,T=map(int,input().split())
S-=1;T-=1
#dp[i][j]:i番目の頂点をmod 3=jで行けるかどうか
dist=[[10**10 for i in range(3)] for i in range(N)]
dist[S][0]=0
q=[]
heapq.heappush(q,(dist[S][0],S,0))
while(len(q)>0):
    d,r,j=heapq.heappop(q)
    if dist[r][j]<d:
        continue
    for p in G[r]:
        if dist[p][(j+1)%3]>dist[r][j]+1:
            dist[p][(j+1)%3]=dist[r][j]+1
            heapq.heappush(q,(dist[p][(j+1)%3],p,(j+1)%3))
#print(dist)
if dist[T][0]==10**10:
    print(-1)
else:
    print(dist[T][0]//3)

Measured memory_bytes: 97568
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define repm(i,a,b) for(ll i=(ll)(a);i>(ll)(b);i--)
#define all(v) v.begin(), v.end()
#define rall(x) (x).rbegin(),(x).rend()
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vc vector<char>
#define vvc vector<vc>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<long long>;
using vvll = vector<vll>;
using vb =vector<bool>;
using vvb=vector<vb>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
//snippets:tmp,cl,cvl,cs,co,coy,con,cov,setp

vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}

int main(){
    ll n;
    cin >> n;
    vll a(n);
    vll d(1000001,0);
    rep(i, n){
        cin >> a[i];
        d[a[i]]+=1;
    }
    ll count=0;
    rep(i,n){
        vll ret;
        ret=divisor(a[i]);
        bool flag=false;
        rep(j,ret.size()){
            if(d[ret[j]]!=0&&(j!=(ll)(ret.size()-1)||d[ret[j]]>1)){
                flag=true;
                break;
            }
        }
        if(flag) continue;
        count++;
    }
    cout << count << endl;
}

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

using namespace std;
typedef long long LL; 

#define MAXN 100001
#define MOD 1000000007

int main(int argc, char** argv) {
#ifdef OJ	
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false);
    
    int N,K;
    cin >> N >> K;

    int ans = 0;
    for (int i = 0; i < N-1; i += K-1)
        ans++;

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

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

using namespace std;

int main() {
    int32_t n, point_taro = 0, point_hanako = 0;
    string card_taro, card_hanako;

    cin >> n;

    for (int32_t i = 0; i < n; i++) {
        cin >> card_taro >> card_hanako;

        if (card_taro < card_hanako) {
            point_hanako += 3;
        } else if (card_taro > card_hanako) {
            point_taro += 3;
        } else {
            point_taro++;
            point_hanako++;
        }
    }

    cout << point_taro << " " << point_hanako << endl;

    return 0;
}

Measured memory_bytes: 3188
import sys
from collections import namedtuple, deque

Process = namedtuple('Process', ('name', 'time'))

queue = deque()

n, q = map(int, sys.stdin.readline().split())
for _ in range(n):
    name, time = sys.stdin.readline().split()
    queue.append(Process(name, int(time)))


def ok():
    pass


current_time = 0

while len(queue):
    process = queue.popleft()
    if process.time <= q:
        current_time += process.time
        print(f'{process.name} {current_time}')
    else:
        current_time += q
        queue.append(Process(process.name, process.time - q))



Measured memory_bytes: 12960
N = int(input())
XL = []
for n in range(N):
    XL.append([int(x) for x in input().split()])
XL = sorted(XL, key=lambda x:x[0]+x[1])
m = -float("inf")
ans = 0
for n in range(N):
    if XL[n][0]-XL[n][1] >= m:
        ans += 1
        m = XL[n][0]+XL[n][1]
print(ans)



Measured memory_bytes: 26788
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

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

	int a;
	if (n % 2 == 0)
	{
		a = n;
	}
	else
	{
		a = 2 * n;
	}

	cout << a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pl = pair<ll,ll>;
using pi = pair<int,int>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
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; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;
int dp[110][4][2];

signed main(){
	//cout << fixed << setprecision(10);
	string s; cin >> s;
    int K; cin >> K;
    int n = s.size();
    dp[0][0][0] = 1;
    rep(i,0,n)rep(j,0,4)rep(k,0,2){
        int x = s[i] - '0';//now
        rep(d,0,10){
            int ni = i+1 , nj = j , nk = k;
            if(d != 0) nj++;
            if(K < nj) continue;
            if(nk == 0){
                if(d > x) continue;
                if(d < x) nk = 1;
            }
            dp[ni][nj][nk] += dp[i][j][k];
        }
    }
    cout << dp[n][K][0] + dp[n][K][1] << endl;
}



Measured memory_bytes: 3632
#define s(a,b) (t=a,a=b,b=t)
f(int*a){*a=(*a&15)<<4|*a>>4;}char p[9],m;q,a,b,c,t,r;main(n){while(scanf("%d",&n),n){r=1,a=22,b=37,c=52;while(n--){scanf("%s",p);m=*p-76;if(m%6==0){s(b,c);q=m>0?f(&c):f(&b);}else if(1<m&&m<8){s(a,b);q=m^7?f(&b):f(&a);}else{s(a,c);q=m>0?f(&c):f(&a);}r+=a>>4;}printf("%d\n",r);}}

Measured memory_bytes: 0
n=1000000
pr = [1] * n
pr[0],pr[1]=0,0
for i in xrange(2, int(n**0.5)+1):
    if pr[i] == 1:
        for j in range(i ** 2, n , i):
                pr[j] =0
for k in xrange(3, n):
    pr[k] += pr[k-1]
while True:
    try:
        m = int(raw_input())
        print pr[m]
    except:
        break

Measured memory_bytes: 36292
x1, y1, x2, y2 = map(int, input().split())
x3 = x2 - (y2-y1)
y3 = y2 + (x2-x1)
x4 = x1 - (y2-y1)
y4 = y1 + (x2-x1)

print(x3, y3, x4, y4, sep=' ')


Measured memory_bytes: 2940
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
ans = 0
for i in range(n):
	ans += b[a[i]-1]
	if i != 0 and a[i] == a[i-1] + 1:
		ans += c[a[i]-2]
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp5
{
    class Program
    {

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long[] A = new long[N + 1];
            long[] B = new long[N];
            String S = Console.ReadLine();
            String[] L = S.Split(' ');

            for(int i=0; i<N+1; i++)
            {
                A[i] = long.Parse(L[i]);
            }

            S = Console.ReadLine();
            L = S.Split(' ');
            long ans = 0;

            for (int i = 0; i < N; i++)
            {
                B[i] = long.Parse(L[i]);
            }

            for (int i=0; i<N; i++)
            {
                if(A[i] <= B[i])
                {
                    ans = ans + A[i];
                    B[i] = B[i] - A[i];
                    A[i] = 0;
                    if (A[i + 1] <= B[i])
                    {
                        ans = ans + A[i + 1];
                        B[i] = B[i] - A[i + 1];
                        A[i + 1] = 0;
                    }
                    else
                    {
                        ans = ans + B[i];
                        A[i + 1] = A[i + 1] - B[i];
                        B[i] = 0;
                    }
                }
                else
                {
                    ans = ans + B[i];
                    B[i] = 0;
                    A[i] = A[i] - B[i];
                }

            }
            Console.WriteLine(ans);

        }
    }
}

Measured memory_bytes: 38092
#include <iostream>
#include <vector>
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (n); i++)
using namespace std;

int main(){
  int n;
  cin >> n;
  int ans = 1000 - (n % 1000);
  if (ans == 1000) ans = 0;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3668
input = gets

i_1 = input.to_s[0]
i_2 = input.to_s[1]
i_3 = input.to_s[2]
i_4 = input.to_s[3]

output = "Good"
output = "Bad" if i_1 == i_2
output = "Bad" if i_2 == i_3
output = "Bad" if i_3 == i_4

puts output


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

int main() {
	vector<int> v(100, 0); int temp;
	while (cin >> temp) v[temp - 1]++;
	temp = *max_element(v.begin(), v.end());
	for (int i = 0; i < 100; i++) if (v[i] == temp) cout << i + 1 << endl;
	return 0;
}


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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

template<class T,class U>bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U>bool chmin(T &a, const U &b){if(b<a){a=b;return 1;}return 0;}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int kk;
    cin>>kk;

    rep1(i,1,kk+1){
        rep1(j,1,kk+1){
            rep1(k,1,kk+1){
                ans += gcd(gcd(i,j),k);
            }
        }
    }

    cout<<ans<<endl;
    //cout <<fixed<<setprecision(16)<< << endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;

    return 0;
}


Measured memory_bytes: 3592
X = int(input())

item_list = [100, 101, 102, 103, 104, 105]
# dp[i]: i円支払う払うことができるなら1
dp = [0 for _ in range(100001)]
dp[0] = 1

for item in item_list:
    for i in range(100001):
        if dp[i] == 1 and i + item <= 100000:
            dp[i+item] = 1

if dp[X] == 1:
    print(1)
else:
    print(0)


Measured memory_bytes: 3912
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
#include <array>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define INF I64_MAX
#define MOD 1000000007


void solve(void)
{
  vector<int> vec(3,0);
  for (int i = 0; i < 3; i++)
  {
    cin>>vec[i];
  }

  sort(vec.begin(),vec.end());

  if((vec[0] == 5)&&(vec[1]==5)&&(vec[2]==7))
  {
    cout<<"YES"<<endl;
  }
  else cout<<"NO"<<endl;
  
 
  
  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  // std::cout << std::fixed;
  // std::cout << std::setprecision(8);

  solve();

 
  return 0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
S=[A[i]-B[i] for i in range(N)]
S.sort()
if S[0]>=0:
  print(0)
  exit()
if S[-1]<0:
  print(-1)
  exit()
  
x=0
y=N-1
while y-x>1:
  if S[(y+x)//2]<0:
    x=(y+x)//2
  else:
    y=(y+x)//2

minus=-sum(S[:y])

z=N-1
s=S[N-1]
while z>y and s<minus:
  z-=1
  s+=S[z]
  
if s<minus:
  print(-1)
else:
  print(N-(z-y))

Measured memory_bytes: 18708
#include <stdio.h>
int abs(int n){
		if(n<0){
		return -1*n;}else
		return n;}
int main(void)
{int N,A,M,B,C,x,i,a,b,c,l,m,tmp;
	scanf("%d%d%d",&A,&B,&C);
if((C>=A)&&(C<=B)){
	printf("Yes");}
	else
	printf("No");


	return 0;
}


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

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; }

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;


int main(){
    int n;
    cin >> n;
    ll ans = 1;
    rep(i, 1, n+1){
        ans *= i;
        ans%=mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using ll = long long;
using P = pair<int, int>;
using MATRIX = vector< vector<ll> >;
template <class T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <class T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}

int main() {
  int N;
  int a[200000], b[200000];
  cin >> N;
  rep(i, N) {
    cin >> a[i] >> b[i];
  }
  sort(a, a + N);
  sort(b, b + N);
  if(N % 2 != 0) {
    cout << b[N / 2] - a[N / 2] + 1 << endl;
  } else {
    int bef = a[N / 2] + a[N / 2 - 1];
    int aft = b[N / 2] + b[N / 2 - 1];
    cout << aft - bef + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 5100
#!/usr/bin/env ruby

s = gets.chomp
l = s[0, 2].to_i
r = s[2, 2].to_i
if 1 <= l && l <= 12 then
  if 1 <= r && r <= 12 then
    puts  "AMBIGUOUS"
  else
      puts "MMYY"
  end
else
  if 1 <= r && r <= 12 then
    puts "YYMM"
  else
    puts "NA"
  end
end



Measured memory_bytes: 1788
def kitaiti(number):
 return (1 + number)/2
def ruisekiwa(mylist):
    s = [0]
    t = 0
    for i in range(len(mylist)):
        t += mylist[i]
        s.append(t)
    return s
def wa(mylist,K):
    a = []
    i = 0
    while K + i < len(mylist):
        a.append(mylist[K + i]-mylist[i])
        i += 1
    return max(a)
N,K = (int(i) for i in input().split())
kitaiti = [kitaiti(int(x)) for x in input().split()]
print(wa(ruisekiwa(kitaiti),K))

Measured memory_bytes: 23300
import sys

n, u, v = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [-1] * (n+1)
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
    if t < a:
        ans = max(ans, a - 1)

print(ans)


Measured memory_bytes: 32288
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <queue>
#include <list>
#include <stack>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;

int main(){
  string S;
  cin >> S;
  int ret = 0;
  char c = '-';
  rep(i,S.length()){
    if(S[i] == c) continue;
    ret++;
    c = S[i];
  }
  cout << ret-1 << endl;
  
  return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define F first
#define S second
#define mp make_pair
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define pq priority_queue
#define M map
#define UM unordered_map
#define graph unordered_map<int,vector<int>>
#define graphw unordered_map<int,vector<pair<int,int>>>
#define V vector
#define mod 1000000007
#define inf 3000000000000000007ll
#define P pair
#define Fast ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) signed(a.size())
#define FIXED cout << fixed << setprecision(12)
#define L list
#define D deque
#define ld long double
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define deb(x) cout<<#x<<" "<<x<<endl;
using namespace std;
// pair operation
template<class T, class U>istream& operator>>(istream& in, pair<T, U> &rhs) {in >> rhs.first; in >> rhs.second; return in;}
template<class T, class U>ostream& operator<<(ostream& out, const pair<T, U> &rhs) {out << rhs.first; out << " "; out << rhs.second; return out;}
template<class T, class U>pair<T, U> operator+(pair<T, U> &a, pair<T, U> &b) {return pair<T, U>(a.first + b.first, a.second + b.second);}
template<class T, class U>pair<T, U> operator-(pair<T, U> &a, pair<T, U> &b) {return pair<T, U>(a.first - b.first, a.second - b.second);}
// Linear STL
// VECTOR
template<class T>istream& operator>>(istream& in, vector<T> &a) {for (auto &i : a)cin >> i; return in;}
template<class T>ostream& operator<<(ostream& out, const vector<T> &a) {for (auto &i : a)cout << i << " "; return out;}
// SET
template<class T>ostream& operator<<(ostream& out, const set<T> &a) {for (auto &i : a)cout << i << " "; return out;}
template<class T>ostream& operator<<(ostream& out, const unordered_set<T> &a) {for (auto &i : a)cout << i << " "; return out;}
template<class T>ostream& operator<<(ostream& out, const multiset<T> &a) {for (auto &i : a)cout << i << " "; return out;}
// MAP
template<class T, class U>ostream& operator<<(ostream& out, const map<T, U> &a) {for (auto &i : a)cout << "(" << i.first << ", " << i.second << "(\n"; return out;}
template<class T, class U>ostream& operator<<(ostream& out, const unordered_map<T, U> &a) {for (auto &i : a)cout << "(" << i.first << ", " << i.second << "(\n"; return out;}


void judge() {
#ifndef ONLINE_JUDGE
	FILE_READ_IN
	FILE_READ_OUT
#endif
}



int main() {
	Fast;
	int t = 1;
	judge();
	// cin >> t;
	while (t--) {
		ld r;
		cin >> r;

		ld ans = 6.28 * r;
		cout << ans << endl;
	}
}


Measured memory_bytes: 3804
#![allow(unused_imports)]
use std::io;
use std::cmp::*;
use std::collections::*;
#[allow(dead_code)]
const M: i64 = 1e9 as i64 + 7;

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}
#[allow(dead_code)]
fn read<T>() -> T where T: std::str::FromStr, T::Err : std::fmt::Debug {
    read_line().trim().parse().unwrap()
}
#[allow(dead_code)]
fn readv<T>() -> Vec<T> where T: std::str::FromStr, T::Err : std::fmt::Debug {
    read_line().split(' ').map(|a| a.trim().parse().unwrap()).collect()
}

fn main() {
    let _ = read::<usize>();
    let aa = readv::<usize>();
    let bb = readv::<usize>();
    let x = aa.iter().fold(0, |acc, &a| acc ^ a);
    let (mut aa, bb): (Vec<_>, Vec<_>) = aa.iter().zip(bb.iter()).filter(|&(&a, &b)| a != b).unzip();
    let n = aa.len();
    aa.push(x);
    let mut nums: HashMap<_, i32> = aa.iter()
        .fold(HashMap::new(), |mut acc, &a| { *acc.entry(a).or_insert(0) += 1; acc });
    for &b in &bb {
        *nums.entry(b).or_insert(0) -= 1;
        if nums[&b] < 0 {
            println!("{}", -1);
            return;
        }
    }

    let mp = aa.iter().collect::<BTreeSet<_>>().into_iter().enumerate()
        .map(|(a, b)| (b, a)).collect::<HashMap<_, _>>();
    let a2: Vec<_> = aa.iter().map(|a| mp[a]).collect();
    let b2: Vec<_> = bb.iter().map(|b| mp[b]).collect();
    let mut dests = b2.iter().enumerate()
        .fold(HashMap::new(), |mut acc, (a, b)| { (acc.entry(b).or_insert(Vec::new())).push(a); acc });
    let mut q: VecDeque<_> = std::iter::once(n).collect();
    let mut rems: HashSet<_> = (0..n + 1).collect();
    let mut ans = n;
    #[cfg(local)] println!("{}: {:?}", "(mp, dests)", (mp, &dests));
    #[cfg(local)] println!("{}: {:?}", "(a2, b2)", (&a2, &b2));
    while !rems.is_empty() {
        while let Some(s_idx) = q.pop_front() {
            if !rems.remove(&s_idx) {
                continue;
            }
            let s_num = a2[s_idx];
            if let Some(destv) = dests.remove(&s_num) {
                for dest in destv {
                    q.push_back(dest);
                }
            }
        }
        if let Some(&rem) = rems.iter().next() {
            q.push_back(rem);
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 32572
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N; cin >> N;
    string S; cin >> S;
    int front=0,st=0;
    for(int i=0;i<N;i++){
        if(S[i]=='('){
            st++;
        }else{
            if(st==0){
                front++;
            }else{
                st--;
            }
        }
    }
    string out = "";
    for(int i=0;i<front;i++){
        out += '(';
    }
    out += S;
    for(int i=0;i<st;i++){
        out += ')';
    }
    cout << out << endl;
    return 0;
}


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

int main() {
    int n, m;
    cin>>n>>m;
    
    long long w[n];
    long long val[n];
    
    long long sumVal = n * 1000;
    
    for(int i = 0;i<n;i++) {
        cin>>w[i]>>val[i]; 
    }
    
    long long dp[n+1][sumVal+1];
    
    for(int i = 0;i<n;i++) {
       for(int j =0;j<=sumVal;j++) {
           dp[i][j] = INT_MAX;
       }
    }
    
    
    
    dp[0][0] = 0;
    dp[0][val[0]] = w[0];
    
    for(int i=1;i<n;i++) {
        for(int v=0;v<=sumVal;v++) {
            dp[i][v] = dp[i-1][v];
            if(v - val[i] >= 0) {
                dp[i][v] = min(dp[i][v], w[i] + dp[i-1][v - val[i]]);
            }
        }
    }

    long long ans = 0;
    for(int i = 0;i<=sumVal;i++) {
        if(dp[n-1][i] <= m) {
            ans = i;
        }
    }
   
    cout<<ans<<endl;
}


Measured memory_bytes: 79104
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define elif else if
using namespace std;
int a,b[110000],c,d=0,e=0;
string s;
signed main()
{
	cin>>a;
	rep(i,a){
		cin>>c;
		b[c]++;
	}
	rep(i,100000){
		d+=b[i];
		if(d==a/2){
			e++;
		}
	}
	cout<<e;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int main(){
	int d,t,s;
	cin>>d>>t>>s;
	d=(d+s-1)/s;
	puts(d<=t?"Yes":"No"); 
	return 0;
}

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

#define pb push_back
#define mp make_pair
#define loop1(x,s,e) for(int x=s;x!=e;x+=1-2*(s>e))
#define input_matrix(a,m,n) for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>a[i][j];
#define input_array(a,n) for(int i=0;i<n;i++)cin>>a[i];
#define all(x) x.begin(),x.end()
#define newl "\n"
#define tests(t) int t; cin>>t; while(t--)
#define speed ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
vector<int> graph[200005];
void dfs(int s,int p,vector<int> &v)
{
    
    for(auto i:graph[s])
    {
        if(i==p)continue;
        v[i]+=v[s];
        dfs(i,s,v);
    }
}
int main()
 {
	int n,q;
	cin>>n>>q;
	for(int i=0;i<n-1;i++)
	{
	    int a,b;
	    cin>>a>>b;
	    a--,b--;
	    graph[a].pb(b);
	    graph[b].pb(a);
	}
	vector<int>v(n,0);
	for(int i=0;i<q;i++)
	{
	    int p,x;
	    cin>>p>>x;
	    p--;
	    v[p]+=x;
	}
	dfs(0,-1,v);
	
	for(int i=0;i<n;i++) cout<<v[i]<<" ";
	return 0;
}

Measured memory_bytes: 26624
/*input
314159265 35897932 384626433
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}

//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}

int main()
{
	IOS;
	ll k,a,b;
	cin>>k>>a>>b;
	b-=a;
	ll ans=1;
	if(b<=2) cout<<k+1<<'\n';
	else{
		ll tmp=min(k,a-1);
		ans+=tmp;
		k-=tmp;

		if(k%2) ans++,k--;

		ans+=k/2*(b);
		cout<<ans<<'\n';
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,c,i,j,a[4][14]={0};
  char b;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf(" %c %d",&b,&c);
    if(b=='S'){
      a[0][c]=1;
    }if(b=='H'){
      a[1][c]=1;
    }if(b=='C'){
      a[2][c]=1;
    }if(b=='D'){
      a[3][c]=1;
    }
  }
  for(i=0;i<4;i++){
    for(j=1;j<=13;j++){
      if(a[i][j]==0){
    if(i==0){
      printf("S %d\n",j);
    }if(i==1){
      printf("H %d\n",j);
    }if(i==2){
      printf("C %d\n",j);
    }if(i==3){
      printf("D %d\n",j);
    }
      }
    }
  }
  return(0);
}

Measured memory_bytes: 2676
N = int(input())
S = input()
dp = [0 for i in range(N)]
b = 0
w = 0
flag1 = True
flag2 = True
for i in range(N):
    if flag1 and S[i] == '.':
        pass
    elif flag1:
        flag1 = False
        b += 1
    elif S[i] == '.':
        dp[i] = b
    else:
        b += 1

for i in reversed(range(N)):
    if flag2 and S[i] == '#':
        pass
    elif flag2:
        flag2 = False
        w += 1
    elif S[i] == '#':
        dp[i] = w
    else:
        w += 1
ans = float('inf')
for i in range(N-1):
    if (S[i] == '.' and S[i+1] == '#') or (S[i] == '#' and S[i+1] == '.'):
        ans = min(ans,dp[i]+dp[i+1])

if ans == float('inf'):
    print(0)
else:
    print(min(b,w,ans))


Measured memory_bytes: 11400