akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int main(void){
    int c[1000001]={},a[200000],n, p[1000001]={},ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&a[i]);
        ++c[a[i]];
    }
    for(int i=2;i<1000001;++i){
        if(!p[i]){
            for(int j=i+i;j<1000001;j+=i) p[j] = 1;
        }
    }
    for(int i=2;i<1000001;++i){
        if(!p[i]){
            for(int j=1,jj=i;jj<1000001;++j,jj+=i) c[jj]+=c[j];
        }
    }
    for(int i=0;i<n;++i) if(c[a[i]] == 1) ++ans;
    printf("%d",ans);
}




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

int main()
{
    ll n;
    string ans;
    static const char table[] = "abcdefghijklmnopqrstuvwxyz";

    cin >> n;
    --n;
    ans = "";
    while (n >= 26) {
        ans += table[n % 26];
        n /= 26;
        --n;
    }
    ans += table[n];
    // 文字列の順番を逆にする
    reverse(ans.begin(), ans.end());

    cout << ans << endl;
}


Measured memory_bytes: 3628
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(ll i = 0; i < n; i++)

int main() {
	ll n, a, b;
	cin >> n >> a >> b;
	if (a > b) {
		cout << 0 << endl;
		return 0;
	}
	if (n == 1) {
		if (a == b) {
			cout << 1 << endl;
			return 0;
		}
		cout << 0 << endl;
		return 0;
	}
	ll min = a * (n - 1) + b;
	ll max = b * (n - 1) + a;
	cout << max - min + 1 << endl;
}

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

#define SENTINEL 2000000000

long int cnt=0;

typedef struct box{
	char a;
	int b;
} card;

void merge(card *A,int left,int mid,int right)//分割した配列を小さい順に結合
{
  int n1 = mid - left;
  int n2 = right - mid;
  card L[n1+1],R[n2+1];
  int k,i,j;
  for (i=0;i<n1;i++) {
  	L[i].a = A[left + i].a;
  	L[i].b = A[left + i].b;
  }
  for (i=0;i<n2;i++) {
  	R[i].a = A[mid + i].a;
  	R[i].b = A[mid + i].b;
  }
  L[n1].b = SENTINEL;//EOF
  R[n2].b = SENTINEL;//EOF
  i = 0;
  j = 0;
    
  for(k=left;k<right;k++){//iが左の要素番号,jが右の要素番号
    if(L[i].b<=R[j].b){//左が小さい場合
      A[k].a = L[i].a;
      A[k].b = L[i].b;
      i=i+1;
    }else{ //右が小さい場合
      A[k].a = R[j].a;
       A[k].b = R[j].b;
      if(L[i].b!=SENTINEL) cnt+=(n1-i);//SENTINELと比較する場合を除いて左側の未ソート部分の要素数をcntに加算
      j = j + 1;
    }
  }
}

void mergeSort(card *A,int left,int right)
{
  int mid,i;
  if(left+1<right){//二分探索のように左端が右端を超えたら終了
    mid = (left + right)/2;
    mergeSort(A, left, mid);//左半分で再帰
    mergeSort(A, mid, right);//右半分で再帰
    merge(A, left, mid, right);//結合
  }
}


int partition(card *A,int p,int r)
{
	int x = A[r].b;//基準値をxに格納
	int box,j,i = p-1;
	
	int k;
	
	char s;
	for( j = p ; j < r ; j++){//jがこれから探索する要素番号を示す
		if( A[j].b <= x){//xより小さければ
			i = i+1;//iをインクリメントする
			box=A[i].b;//xより大きくかつ最後に追加した要素と入れ替える
			s=A[i].a;
			A[i].b=A[j].b;
			A[i].a=A[j].a;
			A[j].b=box;
			A[j].a=s;
		}
	}
	box=A[i+1].b;//基準値をiの位置に格納する
	s=A[i+1].a;
	A[i+1].b=A[r].b;
	A[i+1].a=A[r].a;
	A[r].b=box;
	A[r].a=s;
	//for(k=p;k<r;k++) printf("%c %d\n",A[k].a,A[k].b);
	return i+1;
}


void quicksort(card *A,int p ,int r)
{
	int q;
	if(p<r){
		q=partition(A,p,r);
		quicksort(A,p,q-1);
		quicksort(A,q+1,r);
	}
}

int main(void)
{
	int i,n;
	card *A;
	card *B;
	int left,right;
	int check=0;
	scanf("%d",&n);
	A = (card*)malloc(sizeof(card)*n+1);
	B = (card*)malloc(sizeof(card)*n+1);
	for(i=0;i<n;i++) {
		scanf("%s",&A[i].a);
		scanf("%d",&A[i].b);
		B[i].a=A[i].a;
		B[i].b=A[i].b;
	}
	
	quicksort(A,0,n-1);
	 left=0;
    right=n;
	mergeSort(B,left,right);
	for(i=0;i<n;i++) if(A[i].a!=B[i].a) check=1;
	if(check==0)printf("Stable\n");
	else printf("Not stable\n");
	for(i=0;i<n;i++) printf("%c %d\n",A[i].a,A[i].b);
	free(A);
	free(B);
	return 0;
}


Measured memory_bytes: 3844
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	vector <int> a(3);
	for (int i =0 ; i <3;i++) cin >> a[i];
	sort(a.begin(), a.end());
	int cost = abs(a[1] - a[0]) + abs(a[2] - a[1]);
	cost =  min(cost, abs(a[2] - a[0]) + abs(a[1]-a[2]));
	cout << cost << endl;
	return 0;
}


Measured memory_bytes: 256
import sys

s = input()
t = input()

#print(s)
#print(t)

n = len(s)

dic = {}
dic2 = {}


for i in range(n):
    if s[i] in dic:
        if dic[s[i]] != t[i]:
            print("No")
            sys.exit()
            
    else:
        dic[s[i]] = t[i]
            
            
    if t[i] in dic2:
        if dic2[t[i]] != s[i]:
            print("No")
            sys.exit()
            
    else:
        dic2[t[i]] = s[i]
        
print("Yes")
        


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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int alle = 0;
  for(int i = 0; i < n; i++){
    if(s.at(i) == 'E') alle++;
  }
  
  int count = 0;
  int ans = 10000000;
  for(int i = 0; i < n; i++){
    int now = alle + count;
    if(s.at(i) == 'E'){
      now--;
      alle--;
    }
    ans = min(ans, now);
    if(s.at(i) == 'W'){
      count++;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int N; string S; string ss;
  cin >> N >> S;
  for(int i=0; i<N;++i){
    char x = S[i];
    while(i+1<N && S[i+1]==x) ++i;
    ss += x;
  }
  cout << ss.size();
}

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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N),B(N);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    ll ans =0;
    for(int i=N-1;i>=0;--i){
       
        A[i] += ans;
        // cerr << A[i] << endl;
        if(A[i]%B[i] ==0){
            continue;
        }
        ans += (B[i] -A[i]%B[i]);
    }
    cout << ans << endl;

    return 0;
}

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

int main() {
    int n;
    while (cin >> n and n) {
        vector<int> x(n);
        rep(i, n) cin >> x[i];
        sort(x.begin(), x.end());
        int ans=1e8;
        rep(i, n-1) {
            ans=min(ans, x[i+1]-x[i]);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int a,b,c;
  cin>>a>>b>>c;
  cout<<(a+b+c>21?"bust":"win")<<endl;
  return 0;
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        a,b,c = LI()
        s = set()
        s.add(0)
        t = 0
        r = -1
        for i in range(60):
            while t > c:
                c += 60
            if t <= c <= t+a:
                r = c
                break
            t += a + b

        rr.append(r)
        break

    return '\n'.join(map(str, rr))


print(main())




Measured memory_bytes: 9024
#include <bits/stdc++.h>
using namespace std;
void selectionsort(vector<int> &A, int N, int &count){
    for (int i=0; i<N; i++){
        int minj = i;
        for (int j=i; j<N; j++){
            if (A.at(j) < A.at(minj)){
                minj = j;
            }
        }
        if (A.at(i) != A.at(minj)) count += 1;
        int t = A.at(i);
        A.at(i) = A.at(minj);
        A.at(minj) = t;
    }
}

int main(){
    int N, count = 0;
    cin >> N;
    vector<int> Ai(N);
    for (int j=0; j<N; j++){
        cin >> Ai.at(j);
    }
    selectionsort(Ai, N, count);
    for (int j=0; j<N; j++){
        if (j != N-1) cout << Ai.at(j) << " ";
        else cout << Ai.at(j) << endl;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3116
N = int(input())
S = input()
halfN = int(N / 2)
#print(halfN)
#print(S[0:halfN])
#print(S[halfN:N])

if S[0:halfN] == S[halfN:N]:
  print('Yes')
elif halfN % 2 != 0:
  print('No')
else:
  print('No')

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

int main()
{
    int r, g, b;
    cin >> r >> g >> b;
    if ((r * 100 + g * 10 + b) % 4 == 0)
    {
       cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int N;
int k;
void dfs(long long n,char tag){
	if(n>N){
		return;
	}
	if(tag==7){
		k++;
	}
	dfs(n*10+3,tag|1);
	dfs(n*10+5,tag|2);
	dfs(n*10+7,tag|4);
}

int main(){
	cin>>N;
	k=0;
	dfs(0,0);
	cout<<k;
	return 0;
} 

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

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

const int MAXN = 1e4;

int n, ans, l[MAXN+10];
char s[MAXN+10][20];
int c1, c2, c3;

int main()
{
    int i, j;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%s", s[i]+1), l[i]=strlen(s[i]+1);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<l[i]; j++) if(s[i][j]=='A' && s[i][j+1]=='B') ans++;
        bool a=false, b=false;
        if(s[i][1]=='B') b=true;
        if(s[i][l[i]]=='A') a=true;

        if(a&&b) c1++;
        else if(a) c2++;
        else if(b) c3++;
    }
    if(c1!=0)
    {
        ans+=c1-1;
        if(c2!=0) ans++, c2--;
        if(c3!=0) ans++, c3--;
    }
    ans+=min(c2, c3);
    printf("%d", ans);
}


Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

const (
	initialBufSize = 10000
	maxBufSize     = 1000000
	mod            = 1e9 + 7
)

var (
	sc *bufio.Scanner = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, initialBufSize)
		sc.Buffer(buf, maxBufSize)
		sc.Split(bufio.ScanWords)
		return sc
	}()
)

func main() {
	N := getInt()
	W := getInt()
	ws := make([]int, N)
	vs := make([]int, N)
	for i := 0; i < N; i++ {
		ws[i] = getInt()
		vs[i] = getInt()
	}

	values := make([][]int, N+1)
	for i := 0; i < N+1; i++ {
		values[i] = make([]int, W+1)
	}
	for i := 0; i < N; i++ {
		for j := 0; j < W+1; j++ {
			if j < ws[i] {
				values[i+1][j] = values[i][j]
				continue
			}

			values[i+1][j] = max(values[i][j], values[i][j-ws[i]] + vs[i])
		}
	}

	fmt.Println(values[N][W])
}

type Graph struct {
	n     int
	edges [][]int
}

func NewGraph(n int) *Graph {
	g := &Graph{
		n:     n,
		edges: make([][]int, n),
	}
	return g
}

func (g *Graph) AddEdge(u, v int) {
	g.edges[v] = append(g.edges[v], u)
	g.edges[u] = append(g.edges[u], v)
}

func dfs(c int, edges [][]int, visited map[int]struct{}) {
	visited[c] = struct{}{}

	for _, v := range edges[c] {
		_, flag := visited[v]
		if flag {
			continue
		}
		dfs(v, edges, visited)
	}
}

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func powMod(n, p int) int {
	if p == 0 {
		return 1
	} else if p%2 == 0 {
		t := powMod(n, p/2)
		return calcMod(t * t)
	} else {
		return n * powMod(n, p-1)
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func printIntArray(array []int) {
	strArray := fmt.Sprint(array)
	fmt.Println(strArray[1 : len(strArray)-1])
}

func calcMod(x int) int {
	return x % mod
}


Measured memory_bytes: 81792
field =[]
mark = []

def check_row(n):
    counts = [field[n].count(i) for i in xrange(10)]
    for x,v in enumerate(field[n]):
        if counts[v] > 1:
            put(x,n)

def check_col(n):
    t_field = zip(*field)
    counts = [t_field[n].count(i) for i in xrange(10)]
    for y,v in enumerate(t_field[n]):
        if counts[v] > 1:
            put(n,y)

def check_sq(n):
    ltx,lty = 3*(n%3), (n/3)*3
    tmp = reduce(lambda a,b:a+b,[field[y][ltx:ltx+3]
                   for y in xrange(lty,lty+3)])
    counts = [tmp.count(i) for i in xrange(10)]
    for x in xrange(ltx,ltx+3):
        for y in xrange(lty,lty+3):
            if counts[field[y][x]] > 1:
                put(x,y)

def put(x,y):
    global mark
    mark[y][x] = "*"

N = input()
while True:
    N -= 1
    field = [map(int,raw_input().split()) for _ in xrange(9)]
    mark = [[" "]*9 for _ in xrange(9)]
    for i in xrange(9):
        check_row(i)
        check_col(i)
        check_sq(i)
    for m,f in zip(mark,field):
        print "".join(mm+str(ff) for mm,ff in zip(m,f))
    if N <= 0:
        break
    print

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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)

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

const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

int main(){
    ll N;
    cin >> N;
    ll A[N];
    rep(i,N) {
        ll a;
        cin >> a;
        A[i] = a;
    }
    vector<vector<ll>> dp(N,vector<ll>(2,-1e15));

    dp[1][0] = A[0]+A[1];
    dp[1][1] = -dp[1][0];
    rep(i,N-1) {
        if (i==0) continue;
        dp[i+1][0] = max(dp[i][0]+A[i+1],dp[i][1]+A[i+1]);
        dp[i+1][1] = max(dp[i][0]-A[i+1]-2*A[i],dp[i][1]-A[i+1]+2*A[i]);
    }

    cout << max(dp[N-1][0],dp[N-1][1]) << endl;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    ll total = 1;
    rep(i,N){
        if(A[i] == 0){
            cout << 0 << endl;
            return 0;
        }
    }
    rep(i,N){
       if(A[i]>1e18/total){
           cout << -1 << endl;
           return 0;
       }
       total *= A[i];
    }
    if(total <= 1000000000000000000) cout << total << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 4032
import sys
from operator import itemgetter
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(set(x), key=None, reverse=reverse)):
        zipped[xi] = i + 1
        unzipped[i + 1] = xi
    return zipped, unzipped


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


MOD = 998244353
n = int(input())
x_list = []
y_list = []
for i in range(n):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)
x_zipped, x_unzipped = compress_coordinate(x_list)
y_zipped, y_unzipped = compress_coordinate(y_list)

p = []
for i, (x, y) in enumerate(zip(x_list, y_list)):
    p.append((x_zipped[x], y_zipped[y], i))

info = [[0] * 5 for _ in range(n)]
p.sort(key=itemgetter(0))
# print(*p)
bit1 = BIT1(n)
for m, (px, py, idx) in enumerate(p):
    bit1.add(py, 1)
    s_left = bit1.sum(py) - 1
    s_right = (m + 1) - s_left - 1
    info[idx][2] = s_right
    info[idx][3] = s_left

p.sort(key=itemgetter(0), reverse=True)
# print(*p)

bit2 = BIT1(n)
for m, (px, py, idx) in enumerate(p):
    bit2.add(py, 1)
    s_left = bit2.sum(py) - 1
    s_right = (m + 1) - s_left - 1
    info[idx][1] = s_right
    info[idx][4] = s_left

ans = 0
for _, c1, c2, c3, c4 in info:
    c1 = pow(2, c1, MOD) - 1
    c2 = pow(2, c2, MOD) - 1
    c3 = pow(2, c3, MOD) - 1
    c4 = pow(2, c4, MOD) - 1
    ans += 1
    ans += c1 + c2 + c3 + c4
    ans += c1 * c3 * 2 + c2 * c4 * 2
    ans += c1 * c2 + c2 * c3 + c3 * c4 + c4 * c1
    ans += (c2 * c3 * c4 + c1 * c3 * c4 + c1 * c2 * c4 + c1 * c2 * c3) * 2
    ans += c1 * c2 * c3 * c4 * 2
    ans %= MOD

# print(*info, sep='\n')
print(ans)


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){

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

Node treeMaximum(Node x){

  while(x->right !=NIL){
    x=x->right;
  }
  return x;
    

}

Node treeSearch(Node u, int k){

  if(u==NIL ||k==u->key)
     return u;
  if(k<u->key)return treeSearch(u->left,k);
  else return treeSearch(u->right,k);
  
}

Node treeSuccessor(Node x){
  if(x->right !=NIL)
    return treeSuccessor(x->right);

  Node y;
  y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;

  }
      return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->left;
    }
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if(z->key<y->key)y->left=z;
  else y->right=z;



}

void inorder(Node u){

  if(u==NIL)return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);

  
}
void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
  

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 20448
#include"stdio.h"
#include"stdlib.h"
struct num
{
  int n;
  struct num *next;
};
int main()
{
  int n;
  int q;
  struct num *S;
  int *T;
  struct num *p;
  int i;
  int m;
  int C=0;
  S=(struct num*)malloc(sizeof(struct num));
  S->next=NULL;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&m);
      for(p=S;p->next!=NULL;p=p->next)
        {
          if(p->next->n==m)break;
        }
      if(p->next==NULL)
        {
          p->next=(struct num*)malloc(sizeof(struct num));
          p->next->n=m;
          p->next->next=NULL;
        }
    }
  scanf("%d",&q);
  T=(int*)malloc(sizeof(int)*q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&T[i]);
    }
  for(p=S->next;p!=NULL;p=p->next)
    {
      for(i=0;i<q;i++)
        {
          if(p->n==T[i])
            {
              C++;
              break;
            }
        }
    }
  printf("%d\n",C);
}



Measured memory_bytes: 2088
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rrep(i,n) for(int i=(int)n-1;i>=0;--i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

const int mod = 1000000007;

struct mint {
    long long x;
    mint(long long x=0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

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

    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    mint ans = 0;
    mint k = 1;
    for (int i = 0; i < 60; ++i) {
        vector<int> cnt(2);
        rep(j, n) {
            if (a[j] >> i & 1) cnt[1]++;
            else cnt[0]++;
        }
        ll now = 1LL * cnt[0] * cnt[1];
        ans += k * now;
        k *= 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 5556
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
#include<utility>
#include<queue>
#include <map>

using namespace std;

int main(){

	int n;
	cin>>n;
	int x[n];
	for(int i=0;i<n;i++)cin>>x[i];
	long long min=10000000,ans=0;
	for(int i=1;i<=100;i++){
		ans=0;
		for(int j=0;j<n;j++){
			ans+=(x[j]-i)*(x[j]-i);
		}
		if(ans<min)min=ans;
	}
	cout<<min;
	cout<<endl;

	return 0;
}


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

int main(){
  int n, a, b, x;
  int p[3] = {0};
  cin >> n >> a >> b;
  for( int i = 0; i < n; i++){
    cin >> x;
    if(x <= a){
      p[0]++;
    }else if(a < x && x <= b){
      p[1]++;
    }else{
      p[2]++;
    }
  }
  
  cout << min(p[0], min(p[1], p[2])) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int a,b,c,d,p,x,y,mn;
	scanf("%d %d %d %d %d",&a,&b,&c,&d,&p);
	x=a*p;
	if(p<=c)	{
		y=b;
	}
	else {
		y=b+(p-c)*d;
	}
	mn=min(x,y);
	printf("%d\n",mn);
	return 0;
}


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

int main() {
  long long int q,h,s,d,n,cost=0;
  cin>>q>>h>>s>>d>>n;
  if(min(min(8*q,d),min(4*h,2*s))==d){
    cost+=n/2*d;
    n=n%2;
    cost+=min(4*q,min(2*h,s))*n;
    cout<<cost<<endl;
    return 0;
  }
  cost+=min(4*q,min(2*h,s))*n;
  cout<<cost<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    n = INT()
    l = LIST()
    l.sort()
    ans = 0
    #print(l)

    for i in range(n-1):
        for j in range(i+1, n):
            low = l[i]
            high = l[j]

            p = bisect_left(l, low + high)
            #print('i:', i, 'j:', j, '→', max(0, p-j-1))
            ans += max(0, p - j - 1)

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5352
#include<bits/stdc++.h>
using namespace std;
int N,M;
vector<int> G[100005];
typedef long long ll;

int visited[100005];
bool flag;
ll cnt,A,B;

void dfs(int pos,int depth){
  cnt++;
  visited[pos]=depth%2;
  if(depth%2==0)A++;
  else B++;
  
  for(int to:G[pos]){
    if(visited[to]==-1){
      dfs(to,depth+1);
    }else{
      if( visited[to]%2 != (depth+1)%2 )flag=true;
    }
  }
}

ll ans=0;

int main(){
  cin>>N>>M;
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  ans-=M;
  
  memset(visited,-1,sizeof(visited));
  for(int i=0;i<N;i++){
    if(visited[i]!=-1)continue;
    cnt=A=B=0;
    flag=false;
    dfs(i,0);
    if(flag){
      ans+= ( cnt*(cnt-1))/2;
    }else{
      ans+= A*B;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 6912
#include <iostream>
#include <vector>
#include <map>
#include <utility>

using namespace std;

int main() {
    vector<vector<int> > A(3, vector<int>(3));
    map<int, pair<int, int> > mp;
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            cin >> A[i][j];
            mp[A[i][j]] = make_pair(i, j);
        }
    }
    
    vector<vector<bool> > C(3, vector<bool>(3, false));
    
    int N;
    cin >> N;
    for(int n=0; n<N; n++) {
        int b;
        cin >> b;
        if(mp.find(b)!=mp.end()) {
            C[mp[b].first][mp[b].second] = true;
        }
    }

    bool flag;
    for(int i=0; i<3; i++) {
        flag = true;
        for(int j=0; j<3; j++) {
            if(C[i][j]) {
                continue;
            } else {
                flag = false;
                break;
            }
        }
        if(flag) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    for(int i=0; i<3; i++) {
        flag = true;
        for(int j=0; j<3; j++) {
            if(C[j][i]) {
                continue;
            } else {
                flag = false;
                break;
            }
        }
        if(flag) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    flag = true;
    for(int j=0; j<3; j++) {
        if(C[j][j]) {
            continue;
        } else {
            flag = false;
            break;
        }
    }
    if(flag) {
        cout << "Yes" << endl;
        return 0;
    }
    
    flag = true;
    for(int j=0; j<3; j++) {
        if(C[j][2-j]) {
            continue;
        } else {
            flag = false;
            break;
        }
    }
    if(flag) {
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;


    return 0;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input part
    string s;
    cin >> s;
    int n = s.length();
    int k;
    cin >> k;

    // main part
    set<string> st;
    rep(i,n)
    {
        // kaishi mozi no sitei
        string tmps = "";
        for (int j=i;j<=min(i+k-1,n-1);j++)
        {
            tmps += s[j];
            st.insert(tmps);
        }
    }
    
    // output part
    auto itr = st.begin();

    rep(i,k-1) ++itr;
    cout << *itr << endl;
}


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

// #include <atcoder/all>

// #LIB#

using namespace std;
// using namespace atcoder;
using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#ifdef ONLINE_JUDGE
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');
#endif

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll ans = max({a * c, a * d, b * c, b * d});
  cout << ans << endl;
}


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

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

    vector<tuple<int, int, int>> plan(n);
    int t, x, y;
    for (auto i = 0; i < n; i++) {
        cin >> t >> x >> y;
        plan[i] = make_tuple(t, x, y);
    }

    int distance, time;
    distance = abs(get<1>(plan[0]) - 0) + abs(get<2>(plan[0]) - 0);
    time = get<0>(plan[0]) - 0;
//    cout << distance << " " << time << endl;
    if ((distance != time and abs(distance - time) % 2) or (distance > time)){
        cout << "No" << endl;
        return 0;
    }

    for (auto i = 1; i < n; i++) {
        distance = abs(get<1>(plan[i]) - get<1>(plan[i - 1]))
                  + abs(get<2>(plan[i]) - get<2>(plan[i - 1]));
        time = get<0>(plan[i]) - get<0>(plan[i - 1]);
//        cout << distance << " " << time << endl;
        if ((distance != time and abs(distance - time) % 2) or (distance > time)) {
            cout << "No" << endl;
            return 0;
        }

    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1408
n,m,x = map(int,input().split())
a = list(map(int,input().split()))
a.append(x)
a = sorted(a)
a = list(map(str,a))
b = a.index(str(x))
if b+1 <= len(a)/2:
  print(b)
else:
  print(m-b)

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

int main(){
  int n,k;
  cin>>n>>k;
  vector<int> p(n);
  rep(i,n) cin>>p[i];
  int ans=0;
  sort(p.begin(),p.end());
  rep(i,k) ans+=p[i];
  cout << ans << endl;
}

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

signed main() {
  int N, M; cin >> N >> M;
  
  if(N > 1 && M > 1) cout << N*M-2*N-2*M+4 << endl;
  if(N > 1 && M == 1) cout << N-2 << endl;
  if(N == 1 && M > 1) cout << M-2 << endl;
  if(N == 1 && M == 1) cout << 1 << endl;

}

Measured memory_bytes: 3604
X,Y = map (int, input ().split ())
p = 0
if X == 1:
  p += 300000
elif X == 2:
  p += 200000
elif X == 3:
  p += 100000
if Y == 1:
  p += 300000
elif Y == 2:
  p += 200000
elif Y == 3:
  p += 100000
if X == Y == 1:
  p += 400000
print (p)

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

// #define DEBUG

struct T {
	int key, val, sum;
	int siz, fix;
	T *l, *r;
	T(int k, int v) {
		key = k; val = sum = v;
		siz = 1; fix = rand();
		l = r = NULL;
	}
	void upd() {
		siz = 1;
		if (l) siz += l -> siz;
		if (r) siz += r -> siz;
		sum = val;
		if (l) sum += l -> sum;
		if (r) sum += r -> sum;
	}
};

void split(T *x, int v, T *&a, T *&b) {
	if (!x) {a = b = NULL; return ;}
	if (x -> key <= v) {
		a = x; split(x -> r, v, a -> r, b);
		a -> upd();
	} else {
		b = x; split(x -> l, v, a, b -> l);
		b -> upd();
	}
}

T *merge(T *a, T *b) {
	if (!a || !b) return a ? a : b;
	if (a -> fix < b -> fix) {
		a -> r = merge(a -> r, b);
		a -> upd(); return a;
	} else {
		b -> l = merge(a, b -> l);
		b -> upd(); return b;
	}
}

void _combine(T *&a, T *b) {
	if (!b) return ;
	_combine(a, b -> l);
	_combine(a, b -> r);
	T *l, *m, *r;
	split(a, b -> key, l, r);
	split(l, b -> key - 1, l, m);
	if (!m) m = new T(b -> key, b -> val);
	else m -> val += b -> val, m -> sum += b -> val;
	a = merge(merge(l, m), r);
}

T *combine(T *a, T *b) {
	if (!a || !b) return a ? a : b;
	if (a -> siz < b -> siz) swap(a, b);
	_combine(a, b);
	return a;
}

const int N = 2e5 + 5;
int n;
vector <int> g[N];
T *f[N];
int fmx[N], fmx2[N];
vector <int> mx;
int ans[N];

void prt(T *x) {
	if (!x) return ;
	prt(x -> l);
	cerr << "(" << x -> key << ", " << x -> val << ") ";
	prt(x -> r);
}

void dfs(int u, int p) {
	f[u] = new T(0, 1);
	fmx[u] = 1;
	for (int i = 0; i < g[u].size(); ++ i) {
		int v = g[u][i];
		if (v == p) continue;
		mx.push_back(max(mx[mx.size() - 1], u));
		dfs(v, u);
		mx.resize(mx.size() - 1);
		fmx[u] += fmx2[v];
		f[u] = combine(f[u], f[v]);
	}
	T *l, *m, *r;
	split(f[u], u, l, r);
	m = new T(u, l ? l -> sum : 0);
	f[u] = merge(m, r);
	if (mx.size() >= 2) {
		split(f[u], mx[mx.size() - 2], l, r);
		if (l) fmx2[u] = l -> sum;
		f[u] = merge(l, r);
	}
	// cerr << u << ": " << fmx[u] << ", " << fmx2[u] << endl;
}

void dfsans(int u, int p) {
	if (u) ans[u] = ans[p] - fmx2[u] + fmx[u];
	for (int i = 0; i < g[u].size(); ++ i) {
		int v = g[u][i];
		if (v == p) continue;
		dfsans(v, u);
	}
}

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


Measured memory_bytes: 79104
#include<stdio.h>

int calc(int x){
    int ret=0;
    while(x%100==0){
        x/=100;
        ret++;
    }
    return ret;
}

int main(void){
    int d,n,count=0,num=1;
    scanf("%d%d",&d,&n);
    while(count<n){
        if(calc(num)==d){
            count++;
        }
        ++num;
    }
    printf("%d\n",num-1);
    return 0;
}


Measured memory_bytes: 128
/*
cat <<EOF >mistaken-paste
*/

#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
#define _USE_MATH_DEFINES

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

#define BIG 2000000007
#define VERYBIG 200000000000007LL

#define MOD 1000000007
#define FOD  998244353
typedef uint64_t ull;
typedef  int64_t sll;

#define N_MAX 200000
#define M_MAX 200000


ull n, m;

ull bitpow (ull a, ull x, ull modulo) {
	ull result = 1;
	while (x) {
		if (x & 1) {
			result *= a;
			result %= modulo;
		}
		x /= 2;
		a = (a * a) % modulo;
	}
	return result;
}


sll a[N_MAX];
sll b[N_MAX];

char s[N_MAX + 1];


ull dp[N_MAX + 1][3][3];

ull solve () {
	sll i, j, ki, li;
	// ull result = 0;
	sll result = 0;
	double dresult = 0;
	// ull maybe = 0;
	sll maybe = 0;
	// ull sum = 0;
	sll sum = 0;
	sll item;
	ull *dpcell;

	n = strlen(s);
	if (n == 3) {
		if (s[0] == s[2]) {
			if (s[0] == s[1]) {
				result = 1;
			} else {
				result = 7;
			}
		} else {
			if (s[0] == s[1] || s[1] == s[2]) {
				result = 6;
			} else {
				result = 3;
			}
		}
		goto success;
	}

	bool ndiff = true;
	bool nsame = true;
	for (i = 0; i < n; i++) {
		if (i && s[i - 1] != s[i]) ndiff = false;
		if (i && s[i - 1] == s[i]) nsame = false;

		sum = (sum + (s[i] - 'a')) % 3;
	}
	if (ndiff) {
		result = 1;
		goto success;
	}

	for (i = 0; i < n; i++) { // length
		for (j = 0; j < 3; j++) { // sum
			for (ki = 0; ki < 3; ki++) { // last
				if (i == 0) {
					dp[i][j][ki] = (j == ki ? 1 : 0);
					continue;
				}
				ull befs = (3 + j - ki) % 3;

				dp[i][j][ki] = dp[i - 1][befs][(ki + 1) % 3] + dp[i - 1][befs][(ki + 2) % 3];
				dp[i][j][ki] %= FOD;
			}
		}
	}

	result = (nsame ? (FOD - 1) : 0);
	for (ki = 0; ki < 3; ki++) {
		result += dp[n - 1][sum][ki];
		result %= FOD;
	}
	result = (FOD + bitpow(3, n - 1, FOD) - result) % FOD;

	printf("%lld\n", result);

	return 0;

	success:
	printf("%llu\n", result);
	return 0;
}

int32_t main (void) {
	scanf("%s", s);

	solve();

	return 0;
}


Measured memory_bytes: 15488
#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
using namespace std;

int main() {
	int n, a,s;
	cin >> n >> a;
	s = n % 500;
	if (a < s) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n;
	int min, max;
	double sum;

	scanf("%d", &n);

	int num;
	int pointer=0;
	scanf("%d", &num);
	min=max=sum=num;
	for(int i=0; i<n-1; i++){
		scanf("%d", &num);
		if(min>num) min=num;
		if(max<num) max=num;
		sum+=num;
	}

	printf("%d %d %.0lf\n", min, max, sum);

	return 0;
}

Measured memory_bytes: 1060
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)

int N;
int d[101];

int mochis[101];

int main() {
  scanf("%d", &N);
  rep(i, N) {
    scanf("%d", &d[i]);
    mochis[d[i]]++;
  }
  int count = 0;
  rep(i, 101) if (mochis[i]) count++;
  printf("%d\n", count);
}


Measured memory_bytes: 256
#include <stdio.h>
#define INFTY 1000000
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define True 1
int n;
int M[100][100];

void dijkstra(){
  int minv,u,i,j;
  int d[100],color[100];

  for(i=0;i<n;i++){
    d[i]=INFTY;
    color[i]=WHITE;
  }
  d[0]=0;
  color[0]=GRAY;
  while(True){
    minv=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && color[i]!=BLACK){
        u=i;
        minv=d[i];
      }
    }
    if(u==-1) break;
    color[u]=BLACK;
    for(j=0;j<n;j++){
      if(color[j]!=BLACK && M[u][j]!=INFTY){
        if(d[j]>d[u]+M[u][j]){
          d[j]=d[u]+M[u][j];
          color[j]=GRAY;
        }
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d %d\n",i,(d[i]==INFTY)? -1:d[i]);
  }
}

int main(int argc, char const *argv[]) {
  int i,j,a,b,u,k;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=INFTY;
    }
  }
  for (i = 0; i < n; i++) {
    scanf("%d %d",&u,&k);
    for ( j = 0; j < k; j++) {
      scanf("%d %d",&a,&b);
      M[u][a]=b;
    }
  }
  dijkstra();
  return 0;
}

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

using i32 = int_fast32_t;
using i64 = int_fast64_t;

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

    map<char, i64> c;
    for (auto& e : s) c[e]++;

    i64 ans = c['R'] * c['G'] * c['B'];
    for (i32 d = 1; d < n; d++) {
        for (i32 i = d; i + d < n; i++) {
            if (s[i-d] != s[i] && s[i] != s[i+d] && s[i+d] != s[i-d]) ans--;
        }
    }

    cout << ans << endl;
}


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

int main()
{
    string s1, s2, s3;
    char dif = 'A' - 'a';
    cin >> s1 >> s2 >> s3;
    char s11 = s1[0] + dif;
    char s22 = s2[0] + dif;
    char s33 = s3[0] + dif;
    cout << s11 << s22 << s33 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
const int inf=1e9+7;

int main(){
    int n;cin>>n;
    vin a(n);
    rep(i,n)cin>>a[i];
    rep(i,n-1){
        a[i+1]=__gcd(a[i],a[i+1]);
    }
    cout<<a[n-1]<<endl;
}

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

int main(){
    int n; //dataset number
    std::string before = "Hoshino";
    std::string after = "Hoshina";

    std::cin >> n;
    std::cin.ignore();
    
    for(int i = 0; i < n; ++i){
        std::string str;
        std::getline(std::cin, str);
        std::string::size_type pos = str.find(before);
        while(pos != std::string::npos){
            str.replace(pos, before.size(), after);
            pos = str.find(before, pos + after.size());
        }
	std::cout << str << std::endl;

    }
    return 0;
}

Measured memory_bytes: 3008
#include <stdio.h>

static int a[200001] = {0}, p[200001] = {0};

int main(int argc, char** argv)
{
	int n, i, x;
	int sum = 0;

	scanf("%d", &n);
	for(i=0; i<n; ++i){
		scanf("%d", a + (i + 1));
	}
	for(x = n; x > 0; --x){
		p[x] += a[x];
		for(i=x+x; i<=n; i+=x){
			p[x] += p[i];
		}
		p[x] %= 2;
		sum += p[x];
	}
	printf("%d\n", sum);


	for(i = 1; i <= n; ++i){
		if(p[i]>0){
			printf("%d", i);
			--sum;
			if(sum > 0){
				printf(" ");
			} else {
				printf("\n");
				break;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 2432
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int inf=1e9+7;
int dp[100000][3];
signed main(){
    int n,k,r,s,p;
    string t;
    cin>>n>>k>>r>>s>>p>>t;
    for(int i=0;i<n;i++){
        if(i<k){
            switch(t[i]){
            case'r':
                dp[i][2]=p;
                break;
            case's':
                dp[i][0]=r;
                break;
            case'p':
                dp[i][1]=s;
            }
        }else{
            dp[i][0]=dp[i][1]=dp[i][2]=max({dp[i-k][0],dp[i-k][1],dp[i-k][2]});
            switch(t[i]){
            case'r':
                dp[i][2]=max(dp[i-k][0],dp[i-k][1])+p;
                break;
            case's':
                dp[i][0]=max(dp[i-k][1],dp[i-k][2])+r;
                break;
            case'p':
                dp[i][1]=max(dp[i-k][0],dp[i-k][2])+s;
            }
        }
    }
    int sum=0;
    for(int i=n-k;i<n;i++)
        sum+=max({dp[i][0],dp[i][1],dp[i][2]});
    cout<<sum<<endl;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int64_t N, K;
  cin >> N >> K;
  int64_t A = N % K;
  int64_t B = K - A;
  if (A < B) {
    cout << A << endl;
  }
  else {
    cout << B << endl;
  }
}

Measured memory_bytes: 3584
/*AC,WA,TLE,REの数を数える
093876*/
#include<stdio.h>

int main(void){
    
    char status[5];
    int num;
    int AC = 0;
    int WA = 0;
    int TLE = 0;
    int RE = 0;

    scanf("%d",&num);
    for(int i = 0;i < num;i++){
        scanf("%s",status);
        if(status[0] == 'A'){
            AC++;
        }else if(status[0] == 'W'){
            WA++;
        }else if(status[0] == 'T'){
            TLE++;
        }else if(status[0] == 'R'){
            RE++;
        }else{
            continue;
        }
        
    }
    printf("AC x %d\n",AC);
    printf("WA x %d\n",WA);
    printf("TLE x %d\n",TLE);
    printf("RE x %d\n",RE);
    return 0;
}

Measured memory_bytes: 1704
import java.io.IOException;
import java.util.NoSuchElementException;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            FastScanner fs = new FastScanner();

            int N = fs.nextInt();
            int A = fs.nextInt();
            System.out.println(N % 500 <= A ? "Yes" : "No");
        }
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
        if (hasNextByte()) return buffer[ptr++];
        else return -1;
    }
    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
        while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
        return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if(b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x[ohara],y[ohara],sum,pos,k,xsum=0,ysum=0;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n>>m;
    rep(i,n)cin>>x[i];
    rep(i,m)cin>>y[i];
    rep(i,n-1){
        ll kaisuu=(i+1)*(n-i-1);
        (xsum+=(x[i+1]-x[i])*kaisuu)%=MOD;
    }
    rep(i,m-1){
        ll kaisuu=(i+1)*(m-i-1);
        (ysum+=(y[i+1]-y[i])*kaisuu)%=MOD;
    }
    ans=(xsum*ysum)%MOD;
    Cout(ans);
    return 0;
}


Measured memory_bytes: 5120