akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;

int N;

ll		solve(vector<ll> &A, ll cur)
{
	ll ans = 0;
	for (int i = 1; i < N; i++)
	{
		if (cur > 0 && cur+A[i] >= 0)
		{
			ans += abs(-1-(cur+A[i]));
			cur = -1;
		}
		else if (cur < 0 && cur+A[i] <= 0)
		{
			ans += abs(1-(cur+A[i]));
			cur = 1;
		}
		else
			cur += A[i];
	}
	return (ans);
}

int		main(void)
{
	cin >> N;
	vector<ll> A(N);
	for (int i = 0; i < N; i++)
		cin >> A[i];
	ll ans1 = 0, ans2 = 0;
	ll cur = A[0];
	if (cur <= 0)
	{
		ans1 += abs(1-cur);
		cur = 1;
	}
	ans1 += solve(A, cur);
	cur = A[0];
	if (cur >= 0)
	{
		ans2 += abs(-1-cur);
		cur = -1;
	}
	ans2 += solve(A, cur);
	cout << min(ans1, ans2) << endl;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s,t;
  cin >> s >> t;
  int a,b;
  cin >> a >> b;
  string u;
  cin >> u;
  if (s == u) {
    cout << a-1 << " " << b << endl;
  } else {
    cout << a << " " << b-1 << endl;
  }
}

Measured memory_bytes: 256
using System;

public class hello
{
    public static void Main()
    {
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            string[] line = Console.ReadLine().Trim().Split(' ');
            var ary = Array.ConvertAll(line, int.Parse);
            var diff = 1000000;
            for (int i = 0; i < n-1; i++)
                for (int j = i+1; j < n; j++)
                {
                    var temp = Math.Abs(ary[i] - ary[j]);
                    if (temp < diff) diff = temp;
                }
            Console.WriteLine(diff);
        }
    }
}

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

cnt = [0] * n

for i in range(m):
    cnt[ab[i][0] - 1] += 1
    cnt[ab[i][1] - 1] += 1

for i in range(n):
    print(cnt[i])


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<math.h>
#include<vector>
#include<map>
#include<utility>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin>>N;
    vector<int> a(N);
    vector<int> b(N);
    vector<int> c(N);
    vector<vector<int> > v(N,vector<int>(3));
    for (int i=0;i<N;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    v[0][0]=a[0];
    v[0][1]=b[0];
    v[0][2]=c[0];
    for (int i=1;i<N;i++){
        v[i][0]=a[i]+max(v[i-1][1],v[i-1][2]);
        v[i][1]=b[i]+max(v[i-1][0],v[i-1][2]);
        v[i][2]=c[i]+max(v[i-1][1],v[i-1][0]);
    }
    cout<<max(v[N-1][0],max(v[N-1][2],v[N-1][1]))<<'\n';
}

Measured memory_bytes: 6912
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.edges2 = []                            # ワーシャルフロイド用
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))
            self.edges2.append((y, x, cost))

    def prim(self):
        """
        :return: 最小全域木を選んだ時の重さの総和
        """
        start = 0  # 解析のスタート地点を決める。どこでもいい
        visit = [False] * self.n  # 各頂点までの最短距離
        next_set = [(0, start)]
        res = 0
        while next_set:
            dist, p = heappop(next_set)  # 近いところから順に確定させていく必要があるため、heappop を用いる
            if visit[p]:
                continue
            visit[p] = True
            res += dist  # クラスカル法と違って隣接点を調べていくので、足される数の大きさはバラバラ
            for edge in self.edges[p]:
                q, cost = edge.to, edge.cost
                if visit[q]:
                    continue
                heappush(next_set, (cost, q))  # q を介して他の頂点に行く可能性を考える。q に行くまでの最短距離が明らかになっている点が重要
        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.directed:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for edge in self.edges[x]:
                G.add_edge(x + self.decrement, edge.to + self.decrement, weight=edge.cost)


        edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos, with_labels=True)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.axis("off")
        plt.show()

##############################################################################################################
import sys
input = sys.stdin.readline
from heapq import *


N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

print(graph.prim())


Measured memory_bytes: 74024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int ans=0;
  ans+=b;
  int T=min(b+1,c);
  ans+=T;
  c-=T;
  ans+=min(a,c);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
S = input().strip()
if S=="SUN":
    print(7)
elif S=="MON":
    print(6)
elif S=="TUE":
    print(5)
elif S=="WED":
    print(4)
elif S=="THU":
    print(3)
elif S=="FRI":
    print(2)
elif S=="SAT":
    print(1)

Measured memory_bytes: 38384
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include<complex>
#include<unordered_set>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX = 1000 * 100 + 47;
int A[MAX];

bool is2pow(int a)
{
	int p = 0;
	while ((1 << p) < a) p++;
	return (1 << p) == a;
}

int log2(int a)
{
	int p = 0;
	while ((1 << p) < a) p++;
	return p;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	FOR(i, 0, n) cin >> A[i];

	int ans = 0;
	int last = 0;
	
	FOR(i, 0, n)
	{
		int p = log2(A[i]);
		ans += p;

		//cout << i << ": " << ans << endl;
		if (is2pow(A[i]))
		{
			ans -= min(last, p);
			last = p;
			continue;
		}

		if (p - 1 >= last)
		{
			ans -= min(p - 1, last);
			last = p;
			continue;
		}

		ans -= min(p, last);
		last = p - 1;
	}

	cout << ans << endl;
}

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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define sint int32_t
#define int long long int
#define all(v) v.begin() , v.end()
#define vii vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int32_t main()
{   fastio;


    // int t;
    // cin>>t;
    // while(t--)
    // {

    // }

    int n , k;
    cin>>n>>k;
    int arr[n];
    for(auto &i:arr) cin>>i;

    for(int i=k; i<n; i++) {
        if(arr[i]>arr[i-k]) cout<<"Yes\n";
        else cout<<"No\n";
    }

}

Measured memory_bytes: 5172
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n,a,sub=0,tar;
	cin >> n;
	for(int i=0;i<n;i++){
	    cin >> a;
	    
	    if(i==1){
	        sub=a-tar;
	    }
	    
	    if(i==0){
	        tar=a;
	    }
	    else{
	        sub=max(sub,a-tar);
	        if(a-tar<0){
	            tar=a;
	        }
	        //sub=max(sub,a-tar);
	    }
	}
	cout << sub<<endl;
	
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n+1, 0);
  for (int i = 1; i <= n; i++) cin >> a[i];
  int64_t money = 1000LL;//0日目
  bool zoka = a[1] < a[2]? true: false;//イコールどっち？
  int left = 1, day = 1;
  while(day < n) {
    if(zoka && a[day] > a[day + 1]) {
      money += (int64_t)(money / a[left] * (a[day]-a[left]));
      zoka = false;
      left = day;
    }else if(!zoka && a[day] < a[day + 1]) {
      zoka = true;
      left = day;
    }
    day++;
  }
  if(zoka) money += (int64_t)(money / a[left] * (a[n]-a[left]));
  cout << money;
}

Measured memory_bytes: 3596
#include "bits/stdc++.h"
using namespace std;
static const int PLAYERS = 3;

int main() {
    string deck[PLAYERS];
    int pos[PLAYERS];
    char playerName[PLAYERS] = { 'A', 'B', 'C'};

    for (int i = 0; i < PLAYERS; ++i) {
        cin >> deck[i];
        pos[i] = 0;
    }

    int turn = 0;

    while (true) {
        if (deck[turn].size() <= pos[turn]) {
            break;
        }
        int t = deck[turn][pos[turn]] - 'a';
        pos[turn]++;
        turn = t;
    }

    cout << playerName[turn] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const ll mod = 1000000007;
ll inv[10000100];
ll FactorialInv[10000100];
ll Factorial[10000100];
ll beki(ll a, ll b){
    if(b == 0){
        return 1;
    }
    ll ans = beki(a, b / 2);
    ans = ans * ans % mod;
    if(b % 2 == 1){
        ans = ans * a % mod;
    }
    return ans;
}
void init_combination(){
    const int MAX = 10000002;
    Factorial[0] = 1;
    inv[0] = 1;
    for(int i = 1; i <= MAX; i++){
        Factorial[i] = Factorial[i - 1] * i % mod;
    }
    FactorialInv[MAX] = beki(Factorial[MAX], mod - 2);
    for(ll i = MAX - 1; i >= 0; i--) {
        FactorialInv[i] = FactorialInv[i+1] * (i+1) % mod;
    }
    for(int i = 1; i <= MAX; i++) {
        inv[i] = FactorialInv[i] * Factorial[i-1] % mod;
    }
}
ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}

ll H, W;
string field[25];
ll dist[500][500];
int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
  cin >> H >> W;
  for(int h = 0; h < H; h++) {
    cin >> field[h];
  }
  for(int i = 0; i < H * W; i++) {
    for(int j = 0; j < H * W; j++) {
      dist[i][j] = INF;
    }
    dist[i][i] = 0;
  }
  for(int h = 0; h < H; h++) {
    for(int w = 0; w < W; w++) {
      if(field[h][w] == '#') continue;
      if(h < H - 1 and field[h+1][w] == '.') {
        dist[h*W+w][(h+1)*W+w] = 1;
        dist[(h+1)*W+w][h*W+w] = 1;
      }
      if(w < W - 1 and field[h][w+1] == '.') {
        dist[h*W+w][h*W+w+1] = 1;
        dist[h*W+w+1][h*W+w] = 1;
      }
    }
  }
  for(int i = 0; i < H * W; i++) {
    for(int j = 0; j < H * W; j++) {
      for(int k = 0; k < H * W; k++) {
        chmin(dist[j][k], dist[j][i] + dist[i][k]);
      }
    }
  }
  ll ans = 0;
  for(int i = 0; i < H * W; i++) {
    for(int j = 0; j < H * W; j++) {
      if(dist[i][j] == INF) continue;
      chmax(ans, dist[i][j]);
    }
  }
  cout << ans << endl;
    return 0;
}

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

using namespace std;

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

const int N = 100 * 1000 + 10;

vector<int> g[N];
bool ok = true;
ll out[N];
ll a[N];

void dfs(int v, int p) {
    vector<int> kids;
    for (int to : g[v])
        if (to != p)
            kids.push_back(to);
    if (kids.size() == 0) {
        out[v] = a[v];
        return;
    }
    ll s = 0;
    ll mx = 0;
    for (int to : kids) {
        dfs(to, v);
        s += out[to];
        mx = max(mx, out[to]);    
    }    
    ll high = s;
    ll low = (mx * 2 > s ? mx : s / 2 + s % 2);
    if (a[v] < low || a[v] > high)
        ok = false; 
    ll matched = s - a[v];
    out[v] = s - matched * 2;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);    
    }
    if (n == 2) {
        cout << (a[0] == a[1] ? "YES" : "NO") << endl;
        return 0;    
    }
    int v = 0;
    while (g[v].size() == 1)
        v++;
    dfs(v, v);
    cout << (ok && out[v] == 0 ? "YES" : "NO") << endl;
}   

Measured memory_bytes: 20608
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

fun main() {
    val (h, w, k) = readIntList()
    val grid = Array(h + 2) { Array(w + 2) { ' ' } }
    for (i in 1..h) {
        val row = readLine()!!
        for (j in row.indices) {
            grid[i][j + 1] = row[j]
        }
    }

    var res = 0
    for (i in 0 until (1 shl h)) {
        for (j in 0 until (1 shl w)) {
            var num = 0

            for (m in 1..h) {
                for (l in 1..w) {
                    if (((i shr (m - 1) and 1) == 1) || ((j shr (l - 1) and 1) == 1)) {
                        continue
                    }
                    if (grid[m][l] == '#') {
                        num += 1
                    }
                }
            }

            if (num == k) {
                res += 1
            }
        }
    }

    println(res)
}


Measured memory_bytes: 37096
#include<stdio.h>
#include<stdlib.h>

#define N 2000000
#define M 10000

void CountingSort(unsigned short*,unsigned short*);

int C[M+1],n;

int main(){
  unsigned short *A,*B;
  int i,j;

  scanf("%d",&n);

  A=malloc(sizeof(short)*n-1);
  B=malloc(sizeof(short)*n-1);
  
  for(i=0;i<n;i++){
    scanf(" %d",&A[i]);
  }

  CountingSort(A,B);

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


  return 0;
}

void CountingSort(unsigned short *A,unsigned short *B){
  int i,j;

  for(i=0;i<M+1;i++){
    C[i]=0;
  }

  for(j=0;j<n;j++){
    C[A[j]]++;
  }

  for(i=1;i<M+1;i++){
    C[i]=C[i]+C[i-1];
  }

  for(j=n-1;j>=0;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }

  
  return;
}
  



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

int main(void){
    vector<pair<int,int>> vec(5);
    for(int i=0;i<5;i++){
        cin >> vec[i].second;
        vec[i].first = vec[i].second%10;
        if(vec[i].first == 0) vec[i].first = 10;
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());

    int ans = 0;
    for(int i=0;i<4;i++){
        vec[i].second = (vec[i].second+9)/10;
        ans += 10*vec[i].second;
    }
    ans += vec[4].second;

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

char s[101];

int main() {
    long long k;
    scanf("%s", s);
    scanf("%lld", &k);
    
    int len = strlen(s);
    int res = -1;
    k--;
    for(int i = 0; i < len; i++) {
        if(s[i] != '1' || k == 0) { res = s[i] - '0'; break; }
        k--;
    }
    printf("%d\n", res);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define um unordered_map
#define MAX 100000
using namespace std;

um<int,list<int>> l;
bool vis[MAX+1];
int dp[MAX+1];

int dfs(int src)
{
    vis[src]=true;
    
    for(auto node:l[src])
    {
        int l=0;
        if(!vis[node])
        {
            l=1+dfs(node);
        }
        else
        {
            l=1+dp[node];
        }
        dp[src]=max(dp[src],l);
    }
    return dp[src];
}
int main() {
    
    int n,m;
    cin>>n>>m;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        l[x].pb(y);
    }
    memset(dp,0,sizeof(dp));
    memset(vis,false,sizeof(vis));
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dfs(i));
    }
    cout<<ans;
}


Measured memory_bytes: 15252
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <boost/math/common_factor_rt.hpp>
using namespace std;
#define rep(i, n) for(int i = 0;i < n;i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ll long long

int main(){
  ll n;
  cin >> n;
  ll v[200100];
  ll vg[100100];
  ll vk[100100];
  rep(i, n) cin >> v[i];
  
  rep(i, 100100){
    vg[i] = 0;
    vk[i] = 0;
  }
  
  for(int i=0; i<n; i+=2) vg[v[i]]++;
  for(int i=1; i<n; i+=2) vk[v[i]]++;
  
  ll gmax = 0;
  ll g2max = 0;
  ll kmax = 0;
  ll k2max = 0;
  int gid, kid;
  
  rep(i, 100100) {
    if(vg[i]>g2max){
      if(vg[i]>gmax){
        g2max = gmax;
        gmax = vg[i];
        gid = i;
      }else{
        g2max = vg[i];
      }
    }
    if(vk[i]>k2max){
      if(vk[i]>kmax){
        k2max = kmax;
        kmax = vk[i];
        kid = i;
      }else{
        k2max = vk[i];
      }
    }
  }
  //cout << gmax << kmax << g2max << k2max << endl;
  
  if(gid==kid && (gmax+k2max) >= (kmax+g2max)) cout << n-(gmax+k2max) << endl;
  else if(gid==kid) cout << n-(kmax+g2max) << endl;
  else cout << n-gmax-kmax << endl;
    
}

Measured memory_bytes: 3328
N = int(input())
import math
def d(x,y):
    return math.sqrt((x[0]-y[0])**2+(x[1]-y[1])**2)
ans = 0
xy = [list(map(int,input().split())) for i in range(N)]
for i in range(N-1):
    for j in range(i,N):
        ans += 2*d(xy[i],xy[j])/N
print(ans)

Measured memory_bytes: 3064
while True:
  H,W=map(int,input().split())
  if H==0 and W==0: break
  for i in range(0,H):
    
    if i%2==0:
      for j in range(0,W):
        if j%2==0:
          print("#",sep='',end='')
        else:
          print(".",sep='',end='')
    
    else:
      for j in range(0,W):
        if j%2==0:
          print(".",sep='',end='')
        else:
          print("#",sep='',end='')
    
    print()
  print()


Measured memory_bytes: 7000
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			if ((n | m) == 0)
				break;
			int[] pow3 = new int[n + 1];
			pow3[0] = 1;
			for (int i = 1; i <= n; i++)
				pow3[i] = pow3[i - 1] * 3;
			int[] c = new int[n];
			for (int i = 0; i < 3; i++) {
				int a = scanner.nextInt();
				for (int j = a; j > 0; j--) {
					int b = scanner.nextInt();
					c[n - b] = i;
				}
			}
			int p = 0;
			int x = 0;
			for (int i = 0; i < n; i++) {
				int d = Math.abs(p - c[i]);
				x += pow3[i] * d;
				if (d == 1)
					p = 2 - p;
			}
			int y = pow3[n] - x - 1;
			x = Math.min(x, y);
			System.out.println(x > m ? -1 : x);
		}
	}
}

Measured memory_bytes: 17364
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <limits>
using namespace std;
// 素因数分解
typedef pair<long long, long long> P;
vector<P> prime_factorize(long long n)
{
vector<P> res;
for (long long p = 2; p * p <= n; ++p)
{
if (n % p != 0)
continue;
int num = 0;
while (n % p == 0)
{
++num;
n /= p;
}
res.push_back(make_pair(p, num));
}
if (n != 1)
res.push_back(make_pair(n, 1));
return res;
}
// 因数分解
long long gcd(long long x, long long y)
{
  if (y == 0)
  {
    return x;
  }
  else
  {
    return gcd(y, x % y);
  }
}
const int MOD = 1000000007;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (n); i++)

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int> > G(n,vector<int>());
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<int> dist(n,-1);
    vector<int> prev(n,-1);
    queue<int> que;
    que.push(0);
    dist[0]=0;
    while(!que.empty()){
        int v=que.front();
        que.pop();
        for(auto nv:G[v]){
            if(dist[nv]==-1){
                dist[nv]=dist[v]+1;
                prev[nv]=v;
                que.push(nv);
            }
        }
    }
    cout<<"Yes"<<endl;
    for(int i=1;i<n;i++){
        cout<<prev[i]+1<<endl;
    }
    
return 0;
}

Measured memory_bytes: 10700
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

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

using namespace std;
//        tmp = stoi(S.substr(i,3));
int main(){
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());
    ll N;
    vector <ll> v(3);

    REP(i,3)
    {
        cin >> v[i];
    }

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

    cout << v[0] + v[1] + v[2]*10 << endl;

    return 0;
}

Measured memory_bytes: 256
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();
            var n = line[0];
            var m = line[1];
            var k = line[2];
            var aArray = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();
            var bArray = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();
            //var a = long.Parse(ReadLine());

            long aTotalTime = 0;
            foreach(var a in aArray)
            {
                aTotalTime += a;
            }
            long bTotalTime = 0;
            foreach(var b in bArray)
            {
                bTotalTime += b;
            }

            if(aTotalTime + bTotalTime <= k)
            {
                WriteLine(aArray.Length + bArray.Length);
                return;
            }

            long time = 0;
            var count = 0;
            var aIndex = -1;
            foreach(var a in aArray)
            {
                if(time + a <= k)
                {
                    time += a;
                    count++;
                    aIndex++;
                }
                else
                {
                    break;
                }
            }
            var bIndex = 0;
            foreach(var b in bArray)
            {
                if(time + b <= k)
                {
                    time += b;
                    count++;
                    bIndex++;
                }
                else
                {
                    break;
                }
            }
            if(aIndex == aArray.Length - 1 && bIndex == bArray.Length)
            {
                WriteLine(count);
                return;
            }

            var maxCount = count;
            while(aIndex >= 0 && bIndex < bArray.Length)
            {
                time -= aArray[aIndex];
                count--;
                while(bIndex < bArray.Length)
                {
                    if(time + bArray[bIndex] <= k)
                    {
                        time += bArray[bIndex];
                        bIndex++;
                        count++;
                        maxCount = Max(maxCount, count);
                    }
                    else
                    {
                        break;
                    }
                }
                aIndex--;
            }

            WriteLine(maxCount);
        }
    }
}


Measured memory_bytes: 62340
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <climits> 
#include <assert.h>
#include <random>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod2 = 1'000'000'007;
constexpr ll mod = 998244353;
const double PI = 3.14159265358;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-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;
  vector<int> A(N);
  for(int i=0; i<N; i++) cin >> A[i];
  vector<int> B(N);
  priority_queue<P> que;
  for(int i=0; i<N; i++){
    cin >> B[i];
    que.emplace(B[i],i);
  }
  ll ans = 0;
  bool can = true;
  while(que.size()){
    int num,v;
    tie(num,v) = que.top();
    que.pop();
    if(num < A[v]){
      can = false;
      break;
    }
    int sum = B[(v-1+N)%N] + B[(v+1)%N];
    if(sum > num) continue;
    if((num-A[v])%sum == 0){
      ans += (num-A[v])/sum;
      B[v] = A[v];
    }else{
      ans += num/sum;
      num %= sum;
      B[v] = num;
      que.emplace(num,v);
    }
  }
  for(int i=0; i<N; i++){
    if(A[i] != B[i]) can = false;
  }
  if(can){
    cout << ans << "\n";
  }else{
    cout << "-1\n";
  }
  return 0;
}

Measured memory_bytes: 6792
#include <stdio.h>

using namespace std;

int main(){
	int n;
	scanf("%d",&n);
	int A[n];

	for(int i = 0; i < n; i++) scanf("%d",&A[i]);

	for(int i = n-1; i > 0; i--) printf("%d ",A[i]);
	printf("%d\n",A[0]);
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
 
/* Coding Space*/
int main(){
  map<int,int> m;
  int n; cin >> n;
  rep(i,n){
    int in; cin >> in;
    m[in]++;
  }
  ll ans = 0;
  for(auto i:m){
    if(i.FST <= i.SEC)
      ans +=  i.SEC - i.FST;
    else
      ans += i.SEC;
  }
  cout << ans << endl;
}

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

#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define ABS(x, y) ((x) > (y) ? ((x) - (y)) : ((y) - (x)))

#define DIVUP(x, y) (((x) + ((y) - 1)) / (y))
#define DIVOFF(x, y) (((x) + ((y) / 2)) / (y))
#define REMAINDER(x, y) ((x) % (y))

int main() {
  int A, B, C; scanf("%d%d%d", &A, &B, &C);
  int total = MIN(B, C) * 2;
  if (B > C) {
    total += B - C;
  } else if (C > B) {
    total += MIN(A + 1, C - B);
  }

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


Measured memory_bytes: 760
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    int n, l;
    cin >> n >> l;
    vector<string> s(n);
    rep(i, n) {
        cin >> s[i];
    }
    sort(s.begin(), s.end());
    for ( auto t : s ) {
        cout << t;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
H,W = gets.split.map(&:to_i)

def mini(h,w)
  vv = w % 3 == 0 ? 0 : h
  vh = (1...w).map{ |i|
    ss = [
      h*i,
      (w-i)*(h/2),
      (w-i)*(h - (h/2)),
    ]
    #$stderr.puts "#{i}, #{h/2}, #{h-h/2}, #{w-i}, #{ss}"
    ss.max - ss.min
  }.min
  $stderr.puts "(#{H}, #{W}) -> [#{vv}, #{vh}]"
  [vv,vh].min
end

puts [mini(H,W), mini(W,H)].min

Measured memory_bytes: 3452
#include <bits/stdc++.h>
#include <string>
using namespace std;
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
// sort(a.begin(), a.end(), std::greater<int>());

/*
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}
*/

#define num 10
int main()
{
    int a, b;
    int ans = 0;
    cin >> a >> b;
    REP(i, a, b + 1)
    {
        string temp = to_string(i);
        if (temp[0] == temp[4])
        {
            if (temp[1] == temp[3])
            {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/
vector<ll> lunlun;
ll digits(ll m){
    if(m == 0)return 1;
    ll count = 0;
    while (m > 0){
        m /= 10;
        count++;
     }
     return count;
}

void dfs(ll m, ll digit){
    if(digit > 10) return;
    ll a = m * 10;
    ll b = m % 10;
        
    if(1 <= b and b <= 9){
        dfs(a + b - 1, digit + 1);
        lunlun.push_back(a + b - 1);       
    }
    if(0 <= b and b <= 8){
        dfs(a + b + 1, digit + 1);
        lunlun.push_back(a + b + 1);
    }
    dfs(a + b, digit + 1);
    lunlun.push_back(a + b);
}


int main(){
    ll k; cin >> k;    
    for(ll i = 1; i <= 9; i++){
        dfs(i, 1);
        lunlun.push_back(i);
    }
    sort(lunlun.begin(), lunlun.end());
    cout << lunlun[k - 1] << endl;
}

Measured memory_bytes: 11640
#include<stdio.h>
 
int main(void){
	int N, D;
	if (scanf("%d", &N) == 1);
	if (N >= 100 && N <= 999){
		D = N / 100;
		if ((N - D) % 10 == 0)
			printf("Yes");
		else
			printf("No");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>

using namespace std;

int main() {
	int n, a, b;
	cin >> n >> a >> b;

	int sum = 0;
	for (int i = 1; i <= n; i++) {
		int t = i;
		int x = 0;
		for (int j = 0; j < 5; j++) {
			x += t % 10;
			t /= 10;
		}
		if (a <= x && x <= b) sum += i;
	}

	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    long long N, K;
    cin >> N >> K;
    long long count=0;
    long long p = 1e9+7;
    for (int i=K; i<N+2; i++){
        count = (count + i*(N-i+1) +1) %p;
    }
    cout << count << endl;
}

Measured memory_bytes: 3644
#include <cstdio>

const int SIZE = 100005;
int BIT[26][SIZE];
char s[SIZE];

void add(int idx, int v, int l){
	while(idx < SIZE){
		BIT[l][idx] += v;
		idx += idx & -idx;
	}
}

int get(int idx, int l){
	int ret=0;
	while(idx){
		ret += BIT[l][idx];
		idx -= idx & -idx;
	}
	return ret;
}

int main(){
	int sz=0, lMin, lMinIdx, tmp;
	scanf("%s", s);
	while(s[sz]){
		add(sz+1, 1, s[sz] - 'a');
		++sz;
	}
	for(int i=0; i<26; ++i){
		lMin = 987654321;
		lMinIdx = 0;
		for(int j=2; j<=sz; ++j){
			tmp = 2 * get(j-2, i) - (j-2);
			if(tmp < lMin){
				lMin = tmp;
				lMinIdx = j-1;
			}
			if(2 * get(j, i) - j - lMin > 0){
				printf("%d %d\n", lMinIdx, j);
				return 0;
			}
		}
	}
	printf("-1 -1\n");
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
#define ll long long
#define maxn 200005
#define endl '\n'
using namespace std;
int n;
int arr[maxn];
vector<int> G[maxn];
ll cal(int n) {
	return (ll)n * (n + 1) / 2ll;
}
int in[maxn],out[maxn],sz[maxn];
void dfs1(int u,int pa) {
	static int tmp = 1;
	in[u] = tmp++;
	sz[u] = 1;
	for(int v : G[u])
		if(v != pa) {
			dfs1(v,u);
			sz[u] += sz[v];
		}
	out[u] = tmp++;
}
ll ans[maxn];
vector<int> idxs[maxn];
vector<ll> sum[maxn];
void dfs2(int u,int pa) {
	int k = arr[u];
	for(int v : G[u])
		if(v != pa) {
			dfs2(v,u);
			if(arr[v] != arr[u]) {
				int l = lower_bound(idxs[k].begin(),idxs[k].end(),in[v]) - idxs[k].begin();
				int num = sz[v];
				if(l < (int)sum[k].size())
					num -= (sum[k].back() - sum[k][l - 1]);
				ans[k] -= cal(num);
			}
		}
	while(!idxs[k].empty() && in[u] < idxs[k].back()) {
		sum[k].pop_back();
		idxs[k].pop_back();
	}
	sum[k].push_back(sum[k].back() + sz[u]);
	idxs[k].push_back(in[u]);
	
	if(u == 1) {
		for(int i=1;i<=n;i++)
			if(i != k)
				ans[i] -= cal(n - sum[i].back());
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> arr[i];
	for(int i=1,u,v;i<n;i++) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1,1);
	fill(ans+1,ans+1+n,cal(n));
	for(int i=1;i<=n;i++)	idxs[i].push_back(0) , sum[i].push_back(0);
	dfs2(1,1);
	for(int i=1;i<=n;i++)
		cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 66068
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD7 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int N;
    cin >> N;
    vector<int> V(N);
    for(int i = 0; i < N; i++) cin >> V[i];
    sort(all(V));
    double v = V[0];
    for(int i = 1; i < N; i++){
        v = (v + V[i]) / 2;
    }
    cout << setprecision(10) << v << endl;
}

Measured memory_bytes: 3696
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#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 pb push_back
#define bg begin()
#define en end()

#define pr_arr(name, a, b) \
  for (int i = (a); i < (b); i++) { \
    for (int j = (a); j < (b); j++) {\
      if (j > (a)) printf(" "); \
      printf("%lld", name[i][j]); \
    }\
    printf("\n");\
  }\

#define YES puts("YES")
#define NO  puts("NO")
#define Yes puts("Yes")
#define No  puts("No")

using namespace std;

typedef long long ll;

ll ans1, ans2;
ll A, B, K;

int main(void) {
    scanf("%lld %lld %lld", &A, &B, &K);

    if (K<A) {
        ans1 = A-K;
        ans2 = B;
    } else {
        ans1 = 0;
        ans2 = max<ll>(0, B-(K-A));
    }

  
    printf("%lld %lld\n", ans1, ans2);

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

		
	    public static void main(String[] args) throws java.io.IOException{
	        Scanner scan = new Scanner(System.in);
	 
	        while(true){
	        	int [] p =new int[5];
	        	p[0]=scan.nextInt();
	        	if(p[0]==0)break;
	        	for(int i=1;i<5;i++)p[i]=scan.nextInt();
	        	
	        	int g=0;
	        	int c =0;
	        	int pe =0;
	        	for(int i=0;i<5;i++){
	        		switch(p[i]){
	        		case 1:g++;
	        			break;
	        		case 2:c++;
	        			break;
	        		case 3:pe++;
	        			break;
	        		}
	        	}
	        	if(g==5||c==5||pe==5)
	        		for(int i=0;i<5;i++)
	        		System.out.println(3);
	        	else if(g>0&&c>0&&pe>0)
	        		for(int i=0;i<5;i++)
	        			System.out.println(3);
	        	else if(g==0&&c>pe){
	        		for(int i=0;i<5;i++){
	        			if(p[i]==2)System.out.println(1);
	        			else System.out.println(2);
	        		}
	        	}
	        	else if(g==0){
	        		for(int i=0;i<5;i++){
	        			if(p[i]==2)System.out.println(1);
	        			else System.out.println(2);
	        		}
	        	}
	        	else if(c==0){
	        		for(int i=0;i<5;i++){
	        			if(p[i]==3)System.out.println(1);
	        			else System.out.println(2);
	        		}
	        	}
	        	else if(pe==0){
	        		for(int i=0;i<5;i++){
	        			if(p[i]==1)System.out.println(1);
	        			else System.out.println(2);
	        		}
	        	}
	
	        		
	        	}
	        }
	     
}
	    

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define LL long long
#define MOD 1000000007
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0)
using namespace std;

int main()
{
    fastio;
  LL n;
  cin>>n;
  cout<<(n%1000==0 ? 0:(1000 - n%1000))<<"\n";
  	return 0;
}

Measured memory_bytes: 3636
//gauravsinghh
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define db double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int> 
#define vll vector<long long>
#define mii map<int,int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define os cout<<" "
#define bitcount __builtin_popcount
#define gcd __gcd
#define endl "\n"
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define ford(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fors(container, it, a, b) for(__typeof(container.begin()) it = a; it != b; it++) 
#define MOD 1000000007
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 999999999999999999
#define siz 100005
#define fbo find_by_order
#define ook order_of_key
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define ffo(i, a, b) for(int i = a; i >= b; i--)
#define MAX 100005
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

bool comp(const pair < ll, ll >&a, const pair < ll, ll >&b){
    return ((a.ss < b.ss) || (a.ss == b.ss && a.ff < b.ff));
}

signed main(){ 
    IOS
    string s;
    cin >> s;
    ll n = 753, m = INT_MAX;
    if(sz(s) <= 2){
        ll x = stoi(s);
        cout << abs(n - x) << endl;
        return 0;
    }
    fo(i, 0, sz(s)-3){
        ll x = (s[i]-'0')*100 + (s[i+1]-'0')*10 + (s[i+2]-'0');
        m = min(m, abs(x-n));
    }
    cout << m << endl;
    return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {
	static final int MOD = 1000000007;
	public static void main (String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char[] arr = sc.next().toCharArray();
		boolean flag = true;
		boolean[] isLefts = new boolean[2 * n];
		int leftCount = 0;
		for (int i = 0; i < 2 * n; i++) {
			if (i == 0) {
				isLefts[i] = true;
				leftCount++;
				if (arr[i] != 'B') {
					flag = false;
					break;
				}
			} else {
				if (arr[i] == arr[i - 1]) {
					isLefts[i] = !isLefts[i - 1];
				} else {
					isLefts[i] = isLefts[i - 1];
				}
				if (isLefts[i]) {
					leftCount++;
				}
			}
			if (i == 2 * n - 1 && ((arr[i] == 'W') || isLefts[i])) {
				flag = false;
			}
		}
		if (leftCount != n) {
			flag = false;
		}
		if (!flag) {
			System.out.println(0);
			return;
		}
		long total = 1;
		int lCount = 0;
		int rCount = 0;
		for (int i = 0; i < 2 * n; i++) {
			if (isLefts[i]) {
				lCount++;
			} else {
				total *= lCount - rCount;
				total %= MOD;
				rCount++;
			}
		}
		total *= kaijo(n);
		System.out.println(total % MOD);
	}
	
	static long kaijo(long x) {
		if (x == 0) {
			return 1;
		}
		long ans = x * kaijo(x - 1);
		return ans % MOD;
	}
}


Measured memory_bytes: 35532
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  
  ll n,sum=0;
  cin>>n;
  
  vector<ll> v(n),v2(n);
  //map<ll,ll> m;
  //map<ll,ll>::iterator it;
  
  for(ll i=0;i<n;i++)
  {
   cin>>v[i];
   v2[v[i]-1]++;
  }
  
  for(ll i =0;i<n;i++)
  {
   sum+=v2[i]*(v2[i]-1)/2;
  }
  
  for(ll i=0;i<n;i++)
  {
  	cout<<sum-v2[v[i]-1]+1<<"\n";
  }
  
  return 0;
}
  

Measured memory_bytes: 5760
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <limits>
#include <cassert>
#include <tuple>

#define seq(i, n) for (int i = 0; i < (n); i++)
#define seq2(i, f, t) for (int i = (f); i < (t); i++)
#define rev(i, n) for (int i = (n); i >= 0; i--)
#define rev2(i, f, t) for (int i = (f); i >= (t); i--)
#define all(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;

int distnum(vector<int> p, vector<int> q){
    int sum2 = 0;
    for(int i=0;i<(int)p.size();i++){
        sum2 += abs(p[i]-q[i]) * abs(p[i]-q[i]);
    }
    double d = sqrt(sum2);
    return ceil(d)==floor(d);
}

int solve(int n,int d,vector<vector<int>> v) {
    int res=0;
    const int len=v.size();
    for (int i = 0; i < len; i++){
        for (int j = i+1; j < len; j++){
            res+=distnum(v[i], v[j]);
        }
    }
    return res;
}

int main() {
  #ifdef TEST
    cout << solve(3, 2,{{1,2},{5,5},{-2,8}})<<endl;
    assert(solve(3, 2,{{1,2},{5,5},{-2,8}})==1);
  #else
    int n,d;
    cin>>n>>d;
    vector<vector<int>> v;
    for(int i=0;i < n;i++){
        vector<int> p;
        for(int j=0; j<d;j++){
            int k;
            cin >> k;
            p.push_back(k);
        }
        v.push_back(p);
    }
    cout << solve(n,d,v) << endl;
  
  #endif

  return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

/*** MOD CALCULATION ***/

// const int MOD = 1e9+7;
const int MOD = 998244353;
const int MAX = 2'000'005;

ll addM(ll a, ll b){
	return ((a % MOD) + (b % MOD)) % MOD;
}

ll mulM(ll a, ll b){
	return ((a % MOD) * (b % MOD)) % MOD;
}

ll powM(ll a, ll b){
	if(b == 0) return 1;
  	else if(b == 1) return a % MOD;
  	else if(b%2==0) return mulM(powM(a, b/2), powM(a, b/2));
  	else return mulM(a, mulM(powM(a, (b-1)/2), powM(a, (b-1)/2)));
}

// b^{-1} = b^{p-2} (mod p)
// a/b = a*b^{p-2} (mod p)
ll divM(ll a, ll b){ 
  	return mulM(a, powM(b, MOD-2));
}

// n!, (n!)^{-1} のテーブル作成
ll fac[MAX], finv[MAX], inv[MAX];
void COMBinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    rep3(i,2,MAX-1){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COMB(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

/*** MOD CALCULATION ここまで ***/

void Main(){
    int n, k; cin >> n >> k;
    COMBinit();

    auto f = [&](int X, int Y, int T){
        return addM(COMB(X+Y, X), MOD - COMB(X+Y, X+T));
    };
    
    int ans = 0;
    rep3(R, (k+1)/2, k){
        int B = k - R;
        if(R < n) continue;
        if(R == B) ans = addM(ans, f(R, B - 1, B - n + 1));
        else ans = addM(ans, f(R, B, R - n + 1));
        // cout << R << "," << B << ": " << ans << endl;
    }

    cout << ans << endl;
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 50528
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;


struct union_find {
    vector<ll> par;
    vector<ll> rank;
    vector<ll> count;

    union_find(ll n) : par(n, 0), rank(n, 0), count(n, 1) {
        for(ll i = 0; i < n; ++i){ par.at(i) = i; }
    }

    ll find(ll x){
        if(par.at(x) == x){
            return x;
        }else{
            return par.at(x) = find(par.at(x));
        }
    }

    void unite(ll x, ll y){
        x = find(x);
        y = find(y);
        if(x == y){ return; }
        if(rank.at(x) < rank.at(y)){
            par.at(x) = y;
        }else{
            par.at(y) = x;
            if(rank.at(x) == rank.at(y)){
                rank.at(x)++;
            }
        }

        ll new_count = count.at(x) + count.at(y);
        count.at(find(x)) = new_count;
    }

    bool same(ll x, ll y){
        return find(x) == find(y);
    }

    ll size(ll x){
        return count.at(find(x));
    }
};

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

    vector<array<ll, 3>> xy(n);
    REP(i, n){
        cin >> xy.at(i).at(0) >> xy.at(i).at(1);
        xy.at(i).at(0)--;
        xy.at(i).at(1)--;
        xy.at(i).at(2) = i;
    }
    sort(ALL(xy));

    union_find uf(n);

    set<pair<ll, ll>> yi;

    for(const auto& s : xy){
        bool flg = false;
        for(auto it = yi.begin(); it != yi.end(); ){
            if(it->first > s.at(1)){
                break;
            }else{
                uf.unite(s.at(2), it->second);
                if(flg){
                    it = yi.erase(it);
                }else{
                    flg = true;
                    ++it;
                }
            }
        }
        if(!flg){
            yi.emplace(s.at(1), s.at(2));
        }
    }

    REP(i, n){
        cout << uf.size(i) << endl;
    }
    return 0;
}


Measured memory_bytes: 17196