Submission #289817

#	Time	Username	Problem	Language	Result	Execution time	Memory
289817		duckmoon99	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	204 ms	12480 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 rem = n+k;
	int x;
	stack<int> s, cur;
	stack<ii> ans;
	for(int i = 0; i < n; i++){
		cin >> x;
		s.push(x);
	}
	cur.push(30);
	while(!s.empty()){
		if(cur.top()<=s.top()){
			ans.push(mp(cur.top(),cur.top()==s.top()));
			if(s.top()==cur.top())s.pop();
			cur.pop();
		}else{
			int x=cur.top();
			cur.pop();
			cur.push(x-1);
			cur.push(x-1);
		}
	}
	while(!cur.empty()){
		ans.push(mp(cur.top(),0));
		cur.pop();
	}
	vi fans;
	while(rem>0){
		if(ans.size()==rem || ans.top().se==1 || ans.top().fi==0){
			fans.pb(ans.top().fi);
			ans.pop();
			rem--;
		}else{
			x=ans.top().fi;
			ans.pop();
			ans.push(mp(x-1,0));
			ans.push(mp(x-1,0));
		}
	}
	for(int i = 0; i < n+k; i++){
		cout << fans[i] << " ";
	}
	
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:62:16: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   if(ans.size()==rem || ans.top().se==1 || ans.top().fi==0){
      |      ~~~~~~~~~~^~~~~

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