oj.uz

Submission #431018

# Submission time Handle Problem Language Result Execution time Memory
431018 2021-06-17T08:57:30 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
75 / 100
 491 ms 48504 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<int> varr;
	for(int i = 0 ; i <= n ; i += 1){
		if(i){
			varr.push_back(arr[i]);
		}
		for(auto j : v[i]){
			varr.push_back(j);
		}
	}
	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;
}

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 449 ms 37756 KB Output is correct
2 Correct 416 ms 37696 KB Output is correct
3 Correct 436 ms 37760 KB Output is correct
4 Correct 413 ms 37676 KB Output is correct
5 Correct 445 ms 37808 KB Output is correct
6 Correct 433 ms 37768 KB Output is correct

Subtask #2
45.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 37764 KB Output is correct
2 Incorrect 419 ms 37912 KB Expected EOF
3 Incorrect 416 ms 38036 KB doesn't contain S as a subsequence
4 Correct 417 ms 37780 KB Output is correct
5 Correct 438 ms 37764 KB Output is correct
6 Correct 425 ms 37680 KB Output is correct
7 Correct 434 ms 37828 KB Output is correct
8 Correct 417 ms 37760 KB Output is correct
9 Incorrect 423 ms 48504 KB Expected EOF
10 Incorrect 231 ms 38064 KB not a zalsequence
11 Incorrect 341 ms 47296 KB Expected EOF
12 Correct 123 ms 29736 KB Output is correct
13 Correct 133 ms 29860 KB Output is correct
14 Correct 137 ms 29920 KB Output is correct