Submission #68584

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68584	2018-08-17T12:18:33 Z	aome	Zalmoxis (BOI18_zalmoxis)	C++17	65 / 100	1000 ms	51916 KB

zalmoxis

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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