oj.uz

Submission #862142

# Submission time Handle Problem Language Result Execution time Memory
862142 2023-10-17T14:40:56 Z iskhakkutbilim Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 196 ms 24380 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
int n, k;
vector<pair<int, int> > ans;
int cur;
vector<int> a;
void f(int x){
	if(x < 0) return;
	if(cur >= n or a[cur] >= x){
		
		if(cur < n && a[cur] == x){
			ans.push_back({x, 0});
			cur++;
		}else{
			ans.push_back({x, 1});
		}
	}else{
		f(x-1);
		f(x-1);
	}
}
vector<int> add;
void split(int x){
	if(k == 0 or x == 0){
		add.push_back(x);
	}else{
		k--;
		split(x-1);
		split(x-1);
	}
} 
 
 
main(){
	cin >> n >> k;
	a.resize(n);
	for(int i = 0;i < n; i++){
		cin >> a[i];
	}

	f(30);
	if(ans.size() == n + k){
		for(auto [x, y] : ans) cout << x << ' ';
		return 0;
	}
	k = k - (int)ans.size() + n;
	vector<int> all;
	for(auto [x, y] : ans){
		if(!y){
			all.push_back(x);
			continue;
		}
		add.clear();
		split(x);
		for(int ax : add) all.push_back(ax);
	}
	for(int x : all) cout << x << ' ';
	return 0;
}

Compilation message

zalmoxis.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:46:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |  if(ans.size() == n + k){
      |     ~~~~~~~~~~~^~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 16308 KB Output is correct
2 Correct 190 ms 16304 KB Output is correct
3 Correct 183 ms 16308 KB Output is correct
4 Correct 187 ms 16460 KB Output is correct
5 Correct 182 ms 16824 KB Output is correct
6 Correct 196 ms 16528 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 24240 KB Output is correct
2 Correct 182 ms 16256 KB Output is correct
3 Correct 186 ms 24248 KB Output is correct
4 Correct 192 ms 24380 KB Output is correct
5 Correct 193 ms 24180 KB Output is correct
6 Correct 190 ms 24244 KB Output is correct
7 Correct 189 ms 24240 KB Output is correct
8 Correct 189 ms 24240 KB Output is correct
9 Correct 169 ms 23220 KB Output is correct
10 Correct 111 ms 15548 KB Output is correct
11 Correct 131 ms 20392 KB Output is correct
12 Correct 73 ms 8216 KB Output is correct
13 Correct 61 ms 8328 KB Output is correct
14 Correct 62 ms 8640 KB Output is correct