oj.uz

Submission #125378

# Submission time Handle Problem Language Result Execution time Memory
125378 2019-07-05T07:11:30 Z teomrn Mechanical Doll (IOI18_doll) C++14
47 / 100
 130 ms 14788 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;

	A.push_back(0);

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

	int root = -1;
	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 = root;
		else {
			assert(i - dec + 1 < A.size());
			i = A[i - dec + 1];
		}
	}

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

	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:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    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 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 4 ms 4940 KB Output is correct
6 Correct 5 ms 4940 KB Output is correct
7 Correct 5 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 4 ms 4968 KB Output is partially correct
2 Correct 52 ms 10424 KB Output is correct
3 Partially correct 100 ms 13348 KB Output is partially correct
4 Partially correct 97 ms 14064 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 4968 KB Output is partially correct
2 Correct 52 ms 10424 KB Output is correct
3 Partially correct 100 ms 13348 KB Output is partially correct
4 Partially correct 97 ms 14064 KB Output is partially correct
5 Partially correct 104 ms 14788 KB Output is partially correct
6 Partially correct 125 ms 14648 KB Output is partially correct
7 Partially correct 99 ms 14696 KB Output is partially correct
8 Partially correct 123 ms 14488 KB Output is partially correct
9 Partially correct 85 ms 13352 KB Output is partially correct
10 Partially correct 130 ms 14432 KB Output is partially correct
11 Partially correct 130 ms 14272 KB Output is partially correct
12 Partially correct 83 ms 13300 KB Output is partially correct
13 Correct 54 ms 10988 KB Output is correct
14 Partially correct 84 ms 13384 KB Output is partially correct
15 Partially correct 114 ms 13484 KB Output is partially correct
16 Partially correct 7 ms 5324 KB Output is partially correct
17 Correct 63 ms 10708 KB Output is correct
18 Correct 54 ms 10708 KB Output is correct
19 Partially correct 82 ms 13284 KB Output is partially correct
20 Partially correct 100 ms 14292 KB Output is partially correct
21 Partially correct 98 ms 14180 KB Output is partially correct
22 Partially correct 92 ms 14172 KB Output is partially correct