oj.uz

Submission #431041

# Submission time Handle Problem Language Result Execution time Memory
431041 2021-06-17T09:04:04 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
80 / 100
 597 ms 56788 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]){
			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 481 ms 45664 KB Output is correct
2 Correct 469 ms 45588 KB Output is correct
3 Correct 481 ms 45620 KB Output is correct
4 Correct 466 ms 45652 KB Output is correct
5 Correct 477 ms 45568 KB Output is correct
6 Correct 509 ms 45540 KB Output is correct

Subtask #2
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 45644 KB Output is correct
2 Incorrect 495 ms 45560 KB Expected EOF
3 Correct 494 ms 45608 KB Output is correct
4 Correct 470 ms 45548 KB Output is correct
5 Correct 494 ms 45552 KB Output is correct
6 Correct 494 ms 45600 KB Output is correct
7 Correct 506 ms 45556 KB Output is correct
8 Correct 541 ms 45540 KB Output is correct
9 Incorrect 447 ms 56788 KB Expected EOF
10 Incorrect 266 ms 45068 KB not a zalsequence
11 Incorrect 348 ms 54340 KB Expected EOF
12 Correct 143 ms 29740 KB Output is correct
13 Correct 161 ms 29828 KB Output is correct
14 Correct 149 ms 29896 KB Output is correct