Submission #605762

#	Time	Username	Problem	Language	Result	Execution time	Memory
605762		jairRS	Mechanical Doll (IOI18_doll)	C++17	6 / 100	64 ms	19224 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

void arrangeEndpoints(vi &endpoints)
{
	if (endpoints.size() == 2)
		return;

	vi half1, half2;
	for (int i = 0; i < endpoints.size(); i++)
	{
		if (i % 2 == 0)
			half1.push_back(endpoints[i]);
		else
			half2.push_back(endpoints[i]);
	}
	arrangeEndpoints(half1);
	arrangeEndpoints(half2);
	for (int x : half2)
		half1.push_back(x);
	endpoints = half1;
}

void create_circuit(int M, vi A)
{
	int N = A.size(), S = 0;
	A.push_back(0);
	vi C(M + 1, 0), X(S), Y(S);

	auto addSwitch = [&S, &X, &Y](int x, int y)
	{
		S++;
		X.push_back(x);
		Y.push_back(y);
		return -S;
	};

	auto buildSwitchTree = [&S, &C, &X, &Y, &addSwitch](int trigger, vi &endpoints)
	{
		if (endpoints.size() == 1)
			return C[trigger] = endpoints[0];
		if (endpoints.size() == 2)
			return C[trigger] = addSwitch(endpoints[0], endpoints[1]);
		// treeSize = power2*2 - 1
		// tree Ids in [1, power2*2 - 1]
		// switch Ids in [S + 1, S + power2*2 - 1]
		int power2 = 1;
		while (power2 < endpoints.size())
			power2 *= 2;
		while (endpoints.size() < power2)
			endpoints.insert(endpoints.end() - 1, -(S + 1));
		arrangeEndpoints(endpoints);

		C[trigger] = -(S + 1);
		for (int i = 1; i <= power2 - 1; i++)
		{
			int left = i * 2, right = i * 2 + 1;
			if (right <= power2 - 1)
			{
				X.push_back(-(S + left));
				Y.push_back(-(S + right));
			}
			else
			{
				left -= power2;
				right -= power2;
				X.push_back(endpoints[left]);
				Y.push_back(endpoints[right]);
			}
		}

		S += power2 - 1;
	};

	vvi toMap(M + 1, vi(0));
	toMap[0].push_back(A[0]);
	for (int i = 0; i < N; i++)
		toMap[A[i]].push_back(A[i + 1]);

	for (int trg = 0; trg <= M; trg++)
	{
		vi &endpoints = toMap[trg];
		if (endpoints.size() != 0)
			buildSwitchTree(trg, endpoints);
	}

	answer(C, X, Y);
}

/*
int main()
{
	create_circuit(6, {3, 1, 2, 3, 3, 4, 3, 1, 5, 6, 5, 6, 1, 2, 3, 4, 5, 5});
}
*/

Compilation message (stderr)

doll.cpp: In function 'void arrangeEndpoints(vi&)':
doll.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < endpoints.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~
doll.cpp: In lambda function:
doll.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   while (power2 < endpoints.size())
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~
doll.cpp:53:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |   while (endpoints.size() < power2)
      |          ~~~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp:75:5: warning: control reaches end of non-void function [-Wreturn-type]
   75 |   S += power2 - 1;
      |   ~~^~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56