akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
from itertools import accumulate
n = int(input())
m = (n*(n+1)//2+1)//2
U = 2**20
A = tuple(map(int, input().split()))
def test(x):
  L = [0] + list(accumulate((-1)**(a<x) for a in A))
  B = [0]*(U+1)
  def add(i):
    while i<=U:
      B[i] += 1
      i += i & -i
  def acc(i):
    res = 0
    while i:
      res += B[i]
      i -= i & -i
    return res
  cnt = 0
  for l in L:
    cnt += acc(l+n+5)
    add(l+n+5)
  return cnt >= m
ok = 0
ng = 10**9+1
while ng - ok > 1:
  mid = (ng+ok)//2
  if test(mid):
    ok = mid
  else:
    ng = mid
print(ok)

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

int main(){
  int l;
  cin >> l;
  vector<int> a(l * 2);
  for(int i = 0; i < l * 2; i++) cin >> a[i];
  sort(a.begin(), a.end());
  int ans = 0;
  for(int i = 0; i < l * 2; i += 2){
    ans += min(a[i], a[i + 1]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3568
#include <iostream>

int main() {
  int N;
  int A;
  int B;

  std::cin >> N >> A >> B;

  int planA = 0;

  planA = A * N;
  if (planA <= B) {
    std::cout << planA << std::endl;
  } else {
    std::cout << B << std::endl;
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
	
		Scanner stdIn = new Scanner(System.in);
		
		byte x = stdIn.nextByte();
		
		if (x == 3 || x == 5 || x == 7) {
			System.out.println("YES");
			return;
		}
		
		System.out.println("NO");
	
	}
}

Measured memory_bytes: 21972
# -*- coding: utf-8 -*-

N, K = map(int, input().split())

#Kの偶奇で場合分け
#Kが偶数なら(x,y,z) x, y, z = K/2, 0 (mod K) でKが奇数なら(x,y,z) x, y, z = 0 (mod K)

output = 0

output += int(N / K)**3

if K%2 == 0:
    if N%K >= K / 2:
        output += (int(N / K) + 1)**3
    else:
        output += int(N / K)**3

print (output)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,X,M=MI()
    use=[0]*M
    loopF=0
    loopN=0
    loopS=0
    loopL=[]
    ans=0
    cnt=0
    
    now=X
    
    if N<=4*M:
        for i in range(N):
            ans+=now
            now=(now**2)%M
        print(ans)
        exit()
            
    
    for i in range(M*3):
        use[now]+=1
        if use[now]==2:
            loopF=1
        if use[now]==3:
            cnt=i
            break
        
        ans+=now
        if loopF:
            loopL.append(now)
            loopN+=1
            loopS+=now
        
        now=(now**2)%M
        
    N2=N-cnt
    loop=N2//loopN
    rem=N2%loopN
    
    ans+=loop*loopS
    ans+=sum(loopL[:rem])
    
    print(ans)
    

main()


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  ll N, M;
  cin >> N >> M;
  string S;
  cin >> S;

  if(N == 1){
    cout << 1 << endl;
  }else if(M > 1){

  vector<ll> can_go;
  can_go.push_back(0);
  for(int i = 1; i <= N; i++){
    if(S[N-i] == '0'){
      can_go.push_back(i);
    }
  }

  ll cur = 0;
  ll cur_ind = 0;
  bool dame = false;
  vector<ll> tmp_ans;
  tmp_ans.push_back(0);
  while(cur < N){

    ll left = cur_ind;
    ll right = can_go.size();

    while(right - left > 1){
      ll mid = left + (right - left) / 2;

      if(can_go[mid] > cur + M){
        right = mid;
      }else{
        left = mid;
      }
    }

    if(left == cur_ind){
      dame = true;
      break;
    }

    cur = can_go[left];
    cur_ind = left;
    tmp_ans.push_back(cur);

  }
  vector<ll> ans(tmp_ans.size()-1);
  for(int i = 0; i < ans.size(); i++){
    ans[ans.size()-i-1] = tmp_ans[i+1] - tmp_ans[i]; 
  }

  if(dame){
    cout << -1 << endl;
  }else{
    for(int i = 0; i < ans.size(); i++){
      cout << ans[i] << " ";
    }
    cout << endl;
  }
  }else{

    bool ok = true;
    for(int i = 0; i < S.length()+1; i++){
      if(S[i] == '1'){
        ok = false;
      }
    }

    if(ok){
      for(int i = 0; i < N; i++){
        cout << 1 << " ";
      }
      cout << endl;
    }else{
      cout << -1 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 1528
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
typedef pair<int, int> P;
const int mod = 1e9 + 7, inf = 1e16;

int modpow(int x, int n) {
	if (n == 0) return 1;
	if (n % 2) return x * modpow(x * x % mod, n / 2) % mod;
	return  modpow(x * x % mod, n / 2) % mod;
}

int fact(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= (i + 1);
		ans %= mod;
	}
	return ans;
}

int comb(int n, int r) {
	if (n < r) swap(n, r);
	if (n - r < r) r = n - r;
	return fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) % mod;
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int n,k;
int a[114514];
int ans=inf;
signed main() {
	cin>>n>>k;
	rep(i,n) {
		cin>>a[i];
	}
	rep(i,n-k+1) {
		if(a[i+k-1]<=0) {
			ans=min(ans,-a[i]);
		}
		else if(0<=a[i]) {
			ans=min(ans,a[i+k-1]);
		}
		else {
			ans=min(ans,min(2*a[i+k-1]-a[i],a[i+k-1]-2*a[i]));
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()) {
			double a = sc.nextDouble();
			double b = sc.nextDouble();
			double c = sc.nextDouble();
			double d = sc.nextDouble();
			double e = sc.nextDouble();
			double f = sc.nextDouble();
			
			double x = (e*c - b*f)/(a*e - d*b);
			double y = (d*c - a*f)/(b*d - a*e);
			
			if(x==0.0) {
				x=0;
			}
			if(y==0.0) {
				y=0;
			}
			System.out.printf("%.3f %.3f\n", x, y);
		}
	}
}



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

int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);

  int a, b, c;
  cin >> a >> b >> c;
  if (a + b >= c)
    cout << "Yes\n";
  else
    cout << "No\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(),(a).end()
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,n) for(ll (i)=(n)-1;(i)>=0;i--)
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;
int main(){
    int a,b;
    cin>>a>>b;
    cout<<6-(a+b)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for( int i = 0 ; i < n ; i++ )
 
int main(){
  string S ;
  int A , B ;
  cin >> A >> B ;
  cin >> S ;
  if( S[B-1] == 'A' ) S[B-1] = 'a' ;
  if( S[B-1] == 'B' ) S[B-1] = 'b' ;
  if( S[B-1] == 'C' ) S[B-1] = 'c' ;
  rep(i,A) cout << S[i];
}

Measured memory_bytes: 256
N = int(input())
L = []
for _ in range(N):
    n = int(input())
    t = [list(map(int, input().split())) for _ in range(n)]
    L.append(t)

ans = 0
for i in range(1 << N):
    for p in range(N):
        f = ((i >> p) & 1 == 1)
        if not all([not f or f and (i >> (t[0]-1)) & 1 == t[1] for t in L[p]]):
            break
    else:
        ans = max(ans, str(bin(i)).count('1'))
print(ans)


Measured memory_bytes: 48092
#include<stdio.h>

int main()

{
	int a;
	int b;
	int c;
	int ab;
	int bc;
	int ac;
	int list[100000];
	int cek=100000;
	
	scanf("%d %d %d",&a,&b,&c);
	
	ab= a+b;
	bc= b+c;
	ac= a+c;
	
	list[0]=ab;
	list[1]=bc;
	list[2]=ac;
	
	for(int i=0;i<3;i++)
	{
		if(list[i]<cek)
		{
			cek=list[i];
		}
	}
	
	
	printf("%d",cek);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        

fast();
//ll t;cin>>t;while(t--)
{
    ll n;
    cin>>n;
    n--;
    ll ans=(1ll*n*(1ll*n+1))/2;
    cout<<ans<<endl;
}
return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int x,y;
    while(true){
        cin >> x;
        cin >> y;
        if(x == 0 && y == 0){
            break;
        }
        if(x<y){
            cout << x << " " << y << endl;
        }
        else{
            cout << y << " " << x << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3108
r, c = map(int, input().split())

arr = [input().split() for l in range(r)]

lastans = 0
for a in arr:
    ans = 0
    answord = ""
    for num in a:
        answord += num
        answord += " "
        ans += int(num)
    lastans += ans
    answord += str(ans)
    print(answord)

lastansword = ""
for i in range(c):
    ans = 0
    for j in range(r):
        ans += int(arr[j][i])
    lastansword += str(ans)
    lastansword += " "
lastansword += str(lastans)
print(lastansword)



Measured memory_bytes: 6192
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <string>
#include<algorithm>
#include<map>
#include <vector>
#include <cassert>
#include<cmath>
using namespace std;



int main() {
	long X;
	long res = 0;
	long hoji = 0;
	cin >> X;
	while (X >= 500) {
		X -= 500;
		res+=1000;
	}
	while (X >= 5) {
		X -= 5;
		res += 5;
	}

	cout << res << endl;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(final String[] args) {
    @SuppressWarnings("resource")
    final Scanner sc = new Scanner(System.in);
    final int n = sc.nextInt();
    final int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }

    final int cnt = selectionSort(arr);
    trace(arr);
    System.out.println(cnt);
  }

  static int selectionSort(final int[] arr) {
    int cnt = 0, minIdx;
    for (int i = 0; i < arr.length - 1; i++) {
      minIdx = i;
      // 未ソートの部分から最小の要素の位置を特定して
      for (int j = i; j < arr.length; j++) {
        if (arr[j] < arr[minIdx]) minIdx = j;
      }
      // 交換する
      if(i != minIdx) {
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
        cnt++;
      }
    }
    return cnt;
  }

  static void trace(final int[] arr) {
    final StringBuilder sb = new StringBuilder();
    for (final int num : arr) {
      sb.append(num).append(' ');
    }
    System.out.println(sb.toString().trim());
  }
}



Measured memory_bytes: 26516
#include <iostream>
#include <map>
#include <vector>

using namespace std;

void getDays(int month, int day)
{
    int dayNum[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int fst=0; // 1/1 ?????? (month-1)??????????????\?????§?????\??°
    for(int i=0; i<month-1; i++)
        fst += dayNum[i];
    fst += day; // month???1??\?????§?????\??°
    
    switch(fst % 7) {
        case 0:
            cout << "Wednesday" << endl;
            break;
        case 1:
            cout << "Thursday" << endl;
            break;
        case 2:
            cout << "Friday" << endl;
            break;
        case 3:
            cout << "Saturday" << endl;
            break;
        case 4:
            cout << "Sunday" << endl;
            break;
        case 5:
            cout << "Monday" << endl;
            break;
        case 6:
            cout << "Tuesday" << endl;
            break;
        default:
            break;
    }

}

int main(void)
{
    ios::sync_with_stdio(false);
    int month, day;
    while(1) {
        cin >> month >> day;
        if(month == 0) break;
        getDays(month, day);
    }

    return 0;
}

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

main(){
    ll n,i,count_n=0,ans=0;
    cin >> n;
    vector<ll> d(n);
    for(i=0;i<n;i++) cin >> d[i];

    sort(d.begin(),d.end());
    for(i=d[n/2-1]+1;i<=d[n/2];i++){
        ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
a,b,c=map(int, input().split())
#1ban
ans=abs(b-a)+abs(c-b)
ans2=abs(c-a)+abs(b-c)
if(ans2<ans):
    ans=ans2
#2ban
ans2=abs(a-b)+abs(c-a)
if(ans2<ans):
    ans=ans2
ans2=abs(c-b)+abs(a-c)
if(ans2<ans):
    ans=ans2
#3ban
ans2=abs(a-c)+abs(b-a)
if(ans2<ans):
    ans=ans2
ans2=abs(b-c)+abs(a-b)
if(ans2<ans):
    ans=ans2
print(ans)

Measured memory_bytes: 9184
#include <stdio.h>
#include <string.h>

int main() {
	int A, B;
	scanf("%d%d", &A, &B);
	if (A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0){
		printf("Possible");
	}
	else{
		printf("Impossible");
	}
		return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	private Scanner sc;
	
	public static void main(String[] args) {
		new Main();
	}
	
	public Main() {
		sc = new Scanner(System.in);
		
		int[] prime = new int[50000];
		for (int i = 0; i < prime.length; i++) {
			prime[i] = 1;
		}
		
		for (int i = 2; i < (prime.length / 2); i++) {
			for (int j = 2; (i * j) < prime.length; j++) {
				prime[i * j] = 0;
			}
		}
		prime[0] = 0;
		prime[1] = 0;
		
		int num = Integer.parseInt(sc.nextLine());
		while (num != 0) {
			int sum = 0;
			for (int i = 2; i <= (num / 2); i++) {
				if ((prime[i] == 1) && (prime[num - i] == 1)) sum++;
			}
			System.out.println(sum);
			
			num = Integer.parseInt(sc.nextLine());
		}
	}
}

Measured memory_bytes: 61228
#include <iostream>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e6+5;
int que[N],head=1,tail,n,k,cmp;
void Output(int n){ rep(i,1,n) putchar(i&1?'B':'A'); } 
int main(){
	scanf("%d%d",&n,&k); tail=n;
	rep(i,1,n){
		char c=getchar();
		while(c!='A'&&c!='B') c=getchar();
		que[i]=c=='A';
	}
	rep(i,1,min(k,2*n)){
		if(cmp^que[head]) que[head]^=1;
		else que[++tail]=cmp,cmp^=1,head++;
	}
	if(k<=2*n){
		rep(i,head,tail) putchar((que[i]^cmp)&1?'A':'B');
		return 0;
	}
	if(n&1){
		putchar((que[head]^cmp^((k-2*n)&1))&1?'A':'B');
		Output(n-1);
	}else Output(n);
	return 0;
}

Measured memory_bytes: 2432
def main():
    H,W = list(map(int, input().split()))
    S = [input() for _ in range(H)]

    count_h = [[0] * W for _ in range(H)]
    count_w = [[0] * W for _ in range(H)]

    tmp_cnt_h = [0] * W
    for i in range(H):
        w_cnt = 0
        for j,c in enumerate(S[i]):
            if c == '.':
                tmp_cnt_h[j] += 1
                w_cnt += 1
            else:
                count_w[i][j-w_cnt:j] = [w_cnt]*w_cnt
                w_cnt = 0

                h_cnt = tmp_cnt_h[j]
                for x in range(i-h_cnt,i):
                    count_h[x][j] = h_cnt
                tmp_cnt_h[j] = 0

        count_w[i][W-w_cnt:W] = [w_cnt]*w_cnt

    for i, h_cnt in enumerate(tmp_cnt_h):
        for x in range(H-h_cnt,H):
            count_h[x][i] = h_cnt

    max_light = 0
    for i in range(H):
        for j in range(W):
            max_light = max(max_light, count_h[i][j] + count_w[i][j])
    print(max_light-1)

if __name__ == "__main__":
    main()

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

int main(){
    string s,t;
    cin >> s >> t;
    int ans = 0;
    for(int i=0;i<3;i++){
        if(s[i] == t[i]){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
int ans[10][10];
int main(){
    cin>>n;
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            for(int k=1;k<=n;k++){
                if(k%10==j){
                    int xx=k;
                    while(xx>=10)xx/=10;
                    if(xx==i)ans[i][j]++;
                }
            }
        }
    }
    long long Ans=0;
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            Ans+=ans[i][j]*ans[j][i];
        }
    }
    cout<<Ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<cmath>
#include<iostream>
#include<string>
#include <vector>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
using namespace std;

int main(){
	int n, a[100000], mx = 0, b = 0;

	scanf("%d", &n);
	REP(i, n){
		scanf(" %d", &a[i]);
		if (a[i]>mx){
			mx = a[i];
		}
	}

	REP(i, n){
		if (abs(a[i] - mx / 2) < abs(b - mx / 2)){
			b = a[i];
		}
		else if (abs(a[i] - (mx + 1) / 2) < abs(b - mx / 2)){
			b = a[i];
		}
		else if (abs(a[i] - (mx + 1) / 2) < abs(b - (mx+1) / 2)){
			b = a[i];
		}
		else if (abs(a[i] - (mx) / 2) < abs(b - (mx+1) / 2)){
			b = a[i];
		}
	}

	printf("%d %d\n", mx, b);

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){

    int a;
    double res;
    cin>>a;
    if(a%2==0){
        res=a/2;
    }
    else{
        res=(a/2)+1;
    }
    res=double(res/a);
    printf("%.10f\n",res);





}




Measured memory_bytes: 256
H, W = map(int, input().split())
S =[input() for i in range(H)]

L = [""]*H
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
        L[i] += "#"
    else:
      c = sum(t[max(0,j-1):min(W,j+2)].count("#") for t in S[max(0,i-1):min(H,i+2)])
      L[i] += str(c)
for i in range(H):
  print(L[i])


Measured memory_bytes: 3064
#include<stdio.h>
int main(){
  long long h,w;
  scanf("%lld %lld",&h,&w);
  if(h==1||w==1){
    printf("1\n");
    return 0;
  }
  printf("%lld\n",(h%2)*(w%2)?h*w/2+1:h*w/2);
  return 0;
}


Measured memory_bytes: 128
/* Question 5

Abhishek Trivedi
20192015
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k;
    cin>>k;
    
    for(int i=1;i<=k;i++)
    {
        cout<<"A"<<"C"<<"L";
        //Abhishek trivrdiiiii
        
    }
    
    
    
    return 0;
    
}


Measured memory_bytes: 3544
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>

int main(int argc, char *argv[])
{
    int a[3], b[3];
    int c[4];
    int i;
    int yes;

    // init
    for (i = 0; i < 4; i++) {
        c[i] = 0;
    }
    // read
    for (i = 0; i < 3; i++) {
        scanf("%d %d", &a[i], &b[i]);
        c[a[i] - 1]++;
        c[b[i] - 1]++;
    }

    yes = 1;

    for (i = 0; i < 4; i++) {
        if (c[i] == 0 || c[i] == 3) {
            yes = 0;
        }
    }

    if (yes) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }

    return 0;
}


Measured memory_bytes: 128
import collections

n,k=map(int,input().split())
a=list(map(int,input().split()))
now_k=len(set(a))
d=now_k-k
arr=collections.Counter(a).most_common()
#print(arr)
b=sorted([arr[i][1] for i in range(now_k)])
#print(b)
cnt=now_k
cnt2=0
flg=0
for i in b:
  cnt-=1
  cnt2+=i
  if cnt==k:
    print(cnt2)
    flg=1
    break
if flg==0:
  print(0)

Measured memory_bytes: 48424
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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 int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

int main() {
  rep(i, 0, 3) {
    string c;
    cin >> c;
    cout << c[i];
  }
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(min(k, 50)):
    b = [0]*(n+1)
    for i in range(n):
        b[max(0, i-a[i])] += 1
        b[min(i+a[i]+1, n)] -= 1
    for i in range(1, n+1):
        b[i] += b[i-1]
    for i in range(n):
        a[i] = b[i]
print(*a)

Measured memory_bytes: 170012
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int H, W, K;

void fill2(int w_left, int w_right,
           int h_min, int h_max,
           vector<vector<int>>& ans,
           int &next) {
    FOR(h, h_min, h_max + 1) {
        FOR(w, w_left, w_right + 1) {
            ans[h][w] = next;
        }
    }
    ++next;
}

void fill(int w_left, int w_right, int w_check,
          vector<vector<int>>& ans,
          vector<string>& cells,
          int &next) {

    vector<int> h_flags;
    REP(h, H) {
        if (cells[h][w_check] == '#') {
            h_flags.pb(h);
        }
    }

    fill2(w_left, w_right,
          0, h_flags[0],
          ans, next);

    FOR(i, 1, SIZE(h_flags)) {
        fill2(w_left, w_right,
              h_flags[i - 1] + 1, h_flags[i],
              ans, next);
    }

    // rep
    FOR(h, h_flags.back() + 1, H) {
        FOR(w, w_left, w_right + 1) {
            ans[h][w] = ans[h-1][w];
        }
    }
}

void print_ans(vector<vector<int>>& ans) {
	REP(h, H) {
		REP(w, W) {
			if (w == 0) {
				cout << ans[h][w];
			}
			else {
				cout << " " << ans[h][w];
			}
		}
		cout << endl;
	}
}

int main(void)
{
    cin.sync_with_stdio(false);
    cin >> H >> W >> K;

    vector<string> cells(H);

    REP(h, H) {
        cin >> cells[h];
    }

    vector<int> w_flags;
    REP(w, W) {
        bool has = false;
        REP(h, H) {
            if (cells[h][w] == '#') {
                has = true;
                break;
            }
        }
        if (has) w_flags.pb(w);
    }

    vector<vector<int>> ans(H, vector<int>(W));
    int next = 1;

    fill(0, w_flags[0], w_flags[0],
         ans,
         cells,
         next);

    FOR(i, 1, SIZE(w_flags)) {
        fill(w_flags[i-1] + 1, w_flags[i], w_flags[i],
             ans,
             cells,
             next);
    }

	//print_ans(ans);

    // rep
    FOR(w, w_flags.back() + 1, W) {
        REP(h, H) {
            ans[h][w] = ans[h][w-1];
        }
    }

	print_ans(ans);


    return 0;
}


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

int main() {
  int N,A,B;
  cin>>N>>A>>B;
  string S;
  cin>>S;
  int a=0, b=0;
  for(int i=0;i<N;i++){
    if(S[i]=='a'){
      if(A+B>a+b){
        cout<<"Yes"<<endl;
        a++;
      }
      else{
        cout<<"No"<<endl;
      }
    }
    else if(S[i]=='b'){
      if(A+B>a+b&&B>b){
        cout<<"Yes"<<endl;
        b++;
      }
      else{
        cout<<"No"<<endl;
      }
    }
    else{
      cout<<"No"<<endl;
    }
  }
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }

// max segtree
struct segtree {
	ll seg[800005];
	void update(int nid, int l, int r, int pos, ll v) {
		if (l == pos && pos == r) {
			seg[nid] = v;
			return;
		}

		int m = l + r >> 1;
		if (pos <= m) update(nid * 2, l, m, pos, v);
		else update(nid * 2 + 1, m + 1, r, pos, v);

		seg[nid] = max(seg[nid * 2], seg[nid * 2 + 1]);
	}
	ll query(int nid, int l, int r, int ql, int qr) {
		if (ql == l && qr == r) return seg[nid];

		int m = l + r >> 1;
		if (qr <= m) return query(nid * 2, l, m, ql, qr);
		else if (ql > m) return query(nid * 2 + 1, m + 1, r, ql, qr);
		else return max(
				query(nid * 2, l, m, ql, m),
				query(nid * 2 + 1, m + 1, r, m + 1, qr));
	}
} seg;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n; read(n);
	
	vector<pair<int, pair<int, ll>>> v(n);
	rep(i, 0, n) v[i].second.first = i + 1;
	rep(i, 0, n) read(v[i].first);
	rep(i, 0, n) read(v[i].second.second);

	sort(all(v));

	rep(i, 0, n) {
		int h = v[i].first, pos = v[i].second.first; ll val = v[i].second.second;
		seg.update(1, 0, n, pos, seg.query(1, 0, n, 0, pos - 1) + val);
	}

	die(seg.query(1, 0, n, 0, n));
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

inline void InitRand()
{
    srand((unsigned int)time(NULL));
}

int main() {
    InitRand();
    int D; cin >> D;
    veci C(26);
    vecveci S(D,veci(26));
    veci T(D);
    REP(i,26) cin >> C[i];
    REP(i,D) REP(j,26) cin >> S[i][j];
    veci last(26),pre(26);
    REP(i,D) {
        int cost = 0;
        int d = 1;
        int max_p;
        REP(j,26) {
            pre = last;
            int total = 0;
            total += S[i][j];
            pre[j] = d;
            REP(k,26) {
                total -= C[k]*(d-pre[k]);
            }
            pre[j] = last[j];
            if(total > cost) {
                cost = total;
                max_p = j;
            }
        }
        last[max_p] = d;
        T[i] = max_p;
    }

    veci last_d(26);
    ll old_ans = 0;
    REP(i,D) {
        int d = i+1;
        last_d[T[i]] = d;
        old_ans += S[i][T[i]];
        REP(j,26) {
            old_ans -= C[j]*(d-last_d[j]);
        }
    }

    clock_t s = clock();

    while(1) {
        int B = rand()%D;
        int Q = rand()%26;
        int old_p = T[B];
        T[B] = Q;
        ll score = 0;
        veci last(26);
        REP(j,D) {
            int d = j+1;
            last[T[j]] = d;
            score += S[j][T[j]];
            REP(k,26) {
                score -= C[k]*(d-last[k]);
            }
        }
        if(old_ans < score) {
            old_ans = score;
        }
        else {
            T[B] = old_p;
        }
        clock_t e = clock();
        const double time = static_cast<double>(e - s) / CLOCKS_PER_SEC * 1000.0;
        if(time >= 1980) break;
    }
    REP(i,D) cout << T[i]+1 << endl;
}

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
const ll INF = 1LL << 60;

int main(){
	string s;
	cin >> s;
	if(s[0] == s[1] && s[1] == s[2]) puts("Yes");
	else if (s[1] == s[2] && s[2] == s[3]) puts("Yes");
	else puts("No");
}


Measured memory_bytes: 256
/* [Template].cpp 
Example code to use when starting new code. This particular problem was problem 
977A_Wrong_Subtraction from CodeForces

Compile: g++  -o A.exe A.cpp 
Execute: ./A
*/ 

#include <cstdio>
#include <iostream>
#include <cmath> 
#include <limits> 
#include <iomanip>
#include <cstring> 
#include <bits/stdc++.h>
#include <string>  
using namespace std;

int main() { 	
	char S[20]; 
	
	cin >> S; 
	
	cout << S[0] << S[1] << S[2] << endl; 
	
	return 0; 
} 


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> adj[100001];
bool visited[100001];
int dp[100001];
void dfs (int cur){
    int maxi=-1;
    visited[cur]=true;
    for (int i=0; i<adj[cur].size(); i++){
        if (!visited[adj[cur][i]]) dfs(adj[cur][i]);
        dp[cur]=max(dp[cur], dp[adj[cur][i]]+1);
    }
}
int main(){
    int n, m, x, y;
    cin>>n>>m;
    for (int i=0; i<m; i++){
        cin>>x>>y;
        adj[x-1].emplace_back(y-1);
    }
    for (int i=0; i<n; i++){
        if (!visited[i]) dfs(i);
    }
    cout<<*max_element(dp, dp+n)<<endl;
}

Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int N;
	bool result = false;
	cin >> N;
  	
  	for ( int i=0; i<= N/4; i++){
    	for ( int j=0; j<= (N-i*4)/7; j++){
        	if( N-i*4-j*7 == 0){
            	result = true;
            }
        }
    }
  	
	if(result){
   		cout << "Yes" << endl;
    }
	else{
    	cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <cstring>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n = gi();
    ll s = 0;
    ll sd = 0;
    for (int i = 0; i < n; i++) {
        ll d = gi();
        ll c = gli();
        s += c*d;
        sd += c;
    }

    ll res = s/9 - (s%9 ? 0 : 1);
    res += sd-1;
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
a = input().split()
a = [int(i) for i in a]
now = 0

for i in range(a[2]):
	if a[now] %2 == 0:
		a[1 - now] += a[now] // 2
		a[now] = a[now] // 2
	else:
		a[now] -= 1
		a[1-now] += a[now] //2
		a[now] //= 2
	if now == 0:
		now = 1
	else:
		now = 0
		
print (a[0], a[1])

Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;
int n,q;
const int m=1e5+5;
vector<ll> v(1e5+6);
int main(){
    cin >> n;
    ll ans=0;
    for(int i=0; i<n; i++){ll a; cin >> a; v[a]++; ans+=a;} 
    cin >> q;
    vector<ll> v_ans(m); v_ans[0]=ans;
    for(int i=0; i<q; i++){
        ll b,c; cin >> b >> c; 
        v_ans[i+1] = v_ans[i] + c*v[b] - b*v[b];
        v[c]+=v[b]; v[b]=0;
    }
    for(int i=0; i<q; i++) cout << v_ans[i+1] << "\n";
}

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

using namespace std;

vector<int64_t> nums;
stack<tuple<int64_t, int64_t, size_t>> s;
vector<tuple<int64_t, int64_t, size_t>> next_;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  nums.reserve(N + 1);
  nums.emplace_back();
  for (int i = 1; i <= N; ++i) {
    nums.emplace_back();
    cin >> nums.back();
  }

  const auto left_end = nums.cbegin();
  int64_t result = 0;
  int64_t val = 0;
  for (auto it = left_end + 1; it != nums.cend(); ++it) {
    next_.clear();
    while (!s.empty() && get<1>(s.top()) < *it) {
      auto top = s.top();
      s.pop();
      val -= get<1>(top) * get<2>(top);
      if (get<0>(top) < *it) {
        get<1>(top) = get<0>(top);
        get<0>(top) = *it;
      } else {
        get<1>(top) = *it;
      }
      val += get<1>(top) * get<2>(top);
      if (!next_.empty() && get<0>(next_.back()) == get<0>(top) &&
          get<1>(next_.back()) == get<1>(top)) {
        get<2>(next_.back()) += get<2>(top);
      } else {
        next_.emplace_back(top);
      }
    }
    result += val;
    for (auto it = next_.crbegin(); it != next_.crend(); ++it) {
      s.emplace(move(*it));
    }
    s.emplace(*it, 0, 1);
  }
  cout << result << endl;
}


Measured memory_bytes: 3456
import math
from collections import Counter
def larger_nibeki(i):
    return 2 ** int(math.log2(a) + 1)
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
ans = 0
C = Counter(A)
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Measured memory_bytes: 33752
#include <cstdio>
using namespace std;

int main(void)
{
    int score;
    int A_sum = 0, B_sum = 0;
    
    for (int i = 0; i < 8; i++){
        scanf(" %d", &score);
        if (i < 4){
            A_sum += score;
        }
        else {
            B_sum += score;
        }
    }
    
    printf("%d\n", (B_sum <= A_sum) ? A_sum : B_sum);
    
    return (0);
}

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] rgb = new int[3];
		rgb[0] = sc.nextInt();
		rgb[1] = sc.nextInt();
		rgb[2] = sc.nextInt();
		int N = sc.nextInt();
		sc.close();
		Arrays.sort(rgb);
		int rgb1 = N / rgb[1];
		int rgb2 = N / rgb[2];

		int ans = 0;
		for (int i = 0; i <= rgb2; i++) {
			for (int j = 0; j <= rgb1; j++) {
				int diff = N;
				if (i != 0) {
					diff -= rgb[2] * i;
					if (diff == 0) {
						ans++;
						break;
					}
					if (diff < 0) {
						break;
					}
				}
				if (j != 0) {
					diff -= rgb[1] * j;
					if (diff == 0) {
						ans++;
						break;
					}
					if (diff < 0) {
						break;
					}
				}
				if (diff % rgb[0] == 0) {
					ans++;
				}
				continue;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 23380
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m;
map<string,int> red,blue;

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  cin >> n;
  for(int i=0;i<n;i++){
    string s;
    cin >> s;
    blue[s]++;
  }
  cin >> m;
  for(int i=0;i<m;i++){
    string s;
    cin >> s;
    red[s]++;
  }
  int ans = 0;
  for(auto t:blue){
    ans = max(ans,t.second-red[t.first]);
  }
  cout << ans << endl;



return 0;
}
///....


Measured memory_bytes: 384
// https://atcoder.jp/contests/abc177/tasks/abc177_e
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

const int SZ = 1e6;

// エラトステネスの篩
template <int N> struct Prime {
    bitset<N + 1> b;
    Prime() : b() {
        // trueで初期化
        b.flip();
        b[0] = b[1] = false;
        for (int i = 2; i <= N; ++i) {
            if (b[i]) {
                for (int j = i * i; j <= N; j += i) {
                    b[j] = false;
                }
            }
        }
    }
};
// SZ = 1e6 だと10ms
Prime<SZ> prime;

void solve() {
    int N;
    cin >> N;
    vector<int> A(N), D(SZ + 1);
    for (auto &x : A) {
        cin >> x;
        // 同じ数が重複するケースを考慮
        D[x]++;
    }
    // trueなら "pairwise coprime"
    bool pc = true;

    // ラムダ式で多重ループから抜ける
    [&] {
        REP(i, SZ) {
            // 素数の場合
            if (prime.b[i]) {
                int cnt = 0;
                for (int now = i; now <= SZ && cnt <= 1; now += i) {
                    cnt += D[now];
                    // 共通の素数を含むのでgcd(ALL) >= i
                    if (cnt >= 2) {
                        pc = false;
                        return;
                    }
                }
            }
        }
    }();

    if (pc) {
        cout << "pairwise coprime" << endl;
    } else {
        int g = A[0];
        for (auto &x : A) {
            g = gcd(g, x);
        }
        if (g == 1)
            cout << "setwise coprime" << endl;
        else
            cout << "not coprime" << endl;
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 19016
using System;

namespace C_Sum_of_gcd_of_Tuples__Easy_
{
    class Program
    {
        public static int Ggcd(int x,int y)
        {
            int t = x % y;
            if (t == 0)
            {
                return y;
            }

            return Ggcd(y, t);
        }

        public static int Gcd(int x, int y, int z)
        {
            int s = Ggcd(x, y);

            return Ggcd(s, z);
        }

        static void Main(string[] args)
        {
            int ans = 0;
            int k = int.Parse(Console.ReadLine());
            for(int a = 1; a <= k; a++)
            {
                for (int b = 1; b <= k; b++)
                {
                    for (int c = 1; c <= k; c++)
                    {
                        ans += Gcd(a, b,c);
                    }
                }
            }
            Console.WriteLine(ans);
        }

        
    }
}


Measured memory_bytes: 27536
input();a=list(map(int,input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,len(a)):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%(10**9+7)
print(r)

Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
    ll T1,T2,A1,A2,B1,B2;cin>>T1>>T2>>A1>>A2>>B1>>B2;
    ll C=T1*A1-T1*B1,D=T2*A2-T2*B2,ans=0;
    if(C+D==0){
    	cout<<"infinity"<<endl;
    	return 0;
    }
    if(C>0){
        if(C+D<0){
            ans=C/(-C-D)*2;
            if(C%(C+D))ans+=1;
        }
    }
    else{
        if(C+D>0){
            ans=-C/(C+D)*2;
            if(C%(C+D))ans+=1;
        }
    }
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    a,b=map(int,input().split())
    a-=1;b-=1
    uf.union(a,b)
print(len(set([uf.find(i)for i in range(N)]))-1)

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

int n,t,a;
std::vector<int> h;

void input()
{
    std::cin>>n>>t>>a;
    h.resize(n);
    for(int i=0;i<n;i++)std::cin>>h[i];
}

int main()
{
    input();
    double res=10000000;
    int mini;
    for(int i=0;i<n;i++){
        double tmp = t - h[i]*0.006;
        tmp = std::abs(a-tmp);
        if(tmp<res){
            res = tmp;
            mini = i;
        }
    }
    std::cout<<mini+1<<std::endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>
#include <cstdio>
#include <iomanip>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>()>
#define pb push_back
#define vec vector<int>
#define vecvec vector<vector<int>>
#define vecll vector<ll>
#define vecvecll vector<vector<ll>>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
#define mp make_pair
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
ll lin(){ll x;scanf("%lld",&x);return x;}
int f(int k,int l){
    if((k>12||k==0)&(l>12||l==0))return -2;
    if(k>12||k==0)return -1;
    if(l>12||l==0)return 1;
    return 0;
}
int main(){
    string s=stin();
    int a=s[0]-'0',b=s.at(1)-'0',c=s.at(2)-'0',d=s.at(3)-'0';
    int k=a*10+b,l=10*c+d;
    string ans;
    int q=f(k,l);
    if(q==-2)cout<<"NA"<<endl;
    else if(q==-1)cout<<"YYMM"<<endl;
    else if(q==0)cout<<"AMBIGUOUS"<<endl;
    else cout<<"MMYY"<<endl;
}

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

typedef long long ll;
const int maxn = 1500010;
int n, m; ll f[maxn];
vector<pair<int, int>> G[maxn];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;

void add(int u, int v, int w) {
    G[u].push_back(make_pair(v, w));
}

#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
void build1(int k, int l, int r) {
    if (l == r) { add(l, k + n, 0); return; }
    build1(ls, l, mid), build1(rs, mid + 1, r);
    add(ls + n, k + n, 0), add(rs + n, k + n, 0);
}

void build2(int k, int l, int r) {
    if (l == r) { add(k + 5 * n, l, 0); return; }
    build2(ls, l, mid), build2(rs, mid + 1, r);
    add(k + 5 * n, ls + 5 * n, 0), add(k + 5 * n, rs + 5 * n, 0);
}

void add1(int k, int l, int r, int ql, int qr, int p) {
    if (l >= ql && r <= qr) { add(k + n, p, 0); return; }
    if (mid >= ql) add1(ls, l, mid, ql, qr, p);
    if (mid < qr) add1(rs, mid + 1, r, ql, qr, p);
}

void add2(int k, int l, int r, int ql, int qr, int p) {
    if (l >= ql && r <= qr) { add(p, k + 5 * n, 0); return; }
    if (mid >= ql) add2(ls, l, mid, ql, qr, p);
    if (mid < qr) add2(rs, mid + 1, r, ql, qr, p);
}

int main() {
    scanf("%d %d", &n, &m);
    build1(1, 1, n), build2(1, 1, n);
    int tot = 9 * n;
    for (int i = 1, l, r, c; i <= m; i++) {
        scanf("%d %d %d", &l, &r, &c);
        add1(1, 1, n, l, r, tot + 1), add2(1, 1, n, l, r, tot + 2);
        add(tot + 1, tot + 2, c), tot += 2;
    }
    memset(f, 0x3f, sizeof(f)), q.push({f[1] = 0, 1});
    while (!q.empty()) {
        auto p = q.top(); q.pop();
        if (p.first ^ f[p.second]) continue;
        for (auto nxt : G[p.second]) {
            ll nd = p.first + nxt.second;
            if (nd < f[nxt.first]) q.push({f[nxt.first] = nd, nxt.first});
        }
    }
    printf("%lld\n", f[n] > 1e18 ? -1 : f[n]);
    return 0;
}

Measured memory_bytes: 97008
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;

static const long long INF = 1e18;



int main()
{
	int N, K;
	cin >> N >> K;

	//x,yのデータを格納
	vector< long long > x(N, 0);
	vector< long long > y(N, 0);
	vector< vector<long long> > x_y(N,vector<long long>(2,0));

	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
		x_y[i][0] = x[i];
		x_y[i][1] = y[i];
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	long long x_left, x_right, y_bottom, y_top;
	int cnt;
	vector< long long > a;

	for (int i = 0; i < N;i++) {
		for (int j = i + 1;j < N ;j++) {
			for (int k = 0; k < N ;k++) {
				for (int l = k + 1; l < N ;l++) {
					cnt = 0;
					x_left = x[i];
					x_right = x[j];
					y_bottom = y[k];
					y_top = y[l];

					for (int m = 0; m < N;m++) {
						if (x_left <= x_y[m][0] && x_y[m][0] <= x_right && y_bottom <= x_y[m][1] && x_y[m][1] <= y_top)
							cnt++;
					}

					if (cnt >= K)
						a.push_back((x_right-x_left)*(y_top-y_bottom));



				}
			}
		}
	}
	long long ans;
	ans = *min_element(a.begin(), a.end());
	cout << ans << endl;




	return 0;
}



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

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()

// output
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ln cout << '\n'
template <Z A>
void pr(A a)
{
  cout << a;
  ln;
}
template <Z A, Z B>
void pr(A a, B b)
{
  cout << a << ' ';
}

int ans = 0;
bool check = 0;
int N = 0;
vector<int> v(N);
int a, b;
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

int main()
{
  cin >> a ;
  cout << "ABC" << a ;

  return 0;
}

Measured memory_bytes: 3624