oj.uz

Submission #131931

# Submission time Handle Problem Language Result Execution time Memory
131931 2019-07-18T04:49:50 Z maruii Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 177 ms 14820 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int A[1000006];

void f(int x, int m) {
	if (m < 1) return;
	if (m == 1) {
		cout << x << ' ';
		return;
	}
	f(x - 1, m / 2);
	f(x - 1, m - m / 2);
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, K; cin >> N >> K;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	vector<int> v;
	vector<pii> ans;
	for (int i = 1; i <= N; ++i) {
		while (v.size() && v.back() < A[i]) {
			ans.push_back(pii(v.back(), 1));
			v.push_back(v.back());
			while (v.size() > 1 && v.back() == v[v.size() - 2]) {
				v.pop_back();
				++v.back();
			}	
		}
		ans.push_back(pii(A[i], 0));
		v.push_back(A[i]);
		while (v.size() > 1 && v.back() == v[v.size() - 2]) {
			v.pop_back();
			++v.back();
		}
	}
	while (v.size() > 1) {
		ans.push_back(pii(v.back(), 1));
		v.push_back(v.back());
		while (v.size() > 1 && v.back() == v[v.size() - 2]) {
			v.pop_back();
			++v.back();
		}
	}
	for (int i = v.back(); i < 30; ++i) ans.push_back(pii(i, 1));
	int j = N + K - ans.size();
	for (auto i : ans) {
		if (i.second && j) {
			if (j >= (1 << i.first) - 1) {
				j -= (1 << i.first) - 1;
				for (int k = (1 << i.first); k; --k) cout << 0 << ' ';
			}
			else f(i.first, j + 1), j = 0;
		}
		else cout << i.first << ' ';
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 14676 KB Output is correct
2 Correct 172 ms 14676 KB Output is correct
3 Correct 171 ms 14676 KB Output is correct
4 Correct 177 ms 14676 KB Output is correct
5 Correct 171 ms 14676 KB Output is correct
6 Correct 177 ms 14676 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 14644 KB Output is correct
2 Correct 175 ms 14676 KB Output is correct
3 Correct 172 ms 14804 KB Output is correct
4 Correct 173 ms 14676 KB Output is correct
5 Correct 171 ms 14804 KB Output is correct
6 Correct 174 ms 14704 KB Output is correct
7 Correct 172 ms 14748 KB Output is correct
8 Correct 171 ms 14820 KB Output is correct
9 Correct 159 ms 13400 KB Output is correct
10 Correct 112 ms 7520 KB Output is correct
11 Correct 133 ms 10976 KB Output is correct
12 Correct 74 ms 2424 KB Output is correct
13 Correct 74 ms 2424 KB Output is correct
14 Correct 75 ms 2296 KB Output is correct