Submission #289812

#	Time	Username	Problem	Language	Result	Execution time	Memory
289812		duckmoon99	Zalmoxis (BOI18_zalmoxis)	C++14	95 / 100	163 ms	8428 KiB

zalmoxis

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace std::chrono;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector <ii> vii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

/*
5 1
29 27 25 25 28
*/

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	int x;
	stack<int> s, curr;
	int ans[n+k];
	int idx = n+k-1;
	for(int i = 0; i < n; i++){
		cin >> x;
		s.push(x);
	}
	curr.push(30);
	while(!s.empty()){
		if(curr.top()<=s.top()){
			ans[idx]=curr.top();
			if(s.top()==curr.top())s.pop();
			curr.pop();
			idx--;
		}else{
			int x=curr.top();
			curr.pop();
			curr.push(x-1);
			curr.push(x-1);
		}
	}
	assert(idx+1>=curr.size());
	while(idx>=0){
		if(curr.empty()){ 
			cout << -1 <<'\n';
			return 0;
		}else if(int(curr.size())==idx+1){
			ans[idx]=curr.top();
			curr.pop();
			idx--;
		}else{
			if(curr.top()==0){
				ans[idx]=curr.top();
				curr.pop();
				idx--;
			}else{
				x=curr.top();
				curr.pop();
				curr.push(x-1);
				curr.push(x-1);
			}
		}
	}
	
	for(int i = 0; i < n+k; i++){
		cout<<ans[i]<<" ";
	}
	cout<<'\n';
	
}

Compilation message (stderr)

In file included from /usr/include/c++/9/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/9/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/9/ext/pb_ds/assoc_container.hpp:48,
                 from zalmoxis.cpp:2:
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::stack<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  assert(idx+1>=curr.size());
      |         ~~~~~^~~~~~~~~~~~~

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