akhauriyash/Code-Regression huggingface dataset:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())

    parent = {x:[] for x in range(1,n+1)}

    ans = [None]*n

    ans[0] = 1

    for _ in range(n-1):
        u,v,w = map(int, input().split())
        length = -2*(w%2)+1
        parent[u].append(length*(v))
        parent[v].append(length*(u))

    base = [1]


    while True:
        pop_num = base.pop()
        for i in parent[pop_num]:
            abs_i = abs(i)
            ans[abs_i-1] = ans[pop_num-1]*(i/abs_i)
            parent[abs_i].remove(pop_num*(i/abs_i))
            base.append(abs_i)
        if len(base) == 0:
            break

    for i in ans:
        if i == 1:
            print('1')
        else:
            print('0')


Measured memory_bytes: 33768
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
using namespace std;

using INT = long long;
using UINT = unsigned long long;

unsigned gcd(unsigned a, unsigned b) {
	while (1) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

const UINT mod = 1000000007;

UINT PowMod(UINT x, UINT y)
{
	if (y == 0)
	{
		return 1;
	}
	else if (y == 1)
	{
		return x % mod;
	}
	else if (y % 2 == 0)
	{
		auto tmp = PowMod(x, y / 2);
		return tmp * tmp % mod;
	}
	else
	{
		auto tmp = PowMod(x, y / 2);
		return (tmp * tmp % mod) * x % mod;
	}
}

UINT getModInv(UINT N)
{
	return PowMod(N, mod - 2);
}

int main()
{
	INT r, D, x;
	cin >> r >> D >> x;
	for (size_t i = 0; i < 10; i++)
	{
		cout << (x = r * x - D) << endl;
	}
}


Measured memory_bytes: 256
N, K = map(int, input().split())

x = [int(i) for i in input().split()]

if N == 1 or K == 1:
    print(x[0])
    exit()

ans = 10**100
for i in range(N):
    if i < N-K+1:
        tmp1 = abs(x[i]) + abs(x[i] - x[i+K-1])
        tmp2 = abs(x[i+K-1]) + abs(x[i] - x[i+K-1])
        ans = min(tmp1, tmp2, ans)

print(ans)

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
long N,K;
long a[200001];
int main()
{
  cin>>N>>K;
  for(long i=1;i<=N;i++)
    cin>>a[i];
 for(long i=K+1;i<=N;i++)
 {
   if(i>K && a[i]>a[i-K])
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
 }
    return 0;
  }

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

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

  vector<int> a(n);
  rep(i,n) {
    cin >> a[i];
    a[i]--;
  }

  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    p[a[i]] = i;
  }
  int max_len = 0;
  int minv = -1;
  int tmp = 0;
  for (int i = 0; i < n; i++) {
    if(p[i] > minv){
      minv = p[i];
      tmp++;
      if(i == n - 1) max_len = max(max_len, tmp);
    } else {
      max_len = max(max_len, tmp);
      minv = p[i];
      tmp = 1;
    }
  }
  cout << n - max_len << '\n';
}

Measured memory_bytes: 1920
from copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    for s in test:
        if num in s:
            s.remove(num)
    if len(ans) is n:
        return 1
    if len(test[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(test[num - 1])):
            tmp = test[num - 1][i]
            if tmp is not 0:
                word = ans + str(tmp)
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    if a is not 1 or b is not 1:
        town[a - 1].append(b)
        town[b - 1].append(a)
print(solve(town, 1, '1', N))


Measured memory_bytes: 3444
#include <bits/stdc++.h>
int a[1000005];
using namespace std;


int main(){
    int n,i,j;
    double r;
    cin>>n;
    for(i=1;i<n;i++)
    {
        scanf("%d",&j);
        a[j]++;
    }
    for(i=1;i<=n;i++)
        printf("%d\n",a[i]);
    return 0;
}


Measured memory_bytes: 4592
#include <bits/stdc++.h>
#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 ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;
int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];
    int ans = -1;
    int now = 0;
    rep(i, n - 1)
    {
        if (a[i] >= a[i + 1])
        {
            now++;
        }
        else
        {
            ans = max(ans, now);
            now = 0;
        }
    }

    cout << max(ans, now)
         << endl;
    return 0;
}


Measured memory_bytes: 640
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if e-a>k:
    print(":(")

elif d-a>k:
    print(":(")

elif e-a>k:
    print(":(")

elif c-a>k:
    print(":(")

elif b-a>k:
    print(":(")

else:
    print("Yay!")

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

int main() {
  int n;
  cin>>n;
  int t[n];
  ll sum=0;
  for(int i=0;i<n;i++) {
    cin>>t[i];
    sum+=t[i];
  }
  int m;
  cin>>m;
  for(int i=0;i<m;i++){
    int p,x;
    cin>>p>>x;
    cout<<sum-t[p-1]+x<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
(let ((n (read))
      (a (make-hash-table)))
  (dotimes (i n)
    (let ((ai (read)))
      (setf (gethash ai a)
            (not (gethash ai a)))))
  (format t "~A~%" (loop for key being each hash-key of a
                         using (hash-value value)
                         when value count value)))


Measured memory_bytes: 67684
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  LL A, B, M;
  cin >> A >> B >> M;
  VEC<LL> a(A);
  VEC<LL> b(B);
  VEC<LL> x(M), y(M), c(M);
  REP(i, 0, A) cin >> a[i];
  REP(i, 0, B) cin >> b[i];
  REP(i, 0, M) cin >> x[i] >> y[i] >> c[i];
  LL mia, mib;
  mia = mib = INT32_MAX;
  REP(i, 0, A) { mia = min(mia, a[i]); }
  REP(i, 0, B) { mib = min(mib, b[i]); }

  LL mi = mia + mib;
  REP(i, 0, M) {
    LL tmp = a[x[i] - 1] + b[y[i] - 1] - c[i];
    mi = min(mi, tmp);
  }
  cout << mi << endl;

  return 0;
}


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

int main() {
    int K;
    cin >> K;
    if(K%2==0){
        cout << pow(K/2,2) << endl;
    }
    else{
        cout << K/2 * (K/2 +1) << endl;
    }
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <cmath>
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

int main(){
  vector<int> syoki(5);
  for(int i = 0;i < 5;i++){
    cin >> syoki.at(i);
  }
  for(int i = 0;i < 5;i++){
    if(syoki.at(i) == 0){
      cout << i + 1 << endl;
      break;
    }
  }
}


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

const int N = 305;
const int md = 1e9 + 7;

int n, m;
vector < pair<int,int> > seg[N];
int dp[N][N][N];

void add(int &x, int y) { x += y; while(x >= md) x -= md; if (x < 0) x += md; }

bool check(int i, int j, int k) {
	for (auto segment : seg[i]) {
		int lef = segment.first; // left point
		int dif = segment.second; // different colors
		int cnt = (i >= lef) + (j >= lef) + (k >= lef);
		if (cnt != dif) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int l, r, x; cin >> l >> r >> x;
		seg[r].push_back(make_pair(l, x));
	}
	dp[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			for (int k = 0; k <= j; ++k) {
				if (!dp[i-1][j][k]) continue;
				int nj, nk;
				// i-1
				if (check(i, j, k)) add(dp[i][j][k], dp[i-1][j][k]);
				// j
				if (check(i, i-1, k)) add(dp[i][i-1][k], dp[i-1][j][k]);
				// k
				if (check(i, i-1, j)) add(dp[i][i-1][j], dp[i-1][j][k]);
			}
		}
	}	

	int ans = 0;
	for (int j = 0; j < n; ++j) {
		for (int k = 0; k <= j; ++k) {
			add(ans, dp[n][j][k]);
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 108928
def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

    n, m = map(int, input().split())

    size = (1 << n)

    dp = [inf] * size
    dp[0] = 0

    for _ in range(m):
        price, _ = map(int, input().split())
        key = sum(1 << ind for ind in (int(x) - 1 for x in input().split()))
        for mask in range(size):
            if dp[mask] == inf:
                continue
            n_mask = (mask | key)
            dp[n_mask] = min(dp[n_mask], dp[mask] + price)

    ans = dp[size - 1]
    print(ans if ans != inf else -1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 43740
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function () { return this.index < this.max },
        "next": function () { if (!this.hasNext()) { throw "ArrayIndexOutOfBoundsException"; } else { return this.list[this.index++]; } }
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    const [N, M] = nextIntArray()
    const ac = new Set()
    const judge = new Array(N).fill(false)
    const cnt = new Array(N).fill(0)
    let wa = 0
    while (hasNext()) {
        let [p, s] = nextStrArray()
        p = Number(p)-1
        if(judge[p]) continue
        if (s == "WA") {
            cnt[p]++
        }
        if (s == "AC") {
            ac.add(p)
            wa += cnt[p]
            judge[p] = true
        }
    }
    console.log(ac.size, wa)
}
Main()



Measured memory_bytes: 50216
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;

int main(){
  string s;
  cin >> s;
  string memo;
  memo = s[0];
  int r = 0;
  int l = 0;
  int addr,addl;
  int ans[s.length()] = {0};
  for(int i = 1; i < s.length(); i++){
    if(memo == "R"){
      if(s[i] == 'R'){
        r++;
      }else{
        r++;
        memo = "L";
        addr = i-1;
        addl = i;
        ans[addr] += (r+1)/2;
        ans[addl] += r/2;
        if(i == s.length()-1){
          ans[addl]++;
        }
      }
    }else{
      if(s[i] == 'L' && i != s.length()-1){
        l++;
      }else{
        l++;
        if(i == s.length()-1 && memo == "L") l++;
        memo = "R";
        ans[addr] += l/2;
        ans[addl] += (l+1)/2;
        r = 0;
        l = 0;
      }
    }

  }
  rep(i,s.length()){
    printf("%d ", ans[i]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main{
      public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int num1 = sc.nextInt();
            int num2 = sc.nextInt();
            int num3 = sc.nextInt();
            if((num1 * 100 + num2 *10 + num3) % 4 == 0){
              System.out.println("YES");
            } else {
              System.out.println("NO");
            }
          }
}

Measured memory_bytes: 21972
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
ll mypow(ll x, ll n, ll m) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return mypow(x*x%m, n / 2, m);
	}
	else {
		return x * mypow(x, n - 1, m) % m;
	}
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
///////////////////////////////////////


int main() {
	ll N; cin >> N;
	if (N == 2) {
		cout << 1 << endl;
		return 0;
	}
	vector<ll>v;
	int cnt = 2;
	for (ll i = 2; i*i <= N; ++i) {
		if (N%i == 0) {
			v.push_back(i);
		}
	}
	for (ll i = 0; i < v.size(); ++i) {
		ll n = N;
		while(n>1) {
			if (n%v[i]==0) {
				n /= v[i];
			}
			else {
				break;
			}
		}
		if (n == 1) {
			cnt++;
		}
		else if (n > v[i]) {
			if (n%v[i] == 1) {
				cnt++;
			}
		}
	}
	for (ll i = 2; i*i <= N - 1; ++i) {
		if (i*i == N - 1) {
			cnt++; 
			continue;
		}
		if ((N - 1) % i == 0) {
			cnt += 2;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<map>
using namespace std;
int n,k,l;
int fg[200000],ft[200000];
map<pair<int,int>,int> s;
int findg(int x)
{
    if(fg[x]!=x) fg[x]=findg(fg[x]);
    return fg[x];
}
void ug(int r1,int r2)
{
    fg[r2]=r1;
}
int findt(int x)
{
    if(ft[x]!=x) ft[x]=findt(ft[x]);
    return ft[x];
}
void ut(int r1,int r2)
{
    ft[r2]=r1;
}
int main()
{
    int r1,r2;
    scanf("%d%d%d",&n,&k,&l);
    for(int i=1;i<=n;i++) fg[i]=ft[i]=i;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&r1,&r2);
        r1=findg(r1);
        r2=findg(r2);
        if(r1!=r2) ug(r1,r2);
    }
    for(int i=1;i<=l;i++)
    {
        scanf("%d%d",&r1,&r2);
        r1=findt(r1);
        r2=findt(r2);
        if(r1!=r2) ut(r1,r2);
    }
    for(int i=1;i<=n;i++)
    {
        findg(i);
        findt(i);
    }
    //首先把问题数据用并查集处理为一个个联通块，
    //要 求既通过公路连通又通过铁路连通的城市数 就转化为了 求各fg与ft的交集元素数 
    //所以只需用map统计每个交集中点的数量即可
    for(int i=1;i<=n;i++)
    {
        s[{fg[i],ft[i]}]++;
        //如果两个点之间既能走公路到达，又能走铁路到达，他们肯定属于同一个交集，那么fg[i]与ft[i]的交集元素数+1 
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",s[{fg[i],ft[i]}]);
    }
    return 0;
}

Measured memory_bytes: 13568
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <sstream>
#include <vector>
#include <map>
#include <ctime>
#include <fstream>
using namespace std;


const int N = 100;
const int M = 200;

int arr[N + 1];
int cost[M + 1];

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

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	int sum = 0;
	for (int i = -100; i <= 100; i++) {
		for (int j = 1; j <= n; j++) {
			sum += pow(arr[j] - i, 2);
		}
		cost[i + 100] = sum;
		sum = 0;
	}

	sort(cost, cost + M + 1);

	cout << cost[0] << endl;


	return 0;
}

Measured memory_bytes: 256
#include <queue>
#include <cstdio>
#include <iostream>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <stack>
using namespace std;
typedef long long int ll;

#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(int i=0;i<n;i++)
const int MOD = 1000000007;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll beki(ll a, ll b) {
	ll tmp = 1;
	REP(i, b) tmp *= a;
	return tmp;
}

int A, B;

int main() {
	cin >> A >> B;
	if (A % 2 == 0 || B % 2 == 0) {
		cout << "No" << endl;
	}
	else cout << "Yes" << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def divisible_count(n):
    result = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            result += 1
            if i != n // i:
                result += 1
    return result


def main():
    N = int(input())
    print(sum(divisible_count(x) == 8 for x in range(1, N + 1, 2)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include<cstdio>
using namespace std;
int x,y,xx,yy,n,m,q,c[2005][2005],cnt[2005][2005],e[2005][2005],e2[2005][2005],e3[2005][2005];
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			scanf("%1d",&c[i][j]);
			e2[i][j]=e2[i][j-1];e3[i][j]=e3[i-1][j];
			if(c[i][j]&&c[i][j-1]) ++e2[i][j];
			if(c[i][j]&&c[i-1][j]) ++e3[i][j];
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+c[i][j];
			e[i][j]=e[i-1][j]+e[i][j-1]-e[i-1][j-1];
			if(c[i][j]){
				if(c[i-1][j]) ++e[i][j];
				if(c[i][j-1]) ++e[i][j];
			}
		}
	while(q--){
		scanf("%d%d%d%d",&x,&y,&xx,&yy);--x;--y;
//		printf("**%d %d**\n",cnt[xx][yy]+cnt[x][y]-cnt[x][yy]-cnt[xx][y],e[xx][yy]+e[x+1][y+1]-e[x+1][yy]-e[xx][y+1]+e2[x+1][yy]-e2[x+1][y+1]+e3[xx][y+1]-e3[x+1][y+1]);
		printf("%d\n",cnt[xx][yy]+cnt[x][y]-cnt[x][yy]-cnt[xx][y]-(e[xx][yy]+e[x+1][y+1]-e[x+1][yy]-e[xx][y+1]+e2[x+1][yy]-e2[x+1][y+1]+e3[xx][y+1]-e3[x+1][y+1]));
	}
}

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

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

signed main() {
	int n, ans = 0;
	cin >> n;
	char be='A';
	rep(i, n) {
		char c;
		cin >> c;
		if (c != be) {
			ans++;
			be = c;
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
r, c = map(int, input().split())
sum_list = [0]*(c+1)
for i in range(r):
    r_i = list(map(int, input().split()))
    r_i.append(sum(r_i))
    sum_list = [a+b for a, b in zip(r_i, sum_list)]
    print(" ".join([str(k) for k in r_i]))
print(" ".join([str(k) for k in sum_list]))



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

int main(){
  int a,b;
  cin>>a>>b;
  int ans;
  for(int i=1;i<1e9;i++){
    int a_ans=i*0.08;
    int b_ans=i*0.1;
    if(a_ans==a&&b_ans==b) {
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
  return 0;
}
    


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i= (a); i < (b); ++i)
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const double PI = 3.14159265358979323846;
int main() { double A, B, H, M;
  cin >> A >> B >> H >> M;
  double itiA, itiB;
  //itiB = (6 * M*PI)/180;
  //itiA = (30 * H*PI)/180;
  itiB = (6 * M);
  itiA = (30* ((M/60)+H));
  double kaku = min(abs(itiB - itiA),abs(itiA-itiB));
  kaku = kaku * PI / 180;
  double ans = 0.5 * A * B * sin(kaku);
 /* ans = abs(ans);
  double f = (A * sin(itiB * PI / 180));
  double c = ans * 2 / (A * sin(itiB * PI / 180));*/
  double c = A * A + B * B - 2 * A * B * cos(kaku);
  cout <<fixed<<setprecision(10)<< sqrt(c) << endl;
}

Measured memory_bytes: 4216
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll w, a, b;
  cin >> w >> a >> b;
  if(a < b) {
    cout << max(0LL, b - a - w) << endl;
  } else {
    cout << max(0LL, a - b - w) << endl;
  }
}

Measured memory_bytes: 3624
N = int(input())
W = []
W.append(input())
for n in range(N-1):
  w = input()
  if w[0] != W[-1][-1]:
    print("No")
    break
  elif W.count(w) != 0:
    print("No")
    break
  W.append(w)
else:
  print("Yes")
  

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define Endl endl
typedef long long ll;
const int MAXN = (int)1e5 + 5;
ll a[MAXN];
string s;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	while (cin >> s)
	{
		memset(a, 0, sizeof(a));
		ll L = 0, R = 0, len = s.size(), pos;
		for (int i = 0; i < len;)
		{
			while (s[i] == 'R')
				R++, i++;
			pos = i;
			while (s[i] == 'L')
				L++, i++;
			L--, R--;
			a[pos - 1] = a[pos] = 1;
			ll cnt = max(R, L);
			for (int j = 1; j <= cnt; ++j)
			{
				swap(a[pos - 1], a[pos]);
				if (R)
					a[pos - 1]++, R--;
				if (L)
					a[pos]++, L--;
			}
			if (cnt & 1)
				swap(a[pos - 1], a[pos]);
		}
		for (int i = 0; i < len; ++i)
			cout << a[i] << ' ';
		cout << endl;
	}
}
/*
RRLRL
RRLLLLRLRRLL
RRRLLRLLRRRLLLLL
*/

Measured memory_bytes: 1488
N,M =map(int,input().split())
hight = list(map(int,input().split()))

good_tower=[1]*N
for i in range(M):
  A,B = map(int,input().split())
  A -=1
  B -=1
  if(hight[A]==hight[B]):
    good_tower[A]=0
    good_tower[B]=0
  elif(hight[A]<hight[B]):
    good_tower[A]=0
  else:
    good_tower[B]=0
print(good_tower.count(1))


Measured memory_bytes: 20016
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
using namespace std;
  
int main () {
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i,n) cin >> p.at(i);
  sort(p.begin(),p.end());
  p.at(n-1) /= 2;
  int ans=0;
  rep(i,n) 
    ans += p.at(i);
  cout << ans;
}

Measured memory_bytes: 256
using System;
using System.Diagnostics.CodeAnalysis;

namespace ChokudaiScanner
{
    class MainClass
    {
        static void Main()
        {
            Scanner cin = new Scanner();

            int N = cin.NextInt();
            int[] d = cin.ArrayInt(N);
            Array.Sort(d);
            int ans = 1;
            for(int i = 1; i < N; i++)
            {
                int a = d[i - 1];
                if (!(a == d[i]))
                {
                    ans++;
                }
            }
            Console.WriteLine(ans);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string Next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return Next();
            i = 0;
            return s[i++];
        }

        public string[] ArrayNext(int N)
        {
            string[] Array = new string[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = Next();
            }
            return Array;
        }

        public int NextInt()
        {
            return int.Parse(Next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextInt() + add;
            }
            return Array;
        }

        public long NextLong()
        {
            return long.Parse(Next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextLong() + add;
            }
            return Array;
        }

        public double NextDouble()
        {
            return double.Parse(Next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextDouble() + add;
            }
            return Array;
        }
    }
}



Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
unsigned long long a,b,c;
unsigned long long f(unsigned long long x){
	if(-1==x){
		return 0;
	}
	else{
		return x/c+1;
	}
}
int main(){
	cin>>a>>b>>c;
	cout<<f(b)-f(a-1);
	return 0;
}

Measured memory_bytes: 256
a = list(input())
count=1
answer=0
newlist=[]
masklist=[]
def Souwa(n):
    s=(1/2)*int(n)*int((n+1))
    return int(s)

for i in range(len(a)):
    if i==len(a)-1:
        newlist.append(count)
    elif a[i] =="<" and a[i+1]==">":
        newlist.append(count)
        masklist.append(1)
        count=1
    elif a[i]==">" and a[i+1]=="<":
        newlist.append(count)
        masklist.append(0)
        count=1
    else:
        count+=1

for i in range(len(masklist)):
    if masklist[i]==1:
        if newlist[i]<newlist[i+1]:
            newlist[i]-=1
        else:
            newlist[i+1]-=1

for i in range(len(newlist)):
    answer+=Souwa(newlist[i])
print(answer)

Measured memory_bytes: 11040
#include<iostream>
#include<vector>
#define M 1e16
using namespace std;
typedef long long int ll;
int main(void){
ll x,y;
ll ans=-1;
cin>>x>>y;
ll z=x;

if(z%y!=0){
	ans=z;
	
}


cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

const int INF = 1 << 25;

using pii = pair<int, int>;

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];
    vec<int, 3> dp = make_v(1 << N, N, 2, INF);
    for (int i = 0; i < N; i++) {
      dp[1 << i][i][i & 1] = i;
    }
    for (int m = 1; m < (1 << N); m++) {
      vector<int> hit;
      vector<pii> miss;
      for (int i = N - 1; i >= 0; i--) {
        if ((m >> i) & 1) {
          hit.push_back(i);
        } else {
          miss.emplace_back(i, hit.size() & 1);
        }
      }
      reverse(hit.begin(), hit.end());
      reverse(miss.begin(), miss.end());
      for (int i : hit) {
        for (int p = 0; p < 2; p++) {
          if (dp[m][i][p] >= INF) continue;
          int v = p == 0 ? A[i] : B[i];
          int k = 0;
          for (auto y : miss) {
            int j = y.fst, jp = y.snd;
            int np = (jp ^ k) & 1;
            int nv = np == 0 ? A[j] : B[j];
            if (v <= nv) {
              chmin(dp[m | (1 << j)][j][np], dp[m][i][p] + k);
            }
            ++k;
          }
        }
      }
    }
    int res = INF;
    for (int i = 0; i < N; i++) {
      for (int p = 0; p < 2; p++) {
        chmin(res, dp[(1 << N) - 1][i][p]);
      }
    }
    cout << (res >= INF ? -1 : res) << endl;
  }
  return 0;
}


Measured memory_bytes: 268544
w = int(input())
n = int(input())

amida = []

for i in range(0,w+1):
    amida.append(i)
    
for i in range(n):
    ai,bi = map(int,input().split(","))
    aa = amida[ai]
    bb = amida[bi]
    amida[ai] = bb
    amida[bi] = aa
    
for i in range(1,w+1):
    print(amida[i])
    


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

using namespace std;

int main()
{
    int n;
    cin>>n;
    int count = 0;
    for(int i=1;i<=n;i++){
        int num = n-i;
        for(int j = 1;j*j<=num;j++){
            if(num%j==0){
                if(j*j==num)
                    count+=1;
                else
                    count+=2;
            }
        }
    }
    
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <cmath>

inline void fastscan(int &num) {
    bool neg = false;
    int c;
    num = 0;
    c = getchar_unlocked();
    if (c == '-') {
        neg = true;
        c = getchar_unlocked();
    }
    for (; (c > 47 && c < 58); c = getchar_unlocked()) num = num * 10 + c - 48;
    if (neg) num *= -1;
}

inline void fastout(int n) {
    int N = n, rev, count = 0;
    rev = N;
    if (N == 0) { putchar_unlocked('0'); putchar_unlocked('\n'); return ;}
    while ((rev % 10) == 0) { count++; rev /= 10;}
    rev = 0;
    while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
    while (rev != 0) { putchar_unlocked(rev % 10 + '0'); rev /= 10;}
    while (count--) putchar_unlocked('0');
}
 
int main(){
    
    int N; fastscan(N);
    int v[N];
    for (int i = 0; i < N; ++i) fastscan(v[i]);
    int sum = 0;
 
    for (int i = 1; i < N; ++i) sum += abs(v[i - 1] - v[i]);
    sum = sum + abs(0 - v[0]) + abs(v[N - 1] - 0);
    int diff[N];
    diff[0] = abs(0 - v[0]) + abs(v[0] - v[1]) - abs(0 - v[1]);
    for (int i = 1; i < N - 1; ++i){
        diff[i] = abs(v[i - 1] - v[i]) + abs(v[i] - v[i + 1]) - abs(v[i - 1] - v[i + 1]);
    }
    diff[N - 1] = abs(v[N - 2] - v[N - 1]) + abs(v[N - 1] - 0) - abs(v[N - 2] - 0);

    for (int i = 0; i < N; ++i){
        fastout(sum - diff[i]); putchar_unlocked('\n');
    }
    return 0;
}

Measured memory_bytes: 2048
#include <iostream>
using namespace std;
int main(){
	
	int n,a;
	cin>>n;
	int pos[n];
	for(int i=0;i<n;i++){
		cin>>a;
		pos[a-1]=i+1;
	}
	for(int i=0;i<n;i++){
		cout<<pos[i]<<' ';
	}
	cout<<endl;
	
	return 0;
}

Measured memory_bytes: 1152
n=int(input())
a=list(map(int, input().split()))

def bubble(a:list, n:int) -> None:
    if not isinstance(a, list):
        return None

    cnt=0
    flag=1
    while flag:
        flag=0
        for j in range(n-1,0,-1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
                flag=1
                cnt+=1

    print(" ".join(map(str, a)))
    print(cnt)

bubble(a, n)


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

int main(){
    int n;
    cin >> n;
    int num = n/111;
    if(n%111 != 0 ) ++num;
    cout << num*111 << endl;
}

Measured memory_bytes: 256
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

pub fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let hwk: Vec<usize> = read_vec();
    let h = hwk[0];
    let w = hwk[1];
    let k = hwk[2];
    let mut s: Vec<Vec<char>> = vec![];
    let mut a: Vec<Vec<u32>> = vec![vec![0; w]; h];
    for _ in 0..h {
        let tmp: String = read();
        let tmp2: Vec<char> = tmp.chars().collect();
        s.push(tmp2);
    }
    let mut first = h;
    for i in 0..h {
        if s[i].contains(&'#') {
            first = i;
            break;
        }
    }
    let mut tmp = 0;
    for i in first..h {
        if s[i].contains(&'#') {
            let mut w0: usize = 0;
            while s[i][w0] == '.' {
                w0 += 1;
            }
            for j in 0..w0 {
                a[i][j] = tmp + 1;
            }
            for j in w0..w {
                if s[i][j] == '#' {
                    tmp += 1;
                }
                a[i][j] = tmp;
            }
        } else {
            for j in 0..w {
                a[i][j] = a[i - 1][j];
            }
        }
    }

    for i in 0..first {
        for j in 0..w {
            a[i][j] = a[first][j];
        }
    }

    for i in 0..h {
        for j in 0..w {
            print!("{}", a[i][j]);
            if j == w - 1 {
                println!("");
            } else {
                print!(" ");
            }
        }
    }
}


Measured memory_bytes: 4860
#include<algorithm>
#include<functional>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define FOR(itr,data) for(__typeof((data).begin()) itr=(data).begin();itr!=(data).end();++itr)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

typedef unsigned long long UInt64;
typedef long long Int64;

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

using namespace std;

typedef pair<int ,int > P;


int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(a&b||c) cout<<"Open"<<endl;
	else cout<<"Close"<<endl;
		return 0;
}

Measured memory_bytes: 1160
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 h = sc.nextInt();
    int m = sc.nextInt();

    int keika = 60 * h + m;
    double seta = Math.toRadians(Math.abs(keika * 0.5 - m * 6));
    System.out.println(Math.sqrt(Math.pow(a, 2) + Math.pow(b, 2) - 2 * a * b * Math.cos(seta)));
  }
}


Measured memory_bytes: 27148
// Starting with the name of Allah

#include <bits/stdc++.h>
#define ll long long
#define nl endl
#define Nayon ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define gcd(a,b)         __gcd(a,b)
#define lcm(a,b)         (a/gcd(a,b))*b
#define v_sum(a)         accumulate(a.begin(),a.end(),0)
#define v_max(a)         *max_element(a.begin(),a.end())
#define v_min(a)         *min_element(a.begin(),a.end())
#define v_uni(a)         a.erase(unique(a.begin(),a.end()),a.end())

using namespace std;




int main()
{
	Nayon;
	ll t,a,b;
	cin>>a;
	if(a>=30){
		cout<<"Yes"<<nl;
	}
	else{
		cout<<"No"<<nl;
	}
	return 0;
}


Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define vec(x) vector<x>
#define IINF INT_MAX
#define LLINF LLONG_MAX
ll gcd(ll a,ll b){while(b){ll tmp = a % b;a = b;b = tmp;}return a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define out(x) for(auto i : x) cout << i << " "; cout << endl;
#define outln(x) for(auto i : x) cout << i << endl;
#define vec_cpy(to,from) copy(all(to),back_inserter(from))
#define ary_cpy(to,from) memcpy(to, from, sizeof from)
#define MOD 1000000007
#ifdef DEBUG
   #define debug_echo(expr) cout << expr;
   #define debug_var(var) cout << #var << ": " << var << endl;
#else
   #define debug_echo(expr)
   #define debug_var(var)
#endif

int main(){
  int n;cin >> n;
  vec(int) p(3);
  set<vector<int>> st;
  rep(i,n){
    cin >> p[0] >> p[1] >> p[2];
    sort(all(p));
    st.insert(p);
  }

  cout << (n - st.size()) << endl;
  return 0;
}

Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

int main() {
	ll N;
	cin >> N;
	ll A[N];
	for(int i = 0; i < N; i++) cin >> A[i];

	ll sum[N];
	sum[0] = A[0];
	for(int i = 1; i < N; i++) {
		sum[i] = sum[i - 1] + A[i];
		sum[i] %= mod;
	}

	ll ans = 0;
	for(int i = 0; i < N - 1; i++) {
		ans += (sum[N - 1] * A[i]) % mod - (sum[i] * A[i]) % mod;
		ans %= mod;
		if(ans < 0) ans += mod;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 6752
class Node():
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
        self.depth = 0
        self.sibling = -1
        self.degree = 0
        self.height = -1
        return

def getAncestor(t, n):
    for i in range(n):
        if t[i].parent == -1:
            return i

def setDepth(t, u, p=0):#u : 自分ノードの番号
    t[u].depth = p
    if t[u].left != -1:
        setDepth(t, t[u].left,p+1)
    if t[u].right != -1:
        setDepth(t, t[u].right,p+1)
    return

def seeHeight(h, u):
    h1 = 0
    h2 = 0
    if t[u].right != -1:
        h1 = seeHeight(t[u].height, t[u].right) + 1
    if t[u].left != -1:
        h2 = seeHeight(t[u].height, t[u].left) + 1

    t[u].height = max(h1, h2)
    return t[u].height

import sys

n = int(input())
t = []
for _ in range(n):
    t.append(Node())

for i in range(n):
    a = list(map(int, sys.stdin.readline().split()))
    m = a[0]
    t[m].left = a[1]
    t[m].right = a[2]
    if a[1] != -1:
        t[m].degree += 1
        t[a[1]].parent = m
        t[a[1]].sibling = a[2]
    if a[2] != -1:
        t[m].degree += 1
        t[a[2]].parent = m
        t[a[2]].sibling = a[1]

r = getAncestor(t, n)
setDepth(t, r)
seeHeight(-1, r)

for i in range(n):
    if i == r:
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, root'.format(i, t[i].parent, t[i].sibling, t[i].degree, t[i].depth, t[i].height))
    elif t[i].degree == 0:
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, leaf'.format(i, t[i].parent, t[i].sibling, t[i].degree, t[i].depth, t[i].height))
    else:
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, internal node'.format(i, t[i].parent, t[i].sibling, t[i].degree, t[i].depth, t[i].height))




Measured memory_bytes: 5628
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>
 
using namespace std;
using ll = long long;
 
void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
 
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Unique(a) a.erase(unique(Range(a)), a.end());
#define Reverse(c) reverse(Range(c))
#define Vec2(T, n, m, xs) vector<vector<T>> xs(n, vector<T>(m))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, n, xs, sxs) vector<T> sxs(n+1); For(i, n) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

int main(void){
    Cin(int, n);
    Cinm(int, n, m);
    int ans = 0;
    for(auto e : m) if(e.second % 2) ans ++;
    Cout(ans);
}


Measured memory_bytes: 4388
#include<bits/stdc++.h>
using namespace std;
bool is_palindrome(string s){
	int n=s.size();
	for(int i=0;i<=n/2;i++){
		if(s[i]!=s[n-1-i])
			return false;
	}
	return true;
}
int main(){
	string s; cin>>s;
	int n=s.size();
	int len1=(n-1)/2, len2=(n+3)/2-1;
	string s1=s.substr(0,len1);
	string s2=s.substr(len2);
	if(is_palindrome(s) && is_palindrome(s1) && is_palindrome(s2)) 
		cout<<"Yes"<<endl;
	else 
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long m = sc.nextLong();
		long ans;
		if (n <= m / 2) {
		    ans = n;
		    m -= 2 * n;
		    ans += m / 4;
		} else {
		    ans = m / 2;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
# coding: utf-8
n = int(input())
data = []
for i in range(n):
    s, t = map(str, input().split())
    data.append([s, int(t)])

x = input()
flag = False
ans = 0
for i in range(n):
    if x == data[i][0]:
        flag = True
        continue
    if flag:
        ans += data[i][1]

print(ans)


Measured memory_bytes: 3060
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

print(1-II())



Measured memory_bytes: 9176
#include <iostream>
#include <string>
using namespace std;
int main()
{
	int n, k;
	string s;
	cin >> n >> k >> s;
	if(s[k-1] == 'A') s[k-1] = 'a';
	if(s[k-1] == 'B') s[k-1] = 'b';
	if(s[k-1] == 'C') s[k-1] = 'c';
	cout << s <<endl;
	return 0;
}

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

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    int maxv = a[1]-a[0];
    int minv = a[0];
    for(int i=1;i<n;i++){
        maxv = max(maxv, a[i]-minv);
        minv = min(minv, a[i]);
    }
            
    cout << maxv << endl;
    return 0;
}




Measured memory_bytes: 3552
n = gets.to_i
    towns = (0...n).to_a
    array = []
    n.times do
      x,y = gets.split(" ").map {|v| v.to_i}
      array << [x,y]
    end
    pairs = []
    #始点から終点を結ぶ道を書き足せば綺麗に割れそうな予感がある
    for start in towns
      for goal in towns - [start]
        pairs.push([start, goal].sort).uniq!
      end
    end
    #道を町の数-1回選ぶ？
    #既に通った町に向かう道は選べない
    #町が8つの時、道は28本（8*7/2）あり、その内7本を選ぶ
    d = 0
    #平均さえ求めればいいのだから、全部足して割ればよい？
    for pair in pairs
      dis = (array[pair[0]][0] - array[pair[1]][0]) ** 2 + (array[pair[0]][1] - array[pair[1]][1]) ** 2
      d += Math.sqrt(dis)
    end
    puts d * (n - 1) / pairs.size

Measured memory_bytes: 14272