oj.uz

Submission #431030

# Submission time Handle Problem Language Result Execution time Memory
431030 2021-06-17T09:00:33 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
80 / 100
 519 ms 56712 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 < 30 ; 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;
	if(pos < r && arr[pos+1] == val){
		freq -= 1;
		solve(l,pos-1,val,farr[val]+tag),solve(pos+2,r,val,freq-farr[val]-tag);
		return ;
	}
	solve(l,pos-1,val,farr[val]+tag),solve(pos+1,r,val,freq-farr[val]-tag);
}

int main(){
	cin >> n >> k;
	int kk = 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;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:50:6: warning: unused variable 'kk' [-Wunused-variable]
   50 |  int kk = k;
      |      ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 45564 KB Output is correct
2 Correct 454 ms 45544 KB Output is correct
3 Correct 480 ms 45540 KB Output is correct
4 Correct 473 ms 45600 KB Output is correct
5 Correct 519 ms 45624 KB Output is correct
6 Correct 473 ms 45548 KB Output is correct

Subtask #2
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 45516 KB Output is correct
2 Incorrect 502 ms 45576 KB Expected EOF
3 Correct 459 ms 45664 KB Output is correct
4 Correct 466 ms 45632 KB Output is correct
5 Correct 467 ms 45580 KB Output is correct
6 Correct 480 ms 45604 KB Output is correct
7 Correct 458 ms 45600 KB Output is correct
8 Correct 454 ms 45560 KB Output is correct
9 Incorrect 438 ms 56712 KB Expected EOF
10 Incorrect 244 ms 44896 KB not a zalsequence
11 Incorrect 335 ms 54148 KB Expected EOF
12 Correct 165 ms 29772 KB Output is correct
13 Correct 151 ms 29756 KB Output is correct
14 Correct 157 ms 29808 KB Output is correct