Submission #230720

#	Time	Username	Problem	Language	Result	Execution time	Memory
230720		DrSwad	Mechanical Doll (IOI18_doll)	C++17	100 / 100	148 ms	11384 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int N = int(4e5) + 10;

int c[N];
int x[N], y[N];

void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	c[0] = a[0];
	a.erase(a.begin());
	int n = a.size();

	if (n <= 1) {
		answer(vector<int>(c + 0, c + m + 1), vector<int>(), vector<int>());
		return;
	}

	for (int i = 1; i <= m; i++) c[i] = -1;

	int lv = 0;
	while (!lv || 1 << lv < n) {
		for (int i = 1 << lv; i < 1 << (lv + 1); i++) x[i] = - (i << 1), y[i] = - (i << 1 | 1);
		lv++;
	}

	int rem = (1 << lv) - n;

	for (int i = 0; i < lv; i++) if (rem >> i & 1) {
		int root = 1 << (lv - 1 - i);
		y[root] = -1;
	}

	vector<int> leaf;

	for (int i = 0; i < 1 << lv; i++) {
		int rev_i = 0;
		for (int j = 0; j < lv; j++) if (i >> j & 1) rev_i += 1 << (lv - 1 - j);
		int at = (1 << lv) + rev_i;

		bool flag = true;
		int root = at;
		while (root > 1) {
			if (root & 1) {
				if (y[root >> 1] == -1) flag = false;
			}
			else {
				if (x[root >> 1] == -1) flag = false;
			}
			root >>= 1;
		}

		if (flag) leaf.push_back(at);
	}

	assert(leaf.size() == n);

	for (int i = 0; i < n; i++) {
		if (leaf[i] & 1) y[leaf[i] >> 1] = a[i];
		else x[leaf[i] >> 1] = a[i];
	}

	vector<int> s(1, 1);
	for (int i = 0; i < s.size(); i++) {
		if (s[i] << 1 < 1 << lv) {
			if (x[s[i]] != -1) s.push_back(s[i] << 1);
			if (y[s[i]] != -1) s.push_back(s[i] << 1 | 1);
		}
	}

	vector<int> vx, vy;
	for (int i : s) {
		if (x[i] >= 0) vx.push_back(x[i]);
		else vx.push_back(-(upper_bound(s.begin(), s.end(), -x[i]) - s.begin()));

		if (y[i] >= 0) vy.push_back(y[i]);
		else vy.push_back(-(upper_bound(s.begin(), s.end(), -y[i]) - s.begin()));
	}

	answer(vector<int>(c + 0, c + m + 1), vx, vy);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:2:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:59:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |  assert(leaf.size() == n);
      |         ~~~~~~~~~~~~^~~~
doll.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56