제출 #605702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605702		jairRS	자동 인형 (IOI18_doll)	C++17	6 / 100	80 ms	11412 KiB

doll

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

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

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

	vvi toMap(M + 1, vi());
	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() == 1)
			C[trg] = endpoints[0];
		if (endpoints.size() == 2)
			C[trg] = addSwitch(endpoints[0], endpoints[1]);
		if (endpoints.size() == 3)
		{
			// 0 back 1 2
			int bottom1 = addSwitch(endpoints[0], -(S + 1));
			int bottom2 = addSwitch(endpoints[1], endpoints[2]);
			C[trg] = addSwitch(bottom1, bottom2);
		}
		if (endpoints.size() == 4)
		{
			// 0 2 1 3
			int bottom1 = addSwitch(endpoints[0], endpoints[2]);
			int bottom2 = addSwitch(endpoints[1], endpoints[3]);
			C[trg] = addSwitch(bottom1, bottom2);
		}
	}

	answer(C, X, Y);
}

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