Submission #278225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
278225	2020-08-21T11:20:47 Z	test2	Zalmoxis (BOI18_zalmoxis)	C++14	35 / 100	212 ms	16108 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	162 ms	14304 KB	Output is correct
2	Correct	162 ms	14464 KB	Output is correct
3	Correct	181 ms	14308 KB	Output is correct
4	Correct	163 ms	14304 KB	Output is correct
5	Correct	161 ms	14432 KB	Output is correct
6	Correct	160 ms	14432 KB	Output is correct

Subtask #2

5.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	166 ms	16104 KB	doesn't contain S as a subsequence
2	Correct	162 ms	14404 KB	Output is correct
3	Incorrect	179 ms	16104 KB	doesn't contain S as a subsequence
4	Incorrect	188 ms	16104 KB	doesn't contain S as a subsequence
5	Incorrect	212 ms	16104 KB	doesn't contain S as a subsequence
6	Incorrect	168 ms	16100 KB	doesn't contain S as a subsequence
7	Incorrect	172 ms	16108 KB	doesn't contain S as a subsequence
8	Incorrect	166 ms	16100 KB	doesn't contain S as a subsequence
9	Incorrect	151 ms	14564 KB	doesn't contain S as a subsequence
10	Incorrect	139 ms	10064 KB	doesn't contain S as a subsequence
11	Incorrect	140 ms	10948 KB	doesn't contain S as a subsequence
12	Incorrect	115 ms	10148 KB	not a zalsequence
13	Incorrect	100 ms	10152 KB	not a zalsequence
14	Incorrect	100 ms	10148 KB	not a zalsequence