oj.uz

답안 #431025

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431025 2021-06-17T08:59:30 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 506 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],0});
		}
		for(auto j : v[i]){
			varr.push_back({j,1});
		}
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 506 ms 45600 KB Output is correct
2 Correct 436 ms 45600 KB Output is correct
3 Correct 468 ms 45548 KB Output is correct
4 Correct 454 ms 45552 KB Output is correct
5 Correct 496 ms 45612 KB Output is correct
6 Correct 494 ms 45552 KB Output is correct

Subtask #2
5.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 470 ms 45524 KB doesn't contain S as a subsequence
2 Incorrect 486 ms 45648 KB Expected EOF
3 Incorrect 477 ms 45664 KB doesn't contain S as a subsequence
4 Correct 470 ms 45584 KB Output is correct
5 Incorrect 480 ms 45568 KB doesn't contain S as a subsequence
6 Incorrect 484 ms 45548 KB doesn't contain S as a subsequence
7 Incorrect 485 ms 45548 KB doesn't contain S as a subsequence
8 Incorrect 504 ms 45640 KB doesn't contain S as a subsequence
9 Incorrect 452 ms 56712 KB Expected EOF
10 Incorrect 264 ms 44848 KB doesn't contain S as a subsequence
11 Incorrect 337 ms 54128 KB Expected EOF
12 Incorrect 146 ms 29736 KB doesn't contain S as a subsequence
13 Incorrect 165 ms 29772 KB doesn't contain S as a subsequence
14 Incorrect 160 ms 29736 KB not a zalsequence