oj.uz

Submission #586094

# Submission time Handle Problem Language Result Execution time Memory
586094 2022-06-29T20:51:27 Z AlperenT Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 341 ms 89736 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

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 = 1; 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);

		if(vec.size() >= N) return 31;
	}

	int ptr = 0;

	for(int i = 0; i < vec.size(); i++){
		if(ptr < n && vec[ptr] == arr[i]) 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 == 1) ans.push_back(1);
				else stk.push_back(cur - 1), stk.push_back(cur - 1);
			}

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

	cout << ans.size() << "\n";

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

Compilation message

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 320 ms 88996 KB Execution failed because the return code was nonzero
2 Runtime error 282 ms 87796 KB Execution failed because the return code was nonzero
3 Runtime error 326 ms 88488 KB Execution failed because the return code was nonzero
4 Runtime error 295 ms 88356 KB Execution failed because the return code was nonzero
5 Runtime error 289 ms 88148 KB Execution failed because the return code was nonzero
6 Runtime error 341 ms 89736 KB Execution failed because the return code was nonzero

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 302 ms 88772 KB Execution failed because the return code was nonzero
2 Runtime error 326 ms 89536 KB Execution failed because the return code was nonzero
3 Runtime error 308 ms 87856 KB Execution failed because the return code was nonzero
4 Runtime error 288 ms 87940 KB Execution failed because the return code was nonzero
5 Runtime error 311 ms 88288 KB Execution failed because the return code was nonzero
6 Runtime error 297 ms 88752 KB Execution failed because the return code was nonzero
7 Runtime error 307 ms 88128 KB Execution failed because the return code was nonzero
8 Runtime error 284 ms 87396 KB Execution failed because the return code was nonzero
9 Runtime error 320 ms 77816 KB Execution failed because the return code was nonzero
10 Incorrect 198 ms 51544 KB Expected EOF
11 Runtime error 193 ms 60000 KB Execution failed because the return code was nonzero
12 Incorrect 86 ms 29744 KB Expected EOF
13 Incorrect 90 ms 29784 KB Expected EOF
14 Incorrect 87 ms 29788 KB Expected EOF