Submission #68589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68589	2018-08-17T12:43:03 Z	aome	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	256 ms	7928 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) {
	// assert(need <= 1 << val);
	if (need == 1) {
		cout << val << ' '; return;
	}
	int tmp = min(need - 1, (1 << (val - 1)));
	cal(val - 1, tmp), cal(val - 1, need - tmp);
}
 
int main() {
	ios::sync_with_stdio(false);
	int n, m, x;
	cin >> n >> m >> x;
	vres.push_back(x), vcur.push_back(x);
	for (int i = 1; i < n; ++i) {
		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();
	// assert(vadd.size() <= m);
	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]);
			m -= tmp;
			cal(vres[i], tmp);
		}
		else cout << vres[i] << ' '; 
	}
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vres.size(); ++i) {
                  ~~^~~~~~~~~~~~~
zalmoxis.cpp:58: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	176 ms	6500 KB	Output is correct
2	Correct	172 ms	6640 KB	Output is correct
3	Correct	188 ms	6640 KB	Output is correct
4	Correct	256 ms	6640 KB	Output is correct
5	Correct	203 ms	6664 KB	Output is correct
6	Correct	198 ms	6664 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	206 ms	6672 KB	Output is correct
2	Correct	182 ms	6672 KB	Output is correct
3	Correct	212 ms	6672 KB	Output is correct
4	Correct	210 ms	6764 KB	Output is correct
5	Correct	202 ms	6804 KB	Output is correct
6	Correct	174 ms	6804 KB	Output is correct
7	Correct	182 ms	6804 KB	Output is correct
8	Correct	178 ms	6804 KB	Output is correct
9	Correct	185 ms	7928 KB	Output is correct
10	Correct	136 ms	7928 KB	Output is correct
11	Correct	174 ms	7928 KB	Output is correct
12	Correct	105 ms	7928 KB	Output is correct
13	Correct	105 ms	7928 KB	Output is correct
14	Correct	117 ms	7928 KB	Output is correct