akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class D
{
	public static void Main() => (new Solver()).Solve();
}


public class Solver
{
	public void Solve()
	{
		int Q = GetInt();
		long[] A = new long[Q];
		long[] B = new long[Q];
		for(int i = 0; i < Q; i++)
		{
			A[i] = GetLong();
			B[i] = GetLong();
		}

		long[] ans = new long[Q];
		for(int i = 0; i < Q; i++)
			ans[i] = calc(A[i], B[i]);

		Console.WriteLine(string.Join("\n", ans.Select(x => x.ToString()).ToArray()));
	}

	private long calc(long A, long B)
	{
		if(A == B)
			return (2 * A - 2);

		if(A > B)
			swap(ref A, ref B);

		long T = A * B;
		long ok = 0;
		long ng = (1L << 31);
		while(Math.Abs(ng - ok) > 1)
		{
			long mid = (ng + ok) / 2;
			long max = ((mid + 1) / 2) * (mid + 1 - ((mid + 1) / 2));
			if(max < T)
				ok = mid;
			else
				ng = mid;
		}

		return ok - 1;
	}

	private void swap(ref long x, ref long y)
	{
		long tmp = x;
		x = y;
		y = tmp;
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(int N) => Enumerable.Range(0, N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(int N) => Enumerable.Range(0, N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(int N) => Enumerable.Range(0, N).Select(_ => GetDouble()).ToArray();
	public static string[] GetStrings(int N) => Enumerable.Range(0, N).Select(_ => GetString()).ToArray();
}


Measured memory_bytes: 13396
#include <iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define N 100010

using namespace std;

int main() {
    ll n ,a[N],m,p,q ;
    
    
    cin >> n;
    ll sum=0;

    for (ll i = 1; i <=n; i++) {
        scanf("%lld",&a[i]);
        sum+=a[i];

    }

    cin >> m;
    for (ll i = 1; i <=m; i++) {
        
        scanf("%lld%lld",&p,&q);

       printf("%lld\n",sum+q-a[p]);
    }
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	long int n, sum;
	long int i;

	scanf("%ld", &n);

	sum = 0;

	for (i = 1; i <= n; i++)
	{
		if (i % 3 == 0 || i % 5 == 0)
			continue;
		sum += i;
	}

	printf("%ld", sum);

	return 0;
}

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

int T, N, K, X[100000+10], A[100000+10];
int main(){
    cin >> T;
    for (int t = 0; t < T; t++){
        cin >> N >> K;
        for (int i = 0; i < N; ++i) cin >> X[i];
        for (int i = 0; i+1 < N; ++i) A[i] = X[i+1]-X[i];
        sort(A,A+N-1);
        /*for (int i = 0; i+1 < N; ++i){
            cout << A[i] << endl;
        }  */
        if(N <= K){
            cout << 0 << endl;
        }else{
            int ans = 0;
            for(int i = 0; i < N - K; ++i){
                ans += A[i];
            }
            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 3808
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 10000000000000000; //10^16
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int N,M,X;
    cin >> N >> M >> X;
    vector<vector<int>> A(N+2, vector<int> (M+2));
    for(int i = 1; i < N+1; i++){
        for(int j = 0; j < M+1; j++){
            cin >> A.at(i).at(j);
        }
    }
    
    vector<int> searching(N+2,0);
    vector<int> realize(M+2,0);
    int tmp,ans,money;
    bool check;
    ans = 10000000;
    for(int i = 1; i < pow(2,N); i++){
        tmp = i;
        for(int j = 1; j < N+1; j++){
            searching.at(j) = tmp%2;
            tmp = tmp/2;
        }
        
        for(int j = 0; j < M+1; j++){
            realize.at(j) = 0;
        }
        money = 0;

        for(int j = 1; j < N+1; j++){
            if(searching.at(j) == 1){
                for(int l = 1; l < M+1; l++){
                    realize.at(l) += A.at(j).at(l);
                }
                money += A.at(j).at(0);
            }
        }

        check = true;
        for(int j = 1; j < M+1; j++){
            if(realize.at(j) < X) check = false;
        }

        if(check){
            ans = min(ans, money);
        }

    }

    if(ans == 10000000){
        printf("-1\n");
    }
    else{
        printf("%d\n", ans);
    }

}



Measured memory_bytes: 4176
#include <stdio.h>

int main() {

    int ABC[3];
    int swap[3];

scanf("%d %d %d", &ABC[0], &ABC[1], &ABC[2]);

    swap[0] = ABC[0];
    swap[1] = ABC[1];

    ABC[0] = swap[1];
    ABC[1] = swap[0];

    swap[0] = ABC[0];
    swap[1] = ABC[2];
    ABC[0] = swap[1];
    ABC[2] = swap[0];

printf("%d %d %d\n", ABC[0], ABC[1], ABC[2]);

return 0;

}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String num = sc.nextLine();
        //String line = sc.nextLine();
        check(num);
    }

    public static void check(String num) {

        String[] strs = num.split(" ");
        int a1 = Integer.parseInt(strs[0]) + Integer.parseInt(strs[1]);
        int a2 = Integer.parseInt(strs[0]) - Integer.parseInt(strs[1]);
        int a3 = Integer.parseInt(strs[0]) * Integer.parseInt(strs[1]);

        int max = 0;
        if(a1 >= a2) {
            max = a1;
        } else {
            max = a2;
        }
        if(a3 >= max) {
            System.out.println(a3);
        } else {
            System.out.println(max);
        }
    }
}

Measured memory_bytes: 25300
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {

	int A, B, N;
	string S;

	cin >> N >> A >> B >> S;

	int d=0, nd=0;
	for (int i = 0; i < N; i++) {
		if (S[i] == 'a') {
			d++;
			if (d+nd  <= A+B) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
				d--;
			}

		}
		else if(S[i]=='b') {
			nd++;
			if (d+nd <= A+B && nd <= B) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
				nd--;
			}
		}
		else {
			cout << "No" << endl;
		}
	}

	return 0;
}

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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;

const ll MOD=1000000007;

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b){
  ll p=1;
  for(int i=0;i<b;i++){
    p*=a;
  }
  return p;
}

int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p){
  ll n=solveLinear(a,p,1);
  n=n%p;
  if(n<0)return n+p;
  return n;
}

int d2(ll a){
  int i=0;
  while(a%2==0){
    a/=2;
    i++;
  }
  return i;
}

ll f(ll a){
  int i,d=digit(a,2);
  ll ret=0;
  for(i=0;i<d;i++){
    ll x=(a+1)%(pow1(2,i+1));
    if(i==0 && x==0)x=1;
    ret+=((max(x-pow1(2,i),(ll)0)+(a+1)/pow1(2,i+1)*pow1(2,i)))%2*pow1(2,i);
  }
  return ret;
}

int main(){
  ll i,j,cnt;
  ll a,b;
  cin>>a>>b;
  ll ans=0;
  cout<<(f(b)^f(a-1))<<endl;
}

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

int main(){
    int r, g, b, n, cnt;
    cin >> r >> g >> b >> n;
    cnt = 0;
    int a[3] = {r, g, b};
    sort(a, a + 3);
    int max = n / a[2];
    while(max >= 0){
        int m = n - max * a[2];
        int tmp = m / a[1];
        while(tmp >= 0){
            int l = m - tmp * a[1];
            if(l % a[0] == 0 || l == 0) cnt++;
            tmp--;
        }
        max--;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int k = sc.nextInt();
    String s = sc.next();
    // System.out.println(s.length());
    if(k<s.length()){
      for(int i=0 ; i<k ; i++){
        System.out.print(s.charAt(i));
      }
      System.out.println("...");
    }else{
      System.out.println(s);
    }
  }
}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
typedef double DOUBLE;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

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

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const ll LL_INF = 1e17 + 10;
const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

void solve(){
	ll sum = 0, len = 0;
	int n;
	scanf("%d", &n);
	REP(i, 0, n) {
		ll d, c;
		scanf("%lld%lld", &d, &c);
		len += c;
		sum += d * c;
	}
	ll ans = len - 1 + (sum - 1) / 9;
	cout << ans << endl;
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define INT_MAX INT64_MAX
#define INT_MIN INT64_MIN
#define CLK clock_t clk = clock();//Start of main
#define OCLK cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / CLOCKS_PER_SEC << '\n';//End of main
#define MOD 1000000007
/* DEFINE cout */
#define pln cout << "===============================\n"
#define on cout<<"\n"
#define os cout<<" "
#define o2(a,b) cout<<a<<" "<<b
#define o(a) cout << a
#define bitcount __builtin_popcount
/* DEFINE cout */
#define endl "\n"
#define M_PI 3.14159265358
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//fastio
using namespace std;
struct hash_pair { // use pair as key in unordered_map<pair<int,int>,int,hash_pair>;
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
bool prime[10000001];
int P=MOD-2;
int factorial[10000001]={0};
int powerFunction(int x,int y){
    int res = 1;
    int p = MOD;
    x = x % p;
    while (y > 0){
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
void sieveFunction(int maxLimit){
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1]=false;
    for(int i=2; maxLimit >= i ; i++){
        if(prime[i]){
            for(int j=2*i ; maxLimit >= j ; j+=i)
                prime[j]=false;
        }
    }
}
void factorialFunction(int maxLimit){
    factorial[0]=1;
    for(int i=1 ; i <= maxLimit ; i++)
        factorial[i]=(factorial[i-1]*i)%MOD;
    return;
}
int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
signed main(){
    int r;
    cin >> r;
    cout << 2*M_PI*r << endl;
}






Measured memory_bytes: 3740
import java.util.*;
public class Main { 
    public static void main(String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        for (int i = 1; i <= num; i++) { 
              int x=i;
              if(x % 3 == 0){
                  System.out.print(" "+i);
              }
              else{
                 for (; x>=1; x /= 10) { 
                     if ( x % 10 == 3 ){
                         System.out.print(" "+i);
                         break;
                     }
                 } 
              }
        } 
         System.out.println();
    } 
} 


Measured memory_bytes: 28740
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <utility>
#include <set>
#include <map>
#include <deque>
#include <stack>

using namespace std;

typedef long long ll;

ll A[100005], N;

string s;

void print(){
    for(ll i=0; i<N; i++){
        if (A[i] == 1) cout << 'S';
        else cout << 'W';     
    } 
    cin >> N;
    exit(0);
}

int main(){
	ll i, r, l;
	
	cin >> N >> s;
	
	for(l=0; l<2; l++){
        for(r=0; r<2; r++){
    
	        A[0] = l;
	        A[1] = r;
	
	        for(i=1; i<N-1; i++){
                if (A[i] == 1){
                     if (s[i] == 'o') A[i+1] = A[i-1];
                     else { if (A[i-1] == 1) A[i+1] = 0;
                            else A[i+1] = 1;}     
                }
                else{
                    if (s[i] == 'o') { if (A[i-1] == 1) A[i+1] = 0;
                                       else A[i+1] = 1;}
                    else A[i+1] = A[i-1];
                }
            }
             
	    if ( A[0] == 1 && s[0] == 'o' && A[N-1] == A[1] &&
	         A[N-1] == 1 && s[N-1] == 'o' && A[N-2] == A[0] ||
	         
	         A[0] == 1 && s[0] == 'o' && A[N-1] == A[1] &&
	         A[N-1] == 1 && s[N-1] == 'x' && A[N-2] != A[0] ||
	         
	         A[0] == 1 && s[0] == 'x' && A[N-1] != A[1] &&
	         A[N-1] == 1 && s[N-1] == 'o' && A[N-2] == A[0] ||
	         
	         A[0] == 1 && s[0] == 'x' && A[N-1] != A[1] &&
	         A[N-1] == 1 && s[N-1] == 'x' && A[N-2] != A[0] ||
	         
	         
	         A[0] == 1 && s[0] == 'o' && A[N-1] == A[1] &&
	         A[N-1] == 0 && s[N-1] == 'o' && A[N-2] != A[0] ||
	         
	         A[0] == 1 && s[0] == 'o' && A[N-1] == A[1] &&
	         A[N-1] == 0 && s[N-1] == 'x' && A[N-2] == A[0] ||
	         
	         A[0] == 1 && s[0] == 'x' && A[N-1] != A[1] &&
	         A[N-1] == 0 && s[N-1] == 'o' && A[N-2] != A[0] ||
	         
	         A[0] == 1 && s[0] == 'x' && A[N-1] != A[1] &&
	         A[N-1] == 0 && s[N-1] == 'x' && A[N-2] == A[0] ||
	         
	         
	         A[0] == 0 && s[0] == 'o' && A[N-1] != A[1] &&
	         A[N-1] == 1 && s[N-1] == 'o' && A[N-2] == A[0] ||
	         
	         A[0] == 0 && s[0] == 'o' && A[N-1] != A[1] &&
	         A[N-1] == 1 && s[N-1] == 'x' && A[N-2] != A[0] ||
	         
	         A[0] == 0 && s[0] == 'x' && A[N-1] == A[1] &&
	         A[N-1] == 1 && s[N-1] == 'o' && A[N-2] == A[0] ||
	         
	         A[0] == 0 && s[0] == 'x' && A[N-1] == A[1] &&
	         A[N-1] == 1 && s[N-1] == 'x' && A[N-2] != A[0] ||
	         
	         
	         A[0] == 0 && s[0] == 'o' && A[N-1] != A[1] &&
	         A[N-1] == 0 && s[N-1] == 'o' && A[N-2] != A[0] ||
	         
	         A[0] == 0 && s[0] == 'o' && A[N-1] != A[1] &&
	         A[N-1] == 0 && s[N-1] == 'x' && A[N-2] == A[0] ||
	         
	         A[0] == 0 && s[0] == 'x' && A[N-1] == A[1] &&
	         A[N-1] == 0 && s[N-1] == 'o' && A[N-2] != A[0] ||
	         
	         A[0] == 0 && s[0] == 'x' && A[N-1] == A[1] &&
	         A[N-1] == 0 && s[N-1] == 'x' && A[N-2] == A[0]
	    
	    ){
            print();
        }
        }
    }
	
	cout << -1;
	
}


Measured memory_bytes: 1408
#include <stdio.h>

int main(){

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

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

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    string s = "";
    rep(i,k) s += "ACL";
    cout << s << endl;
}

Measured memory_bytes: 3644
N = int(input())
P = list(map(int, input().split()))
MIN = list()
count = 0
MIN.append(P[0])
for i in range(1, N):
    MIN.append(min(MIN[i - 1], P[i]))
for i in range(0, N):
    if P[i] <= MIN[i]:
        count += 1
print(count)


Measured memory_bytes: 26012
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var k = long.Parse(Console.ReadLine());

            if (s.Length == 1 && k == 1)
            {
                Console.WriteLine(0);
                return;
            }

            var index = 0;
            var arr = new int[s.Length];
            arr[0] = 1;
            
            for (var i = 1; i < s.Length; i++)
            {
                if (s[i] == s[i - 1])
                    arr[index]++;
                else
                {
                    index++;
                    arr[index]++;
                }
            }

            var add = 0;
            if (s[0] == s[s.Length - 1])
                add = arr[0] / 2 +  arr[index] / 2 - (arr[0] + arr[index]) / 2;

            var count = 0L;
            for (var i = 0; i <= index; i++)
            {
                if (arr[i] == 1) continue;
                count += arr[i] / 2;
            }

            if (index == 0)
                Console.WriteLine(s.Length * k / 2);
            else
                Console.WriteLine(k * count - add * (k - 1));
        }
    }
}


Measured memory_bytes: 13140
#include<cstdio>
#include<iostream>
using namespace std;
int n,k,a[262144],f[262144],g[262144],x[262144],y[262144];
int main(){
	scanf("%d",&n);
	for(int i=0;i<(1<<n);i++){
		scanf("%d",&a[i]);
		f[i]=a[i]; x[i]=i; y[i]=-1;
	}
	for(int S=0;S<(1<<n);S++){
		for(int j=0;j<=18;j++){
			if(S&(1<<j)){
				if(f[S^(1<<j)]>f[S]&&x[S^(1<<j)]!=x[S]&&x[S^(1<<j)]!=y[S]) g[S]=f[S],f[S]=f[S^(1<<j)],y[S]=x[S],x[S]=x[S^(1<<j)];
				else if(f[S^(1<<j)]>g[S]&&x[S^(1<<j)]!=x[S]&&x[S^(1<<j)]!=y[S]) g[S]=f[S^(1<<j)],y[S]=x[S^(1<<j)];
				if(g[S^(1<<j)]>f[S]&&y[S^(1<<j)]!=x[S]&&y[S^(1<<j)]!=y[S]) g[S]=f[S],f[S]=g[S^(1<<j)],y[S]=x[S],x[S]=y[S^(1<<j)];
				else if(g[S^(1<<j)]>g[S]&&y[S^(1<<j)]!=x[S]&&y[S^(1<<j)]!=y[S]) g[S]=g[S^(1<<j)],y[S]=y[S^(1<<j)];
			}
		}
	}
	int ans=0;
	for(int i=1;i<(1<<n);i++){
		ans=max(ans,f[i]+g[i]);
		printf("%d\n",ans);
	}
	return 0;
}

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

int main(){
  string S;
  cin>>S;
  if((S[2]=='0'&&S[3]!='0')||(S[2]=='1'&&S[3]=='0')||(S[2]=='1'&&S[3]=='1')||(S[2]=='1'&&S[3]=='2')){
    if((S[0]=='0'&&S[1]!='0')||(S[0]=='1'&&S[1]=='0')||(S[0]=='1'&&S[1]=='1')||(S[0]=='1'&&S[1]=='2')){
      cout<<"AMBIGUOUS"<<endl;
    }
    else{
      cout<<"YYMM"<<endl;
    }
  }
  else{
    if(S[0]=='0'&&S[1]!='0'||S[0]=='1'&&S[1]=='0'||S[0]=='1'&&S[1]=='1'||S[0]=='1'&&S[1]=='2'){
      cout<<"MMYY"<<endl;
    }
    else{
      cout<<"NA"<<endl;
    }
  }
}

Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main() {
    int n, m; cin >> n >> m;
    vector<bool> v(n, false);
    vector<int> v2(n, 1);
    v[0] = true;
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        x--; y--;
        v2[x]--;
        v2[y]++;
        if (v[x]) v[y] = true;
        if (v2[x] == 0) v[x] = false;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (v[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define hi cerr<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1
#define sysp system("pause")
#define PI acos(-1)
#define pf push_front
#define ins insert

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
unsigned XorShift(void){static unsigned x = 123456789;static unsigned y = 362436069;static unsigned z = 521288629;static unsigned w = 88675123;unsigned t;t = x ^ (x << 11);x = y; y = z; z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

main(){
    string s;
    cin>>s;
    int n=s.size();
    if(s[0]==s.back()){
        if(n%2)dump("Second");
        else dump("First");
    }else{
        if(n%2)dump("First");
        else dump("Second");
    }
}


Measured memory_bytes: 512
#include<cstdio>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL INF=1e18;
vector<LL>pos,neg;
int main()
{
	int n;
	LL k;
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		if(a>0)pos.pb(a);
		else if(a<0)neg.pb(a);
	}
	sort(pos.begin(),pos.end());
	sort(neg.begin(),neg.end());
	LL ne=1LL*neg.size()*pos.size();
	LL po=1LL*pos.size()*(pos.size()-1)/2+1LL*neg.size()*(neg.size()-1)/2;
	LL ze=1LL*n*(n-1)/2-ne-po;
	if(k<=ne)
	{
		LL l=-INF,r=0,ans;
		while(l<=r)
		{
			LL mid=(l+r)/2,num=0;
			for(int i=0;i<neg.size();i++)
			{
				LL t=mid%neg[i]?mid/neg[i]+1:mid/neg[i];
				int x=lower_bound(pos.begin(),pos.end(),t)-pos.begin();
				num+=pos.size()-x;
			}
			if(num<k)l=mid+1;
			else r=mid-1,ans=mid;
		}
		cout<<ans;
	}
	else if(k<=ne+ze)puts("0");
	else
	{
		LL l=0,r=INF,ans;
		while(l<=r)
		{
			LL mid=(l+r)/2,num=0;
			for(int i=0;i<pos.size();i++)
			{
				if(pos[i]*pos[i]<=mid)num--;
				LL t=mid/pos[i];
				int x=lower_bound(pos.begin(),pos.end(),t+1)-pos.begin();
				if(x)assert(pos[x-1]*pos[i]<=mid);
				//cout<<pos[x]<<" "<<pos[i]<<" "<<pos[x]*pos[i]<<endl;
				if(x<pos.size())assert(pos[x]*pos[i]>mid);
				num+=x;
			}
			for(int i=0;i<neg.size();i++)
			{
				if(neg[i]*neg[i]<=mid)num--;
				LL t=mid/neg[i];
				int x=lower_bound(neg.begin(),neg.end(),t)-neg.begin();
				assert(neg[x]*neg[i]<=mid);
				if(x)assert(neg[x-1]*neg[i]>mid);
				num+=neg.size()-x;
			}
			assert(num%2==0);
			num=num/2+ze+ne;
		//	cout<<mid<<" "<<num<<endl;
			if(num<k)l=mid+1;
			else r=mid-1,ans=mid;
		}
		cout<<ans;
	}
	return 0;
}


Measured memory_bytes: 2420
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
     int n; cin >> n;
     if ((n & 1) == 0) cout << 0.5 << endl;
     else cout << (1 + floor(n / 2)) / n << endl;
     return  0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

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

    static class TaskC {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int N = in.nextInt();
            long[] cnt = new long[5];
            String march = "MARCH";
            for (int i = 0; i < N; i++) {
                char ini = in.next().charAt(0);
                int find = march.indexOf(ini);
                if (find > -1) {
                    cnt[find]++;
                }
            }
            long ans = 0;
            for (int i = 0; i < 5; i++) {
                for (int j = i + 1; j < 5; j++) {
                    for (int k = j + 1; k < 5; k++) {
                        ans += cnt[i] * cnt[j] * cnt[k];
                    }
                }
            }
            out.println(ans);
        }

    }
}



Measured memory_bytes: 45652
#define _CRT_SECURE_NO_DEPRECATE
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <memory.h>
#include <set>
#include <ctime>
#include <map>
#include <cstring>
#include <iterator>
#include <queue>
#include <assert.h>
#include <bitset>
#include <complex>

//#pragma comment(linker, "/STACK:512000000")

using namespace std;

#define pb emplace_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define forab(i, a, b) for (int i = (a); i < (b); ++i)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int infi = 1e9 + 7;
const ll infl = (ll)1e18 + (ll)7;

string s;
ll sum_dp[1000500];
ll sum_a[1000500];

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
   // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    //freopen("customs.in", "r", stdin); freopen("customs.out", "w", stdout);
    int n;
    cin >> n >> s;
    for (char& c : s) {
        if (c == 'D')
            c = 'a';
        if (c == 'M')
            c = 'b';
        if (c == 'C')
            c = 'c';
    }
    int q;
    cin >> q;
    int cnt_b = 0;
    for (int i = n - 1; i >= 0; --i) {
        sum_dp[i] = sum_dp[i + 1];
        sum_a[i] = sum_a[i + 1];
        if (s[i] == 'b') {
            ++cnt_b;
        }
        if (s[i] == 'a') {
            sum_a[i]++;
            sum_dp[i] += cnt_b;
        }
    }
    forn(qwe, q) {
        int k;
        cin >> k;
        int cnt_b = 0;
        ll ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == 'b') {
                ++cnt_b;
                continue;
            }
            if (s[i] != 'c')
                continue;
            
            int j = max(0, i - k + 1);
            ans += sum_dp[j] - sum_dp[i + 1];
            ans -= (sum_a[j] - sum_a[i + 1]) * cnt_b;
        }
        cout << ans << '\n';
    }


    return 0;
}

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

a, b, k = map(int, raw_input().split())
MAX_AB = max(a,b)

cnt = 0
ans = 0
for i in range(MAX_AB):
    j = MAX_AB - i

    if j == 0:
        continue

    if a%j == 0 and b%j == 0:
        cnt += 1
    if cnt == k:
        ans = j
        break

print ans

Measured memory_bytes: 2568
from operator import itemgetter

n, m = map(int, input().split())
aa = list(map(int, input().split()))
bcbc = [list(map(int, input().split())) for _ in range(m)]
bcbc.extend([[1, a] for a in aa])
bcbc.sort(key=itemgetter(1), reverse=True)

count = 0
s = 0
for b, c in bcbc :
    if count + b >= n :
        b = n - count
    count += b
    s += b*c
    if count == n :
        break
print(s)

Measured memory_bytes: 43212
import sys
from operator import itemgetter


def r(n, ab):

    ss = [x + [x[0] + x[1]] for x in ab]
    ss.sort(key=itemgetter(2), reverse=True)
    
    scr = 0
    sente = True
    for s in ss:
        if sente:
            scr += s[0]
        else:
            scr -= s[1]
        sente = not sente

    return scr

def main():
    input = sys.stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n)]
    print(r(n, ab))


if __name__ == '__main__':
    main()


Measured memory_bytes: 39432
#include <stdio.h>

int main(void)

{
  int a , b;

  scanf("%d %d",&a,&b);

  if ( a > b ) {
  	
  	printf("%d\n",a-1);
  	
  } else {
  	
  	printf("%d\n",a);
  	
  	}

  return 0;
}

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

char A[6];

int main() {
    int n; scanf("%d", &n);
    while(1) {
        sprintf(A, "%d", n);
        if(A[0] == A[1] and A[1] == A[2]) break;
        n++;
    }
    printf("%d\n", n);
}

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

using namespace std;

void solve()
{
	string str;
	getline(cin, str);
	int size = str.size();
	string s;
	vector<string> Vec;
	for(int i = 0; i < size; ++i)
	{
		if(str[i] == ' ' || str[i] == ',' || str[i] == '.')
		{
			if(s.empty())
			{
				continue;
			}
			Vec.push_back(s);
			s.clear();
		}
		else
		{
			s += str[i];
		}
	}
	bool flag = true;
	for(int i = 0; i < Vec.size(); ++i)
	{
		if(3 <= Vec[i].size() && Vec[i].size() < 7)
		{
			if(!flag)
			{
				cout << " ";
			}
			cout << Vec[i];
			flag = false;
		}
	}
	cout << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const ll maxn=1e4+200;
const int inf=0x3f3f3f3f;
const double EPS=1e-10;
//typedef pair<int,int> PA;
double add(double a,double b){//考虑误差的加法运算
    if(abs(a+b)<EPS*(abs(a)+abs(b))) return  0;
    return a+b;
}
class Point{
public:

    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){
    }
    Point operator+ (Point p){
        return Point(add(x,p.x),add(y,p.y));
    }
    Point operator -(Point p){
        return Point(add(x,-p.x),add(y,-p.y));
    }
    Point operator *(double d){
        return Point(x*d,y*d);
    }
    double dot(Point p){//外积 p1.p2  outside
        return add(x*p.x,y*p.y);
    }
    double det(Point p){//内积 p1*p2    inner
        return add(x*p.y,-y*p.x);
    }
    double len(){
        return sqrt(add(x*x,y*y));
    }
};
Point operator *(double d,Point p){
    return Point(p.x*d,p.y*d);
}
Point Projection(Point p1,Point p2,Point p){//p 在线段p1,p2上的投影坐标
    double d1=1.0/(p2-p1).len();
    Point ans=(p-p1).dot((p2-p1))*(p2-p1)*d1*d1;
    return ans+p1;
}
typedef Point P;
int main(){
    P p1,p2;
    scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
    int q;
    scanf("%d",&q);
    while(q--){
        P p;
        scanf("%lf%lf",&p.x,&p.y);
        P ans=Projection(p1,p2,p);
        printf("%.10f %.10f\n",ans.x,ans.y);
    }
    return 0;
}



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

int main() {
  int n, m, a, b;
  cin >> n >> m;
  int c[n] = {};

  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    c[a - 1]++;
    c[b - 1]++;
  }

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

Measured memory_bytes: 256
# ARC082D - Derangement (ABC072D)
def main():
    N = int(input())
    P = tuple(map(int, input().split()))
    ans, cur = 0, 0
    for i, j in enumerate(P, 1):
        if i == j:  # subsequence which needs to replace
            cur += 1
        elif i != j and cur:
            ans += (cur + 1) // 2
            cur = 0
    ans += (cur + 1) // 2
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 14008
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
int dp[100001][3];
int a[100001][3];
int main()
{
	int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i][0]>>a[i][1]>>a[i][2];
memset(dp,-1,sizeof(dp));
dp[0][0]=a[0][0];
dp[0][1]=a[0][1];
dp[0][2]=a[0][2];
for(int i=1;i<n;i++)
{
dp[i][0]=a[i][0]+max(dp[i-1][1],dp[i-1][2]);
dp[i][1]=a[i][1]+max(dp[i-1][0],dp[i-1][2]);
dp[i][2]=a[i][2]+max(dp[i-1][0],dp[i-1][1]);	
}
cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));

}
 
 




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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int N; scanf("%d", &N);
  vector<int> A(N + 1);
  int least = INF, most = -INF;
  int ix_most = -1, ix_least = -1;
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
    if (A[i] > most) {
      ix_most = i;
      most = A[i];
    }
    if (A[i] < least) {
      ix_least = i;
      least = A[i];
    }
  }
  vector<pair<int, int>> ans;
  if (least < 0) {
    if (abs(most) >= abs(least)) {
      for (int i = 1; i < N + 1; ++i) {
        ans.push_back(make_pair(ix_most, i));
      }
      for (int i = 2; i < N + 1; ++i) {
        ans.push_back(make_pair(i - 1, i));
      }
    }
    else {
      for (int i = 1; i < N + 1; ++i) {
        ans.push_back(make_pair(ix_least, i));
      }
      for (int i = N; i > 1; --i) {
        ans.push_back(make_pair(i, i - 1));
      }
    }
  }
  else {
    for (int i = 2; i < N + 1; ++i) {
      ans.push_back(make_pair(i - 1, i));
    }
  }

  // check
  // fprintf(stderr, "DEBUG: ans.size()=%d\n", (int)ans.size());
  // for (int i = 0; i < (int)ans.size(); ++i) {
  //   int x = ans[i].first, y = ans[i].second;
  //   A[y] += A[x];
  // }
  // for (int i = 1; i < N; ++i) {
  //   assert(A[i] <= A[i + 1]);
  // }

  printf("%d\n", (int)ans.size());
  for (int i = 0; i < (int)ans.size(); ++i) {
    printf("%d %d\n", ans[i].first, ans[i].second);
  }

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#define FOR(i, l, r) for(int i = l; i <= r; ++i)

using namespace std;

typedef long long ll;
const int N = 4010;
const int mod = 1e9 + 7;

struct edge{int to, next; ll v;} e[N];
struct Edge{int u, v; ll w;} a[N];

int head[N], f[N][11], dep[N], fa[N], vis[N];
int n, m, cnt, equ, upp;
ll mx[N][11], Pow[N], X, D;

bool operator < (Edge a, Edge b) {return a.w < b.w;}

void ins(int x, int y, ll z)
{
    e[++cnt].to = y; e[cnt].next = head[x]; e[cnt].v = z; head[x] = cnt;
    e[++cnt].to = x; e[cnt].next = head[y]; e[cnt].v = z; head[y] = cnt;
    D += z;
}

void dfs(int x, int y)
{
    for(int i = 0; f[x][i]; ++i)
    {
        f[x][i + 1] = f[f[x][i]][i];
        mx[x][i + 1] = max(mx[x][i], mx[f[x][i]][i]);
    }

    for(int i = head[x]; i; i = e[i].next)
        if (e[i].to != y)
        {
            dep[e[i].to] = dep[x] + 1;
            f[e[i].to][0] = x;
            mx[e[i].to][0] = e[i].v;
            dfs(e[i].to, x);
        }
}

ll get_val(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y); ll ans = 0;

    int d = dep[x] - dep[y];
    for(int i = 10; ~i; --i) if ((1 << i) & d)
    {
        ans = max(ans, mx[x][i]);
        x = f[x][i];
    }

    for(int i = 10; ~i; --i) if (f[x][i] != f[y][i])
    {
        ans = max(ans, max(mx[x][i], mx[y][i]));
        x = f[x][i], y = f[y][i];
    }

    return x == y ? ans : max(ans, max(mx[x][0], mx[y][0]));
}

int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

int main()
{
    scanf("%d%d%lld", &n, &m, &X);
    FOR(i, 1, m) scanf("%d%d%lld", &a[i].u, &a[i].v, &a[i].w);
    Pow[0] = 1; FOR(i, 1, m) Pow[i] = Pow[i - 1] * 2 % mod;

    FOR(i, 1, n) fa[i] = i;
    sort(a + 1, a + m + 1);
    FOR(i, 1, m)
    {
        int p = find(a[i].u), q = find(a[i].v);
        if (p != q) fa[p] = q, ins(a[i].u, a[i].v, a[i].w), vis[i] = 1;
    }

    dfs(1, 0);
    FOR(i, 1, m) if (!vis[i])
    {
        ll tmp = a[i].w - get_val(a[i].u, a[i].v);
        if (tmp == X - D) ++equ;
        if (tmp > X - D) ++upp;
    }

    if (X < D) puts("0");
    if (X == D) printf("%lld\n", ((Pow[n - 1] - 2 + mod) * Pow[m - n + 1] + 2LL * (Pow[equ] - 1) * Pow[upp]) % mod);
    if (X > D) printf("%lld\n", 2LL * (Pow[equ] - 1) * Pow[upp] % mod);

    return 0;
}


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

int main(void) {
    vector<string> vec;
    string input, ans1;
    int maxLen = 0;
    while(cin >> input) {
        vec.push_back(input);
        if(input.length() > maxLen) {
            maxLen = (int)input.length();
            ans1 = input;
        }
    }
    map<int, string> hm;
    vector<string>::iterator ite;
    int max = 0;
    for(ite = vec.begin(); ite != vec.end(); ite++) {
        string now = *ite;
        int cnt = (int)count(vec.begin(), vec.end(), now);
        if(cnt > max) max = cnt;
        hm.insert(make_pair(cnt, now));
    }
    map<int, string>::iterator ite2;
    for(ite2 = hm.begin(); ite2 != hm.end(); ite2++) {
        if(ite2->first == max) {
            cout << ite2->second << " "; break;
        }
    }
    cout << ans1 << endl;
    return(0);
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
struct point{int x;int y;};
int i,j,k,count1=0,count2=0;

int main(){
    string s;
    int ans=0;
    cin>>s;
    rep(i,s.length()){
        if(s[i]=='o')ans++;
    }
    cout<<((ans+15-s.length()>=8)?"YES":"NO")<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node {
  int key;
  Node *right, *left, *parent;
};

Node *root, *NIL;

void insert(int k) {
  Node *x = root;
  Node *y = NIL;
  Node *z;
  
  z = (Node*)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
  while (x != NIL) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    }
    else {
      x = x->right;
    }
  }
  z->parent = y;
  if (y == NIL) {
    root = z;
  }
  else {
    if (z->key < y->key) {
      y->left = z;
    }
    else {
      y->right = z;
    }
  }
}

void inorder(Node *u) {
  if (u == NIL) return;
  inorder(u->left);
  cout << " " << u->key;
  inorder(u->right);
}

void preorder(Node *u) {
  if (u == NIL) return;
  cout << " " << u->key;
  preorder(u->left);
  preorder(u->right);
}

Node* find(Node *u,int k) {
  while (u != NIL && k != u->key) {
    if (k < u->key) {
      u = u->left;
    }
    else {
      u = u->right;
    }
  }
  
  return u;
}

Node* Min(Node *x){
  while(x->left != NIL) x = x->left;
  return x;
}

Node* Successor(Node *x){
  if(x->right != NIL) return Min(x->right);
  Node *y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
}

void Delete(Node *z){
  Node *y, *x;

  if(z->left == NIL || z->right == NIL) y = z;
  else y = Successor(z);

  if(y->left != NIL){
    x = y->left;
  }else{
    x = y->right;
  }

  if(x != NIL){
    x->parent = y->parent;
  }

  if(y->parent == NIL){
    root = x;
  }else{
    if(y == y->parent->left){
      y->parent->left = x;
    }else{
      y->parent->right = x;
    }
  }

  if(y != z){
    z->key = y->key;
  }


  free(y);
}


int main() {
  int n, x;
  string com;
  
  scanf("%d", &n);
  
  for (int i = 0; i < n; ++i) {
    cin >> com;
    if (com == "insert") {
      scanf("%d", &x);
      insert(x);
    }
    else if (com == "print") {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if (com == "find") {
      scanf("%d", &x);
      Node *t = find(root, x);
      if (t != NIL) {
	printf("yes\n");
      }
      else {
	printf("no\n");
      }
    }else if(com == "delete"){
      scanf("%d",&x);
      Delete(find(root, x));
    }
  }
  
  
  return 0;
}





Measured memory_bytes: 22016
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vll = V<ll>;
using VVll = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Msi = M<string, int>;

const ll MOD = 1e9+7;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()


int main() {
    int n, q;
    cin >> n >> q;
    VVi adj(n+1);
    Vi cnt(n+1, 0);
    REP(i, n-1) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    REP(i, q) {
        int p, x;
        cin >> p >> x;
        cnt[p] += x;
    }

    Vi res(n+1, 0);
    res[1] = cnt[1];
    stack<Pii> s;
    s.push(make_pair(1, -1));
    while (!s.empty()) {
        int v = s.top().first;
        int u = s.top().second;
        s.pop();

        FOR(i, adj[v]) {
            if (*i == u) continue;
            cnt[*i] += cnt[v];
            res[*i] = cnt[*i];
            s.push(make_pair(*i, v));
        }
    }

    REP2(i, 1, n+1) {
        std::cout << res[i] << ' ';
    }
    std::cout << '\n';

    return 0;
}


Measured memory_bytes: 17140
#include<bits/stdc++.h>
#define loop(i,a,b) for(i=a;i<b;i++)
using namespace std;


 
int main(){
	int n,k,i,j;
	cin>>n>>k;
	int m=0,sum=0;
	vector<int> w(n);
	loop(i,0,n){
		cin>>w[i];
		m=max(m,w[i]);
		sum+=w[i];
	}
	int left=m,right=sum,cnt;
	int p=(left+right)/2;
	while(left+1<right){
		cnt=1;
		sum=0;
		loop(i,0,n){
			sum+=w[i];
			if(sum>p){
				cnt++;
				sum=w[i];
				if(cnt>k){
					left=p;
					break;
				}
			}
		}
		if(cnt<=k){
			right=p;
		}
		p=(left+right)/2;
	}
	cnt=1;sum=0;
	loop(i,0,n){
		sum+=w[i];
		if(sum>p){
			cnt++;
			sum=w[i];
		}
	}
	if(cnt<=k){
		cout<<p<<endl;
	}else{
		cout<<p+1<<endl;
	}
}

Measured memory_bytes: 3104
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;

vector<bool> valid;
struct uf {
private:
	vector<int> par, ran;
public:
	uf(int n) {
		par.resize(n, 0);
		ran.resize(n, 0);
		valid.resize(n, true);
		rep(i, n) {
			par[i] = i;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (ran[x] < ran[y]) {
			par[x] = y;
			if (!valid[x])valid[y] = false;
		}
		else {
			par[y] = x;
			if (ran[x] == ran[y])ran[x]++;
			if (!valid[y])valid[x] = false;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

void solve() {
	int n, h, w; cin >> n >> h >> w;
	vector<int> a(n), x(n), y(n);
	uf u(h + w);
	vector<pair<int, P>> v;
	rep(i, n) {
		cin >> x[i] >> y[i] >> a[i];
		x[i]--; y[i]--;
		v.push_back({ a[i],{x[i],y[i]} });
	}
	sort(v.begin(), v.end(), greater<pair<int, P>>());
	ll ans = 0;
	vector<bool> used(n, false);
	rep(i, v.size()) {
		int l = v[i].second.first;
		int r = v[i].second.second;
		r += h;
		if (u.same(l, r)) {
			int p = u.find(l);
			if (valid[p]) {
				ans += v[i].first;
				valid[p] = false;
			}
		}
		else {
			int pl = u.find(l);
			int pr = u.find(r);
			if (!valid[pl] && !valid[pr])continue;
			u.unite(l, r);
			ans += v[i].first;
		}
	}
	cout << ans << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(5);
	//init();
	solve();

	//cout << "finish" << endl;
	//stop
	return 0;
}

Measured memory_bytes: 4856
#include<iostream>
using namespace std;
int main(void){
    for(;;){
    char a[3][3];
    int f=0,z=0;
    for (int i=0;i<3;i++){
        cin>>a[i];
        if(a[i][0]=='0'){
            z++;
            break;
        }
        }
        if(z!=0)break;

    for(int i=0;i<1;i++){
        for(int j=0;j<3;j++){
            if(a[i][j]!='+'){
                if(a[0][j]==a[1][j]&&a[1][j]==a[2][j]){
                    cout<<a[0][j]<<endl;
                    f++;
                    goto c;
                }
            }
        }
    }
    for(int j=0;j<1;j++){
        for(int i=0;i<3;i++){
            if(a[i][j]!='+'){
                if(a[i][0]==a[i][1]&&a[i][1]==a[i][2]){
                    cout<<a[i][0]<<endl;
                    f++;
                    goto c;
                }
            }
        }
    }
    if(a[0][0]!='+'){
        if(a[0][0]==a[1][1]&&a[1][1]==a[2][2]){
            cout<<a[0][0]<<endl;
            f++;
            goto c;
        }

    }
    if(a[0][2]!='+'){
        if(a[0][2]==a[1][1]&&a[1][1]==a[2][0]){
            cout<<a[0][2]<<endl;
            f++;
            goto c;
        }
    }

    if(f==0)cout<<"NA"<<endl;
    c:;


    }
    return 0;
}

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn=3e5+5;
ll a[mxn];

void multi(ll &a, ll b){
	a%=MOD; b%=MOD; a*=b; a%=MOD;
	return;
}
void add(ll &a, ll b){
	a%=MOD; b%=MOD; a+=b; a%=MOD;
	return;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	map<int,ii>mp;
	for(int i=0; i<n; i++){
		cin >> a[i];
		for(int j=59; j>=0; j--){
			if(a[i]&(1LL<<j))mp[j].se++;
			else mp[j].fi++;
		}
	}
	ll ans = 0;
	for(int j=59; j>=0; j--){
		ll cur = (1LL<<j)%MOD;
		multi(cur,ll(mp[j].fi)*ll(mp[j].se)%MOD);
		add(ans,cur);
	}
	cout << ans << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 2560