akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};

struct e{
    string s;
    ll cost;
    bool rev;
};

bool ispa(string s){
    int n = s.size();
    for(int i=0;i<n;i++){
        if(s[i] != s[n-1-i]){
            return false;
        }
    }
    return 1;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int n;
    cin>>n;
    string s[n],rev[n];
    ll a[n];
    map<string, ll> used[2];
    for(int i=0;i<n;i++){
        cin>>s[i]>>a[i];
        if(used[0].count(s[i]))chmin(used[0][s[i]], a[i]);
        else used[0][s[i]] = a[i]; 
        rev[i] = s[i];
        reverse(rev[i].begin(),rev[i].end());
        if(used[1].count(rev[i]))chmin(used[1][rev[i]], a[i]);
        else used[1][rev[i]] = a[i];
    }
    ll ans = 1e18;
    queue<e> q;
    for(int i=0;i<n;i++){
        q.push((e){s[i],a[i],0});
    }
    map<string,vector<e>> mp[2];
    for(int i=0;i<n;i++){
        string now = "";
        string rnow="";
        for(int j=0;j<s[i].size();j++){
            now += s[i][j];
            rnow += rev[i][j];
            mp[0][now].push_back((e){s[i].substr(j+1), a[i], 0});
            mp[1][rnow].push_back((e){rev[i].substr(j+1), a[i], 1});
        }
    }
    map<string,ll> visited[2];
    while(q.size()){
        e p = q.front();
        q.pop();
        bool x = p.rev;
        string str = p.s;
        if(visited[x].count(str) && visited[x][str] <= p.cost)continue;
        visited[x][str] = p.cost;
        if(ispa(str)){
            chmin(ans, p.cost);
            continue;
        }
        // check mp[x^1][str] -> x^1
        int nx = x^1;
        if(mp[nx].count(str)){
            for(e i:mp[nx][str]){
                q.push((e){i.s, p.cost + i.cost, nx});
            }
        }
        string now = "";
        // check mp[c^1][str[0:i]] -> x
        for(int j=0;j<p.s.size()-1;j++){
            now += p.s[j];
            if(used[nx].count(now)){
                q.push((e){p.s.substr(j+1), p.cost + used[nx][now], x});
                
            }
        }
    }
    if(ans > 1e17)ans = -1;
    cout << ans << endl;
}   


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

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;


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

	stack<char> stk;
	for (int i = 0; i < s.size(); i++) {
		switch (s[i]) {
		case 'S': {
			stk.push(s[i]);
			break;
		}
		case 'T': {
			if (stk.empty()||stk.top()=='T') {
				stk.push(s[i]);
			} else {
				stk.pop();
			}
			break;
		}
		}
	}
	cout << stk.size() << "\n";
}


Measured memory_bytes: 644
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

vector<vector<int>> edge;
vector<int> vdist, udist;

void dfs(vector<int> &dist, int node, int parent, int d)
{
    dist[node] = d;
    for (int e : edge[node])
    {
        if (e != parent)
        {
            dfs(dist, e, node, d + 1);
        }
    }
}

int main()
{
    int n, u, v;
    cin >> n >> u >> v;
    u--;
    v--;

    edge.resize(n);
    vdist.resize(n);
    udist.resize(n);
    rep(i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    dfs(vdist, v, v, 0);
    dfs(udist, u, u, 0);

    int result = 0;
    rep(i, n)
    {
        if (udist[i] < vdist[i])
        {
            result = max(result, vdist[i] - 1);
        }
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 11648
#include <iostream>
#include <vector>
#include <cmath>
#include <typeinfo>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;


// a**b mod p を返す
ll binary_power(ll a, ll b, ll p){
    if(a==1){
        return 1%p;
    }
    //a**b(mod p)を求めたいとき(とくに100000<b<2**(100000))
    ll blen = log2(b);
    vector<ll> a2(blen+2);
    a2[0] = a;
    for(int i=1; i<blen+2; i++){
        a2[i] = (a2[i-1] * a2[i-1])%p;
    }
    //count = a**b(mod p);
    ll count = 1;
    for(int i=0; i<blen+2; i++){
        if((b>>i & 1) == 1){
            count *= a2[i];
            //cout << count << endl;
            count = count % p;
        }
    }
    return count;
}
int main(){
    ll h,w,a,b;
    cin >> h >> w >> a >> b;
    ll ans = 0;
    ll count;
    ll p = 1000000007;
    vector<ll> f(h+w+1);
    vector<ll> of(h+w+1);

    f[0] = 1;
    f[1] = 1%p;
    for(int i=2; i<=h+w; i++){
        f[i] = f[i-1]*i%p;
    }
    for(int i=1; i<=h+w; i++){
        of[i] = binary_power(f[i], p-2, p);
    }
    ll x1,x2,y1,y2;
    for(ll i=0; i<w-b; i++){
        //cout << i << endl;
        x1 = h-a+b+i-1;
        y1 = h-a-1;
        x2 = w-b-i+a-2;
        y2 = a-1;
        //cout << "x1=" << x1 << endl;
        //cout << "y1=" << y1 << endl;
        //cout << "x2=" << x2 << endl;
        //cout << "y2=" << y2 << endl;
        if(y1==0 or x1==y1){
            count = 1;
        }else{
            count = f[x1];
            count *= of[y1];
            count = count % p;
            count *= of[x1-y1];
            count = count % p;
        }
        if(y2==0 or x2==y2){
            count = count;
        }else{
            count *= f[x2];
            count = count%p;
            count *= of[y2];
            count = count %p;
            count *= of[x2-y2];
            count = count %p;
        }
        //cout << x1 << "C" << y1 << "*" << x2 << "C" << y2 << "modp=" << count << endl; 
        ans += count;
        ans = ans % p;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3328
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n = int(input().strip())
    x = list(map(int, input().strip().split()))
    x.sort()
    ans = sys.maxsize
    for d in range(x[0], x[-1]+1):
        ans = min(sum([(x[i] - d) ** 2 for i in range(n)]), ans)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 62956
#include<bits/stdc++.h>
using namespace std;
const int maxn=200050;
int a[maxn],n,L,R,M,l,r,mid,m,mn,mx,P;

int main(){
    cin >> n >> m;
    for (int i=0;i<n*2;i++) cin >> a[i];
    sort(a,a+n+n);
    L=0; R=n+1;
    while (R-L>1){
        M=(L+R)>>1;
        mn=m*2;
        int st=n*2-M*2;
        for (int i=0;i<M;i++)
            mn=min(mn,a[st+i]+a[n*2-1-i]);
        if (mn>=m) L=M; else R=M;
    }
    P=n-L;
    int ans=0;
    for (int i=0;i<P;i++) ans=max(ans,a[i]+a[P*2-1-i]);
    int st=n*2-L*2;
    for (int i=0;i<L;i++) ans=max(ans,a[st+i]+a[n*2-1-i]-m);
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 15;
const int INF = 1<<29;

int main(int argc, char const *argv[])
{
    int n, e;
    int d[MAX_N][MAX_N];
    cin >> n >> e;

    for (int i = 0; i < n; ++i) {
        fill(d[i], d[i]+n, INF);
    }

    for (int i = 0; i < e; ++i) {
        int si, ti, di;
        cin >> si >> ti >> di;
        d[si][ti] = di;
    }

    int dp[1<<MAX_N][MAX_N];

    for (int i = 0; i < 1<<n; ++i) {
        fill(dp[i], dp[i]+n, INF);
    }

    dp[(1<<n)-1][0] = 0;

    for (int s = (1<<n) - 2; s >= 0 ; s--) {
        for (int v = 0; v < n; ++v) {
            for (int u = 0; u < n; ++u) {
                if (!(s >> u & 1)) {
                    dp[s][v] = min(dp[s][v], dp[s | 1 << u][u] + d[v][u]);
                }
            }
        }
    }

    int ans;

    if (dp[0][0]<INF) {
        ans = dp[0][0];
    }
    else {
        ans = -1;
    }

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


    return 0;
}


Measured memory_bytes: 5048
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <memory>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define FAST_IO std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define pause system("pause")
using namespace std;
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
int const maxn = 200000;
vector<int> e[maxn];
int vis[maxn];
int x[maxn];
int cnt = 0;

struct node {
    int u, s;
    node(const int &u = 0,const int &v = 0) :
        u(u),s(v) {}
}; 

int bfs(int x, int n) {
    queue<node> q;
    q.push(node(x, 0));
    while (!q.empty()) {
        node t = q.front();
        q.pop();
        if (t.u == n)
            return t.s;
        int v = t.u;
        vis[v] = 1;
        for (auto &u : e[v]) {
            if (!vis[u])
                q.push(node(u, t.s + 1));
        }
    }

    return 0;
}

int main(void) {
    FAST_IO;
    int n, m;
    cin >> n >>m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int ans = bfs(1, n);
    if (ans <= 2 && ans != 0)
        cout << "POSSIBLE" << endl;
    else 
        cout << "IMPOSSIBLE" << endl;
    // pause;
    return 0;
}

Measured memory_bytes: 13552
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <typeinfo>
using namespace std;
int main(){
	int a,b,c=0;
	cin>>a>>b;
	for(int i=a;i<=b;i++){
		if(i/10000==i%10&&(i%100)/10==(i%10000)/1000)c++;
	}
	cout<<c<<endl;
	return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int N = 1e5 + 100;

int n, u, v, w;
bool c[N];
vector<pii> nei[N];

void dfs(int v, int par = -1) {
	for (pii p: nei[v])
		if(p.first != par) {
			c[p.first] = c[v] ^ p.second;
			dfs(p.first, v);
		}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> u >> v >> w;
		nei[--u].push_back(pii(--v, w & 1));
		nei[v].push_back(pii(u, w & 1));
	}
	dfs(0);
	for (int i = 0; i < n; i++)
		cout << c[i] << '\n';
	return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h> 
using namespace std; 
const int MAX_N = 5e5 + 5; 
int N, a[MAX_N], sum; 
char s[MAX_N]; 
int main () { 
#ifndef ONLINE_JUDGE 
    freopen("cpp.in", "r", stdin); 
#endif 
	scanf("%s", s + 1); N = strlen(s + 1);
	reverse(&s[1], &s[N + 1]); 
	for (int i = 1; i <= N; i++) a[i] = s[i] - '0'; 
	for (int i = 1; i <= N; i++) a[i] *= 9; 
	for (int i = 1; i <= N; i++) a[i + 1] += a[i] / 10, a[i] %= 10; 
	++N; 
	for (int i = 1; i <= N; i++) sum += a[i]; 
	for (int k = 1; k <= 9 * N; k++) { 
		sum += 9, a[1] += 9; 
		for (int i = 1; i <= N; i++)
			if (a[i] >= 10) a[i + 1]++, sum -= 9, a[i] -= 10;
			else break; 
		if (sum <= 9 * k) return printf("%d\n", k) & 0; 
	} 
	puts("GG"); 
    return 0; 
} 

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

struct vector{int a; int b;};

int com(const void *a, const void *b){
    struct vector *v1 = (struct vector *)a;
    struct vector *v2 = (struct vector *)b;
    return v1->b - v2->b;
}

int main(void) {
    int n, i;
    long long int sum = 0;
    scanf("%d", &n);
    struct vector v[n];
    for(i = 0; i < n; ++i){
        scanf("%d %d", &v[i].a, &v[i].b);
    }
    qsort(v, n, sizeof(struct vector), com);
    for(i = 0; i < n; ++i){
        sum += v[i].a;
        if(sum > v[i].b){printf("No\n"); return 0;}
    }
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 3324
using System;
using System.Linq;

class B
{
	static void Main()
	{
		var s = Console.ReadLine();
		var s1 = s.Remove(s.Length / 2);
		var s2 = s.Substring(s1.Length + 1);
		var s1r = new string(s1.Reverse().ToArray());
		Console.WriteLine(s1 == s2 && s1 == s1r ? "Yes" : "No");
	}
}


Measured memory_bytes: 26520
#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の桁数を求める
bool is_es(string s){
    int n = s.length();
    if(n%2 == 1) return false;
    else{
        string s1 = s.substr(0,n/2);
        string s2 = s.substr(n/2);
        if(s1 == s2) return true;
        else return false;
    }
}
int main()
{
    string s;
    cin >> s;
    int n = s.length();
    int j = n-1;
    rep(i,n){
        s.erase(j,1);
        if(is_es(s)) {
            cout << s.length() << endl;
            return 0;
        }
        j--;
    }

    return 0;
}

Measured memory_bytes: 3604
//AC:152D
#include <bits/stdc++.h>
using namespace std;
void organise(int x,int &first_digit,int &last_digit){
    last_digit = x%10;
    while(x){
        first_digit = x;
        x /= 10;
    }
}
int main()
{
    int n,first_digit,last_digit;
    cin >> n;
    //TWO DIMENSIONAL KEY (row,column) [2D Array]
    map< int,map< int,int > > matrix;
    long long sum = 0;
    for(int i=0;i<=n;i++){
        organise(i,first_digit,last_digit);
        matrix[first_digit][last_digit]++;
    }
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            sum += matrix[i][j]*matrix[j][i];
        }
    }
    cout << sum - 1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
ll dp[100002] = {0};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n, w, i, j, k;
    cin >> n >> w;
    std::vector<pair<ll, ll>> v;
    for(i = 0; i < n; i++) {
        cin >> j >> k;
        v.pb({j, k});
    }
    for(i = 1; i < 100001; i++) {
        dp[i] = INT_MAX;
    }
    for(j = 0; j < n; j++) {
        vector<pair<ll, ll>> temp;
        temp.clear();
        for(i = 0; i < 100001; i++) {
            if(dp[i] != INT_MAX) {
                temp.pb({i + v[j].second, dp[i] + v[j].first});
            }
        }
        for(auto it:temp) {
            dp[it.first] = min(dp[it.first], it.second);
        }
    }
    ll mx = -1;
    for(i = 0; i < 100001; i++) {
        if(dp[i] <= w) {
            mx = i;
        }
    }
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 2932
def main():
    W,H=map(int, input().split())
    P=sorted(int(input())for _ in range(W))
    Q=sorted(int(input())for _ in range(H))
    i,j,ans=0,0,0
    while i<W and j<H:
        if P[i]<Q[j]:
            ans+=P[i]*(H-j+1)
            i+=1
        else:
            ans+=Q[j]*(W-i+1)
            j+=1
    while i<W:
        ans+=P[i]*(H-j+1)
        i+=1
    while j<H:
        ans+=Q[j]*(W-i+1)
        j+=1
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 11616
# -*- coding: utf-8 -*-
import sys


N,M=[int(i) for i in input().rstrip().split()]
sc_list=[[int(j) for j in input().split()] for i in range(M)]
#-----

ans=["x"]*N

Flag=True
for s,c in sc_list:
    if s == 1 and c == 0 and N != 1:
        print("-1")
        sys.exit()
    elif ans[s-1] != "x" and ans[s-1] != c:
        print("-1")
        sys.exit()
    else:
        ans[s-1] = c


if ans[0] == "x":
    if N == 1:
        ans[0] = 0
    else:
        ans[0] = 1

for i in range(1,len(ans)):
    if ans[i] == "x":
        ans[i] = 0

print(*ans,sep="")


Measured memory_bytes: 3188
import scala.io.StdIn.readLine;
import scala.reflect.ClassTag;
object Main {
    def main(args: Array[String]): Unit = {
        val line = readLine.split(" ").map(_.toInt);
        val n = line(0);
        val q = line(1);
        val que = new Queue[(String, Int)](n);
        for (i <- 0 until n) {
            val proc = readLine.split(" ");
            que.enqueue((proc(0), proc(1).toInt));
        }
        var total = 0;
        while (que.isEmpty == false) {
            val (name, time) = que.dequeue;
            if (time <= q) {
                total += time;
                println("%s %d".format(name, total));
            } else {
                total += q;
                que.enqueue((name, time - q));
            }
        }
    }
}
class Queue[A](size: Int)(implicit m: ClassTag[A]) {
    private val arr = m.newArray(size);
    private var leftPtr = 0;
    private var rightPtr = 0;
    private var cnt = 0;
    def isEmpty: Boolean = cnt == 0;
    def isFull: Boolean = cnt == size;
    def enqueue(e: A): Unit = if (isFull) {
        throw new RuntimeException("queue full")
    } else {
        arr(rightPtr) = e;
        cnt += 1;
        rightPtr = if (rightPtr + 1 == size) 0 else rightPtr + 1;
    }
    
    def dequeue: A = if (isEmpty) {
        throw new NoSuchElementException("queue empty");
    } else {
        val e = arr(leftPtr);
        cnt -= 1;
        leftPtr = if (leftPtr + 1 == size) 0 else leftPtr + 1;
        e;
    }
}


Measured memory_bytes: 169744
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h,w,k;
    cin >> h >> w >> k;
    vector<vector<ll>> dp(h+1,vector<ll>(w,0));
    dp[0][0] = 1;
    rep(i,h){
        rep(bit,(1<<(w-1))){
            bool ok = 1;
            rep(j,w-2){
                if ((bit&(1<<j)) and (bit&(1<<(j+1)))) ok = 0;
            }
            if (ok){
                int j = 0;
                while(j < w){
                    if (j == w-1){
                        (dp[i+1][j] += dp[i][j])%=MOD;
                        break;
                    }
                    if (bit&(1<<j)){
                        (dp[i+1][j] += dp[i][j+1])%=MOD;
                        (dp[i+1][j+1] += dp[i][j])%=MOD;
                        j += 2;
                    }
                    else{
                        (dp[i+1][j] += dp[i][j])%=MOD;
                        j++;
                    }
                }
            }
        }
    }
    PRINT(dp[h][k-1]);
}


Measured memory_bytes: 256
u, s, e, w, n, d = input().split()
for i in input():
    if i == 'N':
        u, s, n, d = s, d, u, n
    elif i == 'E':
        u, e, w, d = w, u, d, e
    elif i == 'S':
        u, s, n, d = n, u, d, s
    elif i == 'W':
        u, e, w, d = e, d, u, w
print(u)

Measured memory_bytes: 7436
#include<bits/stdc++.h>
using namespace std;
int deep[100010], par[100010];
vector <int> v[100010];
int a, b, in[100010], n ,m;
int dfs(int x)
{
	if (deep[x] != -1)return deep[x];
	deep[x] = 0;
	for (int i = 0; i < v[x].size(); ++i)deep[x] = max(deep[x], dfs(v[x][i]) + 1);
	return deep[x]; 
}
void dfs2(int x, int p)
{
	if (par[x] != -1)return ;
	else par[x] = p;
	vector <pair<int,int> > c;
	for (int i = 0; i < v[x].size(); ++i){
		c.push_back({deep[v[x][i]], v[x][i]});
	}
	sort(c.begin(), c.end());
	reverse(c.begin(), c.end());
	for (int i = 0; i < c.size(); ++i)dfs2(c[i].second, x);
}
int main()
{
	memset(deep, -1, sizeof deep);
	memset(par, -1, sizeof par);
	cin >> n >> m;
	for (int i = 1; i <= n - 1 + m; ++i){
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		in[b]++;
	}
	int pp;
	for (int i = 1; i <= n; ++i)if(!in[i]){
		pp = i;
	}
	dfs(pp);
	dfs2(pp, 0);
	for (int i = 1; i <= n; ++i)cout << par[i] << endl;
	return 0;
} 

Measured memory_bytes: 19968
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using pii=pair<int,int>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<< endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(ll, W, H, x, y);
  cout << (double)(W * H) / 2 << " " << (x * 2 == W && y * 2 == H);
}


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

int main() {

    int n;
    cin >> n;
    vector<int> numOfBuka(n,0);
    for (int i = 2; i <= n; i++) {
        int a;
        cin >> a;
        numOfBuka[a - 1]++;
    }
    for (int i = 0; i < n; i++) {
        cout << numOfBuka[i] << endl;
    }

    return 0;

}


Measured memory_bytes: 4052
A,B,C = sorted(list(map(int,input().split())))
if (C-A)%2 == (C-B)%2:
    print( (B-A)//2 + C - B )
elif (C-A)%2 == 0:
    print( (C-A)//2 + 1 + (C-B+1)//2 )
else:
    print( (C-B)//2 + 1 + (C-A+1)//2 )


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string.h>
#define REP(i,j,n) for(int i=j;i<n;i++)
#define SORT(x) sort(x.begin(),x.end())

using namespace std;



int main() {
	int n, m;
	int  max=0, maxnum;
	for (;;) {
		cin >> n >> m;
		if (n == 0 && m == 0)break;
		vector<int>v(n);
		REP(i, 0, n) cin >> v[i];

		REP(i, 0, n - 1) {
			REP(j, i + 1, n) {
				if (max < v[i] + v[j] && v[i] + v[j] <= m) {
					max = v[i] + v[j];
				}
			}
		}

		if (max == 0)cout << "NONE" << endl;
		else cout << max << endl;
		max = 0;
	}


	return 0;
}

Measured memory_bytes: 3008
#include<iostream>
#include<queue>
#include<limits>
// #include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<math.h>
#include<iomanip>  
#include<deque> 
#include<stack>
#include<string> 
#include<string.h>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#define ll long long
#define tc(t)  while(t--)
#define V vector
#define Vp vector< pair<int,int> >
#define pb push_back
#define UM unordered_map
#define IT iterator
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define PQ priority_queue
#define _FI ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

 char ar[140000];
vector<ll> SieveOfEratosthenes(ll n) 
{ 
  vector<ll> result;
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
    int count=1;
    for (ll p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        {  
            for (ll i=p*p; i<=n; i += p) 
                {
                  prime[i] = false; 
                }
            count++;
        } 
    } 
  
    for (ll p=2; p<=n; p++) 
       if (prime[p]) 
          {
            result.push_back(p);
          }
    return result;
}



vector<ll> Divisors (ll n)
{
  vector<ll> res;
  for(ll i=1;i<=sqrt(n);i++)
  {
    if(n%i==0)
    {
      if(n/i==i)
      {
        res.pb(i);
      }
      else
      {
        res.pb(i);
        res.pb(n/i);
      }
    }
  }

  return res;
}

ll Div(ll n)
{
  for(ll i=2;i<=sqrt(n);i++)
  {
    if(n%i==0)
      return i;
  }
  return n;
}

int a[4][2]={ {1,0}, {1,-1}, {1,1}, {2,0} } ;
bool validPoint(int x,int y, int N)
{
    return (x>=0 && x<N && y>=0 && y<N);
}


int main()
{
  _FI 

  int t=1;
  // cin>>t;
  tc(t)
  {
    string s;
    cin>>s;
    int n=s.length();
    forn(i,n)
    	cout<<"x";
  }

  return 0;
}



Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int> 
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b && b==c)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.buffer.readline

    # min
    def STfunc(a, b):
        if a < b:
            return a
        else:
            return b

    # クエリは0-indexedで[l, r)
    class SparseTable():
        def __init__(self, A):
            # A: 処理したい数列
            self.N = len(A)
            self.K = self.N.bit_length() - 1
            self.table = [[0] * (self.K + 1) for _ in range(self.N)]
            for i, a in enumerate(A):
                self.table[i][0] = A[i]
            for k in range(1, self.K + 1):
                for i in range(self.N):
                    j = i + (1 << (k - 1))
                    if j <= self.N - 1:
                        self.table[i][k] = STfunc(self.table[i][k - 1], self.table[j][k - 1])
                    else:
                        self.table[i][k] = self.table[i][k - 1]

        def query(self, l, r):
            # [l, r)の最小値を求める
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l][k], self.table[r - (1 << k)][k])

    N = int(input())
    n = N//2
    A = list(map(int, input().split()))

    A_even = A[0:N:2]
    A_odd = A[1:N:2]
    ST_even = SparseTable(A_even)
    ST_odd = SparseTable(A_odd)
    val2idx = [0] * (N+1)
    for i in range(N):
        val2idx[A[i]] = i

    ans = []
    ans_append = ans.append
    pq = [(ST_even.query(0, n), 0, N)]
    for t in range(n):
        v1, left, right = heappop(pq)
        ans_append(v1)
        i = val2idx[v1]
        if i & 1:
            v2 = ST_even.query((i+1)//2, right//2 + 1)
            ans_append(v2)
            j = val2idx[v2]
            if left != i:
                heappush(pq, (ST_odd.query(left//2, i//2), left, i))
            if j-i > 1:
                heappush(pq, (ST_even.query((i+1)//2, j//2), i+1, j))
            if j+1 != right:
                heappush(pq, (ST_odd.query((j+1)//2, right//2), j+1, right))
        else:
            v2 = ST_odd.query(i//2, right//2)
            ans_append(v2)
            j = val2idx[v2]
            if left != i:
                heappush(pq, (ST_even.query(left//2, i//2), left, i))
            if j-i > 1:
                heappush(pq, (ST_odd.query((i+1)//2, j//2), i+1, j))
            if j+1 != right:
                heappush(pq, (ST_even.query((j+1)//2, right//2), j+1, right))

    print(*ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 140140
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stdio.h>
#include<deque>
#include<map>
#include<queue>

typedef long long ll;

#define debug(x) cout << #x << "=" << x << endl;
#define debug_arr(a, n) for(ll i = 0; i < n; i++)cout << a[i] << " "
#define inf 100000000000
#define loop(i,n) for(ll i = 0; i < n; i++)
#define graph vector<vector<ll>>
#define P pair<ll,ll>

using namespace std;

int main(){
    ll n,k,r,s,p;
    cin >>n >>k;
    cin >>r >>s >>p;
    vector<ll> score(n);

    string t;
    cin >>t;

    loop(i,n){
        char hand = t[i];
        if(i-k >= 0){
            if(t[i] == t[i-k]){
                if(score[i-k] != 0) {
                    score[i] = 0;
                    continue;
                }
            }
        }
        if(hand == 'r'){
            score[i] = p;
        }else if (hand == 's')
        {
            score[i] = r;
        }else if (hand == 'p')
        {
            score[i] = s;
        }
    }
    ll result = 0;
    loop(i,n){
        result += score[i];
    }

    cout << result << endl;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(...) out(__VA_ARGS__);cout<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void out(){} template<class T,class... U> void out(T t,U ...u){cout<<t<<" ";out(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(string, S);
  print(S[0] + S[1] + S[2] - 48 * 3);
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
typedef long double ld;
const char sp = ' ';
#define MOD 1000000007
using namespace boost::multiprecision;
using namespace std;

int main(void){
    ll N;
    cin>>N;
    ll a=1, b=1, c=1, d=1;
    rep(i, N){
        a*=10;
        b*=9;
        c*=9;
        d*=8;
        a%=MOD;
        b%=MOD;
        c%=MOD;
        d%=MOD;
    }
    cout<<((a-b-c+d+MOD)%MOD+MOD)%MOD<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
 
int main() {
    int a(0),b,c,ans(0),tmp(0);
  	string s;
  	cin >> a;
  	int x[a];
  	for(int i = 0;i < a;i++)x[i] = 0;
  
  	for(int i = 5;i < a+1;i++){
  		for(int h = 1;h < i;h++){
			for(int j = 1;j < i-h;j++){
              if(h*h+j*j+1*1+h*j+j*1+h*1 > i)break;
          		for(int k = 1;k < i-h-j;k++){
            		if(h*h+j*j+k*k+h*j+j*k+h*k ==i){
              			x[i-1] += 1;
            		}else if(h*h+j*j+k*k+h*j+j*k+h*k > i)break;
          		}
        	}
        }
    }
  for(int i = 0;i < a;i++)cout << x[i] << endl;
  
}
   


Measured memory_bytes: 3512
#include <bits/stdc++.h>
using namespace std;
bool go(char x) {
	if (x == 'A' || x == 'C' || x == 'G' || x == 'T') {
		return true;
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		if (go(s[i])) {
			cnt += 1;
		}
		else {
			ans = max(ans, cnt);
			cnt = 0;
		}
	}
	ans = max(ans, cnt);
	cout << ans << '\n';


}

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

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

    static class TaskB {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] a = in.nextIntArray(n);

            Arrays.sort(a);
            int ans = 0;
            for (int i = n - k; i < n; i++)
                ans += a[i];

            out.println(ans);
        }

    }

    static class FastScanner {
        private InputStream in;
        private byte[] buffer = new byte[1024];
        private int bufPointer;
        private int bufLength;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (bufPointer >= bufLength) {
                if (bufLength == -1)
                    throw new InputMismatchException();

                bufPointer = 0;
                try {
                    bufLength = in.read(buffer);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (bufLength <= 0)
                    return -1;
            }
            return buffer[bufPointer++];
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public long nextLong() {
            long n = 0;

            int b = readByte();
            while (isSpaceChar(b))
                b = readByte();

            boolean minus = (b == '-');
            if (minus)
                b = readByte();

            while (b >= '0' && b <= '9') {
                n *= 10;
                n += b - '0';
                b = readByte();
            }

            if (!isSpaceChar(b))
                throw new NumberFormatException();

            return minus ? -n : n;
        }

        public int nextInt() {
            long n = nextLong();

            if (n < Integer.MIN_VALUE || n > Integer.MAX_VALUE)
                throw new NumberFormatException();

            return (int) n;
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

    }
}



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

int main(void){
  long long int n, m;
  scanf("%lld %lld",&n,&m);
  if(n==1 && m==1) printf("1\n");
  else if(n==1 || m==1) printf("%lld\n",n*m-2);
  else printf("%lld\n",(n-2)*(m-2));

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;

using namespace std;
typedef pair<long,long> pr;
bool pairCompare(const pr& firstElof, const pr& secondElof)
{
    return (firstElof.first < secondElof.first || ((firstElof.first == secondElof.first) && (firstElof.second < secondElof.second)));
}

class Lowlink {
private:
	vector<vector<long>> E;
	vector<long> ord;
	vector<long> low;
	vector<long> prev;
	size_t V;
public:
	Lowlink() : V(0){ }
	Lowlink(size_t v) : 
		V(v),E(v,vector<long>(0)),ord(v,-1),low(v,2147483647),prev(v,-1) {}

	size_t size() {return V;}

	void add_edge_directed(long from,long to){
		E[from].push_back(to);
	}

	void add_edge_undirected(long from,long to){ 
		E[from].push_back(to);
		E[to].push_back(from);
	}

	void dfs(long node,long parent,long order){
		long child = 1;
		prev[node] = parent;
		low[node] =  ord[node] = order;

		REP(i,(long)E[node].size()){
			long to = E[node][i];
			if (to == parent) continue;
			if (ord[to] == -1) { // 子ノードへの辺
				dfs(to,node,order + child);
				child++;
				low[node] = min(low[node],low[to]);
			}
			low[node]=min(low[node],ord[to]);
		}
	}

	vector<pr> find_bridge(void){
		vector<pr> bridge;
		REP(i,V){
			if (ord[i] == (-1)) dfs(i,-1,1);
		}

		REP(i,V){
			if (ord[i] == low[i]) {
				if (prev[i] == (-1)) continue;
				bridge.push_back(pr(min(i,prev[i]),max(i,prev[i])));
			}
		}

		sort(bridge.begin(),bridge.end(),pairCompare);
		return bridge;
	}

	vector<long> find_articulation_point(void){
		vector<long> point;
		vector<char> root(V,0);

		REP(i,V){
			if (ord[i] == (-1)) {
				dfs(i,-1,1);
				root[i] = 1;
			}
		}

		REP(i,V){
			if (prev[i] == (-1)) continue;
			if (root[prev[i]]) root[prev[i]]++;
			else {
				if (ord[prev[i]] <= low[i]) point.push_back(prev[i]);
			}
		}
		
		REP(i,V) if (root[i] >= 3) point.push_back(i);

		sort((point).begin(),(point).end());
		point.erase(unique(point.begin(),point.end()),point.end());

		return point;
	}
};

int main(void){
	long V,E;
	long u,v;
	cin >> V >> E;
	Lowlink ll(V);
	REP(i,E){
		cin >> u >> v;
		ll.add_edge_undirected(u,v);
	}

	vector<long> ans = ll.find_articulation_point();
	REP(i,ans.size()) cout << ans[i] << endl;

	return 0;
}


Measured memory_bytes: 5212
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (ll)4e18;
const int inf = 1001001001;
const int mod = 1000000007;

int mp[505][505];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, w;
	cin >> h >> w;
	rep(i, h)rep(j, w) cin >> mp[i][j];
	vector<tuple<int, int, int, int>> ans;
	rep(i, h) {
		if(i % 2 == 0) rep(j, w) {
			if (mp[i][j] % 2 == 0) continue;
			mp[i][j]--;
			if (j + 1 < w) {
				mp[i][j + 1]++;
				ans.emplace_back(i + 1, j + 1, i + 1, j + 2);
			}
			else if (i + 1 < h) {
				mp[i + 1][j]++;
				ans.emplace_back(i + 1, j + 1, i + 2, j + 1);
			}
		}
		else {
			for (int j = w - 1; j >= 0; --j) {
				if (mp[i][j] % 2 == 0) continue;
				mp[i][j]--;
				if (j - 1 >= 0) {
					mp[i][j - 1]++;
					ans.emplace_back(i + 1, j + 1, i + 1, j);
				}
				else if (i + 1 < h) {
					mp[i + 1][j]++;
					ans.emplace_back(i + 1, j + 1, i + 2, j + 1);
				}
			}
		}
	}
	cout << ans.size() << endl;
	rep(i, ans.size()) {
		printf("%d %d %d %d\n", get<0>(ans[i]), get<1>(ans[i]), get<2>(ans[i]), get<3>(ans[i]));
	}
	return 0;
}


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

int main(){
    int W,a,b;
    cin >> W >> a >>b;
    int distance = 0;

    if (a <= W+b && b<= a+W)
    {
       distance = 0;
    }else if (a > b)
    {
       distance =  a - (b+W) ;
    }else
    {
        distance = b - (a+W);
    }  
    cout << distance << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"os"
)

func main() {
	nums := ScanNums(2)
	for _, n := range nums {
		if n%2 == 0 {
			fmt.Print("No")
			os.Exit(0)
		}
	}
	fmt.Print("Yes")
}

func ScanNums(len int) (nums []int) {
	var num int
	for i := 0; i < len; i++ {
		fmt.Scan(&num)
		nums = append(nums, num)
	}
	return
}

Measured memory_bytes: 512
H, W = gets.split(' ').map(&:to_i)
str = $stdin.read
map = Array.new(H + 2) do |h|
  if h == 0 || h == H + 1
    Array.new(W+2, -2)
  else
    Array.new(W+2) do |w|
      (w == 0 || w == W + 1) ? -2 : -1
    end
  end
end
blacks = []
result = 0
# dxy = [[0,1],[1,0],[0,-1],[-1,0]]
BYTE_BLACK = "#".getbyte(0)
BYTE_DOT = ".".getbyte(0)
i = 0
str.bytes do |byte|
  if byte == BYTE_BLACK
    h = (i / W) + 1
    w = (i % W) + 1
    map[h][w] = 0
    blacks.push([h, w])
    i += 1
  elsif byte == BYTE_DOT
    i += 1
  end
end

while(q = blacks.shift) do
  begin
    h, w = q
    result = map[h][w]
    if map[h+1][w] == -1
      map[h+1][w] = map[h][w] + 1
      blacks.push([h+1,w])
    end
    if map[h-1][w] == -1
      map[h-1][w] = map[h][w] + 1
      blacks.push([h-1,w])
    end
    if map[h][w+1] == -1
      map[h][w+1] = map[h][w] + 1
      blacks.push([h,w+1])
    end
    if map[h][w-1] == -1
      map[h][w-1] = map[h][w] + 1
      blacks.push([h,w-1])
    end
    # この書き方だとだいぶ遅くなる
    # 4.times do |i|
    #   y, x = h + dxy[i][0], w + dxy[i][1]
    #   next unless map[y][x] == -1
    #   result = map[h][w] + 1 if result >= map[h][w]
    #   map[y][x] = result
    #   blacks.push [y,x]
    # end
  rescue NoMethodError => e
  end
end
puts result

Measured memory_bytes: 66044
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;


int main() {
  int a, b, ans=0;
  cin >> a >> b;
  
  if(5<a && a<13) ans = b/2;
  else if(12<a) ans = b;
  
  cout << ans << endl;
  
  return 0;
  
}

Measured memory_bytes: 256
#include<algorithm>
#include<cstdio>
#define mxn 10010
#define pii pair<int,int>
#define fr first
#define sc second
#define mp make_pair
#define LL long long
using namespace std;
const int mod=1e9+7;
LL n,A,B,sl,fh;
LL rd()
{
	sl=0;fh=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
	return sl*fh;
}
int main()
{
	n=rd();A=rd();B=rd();if(A<B) swap(A,B);
	if(!((A-B)&1)) printf("%lld\n",(A-B)/2);
	else printf("%lld\n",min(B,n-A+1)+(A-B-1)/2);
	return 0;
}

Measured memory_bytes: 128
import sys
from collections import deque
q = int(input())
S = deque()
for i in range(q):
    l = list(map(int,input().split()))
    if l[0] == 0:
        if l[1] == 0:
            S.appendleft(l[2])
        else:
            S.append(l[2])
    elif l[0] == 1:
        print(S[l[1]])
    else:
        if l[1] == 0:
            S.popleft()
        else:
            S.pop()




Measured memory_bytes: 21984
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    u32 w, h;
    cin >> w >> h;
    vector<ll> v(w+h);
    int k = w+1, l = h+1;
    for (int i = 0; i < w; ++i) {
        int x;
        scanf("%d", &x);
        v[i] = x*2;
    }
    for (int i = 0; i < h; ++i) {
        int x;
        scanf("%d", &x);
        v[w+i] = x*2+1;
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    for (int i = 0; i < w+h; ++i) {
        if(v[i]%2) {
            ans += v[i]/2 * (k);
            l--;
        }else {
            ans += v[i]/2 * (l);
            k--;
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define sz(x) (int)(x.size())
#define mod 1000000007
#define endl "\n"
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;



int32_t main(){
    ios::sync_with_stdio(false);
    int k;
    cin>>k;
    int n;
    cin>>n;
    vi a(n);
    int mini=0;
    REP(i,0,n){
        cin>>a[i];
        if(i!=0){
            mini=max(mini,a[i]-a[i-1]);
        }
    }
    mini=max(mini,a[0]+k-a[n-1]);
    int ans=k-mini;
    cout<<ans<<"\n";


    return 0;
}

Measured memory_bytes: 1792
//Uneven Number
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
	long long x, s = 0, i = 1, y;
	cin >> x;
	y = x;
	while (y != 0) {
		y = y / 10;
		i = ++i;
	}
	i = --i;
	if (i % 2 == 0) {
		for (int k = i - 1; k >= 0; k = k - 2) {
			s = 9 * pow (10, k -1) + s;
		}
	}
	else if (i % 2 == 1) {
		s = x - pow(10, (i-1)) + 1;
		for (int k = i - 2; k >= 0; k = k - 2) {
			s = 9 * pow (10, k - 1) + s;
		}
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin >> str;
    bool isok = true;
    if(str[0]!='A'){
        isok = false;
    }
    int countC = 0;
    int placeC = -1;
    for(int i=2; i<str.size()-1; i++){
        if(str[i]=='C'){
            countC++;
            placeC=i;
        }
    }
    if(countC!=1){
        isok = false;
    }
    for(int i=1; i<str.size(); i++){
        if(i!=placeC){
            if(isupper(str[i])){
                isok = false;
            }
        }
    }
    if(isok){
        cout << "AC" << endl;
    }else{
        cout << "WA" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
from fractions import gcd
N, X = map(int, input().split())
A = list(map(int, input().split()))
g = 0
for i in range(N):
  if i == 0:
    g = gcd(g, abs(X - A[0]))
  else:
    g = gcd(g, abs(A[i] - A[i-1]))
print(g)

Measured memory_bytes: 91056
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N, max = 0;
    cin >> N;
    vector<int> A(N);
    for (auto& i : A) {
        cin >> i;
        if (i > max) max = i;
    }
    vector<int> B(A);
    sort(B.begin(), B.end(), greater<int>());
    for (int i : A) cout << B[i == B[0] ? 1 : 0] << endl;
}


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

import sys
import os


alab = {}
alab['I'] = 1
alab['V'] = 5
alab['X'] = 10
alab['L'] = 50
alab['C'] = 100
alab['D'] = 500
alab['M'] = 1000

for s in sys.stdin:
    s = s.strip()
    #print('s', s)

    A = []
    for c in s:
        A.append(alab[c])
    #print('A', A)

    for i in range(len(A) - 1):
        if A[i] < A[i+1]:
            A[i] *= -1
    #print('A', A)

    print(sum(A))

Measured memory_bytes: 7296