Submission #133411

#	Time	Username	Problem	Language	Result	Execution time	Memory
133411		hugo_pm	Mechanical Doll (IOI18_doll)	C++17	84 / 100	193 ms	14764 KiB

doll

#include "doll.h"
#include <algorithm>
#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();
	int IND = switchId-1;

	if (true) {
		assert(sz % 2 == 0 && sz >= 2);
		vector<vector<int>> subSor(2);

		for (int i = 0; i < sz/2; ++i) {
			subSor[0].push_back(sortiesOrd[i]);
			subSor[1].push_back(sortiesOrd[i + sz/2]);
		}
 
		sw1[IND] = subSor[0].front();
		for (int x : subSor[0]) if (x != sw1[IND]) {
			sw1[IND] = -newSwitch();
			break;
		}

		sw2[IND] = subSor[1].front();
		for (int x : subSor[1]) if (x != sw2[IND]) {
			sw2[IND] = -newSwitch();
			break;
		}

		if (sw1[IND] < -1) repartir(-sw1[IND], subSor[0]);
		if (sw2[IND] < -1) 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;
		}
	}

	int sz = mainSorties.size();
	int bb = 0;
	int x = 1;
	while (x < sz) { x *= 2; ++bb; }
	int theSkips = x-sz;

	sz = x;
	vector<int> rl(sz, -1);

	int curPris = 0;
	for (int tpsVisite = 0; tpsVisite < sz; ++tpsVisite) {
		vector<int> tb(bb, 0);
		for (int iBit = 0; iBit < bb; ++iBit) {
			if ((1 << iBit) & tpsVisite) tb[iBit] = 1;
		}
		int vraiePos = 0;
		for (int w : tb) {
			vraiePos *= 2;
			vraiePos += w;
		}

		if (vraiePos >= theSkips) {
			rl[vraiePos] = mainSorties[curPris++];
		}
	}
	
	dirSort[0] = seqVoulue.front();
	repartir(mainSwitch, rl);

	answer(dirSort, sw1, sw2);
}

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