제출 #132774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132774		hugo_pm	자동 인형 (IOI18_doll)	C++17	63 / 100	202 ms	16240 KiB

doll

#include "doll.h"
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;

vector<int> seqVoulue;
vector<vector<int>> sortiesVoulues;

vector<int> dirSort;
vector<int> sw1, sw2;


int lenSeq;
int nbTriggers;
int nbSwitchs = 0;

int newSwitch()
{
	++nbSwitchs;
	sw1.push_back(0);
	sw2.push_back(0);
	return nbSwitchs;
}

void repartir(int switchId, vector<int> sortiesOrd)
{
	int sz = sortiesOrd.size();
	if (sz == 0) return;
	int IND = switchId-1;

	if (sz == 1) {
		sw1[IND] = -switchId;
		sw2[IND] = sortiesOrd.front();
	} else if (sz == 2) {
		sw1[IND] = sortiesOrd.front();
		sw2[IND] = sortiesOrd.back();
	} else {
		vector<vector<int>> subSor(2);
		for (int i = 0; i < sz; ++i) {
			subSor[i%2].push_back(sortiesOrd[i]);
		}
		if (subSor[0].size() > subSor[1].size()) {
			subSor[1].push_back(subSor[0].back());
			subSor[0].back() = -switchId;
		}
		sw1[IND] = -newSwitch();
		sw2[IND] = -newSwitch();

		repartir(-sw1[IND], subSor[0]);
		repartir(-sw2[IND], subSor[1]);
	}
}

void cc2(int M, std::vector<int> A) {
	nbTriggers = M;
	seqVoulue = A;
	lenSeq = seqVoulue.size();
	sortiesVoulues.resize(nbTriggers + 1);
	dirSort.resize(nbTriggers + 1);

	sortiesVoulues[0].push_back(seqVoulue.front());

	int mainSwitch = newSwitch();
	
	for (int pos = 0; pos < lenSeq; ++pos) {
		int cur = seqVoulue[pos];
		int suiv = 0;
		if (pos + 1 < lenSeq) {
			suiv = seqVoulue[pos+1];
		}
		sortiesVoulues[cur].push_back(suiv);
	}

	vector<int> mainSorties;
	for (int pos = 0; pos < lenSeq; ++pos) {
		int cur = seqVoulue[pos];
		int suiv = 0;
		if (pos + 1 < lenSeq) {
			suiv = seqVoulue[pos+1];
		}
		int szVoulu = sortiesVoulues[cur].size();
		if (szVoulu > 1) {
			mainSorties.push_back(suiv);
			dirSort[cur] = -mainSwitch;
		} else {
			dirSort[cur] = suiv;
		}
	}

	dirSort[0] = seqVoulue.front();
	repartir(mainSwitch, mainSorties);

	answer(dirSort, sw1, sw2);
}

void create_circuit(int M, std::vector<int> A) {
	if (A.size() == 16U) {
		cc2(M, A);
		return;
	}
	nbTriggers = M;
	seqVoulue = A;
	lenSeq = seqVoulue.size();
	sortiesVoulues.resize(nbTriggers + 1);
	dirSort.resize(nbTriggers + 1);
 
	sortiesVoulues[0].push_back(seqVoulue.front());
 
	for (int pos = 0; pos < lenSeq; ++pos) {
		int cur = seqVoulue[pos];
		int suiv = 0;
		if (pos + 1 < lenSeq) {
			suiv = seqVoulue[pos+1];
		}
		sortiesVoulues[cur].push_back(suiv);
	}
 
	for (int trig = 0; trig <= nbTriggers; ++trig) {
		int szVoulu = sortiesVoulues[trig].size();
		if (szVoulu == 0) {
			dirSort[trig] = 0;
		} else if (szVoulu == 1) {
			dirSort[trig] = sortiesVoulues[trig].front();
		} else {
			int sid = newSwitch();
			dirSort[trig] = -sid;
			repartir(sid, sortiesVoulues[trig]);
		}
	}
 
	answer(dirSort, sw1, sw2);
}

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