Submission #151777

#	Time	Username	Problem	Language	Result	Execution time	Memory
151777		rondojim	parentrises (BOI18_parentrises)	C++17	0 / 100	2 ms	376 KiB

parentrises

#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: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 6
• Subtask 4: 0 / 28
• Subtask 5: 0 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28