Submission #278234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
278234	2020-08-21T11:23:24 Z	test2	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	187 ms	16204 KB

zalmoxis

#include<bits/stdc++.h>

#define I inline void 

using namespace std ; 

using ll = long long ; 
using ld = long double ; 

const int N = 2e6 + 7 ; 

// How interesting!

int n , k ; 
int a[N] ; 

int used = 0 ; 

vector<int> ans ; 

int dfs(int x , int val){
	if(a[x] > val){
		ans.push_back(-val) ; 
		used ++ ; 
		return x ; 
	}
	if(a[x] == val){	
		ans.push_back(val) ; 
		return x + 1 ; 
	}
	int ret1 = dfs(x , val - 1) ; 
	int ret2 = dfs(ret1 , val -1 ) ; 
	return ret2 ;  
}

int main(){
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	//freopen("in.in", "r" , stdin) ;

	cin >> n >> k ; 
	a[n] = (1<<30) ;
	for(int i = 0 ;i < n ; i++){
		cin >> a[i] ; 
	}

	dfs(0 , 30 ) ; 

	vector<int> ans2 = ans ; 

	while(used < k){
		ans = ans2 ; 
		ans2.clear() ; 
		for(auto u : ans){
			ans2.push_back(u) ; 
			while(used < k && ans2.back() < -1){
				int x = ans2.back() ; 
				ans2.pop_back() ; 
				ans2.push_back(x+1) ; 
				ans2.push_back(x+1) ; 
				used ++ ; 
			}
		}
	}


	for(auto u : ans2){
		cout<< abs(u) <<" " ; 
	}
	return 0 ; 
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	187 ms	14432 KB	Output is correct
2	Correct	169 ms	14308 KB	Output is correct
3	Correct	164 ms	14304 KB	Output is correct
4	Correct	163 ms	14432 KB	Output is correct
5	Correct	161 ms	14432 KB	Output is correct
6	Correct	170 ms	14348 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	16104 KB	Output is correct
2	Correct	166 ms	14304 KB	Output is correct
3	Correct	165 ms	16204 KB	Output is correct
4	Correct	164 ms	16104 KB	Output is correct
5	Correct	169 ms	16100 KB	Output is correct
6	Correct	176 ms	16100 KB	Output is correct
7	Correct	166 ms	16100 KB	Output is correct
8	Correct	168 ms	16104 KB	Output is correct
9	Correct	150 ms	14568 KB	Output is correct
10	Correct	122 ms	11376 KB	Output is correct
11	Correct	149 ms	11076 KB	Output is correct
12	Correct	97 ms	9220 KB	Output is correct
13	Correct	100 ms	9012 KB	Output is correct
14	Correct	122 ms	9668 KB	Output is correct