Submission #131907

#	Time	Username	Problem	Language	Result	Execution time	Memory
131907		Diuven	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	261 ms	39820 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

vector<int> S;
list<int> A;
queue<list<int>::iterator> P;

int n, k;

void comp(){
	int s = S.size();
	while(s>1 && S[s-1]==S[s-2]) S[s-2]++, s--, S.pop_back();
}

void put(int x, bool b){
	S.push_back(x); A.push_back(x);
	if(b) P.push(prev(A.end()));
	comp();
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>k;
	for(int i=1; i<=n; i++){
		int x; cin>>x;
		if(S.empty() || S.back()>x){ put(x,0); continue; }
		while(S.back()<x) put(S.back(),1);
		put(x,0);
	}
	while(S.back()!=30) put(S.back(),1);
	while(int(A.size())<n+k){
		auto it = P.front();
		if(*it==0){ P.pop(); continue; }
		(*it)--, P.push(A.insert(it, *it));
	}
	for(int x:A) cout<<x<<' ';

	return 0;
}

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