Submission #61245

#	Time	Username	Problem	Language	Result	Execution time	Memory
61245		Miyukine	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	287 ms	24192 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=(a); i<=(b); ++i)
const int maxn = 1e6 + 5;
typedef pair <int, int> PII;
int tab[maxn], n, k, used;
int stos[maxn], DL = 0;
vector <PII> insert, help;

void updatestos()
{
	while (stos[DL] == stos[DL - 1]) 
	{
		DL--;
		stos[DL]++;
	}
}

void rozloz()
{
	for (auto u : insert)
	{
		if (used < k && u.second > 0)
		{
			++used;
			help.push_back(make_pair(u.first, u.second - 1));
			help.push_back(make_pair(u.first, u.second - 1));
		}
		else help.push_back(make_pair(u.first, u.second));
	}
	
	insert = help;
	help.clear();
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	used = 0;
	stos[0] = 31;
	FOR(i, 1, n) 
	{
		cin >> tab[i];
		while (tab[i] > stos[DL])
		{
			insert.push_back(make_pair(i, stos[DL]));
			++used;
			assert(used <= k);
			stos[DL]++;
			updatestos();
		}
		
		stos[++DL] = tab[i];
		updatestos();
	}
	
	while (stos[1] != 30) 
	{
		insert.push_back(make_pair(n + 1, stos[DL]));
		++used;
		assert(used <= k);
		stos[DL]++;
		updatestos();
	}
	
	//na razie po prostu <= k, niekoniecznie =
	while (used < k) rozloz();
	int iter = 0;
	FOR(i, 1, n)
	{
		while (iter < (int)insert.size() && insert[iter].first == i)
		{
			cout << insert[iter].second << ' ';
			++iter;
		}
		cout << tab[i] << ' ';
	}
	while (iter < (int)insert.size())
	{
		cout << insert[iter].second << ' ';
		++iter;
	}
}

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