oj.uz

Submission #132769

# Submission time Handle Problem Language Result Execution time Memory
132769 2019-07-19T13:56:10 Z hugo_pm Mechanical Doll (IOI18_doll) C++17
47 / 100
 249 ms 262148 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)
{
	int sz = sortiesOrd.size();
	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 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 249 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 262148 KB Execution killed with signal 9
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 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 240 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 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 88 ms 7112 KB Output is correct
3 Partially correct 125 ms 12048 KB Output is partially correct
4 Partially correct 138 ms 13720 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 88 ms 7112 KB Output is correct
3 Partially correct 125 ms 12048 KB Output is partially correct
4 Partially correct 138 ms 13720 KB Output is partially correct
5 Partially correct 180 ms 16748 KB Output is partially correct
6 Partially correct 165 ms 15024 KB Output is partially correct
7 Partially correct 165 ms 15380 KB Output is partially correct
8 Partially correct 174 ms 14492 KB Output is partially correct
9 Partially correct 123 ms 12136 KB Output is partially correct
10 Partially correct 146 ms 13840 KB Output is partially correct
11 Partially correct 147 ms 14412 KB Output is partially correct
12 Partially correct 145 ms 10796 KB Output is partially correct
13 Correct 89 ms 8240 KB Output is correct
14 Partially correct 141 ms 14172 KB Output is partially correct
15 Partially correct 144 ms 14672 KB Output is partially correct
16 Partially correct 5 ms 716 KB Output is partially correct
17 Correct 79 ms 7276 KB Output is correct
18 Correct 81 ms 7088 KB Output is correct
19 Partially correct 153 ms 11684 KB Output is partially correct
20 Partially correct 147 ms 13548 KB Output is partially correct
21 Partially correct 177 ms 14088 KB Output is partially correct
22 Partially correct 165 ms 13196 KB Output is partially correct