제출 #300020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
300020		square1001	자동 인형 (IOI18_doll)	C++14	49 / 100	314 ms	10280 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();
	bool subtask1 = true;
	vector<int> SA = A;
	sort(SA.begin(), SA.end());
	for(int i = 1; i < N; ++i) {
		if(SA[i] == SA[i - 1]) {
			subtask1 = false;
		}
	}
	if(subtask1) {
		vector<int> C1(M + 1, 0);
		C1[0] = A[0];
		for(int i = 0; i < N - 1; ++i) {
			C1[A[i]] = A[i + 1];
		}
		C1[A[N - 1]] = 0;
		answer(C1, vector<int>(), vector<int>());
		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), Y((1 << bits) - 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: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56