oj.uz

답안 #61883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61883 2018-07-27T04:10:56 Z 윤교준(#1798) Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 382 ms 33188 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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