Submission #954853

#	Time	Username	Problem	Language	Result	Execution time	Memory
954853		Trisanu_Das	Mechanical Doll (IOI18_doll)	C++17	47 / 100	64 ms	22348 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN=400010;
typedef vector<int> vec;
vec G[maxN];
int lv[maxN],no[maxN],tmp=-1;
int ln(int x){
	int cnt=1,s=0;
	while(x>cnt){cnt*=2;s++;}
	return s;
}
void create_circuit(int M, std::vector<int> A){
	int N=A.size(),K=ln(N),SW=(1<<K)-1;
	for(int i=N;i<(1<<K);i++)A.push_back(-1);
	A.push_back(0);
	if (SW<1)SW=1;
	vec C(M+1),X(SW),Y(SW);
	C[0]=A[0];X[0]=-1;Y[0]=0;
	for (int i=1;i<=M;i++)C[i]=-1;
	if (N>1){
		no[1]=1;lv[1]=0;
		for (int i=1;i<(1<<(K-1));i++){
			X[i-1]=-i*2;no[i*2]=no[i];lv[i*2]=lv[i]+1;
			Y[i-1]=-i*2-1;no[i*2+1]=no[i]+(1<<lv[i]);lv[i*2+1]=lv[i]+1;
		}
		for (int i=1<<(K-1);i<=SW;i++){
			X[i-1]=A[no[i]];
			Y[i-1]=A[no[i]+(1<<lv[i])];
		}
	}
	answer(C,X,Y);
}

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