Submission #647068

#	Time	Username	Problem	Language	Result	Execution time	Memory
647068		georgievskiy	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	363 ms	26972 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int &x : a) cin >> x;
	vector<pii> t, q, q0;
	for (int i = 0; i < n; i++)
		t.push_back({a[i], i});
	for (int val = 0; val < 30; val++) {
		vector<pii> nt;
		for (int i = 0; i < t.size(); i++) {
			if (t[i].first != val) {
				nt.push_back(t[i]);
				continue;
			}
			if (i + 1 < t.size() && t[i].first == t[i + 1].first) {
				nt.push_back({t[i].first + 1, t[i + 1].second});
				i++;
			} else {
				nt.push_back({t[i].first + 1, t[i].second});
				q.push_back({t[i].second, t[i].first});
				k--;
			}
		}
		t = nt;
	}
	assert(k >= 0);
	while (k > 0) {
		while (q.back().second == 0) {
			q0.push_back(q.back());
			q.pop_back();
		}
		pii last = q.back();
		q.pop_back();
		last.second--;
		q.push_back(last), q.push_back(last);
		k--;
	}
	reverse(q0.begin(), q0.end());
	for (auto x : q0)
		q.push_back(x);
	stable_sort(q.begin(), q.end(), [](pii a, pii b) { return a.first < b.first; });
	vector<int> ans;
	int j = 0;
	for (int i = 0; i < n; i++) {
		ans.push_back(a[i]);
		while (j < q.size() && q[j].first == i)
			ans.push_back(q[j++].second);
	}
	for (int x : ans)
		cout << x << " ";
	return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for (int i = 0; i < t.size(); i++) {
      |                   ~~^~~~~~~~~~
zalmoxis.cpp:20:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |    if (i + 1 < t.size() && t[i].first == t[i + 1].first) {
      |        ~~~~~~^~~~~~~~~~
zalmoxis.cpp:51:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   while (j < q.size() && q[j].first == i)
      |          ~~^~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70