제출 #605767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605767		jairRS	자동 인형 (IOI18_doll)	C++17	0 / 100	0 ms	212 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.push_back(-(S + 1));
			swap(endpoints.back(), endpoints[endpoints.size() - 2]);
		}
		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});
}
*/

컴파일 시 표준 에러 (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: In function 'void create_circuit(int, vi)':
doll.cpp:88:7: warning: unused variable 'endpoints' [-Wunused-variable]
   88 |   vi &endpoints = toMap[trg];
      |       ^~~~~~~~~
doll.cpp:41:7: warning: variable 'buildSwitchTree' set but not used [-Wunused-but-set-variable]
   41 |  auto buildSwitchTree = [&S, &C, &X, &Y, &addSwitch](int trigger, vi &endpoints)
      |       ^~~~~~~~~~~~~~~

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