oj.uz

Submission #769363

# Submission time Handle Problem Language Result Execution time Memory
769363 2023-06-29T13:10:32 Z coloboxx Mechanical Doll (IOI18_doll) C++17
37 / 100
 124 ms 14880 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
#define print(x) if (1) {cerr << (#x) << "= [ "; for (auto it : x) cerr << it << ' '; cerr << "]\n";}

using namespace std;

const int N = 3e5 + 64;

int n, m, k = 0, ptr_v = 0, ptr_seq = 0;
int id[4 * N], L[4 * N], R[4 * N];
vector<int> a, C, X, Y;

void dfs(int v, int l, int to) {
	//show(v), show(to);
	if (!id[v])
		id[v] = ++ptr_v, X.pb(to), Y.pb(to);

	if (l == 0) {
		if (L[v] == R[v])
			++L[v], X[id[v] - 1] = (ptr_seq < n ? a[ptr_seq++] : to);
		else
			++R[v], Y[id[v] - 1] = (ptr_seq < n ? a[ptr_seq++] : to);
	}
	else {
		if (L[v] == R[v]) {
			dfs(v << 1, l - 1, to);
			X[id[v] - 1] = -id[v << 1];
			++L[v];
		}
		else {
			dfs(v << 1 | 1, l - 1, to);
			Y[id[v] - 1] = -id[v << 1 | 1];
			++R[v];
		}
	}
}

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

	while ((1 << (k + 1)) <= n)
		++k;

	int last = 1 << (k + 1);

	//show(last);

	for (int i = 0; i < last; ++i)
		dfs(1, k, (i + 1 == last ? 0 : -last));
	assert(ptr_v + 1 == last); 

	C[0] = -last;
	X.pb(-id[1]), Y.pb(-id[1]);
	
	for (int i = 1; i < C.size(); ++i)
		C[i] = -last;

	/*show(k); 
	print(C); print(X); print(Y);*/
	
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 1; i < C.size(); ++i)
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 84 ms 12880 KB Output is partially correct
3 Partially correct 108 ms 12972 KB Output is partially correct
4 Partially correct 87 ms 13596 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 84 ms 12880 KB Output is partially correct
3 Partially correct 108 ms 12972 KB Output is partially correct
4 Partially correct 87 ms 13596 KB Output is partially correct
5 Partially correct 91 ms 14880 KB Output is partially correct
6 Partially correct 98 ms 14548 KB Output is partially correct
7 Partially correct 95 ms 14692 KB Output is partially correct
8 Partially correct 88 ms 14328 KB Output is partially correct
9 Partially correct 82 ms 12972 KB Output is partially correct
10 Partially correct 88 ms 14212 KB Output is partially correct
11 Partially correct 87 ms 13860 KB Output is partially correct
12 Partially correct 83 ms 13044 KB Output is partially correct
13 Partially correct 84 ms 13484 KB Output is partially correct
14 Partially correct 124 ms 13584 KB Output is partially correct
15 Partially correct 86 ms 13740 KB Output is partially correct
16 Partially correct 3 ms 724 KB Output is partially correct
17 Correct 45 ms 7556 KB Output is correct
18 Partially correct 99 ms 13200 KB Output is partially correct
19 Partially correct 82 ms 13036 KB Output is partially correct
20 Partially correct 89 ms 14048 KB Output is partially correct
21 Partially correct 88 ms 13904 KB Output is partially correct
22 Partially correct 112 ms 13860 KB Output is partially correct