oj.uz

Submission #125393

# Submission time Handle Problem Language Result Execution time Memory
125393 2019-07-05T07:38:39 Z teomrn Mechanical Doll (IOI18_doll) C++14
100 / 100
 147 ms 15320 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 6 ms 4940 KB Output is correct
2 Correct 50 ms 9484 KB Output is correct
3 Correct 47 ms 9100 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 20 ms 6148 KB Output is correct
6 Correct 73 ms 11332 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 50 ms 9484 KB Output is correct
3 Correct 47 ms 9100 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 20 ms 6148 KB Output is correct
6 Correct 73 ms 11332 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 83 ms 12032 KB Output is correct
9 Correct 90 ms 12544 KB Output is correct
10 Correct 134 ms 15320 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 6 ms 4940 KB Output is correct
2 Correct 50 ms 9484 KB Output is correct
3 Correct 47 ms 9100 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 20 ms 6148 KB Output is correct
6 Correct 73 ms 11332 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 83 ms 12032 KB Output is correct
9 Correct 90 ms 12544 KB Output is correct
10 Correct 134 ms 15320 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 130 ms 14412 KB Output is correct
15 Correct 87 ms 10908 KB Output is correct
16 Correct 120 ms 14292 KB Output is correct
17 Correct 5 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 129 ms 14920 KB Output is correct
21 Correct 4 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 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 5 ms 4972 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 79 ms 10532 KB Output is correct
3 Correct 83 ms 10428 KB Output is correct
4 Correct 147 ms 12936 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 79 ms 10532 KB Output is correct
3 Correct 83 ms 10428 KB Output is correct
4 Correct 147 ms 12936 KB Output is correct
5 Correct 121 ms 14088 KB Output is correct
6 Correct 121 ms 13904 KB Output is correct
7 Correct 121 ms 13960 KB Output is correct
8 Correct 117 ms 13628 KB Output is correct
9 Correct 80 ms 10420 KB Output is correct
10 Correct 135 ms 13692 KB Output is correct
11 Correct 116 ms 13276 KB Output is correct
12 Correct 77 ms 10456 KB Output is correct
13 Correct 77 ms 11068 KB Output is correct
14 Correct 83 ms 10732 KB Output is correct
15 Correct 83 ms 10828 KB Output is correct
16 Correct 6 ms 5196 KB Output is correct
17 Correct 89 ms 10760 KB Output is correct
18 Correct 108 ms 10760 KB Output is correct
19 Correct 80 ms 10360 KB Output is correct
20 Correct 115 ms 13524 KB Output is correct
21 Correct 111 ms 13204 KB Output is correct
22 Correct 117 ms 13320 KB Output is correct