oj.uz

Submission #61245

# Submission time Handle Problem Language Result Execution time Memory
61245 2018-07-25T13:13:58 Z Miyukine Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 287 ms 24192 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 6396 KB Output is correct
2 Correct 196 ms 6528 KB Output is correct
3 Correct 205 ms 6528 KB Output is correct
4 Correct 242 ms 6528 KB Output is correct
5 Correct 176 ms 6564 KB Output is correct
6 Correct 266 ms 6564 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 6572 KB Output is correct
2 Correct 187 ms 6572 KB Output is correct
3 Correct 212 ms 6652 KB Output is correct
4 Correct 207 ms 6652 KB Output is correct
5 Correct 287 ms 6652 KB Output is correct
6 Correct 200 ms 6652 KB Output is correct
7 Correct 260 ms 6700 KB Output is correct
8 Correct 206 ms 6700 KB Output is correct
9 Correct 265 ms 9112 KB Output is correct
10 Correct 192 ms 16576 KB Output is correct
11 Correct 179 ms 16576 KB Output is correct
12 Correct 148 ms 24192 KB Output is correct
13 Correct 143 ms 24192 KB Output is correct
14 Correct 162 ms 24192 KB Output is correct