Submission #132768

#	Time	Username	Problem	Language	Result	Execution time	Memory
132768		hugo_pm	Mechanical Doll (IOI18_doll)	C++17	47 / 100	179 ms	16524 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)
{
	assert(switchId > 0);
	int sz = sortiesOrd.size();
	assert(sz >= 2);

	int IND = switchId-1;

	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 create_circuit(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);
}

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