Submission #668204

#	Time	Username	Problem	Language	Result	Execution time	Memory
668204		mdubaisi	Zalmoxis (BOI18_zalmoxis)	C++14	0 / 100	1094 ms	26092 KiB

zalmoxis

#include <bits/stdc++.h>
#include <array>
#include <unordered_set>
#define ll long long
#define all(v) (v.begin()), (v.end())
#define setall(a, val) for(auto& x : a) x = val
clock_t start_time;
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
void init() {
#ifndef ONLINE_JUDGE
	FILE* _ = freopen("in.txt", "r", stdin);
	start_time = clock();
#endif
}
const ll MOD = 1e9 + 7;
const ll N = 5e6 + 7;
const ll M = 5e1 + 7;
using namespace std;
//####################################################################################

int n, k;
int a[N], pos;
vector< pair<bool, bool> > v; // {go to childeren, new node}
void create_tree(int x, int node) {
	if (node >= v.size()) {
		cout << "PROBLEMM!!!!" << endl;
		return;
	}

	if (pos >= n) {
		v[node] = { 0, 1 }, k--;
		return;
	}
	else if (!x || x == a[pos]) {
		v[node] = { 0, 0 };
		pos++;
		return;
	}
	else if (a[pos] < x) {
		create_tree(x - 1, node * 2);
		create_tree(x - 1, node * 2 + 1);
		v[node] = { 1, 0 };
	}
	else
		v[node] = { 0, 1 }, k--;
}

void print(int x, int t) {
	if (!t) {
		cout << x << ' ';
		return;
	}
	else if (x) {
		print(x - 1, 0);
		print(x - 1, t - 1);
	}
}

void solve(int x, int node) {
	if (node >= v.size()) {
		cout << "PROBLEMM!!!!" << endl;
		return;
	}
	if (!v[node].first) {
		print(x, k * v[node].second);
		k -= k * v[node].second;
		return;
	}
	else if (x) {
		solve(x - 1, node * 2);
		solve(x - 1, node * 2 + 1);
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //init(); srand(time(0));

	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	v.resize(N);
	create_tree(30, 1);
	solve(30, 1);
	cout << endl;

	//cerr << get_time() << "s" << endl;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'void init()':
zalmoxis.cpp:11:8: warning: unused variable '_' [-Wunused-variable]
   11 |  FILE* _ = freopen("in.txt", "r", stdin);
      |        ^
zalmoxis.cpp: In function 'void create_tree(int, int)':
zalmoxis.cpp:25:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  if (node >= v.size()) {
      |      ~~~~~^~~~~~~~~~~
zalmoxis.cpp: In function 'void solve(int, int)':
zalmoxis.cpp:60:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  if (node >= v.size()) {
      |      ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70