Submission #295218

#	Time	Username	Problem	Language	Result	Execution time	Memory
295218		SeDunion	Mechanical Doll (IOI18_doll)	C++14	100 / 100	130 ms	11888 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1<<19;
int t[MAXN], id[MAXN];


void create_circuit(int M, vector<int> A) {
	A.push_back(0);
	int N = A.size();
	int l = 1;
	while (l < N) l<<=1;
	for (int i = 0 ; i < l ; ++ i) t[i+l] = MAXN;
	for (int i = 0, j = 0 ; i < l ; ++ i) {
		id[i] = id[i>>1];
		if (i&1) id[i] |= l;
		id[i] >>= 1;
		if (id[i] >= l-N) t[id[i]+l] = A[j++];
	}
	vector<int> X, Y;
	int r = 0;
	for (int i = l ; --i ; ) {
		int L = i<<1, R = i<<1|1;
		if (t[L] != t[R]) {
			t[i] = --r;
			X.push_back (t[L]);
			Y.push_back (t[R]);
		} else {
			t[i] = t[L];
		}
	}
	for (int i = 0 ; i < abs(r) ; ++ i) {
		if (X[i] == MAXN) X[i] = t[1];
		if (Y[i] == MAXN) Y[i] = t[1];
	}
	vector<int> C(M+1, t[1]);
	// for(int i:C)cout<<i<<" ";cout<<"\n";
	// for(int i:X)cout<<i<<" ";cout<<"\n";
	// for(int i:Y)cout<<i<<" ";cout<<"\n";
	answer (C, X, Y);
}

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