oj.uz

Submission #586107

# Submission time Handle Problem Language Result Execution time Memory
586107 2022-06-29T21:40:26 Z AlperenT Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 263 ms 91224 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6;

int n, k, arr[N];

vector<int> nums[N];

vector<pair<int, int>> v, vnext;

vector<int> vec, ans;

bool isneeded[N];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	cin >> n >> k;

	for(int i = 0; i < n; i++){
		cin >> arr[i];

		nums[i].push_back(arr[i]);

		v.push_back({arr[i], i});
	}

	for(int cur = 0; cur <= 29; cur++){
		reverse(v.begin(), v.end());

		while(!v.empty()){
			pair<int, int> p = v.back(); v.pop_back();

			if(p.first != cur) vnext.push_back(p);
			else{
				if(!v.empty() && v.back().first == cur){
					vnext.push_back({cur + 1, v.back().second});
					v.pop_back();
				}
				else{
					nums[p.second].push_back(cur);
					vnext.push_back({cur + 1, p.second});
				}
			}
		}

		swap(v, vnext);
		vnext.clear();
	}

	for(int i = 0; i < n; i++){
		for(auto x : nums[i]) vec.push_back(x);
	}

	int ptr = 0;

	for(int i = 0; i < vec.size(); i++){
		if(ptr < n && vec[i] == arr[ptr]) isneeded[i] = true, ptr++;
	}

	for(int i = 0; i < vec.size(); i++){
		if(isneeded[i]) ans.push_back(vec[i]);
		else{
			vector<int> stk;

			stk.push_back(vec[i]);

			while(!stk.empty() && ans.size() + (vec.size() - i - 1) + stk.size() < n + k){
				int cur = stk.back(); stk.pop_back();

				if(cur == 0) ans.push_back(0);
				else stk.push_back(cur - 1), stk.push_back(cur - 1);
			}

			while(!stk.empty()){
				ans.push_back(stk.back());
				stk.pop_back();
			}
		}
	}

	for(auto x : ans) cout << x << " ";
	cout << "\n";
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < vec.size(); i++){
      |                 ~~^~~~~~~~~~~~
zalmoxis.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 0; i < vec.size(); i++){
      |                 ~~^~~~~~~~~~~~
zalmoxis.cpp:70:73: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |    while(!stk.empty() && ans.size() + (vec.size() - i - 1) + stk.size() < n + k){
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 88980 KB Output is correct
2 Correct 233 ms 89168 KB Output is correct
3 Correct 221 ms 89028 KB Output is correct
4 Correct 234 ms 89176 KB Output is correct
5 Correct 226 ms 89084 KB Output is correct
6 Correct 219 ms 88780 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 91176 KB Output is correct
2 Correct 234 ms 88792 KB Output is correct
3 Correct 230 ms 89068 KB Output is correct
4 Correct 220 ms 91224 KB Output is correct
5 Correct 219 ms 91156 KB Output is correct
6 Correct 216 ms 91056 KB Output is correct
7 Correct 217 ms 89148 KB Output is correct
8 Correct 263 ms 89204 KB Output is correct
9 Correct 233 ms 80868 KB Output is correct
10 Correct 174 ms 52256 KB Output is correct
11 Correct 188 ms 58480 KB Output is correct
12 Correct 92 ms 29844 KB Output is correct
13 Correct 82 ms 29764 KB Output is correct
14 Correct 90 ms 29752 KB Output is correct