Submission #303477

#	Time	Username	Problem	Language	Result	Execution time	Memory
303477		ryansee	Mechanical Doll (IOI18_doll)	C++14	63 / 100	276 ms	12628 KiB

doll

#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	vector<vector<int> > qs(M + 1);
	for(int i = 0; i < N; ++i) {
		qs[A[i]].push_back(i);
	}
	bool subtask3 = true;
	for(int i = 1; i <= M; ++i) {
		if(qs[i].size() >= 5) {
			subtask3 = false;
		}
	}
	if(subtask3) {
		vector<int> C1(M + 1, 0), X1, Y1;
		A.push_back(0);
		C1[0] = A[0];
		for(int i = 1; i <= M; ++i) {
			if(qs[i].size() == 0) continue;
			int ns = X1.size();
			if(qs[i].size() == 1) {
				C1[i] = A[qs[i][0] + 1];
			}
			if(qs[i].size() == 2) {
				C1[i] = -(ns + 1);
				X1.push_back(A[qs[i][0] + 1]);
				Y1.push_back(A[qs[i][1] + 1]);
			}
			if(qs[i].size() == 3) {
				C1[i] = -(ns + 1);
				X1.push_back(-(ns + 2));
				Y1.push_back(-(ns + 3));
				X1.push_back(-(ns + 1));
				Y1.push_back(A[qs[i][1] + 1]);
				X1.push_back(A[qs[i][0] + 1]);
				Y1.push_back(A[qs[i][2] + 1]);
			}
			if(qs[i].size() == 4) {
				C1[i] = -(ns + 1);
				X1.push_back(-(ns + 2));
				Y1.push_back(-(ns + 3));
				X1.push_back(A[qs[i][0] + 1]);
				Y1.push_back(A[qs[i][2] + 1]);
				X1.push_back(A[qs[i][1] + 1]);
				Y1.push_back(A[qs[i][3] + 1]);
			}
		}
		answer(C1, X1, Y1);
		return;
	}
	int bits = 1;
	while((1 << bits) < N) ++bits;
	vector<int> C(M + 1, -1);
	C[0] = A[0];
	vector<int> X((1 << bits) - 1, -1), Y((1 << bits) - 1, -1);
	for(int i = 1; i < 1 << (bits - 1); ++i) {
		X[i - 1] = -(2 * i);
		Y[i - 1] = -(2 * i + 1);
	}
	vector<int> perm;
	for(int i = 1 << bits; i < 2 << bits; ++i) {
		perm.push_back(i);
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) {
		for(int k = 0; k < bits; ++k) {
			if(((i >> k) & 1) != ((j >> k) & 1)) {
				return ((i >> k) & 1) < ((j >> k) & 1);
			}
		}
		return false;
	});
	for(int i = 0; i < 1 << bits; ++i) {
		int tar = i - ((1 << bits) - N);
		if(tar < 0) tar = -1;
		else if(i != ((1 << bits) - 1)) tar = A[tar + 1];
		else tar = 0;
		if(perm[i] % 2 == 0) {
			X[perm[i] / 2 - 1] = tar;
		}
		else {
			Y[perm[i] / 2 - 1] = tar;
		}
	}
	answer(C, X, Y);
}

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