Submission #867470

#	Time	Username	Problem	Language	Result	Execution time	Memory
867470		pizzamoeger	Zalmoxis (BOI18_zalmoxis)	C++14	30 / 100	111 ms	24520 KiB

zalmoxis

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

	int size = inserts.size();
	int ind = 0;
	int ind2 = 0;
	while (inserts.size() < k) {
		inserts[ind].second--;
		inserts.push_back({inserts[ind]});
		if (inserts[ind].second == 0) {
			ind2++;
			ind = ind2;
		} else ind = inserts.size()-1;
	}

	int j = 0;
	for (int i = 0; i < n; i++) {
		while (j < inserts.size() && i == inserts[j].first) {
			cout << inserts[j].second << " ";
			j++;
		}
		cout << S[i] << " ";
	}
	while (j < inserts.size() && n == inserts[j].first) {
		cout << inserts[j].second << " ";
		j++;
	}
	cout << "\n";
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:44:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |  while (inserts.size() < k) {
      |         ~~~~~~~~~~~~~~~^~~
zalmoxis.cpp:55: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]
   55 |   while (j < inserts.size() && i == inserts[j].first) {
      |          ~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:61: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]
   61 |  while (j < inserts.size() && n == inserts[j].first) {
      |         ~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:41:6: warning: unused variable 'size' [-Wunused-variable]
   41 |  int size = inserts.size();
      |      ^~~~

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