제출 #1241497

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241497		Dedibeat	Zalmoxis (BOI18_zalmoxis)	C++20	45 / 100	488 ms	119972 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first 
#define S second 
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T> 
void print(const T &v, int lim = 1e9)
{
    for(auto x : v)
        if(lim-- > 0) cout << x << " ";
    cout << endl;
}
template<typename T>
void print(T *begin, const T *end)
{
    for(T *it = begin; it < end; it++)
        cout << *it << " ";
    cout << endl;
}
const int N = 1e6 + 1;
int a[N], suc[N], zeros[N], b[N];
int n, k;
vector<int> pending[N];
set<pair<int, int>> st;
inline void link(int i, int j)
{
	st.erase({a[j], j});
	suc[i] = suc[j];
	//sz[i] += sz[j];
}
int32_t main()
{
	ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
		st.insert({a[i], i});
		suc[i] = i + 1;
		//sz[i] = 1;
	}
	
	int cnt = 0;

	while(st.size() > 1)
	{
		auto [_, i] = *st.begin();
		st.erase(st.begin());
		int j = suc[i];
		if(j == n || a[j] != a[i])
		{
			pending[i].push_back(a[i]);
			cnt++;
		}
		else 
		{
			link(i, j);
		}
		a[i]++;
		st.insert({a[i], i});
		//print(st);
	}

	for(int i = 0; i < n; i++)
	{
		auto &v = pending[i];
		reverse(v.begin(), v.end());
		while(!v.empty())
		{

			if(cnt == k) break;
			else if(v.back() == 0) 
			{
				v.pop_back();
				zeros[i]++;
			}
			else 
			{
				int sz = v.size();
				cnt++;
				if(--v[sz - 1]) v.push_back(v[sz - 1]);
				else zeros[i]++;
			}
		}
		if(cnt == k) break;
	}

	assert(st.size() == 1);
	int mx = st.begin() -> first;
	assert(mx == 30);


	for(int i = 0; i < n; i++)
	{
		for(auto x : pending[i]) cout << x << " ";
		while(zeros[i]--) cout << "0 ";
		cout << b[i] << " ";
	}

	cout << "\n";
}

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