Submission #1229904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229904		Muhammad_Aneeq	Zalmoxis (BOI18_zalmoxis)	C++20	100 / 100	615 ms	84752 KiB

zalmoxis

#include <iostream>
#include <set>
#include <vector>
#include <deque>
using namespace std;
int const N=1e6+10;
int a[N],nx[N],org[N];
vector<int>res[N]={};
inline void solve()
{
	int n,k;
	cin>>n>>k;
	set<pair<int,int>>s;
	a[n+1]=30;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
		org[i]=a[i];
		nx[i]=i+1;
		s.insert({a[i],i});
	}
	while ((*begin(s)).first!=30)
	{
		int ind=(*begin(s)).second;
		s.erase(*begin(s));
		if (a[ind]==a[nx[ind]])
		{
			s.erase(*begin(s));
			nx[ind]=nx[nx[ind]];
		}
		else
		{
			k--;
			res[nx[ind]-1].push_back(a[ind]);
		}
		a[ind]++;
		s.insert({a[ind],ind});
	}
	for (int i=1;i<=n;i++)
	{
		cout<<org[i]<<' ';
		deque<int>cur;
		cur={begin(res[i]),end(res[i])};
		reverse(begin(cur),end(cur));
		while (cur.size())
		{
			while (cur.back()>0&&k>0)
			{
				int z=cur.back();
				cur.pop_back();
				cur.push_back(z-1);
				cur.push_back(z-1);
				k--;
			}
			cout<<cur.back()<<' ';
			cur.pop_back();
		}
	}
	cout<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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