oj.uz

Submission #430988

# Submission time Handle Problem Language Result Execution time Memory
430988 2021-06-17T08:45:08 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
15 / 100
 493 ms 262148 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 < freq ; i += 1){
			k -= 1;
			v[r].push_back(val);
		}
		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<int> varr;
	for(int i = 0 ; i <= n ; i += 1){
		for(auto j : v[i]){
			varr.push_back(j);
		}
		if(i){
			varr.push_back(arr[i]);
		}
	}
	vector<int> ans;
	while(k > 0){
		if(varr.back() > 0){
			k -= 1;
			int a = varr.back();
			varr.pop_back();
			varr.push_back(a-1),varr.push_back(a-1);
		}else{
			ans.push_back(varr.back());
			varr.pop_back();
		}
	}
	while(varr.size()){
		ans.push_back(varr.back());
		varr.pop_back();
	}
	reverse(ans.begin(),ans.end());
	for(auto i : ans){
		cout << i << " ";
	}cout << endl;
}

Subtask #1
10.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 481 ms 37732 KB Expected EOF
2 Incorrect 461 ms 37772 KB Expected EOF
3 Incorrect 481 ms 37860 KB Expected EOF
4 Correct 465 ms 37780 KB Output is correct
5 Correct 435 ms 37836 KB Output is correct
6 Incorrect 452 ms 37792 KB Expected EOF

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 433 ms 37808 KB Expected EOF
2 Incorrect 450 ms 38020 KB Expected EOF
3 Incorrect 444 ms 38060 KB Expected EOF
4 Incorrect 440 ms 37788 KB Expected EOF
5 Correct 443 ms 37720 KB Output is correct
6 Incorrect 479 ms 37796 KB Expected EOF
7 Incorrect 442 ms 37792 KB Expected EOF
8 Incorrect 493 ms 37788 KB Expected EOF
9 Incorrect 429 ms 47148 KB Expected EOF
10 Incorrect 252 ms 36820 KB not a zalsequence
11 Incorrect 296 ms 39904 KB not a zalsequence
12 Runtime error 323 ms 262148 KB Execution killed with signal 9
13 Runtime error 302 ms 262148 KB Execution killed with signal 9
14 Runtime error 356 ms 262148 KB Execution killed with signal 9