oj.uz

Submission #431189

# Submission time Handle Problem Language Result Execution time Memory
431189 2021-06-17T10:13:03 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
80 / 100
 529 ms 58248 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> v[1000001];
int n,k,arr[1000001];

void solve(int l , int r , int val , int freq){
	if(r == l-1){
		for(int i = 0 ; i < 31 ; i += 1){
			if(freq & (1<<i)){
				v[r].push_back(val+i);
				k -= 1;
			}
		}
		return ;
	}
	int pos = -1;
	for(int i = l ; i <= r ; i += 1){
		if(arr[i] == val){
			pos = i;
			break;
		}
	}
	if(pos == -1){
		solve(l,r,val-1,2*freq);
		return ;
	}
	int farr[31];
	memset(farr,0,sizeof farr);
	for(int i = l ; i < pos ; i += 1){
		farr[arr[i]] += 1;
	}
	int tag = 0;
	for(int i = 0 ; i < val ; i += 1){
		farr[i+1] += farr[i]/2;
		if(farr[i]%2 == 1){
			tag = 1;
		}
	}
	freq -= 1;
	solve(l,pos-1,val,farr[val]+tag),solve(pos+1,r,val,freq-farr[val]-tag);
}

int main(){
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i += 1){
		cin >> arr[i];
	}
	solve(1,n,30,1);
	vector<pair<int,int>> varr;
	for(int i = 0 ; i <= n ; i += 1){
		if(i){
			varr.push_back({arr[i],1});
		}
		for(auto j : v[i]){
			if(j > 30){
				k -= 1;
				v[i].push_back(j-1),v[i].push_back(j-1);
				continue;
			}
			varr.push_back({j,0});
		}
	}
	vector<int> ans;
	while(k > 0){
		if(varr.back().second == 1){
			ans.push_back(varr.back().first);
			varr.pop_back();
			continue;
		}
		if(varr.back().first > 0){
			k -= 1;
			int a = varr.back().first;
			varr.pop_back();
			varr.push_back({a-1,0}),varr.push_back({a-1,0});
		}else{
			ans.push_back(varr.back().first);
			varr.pop_back();
		}
	}
	while(varr.size()){
		ans.push_back(varr.back().first);
		varr.pop_back();
	}
	reverse(ans.begin(),ans.end());
	for(auto i : ans){
		cout << i << " ";
	}cout << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 45560 KB Output is correct
2 Correct 461 ms 45560 KB Output is correct
3 Correct 475 ms 45544 KB Output is correct
4 Correct 524 ms 45580 KB Output is correct
5 Correct 491 ms 45636 KB Output is correct
6 Correct 504 ms 45556 KB Output is correct

Subtask #2
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 45548 KB Output is correct
2 Incorrect 474 ms 45572 KB Expected EOF
3 Correct 529 ms 45588 KB Output is correct
4 Correct 466 ms 45576 KB Output is correct
5 Correct 477 ms 45548 KB Output is correct
6 Correct 470 ms 45620 KB Output is correct
7 Correct 477 ms 45628 KB Output is correct
8 Correct 478 ms 45624 KB Output is correct
9 Incorrect 447 ms 58248 KB Expected EOF
10 Incorrect 298 ms 46196 KB Unexpected end of file - int32 expected
11 Incorrect 338 ms 52240 KB Expected EOF
12 Correct 141 ms 29780 KB Output is correct
13 Correct 139 ms 29736 KB Output is correct
14 Correct 140 ms 29804 KB Output is correct