Submission #82170

#	Time	Username	Problem	Language	Result	Execution time	Memory
82170		KLPP	자동 인형 (IOI18_doll)	C++14	47 / 100	136 ms	8488 KiB

doll

#include "doll.h"
#include<iostream>
#include<vector>
using namespace std;

int reverse(int a,int exp){
	int ans=0;
	while(exp--){ans*=2;
		ans+=a%2;
		a/=2;
	}//cout<<endl;
	return ans;
}

void create_circuit(int M, std::vector<int> A) {vector<int> C(M+1);
	A.push_back(0);
	for(int i=0;i<=M;i++)C[i]=-1;
	C[0]=A[0];
	A.erase(A.begin());
	int N = A.size();
	int pow=1;
	int exp=0;
	while(pow<N){
		pow*=2;
		exp++;
	}
	vector<int> X(pow-1);
	vector<int> Y(pow-1);
	for(int i=0;i<pow/2-1;i++){
		X[i]=2*(-i-1);
		Y[i]=2*(-i-1)-1;
		//cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
	}
	for(int i=pow/2;i<pow;i++){
		int orderX=2*i-pow;
		int orderY=2*i+1-pow;
		//cout<<orderX<<" "<<orderY<<endl;
		//cout<<reverse(orderX,exp)<<endl;
		//cout<<reverse(orderY,exp)<<endl;
		int rX=reverse(orderX,exp);
		int rY=reverse(orderY,exp);
		//cout<<rX<<" "<<rY<<endl;
		if(rX+N>=pow){
			X[i-1]=A[rX-pow+N];
		}else X[i-1]=-1;
		if(rY+N>=pow){
			Y[i-1]=A[rY-pow+N];
		}else Y[i-1]=-1;
	}
	//cout<<pow<<endl;
	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