oj.uz

Submission #586096

# Submission time Handle Problem Language Result Execution time Memory
586096 2022-06-29T20:52:37 Z AlperenT Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 507 ms 124164 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 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 337 ms 116816 KB Execution failed because the return code was nonzero
2 Incorrect 488 ms 123992 KB Expected EOF
3 Runtime error 363 ms 116244 KB Execution failed because the return code was nonzero
4 Runtime error 306 ms 116152 KB Execution failed because the return code was nonzero
5 Runtime error 322 ms 116072 KB Execution failed because the return code was nonzero
6 Runtime error 339 ms 117592 KB Execution failed because the return code was nonzero

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 116428 KB Execution failed because the return code was nonzero
2 Runtime error 357 ms 117380 KB Execution failed because the return code was nonzero
3 Runtime error 313 ms 115696 KB Execution failed because the return code was nonzero
4 Incorrect 497 ms 124164 KB Expected EOF
5 Runtime error 307 ms 116044 KB Execution failed because the return code was nonzero
6 Runtime error 322 ms 116540 KB Execution failed because the return code was nonzero
7 Runtime error 342 ms 115844 KB Execution failed because the return code was nonzero
8 Incorrect 463 ms 122784 KB Expected EOF
9 Incorrect 507 ms 113160 KB Expected EOF
10 Incorrect 228 ms 75048 KB Expected EOF
11 Incorrect 332 ms 95464 KB Expected EOF
12 Incorrect 96 ms 53328 KB Expected EOF
13 Incorrect 95 ms 53248 KB Expected EOF
14 Incorrect 109 ms 53340 KB Expected EOF