oj.uz

Submission #668203

# Submission time Handle Problem Language Result Execution time Memory
668203 2022-12-03T08:58:30 Z mdubaisi Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 67 ms 28284 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;

	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 (!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())
      |      ~~~~~^~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 28236 KB Execution killed with signal 11
2 Runtime error 65 ms 28232 KB Execution killed with signal 11
3 Runtime error 65 ms 28224 KB Execution killed with signal 11
4 Runtime error 64 ms 28200 KB Execution killed with signal 11
5 Runtime error 62 ms 28188 KB Execution killed with signal 11
6 Runtime error 66 ms 28168 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 28188 KB Execution killed with signal 11
2 Runtime error 63 ms 28160 KB Execution killed with signal 11
3 Runtime error 65 ms 28116 KB Execution killed with signal 11
4 Runtime error 64 ms 28216 KB Execution killed with signal 11
5 Runtime error 63 ms 28284 KB Execution killed with signal 11
6 Runtime error 63 ms 28152 KB Execution killed with signal 11
7 Runtime error 65 ms 28152 KB Execution killed with signal 11
8 Runtime error 66 ms 28156 KB Execution killed with signal 11
9 Runtime error 54 ms 26572 KB Execution killed with signal 11
10 Runtime error 30 ms 22604 KB Execution killed with signal 11
11 Runtime error 45 ms 24264 KB Execution killed with signal 11
12 Runtime error 16 ms 20308 KB Execution killed with signal 11
13 Runtime error 16 ms 20208 KB Execution killed with signal 11
14 Runtime error 17 ms 20256 KB Execution killed with signal 11