oj.uz

답안 #867467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867467 2023-10-28T12:44:59 Z 42kangaroo Zalmoxis (BOI18_zalmoxis) C++17
30 / 100
 117 ms 19140 KB 
//
// Created by 42kangaroo on 28/10/2023.
//
#include "bits/stdc++.h"

using namespace std;

#define int long long

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;
	assert(!addBef.empty());
	std::sort(addBef.begin(), addBef.end());
	for (int i = 0; i < n; ++i) {
		vector<int> hasTo;
		while (addInd < addBef.size() && addBef[addInd].first == i) {
			hasTo.push_back(addBef[addInd].second);
			addInd++;
		}
		std::reverse(hasTo.begin(), hasTo.end());
		for (int q = 0; q < hasTo.size(); ++q) {
			int ks = k - addBef.size() + 1;
			int p2 = 1;
			for (int j = 0; j <= 30; ++j, p2 *= 2) {
				if (p2 >= ks || hasTo[q] == j + 1) {
					for (int l = 0; l < min(ks, p2); ++l) {
						if (l < p2 - ks - 1) out.push_back(hasTo[q] - j - 1);
						else out.push_back(hasTo[q] - j);
						assert(hasTo[q] - j - 1 >= 0);
					}
					k -= max(ks, p2) - 1;
					break;
				}
			}
		}
		out.push_back(a[i]);
	}
	for (auto e: out) {
		cout << e << " ";
	}
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:53:17: 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]
   53 |   while (addInd < addBef.size() && addBef[addInd].first == i) {
      |          ~~~~~~~^~~~~~~~~~~~~~~
zalmoxis.cpp:58:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int q = 0; q < hasTo.size(); ++q) {
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 18116 KB Output is correct
2 Correct 108 ms 18376 KB Output is correct
3 Correct 111 ms 18104 KB Output is correct
4 Correct 107 ms 18124 KB Output is correct
5 Correct 107 ms 18360 KB Output is correct
6 Correct 110 ms 18108 KB Output is correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 117 ms 18220 KB Unexpected end of file - int32 expected
2 Runtime error 64 ms 16460 KB Execution killed with signal 6
3 Runtime error 62 ms 16464 KB Execution killed with signal 6
4 Incorrect 108 ms 18360 KB Unexpected end of file - int32 expected
5 Incorrect 110 ms 18360 KB Unexpected end of file - int32 expected
6 Incorrect 110 ms 18132 KB Unexpected end of file - int32 expected
7 Incorrect 117 ms 18120 KB Unexpected end of file - int32 expected
8 Incorrect 108 ms 18372 KB Unexpected end of file - int32 expected
9 Runtime error 63 ms 19140 KB Execution killed with signal 6
10 Incorrect 102 ms 15708 KB Unexpected end of file - int32 expected
11 Runtime error 44 ms 14276 KB Execution killed with signal 6
12 Incorrect 49 ms 10420 KB Unexpected end of file - int32 expected
13 Incorrect 55 ms 10220 KB Unexpected end of file - int32 expected
14 Incorrect 51 ms 10252 KB Unexpected end of file - int32 expected