제출 #294999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294999		kshitij_sodani	자동 인형 (IOI18_doll)	C++14	47 / 100	179 ms	13256 KiB

doll

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
#define mp make_pair
typedef long long llo;

#include "doll.h"
//vector<int> pre[100001];
//vector<int> adj[100001];
vector<int> ac;
vector<int> x;
vector<int> y;
int cur=0;
pair<int,int> adj[1000001];
int stt[1000001];
void con(int ind,int tot,int dd){

	if(ind==tot-1){
	}
	else{
		adj[-dd]={-cur+1,-cur+2};

		x[-dd-1]=cur-1;
		y[-dd-1]=cur-2;
		x.pb(0);
		x.pb(0);
		y.pb(0);
		y.pb(0);
		

		cur--;
		cur--;
		int ba=cur;
		con(ind+1,tot,cur+1);
		con(ind+1,tot,ba);
	}
}
void create_circuit(int m, vector<int> aa) {
	int n=aa.size();
	
	for(int i=0;i<=m;i++){
		ac.pb(-1);
	}
	ac[0]=aa[0];
	int xx=n;
	aa.pb(0);
	int dep=0;
	for(int j=0;j<=19;j++){
		if((1<<j)>=xx){
			dep=j;
			break;
		}
	}
	cur--;
	x.pb(0);
	y.pb(0);
	con(0,dep,cur);
	int op=(1<<dep);
	int ind2=1;
	//continue;
	for(int j=0;j<(1<<dep);j++){
		int st=1;
		//cout<<j<<",,"<<endl;
		for(int jj=0;jj<dep-1;jj++){
			if(stt[st]==0){
				stt[st]=1-stt[st];
				st=adj[st].a;
			}
			else{
				stt[st]=1-stt[st];
				st=adj[st].b;
			}
			
		}
		op--;
		if(op<n){
			if(stt[st]==0){
				x[st-1]=aa[ind2];
			}
			else{
				y[st-1]=aa[ind2];
			}
			stt[st]=1-stt[st];
			ind2++;
		}
		else{
			if(stt[st]==0){
				x[st-1]=-1;
			}
			else{
				y[st-1]=-1;
			}
			stt[st]=1-stt[st];
		}
	}

	
	/*while(x.size()>-cur){
		x.pop_back();
	}
	while(y.size()>-cur){
		y.pop_back();
	}*/
	
	/*for(auto j:ac){
		cout<<j<<",";
	}
	cout<<endl;
	for(auto j:x){
		cout<<j<<",";
	}
	cout<<endl;
	for(auto j:y){
		cout<<j<<",";
	}
	cout<<endl;*/

	answer(ac,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