oj.uz

Submission #68585

# Submission time Handle Problem Language Result Execution time Memory
68585 2018-08-17T12:20:51 Z aome Zalmoxis (BOI18_zalmoxis) C++17
65 / 100
 1000 ms 46508 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) {
		printf("%d ", val); return;
	}
	int tmp = min(need - 1, (1 << (val - 2)));
	cal(val - 1, tmp), cal(val - 1, need - tmp);
}

int main() {
	int n, m, x;
	scanf("%d %d %d", &n, &m, &x);
	vres.push_back(x), vcur.push_back(x);
	for (int i = 1; i < n; ++i) {
		scanf("%d", &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 printf("%d ", vres[i]);
	}
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vres.size(); ++i) {
                  ~~^~~~~~~~~~~~~
zalmoxis.cpp:55:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr < vadd.size() && vadd[ptr] == i) {
       ~~~~^~~~~~~~~~~~~
zalmoxis.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &x);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zalmoxis.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 6364 KB Output is correct
2 Correct 217 ms 6488 KB Output is correct
3 Correct 213 ms 6580 KB Output is correct
4 Correct 210 ms 6624 KB Output is correct
5 Correct 205 ms 6624 KB Output is correct
6 Correct 205 ms 6672 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 6672 KB Output is correct
2 Execution timed out 1098 ms 43944 KB Time limit exceeded
3 Execution timed out 1094 ms 44768 KB Time limit exceeded
4 Correct 213 ms 44768 KB Output is correct
5 Correct 207 ms 44768 KB Output is correct
6 Correct 204 ms 44768 KB Output is correct
7 Correct 205 ms 44768 KB Output is correct
8 Correct 208 ms 44768 KB Output is correct
9 Execution timed out 1096 ms 46508 KB Time limit exceeded
10 Execution timed out 1079 ms 46508 KB Time limit exceeded
11 Execution timed out 1083 ms 46508 KB Time limit exceeded
12 Execution timed out 1085 ms 46508 KB Time limit exceeded
13 Execution timed out 1076 ms 46508 KB Time limit exceeded
14 Correct 103 ms 46508 KB Output is correct