oj.uz

Submission #431188

# Submission time Handle Problem Language Result Execution time Memory
431188 2021-06-17T10:12:20 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
80 / 100
 499 ms 58180 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){
				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 499 ms 45552 KB Output is correct
2 Correct 467 ms 45592 KB Output is correct
3 Correct 463 ms 45548 KB Output is correct
4 Correct 471 ms 45636 KB Output is correct
5 Correct 462 ms 45552 KB Output is correct
6 Correct 482 ms 45568 KB Output is correct

Subtask #2
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 45544 KB Output is correct
2 Incorrect 494 ms 45548 KB Expected EOF
3 Correct 452 ms 45596 KB Output is correct
4 Correct 467 ms 45544 KB Output is correct
5 Correct 474 ms 45724 KB Output is correct
6 Correct 494 ms 45528 KB Output is correct
7 Correct 467 ms 45600 KB Output is correct
8 Correct 470 ms 45596 KB Output is correct
9 Incorrect 446 ms 58180 KB Expected EOF
10 Incorrect 253 ms 46540 KB Unexpected end of file - int32 expected
11 Incorrect 332 ms 52288 KB Expected EOF
12 Correct 141 ms 29900 KB Output is correct
13 Correct 153 ms 29800 KB Output is correct
14 Correct 142 ms 29768 KB Output is correct