oj.uz

Submission #68586

# Submission time Handle Problem Language Result Execution time Memory
68586 2018-08-17T12:34:19 Z aome Zalmoxis (BOI18_zalmoxis) C++17
65 / 100
 1000 ms 45364 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) {
	assert(need <= (1 << (val - 1)));
	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 >> 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] - 1));
			m -= tmp;
			cal(vres[i], tmp);
		}
		else cout << vres[i] << ' '; 
	}
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from zalmoxis.cpp:1:
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(vadd.size() <= m);
         ~~~~~~~~~~~~^~~~
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 179 ms 6368 KB Output is correct
2 Correct 266 ms 6492 KB Output is correct
3 Correct 250 ms 6700 KB Output is correct
4 Correct 236 ms 6700 KB Output is correct
5 Correct 202 ms 6712 KB Output is correct
6 Correct 172 ms 6712 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 6712 KB Output is correct
2 Execution timed out 1084 ms 45364 KB Time limit exceeded
3 Execution timed out 1099 ms 45364 KB Time limit exceeded
4 Correct 186 ms 45364 KB Output is correct
5 Correct 202 ms 45364 KB Output is correct
6 Correct 188 ms 45364 KB Output is correct
7 Correct 188 ms 45364 KB Output is correct
8 Correct 239 ms 45364 KB Output is correct
9 Execution timed out 1084 ms 45364 KB Time limit exceeded
10 Execution timed out 1089 ms 45364 KB Time limit exceeded
11 Execution timed out 1086 ms 45364 KB Time limit exceeded
12 Execution timed out 1083 ms 45364 KB Time limit exceeded
13 Execution timed out 1088 ms 45364 KB Time limit exceeded
14 Correct 96 ms 45364 KB Output is correct