akhauriyash/Code-Regression huggingface dataset:
// #include {{{
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
#include <tuple>
#include <utility>
#include <random>
#include <limits>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <cassert>
// }}}

using namespace std;

// macros {{{
template<typename T, size_t N>
constexpr size_t NELEMS(T (&)[N]) { return N; }

template<typename InputIt>
void PRINT_RANGE(InputIt first, InputIt last)
{
    for(; first != last; ++first)
        cout << *first << (first==last ? "" : " ");
    cout << "\n";
}

template<typename T>
void PRINT_MATRIX(T mat, size_t nr, size_t nc)
{
    for(size_t r = 0; r < nr; ++r) {
        for(size_t c = 0; c < nc; ++c) {
            cout << mat[r][c] << (c==nc-1 ? "" : " ");
        }
        cout << "\n";
    }
}

#define FOR(i, start, end) for(int i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)
// }}}

// types {{{
using ll  = long long;
using ull = unsigned long long;
// }}}

struct Edge {
    int to;
    int cost;
    Edge(int t, int c) : to(t), cost(c) {}
};

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

int V;
int E;
vector<vector<Edge>> G;

bool bellmanford(int start, vector<int>& d)
{
    d.resize(V);
    fill(begin(d), end(d), INF);
    d[start] = 0;

    REP(i, V) {
        REP(from, V) {
            if(d[from] == INF) continue;
            for(Edge e : G[from]) {
                int d_new = d[from] + e.cost;
                if(d_new < d[e.to]) {
                    d[e.to] = d_new;
                    if(i == V-1) return false;
                }
            }
        }
    }

    return true;
}

void solve()
{
    vector<vector<int>> D(V);
    for(auto& d : D) {
        d.resize(V);
    }

    bool allok = true;
    REP(start, V) {
        auto& d = D[start];
        if(!bellmanford(start, d)) {
            allok = false;
            break;
        }
    }

    if(!allok) {
        cout << "NEGATIVE CYCLE" << "\n";
    }
    else {
        REP(start, V) {
            auto& d = D[start];
            REP(v, V) {
                if(d[v] == INF) {
                    cout << "INF";
                }
                else {
                    cout << d[v];
                }
                cout << (v == V-1 ? "\n" : " ");
            }
        }
    }
}

int main()
{
    cin >> V >> E;
    G.resize(V);

    REP(_, E) {
        int s, t, d;
        cin >> s >> t >> d;
        G[s].emplace_back(t, d);
    }

    solve();

    return 0;
}

Measured memory_bytes: 3184
#include <bits/stdc++.h>
#define All(v) v.begin(), v.end()
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    map<char, int> mp;
    string S;
    cin>>S;
    for(auto c : S){
        mp[c]++;
    }
    if(mp.size()!=2){
        cout<<"No"<<endl;
        return 0;
    }else{
        for(auto p : mp){
            if(p.second!=2){
                cout<<"No"<<endl;
                return 0;
            }
        }
        cout<<"Yes"<<endl;
        return 0;
    }
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL x, y;

int main() {
	cin >> x >> y;
	
	LL z = x, ans = 0;
	while(z <= y) {
		ans++;
		z *= 2;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int i, number, k;
  char special_char;
  scanf("%d", &number);
  char str[number + 1];
  scanf("%s", str);
  scanf("%d", &k);
  special_char = str[k - 1];
  for(i = 0; i < number; i++) {
    if(str[i] == special_char) {
      printf("%c", str[i]);
    } else {
      printf("*");
    }
  }
  printf("\n");
  return 0;
}

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{

	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, ans =0; 
	cin >>n;
	VI h(n);
	rep(i, n) cin >>h[i];
	int cr = 0;
	rep(i, n-1){
		if(h[i] >= h[i+1]){
			cr++; ans = max(ans, cr);
		}else cr =0;
	}

	cout << ans <<"\n";
	return 0;
	
	
}


Measured memory_bytes: 640
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    s = input()
    t = input()
    ans = 0
    for i in range(len(s)):
        if s[i] != t[i]:
            ans += 1
    print (ans)






mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


Measured memory_bytes: 74180
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
    using namespace std;
    #define ll long long
    #define ld long double
    #define vll vector<ll>
    #define mll map<ll,ll>
    #define pll pair<ll,ll>
    #define ff first
    #define ss second
    #define pb push_back
    #define deb(x) cout<<#x<<" : "<<x<<endl;
    #define deb2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
    #define deb3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
    #define deb4(w,x,y,z) cout<<#w<<" : "<<w<<"\t"<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
    #define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define printv(a)  for(ll i=0;i<a.size();i++)  cout<<a[i]<<" ";
   
   
    const int mod=998244353.;
    const int N=1e6+5; 
   
    bool sortbysec(const pair<pair<ll,ll>,ll> &a, 
                      const pair<pair<ll,ll>,ll> &b) 
        { 
            return (a.second > b.second); 
        } 
        ll powermod(ll x, ll y, ll p)
        {
            ll res = 1;
            x = x % p;
            while (y > 0)
            {
                if (y & 1) res = (res*x) % p;
                y = y>>1;
                x = (x*x) % p;
            }
            return res;
        }
       
        bool isprime(int n) 
        { 
            if (n <= 1)  return false; 
            if (n <= 3)  return true; 
            if (n%2 == 0 || n%3 == 0) return false; 
            for (int i=5; i*i<=n; i=i+6) 
                if (n%i == 0 || n%(i+2) == 0) 
                   return false; 
           return true; 
        }
       
       
        int main()
    {
        FAST;
      ll n;
      cin>>n;
      vll a(n);
      for(ll i=0;i<n;i++)
      cin>>a[i];
      ll dp[n];
      for(ll i=0;i<n;i++)
      dp[i]=1e9+5;
      dp[0]=0;
      for(ll i=0;i<n;i++)
      {
          for(ll j:{i+1,i+2})
          {
              if(j<n)
              {
                  dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
              }
          }
      }
      cout<<dp[n-1]<<"\n";
        
        
        
        return 0;
    }

Measured memory_bytes: 1792
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let (N, M): (usize, usize) = (read(), read());
    use std::collections::{HashMap, VecDeque};
    let mut graph: HashMap<usize, Vec<usize>> = HashMap::new();
    for _ in 0..M {
        let a: usize = read();
        let b: usize = read();
        let entry = graph.entry(a).or_insert_with(|| vec![]);
        entry.push(b);
        let entry = graph.entry(b).or_insert_with(|| vec![]);
        entry.push(a);
    }
    let mut queue: VecDeque<usize> = VecDeque::new();
    queue.push_front(1);
    let mut ans: Vec<usize> = vec![0; N + 1];
    while let Some(now) = queue.pop_back() {
        match graph.get(&now) {
            None => {
                continue;
            }
            Some(nexts) => {
                for &next in nexts {
                    if ans[next] != 0 {
                        continue;
                    }
                    ans[next] = now;
                    queue.push_front(next);
                }
            }
        }
    }
    for &v in ans.iter().skip(2) {
        if v == 0 {
            println!("-1");
            return;
        }
    }
    println!("Yes");
    for &v in ans.iter().skip(2) {
        println!("{}", v);
    }
}


Measured memory_bytes: 13748
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    K, X = l_inpl()
    ans = []
    print(" ".join([ str(i) for i in list(range(X-K+1, X+K))]))
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 4080
#include <bits/stdc++.h>
#define ll long long
#define pq priority_queue
using namespace std;
const ll INF=(ll)1e9;
const ll MOD=(ll)1e9+7;
const ll MAX=100100;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
template<class T> inline bool chmax(T& a, T b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a>b) { a=b; return 1; } return 0; }

int main(){
    ll N,a=0;
    cin>>N;
    vector<ll> v;
    for(ll i=0;i<N;i++){
        ll n;
        cin>>n;
        if(i>0&&v[a-1]==n) continue;
        v.push_back(n);
        a++;
    }
    if(v.size()==1){
        cout<<"1"<<endl;
        return 0;
    }
    bool f,F=true;
    ll cnt=1;
    for(ll i=0;i<v.size()-1;i++){
        if(F){
            if(v[i]>v[i+1]) f=false;
            else f=true;
            F=false;
            continue;
        }
        if(f&&v[i]>v[i+1]){
            F=true;
            cnt++;
        }else if(!f&&v[i]<v[i+1]){
            F=true;
            cnt++;
        }
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 1400
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10


int main() {
	int A, B; cin >> A >> B;
	if ((A + B) % 2 == 0) {
		cout << (A + B) / 2 << endl;
	}
	else cout << "IMPOSSIBLE" << endl;




	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sf(n) scanf("%lld",&n)
#define sff(n,m) scanf("%lld %lld",&n,&m)
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PLL pair<ll,ll>
#define mod 1000007
#define mx 100002
#define FILE freopen("input.txt","r",stdin)

vector<ll>adj[mx];
ll dp[mx];

ll F(ll u)
{
  if(dp[u]!=-1) return dp[u];

  ll ret = 0;

  for(ll v:adj[u])
  {
    ret = max(ret,1+F(v));
  }

  return dp[u] = ret;
}

int main()
{
ll n,m,a,b;
cin>>n>>m;

while(m--)
{
  cin>>a>>b;
  adj[a].push_back(b);
}

memset(dp,-1,sizeof dp);

ll ans = 0;

for(ll i = 1;i<=n;i++)
{
  ans = max(ans,F(i));
}

cout<<ans<<endl;

return 0;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define dbgi(x) cout << #x << " = " << (x) << "\n";
#define dbgvi(x) cout << #x << " = "; for(int i = 0; i < (x.size()); ++i) cout << x[i] << " ";
#define mrk() cout << "HERE\n"
#define int long long
#define vi vector < int >
#define vs vector < string >
#define vii vector < vi >
#define viii vector < vii >
#define viiii vector < viii >
#define pii pair < int, int >
#define vpii vector < pii >
#define foru(i, a, b) for(int i = a; i < b; ++i)
#define ford(i, b, a) for(int i = b; i > a; --i)
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ld long double
using namespace std;

int n;

vii g;
vi used;

void dfs(int start, int v, int dist, vi &a){
    used[v] = 1;
    a[v] = dist;
    for(int u: g[v]){
        if(!used[u]){
            dfs(start, u, dist + 1, a);
        }
    }
}


signed main(){
    cin >> n;
    g.resize(n);
    used.resize(n);
    foru(i, 0, n - 1){
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    fill(used.begin(), used.end(), 0);
    vi cnt1(n);
    dfs(0, 0, 0, cnt1);
    fill(used.begin(), used.end(), 0);
    vi cnt2(n);
    dfs(n - 1, n - 1, 0, cnt2);
    int balance = 0;
    foru(i, 0, n){
        if(cnt1[i] <= cnt2[i]){
            balance++;
        } else {
            balance--;
        }
    }
    //cout << balance << "\n";
    if(balance > 0){
        cout << "Fennec";
    } else {
        cout << "Snuke";
    }

}



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

using ll = long long;
const int sz = 1e6 + 10;
const ll mod = 1000000007;
int n, ar[65];
ll dp[65][3];
string s1, s2;

ll rec( int x, int pr ) {
    if( x >= n ) return 1;
    ll &ret = dp[x][pr];
    if( ~ret ) return ret;
    ret = 0;
    if( pr == 0 ) {
        if( ar[x] == 1 ) ret = 3 * rec( x + ar[x], 1 );
        if( ar[x] == 2 ) ret = 6 * rec( x + ar[x], 2 );
        ret %= mod;
    }
    else if( pr == 1 ) {
        if( ar[x] == 1 ) ret = 2 * rec( x + ar[x], 1 );
        if( ar[x] == 2 ) ret = 2 * rec( x + ar[x], 2 );
        ret %= mod;
    }
    else if( pr == 2 ) {
        if( ar[x] == 1 ) ret = 1 * rec( x + ar[x], 1 );
        if( ar[x] == 2 ) ret = 3 * rec( x + ar[x], 2 );
        ret %= mod;
    }
    return ret;
}

int main() {
    #ifdef CLown1331
        freopen( "in.txt","r",stdin );
    #endif /// CLown1331
    while( scanf( "%d", &n ) == 1 ) {
        cin >> s1 >> s2;
        memset( dp, -1, sizeof dp );
        memset( ar, 0, sizeof ar );
        for( int i=0; i<n; i++ ) {
            if( s1[i] == s2[i] ) {
                ar[i] = 1;
            }
            else {
                ar[i] = 2;
                i += 1;
            }
        }
        cout << rec( 0, 0 ) << "\n";
    }
    return 0;
}



Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }

    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int A = scan.nextInt();
        int B = scan.nextInt();
        int H = scan.nextInt();
        int M = scan.nextInt();
        double hour_unit = (double) 360 / (12 * 60);
        double minute_unit = 360 / 60;
        double hours = hour_unit * (60 * H + M);
        double minutes = minute_unit * M;
        double hours_pi = Math.PI * (360 - hours) / 180;
        double minute_pi = Math.PI * (360 - minutes) / 180;
        double hours_x = A * Math.cos(hours_pi);
        double hours_y = A * Math.sin(hours_pi);
        double minutes_x = B * Math.cos(minute_pi);
        double minutes_y = B * Math.sin(minute_pi);
        double ans = (hours_x - minutes_x) * (hours_x - minutes_x) + (hours_y - minutes_y) * (hours_y - minutes_y);
        System.out.printf("%.12f\n", Math.sqrt(ans));
    }
}


Measured memory_bytes: 36104
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = list(input())

if S[2] == S[3] and S[4] == S[5]:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 2940
#include <stdio.h>
#include <iostream>

using namespace std;

int main()
{
	//  implement insertion sort
    //  output every result along each step
    int count;
    cin>>count;
    
    int *list = new int[count];
    for(int i =0;i<count;i++){
        cin>>list[i];
    }
    
    for(int k = 0;k<count;k++){
            cout<<list[k];
            if(k!=count-1){
                cout<<' ';
            }
        }
        cout<<endl;
    
    for(int i = 1;i<count;i++){
        int temp = list[i];
        int pos = i;
        for(int j = i-1;j>=0&&temp<list[j];j--){
                list[j+1] = list[j];
                pos = j;
        }
        list[pos] = temp;
        
        for(int k = 0;k<count;k++){
            cout<<list[k];
            if(k!=count-1){
                cout<<' ';
            }
        }
        cout<<endl;
    }
    
    delete[] list;
	return 0;
}

Measured memory_bytes: 3096
from fractions import gcd
A, B, C, D = map(int, input().split())
A-=1
lcm=C*D//gcd(C,D)
#B以下の個数
b = B-(B//C)-(B//D)+B//lcm
#A以下の個数
a = A-(A//C)-(A//D)+A//lcm
print(b-a)

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)

#define dbg(x) cerr << (#x) << " --> " << (x) << nl;
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

#define _9day ""

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree < pair <int, int>, null_type, less < pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1e5 + 7, inf = 1e9 + 7, mod = 1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

int n, m, q;
int ans[N], mx[N];
vector <int> g[N];

struct node {
  int v, d, c;
  node() {}
  node(int v, int d, int c) : v(v), d(d), c(c) {}
  void read() {
    scanf ("%d%d%d", &v, &d, &c);
    d++;
  }
} a[N];

queue <node> st;

void go(int id) {
  st.push(a[id]);
  while (sz(st)) {
    node v = st.front();
    st.pop();
    if (v.d <= mx[v.v]) continue;
    mx[v.v] = v.d;
    if (!ans[v.v]) ans[v.v] = v.c;
    for (auto to : g[v.v])
      st.push(node(to, v.d - 1, v.c));
  }
}

int main() {
  #ifndef _9day
    freopen (_9day".in", "r", stdin);
    freopen (_9day".out", "w", stdout);
  #endif

  scanf ("%d%d", &n, &m);
  rep(i, 1, m) {
    int v, u;
    scanf ("%d%d", &v, &u);
    g[v].pb(u);
    g[u].pb(v);
  }

  scanf ("%d", &q);
  rep(i, 1, q)
    a[i].read();

  per(i, q, 1)
    go(i);

  rep(i, 1, n)
    cout << ans[i] << nl;
  ioi
}


Measured memory_bytes: 9720
use std::io::stdin;
fn read() -> (i32, i32) {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let vec: Vec<i32> = s
        .trim()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    (vec[0], vec[1])
}

fn main() {
    let (a, b) = read();
    if a > b {
        println!("safe")
    } else {
        println!("unsafe")
    }
}


Measured memory_bytes: 2088
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int b[100001];
int main(int argc, const char * argv[]) {
    
    int n,h,ans = 0;
    
    scanf("%d %d",&n,&h);
    
    int ma = 0;
    
    for(int i=0,a;i<n;i++){
        scanf("%d %d",&a,&b[i]);
        if(ma < a)  ma = a;
    }
    
    sort(b,b+n);
    
    for(int i=n-1; i>=0;i--){
        if(ma > b[i]) break;
        
        h = h - b[i];
        ans++;
        if(h<=0){
            printf("%d\n",ans);
            return 0;
        }
    }
    
    if(h%ma != 0) ans+=1; 
    
    printf("%d\n",ans + h/ma);
    
    return 0;
}




Measured memory_bytes: 640
n, m = map(int, input().split())
s = input()
t = input()


def my_lcm(a, b):
    cum = a * b
    if a > b:
        a, b = b, a
    while a != 0:
        a, b = b % a, a
    # b がgcd になっている
    return cum // b


ans = my_lcm(n, m)
s_idx = 0
t_idx = 0
while s_idx < n and t_idx < m:
    if s[s_idx] != t[t_idx]:
        print(-1)
        exit()
    else:
        a = s[s_idx] + t[t_idx]
        t_idx += ans // n
        s_idx += ans // m
print(ans)


Measured memory_bytes: 3316
require 'pp'
n = gets.to_i
h = gets.split.map(&:to_i)
# p n
# p h
1.upto(n-1) do |i|
  if h[i-1] < h[i]
    h[i] -= 1
  elsif h[i-1] > h[i]
    puts 'No'
    exit
  end
end
# p h
puts 'Yes'
#y n y y


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

const int maxn = 100 + 7;

using namespace std;

int T[maxn], tot;
int N, M;

int main() {
	scanf("%d",&N);
	for(int i = 1; i <= N; ++i) {
		scanf("%d",&T[i]);
		tot += T[i];
	}
	scanf("%d",&M);
	for(int i = 1; i <= M; ++i) {
		int P, X;
		scanf("%d%d",&P,&X);
		printf("%d\n",tot - T[P] + X);
	}
	return 0;
}

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

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

    string s, t;
    cin >> s >> t;
    ll n = s.size();
    ll m = t.size();

    vector<vector<int>> cnt(26);
    rep(i, n){
        cnt[s[i] - 'a'].push_back(i);
    }

    rep(i, 26){
        sort(cnt[i].begin(), cnt[i].end());
    }

    // rep(i, 26){
    //     for(auto el: cnt[i]) cout << el << " ";
    //     cout << endl;
    // }

    rep(i, m){
        if(cnt[t[i] - 'a'].empty()){
            cout << -1 << endl;
            return 0;
        }
    }
    ll res = 0;
    int ptr = cnt[t[0] - 'a'].front();
    vector<int> a;
    rep1(i, m){
        a = cnt[t[i] - 'a'];
        if(a.back() <= ptr){
            res += n;
            ptr = a.front();
        }
        else{
            int idx = upper_bound(a.begin(), a.end(), ptr) - a.begin();
            ptr = a[idx];
        }
    }


    cout << res + ptr + 1 << endl;

    return 0;
}

Measured memory_bytes: 4548
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<(n);i++)
#define Rep(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
// const int mod=998244353;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

int modpow(int x,int n){
    int a=1;
    while(n) {
        if(n%2)a*=x,a%=mod;
        x=x*x%mod;
        n/=2;
    }
    return a;
}

void run(){
    int n;
    cin>>n;
    int c=0;
    map<pi,int> m;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        if(!a&&!b){
            c++;
            continue;
        }
        if(!b)m[{1,0}]++;
        else {
            int g=__gcd(a,b);
            a/=g,b/=g;
            if(b<0)a*=-1,b*=-1;
            m[{a,b}]++;
        }
    }
    int ans=1;
    map<pi,bool> f;
    for(auto e:m){
        pi p=e.fi;
        if(f[p])continue;
        int a=p.fi,b=p.se;
        pi q;
        if(!a)q={1,0};
        else if(a<0)q={b,-a};
        else q={-b,a};
        int t=m[q];
        ans=ans*((((modpow(2,e.se)+modpow(2,t))%mod)-1+mod)%mod)%mod;
        f[p]=true,f[q]=true;
    }
    cout<<(ans+c-1+mod)%mod<<endl;
}

Measured memory_bytes: 53504
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_CANDY_MAX		100000									// 最大飴数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i;
	char lc1Buf[1024], lc1Out[1024];

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// 飴数・限界値取得
	int liCCnt, liLimit;
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d%d", &liCCnt, &liLimit);

	// 飴取得
	int li1Candy[D_CANDY_MAX];
	for (i = 0; i < liCCnt; i++) {
#ifdef D_TEST
		fscanf(szpFpT, "%d", &li1Candy[i]);
#else
		fscanf(stdin, "%d", &li1Candy[i]);
#endif
	}
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif

	// 削除数合計取得
	long long llSum = 0;
	for (i = 1; i < liCCnt; i++) {

		// 削除数
		int liDel = li1Candy[i] + li1Candy[i - 1] - liLimit;
		if (liDel < 1) {										// なし
			continue;
		}

		// 削除
		if (li1Candy[i] < liDel) {
			li1Candy[i] = 0;
		}
		else {
			li1Candy[i] -= liDel;
		}

		// 削除数合計
		llSum += (long long)liDel;
	}

	// 結果セット
	sprintf(lc1Out, "%lld\n", llSum);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpT);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
  int N,D,ans=0,cnt=0;
  cin>>N>>D;
  int X[N][D];
  for(int i=0;i<N;i++){
    for(int j=0;j<D;j++) cin>>X[i][j];
  }
  for(int i=0;i<N;i++){
    for(int l=i+1;l<N;l++){
      for(int j=0;j<D;j++){
        ans+=(X[i][j]-X[l][j])*(X[i][j]-X[l][j]);
      }
      for(int k=0;k<10000;k++){
        if(ans==k*k) cnt++;
      }
      ans=0;
    }
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
 
int main(void)
{
    int n,i,j,len,temp,check;
    char st[11];
    int w[41];
     
    while(scanf("%d",&n))
    {
        if(n==0)
        break;
         
        for(i=0;i<n;i++)
        {
            scanf("%s",st);
            len = strlen(st);
            w[i] = len;
        }
        check = 0;
        for(i=0;i<n;i++)
        {
            temp = 0;
            j = i;
            while(1)
            {
                do{
                    temp+=w[j];
                    j++;
                }while(temp<5);
                if(temp>5)
                break;
                temp = 0;
                do{
                    temp+=w[j];
                    j++;
                }while(temp<7);
                if(temp>7)
                break;
                temp = 0;
                do{
                    temp+=w[j];
                    j++;
                }while(temp<5);
                if(temp>5)
                break;
                temp = 0;
                do{
                    temp+=w[j];
                    j++;
                }while(temp<7);
                if(temp>7)
                break;
                temp = 0;
                do{
                    temp+=w[j];
                    j++;
                }while(temp<7);
                if(temp>7)
                break;
                check = 1;
                break;
            }
            if(check==1)
            break;
        }
        printf("%d\n",i+1);
    }
    return 0;
}


Measured memory_bytes: 2068
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;

int main() {

	int K;
	int A, B;
	cin >> K >> A >> B;

	string poss = "NG";

	for (int i = A; i <= B; i++) {
		if (i % K == 0) {
			poss = "OK";
			break;
		}
	}

	cout << poss << endl;

	return 0;
}

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

// 無限大を表す値
const long long INF = 1LL<<60;

// 辺を表す型，ここでは重みを表す型を long long 型とします
struct Edge {
    int to; // 隣接頂点番号
    long long w; // 重み
    Edge(int to, long long w) : to(to), w(w) {}
};

// 重み付きグラフを表す型，各頂点の隣接リストを辺集合で表す
typedef vector<vector<Edge> > Graph;

// 緩和処理 (更新が行われたときは true を返し，行われないときは false を返す)
bool chmin(long long& a, long long b) {
    if (a > b) {
        a = b;
        return true;
    }
    else return false;
}

int main() {
    // 頂点数と辺数，始点
    int N, M, s; cin >> N >> M >> s;

    // グラフ
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        G[a].push_back(Edge(b, w));
    }

    // Bellman-Ford 法
    bool exist_negative_cycle = false; // 負閉路をもつかどうか
    vector<long long> dist(N, INF); // 最終的に各頂点への最短路長が格納される
    dist[s] = 0;
    for (int iter = 0; iter < N; ++iter) {
        bool update = false; // 更新が発生したかどうかを表すフラグ
        for (int v = 0; v < N; ++v) {
            // dist[v] = INF のときは頂点 v からの緩和を行わない
            if (dist[v] == INF) continue;
            
            for (auto e : G[v]) {
                // 緩和処理を行い，更新されたら update を true にする
                if (chmin(dist[e.to], dist[v] + e.w)) {
                    update = true;
                }
            }
        }

        // 更新が行われなかったら，すでに最短路が求められている
        if (!update) break;

        // N 回目の反復で更新が行われたならば，負閉路をもつ
        if (iter == N-1 && update) exist_negative_cycle = true;
    }

    // 結果出力
    if (exist_negative_cycle) cout << "NEGATIVE CYCLE" << endl;
    else {
        for (int v = 0; v < N; ++v) {
            if (dist[v] < INF) cout << dist[v] << endl;
            else cout << "INF" << endl;
        }
    }
}




Measured memory_bytes: 3168
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>
//#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define de(x,y) cout<<#x<<" :"<<x<<y;
#define int long long
#define SZ(xx) ((int)xx.size())
#define lowbit(xx) (xx&(-xx))
#define pb push_back
typedef pair<int,int> pii;

const int maxn = 3e3+5;

int dp[maxn][maxn], arr[maxn];

int dfs(int l,int r,int level) {
	if (l == r) {
		if (level & 1) return dp[l][r] = arr[l];
		else return dp[l][r] = -arr[l];
	}	
	else if (dp[l][r] != -1) return dp[l][r];
	else {
		int fg = 0;
		if (level & 1) fg = 1;
		else fg = -1;
		int A = dfs(l + 1, r, level + 1) + arr[l] * fg, B = dfs(l, r - 1, level + 1) + arr[r] * fg;
		if (level & 1) dp[l][r] = max(A, B);
		else dp[l][r] = min(A, B); 
		return dp[l][r];
	}
}

main() {
	IOS
	int n;
	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++)
		cin >> arr[i]; 
	cout << dfs(1, n, 1) << "\n";
}


Measured memory_bytes: 74452
#include <bits/stdc++.h>
#define ll long long
#define br cout << "\n" ;
#define all(x) (x).begin() ,(x).end()
#define rall(x) (x).rbegin() ,(x).rend()
#define pb push_back
#define ff first
#define ss second 
const int MOD = 1000* 1000 * 1000 + 7;
const int MAXN = 1000*1000 + 10 ; 
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
 int n ;
 cin>>n ;
 bool ok = false ; 
 for(int i = n ; i > 0 ; i=i/10)
{
	int d = i %10 ;
	if (d == 7 )
	ok = true ; 
}
cout << (ok ? "Yes" : "No"); 
return 0 ; 
}		



Measured memory_bytes: 3660
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  ll N,M;
  cin>>N>>M;
  ll a[M];
  ll b[M];
  ll p1[N+1]={};
  ll p2[N+1]={};
  FOR(i,0,M-1){
    cin>>a[i]>>b[i];
    if(a[i]==1){
      p1[b[i]]++;
    }
    if(b[i]==N){
      p2[a[i]]++;
    }
  }

  ll flag=0;
  FOR(i,1,N){
    if(p1[i]==1&&p2[i]==1){
      flag=1;
    }
  }
  if(flag==1){
    cout<<"POSSIBLE"<<endl;
  }else{
    cout<<"IMPOSSIBLE"<<endl;
  }



}
 


Measured memory_bytes: 6528
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] += self.table[s1]
            self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    rr = []

    def f(n,q):
        ps = [0, 1] + [I() for _ in range(n-1)]
        qs = []
        ms = set()
        for i in range(q):
            s,t = LS()
            t = int(t)
            if s == 'M':
                if t in ms:
                    continue
                ms.add(t)
            qs.append((s,t))
        uf = UnionFind(n+1)
        for i in range(2,n+1):
            if i in ms:
                continue
            uf.union(i, ps[i])

        r = 0
        for s,t in qs[::-1]:
            if s == 'Q':
                r += uf.find(t)
            else:
                uf.union(t, ps[t])

        return r

    while 1:
        n,q = LI()
        if n == 0 and q == 0:
            break
        rr.append(f(n,q))

    return '\n'.join(map(str,rr))


print(main())



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

int main()
{
    int N, K;
    cin >> N >> K;
    int A[N + 1] = {};
    int a;
    for (int i = 0; i < N; i++)
    {
        cin >> a;
        A[a] += 1;
    }

    sort(A, A + N + 1);

    int types = 0;
    for (int i = 1; i < N + 1; i++)
    {
        if (A[i] > 0)
        {
            types++;
        }
    }

    int diff = types - K;
    if (diff <= 0)
    {
        cout << 0 << endl;
        return 0;
    }

    int res = 0;
    for (int i = 1; i < N + 1; i++)
    {
        if (A[i] > 0)
        {
            res += A[i];
            diff--;
        }
        if (diff == 0)
        {
            break;
        }
    }

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

Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
using namespace std;

int n,p;
int a[55];
long long f[55][2];
int main()
{
    scanf ("%d %d",&n,&p);
    for (int i=1;i<=n;i++)
        scanf ("%d",&a[i]);
    f[0][0]=1;
    for (int i=1;i<=n;i++)
        {
        if (a[i]%2==1)
            {
            f[i][0]=f[i-1][0]+f[i-1][1];
            f[i][1]=f[i-1][1]+f[i-1][0];
            }
        else
            {
            f[i][0]=2*f[i-1][0];
            f[i][1]=2*f[i-1][1];
            }
        }
    printf ("%lld",f[n][p]);
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    
    n,q=map(int,input().split())
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        p[i],x[i] = map(int,input().split())
        
    px=[[] for i in range(n)]
    for pp,xx in zip(p,x):
        px[pp-1].append(xx)
    px=[sum(i) for i in px]
    c=[0]*n
    flag=[True]*n
     
    from collections import deque
    q = deque([(-1,0,0)])
    while q:
        parent,child,point = q.popleft()
        if parent!=-1:
            flag[parent]=False
        point+=px[child]
        c[child]=point
        for y in tree[child]:
            if y == parent:
                continue
            if flag[y]:
                q.append((child,y,point))
    print(*c)
if __name__ == '__main__':
    main()

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

using namespace std;

int div_roundup(int x, int y)
{
	return (x + y - 1) / y;
}

int main()
{
	int N, K;
	cin >> N >> K;
	int pos_1;
	for (pos_1 = 0; pos_1 < N; ++pos_1) {
		int A;
		cin >> A;
		if (A == 1) {
			break;
		}
	}

	int ans = N;

	for (int i = 0; i + K <= N; ++i) {
		if (pos_1 < i || i + K <= pos_1) {
			continue;
		}
		int result = 1 + div_roundup(i, K - 1) + div_roundup(N - (i + K), K - 1);
		ans = min(ans, result);
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
import math
import itertools


def dist(a, b):
    return math.sqrt((a[0]-b[0])**2 + (a[1] - b[1])**2)


def length(P, p):
    total = 0
    for i in range(len(p)-1):
        total += dist(P[p[i]], P[p[i+1]])
    return total


N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]

print(sum([length(P, p)
           for p in itertools.permutations(range(N))]) / math.factorial(N))


Measured memory_bytes: 4528
import java.util.Scanner;

public class Main {
  public static void main (String[] args) {
    Scanner in = new Scanner(System.in);

    while (in.hasNext()) {
      String S = in.next();
      String T = in.next();
      int count = 0;
      
      for (int i = 0; i < S.length(); ++i) {
        if (S.charAt(i) == T.charAt(i)) {
          ++count;
        }
      }

      System.out.println(count);
    }
  }
}

Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>

using namespace std;

struct itm{
	int val;
	int wht;
};

int main()
{
	int w, n, dp[1001], s, t, c=1;
	itm it[1000];
	
	while(cin >> w && w){
		cout << "Case " << c++ << ":" << endl;
		fill(dp, dp+1001, 0);
		cin >> n;
		for(int i = 0; i < n; i++){
			scanf("%d,%d",&it[i].val,&it[i].wht);
		}
		
		for(int i = 0; i < n; i++){
			for(int j = w; j >= it[i].wht; j--){
				if(j >= it[i].wht){
					dp[j] = max(dp[j], dp[j-it[i].wht]+it[i].val);
				}
			}
		}
		s = t = 0;
		for(int i = 0; i <= w; i++){
			if(dp[i] > s){
				s = dp[i];
				t = i;
			}
		}
		
		cout << s << endl << t << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int h[n];
  for (int i = 0; i < n; i++){
    cin >> h[i];
  }
  int cnt = 0;
  int hei = 0;
  for (int j = 0; j < n; j++){
    if (hei <= h[j]){
      cnt += 1;
      hei = h[j];
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
class Trees{
  vector<long> par;
  vector<long> rank;
  vector<long> size;
  public:
  long root(long i){
    long rt;
    if(par[i]==i){rt=i;rank[i]=1;}
    else{rt=root(par[i]);par[i]=rt;rank[i]=2;}
    return rt;
  }
  void unite(long i,long j){
    long rki=rank[i];long rkj=rank[j];
    if(rki<rkj){if(!same(i,j))size[root(j)]+=size[root(i)];par[root(i)]=root(j);rank[i]++;}
    else{if(!same(i,j))size[root(i)]+=size[root(j)];par[root(j)]=root(i);rank[j]++;}
  }
  bool same(long i,long j){
    return root(i)==root(j);
  }
  Trees(long n){
    for(long i=0;i<n;i++) {par.push_back(i);rank.push_back(1);size.push_back(1);};
  }
  long getsize(long i){
    return size[root(i)];
  }
};
int main(){
  long N,M;cin>>N>>M;
  Trees tree(N);
  vector<long>U(M);U[0]=N*(N-1)/2;
  vector<long>A(M),B(M);for(long i=0;i<M;i++)cin>>A[i]>>B[i];
  
  for(long i=0;i<M-1;i++){
    long a=A[M-i-1],b=B[M-i-1];
    U[i+1]=U[i]-(tree.same(a-1,b-1)?0:tree.getsize(a-1)*tree.getsize(b-1));
    tree.unite(a-1,b-1);
  }
  for(long i=M-1;i>=0;i--)cout<<U[i]<<endl;
}




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

using namespace std;

typedef long long int ll;

int main(){
	ll h,w;
	cin >> h >> w;
	if(w==1 || h==1){
		cout << 1 << "\n";
		return 0;
	}
	ll hlf = (h + 1) / 2;
	ll rem = h - hlf;
	cout << hlf * ((w + 1) / 2) + rem * (w / 2);	
	return 0;
}


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

const ll mod = 1000000007;

int main(void)
{
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll left = c % b == 0 ? c / b : c / b + 1;
	ll right = a % d == 0 ? a / d : a / d + 1;
	if (left <= right) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 3676
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    V=LI()
    
    ans=0
    import heapq
    
    #左からa個，右からb個とって，あまり分で負数を捨てる
    for a in range(K+1):
        for b in range(K+1):
            if a+b>min(K,N):
                break
            hq=[]
            heapq.heapify(hq)
            for i in range(a):
                heapq.heappush(hq,V[i])
            for j in range(b):
                heapq.heappush(hq,V[N-1-j])
                
            temp=0
            rem=K-(a+b)
            for i in range(a+b):
                v=heapq.heappop(hq)
                if v>=0:
                    temp+=v
                else:
                    if rem>0:
                        rem-=1
                    else:
                        temp+=v
                        
            ans=max(ans,temp)
            
    print(ans)
                
            

main()


Measured memory_bytes: 69804
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = list(Counter(a).values())
c.sort()

ans = n
cnt = 0
for i in range(n):
    m = i + 1 - cnt
    while c and c[-1] > ans // m:
        ans -= c.pop()
        cnt += 1
        m -= 1
    print(ans // m)

Measured memory_bytes: 46640