oj.uz

Submission #431211

# Submission time Handle Problem Language Result Execution time Memory
431211 2021-06-17T10:18:43 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
80 / 100
 498 ms 56860 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 , long long 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 495 ms 45552 KB Output is correct
2 Correct 468 ms 45628 KB Output is correct
3 Correct 466 ms 45568 KB Output is correct
4 Correct 461 ms 45636 KB Output is correct
5 Correct 476 ms 45676 KB Output is correct
6 Correct 480 ms 45612 KB Output is correct

Subtask #2
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 45596 KB Output is correct
2 Incorrect 498 ms 45672 KB Expected EOF
3 Correct 490 ms 45596 KB Output is correct
4 Correct 473 ms 45616 KB Output is correct
5 Correct 483 ms 45688 KB Output is correct
6 Correct 494 ms 45632 KB Output is correct
7 Correct 467 ms 45552 KB Output is correct
8 Correct 475 ms 45632 KB Output is correct
9 Incorrect 469 ms 56860 KB Expected EOF
10 Incorrect 261 ms 44980 KB not a zalsequence
11 Incorrect 345 ms 54268 KB Expected EOF
12 Correct 142 ms 29780 KB Output is correct
13 Correct 160 ms 29712 KB Output is correct
14 Correct 141 ms 29788 KB Output is correct