Submission #289770

#	Time	Username	Problem	Language	Result	Execution time	Memory
289770		duckmoon99	Zalmoxis (BOI18_zalmoxis)	C++14	95 / 100	399 ms	10088 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.empty() || idx<=-1){
			//printf("not enough\n");
			cout << -1;
			return 0;
		}
		//printf("curr.top:%d s.top:%d idx:%d\n",curr.top(),s.top(),idx);
		x = curr.top();
		curr.pop();
		if(x<s.top()){
			ans[idx]=x;
			idx--;
		}else if(x==s.top()){
			ans[idx]=x;
			s.pop();
			idx--;
		}else{
			curr.push(x-1);
			curr.push(x-1);
		}
	}
	while(idx>=0){
		if(curr.size()>idx+1 || curr.empty()){
			//printf("leftover");
			cout << -1;
			return 0;
		}else if(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++){
		printf("%d ", ans[i]);
	}
	
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:66:17: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   if(curr.size()>idx+1 || curr.empty()){
      |      ~~~~~~~~~~~^~~~~~
zalmoxis.cpp:70:23: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   }else if(curr.size()==idx+1){
      |            ~~~~~~~~~~~^~~~~~~

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