oj.uz

Submission #431148

# Submission time Handle Problem Language Result Execution time Memory
431148 2021-06-17T09:59:18 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
80 / 100
 539 ms 56812 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){
		assert(i >= 0);
		cout << i << " ";
	}cout << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 45548 KB Output is correct
2 Correct 469 ms 45556 KB Output is correct
3 Correct 482 ms 45548 KB Output is correct
4 Correct 510 ms 45544 KB Output is correct
5 Correct 503 ms 45604 KB Output is correct
6 Correct 489 ms 45596 KB Output is correct

Subtask #2
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 45632 KB Output is correct
2 Incorrect 485 ms 45552 KB Expected EOF
3 Correct 474 ms 45872 KB Output is correct
4 Correct 467 ms 45628 KB Output is correct
5 Correct 487 ms 45596 KB Output is correct
6 Correct 508 ms 45576 KB Output is correct
7 Correct 539 ms 45640 KB Output is correct
8 Correct 467 ms 45552 KB Output is correct
9 Incorrect 470 ms 56812 KB Expected EOF
10 Incorrect 261 ms 45016 KB not a zalsequence
11 Incorrect 352 ms 54280 KB Expected EOF
12 Correct 141 ms 29728 KB Output is correct
13 Correct 146 ms 29712 KB Output is correct
14 Correct 141 ms 29908 KB Output is correct