oj.uz

Submission #285421

# Submission time Handle Problem Language Result Execution time Memory
285421 2020-08-28T22:51:30 Z mohamedsobhi777 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 206 ms 18280 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

# Verdict Execution time Memory Grader output
1 Correct 157 ms 16352 KB Output is correct
2 Correct 172 ms 16424 KB Output is correct
3 Correct 168 ms 16352 KB Output is correct
4 Correct 206 ms 16480 KB Output is correct
5 Correct 176 ms 16480 KB Output is correct
6 Correct 166 ms 16352 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 18212 KB Output is correct
2 Correct 158 ms 16384 KB Output is correct
3 Correct 169 ms 18152 KB Output is correct
4 Correct 170 ms 18276 KB Output is correct
5 Correct 173 ms 18248 KB Output is correct
6 Correct 170 ms 18152 KB Output is correct
7 Correct 181 ms 18152 KB Output is correct
8 Correct 168 ms 18280 KB Output is correct
9 Correct 150 ms 16228 KB Output is correct
10 Correct 121 ms 12020 KB Output is correct
11 Correct 133 ms 11980 KB Output is correct
12 Correct 100 ms 9212 KB Output is correct
13 Correct 95 ms 8880 KB Output is correct
14 Correct 96 ms 9668 KB Output is correct