akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/segtree>
// using namespace atcoder;

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> llVEC;
typedef vector<P> PVEC;
typedef priority_queue<P,PVEC,greater<P> > PPQ;
typedef priority_queue<ll, llVEC, greater<ll> > llPQ;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> &vec){ return (ll)vec.size(); }
template<typename T>
ll sz(priority_queue<T, vector<T>> &pq) {return (ll)pq.size(); }
template<typename T>
ll sz(priority_queue<T, vector<T>, greater<T>> &pq) {return (ll)pq.size(); }
ll sz(string &s) {return (ll)s.size(); } 
ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b; }
bool checkindex(ll i,ll n){ return (i < n && i >= 0); }

int main(){
    string s;
    cin >> s;
    if(s[sz(s)-1] != 's') cout << s << "s" << endl;
    else cout << s << "es" << endl; 
    return 0;
}



Measured memory_bytes: 3624
n = int(input())

mod = 10 ** 9 + 7


def modpow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


ans = modpow(10, n) - 2 * modpow(9, n) + modpow(8, n)

print(ans % mod)


Measured memory_bytes: 9064
#include <bits/stdc++.h>
using namespace std;
inline bool chmin (int& a, int b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
int main() {
  int n;
  string s;
  cin >> n >> s;
  s.insert(s.begin(), '$');
  vector<int> a(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    a[i] = a[i - 1];
    if (s[i] == '#') a[i]++;
  }
  int ret = 1e9;
  for (int i = 0; i <= n; i++) {
    chmin(ret, a[i - 1] + (n - i) - (a[n] - a[i]));
  }
  cout << ret << endl;
  return 0;
}

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

using namespace std;

const int N = 3e6;

string s, t;
int z[N];
int n, k, sz;

int ans[N];
bool used[N];
int rec(int p){
    if(ans[p])
        return ans[p];
    if(z[n+p+1] != n)
        return 0;
    if(used[p]){
        cout << "-1\n";
        exit(0);
    }
    used[p] = true;
    ans[p] = rec((p+n)%sz)+1;
    used[p] = false;
    return ans[p];
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> s >> t;
    string new_s;
    new_s = s+s;
    while(new_s.size() < 2*t.size())
        new_s += s;
    n = t.size();
    sz = s.size();
    k = new_s.size();
    t = t + "#" + new_s;
    int l = 0,
        r = 0;
    for(int i = 1; i < n+k+1; ++i){
        if(i <= r)
            z[i] = min(r-i+1, z[i-l]);
        while(i+z[i] < n+k+1 && t[z[i]] == t[i+z[i]])
            ++z[i];
        if(i+z[i]-1 > r)
            l = i, r = i+z[i]-1;
    }
    for(int i = 0; i < sz; ++i)
        rec(i);
    cout << *max_element(ans, ans+sz) << '\n';
}


Measured memory_bytes: 21168
#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
using namespace std;
typedef long long int llint;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b) {
		cout << c << endl;
	}
	if (b == c) {
		cout << a << endl;
	}
	if (a == c) {
		cout << b << endl;
	}
	return 0;
}

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

map<string, int> memo;

int main(){
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    string s;
    cin >> s;
    memo[s]+=1;
  }
  int maxv = 0;
  for(const auto & x: memo){
    int v = x.second;
    if(v > maxv)maxv = v;
  }
  for(auto it = memo.begin(); it != memo.end(); it++){
    if(it -> second == maxv){
      cout << it -> first << endl;
    }
  }
  return 0;
}
// 連想配列を使う map

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

#define fi first
#define se second
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int(v.size())
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep2(i, n, m) for (ll i = n; i <= (m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (m); --i)

template<class T, class U> void chmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> void chmin(T &a, U b) { if (b < a) a = b; }

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

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

  int x, a; cin >> x >> a;

  if (x < a) cout << 0 << endl;
  else cout << 10 << endl;
  
  return (0);
}

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

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

  int n, m;
  cin >> n >> m;
  vector<vector<P>> ken(100100);
  rep(i, m) {
    int p, y;
    cin >> p >> y;
    ken[p].push_back(make_pair(i, y));
  }

  P answers[100100];
  for( auto &l : ken) {
    sort(l.begin(), l.end(), [](P a, P b){return a.second < b.second;});
  }

  rep(i, 100010) {
    int cnt = 1;
    for (auto a : ken[i]) {
      answers[a.first] = make_pair(i, cnt);
      cnt++;
    }
  }

  for(auto i : answers) {
    if (i.first == 0 && i.second == 0) continue;
    cout << setfill('0') << right << setw(6) << i.first;
    cout << setfill('0') << right << setw(6) << i.second;
    cout << endl;
  }
}

Measured memory_bytes: 7808
import math
from collections import defaultdict
import itertools
N = int(input())
town = [[int(i) for i in input().split(' ')] for _ in range(N)]

dist = 0
c = 0
for v in itertools.permutations(town,len(town)):
    c += 1
    sx = v[0][0]
    sy = v[0][1]
    for i in v[1::]:
        dist += math.sqrt((sx - i[0]) ** 2 + (sy - i[1]) ** 2)
        sx, sy = i[0], i[1]

print(dist/c)

Measured memory_bytes: 3444
#include<iostream>
using namespace std;
static const int N = 100;

int main(){
  int M[N][N];
  int n,u,k,v;

  cin >> n;

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      M[i][j] = 0;
    }
  }

  for(int i=0;i<n;i++){
    cin >> u >> k;
    u--;
    for(int j=0;j<k;j++){
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(j) cout << " ";
      cout << M[i][j];
    }
    cout << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;

    cin >> N;

    int h[N];

    for(int i = 0; i < N; ++i){
        cin >> h[i];
    }

    int c[N];

    c[0] = abs(h[0] - h[1]);
    int c1 = c[0] + abs(h[1] - h[2]);
    int c2 = abs(h[0] - h[2]);
    if(c1 < c2) c[1] = c1;
    else c[1] = c2;

    for(int i = 2; i < N-1; ++i){
        c1 = c[i-1] + abs(h[i] - h[i+1]);
        c2 = c[i-2] + abs(h[i-1] - h[i+1]);
        if(c1 < c2) c[i] = c1;
        else c[i] = c2;
    }

    cout << c[N-2];
}

Measured memory_bytes: 1024
#![allow(unused_macros)]

// cf. [Rustで競技プログラミングの入力をスッキリ記述するマクロ - Qiita](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 main() {
    input! {
        S: String,
    }
    let S: String = S.chars().rev().collect();
    let sc: Vec<char> = S.chars().collect();
    let mut l = 0;

    while l < sc.len() {
        let substr= sc.get(l..).unwrap();
        if substr.starts_with(&['m', 'a', 'e', 'r', 'd']) {
            l += 5;
            continue;
        } else if substr.starts_with(&['r', 'e', 'm', 'a', 'e', 'r', 'd']) {
            l += 7;
            continue;
        } else if substr.starts_with(&['e', 's', 'a', 'r', 'e']) {
            l += 5;
            continue;
        } else if substr.starts_with(&['r', 'e', 's', 'a', 'r', 'e']) {
            l += 6;
            continue;
        }

        println!("NO");
        return;
    }

    println!("YES");
}


Measured memory_bytes: 4352
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

int main() {
  int N;
  cin>>N;
  vector<int64_t> A(N);
  int64_t sum=0;
  int sign=0;
  int64_t absMin=1e9+1;
  for(int i=0;i<N;i++){
    cin>>A[i];
    sum += abs(A[i]);
    if(A[i]<0) sign++;
    absMin = min(absMin,abs(A[i]));
  }
  if(sign%2==0){
    cout<<sum<<endl;
  }else{
    cout<<sum-2*absMin<<endl;
  }
  return 0;
}


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

int main(int argc, char *argv[])
{
    map<int, int> counts;
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        counts[x]++;
    }

    bool valid = true;
    int m;
    cin >> m;
    for(int i = 0; i < m; ++i)
    {
        int x;
        cin >> x;
        if(counts[x] == 0) { valid = false; break; }
        counts[x]--;
    }
    
    cout << (valid ? "YES" : "NO") << endl;
}


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

int main(){
  int H, W, K;
  cin >> H >> W >> K;
  long long md=1e9+7;
  vector<long long> fib(9, 1);
  for (int i=2; i<9; i++) fib[i] = fib[i-1] + fib[i-2];
  vector<long long> ans(W+2,0);
  ans[1] = 1;
  for (int i=1; i<=H; i++){
    vector<long long> nxt(W+2,0);
    for (int j=1; j<=W; j++){
      if (j>1) {
        nxt[j] += ans[j-1]*fib[j-2]*fib[W-j];
        nxt[j] %= md;
      }
      nxt[j] += ans[j]*fib[j-1]*fib[W-j];
      nxt[j] %= md;
      if (j<W){
        nxt[j] += ans[j+1]*fib[j-1]*fib[W-j-1];
        nxt[j] %= md;
      }
    }
    ans = nxt;
  }
  cout << ans[K] << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<stdint.h>
#include<limits.h>
#include<sstream>
#include<iomanip>
#include<cmath>
using namespace std;


int main() {
	int n;
	cin >> n;
	cout << n * n*n;
	

	return 0;
}

Measured memory_bytes: 256
fn main(){
    let mut buf: String = String::new();
    std::io::stdin().read_line(&mut buf).expect("failed to read");
    let s = buf.trim().to_string();

    buf.clear();
    std::io::stdin().read_line(&mut buf).expect("failed to read");
    let t = buf.trim().to_string();

    let ans: u32 = s.chars().zip(t.chars()).map(|(x, y)| if x == y { 0 } else { 1 }).sum();

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


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

int main() {
    li a;
    cin >> a;
    cout << (a - 1) / 2 << endl;

    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(m)]
count=[1]*(n+1)
s=set()
s.add(1)
for a,b in arr:
  count[b]+=1
  count[a]-=1
  if a in s:
    s.add(b)
  if count[a]==0:
    s.discard(a)
print(len(s))

Measured memory_bytes: 34332
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int n,r;
    cin>>n>>r;
    if(n>=10) cout<<r;
    else cout<<r+100*(10-n);
}

Measured memory_bytes: 3576
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <functional>
#include <numeric>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
    long long N;
    string s;
    cin >> N;
    s = to_string(N);
    long long ans = 0LL;
    long long slen = s.length();
    for (int i = 0; i < slen; i++)
    {
        ans += s[i] - '0';
    }
    ans = max(ans, 9LL * (slen - 1LL));
    long long n = N;
    long long tans = 0LL;
    string ss = to_string(n);
    for (long long i = 0; i < ss.length(); i++)
    {
        int sslen = ss.length() - 1;
        if (ss[sslen - i] == '9' || sslen - i == 0)
        {
        }
        else
        {
            n -= (ss[sslen - i] - '0' + 1LL) * pow(10LL, i);
            ss = to_string(n);
            sslen = ss.length() - 1;
            //cout << ss << endl;
        }
        tans += ss[sslen - i] - '0';
    }
    ans = max(ans, tans);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 888
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] s = Console.ReadLine().Split(' ');
            int[] Xs = new int[N];
            for (int i = 0; i < N; i++)
            {
                Xs[i] = int.Parse(s[i]);
            }

            Array.Sort(Xs);
            for (int i = 0; i < N; i++)
            {
                if (int.Parse(s[i]) <= Xs[N/2-1])
                {
                    Console.WriteLine(Xs[N / 2]);
                }
                else
                {
                    Console.WriteLine(Xs[(N / 2) -1 ]);
                }
                
            }
            Console.ReadLine();

        }





    }
}


Measured memory_bytes: 36264
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
          if(n/i==i)
            c++;
          else
            c+=2;
        }

    }

    
    return  c;
}
int func(int n)
{
    return (n*(n+1))/2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   
    int n,l,k;
    cin>>n>>l>>k;
    long long int sum=0;
    sum=k;
    while(n--)
    {
         int h;
         cin>>h;
         sum=sum+(l-1+h)/h;
    }
    cout<<sum;


 return 0;
}








Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

int main(){
  int n,k;cin>>n>>k;
  int sum=0;
  int a[n];
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  vector<int> p;
  for(int i=1;i*i<=sum;++i){
    if(sum%i==0){
      p.push_back(i);
      if(i*i!=sum)p.push_back(sum/i);
    }
  }
  sort(all(p));
  reverse(all(p));
  rep(i,p.size()){
    int b[n];rep(j,n)b[j]=a[j]%p[i];
    sort(b,b+n);
    ll sum[n+1];sum[0]=0;
    rep(j,n)sum[j+1]=sum[j]+b[j];
    rep(j,n){
      if(max(sum[j+1]-sum[0],1ll*(n-j-1)*p[i]-(sum[n]-sum[j+1]))<=k){
        cout<<p[i]<<endl;exit(0);
      }
    }
  }
}
    
    


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define one 1.0
#define inf 1000000000000000000
#define ret return
#define all(vl) vl.begin(),vl.end()
#define sor sort 
#define cl clear
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;
ll n;
int main()
{
	cin>>n;
	vector<ll> a(n),b(n);
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	ll cnt = 0,cnt1 = 0;
	ll in = 0;
	ll ii = 1;
	vector<ll> vl;
	for(int i=0;i<n;i++)
	{
		vl.push_back(ii);
		ii++;
	}
	
	do
	{
		if(vl == a)
			cnt = in;
		if(vl == b)
			cnt1 = in;
		in++;
	}while(next_permutation(all(vl)));
	cout<<abs(cnt1-cnt)<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  
  public static void main (String[] args){
  
	Main main = new Main();
 	Scanner scanner = new Scanner (System.in);
    
  	int H = scanner.nextInt();
    int W = scanner.nextInt();
    
  	String[][] list = new String [H][W];
  
  	scanner.nextLine();
    
  	for (int i=0; i<H; i++){
  		String temp = scanner.nextLine();
    	for (int j=0; j<W; j++){
      		String[] templist = temp.split("");
      		list[i][j] = templist[j];
    	}
  	 }
    for (int i=0; i<H; i++){
      for (int j=0; j<W; j++){
    	  if (list[i][j].equals("#")) {
    	  } else {
    		  main.hantei(i,j,H,W,list);
    	  } 
        }
      }
    
    for(int i=0; i<H; i++) {
    	for (int j=0; j<W; j++) {
    		System.out.print(list[i][j]);
    	}
    	System.out.println();
    }
    }


  void hantei (int i, int j, int H, int W, String[][] list){
    boolean firstLine = false;
    boolean lastLine = false;
    boolean firstColumn = false;
    boolean lastColumn = false;
    int count=0;
    
    if (i==0){
      firstLine = true;
    }
    if (i==H-1){
      lastLine = true;
    }
    if (j==0){
      firstColumn = true;
    }
    if (j==W-1){
      lastColumn = true;
    }
    
    for (int k=0; k<8; k++) {
    	//左上、真上、右上、右横、右下、真下、左下、左横の順にチェックする
    	switch (k) {
    	case 0:
    		if (firstLine == true || firstColumn==true) {
    			break;
    		} 
    	    if (list[i-1][j-1].equals("#")) {
    	    	count++;
    	    }
    		break;
    	case 1:
    		if (firstLine == true) {
    			break;
    		}
    		if (list[i-1][j].equals("#")) {
    			count++;
    		}
    		break;
    	case 2:
    		if (firstLine==true || lastColumn==true) {
    			break;
    		}
    		if (list[i-1][j+1].equals("#")) {
    			count++;
    		}
    		break;
    	case 3:
    		if (lastColumn==true) {
    			break;
    		}
    		if(list[i][j+1].equals("#")) {
    			count++;
    		}
    		break;
    	case 4:
    		if (lastLine==true || lastColumn==true) {
    			break;
    		}
    		if (list[i+1][j+1].equals("#")) {
    			count++;
    		}
    		break;
    	case 5:
    		if (lastLine==true) {
    			break;
    		}
    		if (list[i+1][j].equals("#")) {
    			count++;
    		}
    		break;
    	case 6:
    		if (lastLine==true||firstColumn==true) {
    			break;
    		}
    		if(list[i+1][j-1].equals("#")) {
    			count++;
    		}
    		break;
    	case 7:
    		if(firstColumn==true) {
    			break;
    		}
    		if(list[i][j-1].equals("#")) {
    			count++;
    		}
    		break;
    	}
    	list[i][j]=String.valueOf(count);
    }
  }
}

Measured memory_bytes: 36948
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 200005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int n, m;
int x, y;
map<pair<int,int>, bool> mapa;
vector<int> a;
int main()
{
    cin >> n >> m;
    while(m--)
    {
        cin >> x >> y;
        mapa[make_pair(x, y)] = 1;
        if(y == n)
        {
            a.push_back(x);
        }
    }
    bool f = false;
    bool flag = a.size();
    if(flag)
    {
        for(int i = 0; i < a.size(); ++i)
        {
            if(mapa[make_pair(1, a[i])])
            {
                f = true;
                break;
            }
        }
    }
    if(f)
        puts("POSSIBLE");
    else
        puts("IMPOSSIBLE");
    return 0;
}


Measured memory_bytes: 19320
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,l,j=0;
    cin >> n;
    if(n<=81)
    {
        for(i=1;i<=9;i++)
        {
            if(n%i==0 && n/i<=9)
            {
                j++;
            }
        }
    }
    if(j==0)
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" <<endl;
    }

    return 0;
}


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

using namespace std;

#define rep(i, n) for(long int i = 0; i < n; i++)

int main(){
    long int n;
    cin >> n;
    long int a[n];
    long int x[400001], y[400001];
    // fill(x, x + 400001, 0);
    fill(y, y + 400001, 0);
    rep(i, n) cin >> a[i];
    rep(i, n){
        // if((i + 1) + a[i] <= 200000){
        //     long int idx = (i + 1) + a[i] + 200000;
        //     x[idx]++;
        // }
        if(0 <= (i + 1) - a[i] && (i + 1) - a[i] <= 200000){
            long int idx = (i + 1) - a[i] + 200000;
            y[idx]++;
        }
    }
    long int ans = 0;
    rep(i, n){
        if((i + 1) + a[i] <= 200000){
            long int idx = (i + 1) + a[i] + 200000;
            ans += y[idx];
        }
        if(0 <= (i + 1) - a[i] && (i + 1) - a[i] <= 200000){
            long int idx = (i + 1) - a[i] + 200000;
            y[idx]--;
        }
    }
    cout << ans << endl;
}


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

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct edge{
    ll to, cost;
};


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

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 素数
vector<bool> IsPrime;
void sieve(size_t max){
    if(max+1 > IsPrime.size()){
        IsPrime.resize(max+1,true);
    } 
    IsPrime[0] = false;
    IsPrime[1] = false;

    for(size_t i=2; i*i<=max; ++i){
        if(IsPrime[i]){
            for(size_t j=2; i*j<=max; ++j){
                IsPrime[i*j] = false;
            }
        }
    }
}

// べき乗の余り
ll modpow(ll a, ll n){
    ll res = 1;
    while(n){
        if(n & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        n = n >> 1;
    }
    return res;
}

// コンビネーション
ll MAXN = 2e5+10;
vector<ll> inv(MAXN);
ll nCk(ll n, ll k) {
	ll res = 1;
	for(ll i = 1; i <= k; i++) {
		res = res*(n-i+1) % MOD;
	}
 
	for(ll i = 1; i <= k; i++) {
		res = res*inv[i] % MOD;
	}
	return res;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

int main(){
    ll n, p;
    cin>>n>>p;

    if(n == 1){
        cout<<p<<endl;
        return 0;
    }
    for(ll i=sqrt(p);i>=2;--i){
        ll q = p;
        ll count = 0;
        while(q % i == 0){
            count++;
            q /= i;
            if(count == n){
                cout<<i<<endl;
                return 0;
            }
        }
    }
    cout<<1<<endl;

    return 0;
}

Measured memory_bytes: 4676
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  string s; cin >> s; ll n = s.size(); ll ans = 0;
  vl sum(n+1);
  
  rep(i,n){
    ll a = 0;
    if(s[i] == 'B') a++;
    sum[i+1] = sum[i] + a;
  }
  
  rep(i,n){
    if(s[i] == 'W') ans += sum[i];
  }
  
  cout << ans << endl;
  
  
}

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

int KiriageTime(int x) {
  return (x+9) /10 *10;
}

int sabun(int x) {
  return KiriageTime(x) -x;
}

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

  int KiriageTotal = KiriageTime(A) + KiriageTime(B) + KiriageTime(C) + KiriageTime(D) + KiriageTime(E);
  cout << KiriageTotal - max( {sabun(A), sabun(B), sabun(C), sabun(D), sabun(E)} ) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef long long ll;
const int maxn = 305;
const int mod = 1000000007;

pair<ll,int> get(int x, ll y){
  if(y==1)return make_pair(0L, x);
  if(x+x<=9){
    auto tt = get(x+x, y>>1L);
    tt.first += (y>>1);
    if(y&1){
      tt.second += x;
      tt.first++;
      if(tt.second>=10){
        tt.first++;
        tt.second = tt.second%10+tt.second/10;
      }
    }
    return tt;
  }
  int tmp = x + x;
  int tmp2 = tmp%10+tmp/10;
  auto tt = get(tmp2, y>>1L);
  tt.first += 2*(y>>1L);
  if(y&1){
    tt.second += x;
    tt.first++;
    if(tt.second>=10){
      tt.first++;
      tt.second = tt.second%10+tt.second/10;
    }
  }
  return tt;
}

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  int n;
  cin>>n;
  int cur = 0;
  ll ret = 0;
  for(int i=0;i<n;i++){
    int x;
    ll y;
    cin>>x>>y;
    auto tt = get(x,y);
    ret+=tt.first;
    cur += tt.second;
    if(cur>=10){
      ret++;
      cur = cur%10+cur/10;
    }
    if(i)ret++;
  }
  cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,n;
	cin>>n;
	ll ar[n+1];
	for(i=1;i<=n;i++){
		cin>>ar[i];
	}
		
	ll flg=1,pt[n+1]={0};
	for(i=n;i>=1;i--){
		ll c=0;
		for(j=i;j<=n;j+=i){
			c+=pt[j];
		}
		if(c%2==0){
			if(ar[i]==0) pt[i]=0;
			else pt[i]=1;
		}
		else{
			if(ar[i]==0) pt[i]=1;
			else pt[i]=0;
		}
	}

	vector<ll> vc;
	for(i=1;i<=n;i++){
		if(pt[i]){
			vc.ps(i);
		}
	}
	cout<<vc.size()<<endl;
	for(auto it:vc){
		cout<<it<<" ";
	}
	return 0;
}

Measured memory_bytes: 5108
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    long double n,k,ans=0,count;
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        count=1;
        for(int s=i;s<k;s*=2)
        {
            count*=0.5;
        }
        ans+=(1/n)*count;
    }
    cout << std::setprecision(11) << ans << '\n';
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	static Node[] list;
    public static void main(String[] args){
    	Scanner sc=new Scanner(System.in);
    	int n=sc.nextInt();
    	list =new Node[n];
    	
    	int num,ri,le;
    	for(int i=0;i<n;i++){
    		list[i]=new Node();
    	}
    	for(int i=0;i<n;i++){
    		num=sc.nextInt();
    		list[num].number=num;
    		le=sc.nextInt();
    		ri=sc.nextInt();
    		if(ri==-1){
    			list[num].right=null;
    		}else{
    			list[num].right=list[ri];
    			list[ri].pid=num;
    		}
    		if(le==-1){
    			list[num].left=null;
    		}else{
    			list[num].left=list[le];
    			list[le].pid=num;
    		}
    		
    	}
    	System.out.println("Preorder");
    	for(int i=0;i<n;i++){
    		if(list[i].pid==-1){
    			preorder(list[i]);
    		}
    	}
    	System.out.print("\n");
    	System.out.println("Inorder");
    	for(int i=0;i<n;i++){
    		if(list[i].pid==-1){
    			inorder(list[i]);
    		}
    	}
    	System.out.print("\n");
    	System.out.println("Postorder");
    	for(int i=0;i<n;i++){
    		if(list[i].pid==-1){
    			postorder(list[i]);
    		}
    	}
        System.out.println();
}
    static void preorder(Node node){
    	System.out.print(" ");
    	System.out.print(node.number);
    	if(node.left!=null){
    		preorder(node.left);
    	}
    	if(node.right!=null){
    		preorder(node.right);
    	}
    }
    static void inorder(Node node){
    	if(node.left!=null){
    		inorder(node.left);
    	}
    	System.out.print(" ");
    	System.out.print(node.number);
    	if(node.right!=null){
    		inorder(node.right);
        }
    }
    static void postorder(Node node){
    	if(node.left!=null){
    		postorder(node.left);
    	}
    	if(node.right!=null){
    		postorder(node.right);
        }
    	System.out.print(" ");
    	System.out.print(node.number);
    }	
}
class Node{
	int number;
	int pid;
	Node left;
	Node right;
	Node(){
		pid=-1;
		number=0;
		left=null;
		right=null;
	}
}



Measured memory_bytes: 26396
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int A, B;
  cin >> A >> B;

  cout << A * B << endl;
  
  return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
vector<int>Q;
vector<int>::iterator iter;
int main() {
	int N;
	ios::sync_with_stdio(false);
	cin>>N;
	for(int j=1;(j-2)*(j-2)<=N;j++)
		Q.push_back(j*j);
	iter=upper_bound(Q.begin(),Q.end(),N);
	iter--;
	cout<<*iter;
	return 0;
}


Measured memory_bytes: 512
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        F=[]
        for i in range(n):
            F.append([int(x) for x in raw_input().split()])
        F.append([0 for x in range(n+1)])
        for i in range(n):
            F[i]=F[i]+[sum(F[i])]
        for j in range(n+1):
            s=0
            for i in range(n):
                s=s+F[i][j]
            F[n][j]=s
        G=[[' '*(5-len(str(x)))+str(x) for x in y] for y in F]
        for i in range(n+1):
            print ''.join(G[i])
            

Measured memory_bytes: 4256
#include<bits/stdc++.h>
using namespace std;
int main()
{

    int n;
    cin>>n;
    if(n%10==2 or n%10==4 or n%10==5 or n%10==7 or n%10==9)
    {
        cout<<"hon"<<endl;
    }
    else if(n%10==0  or n%10==1 or n%10==6 or n%10==8)
    {
        cout<<"pon"<<endl;
    }
        else if(n%10==3)
    {
        cout<<"bon"<<endl;
    }



    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

int H,W;
vector<string> S;

int dp[101][101][2];
const int INF=1e9;

int dx[]={0,1};
int dy[]={1,0};

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

  cin>>H>>W;
  S.resize(H);
  rep(i,H) cin>>S[i];

  rep(i,H) rep(j,W) rep(k,2)dp[i][j][k]=INF;
  if(S[0][0]=='.'){
      dp[0][0][0]=0;
      dp[0][0][1]=0;
  }else{
      dp[0][0][0]=1;
      dp[0][0][1]=1;
  }

  priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>> PQ;
  PQ.push(mkt(dp[0][0][0],0,0,0));
  PQ.push(mkt(dp[0][0][1],0,0,1));
  while(!PQ.empty()){
      auto f=PQ.top();
      PQ.pop();
      int c=get<0>(f);
      int x=get<1>(f);
      int y=get<2>(f);
      int d=get<3>(f);
      
      for(int k=0;k<2;k++){
          int nx=x+dx[k];
          int ny=y+dy[k];
          if(nx<0||ny<0||nx>=H||ny>=W) continue;
          int neco=0;
          if(S[x][y]=='#'){
              //if(S[nx][ny]=='.'&&k!=d) neco=1;
          }else{
              if(S[nx][ny]=='#') neco=1;
          }
          if(dp[nx][ny][k]>c+neco){
              dp[nx][ny][k]=c+neco;
              PQ.push(mkt(dp[nx][ny][k],nx,ny,k));
          }
      }
      if(S[x][y]=='.'&&dp[x][y][1-d]>dp[x][y][d]){
          dp[x][y][1-d]=dp[x][y][d];
          PQ.push(mkt(dp[x][y][1-d],x,y,1-d));
      }
  }

  int ans=min(dp[H-1][W-1][0],dp[H-1][W-1][1]);
  cout<<ans<<endl;

  return 0;
}


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

#include <atcoder/all>

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

using namespace std;
using namespace atcoder;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  dsu ds(n);
  while (m--) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    ds.merge(a, b);
  }
  auto g = ds.groups();
  cout << (int)g.size() - 1 << '\n';
  return 0;
}

Measured memory_bytes: 8976
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
last_num = -1
manzoku_sum = 0
for i in A:
    manzoku_sum += B[i - 1]
    if last_num + 1 == i:
        manzoku_sum += C[last_num - 1]
    last_num = i
print(manzoku_sum)


Measured memory_bytes: 3060
#include<stdio.h>

int main() {
 long A,B,N=0;
   scanf("%ld",&A);
   scanf("%ld",&B);
  
  for(int i=0;i<80000;i++){
    double j=i*0.08, k=i*0.1;
    int a=j,b=k;
  	if((a==A) && (b==B)){
      N=i;
      break;
    }
  }
  
  if(N>0){
  	printf("%ld",N);
  }else if(N==0){
    printf("-1");
  }
  
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#define MAX 25
struct Node{
  int parent;
  int left;
  int right;
};

struct Node T[MAX];
int D[MAX], H[MAX];

void calDepth(int i, int d) {
  if (i == -1) return;
  D[i] = d;
  calDepth(T[i].left, d+1);
  calDepth(T[i].right, d+1);
}

int calHeight(int i) {
  int h1 = 0, h2 = 0;
  if (T[i].left != -1) {
    h1 = calHeight(T[i].left) + 1;
  }
  if (T[i].right != -1) {
    h2 = calHeight(T[i].right) + 1;
  }

  if (h1 >= h2) {
    return H[i] = h1;
  } else {
    return H[i] = h2;
  }
}

int pickSibling(int i) {
  if (T[i].parent == -1) return -1;
  if (T[T[i].parent].left != i && T[T[i].parent].left != -1) {
    return T[T[i].parent].left;
  }
  if (T[T[i].parent].right != i && T[T[i].parent].right != -1) {
    return T[T[i].parent].right;
  }
  return -1;
}

void print(int i) {
  printf("node %d: ", i);
  printf("parent = %d, ", T[i].parent);
  printf("sibling = %d, ", pickSibling(i));

  int c;
  c = 0;
  if (T[i].left != -1) c++;
  if (T[i].right != -1) c++;
  printf("degree = %d, ", c);

  printf("depth = %d, ", D[i]);
  printf("height = %d, ", H[i]);

  if (T[i].parent == -1) {
    printf("root");
    printf("\n");
  } else if (T[i].left == -1 && T[i].right == -1) {
    printf("leaf");
    printf("\n");
  } else {
    printf("internal node");
    printf("\n");
  }
}

int main(void) {
  int n;
  scanf("%d", &n);
  int i;
  for (i = 0; i < MAX; i++) {
    T[i].parent = -1;
    T[i].left = -1;
    T[i].right = -1;
  }

  for (i = 0; i < n; i++) {
    int id;
    int l, r;
    scanf("%d %d %d", &id, &l, &r);
    T[id].left = l;
    T[id].right = r;
    if (l != -1) T[l].parent = id;
    if (r != -1) T[r].parent = id;
  }

  int r;
  for (i = 0; i < n; i++) {
    if (T[i].parent == -1) r = i;
  }

  calDepth(r, 0);
  calHeight(r);

  for (i = 0; i < n; i++) {
    print(i);
  }

  return 0;
}



Measured memory_bytes: 2052
# 提出一覧から持ってきた解答
# わかりやすいように各所分解してます

from collections import Counter

N = int(input())

s = []
for _ in range(N):
    # 入力値をソートしてリストにする
    s_input = sorted(input())
    # ソート済みのリストを文字列に変換する
    s2_input = ''.join(s_input)
    # ソート済み文字列用の配列に突っ込む
    s.append(s2_input)

cnt = Counter(s)

full_cnt = 0
for c in cnt.values():
    if c >= 2:
        # 1からnまでの和 -> {(n+1)*n}//2
        # 同じ文字列がa個存在した場合、その組み合わせは重複を排除して{1からa-1までの和}通りある。
        full_cnt += c * (c - 1) // 2


print(full_cnt)

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

int main(){
    
    int k,x;
    cin >> k >> x;

    rep(i,-k+1,k){
        cout << i+x << " ";
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int h,w;
  cin>>h>>w;
  int i,j;
  string s[h];
  for(i=0;i<h;i++)
  {
   cin>>s[i];
  }
  int row[h][w], col[h][w];
  for(i=0;i<h;i++)
  {
      for(j=0;j<w;j++)
      {
          row[i][j]=0;
          col[i][j]=0;
      }
  }
  int ans=0;
  for(i=0;i<h;i++)
  {
    for(j=0;j<w;j++)
    {
      if(s[i][j]=='.')
      {
        int r=i+1,c=j+1,cr=0,cc=0;
        if(i>0 && s[i-1][j]=='.') {cr = row[i-1][j];row[i][j] = row[i-1][j];}
        else {
        while(r<h && s[r][j]!='#') {cr++;r++;}
        row[i][j]=cr;
        }
        if(j>0 && s[i][j-1]=='.') {cc = col[i][j-1];col[i][j]=col[i][j-1];}
        else{
        while(c<w && s[i][c]!='#') {cc++;c++;}
        col[i][j]=cc;
        }
        if(ans<cr+cc+1) ans=cr+cc+1;
      }
    }
  }
  cout<<ans;
  return 0;
}

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

constexpr int INF = 1 << 29;

int H, W;
string dat[50];

struct rect_dat {
    int lh, rh, lw, rw;
    rect_dat(): lh(INF), rh(-INF), lw(INF), rw(-INF) {}
};

int main() {
    int N; cin >> N;
    for (int _ = 0; _ < N; ++_) {
        cin >> H >> W;
        for (int j = 0; j < H; ++j) { cin >> dat[j]; }
        
        rect_dat rect[26];
        int is_back[26][26];
        for (int j = 0; j < 26; ++j) {
            fill(is_back[j], is_back[j]+26, -1);
            is_back[j][j] = 0;
        }

        for (int j = 0; j < H; ++j) {
            for (int k = 0; k < W; ++k) {
                if (dat[j][k] == '.') { continue; }
                int ind = dat[j][k] - 'A';

                rect[ind].lh = min(rect[ind].lh, j);
                rect[ind].rh = max(rect[ind].rh, j);

                rect[ind].lw = min(rect[ind].lw, k);
                rect[ind].rw = max(rect[ind].rw, k);
            }
        }

        const string SAFE = "SAFE", SUSPICIOUS = "SUSPICIOUS";
        const string msg = [&]() -> string { 
            for (int x = 0; x < 26; ++x) {
                char ch = x + 'A';
                for (int j = rect[x].lh; j <= rect[x].rh; ++j) {
                    for (int k = rect[x].lw; k <= rect[x].rw; ++k) {
                        if (dat[j][k] == '.') {
                            return SUSPICIOUS;
                        }
                        if (dat[j][k] == ch) { continue; }
                        int y = dat[j][k] - 'A';
                        if (is_back[x][y] < 0) {
                            is_back[x][y] = 1;
                            for (int j = 0; j < 26; ++j) {
                                if (y == j) { continue; }
                                if (is_back[y][j] == 1) {
                                    if (is_back[x][j] == 0) {
                                        return SUSPICIOUS;
                                    }
                                    is_back[x][j] = 1;
                                }
                            }
                            is_back[y][x] = 0;
                        } else if (is_back[x][y] == 0) {
                            return SUSPICIOUS;
                        }
                    }
                }
            }
            return "SAFE";
        }();

        cout << msg << endl;
    }
    return 0;
}

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

right_answers = list(int(input()) for _ in list(range(Q)))
indexes = [v-1 for v in right_answers]

scores = [K-Q for _ in range(N)]

for i in indexes:
    scores[i] = scores[i]+1

for j in scores:
    if j > 0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 58328
package main

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

func main() {
	var n int
	fmt.Scan(&n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	var ok bool
	var cnt int
	for i := 0; i < n; i++ {
		sc.Scan()
		d1, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		d2, _ := strconv.Atoi(sc.Text())
		if d1 == d2 {
			cnt++
			if cnt >= 3 {
				ok = true
			}
		} else {
			cnt = 0
		}
	}
	if ok {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


Measured memory_bytes: 1840
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from itertools import accumulate

def ok(x,A,Acum):
    size = Acum[x]
    for creature in A[x + 1:]:
        if creature  <= 2*size:
            size += creature
    if size == Acum[-1]:
        return True
    return False

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    Acum = list(accumulate(A))
    
    l = -1
    r = N
    while r - l > 1:
        mid = (r + l)//2
        if ok(mid,A,Acum):
            r = mid
        else:
            l = mid
    print(N - r)  
if __name__ == '__main__':
    main()

Measured memory_bytes: 14432
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)
#define RREP(i, n) for(int i = (n)-1; i >= 0; --i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define prique priority_queue
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.1415926
#define coutdb cout<<fixed<<setprecision(15)

const int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef int_fast64_t ll;
#define int int_fast64_t

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

int dp[61][2][2][2]; // dp[digit][L<=x?][y<=R?][same digit?]

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

  int L, R; cin >> L >> R;
  dp[60][0][0][0] = 1;
  for(int i = 59; i >= 0; i--){
    int ld = L>>i & 1, rd = R>>i & 1; //  (2進で)下からi桁目だけ見る (0-indexed)
    REP(j, 2) REP(k, 2) REP(s, 2){
      int tmp = dp[i+1][j][k][s];
      REP(x, 2) REP(y, 2){ // x, yの下からi桁目
        if(x and !y) continue; // x=1, y=0 はアウト

        int nj = j, nk = k, ns = s;
        if(!s and x!=y) continue; // 桁が揃わないのでアウト
        if(x and y) ns = 1;
        // j :  L<=x ?
        if(!j and !x and ld) continue; // x < L が確定するのでアウト
        if(x and !ld) nj = 1;
        // k :  y<=R ?
        if(!k and y and !rd) continue; // R < r が確定するのでアウト
        if(!y and rd) nk = 1;

        dp[i][nj][nk][ns] += tmp;
        dp[i][nj][nk][ns] %= MOD;
      }
    }
  }
  int ans = 0;
  REP(j, 2)REP(k, 2)REP(s, 2){
    // j==0 -> x==L, j==1 -> L<=x
    // k==0 -> y==R, k==1 -> y<=R
    // s==0 -> 全部桁同じ, s==1 -> 最上位が揃う
    ans += dp[0][j][k][s];
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
import heapq
N,M=map(int,input().split())
alist=list(map(int,input().split()))

cblist=[]
for i in range(M):
  B,C=map(int,input().split())
  cblist.append((C,B))
cblist.sort(reverse=True)

hq=[]
for a in alist:
  heapq.heappush(hq,a)
  
for C,B in cblist:
  for i in range(B):
    if C<=hq[0]:
      print(sum(hq))
      sys.exit(0)
    else:
      heapq.heapreplace(hq,C)
else:
  print(sum(hq))

Measured memory_bytes: 21440