oj.uz

Submission #647068

# Submission time Handle Problem Language Result Execution time Memory
647068 2022-10-01T13:53:50 Z georgievskiy Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 363 ms 26972 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 26700 KB Output is correct
2 Correct 283 ms 26956 KB Output is correct
3 Correct 308 ms 26716 KB Output is correct
4 Correct 315 ms 26860 KB Output is correct
5 Correct 304 ms 26972 KB Output is correct
6 Correct 288 ms 26464 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 26688 KB Output is correct
2 Correct 363 ms 26456 KB Output is correct
3 Correct 309 ms 26844 KB Output is correct
4 Correct 321 ms 26968 KB Output is correct
5 Correct 316 ms 26804 KB Output is correct
6 Correct 327 ms 26804 KB Output is correct
7 Correct 289 ms 26868 KB Output is correct
8 Correct 289 ms 26956 KB Output is correct
9 Correct 259 ms 25368 KB Output is correct
10 Correct 170 ms 23772 KB Output is correct
11 Correct 200 ms 25848 KB Output is correct
12 Correct 134 ms 25920 KB Output is correct
13 Correct 144 ms 26068 KB Output is correct
14 Correct 134 ms 25960 KB Output is correct