oj.uz

Submission #125365

# Submission time Handle Problem Language Result Execution time Memory
125365 2019-07-05T07:04:09 Z teomrn Mechanical Doll (IOI18_doll) C++14
53 / 100
 174 ms 20820 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 nod = X.size() + 1;
		X.push_back(0);
		Y.push_back(0);
		int st = build_switch(h - 1, from, fii);
		int dr = build_switch(h - 1, from + (1 << (h - 1)), fii);
		X[nod - 1] = st;
		Y[nod - 1] = dr;
		return -nod;
	}
	return fii[from];
}

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

	urm[0].push_back(A[0]);
	A.push_back(0);
	for (int i = 0; i + 1 < A.size(); i++)
		urm[A[i]].push_back(A[i + 1]);

	C.resize(m + 1);

	for (int i = 0; i <= m; i++) {
		if (urm[i].empty())
			continue;
		int nr = urm[i].size();
		int h = 0, root = -(X.size() + 1);
		while ((1 << h) < nr)
			h++;
		auto ord = build_ord(h);
		// o sa am ordinea ord cand apelez cv de adancime h

		int decalaj = ord.size() - nr;
		for (auto & j : ord) {
			if (j < decalaj)
				j = root;
			else {
				assert(j - decalaj < urm[i].size());
				j = urm[i][j - decalaj];
			}
		}

		C[i] = build_switch(h, 0, ord);
	}

	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i + 1 < A.size(); i++)
      |                  ~~~~~~^~~~~~~~~~
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:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     assert(j - decalaj < urm[i].size());
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 40 ms 8724 KB Output is correct
3 Correct 36 ms 8380 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 18 ms 6164 KB Output is correct
6 Correct 57 ms 10348 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 5 ms 4940 KB Output is correct
2 Correct 40 ms 8724 KB Output is correct
3 Correct 36 ms 8380 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 18 ms 6164 KB Output is correct
6 Correct 57 ms 10348 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 64 ms 11136 KB Output is correct
9 Correct 103 ms 11532 KB Output is correct
10 Correct 135 ms 14736 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 5 ms 4940 KB Output is correct
2 Correct 40 ms 8724 KB Output is correct
3 Correct 36 ms 8380 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 18 ms 6164 KB Output is correct
6 Correct 57 ms 10348 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 64 ms 11136 KB Output is correct
9 Correct 103 ms 11532 KB Output is correct
10 Correct 135 ms 14736 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 136 ms 16416 KB Output is correct
15 Correct 66 ms 10884 KB Output is correct
16 Correct 100 ms 13776 KB Output is correct
17 Correct 4 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 109 ms 15192 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 4920 KB Output is partially correct
2 Correct 50 ms 10744 KB Output is correct
3 Partially correct 86 ms 14748 KB Output is partially correct
4 Partially correct 92 ms 15196 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 4920 KB Output is partially correct
2 Correct 50 ms 10744 KB Output is correct
3 Partially correct 86 ms 14748 KB Output is partially correct
4 Partially correct 92 ms 15196 KB Output is partially correct
5 Partially correct 152 ms 18120 KB Output is partially correct
6 Partially correct 163 ms 19460 KB Output is partially correct
7 Partially correct 135 ms 19008 KB Output is partially correct
8 Partially correct 142 ms 20100 KB Output is partially correct
9 Partially correct 81 ms 14516 KB Output is partially correct
10 Partially correct 162 ms 19544 KB Output is partially correct
11 Partially correct 174 ms 20820 KB Output is partially correct
12 Partially correct 82 ms 14952 KB Output is partially correct
13 Partially correct 109 ms 13556 KB Output is partially correct
14 Partially correct 87 ms 13196 KB Output is partially correct
15 Partially correct 86 ms 12836 KB Output is partially correct
16 Partially correct 6 ms 5196 KB Output is partially correct
17 Partially correct 73 ms 12184 KB Output is partially correct
18 Partially correct 96 ms 13076 KB Output is partially correct
19 Partially correct 74 ms 12760 KB Output is partially correct
20 Partially correct 107 ms 16196 KB Output is partially correct
21 Partially correct 124 ms 18732 KB Output is partially correct
22 Partially correct 95 ms 15396 KB Output is partially correct