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

const int N = 100005;
const int mod = 1e9 + 7;

int mul(int x,int y) {
	return (long long) x * y % mod;
}

int n;
vector<int> g[N];
int f[N][2];

void dfs(int u,int p) {
	f[u][0] = f[u][1] = 1;
	for (int v : g[u]) if (v != p) {
		dfs(v, u);
		f[u][0] = mul(f[u][0], f[v][0] + f[v][1]);
		f[u][1] = mul(f[u][1], f[v][0]);
	}
} 

int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; ++i) {
		int u, v; 
		scanf("%d %d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	dfs(1, -1);
	printf("%d\n", (f[1][0] + f[1][1]) % mod);
}

Measured memory_bytes: 13440
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int vis[5];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<5;i++){
        vis[i]=-1;
    } 
    int s,c;
    int flag=0;
    while(m--){
        cin>>s>>c;
        if(vis[s]==-1||vis[s]==c)
        vis[s]=c;
        else{
            flag=1;
        }
    }
    if(vis[1]==0&&n>1){
        flag=1;
    }
    for(int i=1;i<=n;i++){
        if(n==1&&vis[1]==-1){
            cout<<0<<endl;
            return 0;
        }
        if(vis[i]==-1){
            if(i==1){
                vis[1]=1;
            }
            else{
                vis[i]=0;
            }

        }
    }
    if(flag==1){
        puts("-1");
    }
    else{
        for(int i=1;i<=n;i++){
            cout<<vis[i];
        }
    }
    return 0;
}

Measured memory_bytes: 888
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;
int main()
{
    int N, i, k;
    cin >> N;
    int buka[N];
    for (i = 0; i < N; i++)
    {
        buka[i] = 0;
    }
    for (i = 0; i < (N - 1); i++)
    {
        cin >> k;
        buka[k - 1]++;
    }
    for (i = 0; i < N; i++)
    {
        cout << buka[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 4416
(let* ((n (read)))
  (cond ((<= 1 n 9) (princ n))
        ((<= 10 n 99) (princ 9))
        ((<= 100 n 999) (princ (+ 9 (- n 99))))
        ((<= 1000 n 9999) (princ 909))
        ((<= 10000 n 99999) (princ (+ 909 (- n 9999))))
        (t (princ 90909))))

Measured memory_bytes: 11744
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
int main()
{
    string s;
    cin >> s;

    string str = "keyence";
    bool check[7] = {false,false,false,false,false,false,false};
    int start = 0;
    int end = str.length() - 1;

    rep(i, s.length()){
        if(s[i] == str[start]){
            check[start] = true;
            start++;
        }
        else{
            break;
        }
    }
    for(int i=s.length()-1; i>=0; i--){
        if(s[i] == str[end]){
            check[end] = true;
            end--;
        }
        else{
            break;
        }
    }

    rep(i, 7){
        if(!check[i]){
            cout << "NO";
            return 0;
        }
    }

    cout << "YES";

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        for(int i=1; ; i++){
            int x = sc.nextInt();
            if(x==0){
                break;
            }
            System.out.printf("Case %d: %d\n",i,x);
        }
 
    }
 
}


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

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

    string n;
    cin >> n;

    rep(i, n.length()){
        cout << 10 - (n[i] - '0');
    }
    cout << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		int c=scan.nextInt();
if(a==b) {
	System.out.println(c);
}
else if(b==c){
	System.out.println(a);
}
else {
	System.out.println(b);
}
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    string s;
    cin>>s;
    vector<int> dp(2019, 0);
    dp[s[0] - '0'] += 1;
    ll ans = 0;
    for(ll i=1; i<s.size(); i++)
    {
        ll d  = s[i] - '0';
        vector<int> t(2019, 0);
        t[d] += 1;
        for(ll j=0; j<2019; j++)
        {
            ll r = (10*j + d)%2019;
            t[r] += dp[j];
            if(r == 0)
            {
                ans = ans + dp[j];
            }
        }
        for(int j=0; j<2019; j++)
        {
            dp[j] = t[j];
        }
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 3712
#include <iostream>
#include <string>
#include <vector>
std::string  S,Ans;
int S_length;
 
int main(void){
    std::cin >> S;

    S_length = S.length();

    for(int i = 0;i < S_length;i++){
        std::cout << "x";
    }
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
q = 1000000007

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cnt += 1
            continue
        else:
            cost[i] = cost[i - 1] + cost[i - 2]

    print(cost[-1] % q)


Measured memory_bytes: 460056
a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if 500 * i + 100 * j + 50 * k == x:
                ans += 1

print(ans)


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

int main(){
    int i,max=0,slen;
    char s[20], str[10];
    int ans=0;
    
    scanf("%s", &s);
    slen = strlen(s);

    for(i=0; i<slen; i++){
        if(s[i] == 'A'){
            ans += 1;
        }else if( s[i] == 'C' ){
            ans += 1;
        }else if(s[i] == 'G'){
            ans += 1;
        }else if(s[i] == 'T'){
            ans += 1;
        }else{
            ans = 0;
        }
        if(max<ans){
            max = ans;
        }
    }

    printf("%d", max);
    return 0;

}

Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define mod 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=2050;
//↑templete
int main() {
	ll N,K;
	cin>>N>>K;
	vint A;
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		A.eb(a);
	}
	ll bef[SIZE]={}, aft[SIZE]={};	//自分より大きい数
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(j<i && A[i]<A[j])
				bef[i]++;
			if(i<j && A[i]<A[j])
				aft[i]++;
		}
	}
	ll ans=0;
	for(int i=0;i<N;i++){
		ll k=K;
		ll M=(k*(k+1)/2)%MOD;
		ans+=bef[i]*M%MOD;
		ans%=MOD;
		ll L=(k*(k-1)/2)%MOD;
		ans+=aft[i]*L%MOD;
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace AOJ.Volume1
{
    public class PocketPagerInput
    {
        public static void Main()
        {
            var dic = new Dictionary<string, string>
            {
                {"11", "a"}, {"12", "b"}, {"13", "c"}, {"14", "d"}, {"15", "e"},
                {"21", "f"}, {"22", "g"}, {"23", "h"}, {"24", "i"}, {"25", "j"},
                {"31", "k"}, {"32", "l"}, {"33", "m"}, {"34", "n"}, {"35", "o"},
                {"41", "p"}, {"42", "q"}, {"43", "r"}, {"44", "s"}, {"45", "t"},
                {"51", "u"}, {"52", "v"}, {"53", "w"}, {"54", "x"}, {"55", "y"},
                {"61", "z"}, {"62", "."}, {"63", "?"}, {"64", "!"}, {"65", " "}
            };
            while (true)
            {
                string input = Console.ReadLine();
                if (string.IsNullOrEmpty(input)) { break; }

                string answer = "";

                // 文字数が偶数でない場合は変換できない
                if (input.Length % 2 != 0)
                {
                    Console.WriteLine("NA");
                    continue;
                }

                // 使用している文字が正しいか
                var check = input.ToCharArray();
                int cnt = 1;
                bool enable = true;
                foreach (var c in check)
                {
                    // 奇数番目の文字は"1"?"6"
                    // 偶数番目の文字は"1"?"5"
                    char to_char = cnt % 2 == 0 ? '5' : '6';
                    if (c < '1' || c > to_char)
                    {
                        enable = false;
                        break;
                    }
                    cnt++;
                }
                if (!enable)
                {
                    Console.WriteLine("NA");
                    continue;
                }

                for (int i = 0; i < input.Length; i = i + 2)
                {
                    answer += dic[input.Substring(i, 2)];
                }

                Console.WriteLine(answer);
            }
        }
    }
}

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

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

    //good luck kittu!
    ll a, b, n, t1, t2; cin>>a>>b>>n;
    ll x = min(b-1, n);
    t1 = (a*x)/b;
    t2 = x/b;
    t2 *= a;
    cout<<t1-t2<<"\n";
    return 0;
}

Measured memory_bytes: 3648
A,B,C,D,E,F=map(int,input().split())
best_water=0
best_salt=0
best_rate=0
for i in range(30//A+1):#Aの投入数
  for j in range(30//B+1):#Bの投入数
    water=(i*A+j*B)*100
    if water<=F and water:
      max_salt=min(F-(i*A+j*B)*100,(i*A+j*B)*E)
      for k in range(max_salt//C+1):#Cを何個使うか
        l=(max_salt-C*k)//D#Dは何個つかえるか
        salt=k*C+l*D
        rate=100*salt/(water+salt)
        if rate>=best_rate and rate<=E and water+salt<=F:
          best_rate=rate
          best_salt=salt
          best_water=water
print(best_water+best_salt,best_salt)

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

using namespace std;

#define fori(x) for (int i = 0; i < x; ++i)
#define forj(x) for (int j = 0; j < x; ++j)

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << ((a - b - c >= 0) ? 0 : c - (a - b));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    ll ans = 1;
    rep(i, n) {
        if (i == 0) {
            ans *= k;
        } else {
            ans *= (k-1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
/**
 * Created by hiramekun at 20:50 on 2020-04-04.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll x, y, z;
    cin >> x >> y >> z;
    cout << z << ' ' << x << ' ' << y << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

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

using namespace std;

int main() {
	int x, y, s;
	while (cin >> x >> y >> s) {
		if (x == 0 && y == 0 && s == 0) {
			break;
		}
		int k, p;
		int kk, pp;
		int a, b;
		int MAX = 0;
		for (int i = 1; i < s; i++) {
			bool hantei = true;
			bool hantei2 = true;
			k = (double)i * (double)(100 + x) / 100.0;
			kk = k;
			k = s - k;
			if (k <= 0) {
				break;
			}
			p = (double)k * 100.0 / (double)(100 + x);
			pp = (double)p * (double)(100 + x) / 100.0;
			if (kk + pp == s) {
				hantei = false;
			}
			pp = (double)(p+1) * (double)(100 + x) / 100.0;
			if (kk + pp == s) {
				hantei2 = false;
				p++;
			}
			if (hantei && hantei2) {
				continue;
			}
			a = (double)i * (double)(100 + y) / 100.0;
			b = (double)p * (double)(100 + y) / 100.0;
			MAX = max(MAX, a+b);
		}
		cout << MAX << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
N = int(input())
A = list(map(int, input().split()))
import numpy as np
mod = 10**9+7
ans = 0
A = np.array(A)
for i in range(60):
  one = np.count_nonzero(A>>i&1)
  zero = N - one
  ans += one*zero*pow(2,i)
  ans %= mod
  #print(one,zero)

print(ans)

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

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int N = Integer.parseInt(sc.next());
	static int W = Integer.parseInt(sc.next());
	static final int INF = Integer.MAX_VALUE;
	static int V = N*1000;
	static int[] w = new int[N];
	static int[] v = new int[N];
	static long[][] dp = new long[N+1][V+1];
	public static void main(String[] args) {
		for (int i = 0; i < N; i++) {
			w[i] = Integer.parseInt(sc.next());
			v[i] = Integer.parseInt(sc.next());
		}
		Arrays.stream(dp).parallel().forEach(i -> Arrays.fill(i, INF));
		dp[0][0] = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < V+1; j++) {
				if (j - v[i]>=0) {
					dp[i+1][j] = Math.min(dp[i][j], dp[i][j-v[i]]+w[i]);
				} else {
					dp[i+1][j] = dp[i][j];
				}
			}
		}
		int ans = -1;
		for (int j = 0; j < V+1; j++) {
			if (dp[N][j]<=W) {
				ans = j;
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 131156
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (unsigned long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (unsigned long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl

// gcc拡張マクロ
#define gcd __gcd
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    int n, q;
    string s;
    cin >> n >> q;
    cin >> s;

    vector<int> l(n), r(n);
    REP(i, q) cin >> l[i] >> r[i];

    vector<ll> ac(n, 0);
    vector<ll> imos(n+1, 0);
    REP(i, n-1) if (s[i] == 'A' && s[i+1] == 'C') ac[i] = 1;
    REP(i, n) imos[i+1] = imos[i] + ac[i];

    REP(i, q) {
        ll ans = imos[r[i]] - imos[l[i]-1];
        if (r[i] != n && s[r[i]-1] == 'A' && s[r[i]] == 'C') ans--;
        cout << ans << endl;
    }
    
}

Measured memory_bytes: 3456
Sa, Sb, Sc = [input() for i in range(3)]

turn = "a"
ia, ib, ic = 0, 0, 0



while True:
  if turn == "a":
    if ia == len(Sa):
      print("A")
      break
    else:
      turn = Sa[ia]
      ia += 1
  if turn == "b":
    if ib == len(Sb):
      print("B")
      break
    else:
      turn = Sb[ib]
      ib += 1
  if turn == "c":
    if ic == len(Sc):
      print("C")
      break
    else:
      turn = Sc[ic]
      ic += 1

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#define fi first
#define se second
#define pb(i) push_back(i)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define mes(a,b) memset(a,b,sizeof(a))
#define sbs(i,j) substr(i,j)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
const int inf = - INF;
const int mod = 1e9+7;
const double pi = acos(-1.0);

ll ans[N];
int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    rep(i,2,n){
        int t=i;
        rep(j,2,t){
            while(t%j==0){
                ans[j]++;
                t/=j;
            }
        }
        if(t!=1) ans[t]++;
    }
    ll sum=1;
    rep(i,1,n)
        if(ans[i]!=0) sum=(sum*(ans[i]+1))%mod;
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
 
 
int main(){
    string S; cin >> S;
    string temp = "ACGT";
    ll ans = 0;
    ll cnt = 0;
    int i = 0;
    while(i < S.size()){
        if(temp.find(S[i]) == string::npos) cnt = 0;
        else cnt++;
        ans = max(ans, cnt);
        i++;
    }
    cout << ans << endl;



}

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

typedef long long int ll;
typedef unsigned long long int ull;

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

using namespace std;

int main()
{
  int r, g, b, n;
  cin >> r >> g >> b >> n;

  int c = 0;

  REP(i, (n / r) + 1)
  {
    REP(j, (n / g) + 1)
    {
      if ((n - r * i - g * j) % b == 0 && n - r * i - g * j >= 0)
      {
        c++;
      }
    }
  }

  cout << c << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <regex>
#ifdef _DEBUG
#include "debug.h"
#endif
#define int ll
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define mkpr make_pair
#define mktp make_tuple
#define tv(tp, i) get<(i)>(tp)
#define CLEAR(obj) obj = decltype(obj)()
#define var auto
#define OUT(type) type &
#define IN(type) const type &
#define self (*this)
#define in :
#define True true
#define False false
using namespace std; using str = string; using cstr = const str;
using ll = long long; using ull = unsigned long long; using cint = const int; using cll = const ll;
using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>;
using vb = vector<bool>; using vvb = vector<vb>; using vd = vector<double>; using vvd = vector<vd>;
using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<double, double>; using psl = pair<string, ll>;
using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;
static const int MGN = 10; static const int ARYSZ_MAX = (int)1e7;
static const ll LINF = LLONG_MAX/2;
#ifdef int
static const int INF = LINF;
#else
static const int INF = INT_MAX/2;
#endif
static double EPS = 1e-9;
static inline bool DBLEQ(double a, double b) {return abs(a - b) < EPS;}
static inline void EPR(str msg) {cerr << msg << endl;}
static inline void AST(bool exp, str msg) {if(!exp){EPR(msg);} assert(exp);}
static inline void TAST(bool exp, str msg) {if(!exp){EPR(msg);} while(!exp){}}


int32_t main(int32_t argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef _DEBUG
    vs args(argv, argv+argc);
    string sample = make_sample(args, 7);
    ifstream ifs(sample); cin.rdbuf(ifs.rdbuf());
#endif


    int N, K; cin>>N>>K;

    int x = N;
    if (abs(x-K) >= x) {
        cout << x << endl;
        return 0;
    }

    x %= K;
    if (x == 0 or abs(x - K) == 0) {
        cout << 0 << endl;
        return 0;
    }

    while (True) {
        if (abs(x-K) >= x) break;
        x = abs(x-K);
    }

    int ans = x;
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int users;
int games;
int targets[100];
int answers[100][100];

int main(void) {
	cin >> users;
	cin >> games;
	for (int i = 0; i < games; i++) {
		cin >> targets[i];
		targets[i]--;
	}
	for (int i = 0; i < games; i++) {
		for (int j = 0; j < users; j++) {
			cin >> answers[i][j];
			answers[i][j]--;
		}
	}
	
	
	
	for (int i = 0; i < users; i++) {
		int score = 0;
		for (int j = 0; j < games; j++) {
			if (answers[j][i] == targets[j]) {
				score++;
				if (targets[j] == i) {
					for (int k = 0; k < users; k++) {
						if (answers[j][k] != i) score++;
					}
				}
			}
			//cout << score << " ";
		}
		cout << score << endl;
	}
}

Measured memory_bytes: 1200
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

int H, A[500001];

void maxHeapify(int i) {
	int l = 2 * i,
		r = 2 * i + 1;

	int largest = i;
	if (l <= H&&A[l] > A[i])largest = l;
	if (r <= H&&A[r] > A[largest])largest = r;

	if (largest != i) {
		swap(A[i], A[largest]);
		maxHeapify(largest);
	}
}

int main() {
	cin >> H;
	for (int i = 1; i <= H; i++) {
		cin >> A[i];
	}
	for (int i = H / 2; i >= 1; i--) {
		maxHeapify(i);
	}
	for (int i = 1; i <= H; i++) {
		cout << " " << A[i];
	}
	cout << endl;

	return 0;
}

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

using namespace std;

int n,i,j,a[200005];

int main(){
	scanf("%d", &n);
	
	long long tot = 0;
	
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
		tot += a[i];
	}
	
	long long res = 1e18;
	long long cur = 0;
	
	for(i = 0; i < n - 1; i++){
		cur += a[i];
		res = min(res, abs((tot - cur) - cur));
	}
	
	printf("%lld\n", res);
}


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


int main(){
    string n;
    cin >>n;
    for(int i=0;i<n.size();i++){
        if(n[i]=='1') n[i]='9';
        else n[i]='1';
    }
    cout << n << endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int read() {
	int x; scanf("%d", &x); return x;	
}
const int maxn = 1e6 + 10;
const int INF = 1e9;
int mod = 1e9 + 7;
#define ll long long 
int n;
int a[1000];
int main() {
	#ifdef LOCAL
		freopen("1.in", "r", stdin);
	#endif
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	int ans = 0;
	for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) for (int k = j + 1; k <= n; ++k) {
		if (a[i] == a[j] || a[i] == a[k] || a[j] == a[k]) continue;
		vector<int>t; t.clear();
		t.push_back(a[i]);	t.push_back(a[j]);	t.push_back(a[k]);
		sort(t.begin(), t.end());
		if (t[0] + t[1] > t[2]) {
			ans++;
	//		cout << t[0] << ' ' << t[1] << ' ' << t[2] << endl;
	//		cout << i << ' ' << j << ' ' << k << endl;
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main() {
  int N; cin >> N;
  int a[N];

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

  sort(a,a + N);

  int alice = 0, bob = 0;
  for (int i = 1; i < N+1; i++) {
    if(i % 2 == 1) alice += a[N-i];
    else bob += a[N-i];
  }

  cout << alice - bob << endl;
}



Measured memory_bytes: 256
from collections import deque

# N, W = 3, 5
# ARR = [
#     ['.', '.', '.', '#', '.'],
#     ['.', '#', '.', '#', '.'],
#     ['.', '#', '.', '.', '.']
# ]

N, W, = 3, 3
ARR = [
    ['.', '.', '.'],
    ['.', '.', '.'],
    ['.', '.', '.'],
]

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

ARR = []

for i in range(N):
    ARR.append(list(map(str, input())))


def dfs(start, n, w, arr):
    d = deque()
    d.append(start)

    states = [[0 for j in range(w)] for i in range(n)]

    maxDistance = start[2]
    while len(d) > 0:
        coordinate = d.popleft()
        coorY = coordinate[0]
        coorX = coordinate[1]
        distance = coordinate[2]
        if states[coorY][coorX] == 1:
            continue
        maxDistance = max(distance, maxDistance)

        states[coorY][coorX] = 1
        leftX, leftY = coorX - 1, coorY
        rightX, rightY = coorX + 1, coorY
        topX, topY = coorX, coorY - 1
        bottomX, bottomY = coorX, coorY + 1

        if leftX >= 0 and leftY >= 0:
            if arr[leftY][leftX] == ".":
                d.append([leftY, leftX, distance + 1])

        if rightX <= w - 1 and rightY <= n - 1:
            if arr[rightY][rightX] == ".":
                d.append([rightY, rightX, distance + 1])

        if topY >= 0:
            if arr[topY][topX] == ".":
                d.append([topY, topX, distance + 1])

        if bottomY <= n - 1:
            if arr[bottomY][bottomX] == ".":
                d.append([bottomY, bottomX, distance + 1])

    return maxDistance


def calculate(n, w, arr):
    distances = []

    for i in range(n):
        for j in range(w):
            if arr[i][j] == ".":
                distance = dfs([i, j, 0], n, w, arr)
                distances.append(distance)

    maxDistance = max(distances)
    print(maxDistance)


# dfs([0, 0, 0], N, W, ARR)

calculate(N, W, ARR)


Measured memory_bytes: 3316
from sys import stdin
s = stdin.readline().rstrip()
bef = s[:2]
aft = s[2:]

if bef == '00':
    if aft == '00':
        print('NA')
    elif int(aft) > 0 and int(aft) < 13:
        print('YYMM')
    else:
        print('NA')
elif int(bef) > 0 and int(bef) < 13:
    if aft == '00':
        print('MMYY')
    elif int(aft) > 0 and int(aft) < 13:
        print('AMBIGUOUS')
    else:
        print('MMYY')
else:
    if aft == '00':
        print('NA')
    elif int(aft) > 0 and int(aft) < 13:
        print('YYMM')
    else:
        print('NA')



Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

int main()
{
    ll i,j,n,m;
    cin>>n;
    vector<ll> a(n);
    for(i=0;i<n;i++) cin>>a[i];
    map<ll,bool> mp;
    for(i=0;i<n;i++)
    {
    	ll cur = a[i];
    	ll pr = 0;
    	while(cur%2==0)
    	{
    		cur/=2;
			pr = 1;
    	}
    	if(pr==1) 
    	{
    		if(mp.find(2)==mp.end())
    		{
    			mp[2]=1;
    		}
    		else
    		{
    			ll gcd = 0;
		    	for(ll k=0;k<n;k++) gcd = __gcd(gcd,a[k]);
		    	if(gcd==1) cout<<"setwise coprime\n";
		    	else cout<<"not coprime\n";
		    	return 0;
    		}
    	}
    	for(j=3;j*j<=cur;j+=2)
    	{
    		ll pr = 0;
    		while(cur%j==0)
    		{
    			cur/=j;
    			pr = 1;
    		}
	    	if(pr==1) 
	    	{
	    		if(mp.find(j)==mp.end())
	    		{
	    			mp[j]=1;
	    		}
	    		else
	    		{
	    			ll gcd = 0;
			    	for(ll k=0;k<n;k++) gcd = __gcd(gcd,a[k]);
			    	if(gcd==1) cout<<"setwise coprime\n";
			    	else cout<<"not coprime\n";
			    	return 0;
	    		}
    		}
    	}
    	if(cur!=1)
    	{
    		if(mp.find(cur)==mp.end()) mp[cur] = 1;
    		else
    		{
    				ll gcd = 0;
			    	for(ll k=0;k<n;k++) gcd = __gcd(gcd,a[k]);
			    	if(gcd==1) cout<<"setwise coprime\n";
			    	else cout<<"not coprime\n";
			    	return 0;	
    		}
    	}
    }
	cout<<"pairwise coprime\n";
}

Measured memory_bytes: 11120
N = int(input())

if N == 1:
    print(0)
    exit()


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


count = 0

arr = factorization(N)

for a in arr:
    now = a[0]
    now_z = a[0]
    while True:
        if N % now_z == 0:
            count += 1
            N //= now_z
            now_z *= now
        else:
            break
print(count)

Measured memory_bytes: 9496
// Problem : A - Study Scheduling
// Contest : AtCoder - NOMURA Programming Competition 2020
// URL : https://atcoder.jp/contests/nomura2020/tasks/nomura2020_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

#define Fast            ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define fWrite          freopen ("out.txt","w",stdout);
#define TC              int t;cin >> t;FOR(tc,1,t)
#define LL              long long
#define ULL             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define all(a)          a.begin(),a.end()
#define MEM(a,x)        memset(a,x,sizeof(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)

int main()
{
    Fast
    int h1,m1,h2,m2,k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int s = h1*60+m1;
    int e = h2*60+m2;
    int diff = e-s;
    cout << diff-k;
}


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

void print_vec(vector<int> vec) {
  cout << "[";
  for (int i = 0; i < vec.size(); i++) {
    if (i) {
      cout << ", ";
    }
    cout << vec.at(i);
  }
  cout << "]...size: " << vec.size() << endl;
}

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

  vector<vector<int>> vec_a(n, vector<int>(m));
  vector<int> vec_b(m);
  vector<int> vec_c(n, 0);

  rep(i, n) {
    rep(j, m) { cin >> vec_a.at(i).at(j); }
  }

  rep(i, m) { cin >> vec_b.at(i); }

  rep(i, n) {
    rep(j, m) { vec_c.at(i) += vec_a.at(i).at(j) * vec_b.at(j); }
  }

  for (auto &&i : vec_c) {
    printf("%d\n", i);
  }
}



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

int main(){
    int n, m, c;
    cin >> n >> m >> c;
    int b[m];
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    int count = 0;
    for(int i = 0; i < n; i++){
        int buf = c;
        for(int j = 0; j < m; j++) {
            int a;
            cin >> a;
            buf += a * b[j];
        }
        if(buf > 0){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

#define BR "\n"
#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a, b) ((((a) % (b) ) + (b)) % (b))
#define FEACH(it, cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it, cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define is insert
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define MAX(V, T) V=max(V,T)

#define DumpArray(cont, from, to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i]<<")";} cout<<endl;

/*
 * ***_bound(6)
 * 5 6 6 6 6 6 7 7 7
 *   ^lower    ^upper
 * void reverse(c.begin(), c.end())
 *
 * graph
 * seg tree
 * dp
 * brute force
 */
struct Comparator{
    int operator()(int l, int r) const {
        return r<l;
    }
};
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<char> vc;
typedef vector<vector<char>> vv;
//set<int, Comparator> S;
int main() {
    int N;
    string S;
    cin >> N >> S;
    int ans=0;
    for(int i=0;i<N-2;++i) {
        if (S[i]=='A' &&S[i+1]=='B'&&S[i+2]=='C')ans++;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,N,j) for(int i = (N-1);i >= (j);i--)
#define _rec(i,N,j) for(int i = (N);i >=(j);i--)
#define ALL(x) x.begin(),x.end()
#define MEM(a,n) memset(a,n,sizeof(a))
#define fst first
#define scd second
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

int get_int(){int x;scanf("%d",&x);return x;}
LL get_ll(){LL x;scanf("%lld",&x);return x;}
double get_db(){double x;scanf("%lf",&x);return x;}

template<typename T> int chmin(T &a,T b){if(a > b){a = b;return 1;}else return 0;}
template<typename T> int chmax(T &a,T b){if(a < b){a = b;return 1;}else return 0;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {_for(i,0,v.size()) os << v[i] << " ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){for(auto a:v) os << a <<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){os << v.fst <<" "<<v.scd << " ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& v){for(auto a:v) cout << a << endl;return os;}

static const int dx[8] = { 1,  0, -1,  0,  1, -1,  1, -1};
static const int dy[8] = { 0,  1,  0, -1,  1, -1, -1,  1};
const double pi  = acos(-1.0);
const double eps = 1e-8;
const LL  INF  = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;
const int mod = 1e9+7;


const int maxn = 1e5+5;
const int maxnn = 2e5+10;

int connect[maxnn];
int vis[maxnn];
vector<int> G[maxnn];
int N;
int e = 0;
LL numx,numy;

int gy(int y){return maxn + y;}

void dfs(int i,int c){
    connect[i] = c;
    if(i < maxn) ++numx;
    else ++numy;
    for(auto a:G[i]){
        ++e;
        if(connect[a] == -1){
            dfs(a,c);
        }
    }
}

int main()
{
    int cnt  = 0;
    scanf("%d",&N);
    MEM(connect,-1);
    _for(i,0,N){
        int x,y;
        scanf("%d %d",&x,&y);
        G[x].PB(gy(y));
        G[gy(y)].PB(x);
        vis[gy(y)] = 1;
        vis[x] = 1;
    }

    LL ans = 0;

    _for(i,0,maxnn){
        if(vis[i] && connect[i] == -1){
            numx = 0;numy = 0;e = 0;
            dfs(i,cnt++);
            if(numx + numy >= 3){
                ans += numx * numy - e/2;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 11520
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iterator>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
 
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))
 
typedef long long ll;

using namespace std;
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  int n,k;
  cin>>n>>k;
  
  vector<ll> h(n);
  
  rep(i,n) {
    cin>>h[i];
  }
  
  sort(all(h));
  
  if (n<=k) {
    cout<<0<<endl;
  } else {
    ll ans=0;
    rep(i, n-k) {
      ans += h[i];
    }
    
    cout<<ans<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int cnt[100001], chk[100001], N, M;
int main()
{
    scanf("%d %d", &N, &M);
    chk[1] = 1;
    for(int i = 1; i <= N; i++) cnt[i] = 1;
    for(int i = 1; i <= M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        if(cnt[a] > 1 && chk[a] == 1)
        {
            chk[b] = 1;
            cnt[a]--;
            cnt[b]++;
        }
        else if(cnt[a] == 1 && chk[a] == 1)
        {
            chk[b] = 1;
            chk[a] = 0;
            cnt[a]--;
            cnt[b]++;
        }
        else if(chk[a] == 0)
        {
            cnt[a]--;
            cnt[b]++;
        }
    }
    int ANS = 0;
    for(int i = 1; i <= N; i++)
    {
        if(chk[i] == 1) ANS++;
    }
    printf("%d", ANS);
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[6] = {1, 0, -1, 0,1,1};
const int dy[6] = {0, 1, 0, -1,1,-1};
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; }
// ---------------------------------------------------------------------------


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    cout << fixed << setprecision(10) << PI*double(N*2) << enld;


    return 0;
}

Measured memory_bytes: 3804
N=int(input())
d={}
ans=[]
num=0
for x in range(N):
  S=input()
  if S not in d:
    d[S]=1
  else:
    d[S] += 1
  if d[S]>num:
    num=d[S]
    ans=[]
    ans.append(S)
  elif d[S]==num:
    ans.append(S)
ans.sort()
for i in range(len(ans)):
  print(ans[i])
    


Measured memory_bytes: 36620
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=a;i--)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define de(x) cout << #x << "=" << x << endl
#define dd(x) cout << #x << "=" << x << " "
#define pw(x) (1ll<<(x))
#define pq priority_queue
#define endl "\n"
int main()
{
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
    	if(s[i]!='?') cout<< s[i];
    	else cout <<"D";
	}
    return 0;
}


Measured memory_bytes: 3788
#include <memory>
#include <utility>

template <class Key, class T> class splay_associative_array {
public:
	using key_type = Key;
	using value_type = T;
	using reference = value_type &;

private:
	class node_type {
	public:
		typename splay_associative_array::key_type key;
		typename splay_associative_array::value_type value;
		::std::unique_ptr<node_type> left, right;
		node_type(const key_type &key) : key(key), value(), left(), right() {}
	};
	using pointer = ::std::unique_ptr<node_type>;

	pointer root;

public:
	splay_associative_array() : root() {}

	reference operator[](const key_type &key) {
		pointer left, right;
		pointer *next_l = &left, *next_r = &right;
		while (1) {
			if (!root)
				root = ::std::make_unique<node_type>(key);
			if (!(root->key <= key)) {
				if (!root->left)
					root->left = ::std::make_unique<node_type>(key);
				if (!(root->left->key <= key)) {
					*next_r = ::std::move(root->left);
					root->left = ::std::move((*next_r)->right);
					(*next_r)->right = ::std::move(root);
					next_r = &(*next_r)->left;
					root = ::std::move(*next_r);
				}
				else if (!(key <= root->left->key)) {
					*next_r = ::std::move(root);
					next_r = &(*next_r)->left;
					*next_l = ::std::move(*next_r);
					next_l = &(*next_l)->right;
					root = ::std::move(*next_l);
				}
				else {
					*next_r = ::std::move(root);
					next_r = &(*next_r)->left;
					root = ::std::move(*next_r);
				}
			}
			else if (!(key <= root->key)) {
				if (!root->right)
					root->right = ::std::make_unique<node_type>(key);
				if (!(root->right->key <= key)) {
					*next_l = ::std::move(root);
					next_l = &(*next_l)->right;
					*next_r = ::std::move(*next_l);
					next_r = &(*next_r)->left;
					root = ::std::move(*next_r);
				}
				else if (!(key <= root->right->key)) {
					*next_l = ::std::move(root->right);
					root->right = ::std::move((*next_l)->left);
					(*next_l)->left = ::std::move(root);
					next_l = &(*next_l)->right;
					root = ::std::move(*next_l);
				}
				else {
					*next_l = ::std::move(root);
					next_l = &(*next_l)->right;
					root = ::std::move(*next_l);
				}
			}
			else {
				*next_l = ::std::move(root->left);
				root->left = ::std::move(left);
				*next_r = ::std::move(root->right);
				root->right = ::std::move(right);
				return root->value;
			}
		}
	}
};

#include <iostream>
#include <map>

int main() {
	using i64 = long long;
	int n;
	::std::cin >> n;

	::std::map<i64, i64> mp;
	i64 sum = 0, ans = 0;
	mp[0] = 1;

	while (n--) {
		int a;
		::std::cin >> a;
		
		sum += a;
		ans += mp[sum]++;
	}

	::std::cout << ans << ::std::endl;

	return 0;
}


Measured memory_bytes: 12800
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll mod=1000000007;
const char nl='\n';

void solve()
{
    ll i,j,l,r,n,k,m,u,v,x,y,z,q,p,h;
    string s;
    cin>>s;
    ll ans;
    if(s=="SSS") ans=0;
    if(s=="RSS") ans=1;
    if(s=="SRS") ans=1;
    if(s=="SSR") ans=1;
    if(s=="RRS") ans=2;
    if(s=="SRR") ans=2;
    if(s=="RSR") ans=1;
    if(s=="RRR") ans=3;
    cout<<ans<<nl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1,i=1;
//    cin >> t;
	while (t--)
	{
//	    cout<<"Case #"<<i++<<": ";
		solve();
	}
	return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <cmath>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define psi pair < string, int>

queue<psi> Q;

ll ans;
int N, k;
string st;

void dfs(){
    if(N==1){
        cout << "a" << endl;
        return;
    }

    Q.push(make_pair("a", 1));

    while(!Q.empty()){
        psi tmp = Q.front();
        Q.pop();
        k = tmp.second;

        rep(i, k+1){
            st = tmp.first;
            char c = 'a' + i;
            st += c;
            
            if(st.size() == N)
                cout << st << endl;
            else{
                if(i==k)
                    Q.push(make_pair(st, k+1));
                else
                    Q.push(make_pair(st, k));
            }
        }
    }
}

// void recurr_enum(string st, int k){
//     if(st.size() == N){
//         cout << st << endl;
//         return;
//     }

//     rep(i, k+1){
//         char tmp = 'a' + i;
//         string buff = st + tmp;
//         if(i==k)
//             recurr_enum(buff, k+1);
//         else
//             recurr_enum(buff, k);
//         }
//     }

void solve(){
    // recurr_enum("a", 1);
    dfs();
}

int main(){
    cin >> N;

    solve();
}


Measured memory_bytes: 3200
#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;

int n, a, b;
ll ans, sum;

ll combo(int n, int k) {
    int a = k, b = n - k;
    if (a < b)
        swap(a, b);
    int bi = 1;
    ll res = 1;
    for (int i = a + 1; i <= n; ++i) {
        while (1e18 / i < res && bi <= b) {
            res /= bi;
            ++bi;
        }
        res *= i;
    }
    for (; bi <= b; ++bi) {
        res /= bi;
    }
    return res;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
    cin >> n >> a >> b;
    vector<ll> ar(n);
    rep(i, 0, n) {
        cin >> ar[i];
    }
    sort(all(ar), greater<ll>());
    rep(i, 0, a) {
        sum += ar[i];
    }
    cout << fixed << setprecision(6) << sum / (double)a << '\n';
    if (ar[a - 1] == ar[0]) {
        int tot = 0;
        rep(i, 0, n)
            if (ar[i] == ar[0])
                tot = i;
        ++tot;
        for (int i = a; i <= min(tot, b); ++i) {
            ans += combo(tot, i);
        }
    } else {
        // Count how many there are of ar[a - 1]. THen it's n Choose cnt
        int tot = 0, used = 0;
        rep(i, 0, n) {
            if (ar[i] == ar[a - 1]) {
                ++tot;
                if (i < a) ++used;
            }
        }
        ans = combo(tot, used);
    }
    cout << ans;
}


Measured memory_bytes: 3740
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if 0 in a:
        print(0)
        exit()
    else:
        ans = 1
        for i in a:
            ans *= i
            if ans > 10**18:
                print(-1)
                exit()
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 21776
n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
	c=int(c)
	for f in range(2):
		for j in range(k+1):
			for l in range(10*f or c+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])

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

int main(){
    int N, M;
    cin >> N >> M;
    int p;
    bool flag[N] = {};
    int sum_ac=0;
    int sum_wa[N] = {};
    int sum_wa_sum =0;
    char s[2];

    for(int i;i<M;i++){
        cin >> p >> s;
       if(flag[p-1]){}
        else if(s[0] == 'A')
        {
            sum_ac++;
            flag[p-1]=true;
        }
        else
        {
            sum_wa[p-1]++;
        }
    }
    for(int i=0;i<N;i++){
        if(flag[i])
            sum_wa_sum+=sum_wa[i];
    }
    cout << sum_ac << " " << sum_wa_sum;

    return 0;
}

Measured memory_bytes: 768