oj.uz

Submission #230720

# Submission time Handle Problem Language Result Execution time Memory
230720 2020-05-11T10:56:59 Z DrSwad Mechanical Doll (IOI18_doll) C++17
100 / 100
 148 ms 11384 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 5396 KB Output is correct
3 Correct 50 ms 4888 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 69 ms 6544 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 5396 KB Output is correct
3 Correct 50 ms 4888 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 69 ms 6544 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 87 ms 8760 KB Output is correct
9 Correct 107 ms 8668 KB Output is correct
10 Correct 126 ms 11384 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 5396 KB Output is correct
3 Correct 50 ms 4888 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 69 ms 6544 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 87 ms 8760 KB Output is correct
9 Correct 107 ms 8668 KB Output is correct
10 Correct 126 ms 11384 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 122 ms 10920 KB Output is correct
15 Correct 108 ms 7796 KB Output is correct
16 Correct 120 ms 10724 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 129 ms 11052 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 89 ms 7844 KB Output is correct
3 Correct 83 ms 7412 KB Output is correct
4 Correct 114 ms 10156 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 89 ms 7844 KB Output is correct
3 Correct 83 ms 7412 KB Output is correct
4 Correct 114 ms 10156 KB Output is correct
5 Correct 124 ms 10652 KB Output is correct
6 Correct 115 ms 10412 KB Output is correct
7 Correct 122 ms 10420 KB Output is correct
8 Correct 114 ms 10284 KB Output is correct
9 Correct 85 ms 7392 KB Output is correct
10 Correct 118 ms 10268 KB Output is correct
11 Correct 148 ms 10100 KB Output is correct
12 Correct 87 ms 7484 KB Output is correct
13 Correct 71 ms 8356 KB Output is correct
14 Correct 125 ms 7652 KB Output is correct
15 Correct 137 ms 7796 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 68 ms 8096 KB Output is correct
18 Correct 83 ms 8064 KB Output is correct
19 Correct 94 ms 7416 KB Output is correct
20 Correct 123 ms 10180 KB Output is correct
21 Correct 121 ms 10200 KB Output is correct
22 Correct 119 ms 10160 KB Output is correct