Submission #365476

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
365476	2021-02-11T17:38:09 Z	tfg	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	282 ms	10476 KB

zalmoxis

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

const int ms = 1001000;
int n, k;
int a[ms], b[ms];

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	std::cin >> n >> k;
	for(int i = 0; i < n; i++) {
		std::cin >> a[i];
	}
	for(int p = 0; p < 30; p++) {
		int j = 0;
		for(int i = 0; i < n;) {
			if(std::abs(a[i]) > p) {
				b[j++] = a[i++];
			} else {
				int sum = 0;
				//std::cout << "starting from " << i << std::endl;
				while(i < n && std::abs(a[i]) <= p) {
					b[j++] = a[i];
					sum += 1 << std::abs(a[i++]);
				}
				//std::cout << "sum " << sum << ", ending at " << i << std::endl;
				sum %= 1 << (p+1);
				assert(sum == 0 || sum == (1 << p));
				if(sum) {
					b[j++] = -p;
					k--;
				}
			}
		}
		n = j;
		std::swap(a, b);
	}
	for(int i = 0; i < n; i++) {
		if(a[i] >= 0) {
			std::cout << a[i] << ' ';
			continue;
		}
		std::vector<int> wtf(1, -a[i]);
		while(!wtf.empty()) {
			if(k == 0 || wtf.back() == 0) {
				std::cout << wtf.back() << ' ';
				wtf.pop_back();
				continue;
			} else {
				int val = wtf.back();
				wtf.pop_back();
				wtf.push_back(val-1);
				wtf.push_back(val-1);
				k--;
			}
		}
	}
	std::cout << '\n';
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	237 ms	10348 KB	Output is correct
2	Correct	232 ms	10476 KB	Output is correct
3	Correct	234 ms	10348 KB	Output is correct
4	Correct	231 ms	10348 KB	Output is correct
5	Correct	230 ms	10348 KB	Output is correct
6	Correct	230 ms	10476 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	268 ms	10248 KB	Output is correct
2	Correct	230 ms	10348 KB	Output is correct
3	Correct	235 ms	10348 KB	Output is correct
4	Correct	230 ms	10348 KB	Output is correct
5	Correct	239 ms	10284 KB	Output is correct
6	Correct	233 ms	10348 KB	Output is correct
7	Correct	229 ms	10348 KB	Output is correct
8	Correct	282 ms	10348 KB	Output is correct
9	Correct	223 ms	10348 KB	Output is correct
10	Correct	182 ms	10220 KB	Output is correct
11	Correct	201 ms	10220 KB	Output is correct
12	Correct	147 ms	10220 KB	Output is correct
13	Correct	148 ms	10220 KB	Output is correct
14	Correct	148 ms	10220 KB	Output is correct