akhauriyash/Code-Regression huggingface dataset:
class Ant
	def initialize(*args)
		@index, @dx, @x = args
	end
	attr_accessor :index, :dx, :x, :time
end

loop {
	n, l = gets.split.map &:to_i
	break if n == 0
	ants = (1..n).map {|i|
		dir, x = gets.chomp.split 
		Ant.new(i, {?R=>1, ?L=>-1}[dir], x.to_i)
	}

	events = []
	ants.combination(2){|a1, a2|
		next if a1.dx == a2.dx || 
				(a1.x + a2.x).odd? ||
				(a1.dx > 0) ^ (a1.x < a2.x)
		events << [a1.index, a2.index, (a2.x - a1.x).abs / 2]
	}
	ants.each{|a| a.time = (a.dx > 0 ? l - a.x : a.x)}

	events.sort_by(&:last).each{|i, j, _|
		a1 = ants[i-1]
		a2 = ants[j-1]
		a1.index, a2.index = a2.index, a1.index
	}

	last = ants.max_by{|a| [a.time, -a.dx]}
	puts "#{last.time} #{last.index}"
}

Measured memory_bytes: 6120
using System;
using System.Linq;
using System.Collections.Generic;

namespace Aizu
{
    class OnlineJudge
    {
        public static void Main()
        {
            for(int i; (i = int.Parse(Console.ReadLine())) != 0;) {
                var d = new Dictionary<string, int>();
                while(i-- > 0) {
                    Array.ForEach(Console.ReadLine().Split(), q => d[q] = 1 + (d.ContainsKey(q) ? d[q] : 0));
                }
                var k = Console.ReadLine()[0];
                var c = d.Where(q => q.Key[0] == k).OrderByDescending(q => d[q.Key]).ThenBy(q => q.Key).Select(q => q.Key).Take(5).ToArray();
                Console.WriteLine(c.Length == 0 ? "NA" : String.Join(" ", c));
            }
        }
    }
}

Measured memory_bytes: 7280
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define FOR(i, r, n) for (int i=(int)(r); i<=(int)(n); i++)
#define all(v) v.begin(), v.end()
#define INF 2147483647
#define INF64 9223372036854775807
#define MOD 1000000007

struct UnionFind {

    vector<int> ne, nesz;

    void set(int n){

        rep(i, n+1){
            ne.push_back(i);
            nesz.push_back(1);
        }

    }

    int rt(int a){

        if(ne[a]==a) return a;
        else{
            int x=rt(ne[a]);
            ne[a]=x;
            return x;
        }

    }

    void cn(int a, int b){

        a=rt(a);
        b=rt(b);

        if(a==b) return;

        nesz[b]+=nesz[a];
        ne[a]=b;
    
        return;

    }

    bool ch(int a, int b){

        if(rt(a)==rt(b)) return true;
        else return false;

    }

    int size(int a){

        a=rt(a);
        return nesz[a];

    }

};

/*

union find

structの変数をufとして

uf.set  :ufの頂点数を設定
uf.rt   :aの根を調べる
uf.cn   :aとbのを連結する
un.ch   :aとbがつながっているか調べる
uf.size :aの根の大きさを調べる

O(logN)

rankは未実装

*/

int main(){

    int n, m, k; cin>>n>>m>>k;

    vector<vector<int>> ng(n+1, vector<int>(0));

    UnionFind uf;
    uf.set(n);

    rep(i, m){
        int a, b; cin>>a>>b;
        uf.cn(a, b);
        ng[a].push_back(b);
        ng[b].push_back(a);
    }

    rep(i, k){
        int a, b; cin>>a>>b;
        if(uf.ch(a, b)){
            ng[a].push_back(b);
            ng[b].push_back(a);
        }
    }

    FOR(i, 1, n){

        int ans=uf.size(i);
        ans-=ng[i].size()+1;

        cout<<ans<<" ";

    }

    cout<<endl;

}

Measured memory_bytes: 11656
s=input().split()
n,m=int(s[0]),int(s[1])
l=[[] for i in range(100001)]
d=[{} for i in range(100001)]
input_memo=[]
for i in range(m):
    s=input().split()
    p,y=int(s[0]),int(s[1])
    input_memo.append((p,y))
    l[p].append(y)
for i in range(100001):
    l[i].sort()
for i in range(100001):
    cnt=1
    for j in l[i]:
        d[i][j]=cnt
        cnt+=1
for (p,y) in input_memo:
    print(str(p).zfill(6)+str(d[p][y]).zfill(6))

Measured memory_bytes: 95408
#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

int main(){
  cin.sync_with_stdio(false);
  int n;
  cin >> n;
  int mini = INF, a;
  rep(i, n) {
    cin >> a;
    int j = 0;
    while(a % 2 == 0) a /= 2, j++;
      minch(mini, j);
  }
  cout << mini << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define zy -2147382637
#define bql 2147483647
#define ll long long
#define ull unsigned long long
#define ld long double
#define il inline
#define sz(x) x.size()
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define maxn 100010
#define rp(i, l, r) for (int i = l; i <= r; i++)
#define rb(i, r, l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a<b)return a;else return b;}
ll lowbit(ll x){return x&(-x);}
ll prime(ll x){
   if(x<=1)return false;
   for(int i=2;i<=int(sqrt(x));i++){
	   if(x%i==0)return false;
   }return true;
}
ll gcd(ll a,ll b){ll r;while(b>0){r=a%b;a=b;b=r;}return a;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll read() {
	char c = getchar(); ll w = 1; ll x = 0;
	while (!isdigit(c))
		(c == '-') && (w = -w), c = getchar();
	while (isdigit(c))
		x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
	x *= w;
}
const int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1},
		  dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int main(){
	fast;
	ll n;
	cin>>n;
	cout<<n*n*n<<endl;
	return 0;
}/*『你强归你强，我永不示弱』*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
 
typedef long long int ll;
typedef pair<int, int> P;
 
const long long INF = 3e18 + 12;
const int inf = 1e9;
 
int main() {
  string a;
  cin >> a;
  int sum = 0;
  rep(i, 3) {
    if (a[i] == '1') {
      sum++;
    }
  }
  cout << sum << endl;
 
  return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  F
//
//  Created by 曾憲揚 on 2020/8/12.
//  Copyright © 2020 曾憲揚. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int a[maxn];
vector<int> e[maxn];
int dp[maxn];
int ans[maxn];

int bs(int l, int r, int t){
    if(r<l) return l;
    if(dp[r] < t) return r+1;
    
    while(r > l){
        int m = (l+r)/2;
        if(dp[m] < t) l=m+1;
        else r = m;
    }
    return r;
}

void dfs(int p, int cur, int r){
    int pos = bs(0, r, a[cur]);
    int reg = dp[pos];
    dp[pos] = a[cur];
    
    if(pos == r+1) ans[cur] = (++r) + 1;
    else           ans[cur] = r+1;
    for(int i: e[cur]){
        if(i!=p) dfs(cur, i, r);
    }
    dp[pos] = reg;
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
   
    int n; cin >> n;
    fill(dp, dp+n+1, 2e9);
    
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=1; i<n ; i++){
        int u, v; cin >> u >> v;
        u--; v--;
        e[u].push_back(v); e[v].push_back(u);
    }
    dfs(0, 0, -1);
    for(int i=0; i<n; i++){
        cout << ans[i] << endl;
    }
    return 0;
}


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

int main() {
	long long a, b, k;
	cin >> a >> b >> k;
    if (k <= a)
      cout << a-k << " " << b << endl;
    else if (k <= a + b)
      cout << 0 << " " << b - (k - a) << endl;
    else
      cout << 0 << " " << 0 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  for(int i = 0;i < s.size();i++){
    if(i == s.size()-1)cout << -1 << " " << -1 << endl;
    else if(s[i] == s[i+1]){
      cout << i+1 << " " << i+2 << endl;
      break;
    }else if(i < s.size()-1 && s[i] == s[i+2]){
      cout << i+1 << " " << i+3 << endl;
      break;
    }
  }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
   ll  n,W;
    cin>>n>>W;
    pair<ll,ll> *arr=new pair<ll,ll>[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i].first>>arr[i].second;
    }
    ll **dp=new ll*[2];
    for(int i=0;i<2;i++)
    {
        dp[i]=new ll[W+1]();
    }
    ll temp=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {dp[temp][j]=dp[temp^1][j];
          if(j>=arr[i-1].first)
              dp[temp][j]=max(dp[temp^1][j],dp[temp^1][j-arr[i-1].first]+arr[i-1].second);
        }
        temp^=1;
    }
    cout<<dp[temp^1][W]<<endl;
}

Measured memory_bytes: 5064
import sys

def insertionSort(A, N):
    print(' '.join(map(str, A)))
    for i in range(1, N):
        v = A[i]
        j = i-1

        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j-=1
        A[j+1] = v
        print(' '.join(map(str, A)))

N = int(input())
A = list(map(int, input().split()))

insertionSort(A, N)



Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define ld long double
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
const int inf=1e9+7;

int main()
{
	ll n,k;
	cin>>n>>k;
	ll a[n];
	vector<bool> dp(k+1,0);
	loop(i,0,n)
	{
		cin>>a[i];
	}
	loop(i,1,k+1)
	{
		loop(j,0,n)
		{
			if(i-a[j]>=0 && dp[i-a[j]]==0 ) 
			{
				dp[i]=1;
				break;
			}
		}
	}
	(dp[k])?cout<<"First":cout<<"Second";
	return 0;
}




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

#define rep(i, n) for(int i=0; i < n; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll=long long;

int main() {
  int n,d;
  cin >> n >> d;
  int ans = n/(2*d+1);
  if (n%(2*d+1)) ans+=1;

  cout << ans;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int S = sc.nextInt();
        int W = sc.nextInt();

        System.out.println(solve(S, W));

        sc.close();
    }

    static String solve(int S, int W) {
        return (S > W) ? "safe" : "unsafe";
    }
}

Measured memory_bytes: 35660
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;

int main(){
  long long N;
  cin >> N;
  vector<long long> A(N-1);
  vector<long long> sub(N,0);
  for(long long i=0;i<N-1;i++){
    cin >> A.at(i);
    sub.at(A.at(i)-1)++;
  }

  for(long long i=0;i<N;i++){
    cout << sub.at(i) <<endl;
  }
  
  return 0;
}


Measured memory_bytes: 6364
#include<iostream>
#include<algorithm>
#include <list>
#include <numeric>
#include<vector>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

using namespace std;

int main(void) {
 long long int n, m, tmp1, tmp2, ans=0,ind;
 cin >> n >> m;
 long long int a[n], b[m], c[n], d[n];
 fill(d, d+n, -1);
 for(long long int i=0;i<n;i++) { cin >> a[i]; }
 sort(a, a+n);
 vector<pair<int,int> > p;
 
  for(long long int i=0;i<m;i++) {
    cin >> tmp1 >> tmp2;
    p.push_back({tmp2, tmp1});
  }
  sort(p.begin(), p.end());
  ind=0;
  for(int i=m-1;i>=0;i--) {
    tmp1 = p[i].second; tmp2 = p[i].first;
    for(long long int j=0;j<tmp1;j++) {
     if(ind==n) break;
     d[ind++]=tmp2;
   }
   if(ind==n) break;
  }
  
  for(long long int i=0;i<n;i++) { ans+= max(a[i], d[i]); }
  cout << ans << endl;
}

Measured memory_bytes: 2936
#include<iostream>
#include<string>
#include<map>
#include<string.h>
#include<vector>
#include<set>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define pb push_back
ll k,m;
vector<ll> mp;
int main()
{
	ll n,a[10001];
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n;i++)
	{
		k=0;
		while(a[i]%2==0)
		{
			k++;
			a[i]/=2;
		}
		mp.pb(k);
	}
	for(int i=0;i<mp.size();i++)
	{
		m+=mp[i];
	}
	cout<<m<<endl;		
	//system("pause");
	return 0;
}

Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main()
{
	int n, c0 = 0, c1 = 0, c2 = 0, c3 = 0;
	string cur;

	cin >> n;

	while(n--)
	{
		cin >> cur;

		if (cur == "AC")
			c0++;
		else if (cur == "WA")
			c1++;
		else if (cur == "TLE")
			c2++;
		else
			c3++;
	}

	cout << "AC x " << c0 << endl
		 << "WA x " << c1 << endl
		 << "TLE x " << c2 << endl
		 << "RE x " << c3 << endl;

	return 0;
}


Measured memory_bytes: 3240
#include<cstdio>
unsigned prime[238] = {2, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499};
unsigned count[4], mod_five[4][55];

int main(){
    unsigned N;
    scanf("%u", &N);
    for (size_t i = 0; i < N<<2; i++){
        unsigned r = prime[i]%5-1;
        mod_five[r][count[r]++] = prime[i];
        if(count[r] == N){
            for (size_t j = 0; j < N; j++){
                if(j) printf(" ");
                printf("%u", mod_five[r][j]);
            }
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 1684
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
using namespace std;
int main()
{

	//int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	long long a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, i = 0, j = 0, k = 0, l = 0, ans = 0;
	//cout << LONG_MAX << endl;
	//string s[1001];
	//long long n, A[1000000000];
	long long n, m;
	long long  z[100000];
//	cin >> n;

	//cin >> a;
	//cin >> b;
	//cin >> c;
	//cin >> d;
	//m = 0;
	int A[4];
	cin >> A[0];
	cin >> A[1];
	cin >> A[2];
	sort(A, A + 3);

	//std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	cout << abs(A[0] - A[1]) + abs(A[2] - A[1])  << endl;

	return 0;
}

Measured memory_bytes: 256
/*

  _|_|                              _|  _|    _|
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|
_|    _|  _|_|          _|          _|  _|_|
_|    _|  _|          _|      _|    _|  _|  _|
  _|_|    _|        _|_|_|_|    _|_|    _|    _|

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
const int maxn=4e5+1000;
const int inf=1e9+100;
using namespace std;
vi E[maxn],inset[maxn];
int s=2e5+1,t=2e5+2,cnt=1,head[maxn];
struct gg{
    int u,v,w,next;
}side[maxn*2];
void ins(int u,int v,int w) {
    side[++cnt]=(gg){u,v,w,head[u]};head[u]=cnt;
    side[++cnt]=(gg){v,u,0,head[v]};head[v]=cnt;
}
int rk[maxn],cur[maxn];
queue<int>q;
bool bfs() {
    memset(rk,0,sizeof(rk));rk[s]=1;
    while(!q.empty())q.pop();q.push(s);
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=side[i].next) {
            int v=side[i].v;if(rk[v]||!side[i].w)continue;
            rk[v]=rk[u]+1;
            q.push(v);
        }
    }
    if(!rk[t])return 0;
    return 1;
}
int dfs(int u,int flow) {
    if(u==t||!flow)return flow;
    int tot=0;
    for(int &i=cur[u];i;i=side[i].next) {
        int v=side[i].v;//cout<<v<<' '<<rk[v]<<endl;
        if(rk[v]!=rk[u]+1||!side[i].w)continue;
        int sent=dfs(v,min(flow,side[i].w));
        side[i].w-=sent;side[i^1].w+=sent;
        flow-=sent;tot+=sent;
    }
    return tot;
}
int dinic(){
    int maxflow=0;
    while(bfs()){
        memcpy(cur,head,sizeof(cur));
        maxflow+=dfs(s,inf);
    }
    return maxflow;
}
int match[maxn];//match[set_id]=match_point_id
bool inq[maxn];
pii ans[maxn];
int main(){
    //ios::sync_with_stdio(0);
    int n;scanf("%d",&n);//cin>>n;
    rep(i,1,n-1) {
        int c;scanf("%d",&c);//cin>>c;
        rep(j,1,c) {
            int u;scanf("%d",&u);//cin>>u;
            E[i].pb(u);inset[u].pb(i);
            ins(u,n+i,1);
        }
    }
    rep(i,2,n)ins(s,i,1);
    rep(i,1,n-1)ins(n+i,t,1);
    int flow=dinic();
    if(flow!=n-1) {
        printf("-1\n");//cout<<"-1";
        return 0;
    }
    rep(i,n+1,n+n-1) {
        for(int j=head[i];j;j=side[j].next) {
            int v=side[j].v;
            if(v<=n&&side[j].w) {
                match[i-n]=v;break;
            }
        }
    }
    while(!q.empty())q.pop();
    int tot=1;q.push(1);inq[1]=1;
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=0;i<inset[u].size();i++) {
            int setid=inset[u][i],set_match=match[setid];
            if(!inq[set_match]) {
                inq[set_match]=1;ans[setid]=mk(u,set_match);
                q.push(set_match);tot++;
            }
        }
    }
    if(tot!=n) {
        printf("-1\n");//cout<<"-1";
        return 0;
    }
    for(int i=1;i<n;i++) {
        printf("%d %d\n",ans[i].fi,ans[i].se);
        //cout<<ans[i].fi<<' '<<ans[i].se<<endl;
    }
    return 0;
}


Measured memory_bytes: 52840
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define gcd __gcd
#define lcm(n, m) n * m / gcd(n, m)
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define so(n) sort(n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数

int main() {
  int N, b = 0;
  ci(N);
  ve<dl> v(N);
  rep(i, N){
    ci(v.at(i));
  }
  so(v);
  dl a = v.at(0);
  repi(i, 1, N){
    a = (a + v.at(i)) / 2.0;
  }
  sp(9);
  co(a);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct P
{
	int a, v;
	
	bool operator<(const P &t)const{
		if (v == t.v) return a > t.a;
		return v < t.v;
	}
};

int n;
P dat[10000000];

void update(int i, int x)
{
	i += n - 1;
	dat[i].v += x;
	while (i > 0){
		i = (i - 1) / 2;
		dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
	}
}

int main()
{
	int q;
	scanf("%d %d", &n, &q);
	
	for (int i = 1;; i *= 2){
		if (n <= i){
			n = i;
			break;
		}
	}
	for (int i = 0; i < n; i++){
		dat[i + n - 1].a = i;
	}
	
	for (int i = 0; i < q; i++){
		int a, v;
		scanf("%d %d", &a, &v);
		a--;
		update(a, v);
		printf("%d %d\n", dat[0].a + 1, dat[0].v);
	}
	
	return 0;
}

Measured memory_bytes: 19544
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
      	sc.close();
      	int n = 0;
      	for (int i=0; i<3; i++) {
          if (s.substring(i,i+1).equals("1")) {
            n++;
          }
        }
          System.out.println(n);
	}
}

Measured memory_bytes: 35636
#include <stdio.h>

#define MAX 40
int pre[MAX] ={0};
int in[MAX] = {0};
int cnt = 0;
int n;

int next(int A[]) {
	int ret;
	ret = A[cnt];
	++cnt;
	return ret;
}

int in_find(int c) {
	int i = 0;
	while (in[i] != c) {
		++i;
	}
	return i;
}

void reconstruction(int l, int r) {
	int c, m;
	
	if (l >= r) return;
	c = next(pre);
	m = in_find(c);

	reconstruction(l, m);
	reconstruction(m + 1, r);
	if (c != pre[0]) {
		printf("%d ", c);
	} else {
		printf("%d\n", c);
	}
	return;
}

int main(void) {
	int i;

	scanf("%d", &n);

	for (i = 0; i < n; ++i) {
		scanf(" %d", &pre[i]);
	}

	for (i = 0; i < n; ++i) {
		scanf(" %d", &in[i]);
	}

	reconstruction(0, n);
//	printf("\n");
	return 0;	
}

Measured memory_bytes: 2768
def main():
    N, K = map(int, input().split())
    S = input()
    lz = []
    lo = []
    o = z = 0
    for i in S:
        if i == '1':
            o += 1
            if z > 0:
                lz.append(z)
                z = 0
        else:
            z += 1
            if o > 0:
                lo.append(o)
                o = 0
    lo.append(o)
    if z > 0:
        lz.append(z)
    if len(lz) <= K:
        return N
    if S[0] == '1':
        lz[0] += lo[0]
        lo = lo[1:]
    lo.append(0)
    m = t = sum(lz[:K]) + sum(lo[:K])
    for i in range(len(lz) - K):
        if i == 0:
            t -= lz[i]
        else:
            t -= (lz[i] + lo[i-1])
        t += (lz[i + K] + lo[i + K])
        m = max(m, t)
    return m
print(main())


Measured memory_bytes: 45424
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;

int main()
{
  ll n,k;
  cin>>n>>k;
  ll a[n]={0},b[n];
  n++;
  for(int i=1;i<=n;i++)
  {
    a[i] = i;
    a[i] = a[i-1]+a[i];
  }

  // for(int i=0;i<=n;i++)
  //   cout<<a[i]<<" ";
  // cout<<endl;
  ll res = 0;
    for(int i=k;i<=n;i++)
    {
      res += a[n] - a[n-i] - a[i] +1;
      res %= mod;
    }
    cout<<res;


  return 0;
}


Measured memory_bytes: 5188
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int n, k;
    cin >> n >> k;
    vint a(n);
    rep(i, n) cin >> a[i];
    map<int, int> mp;
    rep(i, n) mp[a[i]]++;
    vector<pair<int, int>> ls;
    for (auto x : mp) {
        ls.emplace_back(x.se, x.fi);
    }
    sort(all(ls));
    int ans = 0;
    rep(i, max((int)ls.size() - k, 0)) ans += ls[i].fi;

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

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

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define FOR(i,m,n) for(int i=(m) ; i<(n) ; i++)
#define FORR(i,m,n) for(int i=(m) ; i>=(n) ; i--)

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

typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

int main(){
   int n,k;cin >> n >> k;
   string s;cin >>s;
   vector<int> sum;

   int now = 1;
   int cnt = 0;
   for(int i=0;i<n;i++){
      if(s[i] == (char)(now + '0')){
         cnt++;
      }else{
         sum.push_back(cnt);
         cnt = 1;
         now = 1 - now;
      }
   }
   if(cnt != 0)sum.push_back(cnt);
   if(sum.size() % 2 == 0)sum.push_back(0);
   
   int left = 0,right = 0;
   int ans = 0;
   int tmp = 0;
   for(int i=0;i<sum.size();i+=2){
      int nextLeft = i;
      int nextRight = min(i+2*k+1,(int)sum.size());
      while(nextLeft > left){
         tmp -= sum[left];
         left++;
      }
      while(nextRight > right){
         tmp += sum[right];
         right++;
      }
      ans = max(ans,tmp);
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 1020
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int dij[] = {0, 1, 0, -1, 0};
int main() {
    int h, w, n; cin >> h >> w >> n;
    vector<string> grid(h);
    for (string &s: grid) cin >> s;
    int si, sj;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        if (grid[i][j] == 'S') si = i, sj = j;
    }
    int gi, gj;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        if (grid[i][j] == '0' + n) gi = i, gj = j;
    }
    using vvi = vector<vector<int>>;
    vector<vvi> dp(n + 1, vvi(h, vector<int>(w, -1)));
    queue<tuple<int, int, int>> que;
    dp[0][si][sj] = 0; que.emplace(0, si, sj);
    while (!que.empty()) {
        int d, i, j;
        tie(d, i, j) = que.front(); que.pop();
        for (int k = 0; k < 4; k++) {
            int ni = i + dij[k];
            int nj = j + dij[k + 1];
            if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
            if (grid[ni][nj] == 'X') continue;
            int nd = d + (grid[ni][nj] == '0' + d + 1);
            if (~dp[nd][ni][nj]) continue;
            dp[nd][ni][nj] = dp[d][i][j] + 1;
            que.emplace(nd, ni, nj);
        }
    }
    cout << dp[n][gi][gj] << endl;
    return 0;
}


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

int main(){
    int N;
    string S;
    int total = 0;

    cin >> N >> S;

    for (size_t i = 1; i < N; i++)
    {
        if(S.at(i) == S.at(i-1)){
            total++;
        }
    }

    cout << N - total;
    
}

Measured memory_bytes: 512
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
k=N()
s=input()
if len(s)<=k:
    print(s)
else:
    print(s[:k]+"...")

Measured memory_bytes: 61892
h, w = map(int, input().split())
grid = [0]*h
for i in range(h):
  grid[i] = input()

counter = [[[0, 0] for j in range(w)] for i in range(h)]
ans = 0
for i in range(h):
  for j in range(w):
    if grid[i][j] == "#":
      continue
    if i == 0 or (i != 0 and grid[i-1][j] == "#"):
      k = 0
      while i+k < h and grid[i+k][j] == ".":
        k += 1
      counter[i][j][0] = k-1
    else:
      counter[i][j][0] = counter[i-1][j][0]
    if j == 0 or (j != 0 and grid[i][j-1] == "#"):
      k = 0
      while j+k < w and grid[i][j+k] == ".":
        k += 1
      counter[i][j][1] = k-1
    else:
      counter[i][j][1] = counter[i][j-1][1]
    if ans < counter[i][j][0]+counter[i][j][1]:
      ans = counter[i][j][0]+counter[i][j][1]
print(ans+1)

Measured memory_bytes: 397924
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (int i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": ";
    printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  ll N;
  cin >> N;
  vector<ll> P(N);
  rep(i, N) {
    cin >> P[i];
  }
  //printvec(P);

  vector<ll> Q(N);
  rep(i, N) {
    Q[P[i]-1] = i+1;
  }
  //printvec(Q);

  // We search the longuest continueous increasing seqneunces
  ll ans = 0;
  ll cnt = 1;
  for (int i = 0; i < N-1; ++i) {
    if (Q[i] < Q[i+1]) {
      ++cnt;
    } else {
      if (ans < cnt) { ans = cnt; }
      cnt = 1;
    }
  }
  if (ans < cnt) { ans = cnt; }

  cout << N - ans << endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> ab(n);
    vector<pair<int, int>> cd(n);
    rep(i, n) {
        int tmpx, tmpy;
        cin >> tmpx >> tmpy;
        ab[i] = make_pair(tmpx, tmpy);
    }
    rep(i, n) {
        int tmpx, tmpy;
        cin >> tmpx >> tmpy;
        cd[i] = make_pair(tmpx, tmpy);
    }
    sort(ab.begin(), ab.end());
    sort(cd.begin(), cd.end());
//    reverse(ab.begin(), ab.end());
//    reverse(cd.begin(), cd.end());
//    printf("\n");
//    rep(i, n ) cout << ab[i].first << " " << ab[i].second << endl;
//    printf("\n");
//    rep(i, n ) cout << cd[i].first << " " << cd[i].second << endl;
    int ans = 0;
    vector<bool> flgab(n, false);
    rep(i, n) {
        int tmp_num = 0;
        bool ok = false;
        rep(j, n) {
            if ( flgab[j] ) continue;
            if ( cd[i].first > ab[j].first && cd[i].second > ab[j].second ) {
                if ( !ok ) {
                    tmp_num = j;
                    ok = true;
                }
                else if ( ab[tmp_num].second < ab[j].second ) {
                    tmp_num = j;
                }
            }
        }
        if ( ok ) {
//            cout << cd[i].first << " " << cd[i].second << " " << ab[tmp_num].first << " " << ab[tmp_num].second << endl;
            ++ans;
            flgab[tmp_num] = true;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>//数据输入输出流
#include <cstring>//字符串操作函数
#include <cstdio>//C的输入输出
#include <cstdlib>//定义杂项函数及内存分配函数
#include <cmath>//C中的数学函数
#include <string>//c++中的string类 他不能用strcpy等c函数去操作
#include <vector>//STL vetor
#include <list>//STL list
#include <map>// STL map
#include <queue>// STL queue
#include <stack>//sTL stack
#include <bitset>//bitset可按位定义串
//比如：bitset <1000> all;定义一个1000位的串
#include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
#include <numeric>//常用数字操作 一般和algorithm搭配使用
#include <functional>//STL定义运算函数（代替运算符）
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int> PII;
#define fi first
#define se second
#define LOCAL
#define zeros(a,n) memset(a,0,(n)*sizeof(a[0]))
const int modn = 1e9+7;
int mod(int x) { return x<0?x+modn:x<modn?x:x-modn; }
//inv [ i ] = (modn - modn/i)*inv[ modn%i ] %modn;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    bool flag = true;
    while(a > 0 && c > 0){
        if(flag) c -= b;
        else a -= d;
        flag = !flag;
    }
    if(a <= 0) cout << "No\n";
    else cout << "Yes\n";
    return 0;
}



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

int main() {
	int n;
	string p;
	cin >> n >> p;
	int al = 0;
	for (int x = 0;x < n;x++) {
		string s;
		cin >> s;
		int a = s.size();
		int b = p.size();

		for (int i = 0;i <= a - b;i++) {
			for (int j = 0;j <= (a - b) / (b - 1);j++) {
				string sa;
				for (int k = 0;k < b;k++) {
					if (i + ((1 + j)*k) < a)sa.push_back(s[i + ((1 + j)*k)]);
				}
				if (sa == p) {
					al++;
					goto floop;
				}
			}
		}
		floop:;
	}
	cout << al << endl;
}

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

int n;

int main() {
#ifdef LOCAL
    freopen("xxx.in", "r", stdin);
    freopen("xxx.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll a, b;
    cin >> n;
    cin >> a >> b;
    for (int i = 1; i < n; ++i) {
        ll x, y;
        cin >> x >> y;
        ll k1 = a / x + (a % x != 0);
        ll k2 = b / y + (b % y != 0);
        a = x * max(k1, k2);
        b = y * max(k1, k2);
    }
    cout << a + b;
    return 0;
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         LLONG_MAX/3
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

struct ES {
    int from;
    int to;
    LL cost;
};

int main() {
    std::ios::sync_with_stdio(false);
    int n, m;cin >> n >> m;
    vector<ES> es;
    for(int i=0;i<m;i++){
        int a, b;LL c;cin >> a >> b >> c;
        a--;b--;
        c *= -1;
        es.push_back({a, b, c});
    }

    // shortest path
    vector<LL> d(n, INF);
    d[0] = 0;
    for(int i=0;i<n-1;i++){
        for(auto e : es){
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }

    vector<bool> neg(n);
    for(int i=0;i<n;i++){
        for(auto e : es){
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                neg[e.to] = true;
            }
            if(neg[e.from]) neg[e.to] = true;
        }
    }

    if(neg[n-1]){
        cout << "inf" << endl;
    }else{
        cout << -d[n-1] << endl;
    }

    return 0;
}


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

class Proc{
	string name;
	int time;
public:
	Proc(string n, int t) : name(n), time(t){}
	Proc() : name(""), time(0){}
	int execute(int q){return time -= q;};
	string get_name(){return name;};
	int get_time(){return time;};
};
int main(){
	int n, q;
	cin >> n >> q;
	Proc queue[n];
	string name;
	int time;
	for (int i = 0; i < n; i ++){
		cin >> name >> time;
		queue[i] = Proc(name, time);
	}
	int i = 0, last = 0, now_time = 0, size = n, temp = 0;
	while (size > 0){
		now_time += q;
		temp = queue[i].execute(q);
		if (temp <= 0){
			now_time += temp;
			cout << queue[i].get_name() << " " << now_time << "\n";
			size -= 1;
			i = (i + 1) % n;
		}else{
			queue[last] = queue[i];
			i = (i + 1) % n;
			last = (last + 1) % n;
		}
	}
}

Measured memory_bytes: 4336
#include <cmath>
#include<iostream>
#include <functional>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <iomanip>
using namespace std;
 
int main(){    
  int N,K,count=0;
  cin >> N >> K;
  int h;

  for(int i=0;i<N;i++){
    cin >> h;
    if(h >= K){
      count++;
    }
  }
  
  cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i = 0;i < n;i++)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()

template<class T> bool chmax(T& a,T b){ if(a < b){ a = b; return true; }else return false; }
template<class T> bool chmin(T& a,T b){ if(a > b){ a = b; return true; }else return false; }
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;
using vpi = vector<Pi>;
using vpl = vector<Pl>;
 
#define debug(arr) cout << #arr << " = " << arr << '\n'
#define debug2(a,b) cout << "[" << #a << "," << #b << "] = " << "[" << a << "," << b << "]" << '\n'
template<class T> ostream &operator << (ostream& out, const vector<T>& arr) {
	cout << "{"; for (int i = 0; i < arr.size(); i++)cout << (!i ? "" : ", ") << arr[i]; cout << "}";
	return out;
}
template<class T> ostream &operator << (ostream& out, const vector<vector<T> >& arr) {
	cout << "{\n"; for (auto& vec : arr)cout << "  " << vec << ",\n"; cout << "}";
	return out;
}
template<class S,class T> ostream &operator << (ostream& out, const pair<S,T>& p){
  cout << "{" << p.first << "," << p.second << "}" << '\n';
  return out;
}
template<class T> istream &operator >> (istream& in, vector<T>& arr) {
	for (auto& i : arr)cin >> i; return in;
}

/////////////////////////////////////////////////////////////////////////

int main(int argc, char const* argv[])
{
  int d,s,t;cin >> d >> s >> t;
  if (s * t >= d) {
    cout << "Yes" << '\n';
  }else{
    cout << "No" << '\n';
  }
  return 0;
}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int fact(int n) {
    if (n == 0) return 0;
    int ans = 1;
    rep1r(i, n) ans *= i;
    return ans;
}

int main(){
    int n;
    cin >> n;
    vi p(n), q(n);
    rep(i, n) cin >> p[i];
    rep(i, n) cin >> q[i];
    int a = 0, b = 0;
    set<int> up, uq;
    rep(i, n) {
        int uNum = p[i] - 1;
        int uTmpNum = uNum;
        rep1(j, uTmpNum) {
            if (up.find(j)!=up.end()) --uNum;
        }
        a += uNum * fact((n-1)-i);
        up.insert(p[i]);
    }
    rep(i, n) {
        int uNum = q[i] - 1;
        int uTmpNum = uNum;
        rep1(j, uTmpNum) {
            if (uq.find(j)!=uq.end()) --uNum;
        }
        b += uNum * fact((n-1)-i);
        uq.insert(q[i]);
    }
    cout << abs(a-b) << endl;
    return 0;
}


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

fact = [0] * (N+1)
inv = [0] * (N+1)

fact[0] = fact[1]  = 1
inv[1] = 1

for i in range(2, N+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD # //で良いのかな?

def main():
    if N == 1:
        print(M)
        return 
    num = M
    nums = [M]
    for i in reversed(range(1,N)):
        num *= i*(M-1)
        num *= inv[N-i]
        num %= MOD
        nums.append(num)
    nums.reverse()
    print(sum(nums[:K+1])%MOD)

    
if __name__ == "__main__":
    main()

Measured memory_bytes: 34020
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <map>
#include <numeric>

namespace test {
  std::string to_string(char val) {
    return std::string(1, val);
    // return std::string{val};
  }
}

using namespace std;

int main(void) {
  int d; cin >> d; d -= 25;
  string a = "Christmas";
  
  while(d != 0){
    a += " Eve";
    
    d++;
  }
  cout << a << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N, number, l, r;
  number = 0;
  cin >> N;
  
  for (int i = N ; i > 0 ; i--)
  {
    cin >> l >> r;
    number += r - l + 1;
  }

  cout << number << endl;
  return 0;
}

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

const int MAXN = 2e5 + 10;
const long long MOD = 1e9 + 7;

int N;
int A[MAXN];
int PREV[MAXN];
long long DP[MAXN];
int main(void){
    cin >> N;
    for(int i = 1 ; i <= N ; i++) cin >> A[i];

    DP[0] = 1;
    for(int i = 1 ; i <= N ; i++){
        DP[i] = DP[i - 1];
        if(A[i] != A[i - 1]){
            if(PREV[A[i]] != 0){
                DP[i] += DP[PREV[A[i]]];
                DP[i] %= MOD;
            }
        }
        PREV[A[i]] = i;
        //cout << DP[i] << '\n';
    }

    cout << DP[N];
    return 0;
}

Measured memory_bytes: 3328
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO ?????????????????????????????????????????????
		BufferedReader br =
				new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() );

		String[] str = br.readLine().split(" ");
		Bag[] preW = new Bag[n]; // ??´????????????????????? w_i ?????\????????????
		Bag[] postW = new Bag[n]; // ??´??????????????????????????\????????????
		for (int i=0; i < n; i++) {
			preW[i] = new Bag( Integer.parseInt(str[i]), i );
			postW[i] = preW[i];
		}

		Arrays.sort(postW);
		for (int i=0; i < n; i++) {
			postW[i].posti = i;
		}

		/*
		 * 5, 4, 1, 3, 2, : W  pre
		 *
		 *                  W[0] = 5
		 *  , 4, 1, 3, 2, : bag = 5, nextbag = 2,
		 *             5,
		 *
		 *  , 4, 1, 3, 5, : bag = 2, nextbag = 4,
		 *    2,
		 *
		 *  , 2, 1, 3, 5, : bag = 4, nextbag = 3,
		 *          4,
		 *
		 *  , 2, 1, 4, 5, : bag = 3, nextbag = 1,
		 *       3,
		 *
		 *  , 2, 3, 4, 5, : bag = 1, nextbag = 5,
		 * 1,
		 *                  bag = 5,
		 *                  bag.prei = 0
		 *
		 * 1, 2, 3, 4, 5, : orderedW  post
		 */

		Bag bag, nextbag;
		int count;
		int ans = 0;
		int least = postW[0].wei;
		for (int i=0; i < n; i++) {
			bag = postW[i];
			if (bag.label == true) continue;
			if (bag.prei == bag.posti) continue;

			bag.label = true;
			count = 0;
			int mini = bag.wei;
			while (true) {
				nextbag = preW[bag.posti]; // nextbag.prei == bag.posti
				if (nextbag == postW[i]) break; // postW[i] ??????????????¨??????nextbag????????£??????????????????postW[i]????????£????????????
				nextbag.label = true;
				count++;
				ans += nextbag.wei;
				bag = nextbag;
			}
			int nochange = mini * count;
			int change = (least+mini)*2 + least*count;
			ans += Math.min(change, nochange);
		}

		System.out.println(ans);
	}

	static class Bag implements Comparable<Bag> {
		int wei; // weight

		int prei; // pre index ??´?????????????????????????????????

		int posti; // post index ??´??????????????¨?????????????????????

		boolean label = false;

		Bag(int w, int i) {
			this.wei= w;
			this.prei = i;
		}

//		Bag next(Bag[] preW, Bag[] postW) {
//			int index = this.posti;
//			return preW[index];
//		}

		@Override
		public int compareTo(Bag b) {
			return this.wei - b.wei;
		}

		@Override
		public String toString() {
			return "" + wei;
		}
	}
}

Measured memory_bytes: 25144
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))
 
n = inp()
l = []
r = []
for i in range(n):
    q,w = inpl()
    l.append(q)
    r.append(w)
for i in range(n-1):
    if l[i+1] >= l[i] and r[i+1] >= r[i]:
        continue
    tmp = max(-(-l[i]//l[i+1]), -(-r[i]//r[i+1]))
    l[i+1] *= tmp
    r[i+1] *= tmp
print(l[n-1] + r[n-1])

Measured memory_bytes: 4080
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PriorityQueue<Long> queue = new PriorityQueue<>();
        int N = sc.nextInt();
        long K = sc.nextLong();
        long[] list = new long[N];
        for (int i = 0; i < N; i++) {
            long num = sc.nextLong();
            list[i] = num;
        }
        Arrays.sort(list);
        long l = -1000000000000000001L;
        long r = 1000000000000000001L;
        while (l + 1 < r) {
            long m = (l + r) / 2;
            if (isUnderK(list, m, K)) {
                l = m;
            } else {
                r = m;
            }
        }
        System.out.println(l);
    }
    
    // under num 
    private static boolean isUnderK(long[] list, long num, long k) {
        long count = 0;
        for (int i = 0; i < list.length; i++) {
            int l = -1, r = list.length;
            if (list[i] < 0) {
                while (l + 1 < r) {
                    int m = (l + r) / 2;
                    if (list[m] * list[i] < num) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                count += (list.length - r);
            } else {
                while (l + 1 < r) {
                    int m = (l + r) / 2;
                    if (list[m] * list[i] < num) {
                        l = m;
                    } else {
                        r = m;
                    }
                }
                count += r;
            }
            if (list[i] * list[i] < num)
                count--;
        }
        count /= 2;
        return count < k;
    }
}


Measured memory_bytes: 88664
N = int(input())
A = [[int(i) for i in input().split()] for j in range(2)]
DP = [[0 for i in range(N)] for j in range(2)]
DP[0][0], DP[1][0] = A[0][0], A[0][0] + A[1][0]

for i in range(1, N):
    DP[0][i] = DP[0][i-1] + A[0][i]
    DP[1][i] = max(DP[0][i], DP[1][i-1]) + A[1][i]
print(DP[1][N-1])

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

int main(int argc, char *argv[])
{
    int second;
    std::cin >> second;

    int minuite = second / 60;
    second = second % 60;
    int hour = minuite / 60;
    minuite = minuite % 60;

    std::cout << hour << ":" << minuite << ":" << second << std::endl;
}

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

int main()
{
  int s;
  cin >> s;
  int i = 1;
  while (s != 1 && s != 2 && s != 4)
  {
    if (s % 2 == 0)
    {
      s /= 2;
    }
    else
    {
      s = 3 * s + 1;
    }
    i++;
  }
  cout << i + 3 << endl;

  return 0;
}


Measured memory_bytes: 256