akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    input!{
        n: usize,
        a: [i32; n],
    }
    let mut xacc = vec![0; n + 1];
    let mut sacc = vec![0; n + 1];
    for i in 0 .. n {
        xacc[i + 1] = xacc[i] ^ a[i];
        sacc[i + 1] = sacc[i] + a[i];
    }
    let mut ans: u64 = 0;
    for i in 0 .. n {
        let mut pass = i;
        let mut fail = n;
        while fail - pass > 1 {
            let mid = (fail + pass) / 2;
            if sacc[mid + 1] - sacc[i] == (xacc[mid + 1] ^ xacc[i]) {
                pass = mid;
            } else {
                fail = mid;
            }
        }
        ans += (pass + 1 - i) as u64;
    }
    puts!("{}\n", ans);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 10620
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
  string s;
  cin >> s;
  vector<bool> a(3, false);
  for (int i = 0; i < 3; i++) {
    a[s[i] - '0' - 49] = true;
  }
  for (int i = 0; i < 3; i++) {
    if (a[i] == false) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 888
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    int n,k,h,s= 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> h;
        if(h >= k)
            s += 1;
    }
    cout << s;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define rint register int
using namespace std;
const int N=1e5+50;
int n,a[N<<1],Q,f[35][N],L;
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]); 
  scanf("%d",&L);
  for(int i=1;i<=n;i++)
    {
        int x=upper_bound(a+i+1,a+n+1,a[i]+L)-a-1;
        f[0][i]=x;
    }
  for(int j=1;j<=30;j++)
    for(int i=1;i<=n;i++)
      f[j][i]=f[j-1][f[j-1][i]];
  scanf("%d",&Q);
  while(Q--)
  {
  	int l,r,ans=0;
  	scanf("%d%d",&l,&r);
  	if(l>r) swap(l,r); 
  	for(int i=30;i>=0;i--)
  	{  
	  if(f[i][l]<r) l=f[i][l],ans+=(1<<i);	
  	}
  	printf("%d\n",ans+1);
  }
  return 0;
}


Measured memory_bytes: 15104
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
//ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}
//ld dis(ll a,ll b,ll c,ll d){return sqrt((a-c)*(a-c)+(b-d)*(b-d)) ;}

int main(){
	ll n,k ;
	cin >> n >> k ;
	if(k>n*(n-1)/2-(n-1)) cout << -1 << endl ;
	else{
		cout << n-1+(n*(n-1)/2-(n-1)-k) << endl ;
		for(int i=1;i<n;i++) cout << "1 " << i+1 << endl ;
		ll cnt = n*(n-1)/2-(n-1)-k ;
		for(int i=1;i<n&&cnt!=0;i++){
			for(int j=i+1;j<n&&cnt!=0;j++){
				cnt-- ;
				cout << i+1 << " " << j+1 << endl ;
			}
		}
	}
}


Measured memory_bytes: 256
#define _DEBUG 1
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#ifdef _DEBUG
#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z)                                                     \
  cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z \
       << endl
#define check(s) cerr << s << endl
#else
#define dump(x)
#define dump2(x, y)
#define dump3(x, y, z)
#define check(s)
#endif

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());

const ll LINF = 2e18;
const int INF = 1e9;

void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
void yesOrNo(bool flg) {
  if (flg)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

void solve(ll N, ll A) {
  bool result = (N % 500) <= A;
  yesOrNo(result);
}

int main() {
  ll N;
  scanf("%lld", &N);
  ll A;
  scanf("%lld", &A);
  solve(N, A);
  return 0;
}


Measured memory_bytes: 256
import heapq

def readlines(n):
    for _ in range(n):
        b, c = map(int, input().split())
        yield b, c

def main():
    _, M = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)
    heapq.heapify(A)

    for b, c in sorted(readlines(M), key=lambda x: -x[1]):
        for _ in range(b):
            o = heapq.heappushpop(A, c)
            if o < c:
                total += c - o
            else:
                break
            
    print(total)

main()

Measured memory_bytes: 25720
#include <cstdio>
#include <algorithm>    
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <cstring>
#include <cmath>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int uii;
typedef pair<int,int> pii;
typedef unsigned long long uLL; 
typedef vector<int> vii; 
//__int128

int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	int n, k, x[55], t[55];
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n; ++i){
		cin >> x[i];
	}
	int res = 0;
	for(int a = 0; a <= n; ++a){
		for(int b = 0; b <= n; ++ b){
			for(int c = 0; c <= a; ++c){
				for(int d = 0; d <= b; ++d){
					if(a + b + c + d <= k && a + b <= n){
						memcpy(t, x, sizeof(t));
						sort(t, t + a);
						int tot = 0;
						for(int i = c; i < a; ++i){
							tot += t[i];
						}
						sort(t - b + n, t + n);
						for(int i = n - b + d; i < n; ++i){
							tot += t[i];
						}
						// res = max(tot, res);
						if(tot > res){
							// cout << a << b << c << d << endl;
							res = tot;
						}
					}
				}
			}
		}
	}
	cout << res << endl;
	return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> v(N,0);
  
  int kind = 0;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if (v[x-1] == 0) kind += 1;
    v[x-1] += 1;
  }
  sort(v.begin(), v.end());
  
  int op = 0;
  int del_k = kind - K;
  int i = 0;
  for (int j = 0; j < del_k; i++) {
    if (v[i] == 0) continue;
    op += v[i];
    j++;
  }
  
  cout << op << endl;
}

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

namespace _1_4_A {
    class Program {
        static void Main(string[] args) {
            var input = Console.ReadLine().Split(' ');
            var numbers = input.Select(x => int.Parse(x)).ToArray();
            Console.WriteLine($"{numbers[0] / numbers[1]} {numbers[0] % numbers[1]} {(double)numbers[0] / numbers[1]:0.000000000}");
        }
    }
}



Measured memory_bytes: 18444
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    AIN(ll, A, N);
    ll ans = 0;
    REP1(i, N - 1)
    {
        ans += max(0LL, A[i - 1] - A[i]);
        if (A[i] < A[i - 1])
        {
            A[i] = A[i - 1];
        }
    }
    OUT(ans);
}

Measured memory_bytes: 4676
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    string x;
    cin >> x;
    int n = x.size();
    int t = 0;
    int s = 0;
    int maxt = 0;
    int maxs = 0;

    rep(i, n) {
        if(x[i] == 'T') {
            t++;
        }
        else {
            t--;
        }

        if(maxt < t) {
            maxt = t;
        }
    }

    for(int i = n-1; i >= 0; i--) {
        if(x[i] == 'S') {
            s++;
        }
        else {
            s--;
        }

        if(maxs < s) {
            maxs = s;
        }
    }

    int ans = maxt + maxs;

    cout << ans;

    cout << endl;
    return 0;
}

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n,t;
  cin >> n >> t;

  vll a(n), b(n);
  vector<pll> ab(n);
  REP(i, n)
    cin >> ab[i].FI >> ab[i].SE;

  sort(ab.begin(), ab.end());
  ll dp[n+1][t+1];
  REP(i, n+1){
    REP(j, t+1)
      dp[i][j] = 0;
  }


  REP(i, n){
    for(int j = t-1; j>=0; j--){
      ll time = ab[i].FI;
      ll value = ab[i].SE;
      dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
      dp[i+1][min(t, j+time)] = max(dp[i+1][min(t, j+time)], dp[i][j]+value);
    }

  }


  ll ans = 0;
  for(int i = 0; i <= n; i++){
    ans = max(ans, dp[i][t]);
  }

  cout << ans << endl;



}


Measured memory_bytes: 70656
#include <iostream>
#include <cstdio>

char s[16];

int main(int argc, char *argv[]) {
  scanf("%s", s);
  int digits = 0;
  for(int i = 0; ; i++){
    if(s[i] < '0' || '9' < s[i]) {
      s[i] = 0;
      digits = i;
      break;
    }
    s[i] -= '0';
  }
  uint64_t grand_total = 0;
  for(int bits = 0; bits < (1 << (digits - 1)); bits++){
    uint64_t sum = 0;
    uint64_t last_num = 0;
    for(int i = 0; i < digits - 1; i++){
      last_num *= 10;
      last_num += s[i];
      if((bits & (1 << i)) == 0) continue;
      sum += last_num;
      last_num = 0;
    }
    last_num *= 10;
    last_num += s[digits - 1];
    sum += last_num;
    grand_total += sum;
  }
  std::cout << grand_total << std::endl;
  return 0;
}


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

int main(){

    int N;
    cin >> N;
    string S[N];
    for(int i = 0;i<N;i++) cin >> S[i];

    //重複消去
    /*
    for(int i = 0;i<N;i++){
        if(i != 0){
            for(int j = 0;j<i;j++){
                if(S[i] == S[j]){
                    S[i] == ".....";
                    break;
                }
            }
        }
    }
    */
    //S.sort();
    //S.unique();

    long long int M=0,A=0,R=0,C=0,H=0;
    long long int ans;

    string s;
    bool flag;
    for(int i = 0;i<N;i++){
        /*
        flag = false;
        if(i != 0){
            for(int j = 0;j<i;j++){
                if(S[i] == S[j]) break;
                else flag = true;
            }
        }
        else if (i == 0) flag = true;
        */
        //if(flag){
            s = S[i][0];
            if(s == "M") M++;
            else if(s == "A") A++;
            else if(s == "R") R++;
            else if(s == "C") C++;
            else if(s == "H") H++;
        //}
    }

    ans = M*A*R + M*A*C + M*A*H + M*R*C + M*R*H + M*C*H + A*R*C + A*R*H + A*C*H +R*C*H;
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 6144
from collections import Counter

N, M = map(int, input().split())
X = list(map(int, input().split()))

dupCnt = Counter()
modCnt = Counter()

for x, c in Counter(X).items():
    x %= M
    dupCnt[x] += c // 2
    modCnt[x] += c

ans = 0
for i in range(M):
    j = M - i
    if i > j:
        break
    if i == j or i == 0:
        ans += modCnt[i] // 2
        continue

    mi = min(modCnt[i], modCnt[j])
    ans += mi

    ans += min((modCnt[i] - mi) // 2, dupCnt[i])
    ans += min((modCnt[j] - mi) // 2, dupCnt[j])

print(ans)


Measured memory_bytes: 35932
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

/* エラトステネスのふるい

   O(n log log n) だいたい線形。 10万とかは余裕
*/
template<typename T>
std::vector<T> sieve(T n)
{
    std::vector<T> primes;
    std::vector<bool> is_prime(n, true);
    is_prime[0] = is_prime[1] = false;

    for (T i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (T j = 2 * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}



int main()
{
    int64_t N;
    std::cin >> N;

    auto pv = sieve((int64_t)55555);

    int c = 0;
    for (auto p: pv) {
        if (p % 5 == 1) {
            std::cout << p;
            c++;
            if (c == N) {
                return 0;
            }
            else {
                std::cout << " ";
            }
        }
    }
    return 0;
}


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

int main(){
    int a, b;
    cin >> a >> b;
    int ans = 1;
    while(ans<=1000){
        int x = (ans * 8) / 100;
        int y = (ans * 10) / 100;
        if(x==a && y==b)
            break;
        ans++;
    }
    if(ans<=1000)
        cout << ans << endl;
    else cout << "-1\n";
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
void setIO(string name = "b") {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}

int main() {
    //setIO();
    string a, b, c; cin >> a >> b >> c;
    int p1 = 0, p2 = 0, p3 = 0; int cur = 1;
    char ans;
    while (p1 <= a.length() && p2 <= b.length() && p3 <= c.length()) {
        if (cur == 1) {
            if (p1 == a.length()) {
                ans = 'A';
                break;
            }
            cur = (a[p1] - 'a') + 1;
            p1++;
        } else if (cur == 2) {
            if (p2 == b.length()) {
                ans = 'B';
                break;
            }
            cur = (b[p2] - 'a') + 1;
            p2++;
        } else if (cur == 3) {
            if (p3 == c.length()) {
                ans = 'C';
                break;
            }
            cur = (c[p3] - 'a') + 1;
            p3++;
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 3600
n,m = map(int,input().split())
l = []
r = []

for i in range(m):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)
left = max(l)
right = min(r)

if left > right:
    print(0)
else:
    print(right - left + 1)


Measured memory_bytes: 10996
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define MOD_Q 998244353
#define PI 3.14159265358979
#define ll long long
using namespace std;

bool isEqual(vector<int> per, vector<int> p)
{
	int n = p.size();
	for (int i = 0; i < n; i++) {
		if (per[i] != p[i]) {
			return false;
		}
	}

	return true;
}

int main()
{
	int n;
	cin >> n;
	vector<int> per(n);
	vector<int> p(n);
	vector<int> q(n);

	for (int i = 0; i < n; i++) {
		cin >> p[i];
		per[i] = i + 1;
	}
	for (int i = 0; i < n; i++) {
		cin >> q[i];
	}

	int a = 0, b = 0, x = 1;

	do {
		if (isEqual(per, p))a = x;
		if (isEqual(per, q))b = x;
		x++;
	} while (next_permutation(per.begin(), per.end()) && a * b == 0);

	printf("%d", a > b ? a - b : b - a);

	return 0;
}



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

int main() {
	int n;
	bool clear = true;
	cin >> n;
	string s[100];
	for (int i = 0; i < n; i++) {
		cin >> s[i];

		if (i == 0) {
			continue;
		}

		if (s[i - 1][s[i - 1].size() - 1] != s[i][0]) {
			clear = false;
		}

		for (int j = 0; j < i - 1; j++) {
			if (s[i] == s[j]) {
				clear = false;
			}
		}

		if (!clear) {
			break;
		}
	}
	if (clear) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

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

int main(){
  int n;
  string s;
  cin >> n >> s;
  
  int ans = 0;
  for(int i = 1; i < n; i++){
    vector<int> ch1(26, 0);
    vector<int> ch2(26, 0);
    string s1 = s.substr(0, i);
    string s2 = s.substr(i);
    int tmp = 0;
    
    for(int j = 0; j < s1.size(); j++){
      ch1[s1[j] - 'a'] = 1;
    }
    for(int j = 0; j < s2.size(); j++){
      ch2[s2[j] - 'a'] = 1;
    }
    for(int j = 0; j < 26; j++){
      tmp += ch1[j] & ch2[j];
    }
    ans = max(ans, tmp);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();

		BigDecimal nums[] = new BigDecimal[n];
		for(int i=0; i<n; i++) {
			nums[i]=new BigDecimal(sc.nextInt());
		}
		
		BigDecimal molecule = new BigDecimal(1);
		for(int i=0; i<n; i++) {
			molecule=molecule.multiply(nums[i]);
		}
		
		BigDecimal denominator = new BigDecimal(0);
		
		for(int i=0; i<n; i++) {
			denominator=denominator.add(molecule.divide(nums[i]));
		}

		System.out.println(molecule.divide(denominator, 10, BigDecimal.ROUND_HALF_UP));

	}
}

Measured memory_bytes: 23252
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#define MOD (1000000007l)

using namespace std;

int main(void) {
  long N, M, C;
  cin >> N >> M >> C;
  vector<long> B;
  for (long i = 0; i < M; i++) {
    long tmp;
    cin >> tmp;
    B.push_back(tmp);
  }
  long ret = 0;
  for (long i = 0; i < N; i++) {
    long result = 0;
    for (long j = 0; j < M; j++) {
      long tmp;
      cin >> tmp;
      result += tmp * B[j];
    }
    result += C;
    if (result > 0) ret++;
  }
  cout << ret << endl;
  return 0;
}


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

int main(){
    int N; cin >> N;
    int N_2 = N+1;
    int ans = N / 1.08; 
    int ans_2 = N_2 / 1.08;
    //cout << ans << " " << ans_2 << endl;
    //cout << floor((double)ans * 1.08) << " " << floor((double)ans_2 * 1.08) << endl;
    if(floor((double)ans * 1.08) != N && floor((double)ans_2 * 1.08) != N) cout << ":(" << endl;
    else if(floor((double)ans * 1.08) == N) cout << ans << endl;
    else if(floor((double)ans_2 * 1.08) == N) cout << ans_2 << endl;
    //else cout << ans << endl;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

const int nmax = 1e9 + 7;
const long long INF = 1e18;
const double PI = 2 * asin(1);
typedef long long ll;


int main(){
  ll H, W; int N; cin >> H >> W >> N;

  vector < pair<int, int> > AB;
  int da[3] = {-1, 0, 1}, db[3] = {-1, 0, 1};
  for (int i = 0; i < N; i++){
    int A, B; cin >> A >> B;
    for (int j = 0; j < 3; j++){
      for (int k = 0; k < 3; k++){
        int I = A + da[j], J = B + db[k];
        if (2 <= I && I <= H - 1 && 2 <= J && J <= W - 1){
          AB.push_back(make_pair(I, J));
        }
      }
    }
  }
  sort(AB.begin(), AB.end());

  vector <ll> ans(10);
  ans[0] = (H - 2) * (W - 2);

  if (N > 0){
  int cnt = 1;
  for (int i = 0; i < AB.size() - 1; i++){
    if (AB[i] == AB[i + 1]){
      cnt++;
    }else{
      ans[cnt]++;
      ans[0]--;
      cnt = 1;
    }
  }
  ans[cnt]++; ans[0]--;
  }

  for (int i = 0; i < 10; i++){
    cout << ans[i] << endl;
  }
  

  return 0;
}


Measured memory_bytes: 10092
#include<stdio.h>

int main()

{
    int x[10000],i=0;
    while(1){
        scanf("%d",&x[i]);
        if(x[i]==0){break;}
        i++;
    }
    int k = i;
    for(i = 0;i<k;i++){
        printf("Case %d: %d\n",i+1,x[i]);
    }
    return 0;
}



Measured memory_bytes: 2044
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <map>
#include <cstdio>
#include <iomanip>
#include <list>
#include <set>

using namespace std;

int main(void) {
	long long N, K;
	long long ans = 0;
	scanf("%lld %lld\n", &N, &K);

	if (K % 2 == 0) {
		ans = (N / K)*(N / K)*(N / K);
		long long b = (N + K / 2) / K;
		ans += b * b * b;
	}
	else {
		ans = (N / K)*(N / K)*(N / K);
	}
	
	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n))
#define Vec(a,n) vector<string> (a)((n))
using namespace std;
signed main(){
	int n,a,b;
	cin >> n >> a >> b;
	if(a > b){
		cout << 0 << endl;
	}
	else{
		int min = a * (n-1) + b;
		int max = a + b * (n-1);
		max = max-min+1;
		(max > 0)? cout << max << endl : cout << 0 << endl;
	}

    return 0;
}

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

int main()
{
    ll A, B, C, D;
    cin >> A >> B >> C >> D;

    while (A > 0 && C > 0)
    {
        C -= B;
        if (C <= 0)
        {
            cout << "Yes" << endl;
            break;
        }

        A -= D;
        if (A <= 0)
        {
            cout << "No" << endl;
            break;
        }
    }
}


Measured memory_bytes: 3624
def swap(a, b):
    return b, a

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = swap(A[i], A[j])
    A[i+1], A[r] = swap(A[i+1], A[r])
    return A, i+1 

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

B, i = partition(A, 0, n-1)
print(*B[0:i], sep=" ", end=" ")
print("[{0}]".format(B[i]), end=" ")
print(*B[i+1:], sep=" ")


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

int main() {
    int n;
    cin >> n;
    vector<int> L(n);
    rep(i,n) cin >> L[i];
    sort(L.begin(), L.end());
    int ans = 0;
    rep(b,n)rep(a,b) {
        int ab = L[a]+L[b];
        int r = lower_bound(L.begin(), L.end(), ab) - L.begin();
        int l = b+1;
        ans += r-l;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3576
import java.util.*

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

fun problem124c(s: String): Int {
    val BLACK = "0"
    val WHITE = "1"
    val dp = (s.indices).map { "0" }.toMutableList()
    var count = 0
    dp[0] = s[0].toString()
    for (i in 1 until s.length) {
        if (s[i].toString() == BLACK && dp[i - 1] == BLACK) {
            count++
            dp[i] = WHITE
        } else if(s[i].toString() == WHITE && dp[i - 1] == WHITE) {
            count++
            dp[i] = BLACK
        } else {
            dp[i] = s[i].toString()
        }
    }
    return count
}

Measured memory_bytes: 44560
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
using namespace std;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	for (int i = b; i <= c; i++) {
		if (i % a == 0) {
			cout << "OK" << endl;
			return 0;
		}
	}
	cout << "NG" << endl;
}

Measured memory_bytes: 3636
#include <stdio.h>
int main(void){
    /* 変数宣言，ちゃんと初期化しよう */
    int A = 0;
    int B = 0;
    int ans = 0;
    /* 変数宣言終わり */
    
    /* 入力を受け付ける部分*/
    
    // %dはdecimalの略．つまり，入力を10進数として扱うよという意味．
    scanf("%d %d", &A, &B);
    
    /* 入力を受け付ける部分終わり*/
    
    
    /* 何か処理*/
        ans = A*B;
    
    if(A%B == 0){
      /* 真の場合の処理 */
      ans = 0; 
    }else{
      /* 偽の場合の処理 */
      ans = 1;
    }
    
    for(int i = 0; i < 10; i++){ 
      // i = 0,1,2,3,4,5,6,7,8,9のとき処理される
      
    }
    
    /* 何か処理終わり*/
    
    
    /* 出力する部分*/
    
    printf("%d", ans); // %dの部分にansの値が表示される
    
    /* 出力する部分*/
    
    
    
    return 0;
}






Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> v(N); rep(i, 0, N) { cin >> v[i]; }
	int ans(0);
	int l(0);
	while (l < N) {
		int r1(l + 1);
		while (r1 < N&&v[r1] >= v[r1 - 1])r1++;
		int r2(l + 1);
		while (r2 < N&&v[r2] <= v[r2 - 1])r2++;
		l = max(r1, r2);
		ans++;

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

Measured memory_bytes: 640
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)


Measured memory_bytes: 92584
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

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

    ll ans = 0;
    for (ll i = 1; i <= N; i++) {
        if (to_string(i).size() % 2 == 1) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin >> n >> m;
    char a[256][256], b[256][256];
    
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin >> a[i][j];

    for(int i=0;i<m;i++) for(int j=0;j<m;j++) cin >> b[i][j];
    
    bool exist = false;
    
    for(int i2=0;i2<n;i2++){
        for(int j2=0;j2<n;j2++){
            if(i2+m-1>=n||j2+m-1>=n) continue;
            
            bool point = true;
            for(int i=0;i<m;i++){
                for(int j=0;j<m;j++){
                    if(a[i+i2][j+j2] != b[i][j]) point = false;
                }
            }
            if(point) exist = true;
        }
    }
    
    if(exist){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
}


Measured memory_bytes: 256
n,m = list(map(int, input().split()))
cities = [0 for i in range(n)]
for i in range(m):
    bridges = list(map(int, input().split()))
    cities = [x+1 if i+1 in bridges else x for i,x in enumerate(cities)]
print("\n".join(list(map(str, cities))))

Measured memory_bytes: 3060
import math
def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    P_e = []
    for p in P:
        P_e.append((1 + p)/2)

    P_sum = [0]
    tmp = 0
    for i in range(N):
        tmp += P_e[i]
        P_sum.append(tmp)

    max = 0
    for i in range(K, N+1):
        tmp = P_sum[i] - P_sum[i-K]
        if tmp > max:
            max = tmp

    print(max)
    return 0
if __name__ == '__main__':
    main()

Measured memory_bytes: 25060
n,m = map(int,input().split())

li = [True] * n

a = 1 + m
if m % 2 == 0:
    for i in range(m//2):
        print(1+i, a-i)
    for i in range(m//2):
        print(a+1+i, a+m-i)

else:
    for i in range((m+1)//2):
        print(1+i, a-i)
    for i in range(m//2):
        print(a+1+i, a+m-i)


Measured memory_bytes: 10316
#include <stdio.h>
int main (){
	int n;
	long long int total = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		if(i%3 != 0 && i%5 != 0){
			total += i;
		}
	}
	printf("%lld", total);
	return 0;
}

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

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  for(int i=1;i<=100;i++){
    if((b*i+c)%a==0){
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
  return 0;
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

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

	int K, X;
	cin >> K >> X;

	if (500 * K >= X)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}

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

int main() {
  int N,i,NUM;
  cin >> N;
  vector<int> DATA(N);
  vector<int> COPY(N);
  vector<int> MEMO(N);
  
  

  for (i=0; i<N; i++) {
    cin >> DATA.at(i);
    COPY.at(i) = DATA.at(i);
  }
  sort(DATA.begin(), DATA.end() );
  
  NUM = 0;
  for (i=0; i<N; i++) {
    if(DATA.at(i) == COPY.at(i)) {
      MEMO.at(i) = 0;
    }
    else {
      MEMO.at(i) = 1;
      NUM = NUM +1;
    }
  }
  if( NUM == 0) {
    cout << "YES" << endl;
  }
  else if( NUM == 2) {
    cout << "YES" << endl;
  }
  else { 
    cout << "NO" << endl;
  }
    
}

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

int calc(char c, stack<int> &s){
    int ans = 0;

    int a, b;
    b = s.top();
    s.pop();
    a = s.top();
    s.pop();
    //cout << a << b << endl;
    if(c == '+'){
        ans = a + b;
    }
    else if(c == '-'){
        ans = a - b;
    }
    else if(c == '*'){
        ans = a * b;
    }
    //cout << ans << endl;
    return  ans;
}

int sub(stack<int> &s){
    int a, b;

}

int main(){    
    stack<int> nums;
    while(true){
        string input;
        cin >> input;

        if(cin.eof()){
            break;
        }
        else if (input == "+" || input == "-" || input == "*")
        {
            nums.push(calc(input.at(0),nums));
        }
        else if (isdigit(input.at(0)) != 0)
        {
            //cout << "push num:" << input << endl;
            nums.push(stoi(input));            
        }        
    }

    cout << nums.top() << endl;
    return 0;
}


Measured memory_bytes: 3180
#include<stdio.h>
#define MAX 10000
#define NIL -1

typedef struct Node{int p,l,r;}Node;
struct Node T[MAX];
int n;

void preParse(int u){
  if(u==NIL) return;
  printf(" %d",u);
  preParse(T[u].l);
  preParse(T[u].r);
}

void inParse(int u){
  if(u==NIL) return;
  inParse(T[u].l);
  printf(" %d",u);
  inParse(T[u].r);
}

void postParse(int u){
  if(u==NIL) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d",u);
}

int main(){
  int i,v,l,r,root;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    T[i].p=NIL;
  }
  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l = l;
    T[v].r = r;
    if(l!=NIL) T[l].p = v;
    if(r!=NIL) T[r].p = v;
  }
  for(i=0;i<n;i++) if(T[i].p==NIL) root = i;

  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");

  return 0;
}




Measured memory_bytes: 2108
dice = list(map(int,input().split()))

def move(x):
    if x == "N":
        d[0],d[1],d[2],d[3],d[4],d[5] = d[1],d[5],d[2],d[3],d[0],d[4]

    elif x == "W":
        d[0],d[1],d[2],d[3],d[4],d[5] = d[2],d[1],d[5],d[0],d[4],d[3]

    elif x == "E":
        d[0],d[1],d[2],d[3],d[4],d[5] = d[3],d[1],d[0],d[5],d[4],d[2]

    elif x == "S":
        d[0],d[1],d[2],d[3],d[4],d[5] = d[4],d[0],d[2],d[3],d[5],d[1]

q = int(input())

for i in range(q):
    a,b = map(int,input().split())
    d = dice

    if a == dice[1]:
        move("N")
    if a == dice[2]:
        move("W")
    if a == dice[3]:
        move("E")
    if a == dice[4]:
        move("N")
    if a == dice[5]:
        move("S")
        move("S")

    if b == d[1]:
        print(d[2])
    if b ==  d[2]:
        print(d[4])
    if b ==  d[3]:
        print(d[1])
    if b ==  d[4]:
        print(d[3])


Measured memory_bytes: 5616
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}


int main() {
    string t;
    cin >> t;
    int y = 0;
    ll ans = 0;
    for (int i = 0; i < t.size(); i++) {
        if (t.at(i) == '?') {
            t.at(i) = 'D';
        }
    }
    cout << t << endl;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
using i64 = long long;

std::vector<std::deque<int>> go, ge;
std::vector<int> r;

void dfs(int v, int p) {
    for (int c : ge[v]) {
        if (c == p) continue;
        r[c] = r[v];
        dfs(c, v);
    }
    for (int c : go[v]) {
        if (c == p) continue;
        r[c] = !r[v];
        dfs(c, v);
    }
}

int main() {
    int n;
    std::cin >> n;
    go.resize(n); ge.resize(n); r.resize(n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        --u; --v;
        if (w % 2) {
            go[u].push_back(v);
            go[v].push_back(u);
        } else {
            ge[u].push_back(v);
            ge[v].push_back(u);
        }
    }

    r[0] = 0;
    dfs(0, -1);
    for (int i = 0; i < n; i++) std::cout << r[i] << std::endl;

    return 0;
}


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

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

print(len(Base_10_to_n(a[0], a[1])))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
#include <ctime>
#include <atcoder/all>
using namespace std;
#define _LL long long
#define rep(i, n) for (_LL i = 0; i < (_LL)(n); i++)
#define vecrep(itr, v) for (auto itr = (v).begin(); itr != (v).end(); itr++)
using namespace atcoder;

int main()
{
    int n, d; cin >> n >> d;
    vector<pair<int, int>> p(n);
    rep(i, n) cin >> p[i].first >> p[i].second; 
    two_sat ts(n);
    rep(i, n - 1)
        for(int j = i + 1; j < n; j++ )
        {
            if( abs(p[i].first - p[j].first) < d ) ts.add_clause(i, false, j, false);
            if( abs(p[i].first - p[j].second) < d ) ts.add_clause(i, false, j, true);
            if( abs(p[i].second - p[j].first) < d ) ts.add_clause(i, true, j, false);
            if( abs(p[i].second - p[j].second) < d ) ts.add_clause(i, true, j, true);
        }

    if( ts.satisfiable() )
    {
        cout << "Yes" << endl;
        auto ans = ts.answer();
        rep(i, n) cout << (ans[i] ? p[i].first : p[i].second) << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;    
}

Measured memory_bytes: 3740
#include<stdio.h>
int n,A[50];
int solve(int i,int m){
	if(m==0) return 1;
	if(i>=n) return 0;
	int res = solve(i+1,m) || solve(i+1,m-A[i]);
	return res;
}

int main(){
	int q,M,i;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&A[i]);
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&M);
		if(solve(0,M)) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

Measured memory_bytes: 2680
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
const int maxn = 1e5 + 5;
const int inf = 1000000000;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338; // double PI = 4*atan(1);



int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fastio
	//ifstream cin (".in");
	//ofstream cout (".out");
    int A, B, C;
	cin >> A >> B >> C;
	int it = 0;
	while (A%2==0 && B%2==0 && C%2==0) {
		int a = A/2, b = B/2, c = C/2;
		A = b+c;
		B = a+c;
		C = a+b;
		++it;
		if (it > 1000000) {
			cout << -1 << endl;
			return 0;
		}
	}
	cout << it << endl;
}





Measured memory_bytes: 3604
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl;
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2

int n, m;
vector<int>e[101010];
vector<int>er[101010];
set<int>aba[101010];
int dist[101010];
queue<int>q;
void dfs(int st,int curdist,int cur){
	if (aba[cur].count(curdist))return;
	else aba[cur].insert(curdist);
	if (curdist == 3) {
		if (dist[cur] == -1) {
			dist[cur] = dist[st] + 3;
			q.push(cur);
			return;
		}
		else {
			return;
		}
	}
	fore(x, er[cur])dfs(st, curdist + 1,x);
}

void bfs(int t) {
	dist[t] = 0;
	q.push(t);
	while (q.size()) {
		int tp = q.front();
		q.pop();
		dfs(tp,0,tp);
	}
}

int main() {
	memset(dist, -1, sizeof(dist));
	cin >> n >> m;
	rep(i, 0, m) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		e[u].pb(v);
		er[v].pb(u);
	}
	int s, t;
	cin >> s >> t;
	s--, t--;
	bfs(t);

	if (dist[s] != -1) {
		puts(dist[s] / 3);
	}
	else {
		puts(-1);
	}

	return 0;
}


Measured memory_bytes: 35072
#include <iostream>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;

struct CombInv{
                const long long MOD = 1e9+7;

                //nPrを返す
                long long Permutation(long long n, long long r){
                        long long tmp = 1;
                        long long i = n;
                        while(i!=n-r){
                                tmp *= i;
                                tmp %= MOD;
                                --i;
                        }
                        return tmp;
                }

                //x!を返す
                long long Factorial(long long x){
                        long long tmp = 1;
                        long long i = 1;
                        while(i<=x){
                                tmp *= i;
                                tmp %= MOD;
                                ++i;
                        }
                        return tmp;
                }

                //x^pを返す
                long long FastPow(long long x, long long p){
                        if(p==1) return x;
                        if(p%2==0){
                                long long sr = FastPow(x, p/2);
                                return (sr*sr)%MOD;
                        }else{
                                long long sr = FastPow(x, (p-1)/2);
                                return ((x*sr)%MOD*sr)%MOD;
                        }
                }

                //chi/parをMODで割った余りを返す
                long long FractionalRemainder(long long par, long long chi=1){
                        return (chi%MOD*FastPow(par, MOD-2))%MOD;
                }

                //nCrを返す
                long long Combination(long long n, long long r){
                        return (Permutation(n,r)*(FractionalRemainder(Factorial(r))))%MOD;
                }
        };

int main(){
        ll n,a,b,ans;
        cin >> n >> a >> b;
        CombInv ci;
        ans = ci.FastPow(2, n) - 1;
        ans -= ci.Combination(n,a);
        if(ans<0) ans += MOD;
        ans -= ci.Combination(n,b);
        if(ans<0) cout << ans+MOD << endl;
        else cout << ans << endl;
        return 0;
}

Measured memory_bytes: 3676