oj.uz

Submission #125394

# Submission time Handle Problem Language Result Execution time Memory
125394 2019-07-05T07:39:06 Z teomrn Mechanical Doll (IOI18_doll) C++14
100 / 100
 146 ms 15312 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 200010;
vector <int> X, Y, C;
int n, m;
vector <int> urm[NMAX], act;


vector <int> build_ord(int h)
{
	if (h == 0)
		return { 0 };
	auto x = build_ord(h - 1);
	auto y = x;
	for (auto & i : x)
		i *= 2;
	for (auto & i : y)
		i = 2 * i + 1;
	for (auto i : y)
		x.push_back(i);
	return x;
}

int build_switch(int h, int from, vector <int> & fii)
{
	if (h != 0) {
		int st = build_switch(h - 1, from, fii);
		int dr = build_switch(h - 1, from + (1 << (h - 1)), fii);
		if (st == -1e9 && dr == -1e9)
			return -1e9;
		int nod = X.size() + 1;
		X.push_back(st);
		Y.push_back(dr);
		return -nod;
	}
	return fii[from];
}

void normalize(int * v, int l)
{
	vector <int> nrm;
	for (int i = 0; i < l; i++)
		nrm.push_back(v[i]);
	sort(nrm.begin(), nrm.end());
	for (int i = 0; i < l; i++)
		v[i] = lower_bound(nrm.begin(), nrm.end(), v[i]) - nrm.begin();
}

void create_circuit(int M, std::vector<int> A) {
	n = A.size(), m = M;

	A.push_back(0);

	C.resize(m + 1);
	C[0] = A[0];

	int h = 0;
	while ((1 << h) < n)
		h++;
	auto ord = build_ord(h);
	int dec = ord.size() - n;

	normalize(ord.data() + dec, ord.size() - dec);
	for (int i = 0; i < dec; i++)
		ord[i] = -1e9;
	for (auto & i : ord) {
		if (i >= 0) {
			assert(i + 1 < A.size());
			i = A[i + 1];
		}
	}

	int root = build_switch(h, 0, ord);
	fill(C.begin() + 1, C.end(), root);

	for (auto & i : X)
		if (i == -1e9)
			i = root;
	for (auto & j : Y)
		if (j == -1e9)
			j = root;

	//cerr << "Am folosit " << X.size() << " chestii\n";
	answer(C, X, Y);
}

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:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    assert(i + 1 < A.size());
      |           ~~~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 50 ms 9472 KB Output is correct
3 Correct 52 ms 9084 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 19 ms 6092 KB Output is correct
6 Correct 76 ms 11364 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 50 ms 9472 KB Output is correct
3 Correct 52 ms 9084 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 19 ms 6092 KB Output is correct
6 Correct 76 ms 11364 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 85 ms 12060 KB Output is correct
9 Correct 91 ms 12508 KB Output is correct
10 Correct 126 ms 15312 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 50 ms 9472 KB Output is correct
3 Correct 52 ms 9084 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 19 ms 6092 KB Output is correct
6 Correct 76 ms 11364 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 85 ms 12060 KB Output is correct
9 Correct 91 ms 12508 KB Output is correct
10 Correct 126 ms 15312 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 124 ms 14452 KB Output is correct
15 Correct 79 ms 10920 KB Output is correct
16 Correct 117 ms 14284 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 5 ms 4940 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 130 ms 15036 KB Output is correct
21 Correct 5 ms 4940 KB Output is correct
22 Correct 5 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 105 ms 10492 KB Output is correct
3 Correct 87 ms 10424 KB Output is correct
4 Correct 107 ms 12880 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 105 ms 10492 KB Output is correct
3 Correct 87 ms 10424 KB Output is correct
4 Correct 107 ms 12880 KB Output is correct
5 Correct 116 ms 14136 KB Output is correct
6 Correct 115 ms 13960 KB Output is correct
7 Correct 113 ms 13908 KB Output is correct
8 Correct 142 ms 13644 KB Output is correct
9 Correct 76 ms 10356 KB Output is correct
10 Correct 116 ms 13576 KB Output is correct
11 Correct 114 ms 13244 KB Output is correct
12 Correct 80 ms 10404 KB Output is correct
13 Correct 76 ms 11028 KB Output is correct
14 Correct 91 ms 10800 KB Output is correct
15 Correct 115 ms 10860 KB Output is correct
16 Correct 6 ms 5152 KB Output is correct
17 Correct 74 ms 10772 KB Output is correct
18 Correct 75 ms 10680 KB Output is correct
19 Correct 76 ms 10396 KB Output is correct
20 Correct 113 ms 13504 KB Output is correct
21 Correct 120 ms 13240 KB Output is correct
22 Correct 146 ms 13316 KB Output is correct