oj.uz

Submission #133412

# Submission time Handle Problem Language Result Execution time Memory
133412 2019-07-20T14:40:51 Z hugo_pm Mechanical Doll (IOI18_doll) C++17
100 / 100
 182 ms 16868 KB 
#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();
	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 {
		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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 42 ms 6540 KB Output is correct
3 Correct 35 ms 5424 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 41 ms 8004 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 42 ms 6540 KB Output is correct
3 Correct 35 ms 5424 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 41 ms 8004 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 112 ms 11264 KB Output is correct
9 Correct 98 ms 12260 KB Output is correct
10 Correct 176 ms 16868 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 42 ms 6540 KB Output is correct
3 Correct 35 ms 5424 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 41 ms 8004 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 112 ms 11264 KB Output is correct
9 Correct 98 ms 12260 KB Output is correct
10 Correct 176 ms 16868 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 172 ms 14912 KB Output is correct
15 Correct 121 ms 11712 KB Output is correct
16 Correct 172 ms 13960 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 170 ms 16236 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 39 ms 5440 KB Output is correct
3 Correct 52 ms 7996 KB Output is correct
4 Correct 62 ms 9340 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 39 ms 5440 KB Output is correct
3 Correct 52 ms 7996 KB Output is correct
4 Correct 62 ms 9340 KB Output is correct
5 Correct 167 ms 14820 KB Output is correct
6 Correct 173 ms 14212 KB Output is correct
7 Correct 166 ms 13860 KB Output is correct
8 Correct 182 ms 13672 KB Output is correct
9 Correct 98 ms 9724 KB Output is correct
10 Correct 155 ms 12980 KB Output is correct
11 Correct 156 ms 12852 KB Output is correct
12 Correct 124 ms 9956 KB Output is correct
13 Correct 103 ms 8200 KB Output is correct
14 Correct 130 ms 11660 KB Output is correct
15 Correct 134 ms 11976 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 89 ms 7460 KB Output is correct
18 Correct 90 ms 7260 KB Output is correct
19 Correct 107 ms 10260 KB Output is correct
20 Correct 150 ms 13044 KB Output is correct
21 Correct 149 ms 12544 KB Output is correct
22 Correct 168 ms 12676 KB Output is correct