Submission #61883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
61883	2018-07-27T04:10:56 Z	윤교준(#1798)	Zalmoxis (BOI18_zalmoxis)	C++11	100 / 100	382 ms	33188 KB

zalmoxis

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define befv(V) ((V)[sz(V)-2])
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const bool debug = 0;
const int MAXN = 1000005;

vector<int> G[MAXN];

int A[MAXN];

int N, K;

void f(vector<int> &V, int v, int &lft) {
	if(lft <= 0 || !v) {
		V.eb(v);
		return;
	}
	lft--;
	f(V, v-1, lft);
	f(V, v-1, lft);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> K;
	for(int i = 1; i <= N; i++) cin >> A[i];

	{
		vector<pii> V;
		for(int i = 1; i <= N; i++) {
			if(V.empty() || V.back().first > A[i]) {
				V.eb(A[i], i);
				continue;
			}
			for(; V.back().first < A[i];) {
				G[V.back().second].eb(V.back().first);
				V.back().first++;
				for(; 1 < sz(V) && befv(V).first == V.back().first;) {
					befv(V).second = V.back().second;
					V.pop_back();
					V.back().first++;
				}
			}
			V.eb(A[i], i);
			for(; 1 < sz(V) && befv(V).first == V.back().first;) {
				befv(V).second = V.back().second;
				V.pop_back();
				V.back().first++;
			}
		}

		if(debug) {
			for(auto v : V) printf("(%d,%d) ", v.first, v.second);
			puts("");
		}

		for(; V[0].first < 30;) {
			G[V.back().second].eb(V.back().first);
			V.back().first++;
			for(; 1 < sz(V) && befv(V).first == V.back().first;) {
				befv(V).second = V.back().second;
				V.pop_back();
				V.back().first++;
			}
		}
	}

	{
		int lft = K;
		for(int i = 1; i <= N; i++) lft -= sz(G[i]);
		for(int i = 1; i <= N; i++) {
			if(lft <= 0 || G[i].empty()) continue;
			vector<int> V;
			for(int v : G[i]) f(V, v, lft);
			swap(G[i], V);
		}
	}

	for(int i = 1; i <= N; i++) {
		printf("%d ", A[i]);
		for(int v : G[i]) printf("%d ", v);
	}
	puts("");
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	257 ms	29816 KB	Output is correct
2	Correct	249 ms	29940 KB	Output is correct
3	Correct	231 ms	30028 KB	Output is correct
4	Correct	382 ms	30028 KB	Output is correct
5	Correct	265 ms	30028 KB	Output is correct
6	Correct	323 ms	30232 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	220 ms	30232 KB	Output is correct
2	Correct	211 ms	30232 KB	Output is correct
3	Correct	229 ms	30256 KB	Output is correct
4	Correct	237 ms	30256 KB	Output is correct
5	Correct	244 ms	30256 KB	Output is correct
6	Correct	342 ms	30256 KB	Output is correct
7	Correct	279 ms	30256 KB	Output is correct
8	Correct	252 ms	30260 KB	Output is correct
9	Correct	227 ms	33068 KB	Output is correct
10	Correct	195 ms	33068 KB	Output is correct
11	Correct	218 ms	33188 KB	Output is correct
12	Correct	137 ms	33188 KB	Output is correct
13	Correct	187 ms	33188 KB	Output is correct
14	Correct	140 ms	33188 KB	Output is correct