Submission #158055

#	Time	Username	Problem	Language	Result	Execution time	Memory
158055		kig9981	Mechanical Doll (IOI18_doll)	C++17	12 / 100	61 ms	6368 KiB

doll

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

int tree[1<<18];
 
void create_circuit(int M, vector<int> A)
{
	int N=A.size()+1, c=-1, SZ=1;
	vector<int> C(M+1,-1), X(1), Y(1), temp;
	A.push_back(0);
	for(;SZ<N;SZ<<=1);
	memset(tree,0x7f,sizeof(tree));
	for(int i=0;i<N;i++) {
		int j=0;
		for(int b=1;b<SZ;b<<=1) {
			j<<=1;
			if((SZ-1-i)&b) j|=1;
		}
		temp.push_back(j);
	}
	sort(temp.begin(),temp.end());
	for(int i=0;i<N;i++) {
		int j=0;
		for(int b=1;b<SZ;b<<=1) {
			j<<=1;
			if(temp[i]&b) j|=1;
		}
		tree[SZ+j]=A[i];
	}
	for(int i=SZ;--i>1;) if(tree[2*i]!=0x7f7f7f7f || tree[2*i+1]!=0x7f7f7f7f) {
		tree[i]=--c;
		X.push_back(tree[2*i]==0x7f7f7f7f ? -1:tree[2*i]);
		Y.push_back(tree[2*i+1]==0x7f7f7f7f ? -1:tree[2*i+1]);
	}
	tree[1]=-1;
	X[0]=tree[2]==0x7f7f7f7f ? -1:tree[2];
	Y[0]=tree[3]==0x7f7f7f7f ? -1:tree[3];
	answer(C,X,Y);
}

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