oj.uz

Submission #867485

# Submission time Handle Problem Language Result Execution time Memory
867485 2023-10-28T13:42:25 Z pizzamoeger Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 117 ms 25900 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main () {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int n, k; cin >> n >> k;
	vector<int> S (n);
	for (int i = 0; i < n; i++) cin >> S[i];
	n++;
	S.push_back(30);

	stack<int> nums;
	vector<pair<int,int>> inserts;
	int i = 0;
	while (i < n) {
		int cur = S[i];
		while (!nums.empty()) {
			int top = nums.top();
			//cerr << cur << " " << top << " " << i << "\n";
			if (cur == top) {
				cur++;
				nums.pop();
			} else if (cur > top) {
				inserts.push_back({i, top});
				cur = top+1;
				nums.pop();
				i--;
			} else {
				nums.push(cur);
				break;
			}
		}
		if (nums.empty()) 	nums.push(cur);
		i++;
	}

	if (!nums.empty() && nums.top() != 31) inserts.push_back({n, nums.top()});

	int left = k-inserts.size();
	int j = 0;
	while (left > 0) {
		while (inserts[j].second == 0) j++;
		inserts[j].second--;
		inserts.push_back(inserts[j]);
		left--;
	}

	sort(inserts.begin(), inserts.end());

	j = 0;
	for (int i = 0; i < n; i++) {
		while (j < inserts.size() && i == inserts[j].first) {
			int cnt = inserts[j].second;
			cout << cnt << " ";
			j++;
		}
		if (i != n-1) cout << S[i] << " ";
	}
	while (j < inserts.size() && n == inserts[j].first) {
		assert(false);
		int cnt = inserts[j].second;
		cout << cnt << " ";
		j++;
	}
	cout << "\n";
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:56:12: 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]
   56 |   while (j < inserts.size() && i == inserts[j].first) {
      |          ~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:63:11: 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]
   63 |  while (j < inserts.size() && n == inserts[j].first) {
      |         ~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 17996 KB Output is correct
2 Correct 102 ms 16488 KB Output is correct
3 Correct 102 ms 18000 KB Output is correct
4 Correct 102 ms 18000 KB Output is correct
5 Correct 101 ms 18024 KB Output is correct
6 Correct 111 ms 16224 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 16464 KB Output is correct
2 Correct 109 ms 16720 KB Output is correct
3 Correct 103 ms 16732 KB Output is correct
4 Correct 106 ms 16208 KB Output is correct
5 Correct 102 ms 17488 KB Output is correct
6 Correct 101 ms 16980 KB Output is correct
7 Correct 107 ms 17764 KB Output is correct
8 Correct 103 ms 17496 KB Output is correct
9 Correct 106 ms 18148 KB Output is correct
10 Correct 115 ms 25900 KB Output is correct
11 Correct 117 ms 18952 KB Output is correct
12 Correct 103 ms 18240 KB Output is correct
13 Correct 85 ms 18100 KB Output is correct
14 Correct 85 ms 18360 KB Output is correct