oj.uz

Submission #668204

# Submission time Handle Problem Language Result Execution time Memory
668204 2022-12-03T08:59:39 Z mdubaisi Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 1000 ms 26092 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 25756 KB Time limit exceeded
2 Execution timed out 1093 ms 25636 KB Time limit exceeded
3 Execution timed out 1075 ms 25656 KB Time limit exceeded
4 Execution timed out 1084 ms 25996 KB Time limit exceeded
5 Execution timed out 1090 ms 26008 KB Time limit exceeded
6 Execution timed out 1087 ms 25656 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 25704 KB Time limit exceeded
2 Execution timed out 1089 ms 26092 KB Time limit exceeded
3 Execution timed out 1089 ms 25408 KB Time limit exceeded
4 Execution timed out 1085 ms 26068 KB Time limit exceeded
5 Execution timed out 1086 ms 25960 KB Time limit exceeded
6 Execution timed out 1038 ms 25640 KB Time limit exceeded
7 Execution timed out 1044 ms 25332 KB Time limit exceeded
8 Execution timed out 1093 ms 25624 KB Time limit exceeded
9 Execution timed out 1090 ms 25332 KB Time limit exceeded
10 Execution timed out 1090 ms 23620 KB Time limit exceeded
11 Execution timed out 1088 ms 23860 KB Time limit exceeded
12 Execution timed out 1055 ms 22220 KB Time limit exceeded
13 Execution timed out 1092 ms 22640 KB Time limit exceeded
14 Execution timed out 1094 ms 22284 KB Time limit exceeded