oj.uz

Submission #668205

# Submission time Handle Problem Language Result Execution time Memory
668205 2022-12-03T09:01:51 Z mdubaisi Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 1000 ms 35740 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 = 1e7 + 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 1081 ms 35668 KB Time limit exceeded
2 Execution timed out 1085 ms 35556 KB Time limit exceeded
3 Execution timed out 1089 ms 35436 KB Time limit exceeded
4 Execution timed out 1075 ms 35132 KB Time limit exceeded
5 Execution timed out 1094 ms 35740 KB Time limit exceeded
6 Execution timed out 1093 ms 35440 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 35452 KB Time limit exceeded
2 Execution timed out 1075 ms 35708 KB Time limit exceeded
3 Execution timed out 1047 ms 35112 KB Time limit exceeded
4 Execution timed out 1090 ms 35532 KB Time limit exceeded
5 Execution timed out 1098 ms 35316 KB Time limit exceeded
6 Execution timed out 1081 ms 35104 KB Time limit exceeded
7 Execution timed out 1091 ms 35584 KB Time limit exceeded
8 Execution timed out 1098 ms 35512 KB Time limit exceeded
9 Execution timed out 1095 ms 35048 KB Time limit exceeded
10 Execution timed out 1046 ms 32768 KB Time limit exceeded
11 Execution timed out 1085 ms 33376 KB Time limit exceeded
12 Execution timed out 1097 ms 32172 KB Time limit exceeded
13 Execution timed out 1095 ms 31992 KB Time limit exceeded
14 Execution timed out 1077 ms 32048 KB Time limit exceeded