oj.uz

답안 #278234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278234 2020-08-21T11:23:24 Z test2 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 187 ms 16204 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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