oj.uz

Submission #867478

# Submission time Handle Problem Language Result Execution time Memory
867478 2023-10-28T13:10:26 Z pizzamoeger Zalmoxis (BOI18_zalmoxis) C++14
40 / 100
 103 ms 11712 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];

	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() != 30) inserts.push_back({n, nums.top()});

	int left = k-inserts.size();

	vector<int> new_s;
	int j = 0;
	for (int i = 0; i < n; i++) {
		while (j < inserts.size() && i == inserts[j].first) {
			int cnt = inserts[j].second;
			while (left > 1 && cnt > 1) {
				cnt--;
				cout << cnt << " ";
				left--;
			}
			if (left == 1) {
				cout << cnt-1 << " " << cnt-1 << " ";
				left = 0;
			}
			else cout << cnt << " ";
			j++;
		}
		cout << S[i] << " ";
	}
	while (j < inserts.size() && n == inserts[j].first) {
		int cnt = inserts[j].second;
		while (left > 1 && cnt > 1) {
			cnt--;
			cout << cnt << " ";
			left--;
		}
		if (left == 1) {
			cout << cnt-1 << " " << cnt-1 << " ";
			left = 0;
		}
		else cout << cnt << " ";
		j++;
	}
	cout << "\n";
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 10324 KB Output is correct
2 Correct 94 ms 10324 KB Output is correct
3 Correct 94 ms 10320 KB Output is correct
4 Correct 96 ms 10336 KB Output is correct
5 Correct 92 ms 10268 KB Output is correct
6 Correct 96 ms 10324 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 10316 KB Unexpected end of file - int32 expected
2 Correct 95 ms 10332 KB Output is correct
3 Correct 93 ms 10324 KB Output is correct
4 Incorrect 97 ms 10316 KB not a zalsequence
5 Incorrect 93 ms 10328 KB not a zalsequence
6 Incorrect 92 ms 10312 KB not a zalsequence
7 Incorrect 102 ms 10336 KB Unexpected end of file - int32 expected
8 Incorrect 94 ms 10320 KB Unexpected end of file - int32 expected
9 Incorrect 91 ms 11712 KB not a zalsequence
10 Incorrect 69 ms 7124 KB Unexpected end of file - int32 expected
11 Incorrect 81 ms 8916 KB not a zalsequence
12 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
13 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
14 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected