oj.uz

Submission #132768

# Submission time Handle Problem Language Result Execution time Memory
132768 2019-07-19T13:54:10 Z hugo_pm Mechanical Doll (IOI18_doll) C++17
47 / 100
 179 ms 16524 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 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 2 ms 204 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 75 ms 7136 KB Output is correct
3 Partially correct 128 ms 12088 KB Output is partially correct
4 Partially correct 150 ms 13736 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 75 ms 7136 KB Output is correct
3 Partially correct 128 ms 12088 KB Output is partially correct
4 Partially correct 150 ms 13736 KB Output is partially correct
5 Partially correct 173 ms 16524 KB Output is partially correct
6 Partially correct 179 ms 15056 KB Output is partially correct
7 Partially correct 161 ms 15404 KB Output is partially correct
8 Partially correct 150 ms 14488 KB Output is partially correct
9 Partially correct 126 ms 12036 KB Output is partially correct
10 Partially correct 145 ms 13764 KB Output is partially correct
11 Partially correct 151 ms 14392 KB Output is partially correct
12 Partially correct 130 ms 10744 KB Output is partially correct
13 Correct 84 ms 8212 KB Output is correct
14 Partially correct 137 ms 14192 KB Output is partially correct
15 Partially correct 139 ms 14552 KB Output is partially correct
16 Partially correct 6 ms 716 KB Output is partially correct
17 Correct 89 ms 7236 KB Output is correct
18 Correct 76 ms 7024 KB Output is correct
19 Partially correct 130 ms 11604 KB Output is partially correct
20 Partially correct 159 ms 13576 KB Output is partially correct
21 Partially correct 137 ms 14080 KB Output is partially correct
22 Partially correct 140 ms 13264 KB Output is partially correct