oj.uz

Submission #125388

# Submission time Handle Problem Language Result Execution time Memory
125388 2019-07-05T07:31:01 Z teomrn Mechanical Doll (IOI18_doll) C++14
47 / 100
 129 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 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;

	for (auto & i : ord) {
		if (i < dec)
			i = -1e9;
		else {
			assert(i - dec + 1 < A.size());
			i = A[i - dec + 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;

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

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
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 #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 4900 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 5 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
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 5000 KB Output is partially correct
2 Correct 50 ms 10480 KB Output is correct
3 Partially correct 87 ms 13352 KB Output is partially correct
4 Partially correct 90 ms 14232 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 5000 KB Output is partially correct
2 Correct 50 ms 10480 KB Output is correct
3 Partially correct 87 ms 13352 KB Output is partially correct
4 Partially correct 90 ms 14232 KB Output is partially correct
5 Partially correct 99 ms 15320 KB Output is partially correct
6 Partially correct 128 ms 15132 KB Output is partially correct
7 Partially correct 97 ms 15216 KB Output is partially correct
8 Partially correct 129 ms 14816 KB Output is partially correct
9 Partially correct 126 ms 13292 KB Output is partially correct
10 Partially correct 91 ms 14828 KB Output is partially correct
11 Partially correct 114 ms 14476 KB Output is partially correct
12 Partially correct 88 ms 13300 KB Output is partially correct
13 Correct 56 ms 11136 KB Output is correct
14 Partially correct 97 ms 13708 KB Output is partially correct
15 Partially correct 100 ms 13868 KB Output is partially correct
16 Partially correct 6 ms 5324 KB Output is partially correct
17 Correct 71 ms 10768 KB Output is correct
18 Correct 54 ms 10752 KB Output is correct
19 Partially correct 81 ms 13360 KB Output is partially correct
20 Partially correct 94 ms 14660 KB Output is partially correct
21 Partially correct 98 ms 14436 KB Output is partially correct
22 Partially correct 90 ms 14488 KB Output is partially correct