akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

 using namespace std;
 typedef long long ll;
 #define rep(i, n) for(int i = 0; i < (int)(n); i++)

 int main() {
   int N, K, tmp, count = 0, ans = 0, sum = 0;
   cin >> N >> K;
   vector<int> A(N + 1);
   rep(i, N) {
     cin >> tmp;
     A.at(tmp)++;
     if (A.at(tmp) == 1) count++; //ボールが存在する数字の種類
   }

   if (count <= K) ans = 0;
   else {
     sort(A.begin(), A.end()); //0個含めて個数が少ない順にソート
     for(int i = N - count; i < N; i++) {
       if (A.at(i) > 0) {
         if (count > K) {
           ans += A.at(i);
           count--;
           if (count == K) break;
         }
       }
     }
   }

   cout << ans << endl;
 }


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w,k,ans1=0;
  cin>>h>>w>>k;
  int b1=pow(2,h),b2=pow(2,w);
  vector<vector<char>> c(h,vector<char>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      scanf(" %c",&c[i][j]);
    }
  }
  for(int i=0;i<b1;i++){
    for(int j=0;j<b2;j++){
      int ans=0;
      for(int l=0;l<h;l++){
        for(int m=0;m<w;m++){
          if(c[l][m]=='#'&&(!(i & (1<<l))) &&(!(j & (1<<m)))){
            ans++;
          }
        }
      }
      if(ans==k){
        ans1++;
      }
    }
  }
  cout<<ans1<<endl;
}

Measured memory_bytes: 4124
use std::io::Read;

fn main() {
    let mut buf = String::new();

    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: u32 = iter.next().unwrap().parse().unwrap();
    let number_tuple: Vec<(i32, i32, i32)> = (0..n)
        .map(|_| {
            (
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
            )
        })
        .collect();

    let mut prev_numbers = (0, 0, 0);
    let mut result = "Yes";
    for numbers in number_tuple {
        let time_diff = numbers.0 - prev_numbers.0;
        let x_diff = i32::abs(numbers.1 - prev_numbers.1);
        let y_diff = i32::abs(numbers.2 - prev_numbers.2);
        if time_diff < x_diff + y_diff {
            result = "No";
            break;
        }
        if (time_diff % 2 == 0 && (x_diff + y_diff) % 2 != 0)
            || (time_diff % 2 != 0 && (x_diff + y_diff) % 2 == 0)
        {
            result = "No";
            break;
        }
        prev_numbers = numbers;
    }
    println!("{}", result);
}

Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	int minn=0x3f3f3f3f;
	scanf("%d%d%d",&a,&b,&c);
	minn=min(a+b,minn);
	minn=min(a+c,minn);
	minn=min(b+c,minn);
	printf("%d",minn);
	return 0;
 } 

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
q = int(input())
s = sum(a)
d = {}
for i in a:
    if i not in d:
        d[i] = 0
    d[i] += 1
for _ in range(q):
    b,c = map(int,input().split())
    if b not in d:
        print(s)
        continue
    if c not in d:
        d[c] = 0
    new = d[c] + d[b]
    s -= d[b]*b
    s += (new - d[c])*c
    d[b] = 0
    d[c] = new
    print(s)

Measured memory_bytes: 20628
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

using namespace std;

int main()
{
    int n;

    cin >> n;
    cout << n*n*n;

}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n, x;
    cin >> n >> x;
    
    vector<ll> l(n);
    for(ll i=0; i<n; i++)
        cin >> l[i];
    
    vector<ll> d(n+1);
    d[0] = 0;
    for(ll i=1; i<n+1; i++)
        d[i] = d[i-1] + l[i-1];
    
    ll ind = 0;
    for(; d[ind] <= x && ind < n+1; ++ind)
        continue;
    
    cout << ind << endl;
    
    return 0;
}



Measured memory_bytes: 256
// ABC 151-D
// 2020.1.12 bal4u

#include <stdio.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

void ins(char *s) { // 文字列の入力　スペース以下の文字で入力終了
	do *s = gc();
	while (*s++ > ' ');
	*(s-1) = 0;
}

int H, W;
char map[22][22];
char vis[22][22];
int ans;

#define MAX 1000000
typedef struct { int r, c; int s; } Q;
Q q[MAX+5]; int top, end;
int mv[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

void bfs(int r0, int c0) {
	int i, r, c, s, rr, cc, ma;

	memset(vis, 0, sizeof(vis));
	top = 0, end = 1;
	q[0].r = r0, q[0].c = c0, q[0].s = 0;
	vis[r0][c0] = 1;
	while (top != end) {
		r = q[top].r, c = q[top].c, s = q[top++].s;
		if (s > ans) ans = s;
		for (i = 0; i < 4; ++i) {
			rr = r + mv[i][0], cc = c + mv[i][1];
			if (map[rr][cc] == '.' && vis[rr][cc] == 0 &&
				rr >= 0 && rr < H && c >= 0 && c < W) {
				vis[rr][cc] = 1;
				q[end].r = rr, q[end].c = cc, q[end++].s = s+1;
			}
		}
	}
}

int main()
{
	int r, c;
	
	H = in(), W = in();
	for (r = 0; r < H; ++r) ins(map[r]);
	for (r = 0; r < H; ++r) for (c = 0; c < W; ++c) {
		if (map[r][c] == '.') bfs(r, c);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
n, k = map(int, input().split())
ans = []
count = 0

for i in range(k):
  d = int(input())
  l = list(map(int, input().split()))
  for j in range(d):
    if l[j] not in ans:
      ans.append(l[j])
  
print(n - len(ans))

Measured memory_bytes: 9164
#include<stdio.h>
int main()
{
	int n;
	while((scanf("%d",&n)!=EOF)&&(n!=0))
	{
		int i;
		int a[100000];
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		int one=0,two=0,four=0;
		for(i=0;i<n;i++)
		{
			if(a[i]%4==0)
			{
				four++;
			}
			else if(a[i]%2==0)
			{
				two++;
			}else
			{
				one++;
			}
		}
		if(four<one-1||(four==one-1)&&two!=0)
		{
			printf("No");
		}else
		{
			printf("Yes");
		}
	}
return 0;
}

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

using namespace std;

int main(){
	long long a, b, c, d, mod = 998244353;
	cin>>a>>b>>c>>d;
	long long dp[c+1][d+1] = {};
	dp[a][b] = 1;
	for(long long i = 1; i <= c; i++){
		for(long long j = 1; j <= d; j++){
			dp[i][j] += dp[i-1][j]*j;
			dp[i][j] += dp[i][j-1]*i;
			dp[i][j] -= ((i-1)*(j-1)*dp[i-1][j-1])%mod;
			dp[i][j] = (dp[i][j]+mod)%mod;
		}
	}
	cout<<dp[c][d];
}


Measured memory_bytes: 73976
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;vll a(n),ans(100010,0);
  for(ll i=0;i<n;i++){cin>>a[i];ans[a[i]]++;ans[a[i]+1]++;ans[a[i]+2]++;}
  cout<<*max_element(ans.begin(),ans.end());
}

Measured memory_bytes: 1792
import sys
from collections import defaultdict
import math
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
d = defaultdict(int)
M_ = M
MOD = 10 ** 9 + 7

if M == 1:
    print(1)
    exit()

while True:
    for i in range(2, int(M_ ** 0.5) + 1):
        if M_ % i == 0:
            M_ //= i
            d[i] += 1
            break
    else:
        if M_ != 1:
            d[M_] += 1
        break

maxi = max(d.values())
fact = [0] * (maxi + N + 1)
p = 1

def nCr(n, r):
    if r > n - r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(2, r+1):
        ret //= i

    return ret

ans = 1
nCr_d = {}
for key, val in d.items():
    if (val+N-1, N-1) not in nCr_d:
        nCr_d[(val+N-1, N-1)] = nCr(val+N-1, N-1)
    ans = (ans * nCr_d[(val+N-1, N-1)]) % MOD

print(ans)

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

int main() {
    string a;
    cin >> a;
    int n = a.size();
    vector<int> counter(256, 0);

    ll ans = 1;
	rep(i,n) {
		ans += i - counter[a[i]];
		counter[a[i]]++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
int l[203],n,ans;
int main(){
  cin>>n;
  for(int i=0;i<n*2;i++)cin>>l[i];
  sort(l,l+(n*2));
  for(int i=(n*2)-2;i>=0;i-=2)ans+=l[i];
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
  int n,k,d,ele,count=0;
  scanf("%d%d",&n,&k);
  int a[n+1];
  for (int i=0;i<=n;i++)
    a[i]=0;
  for (int i=0;i<k;i++)
  {
    scanf("%d",&d);
    for (int j=0;j<d;j++)
    {
      scanf("%d",&ele);
      a[ele]++;
    }
  }
  for (int i=1;i<=n;i++)
  {
    if (a[i]==0)
      count++;
  }
  printf("%d\n",count);
  return 0;
}

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

struct S {
	ll zer;
	ll one;
	ll inv;
};

S op(S x, S y) {
	return S{
		x.zer + y.zer, 
		x.one + y.one, 
		x.inv + y.inv + x.one * y.zer
	};
}

S e() {
	return S{0, 0, 0};
}
/*
struct F {
	bool flipped?;
};
*/
S mapping(bool f, S x) {
	if (f) {
		return S{
			x.one,
			x.zer,
			x.zer * x.one - x.inv
		};
	} else return x;
}

bool composition(bool f, bool g) {
	return f ^ g;
}

bool id() {
	return false;
}

int main() {
	cin.tie(nullptr); ios_base::sync_with_stdio(false);
	int n, q; cin >> n >> q;
	vector<S> a(n);
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;
		if (x == 1) a[i] = S{0, 1, 0};
		else a[i] = S{1, 0, 0};
	}
	lazy_segtree<S, op, e, bool, mapping, composition, id> st(a);
	for (int i = 0; i < q; ++i) {
		int t, l, r; cin >> t >> l >> r;
		if (t == 1) {
			st.apply(l-1, r, true);
		}
		else {
			cout << st.prod(l-1, r).inv << "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 20348
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=110;
const int inf=999999999;
int n,m;
int tot=1;
int edge[MAXN*MAXN*2],nxt[MAXN*MAXN*2],w[MAXN*MAXN*2],hd[MAXN*MAXN];
inline void add_edge(int u,int v,int c)
{
    edge[tot]=v,w[tot]=c;
    nxt[tot]=hd[u],hd[u]=tot++;
}
struct node{
    int pos,val;
    friend bool operator <(node a,node b)
    {
        return a.val>b.val;
    }
};
priority_queue<node> q;
int dis[MAXN*MAXN];
char mp[MAXN][MAXN];
bool book[MAXN*MAXN];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++) cin>>mp[i][j];
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        if(i<n-1) add_edge(i*m+j+1,(i+1)*m+j+1,(mp[i][j]=='.'&&mp[i+1][j]=='#'));
        if(j<m-1) add_edge(i*m+j+1,i*m+(j+1)+1,(mp[i][j]=='.'&&mp[i][j+1]=='#'));
    }
    add_edge(0,1,mp[0][0]=='#');
    for(int i=0;i<=n*m;i++) dis[i]=(i==0)? 0:inf;
    q.push({0,0});
    while(!q.empty())
    {
        int x=q.top().pos;q.pop();
        if(book[x]) continue;
        book[x]=1;
        for(int i=hd[x];i;i=nxt[i])
        if(dis[edge[i]]>dis[x]+w[i])
        {
            dis[edge[i]]=dis[x]+w[i];
            q.push({edge[i],dis[edge[i]]});
        }
    }
    cout<<dis[n*m]<<endl;
	return 0;
}


Measured memory_bytes: 640
n = input()
card = range(1, 2*n+1)
for i in xrange(input()):
    k = input()
    if k==0:
        card = [card[i/2 + (i%2)*n] for i in xrange(2*n)]
    else:
        card = card[k:] + card[:k]
for i in xrange(2*n):
    print card[i]

Measured memory_bytes: 4212
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> tri;
typedef pair<double,double> point;
const ll MAX = 30000;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};
ll mod_pow(ll n, ll p, ll m){
    ll ret = 1;
    ll mul = n%m;
    while(p){
        if (p&1) ret = ret*mul%m;
        p >>= 1;
        mul = mul*mul%m;
    }
    return ret;
}
ll popcount(ll a){
    ll res = 0;
    while (a > 0){
        res += a%2;
        a /= 2;
    }
    return res;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    string x;
    cin >> n >> x;
    vector<ll> p(n+1,0);
    rep(i,1,n+1){
        ll a = i,c = 0;
        while (a != 0){
            a %= popcount(a);
            c++;
        }
        p[i] = c;
    }
    ll cnt = 0;
    rep(i,n){
        if (x[i] == '1') cnt++;
    }
    ll s = cnt-1,l = cnt+1,sn = 0,ln = 0,ns = 1,nl = 1;
    rep(i,n){
        if (s != 0) (sn += (x[n-i-1]-'0')*ns)%=s;
        (ln += (x[n-i-1]-'0')*nl)%=l;
        if (s != 0) (ns *= 2)%=s;
        (nl *= 2)%=l;
    }
    rep(i,n){
        if (x[i] == '0'){
            ll m = mod_pow(2,n-i-1,l);
            PRINT(p[(ln+m)%l]+1);
        }
        else{
            if (cnt == 1){
                PRINT(0);
            }
            else{
                ll m = mod_pow(2,n-i-1,s);
                PRINT(p[(sn+s-m)%s]+1);
            }
        }
    }
}


Measured memory_bytes: 5192
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define MAX 10e9

ll mul = 1000000007;
ll N;
std::vector<ll> v;
ll ans = 1;

int main() {
  cin >> N;
  rep(i,N) {
    ll a;
    scanf("%lld", &a);
    v.push_back(a);
  }

  ll end = N - 1;
  ll bucket[N];
  rep(i,N) bucket[i] = 0;

  sort(v.begin(), v.end());

  for (auto itr = v.begin(); itr != v.end(); ++itr) {
    bucket[*itr]++;
  }

  for (int i = end; i >= 0; i -= 2) {
    if (i == 0) {
      if (!bucket[i]) {
        cout << 0 << endl;
        return 0;
      }
    } else {
      if (!(bucket[i] == 2)) {
        cout << 0 << endl;
        return 0;
      } else {
        ans *= 2;
        ans %= mul;
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 1908
rtimes = []

24.times.each do
  rn, rt = gets.strip.split(" ")
  rtimes << [rn, rt.to_f]
end

semifinals = []
rests = []

for t in (0..2)
  race = rtimes[(t * 8), 8].sort{|a, b| a[1] <=> b[1]}
  semifinals << race.shift
  semifinals << race.shift
  rests += race
end

rests.sort!{|a, b| a[1] <=> b[1]}
semifinals << rests.shift
semifinals << rests.shift

semifinals.each{|rn, rt| printf("%s %.2f\n", rn, rt)}




Measured memory_bytes: 6880
#include <vector>
#include <iostream>
using namespace std;
int n, m, memo[100100];
vector<int> adj[100100];

int dfs(int i) {
    if (memo[i] >= 0) return memo[i];
    int len = 0;
    for (int j : adj[i]) len = max(len, dfs(j) + 1);
    return memo[i] = len;
}

int main() {
    cin >> n >> m;
    while (m--) {
        int x, y; cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
    }
    fill(memo, memo+n, -1);
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, dfs(i));
    cout << ans << endl;
}


Measured memory_bytes: 8192
#include <unordered_map>
  #include <functional>
  #include <algorithm>
  #include <iostream>
  #include <climits>
  #include <vector>
  #include <stack>
  #include <queue>
  #include <map>
  #include <set>
  #define mod 1000000007
  using namespace std;
  #define ll long long int
    
  
  int main()
  {
  ll n;
  cin>>n;
  ll a[n];
  for(int i=0;i<n;i++) 
    {
      cin>>a[i];
    }
  ll suffix[n];
  suffix[n-1]=a[n-1];
   for(int i=n-2;i>=0;i--)
   {
    suffix[i]=(suffix[i+1]+a[i])%mod;
   }
   ll ans=0;
   for(int i=0;i<n-1;i++)
   {
    ans=(ans+(a[i]*suffix[i+1])%mod)%mod;
   }
   cout<<ans;
 }


Measured memory_bytes: 6664
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		long tempA = A;
		ArrayList<Long> ary1 = new ArrayList<Long>();
		for(int i = 2; i <= Math.sqrt(tempA); i++) {
			int flag = 0;
			while(A % (long)i == 0) {
				if(flag == 0) ary1.add((long)i);
				flag = 1;
				A /= i;
			}
		}
		if(A != 1) {
			ary1.add(A);
		}
		long tempB = B;
		ArrayList<Long> ary2 = new ArrayList<Long>();
		for(int i = 2; i <= Math.sqrt(tempB); i++) {
			int flag = 0;
			while(B % (long)i == 0) {
				if(flag == 0) ary2.add((long)i);
				flag = 1;
				B /= i;
			}
		}
		if(B != 1) {
			ary2.add(B);
		}
		long ans = 0;
		for(int i = 0; i < ary1.size(); i++) {
			if(ary2.contains(ary1.get(i))) ans++;
		}
		System.out.println(ans + 1);
	}
}


Measured memory_bytes: 24020
while True:
	h,w=map(int,input().split())
	if h==0 and w==0:
		break
		
	for i in range(h):
		for j in range(w):
			if i==0 or i==h-1:
				print("#",end="")
			else:
				if j==0 or j==w-1:
					print("#",end="")
				else:
					print(".",end="")
		print("")
	print("")
			


Measured memory_bytes: 7008
#include <bits/stdc++.h>
#define N 200010
#define pb push_back
#define fi first
#define se second
#define si size()
#define ll long long
#define mp make_pair
#define iter ::iterator
#define all(v) v.begin(), v.end()
#define pp pop_back
#define mapiter map<int, int>::iterator
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forn1(i, n) for(int i = 1; i <= n; ++i)
#define forr(i, n)	for(int i = n - 1; i >= 0; --i)
#define forr1(i, n)	for(int i = n; i >= 1; --i)
#define form(l, r, i)	for(int i = l; i <= r; ++i)
#define forv(r, l, i)	for(int i = r; i >= l; --i)
#define r0 return 0
#define barnarnar ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lld long double
#define elif else if
 
const int inf = 1e9 + 7;
const lld EPS = 0.00000001;
const ll modwdop = 998244353ll;
 
ll pp = 13337ll;
ll modw = 1e9 + 7;
 
using namespace std;

int main()
{
	barnarnar
	int n, m;
	cin >> n >> m;
	cout << (n + m) * (n + m - 1) / 2- n * m;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
#define REP(i,n) for (int i = 0; i < n; ++i)
#define REPR(i,n) for (int i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORE(x,xs) for (auto& x : xs)
#define ALL(x) x.begin(), x.end()

const int MAX = 2e5+10;
const ll INF = 1e18;
ll N, C;
ll H[MAX];
ll dp[MAX];

template<typename T> class ConvexHullTrick {
private:
    typedef pair<T, T> tt;
    vector<tt> lines;
    bool isMonotricX;
    function<bool(T l, T r)> comp;

public:
    ConvexHullTrick(bool flagX = false, function<bool(T l, T r)> compFunc = [](T l, T r) {return l >= r;}) : isMonotricX(flagX), comp(compFunc) {
        lines.emplace_back(0, 0);
    };

    bool check(tt l1, tt l2, tt l3) {
        if (l1 < l3) swap(l1, l3);
        return (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first);
    }

    void add(T a, T b) {
        tt line(a, b);
        while (lines.size() >= 2 && check(*(lines.end()-2), lines.back(), line)) lines.pop_back();
        lines.emplace_back(line);
    }

    T f(int i, T x) {
        return lines[i].first * x + lines[i].second;
    }

    T f(tt line, T x) {
        return line.first * x + line.second;
    }

    T get(T x) {
        if (isMonotricX) {
            static int head = 0;
            while (lines.size() - head >= 2 && comp(f(head, x), f(head+1, x))) head++;
            return f(head, x);
        } else {
            int low = -1, high = lines.size() - 1;
            while (high - low > 1) {
                int mid = (high + low)/2;
                (comp(f(mid, x), f(mid+1, x)) ? low : high) = mid;
            }
            return f(high, x);
        }
    }
};

int main () {
    cin >> N >> C;
    ConvexHullTrick<ll> cht(false);
    REP (i, N) {
        cin >> H[i];
        ll res = INF;
        if (i == 0) res = 0;
        else res =cht.get(H[i]) + H[i]*H[i] + C;
        dp[i] = res;
        cht.add(-2*H[i], dp[i]+H[i]*H[i]);
    }
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 8944
from math import factorial


def main():
    n, m = map(int, input().split())
    if abs(n-m) == 0:
        ans = (2*factorial(n)*factorial(m)) % (10**9 + 7)
    elif abs(n-m) == 1:
        ans = (factorial(n)*factorial(m)) % (10**9 + 7)
    else:
        ans = 0
    print(ans)


if __name__ == "__main__":
    main()


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

void swap(int *a,int *b);

int main(void){
  int x,y,z;
  scanf("%d %d %d",&x,&y,&z);
  swap(&x,&y);
  swap(&x,&z);
  printf("%d %d %d",x,y,z);
  
  return 0;
}

void swap(int *a,int *b){
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
	return;
}
     
  

Measured memory_bytes: 1732
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

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

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let a: isize = iterator.next().unwrap().parse().unwrap();
    let b: isize = iterator.next().unwrap().parse().unwrap();

    let c: isize = iterator.next().unwrap().parse().unwrap();
    let d: isize = iterator.next().unwrap().parse().unwrap();

    vec![
        a * c,
        a * d,
        b * c,
        b * d,
    ].iter().max().unwrap().to_string()
}


Measured memory_bytes: 2128
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    buf = {}
    K = iRaw()
    tmp = 7%K
    buf[tmp]=1
    idx = 1
    while True:
        if tmp == 0:
            print(idx)
            return
        idx+=1
        tmp = (tmp*10+7)%K
        if tmp in buf:
            print(-1)
            return
        buf[tmp]=1

main()


Measured memory_bytes: 204556
#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

int main() {
    int N, M;
    map<int, vector<int>> workMap {};

    cin >> N >> M;

    for (int i { 0 }; i < N; ++i) {
        int a, b;
        cin >> a >> b;

        if (!workMap.count(a)) {
            workMap[a] = {};
        }

        workMap[a].push_back(b);
    }

    priority_queue<int> targets {};

    int result = 0;
    for (int i { M - 1 }; i >= 0; --i) {
        int remainDay = M - i;
        vector<int> moneys = {};
        if (workMap.count(remainDay)) {
            moneys = workMap.at(remainDay);
            for (const auto& w : moneys) targets.push(w);
        }

        if (targets.empty()) continue;

        int maxWorkMoney = targets.top();
        targets.pop();

        result += maxWorkMoney;
    }
    cout << result << endl;

    return 0;
}


Measured memory_bytes: 10880
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

int n, m;
int a[100010];

int ans = 0;

vi G[100010];

int dfs( int x , int p ){
  int res = 0;
  YYS( w , G[x] ){
    if( w == p ){
      continue;
    }
    chmax( res , dfs( w , x ) );
  }
  res++;
  if( p != 0 and res == m ){
    ans++;
    return 0;
  }
  return res;
}

int main(){

  n = in();
  m = in();
  REP( i , n ){
    a[i] = in() - 1;
  }
  
  if( a[0] != 0 ){
    a[0] = 0;
    ans = 1;
  }

  REP( i , n ){
    G[ a[i] ].pb( i );
  }

  dfs( 0 , 0 );

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


Measured memory_bytes: 10752
def calc(n):
    if res[n] != 0:
        return res[n]
    tmp = calc(n-1) + calc(n-2)
    res[n] = tmp
    return tmp

N = int(input())
res = [0] * 100
res[0] = 2
res[1] = 1
calc(N)
print(res[N])

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

int main(){
    int N, T, A;
    cin >> N >> T >> A;
    double min_dif = 10000;
    int place = 0;
    for (int i = 0; i < N; i++){
        int H;
        cin >> H;
        if (abs(T - H * 0.006 - A) < min_dif){
            min_dif = abs(T - H * 0.006 - A);
            place = i;
        }
    }
    cout << place + 1 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int a=scan.nextInt();
        int b=scan.nextInt();
        int area=a*b;
        int lap=2*(a+b);
        System.out.println(area+" "+lap);
    }
}


Measured memory_bytes: 26140
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int A, B, cost = 0;
  cin >> A >> B;
  if(A >= 13){
    cost = B;
  } else if(A >= 6){
    cost =B / 2;
  }
  
  cout << cost << endl;
  
  return 0;
}

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

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

    

Measured memory_bytes: 256
a, b, k = [int(i) for i in input().split(" ")]

for i in range(int(k / 2)):
  if a % 2 == 1:
    a -= 1

  b += (a / 2)
  a = a / 2

  if b % 2 == 1:
    b -= 1

  a += (b / 2)
  b = b / 2

if k % 2 == 1:
    if a % 2 == 1:
        a -= 1

    b += (a / 2)
    a = a / 2

print("{} {}".format(int(a), int(b)))

Measured memory_bytes: 3064
import bisect
A,B,Q=map(int,input().split())
INF=10**12
S=[-INF]
for i in range(A):
  S.append(int(input()))
S.append(INF)
T=[-INF]
for i in range(B):
  T.append(int(input()))
T.append(INF)
for i in range(Q):
  x=int(input())
  sh=S[bisect.bisect_left(S,x)]
  sl=S[bisect.bisect_left(S,x)-1]
  th=T[bisect.bisect_left(T,x)]
  tl=T[bisect.bisect_left(T,x)-1]
  a1=abs(x-sh)+abs(sh-th)
  a2=abs(x-sl)+abs(sl-th)
  a3=abs(x-sh)+abs(sh-tl)
  a4=abs(x-sl)+abs(sl-tl)
  a5=abs(x-th)+abs(th-sh)
  a6=abs(x-tl)+abs(tl-sh)
  a7=abs(x-th)+abs(th-sl)
  a8=abs(x-tl)+abs(tl-sl)
  print(min(a1,a2,a3,a4,a5,a6,a7,a8))

Measured memory_bytes: 12092
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;

int main() {
	int M, N, K;
	cin >> M >> N >> K;
	vs field(M);
	REP(i, M) {
		cin >> field[i];
	}

	vvi J(M+1, vi(N+1)), O(M+1, vi(N+1)), I(M+1, vi(N+1));
	REP(i, M) {
		REP(j, N) {
			if (field[i][j] == 'J') {
				J[i+1][j+1] = 1;
			}
			else if (field[i][j] == 'O') {
				O[i+1][j+1] = 1;
			}
			else if (field[i][j] == 'I') {
				I[i+1][j+1] = 1;
			}
		}
	}
	FOR(i, 1, M) {
		FOR(j, 2, N) {
			J[i][j] += J[i][j - 1];
			O[i][j] += O[i][j - 1];
			I[i][j] += I[i][j - 1];
		}
	}
	FOR(i, 2, M) {
		FOR(j, 1, N) {
			J[i][j] += J[i - 1][j];
			O[i][j] += O[i - 1][j];
			I[i][j] += I[i - 1][j];
		}
	}

	int a, b, c, d;
	REP(i, K) {
		cin >> a >> b >> c >> d;
		a--; b--;
		int ansj = J[c][d] - J[c][b] - J[a][d] + J[a][b];
		int anso = O[c][d] - O[c][b] - O[a][d] + O[a][b];
		int ansi = I[c][d] - I[c][b] - I[a][d] + I[a][b];
		cout << ansj << " " << anso << " " << ansi << endl;
	}
	
	return 0;
}

Measured memory_bytes: 13940
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define se second
#define pb push_back
#define ft fflush(stdout)
 
 
using namespace std;
 
 
const int N = 3e5 + 123;
const int PLS = 3e5 + 123;
const ll mod = 1e9 + 7;
const ll inf = 1e16;


ll n, c[4], x;
double dp[302][302][302];
bool vis[302][302][302];


int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        c[x]++;    
    }
    double m = n;
    cout.precision(20);
    for (ll k = 0; k <= 300; k++)
        for (ll j = 0; j <= 300; j++)
            for (ll i = 0; i <= 300; i++) {
                double t = (i + j + k), t1, t2, t3;
                if (t > n)
                    continue;
                if (t == 0) {
                    dp[i][j][k] = 0;
                    continue;
                }
                t1 = i; t2 = j; t3 = k;
                dp[i][j][k] = m / t;
                dp[i][j][k] += (t1 / t) * dp[i - 1][j][k];
                dp[i][j][k] += (t2 / t) * dp[i + 1][j - 1][k];
                dp[i][j][k] += (t3 / t) * dp[i][j + 1][k - 1];
            }
    cout << dp[c[1]][c[2]][c[3]];
}


Measured memory_bytes: 215296
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;
int cnt[N];
int a[N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	for (int i = 1; i < N; i++) cnt[i] = cnt[i >> 1] + (i & 1);
	int n;
	cin >> n;
	int A, B, C;
	cin >> A >> B >> C;
	int tot = 1 << n;
	for (int i = 0; i < n; i++) cin >> a[1<<i];
	for (int i = 1; i < tot; i++)
	{
		a[i] = a[i - (i & -i)] + a[i & -i];
	}
	int ans = INF;
	for (int i = 1; i < tot; i++)
	{
		for (int j = 1; j < tot; j++)
		{
			if (i & j) continue;
			for (int k = 1; k < tot; k++)
			{
				if (i & k) continue;
				if (j & k) continue;
				ans = min(ans, abs(a[i] - A) + abs(a[j] - B) + abs(a[k] - C) + (cnt[i] + cnt[j] + cnt[k] - 3) * 10);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1152
//frame.cpp
#include<iostream>
using namespace std;

int main()
{
    int h,w,flag,i,j;
    flag=0;
    while (flag==0)
    {
        cin>>h>>w;
        if (h==0 && w==0)
        {
            flag=1;
        }
        else
        {
            for ( i = 0; i < h; i++)
            {
                for ( j = 0; j < w; j++) 
                {
                    if (i==0 || i==h-1 || j==0 || j==w-1) cout<<"#";
                    else cout<<".";
                }
                cout<<endl;
            }
            cout<<endl;
        }
    }
}


Measured memory_bytes: 3092
#include <stdio.h>
#include <math.h>


int main(void){
  
  int i, j;
  for(i = 1; i < 10; i++){
    for(j = 1; j < 10; j++){
	printf("%dx%d=%d\n", i, j, i*j);

    }
  }

  return 0;
  
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
#define w(x) int x; cin>>x; while(x--)
ll int n , mod=1e9+7;
ll int dp[2001];
ll int recur(int n)
{
	if(n==0)
		return 1;
	if(dp[n]!=-1)
		return dp[n];
	ll int ans=0;
	for(int i=3;i<=n;i++)
	{
		ans+=recur(n-i);
		ans=ans%mod;
	}
	return dp[n]=ans;
}
int main()
{
	memset(dp , -1, sizeof(dp));
	dp[1]=0;
	dp[2]=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>n;
	cout<<recur(n);
}

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


void solve(long long N, long long K){
    cout << min(abs(N - K * (N / K)), abs(N - K * (N / K) - K)) << endl;
    return;
}

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


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,a,b) for(int i=(int)(a-1);i>=b;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define INF INT_MAX/3
char s[100001];

int main(){
    scanf("%s", s);
    int n = strlen(s), mini = n;
    repl(i, 1, n) if (s[i - 1] != s[i]) minch(mini, max(i, n - i));
    printf("%d\n", mini);
    return 0;
}

Measured memory_bytes: 384
import kotlin.Long as Num

const val mod=1000000007

fun modpow(n:Num,p:Num=mod-2L):Num=when {
	p==0L->1L
	p%2==1L->n*modpow(n,p-1)%mod
	else-> {
		val d=modpow(n,p/2)
		d*d%mod
	}
}

fun nCr(n:Num,r:Num):Num {
	var res=1L
	for(i in n-r+1..n) {
		res*=i
		res%=mod
	}
	for(i in 2..r) {
		res*=modpow(i)
		res%=mod
	}
	return res
}

fun main(args:Array<String>) {
	val (n,a,b)=readLine()!!.split(" ").map {it.toLong()}
	println((modpow(2,n)+mod*2-1-nCr(n,a)-nCr(n,b))%mod)
}


Measured memory_bytes: 37944
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

ll read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	ll x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=1e5+5;

int n,fa[N],ord[N],sz[N];
ll d[N],sum;
vector<int> son[N];
map<ll,int> id;

void dfs(int x,int d) {
	sum+=d;
	for(int y:son[x]) dfs(y,d+1);
}

bool cmp(int x,int y) {return d[x]<d[y];}

int main() {
	n=read();
	fo(i,1,n) d[i]=read(),ord[i]=i,sz[i]=1;
	sort(ord+1,ord+n+1,cmp);
	fo(i,1,n) id[d[ord[i]]]=i;
	fd(i,n,2) {
		int x=ord[i];
		ll s=d[x]-n+2*sz[x];
		if (!id.count(s)) {puts("-1");return 0;}
		int y=id[s];
		if (y>=i) {puts("-1");return 0;}
		fa[x]=ord[y];sz[ord[y]]+=sz[x];
		son[ord[y]].push_back(x);
	}
	dfs(ord[1],0);
	if (sum!=d[ord[1]]) {puts("-1");return 0;}
	fo(i,1,n) if (fa[i]) printf("%d %d\n",i,fa[i]);
	return 0;
}

Measured memory_bytes: 16640
"""
道路でつながっているやつが鉄道でもつながっているかどうかを調べるにはどうすればいい？
普通に木ごとのサイズを求めておけばいいのか？

道路ネットワークを根ごとにグルーピングする。その中で、さらに鉄道の根ごとにグルーピングする。
でchooseでペア数を求めれば良い。

"""
import math
import sys
sys.setrecursionlimit(200000)
class UnionFind():
    def __init__(self,n):
        self.parents = [i for i in range(n+1)]

    def find(self,x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self,x,y):
        self.parents[self.find(y)]=self.find(x)

N,K,L = map(int,input().split())
A = UnionFind(N)
B = UnionFind(N)
for i in range(K):
    p,q = map(int,input().split())
    A.union(p,q)

for i in range(L):
    r,s = map(int,input().split())
    B.union(r,s)


group = {}
for i in range(1,N+1):
    roadRoot = A.find(i)
    if roadRoot not in group:
        group[roadRoot] = {}
    railRoot = B.find(i)
    if railRoot not in group[roadRoot]:
        group[roadRoot][railRoot] = []
    group[roadRoot][railRoot].append(i)

ans = [[]for _ in range(N)]
for i in group.items():
    for j in i[1].values():
        for k in j:
            ans[k-1] = str(len(j))

ans = " ".join(ans)
print(ans)


Measured memory_bytes: 124752
import math

while True:
    n = int(input())
    if n == 0:
        break
    s = list(map(int, input().split()))

    m = sum(s) / n
    a = 0
    for i in range(n):
        a += (s[i] - m) ** 2
    a = math.sqrt(a / n)
    print("{:5f}".format(a))



Measured memory_bytes: 5704
import java.util.*;
public class Main
{
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		long n = s.nextLong();
		long t;
		t=((n/500)*1000);
		t+=(((n%500)/5)*5);
		System.out.println(""+t);
	}
}


Measured memory_bytes: 23764
n, y = map(int,input().split())
ans10000 = 0
ans5000 = 0
ans1000 =0

for i_a in range(n+1):
    for i_b in range(n+1-i_a):
        i_c = n - i_a -i_b
        total = 10000*i_a + 5000*i_b + 1000*i_c
        if total == y:
            ans10000 = i_a
            ans5000 = i_b
            ans1000 = i_c
if ans10000==0 and ans5000==0 and ans1000==0:
    ans10000 = -1
    ans5000 = -1
    ans1000 = -1

print(ans10000, ans5000, ans1000)


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


Measured memory_bytes: 512
// Why am I so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = (int)2e5 + 5;

int cl[MAXN], cr[MAXN];

int arr[MAXN];

int st[MAXN];

int n, sz;

ll ans;

void solve() {                   
	scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
    	scanf("%d", &arr[i]);
    }

    sz = 0;

    for (int i = 1; i <= n; ++i) {
		while (sz > 0 && arr[st[sz]] > arr[i]) {
			--sz;
		}

		cl[i] = (sz == 0 ? 1 : st[sz] + 1);
		st[++sz] = i;
	}

	sz = 0;

    for (int i = n; i > 0; --i) {
		while (sz > 0 && arr[st[sz]] > arr[i]) {
			--sz;
		}

		cr[i] = (sz == 0 ? n : st[sz] - 1);
		st[++sz] = i;
	}                               

	for (int i = 1; i <= n; ++i) {
		ans += arr[i] * (i - cl[i] + 1ll) * (cr[i] - i + 1ll);
	}

	printf("%lld\n", ans);
}

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 3328
use io::*;
use std::*;

fn solve(S: i64, W: i64) {
    if (S > W) {
        println!("safe");
    } else {
        println!("unsafe");
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
fn main() {
    let con = read_string();
    let mut scanner = Scanner::new(&con);
    let mut S: i64;
    S = scanner.next();
    let mut W: i64;
    W = scanner.next();
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(move || solve(S, W)).unwrap().join().unwrap();
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


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

using namespace std;

int main()
{
	map<char,string>P;

	P[32]="101";
	P[39]="000000";
	P[44]="000011";
	P[45]="10010001";
	P[46]="010001";
	P[63]="000001";
	P[65]="100101";//A
	P[66]="10011010";
	P[67]="0101";
	P[68]="0001";
	P[69]="110";
	P[70]="01001";
	P[71]="10011011";
	P[72]="010000";
	P[73]="0111";
	P[74]="10011000";
	P[75]="0110";
	P[76]="00100";
	P[77]="10011001";
	P[78]="10011110";
	P[79]="00101";
	P[80]="111";
	P[81]="10011111";
	P[82]="1000";
	P[83]="00110";
	P[84]="00111";
	P[85]="10011100";
	P[86]="10011101";
	P[87]="000010";
	P[88]="10010010";
	P[89]="10010011";
	P[90]="10010000";

	map<string,string>PP;
	PP["00000"]='A';
	PP["00001"]='B';
	PP["00010"]='C';
	PP["00011"]='D';
	PP["00100"]='E';
	PP["00101"]='F';
	PP["00110"]='G';
	PP["00111"]='H';
	PP["01000"]='I';
	PP["01001"]='J';
	PP["01010"]='K';
	PP["01011"]='L';
	PP["01100"]='M';
	PP["01101"]='N';
	PP["01110"]='O';
	PP["01111"]='P';
	PP["10000"]='Q';
	PP["10001"]='R';
	PP["10010"]='S';
	PP["10011"]='T';
	PP["10100"]='U';
	PP["10101"]='V';
	PP["10110"]='W';
	PP["10111"]='X';
	PP["11000"]='Y';
	PP["11001"]='Z';
	PP["11010"]=' ';
	PP["11011"]='.';
	PP["11100"]=',';
	PP["11101"]='-';
	PP["11110"]="'";
	PP["11111"]='?';

	string str;
	while(getline(cin,str))
	{
		int count=0;
		string set_str;
		string keep;
		string ans_str;

		for(int i=0;i<str.length();i++)
		{
			set_str += P[str[i]];
		}

		while(set_str.length()%5)set_str+='0';

		for(int i=0;i<set_str.length();i++)
		{
			ans_str += set_str[i];
			count++;
			if(!(count%5) && count)
			{
				cout << PP[ans_str];
				ans_str.erase(ans_str.begin(),ans_str.end());
			}
		}
		cout << endl;
	}
	
	return 0;
}

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

#define MAX 10001

int n,q;
int p[MAX] = {}, r[MAX] = {};

void makeSet(int x){
	p[x] = x;
}

void link(int x,int y){
	if(r[x] > r[y]){
		p[y] = x;
	}
	else{
		p[x] = y;
		if(r[x] == r[y]){
			r[y]++;
		}
	}
}

int findSet(int x){
	if(x != p[x]){
		p[x] = findSet(findSet(p[x]));
	}
	return p[x];
}

void uni(int x,int y){
	link(findSet(x), findSet(y));
}

int same(int x,int y){
	if(findSet(x) == findSet(y)){
		return 1;
	}
	else{
		return 0;
	}
}

int main(){
	cin >> n >> q;
	for(int i = 0;i < n;i++){
		makeSet(i);
	}

	int a,b,c;
	for(int i = 0;i < q;i++){
		cin >> a >> b >> c;
		if(a == 0){
			uni(b,c);
		}
		else if(a == 1){
			cout << same(b,c) << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3180
Main(function(input) {
	input = input.trim().split('\n');
	input.shift();
	input.forEach(function(line) {
		var tmp = line.split(' ');
		var k = tmp[0];
		var p = tmp[1];
		console.log(k % p || p);
	});
});

function Main(main) {
	var input = '';

	process.stdin.resume();
	process.stdin.setEncoding('utf8');
	process.stdin.on('data', function(chunk) {
		input += chunk;
	});
	process.stdin.on('end', function() {
		main(input);
	});
};

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

int main()
{
	string s;
	cin >> s;
	long long ans=0,len=(int)s.size()-1;
	
	for(int i=0;i<(1<<len);++i)
	{
		long long sum=s[0]-'0';
		for(int j=0;j<len;++j)
		{
			if(i & (1<<j))
			{
				ans+=sum;
				sum=0;
			}
			sum=sum*10+s[j+1]-'0';
		}
		ans+=sum;
	}
	cout << ans << endl;
}

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

int main() {
  int x, y;
  cin >> x >> y;
  for (int i = 0; i <= x; i++){
    int kame = x -i;
    int leg = i*2+kame*4;
    if (leg == y) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3612