oj.uz

답안 #68584

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68584 2018-08-17T12:18:33 Z aome Zalmoxis (BOI18_zalmoxis) C++17
65 / 100
 1000 ms 51916 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> vres, vcur, vadd;

void add() {
	int tmp = vcur.back();
	vadd.push_back(vres.size());
	vres.push_back(tmp);
	++tmp;
	vcur.pop_back();
	while (vcur.size() && vcur.back() == tmp) {
		vcur.pop_back(), tmp++;
	}
	vcur.push_back(tmp);	
}

void cal(int val, int need) {
	if (need == 1) {
		cout << val << ' '; return;
	}
	int tmp = min(need - 1, (1 << (val - 2)));
	cal(val - 1, tmp), cal(val - 1, need - tmp);
}

int main() {
	ios::sync_with_stdio(false);
	int n, m, x;
	cin >> n >> m;
	cin >> x;
	vres.push_back(x), vcur.push_back(x);
	for (int i = 1; i < n; ++i) {
		int x; cin >> x;
		if (vcur.back() > x) {
			vres.push_back(x), vcur.push_back(x);
		}
		else {
			while (vcur.back() < x) add();
			if (vcur.back() > x) {
				vres.push_back(x), vcur.push_back(x);
			}
			else {
				vres.push_back(x);
				++x;
				vcur.pop_back();
				while (vcur.size() && vcur.back() == x) {
					vcur.pop_back(), x++;
				}
				vcur.push_back(x);
			}
		}
	}
	while (vcur.back() != 30) add();
	int ptr = 0;
	for (int i = 0; i < vres.size(); ++i) {
		if (ptr < vadd.size() && vadd[ptr] == i) {
			++ptr;
			int tmp = min(m - ((int)vadd.size() - ptr), 1 << (vres[i] - 1));
			m -= tmp;
			cal(vres[i], tmp);
		}
		else cout << vres[i] << ' '; 
	}
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vres.size(); ++i) {
                  ~~^~~~~~~~~~~~~
zalmoxis.cpp:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr < vadd.size() && vadd[ptr] == i) {
       ~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 8672 KB Output is correct
2 Correct 168 ms 8952 KB Output is correct
3 Correct 174 ms 8952 KB Output is correct
4 Correct 185 ms 8952 KB Output is correct
5 Correct 162 ms 8952 KB Output is correct
6 Correct 185 ms 8952 KB Output is correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 8952 KB Output is correct
2 Execution timed out 1092 ms 49696 KB Time limit exceeded
3 Execution timed out 1095 ms 50968 KB Time limit exceeded
4 Correct 188 ms 50968 KB Output is correct
5 Correct 181 ms 50968 KB Output is correct
6 Correct 179 ms 50968 KB Output is correct
7 Correct 174 ms 50968 KB Output is correct
8 Correct 231 ms 50968 KB Output is correct
9 Execution timed out 1092 ms 51624 KB Time limit exceeded
10 Execution timed out 1095 ms 51916 KB Time limit exceeded
11 Execution timed out 1099 ms 51916 KB Time limit exceeded
12 Execution timed out 1092 ms 51916 KB Time limit exceeded
13 Execution timed out 1079 ms 51916 KB Time limit exceeded
14 Correct 95 ms 51916 KB Output is correct