akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
struct Node{
	int key;
	Node *prev,*next;
};
Node *nil;

Node* listSearch(int key){
	Node *cur = nil->next;

	while( cur != nil && cur->key != key){
		cur = cur->next;
	}
	return cur;
}
void init(){
	nil = (Node*)malloc(sizeof(Node));
	nil->next = nil;
	nil->prev = nil;
}
void printList(){
	Node *cur = nil->next;
	int isf = 0;
	while( 1 ){
		if(cur == nil) break;
		if(isf++ > 0) printf(" ");
		printf("%d",cur->key);
		cur = cur->next;
	}
	printf("\n");
}
void deleteNode(Node *t){
	if( t == nil) return;
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t);
}
void deleteFirst(){
	deleteNode(nil->next);
}
void deleteLast(){
	deleteNode(nil->prev);
}
void deleteKey(int key){
	deleteNode(listSearch(key));
}
void insert(int key){
	Node *x = (Node*)malloc(sizeof(Node));
	x->key = key;
	x->next = nil->next;
	nil->next->prev = x;
	nil->next = x;
	x->prev = nil;
}

int main(){
	int key,n,i;
	int size = 0;
	int x;
	char command[20];
	int np=0,nd=0;

	scanf("%d",&n);
	init();
	for(int i = 0;i < n;i++){
		scanf("%s%d",command,&x);
		if(command[0] == 'i'){
			insert(x);
		}else if(command[0] == 'd'){
			if(strlen(command) > 6){
				if(command[6] == 'F') deleteFirst();
				else if(command[6] == 'L') deleteLast();
			}else{
				deleteKey(x);
				nd++;
			}
			size--;
		}
	}
	printList();

	return 0;
}

Measured memory_bytes: 33952
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <math.h>
#include <cmath>
#include <set>   

using namespace std;


int main() {

	int x, y;
	cin >> x >> y;
	
	if (x + y > 9) {
		cout << "error" << endl;
	}
	else {
		cout << x + y << endl;

	}

}

Measured memory_bytes: 256
def resolve():
    '''
    code here
    '''
    Sd = input()
    T = input()

    r_Sd = Sd[::-1]
    r_T = T[::-1]

    def chk(a, b):
        res = ''
        for j in range(len(b)):
            if a[j] == '?' or a[j] == b[j]:
                res += b[j]
            else:
                return False
        else:
            return res 

    if len(Sd) >= len(T):
        for i in range(len(Sd)- len(T)+1):
            temp_words = r_Sd[i:i+len(T)+1]
            res = r_Sd[:i]
            
            temp = chk(temp_words, r_T)
            if temp:
                res = res + temp + r_Sd[i+len(T):]                
                print(res.replace('?', 'a')[::-1])
                break
        else:
            print('UNRESTORABLE')
    else:
        print('UNRESTORABLE')

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(1000000)


def dfs(s):
    if len(s) == n:
        print(s)
        return
    kind = len(set(s))
    for i in range(kind + 1):
        dfs(s + chr(ord('a') + i))


n = int(input())
dfs('')


Measured memory_bytes: 4412
#int でsplitを使う場合はmap関数を利用しなければならない
H,N = map(int,input().split())
li=[]
x=[]
for i in range(N):
    A,B = map(int,input().split())
    x.append(A)
    li.append([A,B])
dp = [10**9]*(H+max(x))
dp[0] = 0
for i in range(1,len(dp)):
    dp[i] = min(dp[i-a] + b for a,b in li)
print(min(dp[H:]))


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a, b;
	cin>>n;
	if(n==1){
		cout<<"Hello World"<<'\n';
		return 0;
	}
	else{
		cin>>a>>b;
		cout<<a+b<<'\n';
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
       int a = sc.nextInt();
       int b = sc.nextInt(); 
       int c = sc.nextInt();
       
        int tmp;
        if(a>b){
            tmp = b;
            b = a;
            a = tmp;
        }
        if(a>c){
            tmp = c;
            c = a;
            a = tmp;
        }
        if(b>c){
            tmp = c;
            c = b;
            b = tmp;
        }
        
        System.out.println(a+" "+b+" "+c);
        
    }
}


Measured memory_bytes: 26408
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)

using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>> N;
    int p[N];
    rep(i,0,N) cin>>p[i];
    sort(p,p+N);
    int ans=0;
    rep(i,0,N) ans+=p[i];
    ans-=p[N-1]/2;
    cout << ans<<"\n";
}



Measured memory_bytes: 256
import math
from decimal import Decimal

A,B,H,M = input().split()
A,B,H,M = int(A),int(B),int(H),int(M)

ans = Decimal(math.sqrt((A ** 2) + (B ** 2) - (2 * A * B * math.cos(math.radians((6 * M) - (30 * H) - (M / 2))))))

print(ans)

Measured memory_bytes: 10328
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int nmax = 100100;
int A,B,C;
int a[nmax];

void read(){
    cin >> A >> B >> C;
    int z = max(A, max(B, C));
    int s = A + B + C;
    while( (z*3 - s) % 2 !=  0)
    {
        z+=1;
    }
    cout << (z*3-s)/2 << endl;
}

void solve(){

}

int main(){
    read();
    solve();
}

Measured memory_bytes: 256
def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  if 0 in A:
      print(0)
      return
    
  prod = 1
  for a in A:
      prod *= a
      if prod > 1000000000000000000:
          print(-1)
          return
        
  print(prod)
  
main ()

Measured memory_bytes: 21712
n = int(input())
a = list(sorted(list(map(int,input().split()))))
b = list(sorted(list(map(int,input().split()))))
c = list(sorted(list(map(int,input().split()))))

def bs_left(ls,target):
    low, high = 0, len(ls)
    while low < high:
        mid = (low+high) // 2
        if ls[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

def bs_right(ls,target):
    low, high = 0, len(ls)
    while low < high:
        mid = (low+high) // 2
        if target < ls[mid]:
            high = mid
        else:
            low = mid + 1
    return low

ans = 0
for i in b:
    ans += (bs_left(a,i)*(n-bs_right(c,i)))

print(ans)

Measured memory_bytes: 23584
/**
  *  Worg
  */
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

int main() {
	int n, m; std::cin >> n >> m;
	std::vector<std::vector<int>> graph(n);
	std::vector<int> degree(n, 0), dp(n, 0);

	for (int i = 0; i < m; i++) {
		int u, v; std::cin >> u >> v;
		u--; v--;
		graph[u].push_back(v);
		degree[v] += 1;
	}

	std::queue<int> q;
	for (int i = 0; i < n; i++) {
		if (!degree[i]) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int node = q.front(); q.pop();

		for (auto& x: graph[node]) {
			degree[x] -= 1;
			dp[x] = std::max(dp[x], dp[node] + 1);

			if (degree[x] == 0) {
				q.push(x);
			}
		}
	}

	int answer = 0;
	for (int i = 0; i < n; i++) {
		answer = std::max(answer, dp[i]);
	}
	std::cout << answer << "\n";
	return 0;
}

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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;
typedef tuple<long long, long long, long long> tllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
bool compTuple(const tllint& arg1, const tllint& arg2) { return get<2>(arg1) > get<2>(arg2); }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

int main(void) {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for(int in=0;in<n;in++) {
        cin >> a[in];
    }
    for(int in=0;in<n;in++) {
        if(in<k) continue;
        if(a[in-k]<a[in]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

const int INF = 99999999;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int H, W;
vector<string> s;

bool inside(int x, int y) {
    return 0 <= x && x < H && 0 <= y && y < W;
}

int bfs(int sx, int sy) {
    queue<P> que;
    que.push(P(sx, sy));
    vector<vector<int>> d(H, vector<int>(W, INF));
    d[sx][sy] = 0;
    int ans = 0;

    while (!que.empty()) {
        P p = que.front(); que.pop();
        ans++;

        rep(k, 4) {
            int nx = p.first + dx[k], ny = p.second + dy[k];

            if (inside(nx, ny) && s[nx][ny] != '#' && d[nx][ny] == INF) {
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    return ans;
}

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

    while (cin >> W >> H, W) {
        s.clear();
        s.resize(H);
        int sx, sy;
        rep(i, H) {
            cin >> s[i];
            rep(j, W) {
                if (s[i][j] == '@') {
                    sx = i, sy = j;
                }
            }
        }
        cout << bfs(sx, sy) << endl;
    }

}

Measured memory_bytes: 3092
package main

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

var sc = bufio.NewScanner(os.Stdin)

var maxlist = []int{}
var minlist = []int{}

var RANK = 400

// get next int value
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

// main calc
func calc() {
	sc.Split(bufio.ScanWords)
	n := nextInt()

	for i := 0; i < n; i++ {
		a := nextInt()
		rank := a / 400
		if rank > 7 {
			maxlist = append(maxlist, len(maxlist)+8)
		} else {
			if assoc(rank, maxlist) == -1 {
				maxlist = append(maxlist, rank)
				minlist = append(minlist, rank)
			}
		}
	}
}

// list finder
func assoc(i int, list []int) int {
	ans := -1

	for _, v := range list {
		if v == i {
			ans = v
		}
	}
	return ans
}

// main
func main() {
	calc()
	if len(minlist) == 0 {
		minlist = append(minlist, 1)
	}
	fmt.Print(len(minlist), len(maxlist))
}


Measured memory_bytes: 640
def dfs(A):
    if len(A) == n+1:
        p = 0
        for i in range(q):
            if A[b[i]]-A[a[i]] == c[i]:
                p += d[i]
        global ans
        if p > ans:
            ans = p
        return
    num = A[-1]
    global m
    while num <= m:
        dfs(A[:]+[num])
        num += 1
                    

if __name__ == "__main__":
    n, m, q = map(int, input().split())
    a, b, c, d = [None]*q, [None]*q, [None]*q, [None]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    ans = 0
    dfs([1])
    print(ans)

Measured memory_bytes: 78616
from collections import defaultdict

N = int(input())
cnt = defaultdict(int)
for _ in range(N):
    s = [c for c in input()]
    s.sort()
    a = ''.join(s)
    cnt[a] += 1

ans = 0
for c, f in cnt.items():
    ans += f * (f - 1) // 2
print(ans)

Measured memory_bytes: 18236
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n) for (int i = n; 0<i;i--)
#define print(out) cout<< out  << "\n";
#define mod 1000000007
const int INF = 1e8;
typedef pair<int,int> P;

int main(){
  ll L,R,R2,ans=2018;cin>>L>>R;
  R2=min(L+2019,R);
  for(ll i=L;i<R2+1;i++){
    for(ll j=i+1;j<R2+1;j++){
      ans=min(ans,(i*j)%2019);
    }
  }
  print(ans)

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  int a, b, h;
  cin >> a >> b >> h;
  cout << (a+b)*h/2 << endl;
  return 0;
}

Measured memory_bytes: 256
import numpy as np

N, A, B, C, D = map(int, input().split())
A, B, C, D = A-1, B-1, C-1, D-1
S = input()

reachable_C = np.full(N+2, False, np.bool)
reachable_D = np.full(N+2, False, np.bool)

reachable_C[C] = True
reachable_D[D] = True

for i in range(N)[::-1]:
	if S[i] == '#':
		continue
	
	if reachable_C[i+1] or reachable_C[i+2]:
		reachable_C[i] = True
	if reachable_D[i+1] or reachable_D[i+2]:
		reachable_D[i] = True

l = max(A, B)
r = min(C, D) + 1

print('Yes'
	if reachable_C[A]
		and reachable_D[B]
		and (
			(A < B and C < D or B < A and D < C)
			or "..." in S[l-1:r+1])
	else 'No')


Measured memory_bytes: 21628
a,b,k = map(int, input().split())
#print(l)
c = b-a+1

x = []
if k*2 > c:
    for i in range(a, b+1):
        x.append(i)
else:
    for j in range(a, a+k):
        x.append(j)
    for j in range(b-k+1, b+1):
        x.append(j)

print(*sorted(x), sep='\n')


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long k;
    cin>>k;
    queue<long long> q;
    for(int i=1;i<=9;i++) q.push(i);
    while(!q.empty())
    {
        long long x=q.front();
        q.pop();
        k--;
        if(k==0)
        {
            cout<<x<<endl;
            return 0;
        }
        for(int i=x%10-1;i<=x%10+1;i++)
        {
            if(i<0||i>=10) continue;
            q.push(x*10+(long long)i);
        }
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#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--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main()
{
	int r;
	cin >> r;
	cout << 3*r*r << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdlib>

using namespace std;

struct Bri
{
    int a;
    int b;
};

int main()
{
    int n, m;
    cin >> n >> m;
    
    vector<Bri> v(m);
    for(int i = 0; i < m; i++)
    {
        cin >> v[i].a >> v[i].b;
    }

    sort(v.begin(), v.end(), [](const Bri &x, const Bri &y){return x.b < y.b;});
    
    vector<int> tmp;
    tmp.push_back(v[0].b - 1);
    int ans = 1;
    int cnt = 0;
    while(1)
    {
        bool flag = true;
        for(int i = 0; i < m; i++)
        {
            bool flag2 = true;
            for(int j = 0; j < tmp.size(); j++)
            {
                if(v[i].a <= tmp[j] && v[i].b > tmp[j])
                {
                    break;
                }
                if(j == tmp.size() - 1)
                {
                    flag2 = false;
                }
            }
            
            if(flag2 == false)
            {
                flag = false;
                ans++;
                tmp.push_back(v[i].b - 1);
                break;
            }
        }      
        
        if(flag == true)
        {
            break;
        }
    }
        
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x=1,c=0;
		int N = sc.nextInt();
		int[] a = new int [N+1];
		a[0]=0;
		for(int i=1;i<=N;i++) {
			a[i]=sc.nextInt();
		}
		for(;;) {
			if(a[x]==2) {
				c++;
				break;
			}
			else if(N<c) {
				c=-1;
				break;
			}
			else {
				c++;
				x=a[x];
			}
		}
		System.out.print(c);
		sc.close();
	}
}

Measured memory_bytes: 50592
n,l = map(int, input().split())

t = []
for i in range(n):
    t.append(i+l)
max = sum(t)

d = 10**9
ans = 0
for i in range(n):
    if d >= abs(max-(max-t[i])):
        ans = max-t[i]
        d = abs(max-(max-t[i]))

print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;

signed main() {
	int H, W;
	cin >> H >> W;
	vector<vector<string>>S(H, vector<string>(W));
	rep(i, H)rep(j, W)cin >> S[i][j];
	rep(i, H)rep(j, W) {
		if (S[i][j] == "snuke") {
			char ans = 'A' + j;
			cout << ans << i + 1;
		}
	}
}

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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = rbegin(s); i != rend(s); ++i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.ne(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }
template<class A, int N, class T>
void fillArray(A(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); }

class UnionFind {
public:
    UnionFind() :data(0) {}
    UnionFind(int size) : data(size, -1) { }
    void resize(int size) { *this = { size }; }
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) std::swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
private:
    std::vector<int> data;
};

int n, m;
ll a[100005];
vector<ll> b[100005];
void solve() {
    cin >> n >> m;
    rep(i, n) cin >> a[i];

    UnionFind uf(n);
    rep(i, m) {
        int x, y;
        cin >> x >> y;
        uf.unite(x, y);
    }

    rep(i, n) {
        auto r = uf.root(i);
        b[r].push_back(a[i]);
    }

    int cnt = 0;
    ll ans = 0;
    vector<ll> v;
    rep(i, n) {
        if (!b[i].empty()) {
            ++cnt;
            all(sort, b[i]);
            ans += b[i][0];
            reps(j, b[i].size() - 1) v.push_back(b[i][j]);
        }
    }

    if (cnt == 1) {
        cout << 0 << endn;
        return;
    }

    if ((cnt - 1) * 2 > n) {
        cout << "Impossible" << endn;
        return;
    }

    all(sort, v);
    rep(i, cnt - 2) ans += v[i];

    cout << ans << endn;
}

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


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

using namespace std;

int main()
{
	const string eot = "END_OF_TEXT";
	string d, w;

	cin >> d;
	unsigned int ans = 0;
	while (cin >> w) {
		if (w == eot)
			break;

		for (unsigned int i = 0; i < w.length(); ++i)
			w[i] = tolower(w[i]);
		if (w == d)
			ans++;
	}

	cout << ans << endl;

	return 0;
}



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

double dp[3010][3010];
double p[3010];

int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i];
    dp[0][0]=1.0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=dp[i-1][j]*(1-p[i]);
            if(j)dp[i][j]+=dp[i-1][j-1]*p[i];
        }
    }
    double ans=0.0;
    for(int i=(n+1)/2;i<=n;i++)ans+=dp[n][i];
    cout<<fixed<<setprecision(10)<<ans<<endl;
}


Measured memory_bytes: 70784
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let mut t: Graph = Graph::new(n);
    for i in 0..n - 1 {
        let a: usize = scan(tokens);
        let b: usize = scan(tokens);
        t.add_edge(a - 1, b - 1, i);
    }
    t.solve();
}

struct Graph {
    edges: Vec<Vec<(usize, usize)>>,
    colors: Vec<usize>,
}

impl Graph {
    fn new(n: usize) -> Graph {
        Graph {
            edges: vec![Vec::new(); n],
            colors: vec![0; n - 1],
        }
    }
    fn add_edge(&mut self, i: usize, j: usize, e: usize) {
        self.edges[i].push((j, e));
        self.edges[j].push((i, e));
    }
    fn solve(&mut self) {
        let k = self.edges.iter().map(|es| es.len()).max().unwrap();
        self.dfs(0, 0);
        println!("{}", k);
        for &c in &self.colors {
            println!("{}", c);
        }
    }
    fn dfs(&mut self, i: usize, c0: usize) {
        let mut c = 0;
        for (j, e) in self.edges[i].clone() {
            if self.colors[e] != 0 {
                continue;
            }
            c += 1;
            if c == c0 {
                c += 1;
            }
            self.colors[e] = c;
            self.dfs(j, c);
        }
    }
}


Measured memory_bytes: 17148
from collections import defaultdict

n = int(input())

s_dict = defaultdict(int)
for _ in range(n):
    s = input()
    s_dict[s] += 1

count_max = max(s_dict.values())
s_list = sorted([s for s, count in s_dict.items() if count == count_max])
for s in s_list:
    print(s)

Measured memory_bytes: 33372
# Problem C - Many Requirements

# input
N, M, Q = map(int, input().split())
query = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    query.append([a, b, c, d])

# dfs search
def dfs(nums, score, ini_num, keta):
    if keta==N+1:
        tmp_score = 0
        for q in query:
            if nums[q[1]]-nums[q[0]]==q[2]:
                tmp_score += q[3]
        score = max(score, tmp_score)
    else:
        for i in range(ini_num, M+1):
            nums[keta] = ini_num
            score = max(score, dfs(nums, score, i, keta+1))
    return score

# initialization
nums = [0]*(N+1)
max_score = 0

max_score = dfs(nums, 0, 1, 1)
# output
print(max_score)


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

using namespace std;

int main(void){
  int N;
  string S;
  long long r, g, b, ans;

  r = g = b = 0;

  cin >> N;
  cin >> S;

  for(int i=0; i<N; i++){
    if(S[i]=='R') r++;
    if(S[i]=='G') g++;
    if(S[i]=='B') b++;
  }
  ans = r * g * b;

  for(int k=2; k<N; k++){
    for(int i=0; i<k-1; i++){
      if((i+k)%2==0){
        int j = (i + k) / 2;
        if(S[i]!=S[j] && S[j]!=S[k] && S[i]!=S[k]) ans--;
      }
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

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

const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

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

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

template<class TYPE>
struct edge{
    TYPE to,cost; 
    edge(TYPE t,TYPE c){
        to = t;
        cost = c;
    }
};

int main(){
    int x;
    cin >> x;
    if( x >= 30) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3596
#include <stdio.h>
 
int main(void){
	
	int a,b,c;
	
	scanf("%d %d %d",&a,&b,&c);
	
	if(a >= c && a >= b){
	printf("%d\n",b + c);
	} else if (b >= c &&  b >= a){
	printf("%d\n",a + c);
	} else {
	printf("%d\n",a + b);
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


int top, S[1000];


void push( int x){

	S[ ++top] = x;

	}

int pop(){

	top--;

	return S[top + 1];

	}


int main(){

	int a, b;

	top = 0;

	char s[100];

	while( scanf("%s", s) != EOF){

		if( s[0] == '+' ){

			a = pop();

			b = pop();

			push( a+ b);

		}	else if ( s[0] == '-' ){

			b = pop();

			a = pop();

			push( a - b);

		}	else if ( s[0] == '*'){

			a = pop();

			b = pop();

			push( a* b);

		}	else{

			push( atoi(s));

		}

	}

	printf( "%d\n", pop());

	return 0;

}

Measured memory_bytes: 980
//Khodaya aghideye man ra az dast oghde am masoon dar!
#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;
template <typename T> using ordered_set =  tree<T, null_type, greater<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset =  tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
#pragma optimize O3
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 3;
const int infint = (ll)1e9;
const ll inf = (ll)1e18;
int main()
{	
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	ll a, b;
	cin >> a >> b;
	if(a <= 0 && b >= 0)
		return cout << "Zero", 0;
	if(a > 0)
	{
		return cout << "Positive", 0;
	}
	if((b - a + 1) % 2)
		return cout << "Negative", 0;
	cout << "Positive";
}

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

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};
};

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

template <class Cost>
std::vector<Cost> bellman_ford(const Graph<Cost>& graph, int s) {
    constexpr Cost INF = std::numeric_limits<Cost>::max();

    int n = graph.size();
    std::vector<Cost> dist(n, INF);
    dist[s] = 0;

    for (int t = 0; t < n; ++t) {
        bool update = false;
        for (int v = 0; v < n; ++v) {
            for (const auto& e : graph[v]) {
                if (dist[v] != INF && dist[e.dst] > dist[v] + e.cost) {
                    dist[e.dst] = dist[v] + e.cost;
                    update = true;
                }
            }
        }

        if (!update) break;
        if (t == n - 1) {
            // if there is a negative cycle, return empty array
            return std::vector<Cost>();
        }
    }
    return dist;
}

constexpr int INF = std::numeric_limits<int>::max();

int main() {
    int n, m, s;
    std::cin >> n >> m >> s;

    Graph<int> graph(n);
    while (m--) {
        int u, v, d;
        std::cin >> u >> v >> d;
        graph[u].emplace_back(u, v, d);
    }

    auto dist = bellman_ford(graph, s);
    if (dist.empty()) {
        std::cout << "NEGATIVE CYCLE" << std::endl;
        return 0;
    }
    for (int d : dist) {
        if (d == INF) {
            std::cout << "INF" << std::endl;
        } else {
            std::cout << d << std::endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3168
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <map>

int main(){
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  
  int32_t N;
  std::string S;
  std::cin >> N;
  std::cin >> S;

  //using checked_pair_type = std::pair<int32_t, int32_t>;
  //using checked_map_type = std::unordered_map<checked_pair_type, int32_t>;
  using checked_map_type = std::unordered_map<int32_t, int32_t>;
  checked_map_type check_map;

  int32_t num_unique[N] = {};
  int32_t find_pair[100] = {};
  int32_t find_num[10] = {};
  int32_t unique_cnt = 0;
  for (int32_t i = N - 1; i > 0; i--) {
    int32_t numSi = std::stoi(S.substr(i,1));
    //check num_pair
    for (int32_t num = 0; num <10; num++) {
      if (find_num[num] == 1) {
        int32_t pair = 10 * numSi + num;
        if (find_pair[pair] == 0) {
          find_pair[pair]++;
          unique_cnt++;
        }
      }
    }
    //update dp
    num_unique[i] = unique_cnt;
    //update find_num
    if (find_num[numSi] == 0) {
      find_num[numSi] = 1;
    }
  }

  //for (int32_t tmp = 0; tmp < N; tmp++){
  //  std::cout << num_unique[tmp] << std::endl;
  //}

  int64_t res = 0;
  for (int32_t dig1_idx = 0; dig1_idx < N - 2; dig1_idx++) {
    int32_t dig1 = std::stoi(S.substr(dig1_idx, 1));
    if (check_map[dig1] == 0) {
      check_map[dig1]++;
      res += num_unique[dig1_idx + 1];
    }
  }

  std::cout << res << std::endl;
  return 0;
}


Measured memory_bytes: 512
def main(n,k,ab):
  ks=[k]
  m=len(bin(k))-2
  # kはm桁
  kbin=bin(k)[2:]
  now=0
  for i in range(m):
    if kbin[i]=='1' and i<m-1:
      ks.append(now+pow(2,m-i-1)-1)
    now+=int(kbin[i])*pow(2,m-i-1)
  ans=0
  for x in ks:
    tmp=0
    for a,b in ab:
      if a|x==x:tmp+=b
    ans=max(ans,tmp)
  print(ans)

n,k=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
main(n,k,ab)

Measured memory_bytes: 85548
#include <iostream>
using namespace std;
int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        if(a%2 == 0) {
            if(!(a%3 == 0 || a%5 == 0)) {
                puts("DENIED");
                return 0;
            }
        }
    }
    puts("APPROVED");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(a, b) << " " << max(0, a + b - n) << endl;
    return 0;
}

Measured memory_bytes: 256
N,X=map(int,input().split())
def f(n,x):
  if x==1 and n==0:
    return 1
  if x==1:
    return 0
  if x==2**(n+2)-3:
    return 2**(n+1)-1
  if x==2**(n+1)-1:
    return 2**n
  res=0
  if 1<x<2**(n+1)-1:
    res=f(n-1,x-1)
    return res
  if 2**(n+1)-1<x<2**(n+2)-3:
    res=2**n+f(n-1,x-2**(n+1)+1)
    return res
print(f(N,X))
    

Measured memory_bytes: 38384
#include<iostream>
#include <vector>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
using namespace std;
int main(){
	int n; cin >>n;
	vector<int> a(n);
	cinf(n,a);
	for(int i=n-1;i>=1;i--){
		cout << a[i]<<" ";
	}
	cout << a[0]<<endl;
	return 0;
}


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

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

    int n;
    cin >> n;
    double v[n];
    rep (i, n) cin >> v[i];
    sort(v, v + n);
    rep (i, n) {
        if (i == 0 || i == 1) v[i] /= pow(2, n-1); 
        else v[i] /= pow(2, n-i);
    }
    double res = 0;
    rep (i, n) res += v[i];
    cout << res << endl;
}

Measured memory_bytes: 4292
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

use std::ascii::AsciiExt;
use std::cmp;
use std::io::Write;
use std::iter::Iterator;

fn main() {
    input! {
        n:usize,
        q:usize,
        e:[(usize, usize); n-1],
        p:[(usize, usize);q]
    }

    let mut tree :Vec<Vec<usize>> = vec![vec![]; n];
    for (a, b) in e {
        tree[a-1].push(b-1);
        tree[b-1].push(a-1);
    }

    let mut dp = vec![0;n];
    for (p, x) in p {
        dp[p-1] += x;
    }

    let mut used = vec![false; n];
    let mut s = vec![];
    s.push(0);

    while let Some(v) = s.pop() {
        used[v] = true;
        for &u in tree[v].iter() {
            if used[u] {
                continue;
            }
            dp[u] += dp[v];
            s.push(u);
        }
    }

    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());

   for (i, ans) in dp.iter().enumerate() {
        if i > 0 {
            write!(out, " ").unwrap();
        }
        write!(out, "{}", *ans).unwrap();
    }
    writeln!(out, "").unwrap();

}


Measured memory_bytes: 26876
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let s: Vec<char> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().chars().collect()
    };

    let N = s.len();
    let l = (0..N).find(|&i| s[i] == 'A').unwrap();
    let r = (0..N).rev().find(|&i| s[i] == 'Z').unwrap();
    let ans = r - l + 1;

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i < (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define repb(bit, n, init) for (ll bit = init; bit < (1 << n); ++bit)

int main()
{
    string s, w;
    ll cnt = 0;
    cin >> s;
    while (cin >> w)
    {
        if (w == "END_OF_TEXT")
        {
            break;
        }
        repi(i, w.length(), 0)
        {
            w.at(i) = tolower(w.at(i));
        }
        if (s.compare(w) == 0)
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3120
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val s = sc.next()

    println(abc114b(s))
}

private fun abc114b(s: String): Int {
  val ansList = mutableListOf<Int>()

  var start = 0
  var end = start + 3
  while (end <= s.length) {
    val sub = s.subSequence(start, end)
    val si = sub.toString().toInt()
    val diff = Math.abs(si - 753)
    ansList.add(diff)

    start++
    end++
  }

  return ansList.min()!!
}


Measured memory_bytes: 29736
import math

S = raw_input()

# Greedy
rock = 0
paper = 0
score = 0
for n in S:
    if n == 'g': # rock
        if paper < rock:
            paper += 1
            score += 1
        else:
            rock += 1
    else:
        if paper < rock:
            paper += 1
        else:
            rock += 1
            score -= 1

print score


Measured memory_bytes: 2820
#include <bits/stdc++.h>
using namespace std;
static auto faster_iostream = []() { ios::sync_with_stdio(0); cin.tie(0); return 0; }();void print(){cout<<'\n';}template<class T,class ...U>void print(T x, U ...y){cout<<x<<' ';print(y...);}
typedef long long ll; typedef long double db;
const int N = 4e6 + 5, M = 998244353;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  map<int, ll> mp;
  for (int &v : a) {
    cin >> v;
    mp[v]++;
  }
  ll ans = 0;
  for (auto it : mp) {
    ans += it.second * (it.second - 1) / 2;
  }
  for (int v : a) {
    cout << ans - mp[v] + 1 << '\n';
  }
}


Measured memory_bytes: 10368
#include<iostream>
#include<algorithm>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef pair<int,int> P;

const int M = 1010, G = M/2;
int m,n;
int grid[M][M];
bool vis[M][M];
P dp[M][M];
int dy[] = {1,0,-1,0}, dx[] = {0,1,0,-1};

bool pt[M*M];

int main(){
  for(int i=0;i<M*M;i++)pt[i] = true;
  pt[0] = pt[1] = false;

  for(int i=2;i<=M;i++){
    if(pt[i]){
      for(int j=2*i;j<M*M;j+=i)pt[j] = false;
    }
  }
  
  while(cin >> m >> n,m){
    rep(i,M)rep(j,M){
      grid[i][j] = -1;
      vis[i][j] = false;
      dp[i][j] = P(0,0);
    }

    int y = G, x = G, d = 0;
    int sy,sx;
    rep(i,m){
      if(i+1==n){sy = y; sx = x;}
      grid[y][x] = i+1;
      int nxt = grid[y+dy[(d+1)%4]][x+dx[(d+1)%4]];
      if(nxt<0)d = (d+1)%4;
      y += dy[d]; x += dx[d];
    }

    vis[sy][sx] = true;
    dp[sy][sx] = P(pt[n],(pt[n]?n:0));

    P ans = dp[sy][sx];
    rep(i,M)rep(j,M){
      if(!vis[i][j])continue;
      rep(k,3){
	if(grid[i+1][j+k-1]<0)continue;
	vis[i+1][j+k-1] = true;

	P tmp = dp[i][j];
	int val = grid[i+1][j+k-1];
	if(pt[val]){
	  tmp.first++;
	  tmp.second = val;
	}

	dp[i+1][j+k-1] = max(dp[i+1][j+k-1],tmp);
	ans = max(ans,tmp);
      }
    }

    cout << ans.first << " " << ans.second << endl;
  }
}

Measured memory_bytes: 15108
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tcase int _; cin >> _; while(_--)
const int MAX = 1e6;
const int MOD = 1e9+7;

int v[MAX];
int n;
int suff[MAX];

void solve() {
	cin >> n;
	for(int i=0; i<n; i++) cin >> v[i];
	suff[n-1] = v[n-1];
	for(int i=n-2; i>=0; i--) suff[i] = (v[i] + suff[i+1]) % MOD;
	int ans=0;
	for(int i=0; i<n-1; i++) ans = (ans + v[i]*suff[i+1]%MOD) % MOD;
	cout << ans;
}

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

 	solve();

  	return 0;
}



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

int main() {
    string s; cin >> s;
    int n = s.size();
    ll ans = 0;
    rep(i, n){
        int x = s[i] - '0';
        ans += x;
    }

    if(ans % 9 == 0){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3728
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

int main(){
  int N; cin>>N;
  vector<set<int>> st(10*N);
  for(int i=0;i<N;i++){
    int a; cin>>a;
    st[0].insert(a);
  }
  int i = 0;
  while(st[i].size() > 1){
    int a = *st[i].begin();
    for(auto itr=st[i].begin(); itr!=st[i].end(); itr++){
      int b = *itr;
      if(b%a)
        st[i+1].insert(b%a);
      else
        st[i+1].insert(a);
    }
    i++;
  }
  cout<<*st[i].begin()<<endl;
  return 0;
}


Measured memory_bytes: 52096
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int a,b; cin>>a>>b;
    cout<<(a*b%2==0 ? "Even" : "Odd")<<endl;
}

Measured memory_bytes: 3604
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int Nil=-1;
const int Max=1000000;
int n,m,np=0;

struct node
{
    int location;
    int p,l,r;
    node() {}
}T[Max];

struct point
{
    int id,x,y;
    point() {}
    point(int id,int x,int y):id(id),x(x),y(y) {}
    bool operator < (const point& p) const
    {
        return id < p.id;
    }

    void print()
    {
        printf("%d\n",id);
    }
}P[Max];

bool less_x(const point& p1,const point& p2)
{
    return p1.x<p2.x;
}

bool less_y(const point& p1,const point& p2)
{
    return p1.y<p2.y;
}

int makekdtree(int l,int r,int dep)
{
    if(!(l<r)) return Nil;
    int mid=(l+r)/2;
    int num=np++;
    if(dep%2==0)
      sort(P+l,P+r,less_x);
    else
      sort(P+l,P+r,less_y);
    T[num].location=mid;
    T[num].l=makekdtree(l,mid,dep+1);
    T[num].r=makekdtree(mid+1,r,dep+1);
    return num;
}

void find(int v,int sx,int tx,int sy,int ty,int dep,vector<point>& ans)
{
    int x=P[T[v].location].x;
    int y=P[T[v].location].y;
    if(sx <= x && x <= tx && sy <= y && y <= ty)
      ans.push_back(P[T[v].location]);

    if(dep%2 == 0)
    {
      if(T[v].l != Nil)
        if(sx <= x)
          find(T[v].l,sx,tx,sy,ty,dep+1,ans);
      if(T[v].r != Nil)
        if(x <= tx)
          find(T[v].r,sx,tx,sy,ty,dep+1,ans);
    }
    else
    {
        if(T[v].l != Nil)
          if(sy <= y)
            find(T[v].l,sx,tx,sy,ty,dep+1,ans);
        if(T[v].r != Nil)
          if(y <= ty)
            find(T[v].r,sx,tx,sy,ty,dep+1,ans);
    }
}

int main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        P[i]=point(i,x,y);
        T[i].p=T[i].l=T[i].r=Nil;
    }
    int root = makekdtree(0,n,0);
    scanf("%d",&m);
    int sx,sy,tx,ty;
    vector<point> ans;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&sx,&tx,&sy,&ty);
        ans.clear();
        find(0,sx,tx,sy,ty,0,ans);
        sort(ans.begin(),ans.end());
        for(int j=0;j<ans.size();++j)
          ans[j].print();
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 16388
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define REPR(i,n) for(int i=(int)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(int i=(int)(b)-1,_a=(int)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}

#define MOD 1000000007LL
#define INF (1LL<<60)
/*
 ACAC
00112

 12345678
 ACACTACG
001122233 
*/
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,Q,L,R;
	string S;
	while(cin>>N>>Q>>S) {
		VI co(N+1);
		RANGE(i, 1, N+1) co[i] = co[i-1] + (0<=i-2 ? S[i-2]=='A'&&S[i-1]=='C' : 0);
//		DD(co);
		REP(i, Q) {
			cin>>L>>R;
//			DD(co[R]);
//			DD(co[L-1]);
			ll ans = co[R] - co[L-1] - (0<=L-2 ? S[L-2]=='A'&&S[L-1]=='C' : 0);
			cout<<ans<<endl;
		}
	}
	
	return 0;
}


Measured memory_bytes: 1872