Submission #255175

#	Time	Username	Problem	Language	Result	Execution time	Memory
255175		amoo_safar	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	374 ms	64504 KiB

zalmoxis

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

vector<pll> nw, fut, All;
vector<ll> Ans;

void Ins(ll num, ll cnt){
	if(cnt == 1){
		Ans.pb(num);
		return ;
	}
	Ins(num - 1, cnt / 2);
	Ins(num - 1, (cnt + 1) / 2);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, k;
	cin >> n >> k;
	ll v;
	for(int i = 1; i <= n; i++){
		cin >> v;
		All.pb({v, i * (k + 2)});
		nw.pb({v, i * (k + 2)});
	}
	ll rq = k;
	int m;
	for(int lg = 0; lg < 30; lg++){
		fut.clear();
		m = nw.size();
		for(int i = 0; i < m; i++){
			if(nw[i].F != lg){
				fut.pb(nw[i]);
				continue;
			}
			if((i + 1 < m) && (nw[i + 1].F == lg)){
				fut.pb({nw[i + 1].F + 1, nw[i + 1].S});
				i ++;
				continue;
			}
			fut.pb({nw[i].F + 1, nw[i].S + 1});
			All.pb({nw[i].F, nw[i].S + 1});
			rq --;
		}
		swap(nw, fut);
	}
	//assert(rq >= 0);
	sort(all(All), [&](pll A, pll B){
		return A.S < B.S;
	});
	for(auto X : All){
		if(X.S % (k + 2) == 0){
			Ans.pb(X.F);
			continue;
		}
		ll d = min(rq, (1ll << X.F) - 1);
		Ins(X.F, d + 1);
		rq -= d;
	}
	for(auto x : Ans) cout << x << ' ';
	cout << '\n';
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70