Submission #769363

#	Time	Username	Problem	Language	Result	Execution time	Memory
769363		coloboxx	Mechanical Doll (IOI18_doll)	C++17	37 / 100	124 ms	14880 KiB

doll

#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 (stderr)

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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56