oj.uz

Submission #867453

# Submission time Handle Problem Language Result Execution time Memory
867453 2023-10-28T12:23:43 Z 42kangaroo Zalmoxis (BOI18_zalmoxis) C++17
30 / 100
 124 ms 10660 KB 
//
// Created by 42kangaroo on 28/10/2023.
//
#include "bits/stdc++.h"

using namespace std;

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;
	bool first = true;
	for (int i = 0; i < n; ++i) {
		while (addInd < addBef.size() && addBef[addInd].first == i) {
			if (first) {
				int ks = k - addBef.size() + 1;
				int p2 = 1;
				for (int j = 0; j <= 30; ++j, p2*= 2) {
					if (p2 >= ks) {
						for (int l = 0; l < ks; ++l) {
							if (l < p2 - ks - 1) out.push_back(addBef[addInd].second - j - 1);
							else out.push_back(addBef[addInd].second - j);
						}
						break;
					}
				}
				first = false;
				addInd++;
			} else {
				out.push_back(addBef[addInd++].second);
			}
		}
		out.push_back(a[i]);
	}
	for (auto e: out) {
		cout << e << " ";
	}
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 10436 KB Output is correct
2 Correct 106 ms 10432 KB Output is correct
3 Correct 106 ms 10356 KB Output is correct
4 Correct 106 ms 10380 KB Output is correct
5 Correct 105 ms 10596 KB Output is correct
6 Correct 105 ms 10432 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 10432 KB Unexpected end of file - int32 expected
2 Incorrect 118 ms 10440 KB Unexpected end of file - int32 expected
3 Incorrect 124 ms 10388 KB Unexpected end of file - int32 expected
4 Incorrect 109 ms 10356 KB Unexpected end of file - int32 expected
5 Incorrect 105 ms 10432 KB Unexpected end of file - int32 expected
6 Incorrect 103 ms 10364 KB Unexpected end of file - int32 expected
7 Incorrect 104 ms 10660 KB Unexpected end of file - int32 expected
8 Incorrect 111 ms 10360 KB Unexpected end of file - int32 expected
9 Incorrect 92 ms 10504 KB Unexpected end of file - int32 expected
10 Incorrect 64 ms 9032 KB Unexpected end of file - int32 expected
11 Incorrect 85 ms 9800 KB Unexpected end of file - int32 expected
12 Incorrect 49 ms 8396 KB Unexpected end of file - int32 expected
13 Incorrect 49 ms 8384 KB Unexpected end of file - int32 expected
14 Incorrect 49 ms 8380 KB not a zalsequence