oj.uz

Submission #867477

# Submission time Handle Problem Language Result Execution time Memory
867477 2023-10-28T13:07:22 Z 42kangaroo Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 129 ms 19772 KB 
//
// Created by 42kangaroo on 28/10/2023.
//
#include "bits/stdc++.h"

using namespace std;

#define int long long

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<pair<int, int>> addBef;
	stack<pair<int, int>> st;
	auto mergeBack = [&st]() {
		while (st.size() > 1) {
			auto t = st.top();
			st.pop();
			if (st.top().second == t.second) {
				st.top().second++;
			} else {
				st.push(t);
				break;
			}
		}
	};
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && st.top().second < a[i]) {
			addBef.push_back(st.top());
			st.push({-1, st.top().second});
			mergeBack();
		}
		st.push({i, a[i]});
		mergeBack();
	}
	while (!st.empty() && st.top().second < 30) {
		addBef.push_back(st.top());
		st.push({-1, st.top().second});
		mergeBack();
	}
	vector<int> out;
	int addInd = 0;
	assert(!addBef.empty());
	std::sort(addBef.begin(), addBef.end());
	for (int i = 0; i < n; ++i) {
		vector<int> hasTo;
		while (addInd < addBef.size() && addBef[addInd].first == i) {
			hasTo.push_back(addBef[addInd].second);
			addInd++;
		}
		std::reverse(hasTo.begin(), hasTo.end());
		for (int q = 0; q < hasTo.size(); ++q) {
			int ks = k - addBef.size() + 1;
			int p2 = 1;
			for (int j = 0; j <= 30; ++j, p2 *= 2) {
				if (p2 >= ks || hasTo[q] == j + 1) {
					for (int l = 0; l < min(ks, p2); ++l) {
						if (l < p2 - ks) out.push_back(hasTo[q] - j + 1);
						else out.push_back(hasTo[q] - j);
					}
					k -= min(ks, p2) - 1;
					break;
				}
			}
		}
		out.push_back(a[i]);
	}
	for (auto e: out) {
		cout << e << " ";
	}
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:53:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   while (addInd < addBef.size() && addBef[addInd].first == i) {
      |          ~~~~~~~^~~~~~~~~~~~~~~
zalmoxis.cpp:58:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int q = 0; q < hasTo.size(); ++q) {
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 18392 KB Output is correct
2 Correct 110 ms 18124 KB Output is correct
3 Correct 109 ms 18376 KB Output is correct
4 Correct 107 ms 18120 KB Output is correct
5 Correct 114 ms 18324 KB Output is correct
6 Correct 114 ms 18116 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 18196 KB Output is correct
2 Correct 113 ms 18912 KB Output is correct
3 Correct 114 ms 18356 KB Output is correct
4 Correct 115 ms 18372 KB Output is correct
5 Correct 107 ms 18128 KB Output is correct
6 Correct 107 ms 18108 KB Output is correct
7 Correct 110 ms 18172 KB Output is correct
8 Correct 110 ms 18124 KB Output is correct
9 Correct 112 ms 19772 KB Output is correct
10 Correct 101 ms 15712 KB Output is correct
11 Correct 98 ms 18760 KB Output is correct
12 Correct 49 ms 10260 KB Output is correct
13 Correct 54 ms 10416 KB Output is correct
14 Correct 54 ms 10424 KB Output is correct