oj.uz

Submission #431034

# Submission time Handle Problem Language Result Execution time Memory
431034 2021-06-17T09:01:59 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
80 / 100
 528 ms 56704 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;
	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:45:6: warning: unused variable 'kk' [-Wunused-variable]
   45 |  int kk = k;
      |      ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 45552 KB Output is correct
2 Correct 469 ms 45620 KB Output is correct
3 Correct 508 ms 45548 KB Output is correct
4 Correct 498 ms 45548 KB Output is correct
5 Correct 466 ms 45736 KB Output is correct
6 Correct 527 ms 45536 KB Output is correct

Subtask #2
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 45644 KB Output is correct
2 Incorrect 479 ms 45604 KB Expected EOF
3 Correct 477 ms 45684 KB Output is correct
4 Correct 474 ms 45600 KB Output is correct
5 Correct 489 ms 45532 KB Output is correct
6 Correct 468 ms 45580 KB Output is correct
7 Correct 495 ms 45564 KB Output is correct
8 Correct 462 ms 45720 KB Output is correct
9 Incorrect 492 ms 56704 KB Expected EOF
10 Incorrect 283 ms 44904 KB not a zalsequence
11 Incorrect 396 ms 54116 KB Expected EOF
12 Correct 172 ms 29760 KB Output is correct
13 Correct 164 ms 29720 KB Output is correct
14 Correct 149 ms 29824 KB Output is correct