oj.uz

Submission #255175

# Submission time Handle Problem Language Result Execution time Memory
255175 2020-07-31T13:41:29 Z amoo_safar Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 374 ms 64504 KB 
// 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 64108 KB Output is correct
2 Correct 268 ms 64488 KB Output is correct
3 Correct 266 ms 64220 KB Output is correct
4 Correct 253 ms 64348 KB Output is correct
5 Correct 258 ms 64368 KB Output is correct
6 Correct 256 ms 63836 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 64220 KB Output is correct
2 Correct 313 ms 63964 KB Output is correct
3 Correct 358 ms 64360 KB Output is correct
4 Correct 267 ms 64384 KB Output is correct
5 Correct 327 ms 64356 KB Output is correct
6 Correct 280 ms 64232 KB Output is correct
7 Correct 263 ms 64348 KB Output is correct
8 Correct 362 ms 64504 KB Output is correct
9 Correct 263 ms 58600 KB Output is correct
10 Correct 166 ms 29204 KB Output is correct
11 Correct 206 ms 45064 KB Output is correct
12 Correct 93 ms 10324 KB Output is correct
13 Correct 91 ms 10392 KB Output is correct
14 Correct 87 ms 10324 KB Output is correct