Submission #1274811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274811		nicolo_010	Mechanical Doll (IOI18_doll)	C++20	53 / 100	56 ms	13964 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int gen(vector<int> &after, vector<int> &X, vector<int> &Y, int &S) {
	int sz = after.size();
	if (sz == 0) {
		return 0;
	}
	if (sz == 1) {
		return after[0];
	}
	else {
		int b = 0;
		while ((1<<b) < sz) {
			b++;
		}
		int pw = (1<<b);
		vector<int> bits(pw);
		for (int i=0; i<pw; i++) {
			bits[i] = (bits[i/2])/2 | ((i&1) << (b-1));
		}

		int id = --S;
		for (int i=0; i<(pw-1)/2; i++) {
			X.push_back(--S);
			Y.push_back(--S);
		}
		for (int i=0; i<pw; i++) {
			vector<int> &aux = (i%2 ? Y : X);
			if (bits[i] < (pw-sz)) {
				aux.push_back(id);
			}
			else {
				aux.push_back(after[bits[i] - (pw-sz)]);
			}
		}
		return id;
	}
}

void create_circuit(int M, std::vector<int> A) {
	A.push_back(0);
	int N = A.size();
	vector<int> C(M+1);
	vector<int> X, Y;
	vector<vector<int>> after(M+1);
	for (int i=0; i<N; i++) {
		after[A[i]].push_back(A[(i+1)%N]);
	}
	int S=0;
	for (int i=0; i<M+1; i++) {
		C[i] = gen(after[i], X, Y, S);
	}
	answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56