제출 #295768

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

doll

#include "doll.h"

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

#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

struct sw{
	int l,r;
	bool flip=false;
	
	sw(){}
	sw(int _l,int _r){
		l=_l,r=_r;
	}
};

int IDX=2;
sw switches[400005];

void create_circuit(int m, vector<int> arr) {
	vector<int> dev={arr[0]};
	rep(x,0,m) dev.push_back(-1);
	
	if (sz(arr)==1){
		answer(dev,{},{});
		return;
	}
	else if (sz(arr)==2){
		answer(dev,{arr[1]},{0});
		return;
	}
	
	switches[1]=sw(arr[1],arr[2]);
	
	int ss=1;
	while (ss<sz(arr)) ss<<=1;
	while (sz(arr)<ss) arr.push_back(-1);
	arr.push_back(0);
	
	rep(x,3,sz(arr)){
		int curr=1;
		
		while (true){
			switches[curr].flip^=true;
			if (switches[curr].flip){
				if (switches[curr].l<0) curr=-switches[curr].l;
				else{
					switches[IDX]=sw(switches[curr].l,arr[x]);
					switches[curr].l=-IDX;
					IDX++;
					break;
				}
			}
			else{
				if (switches[curr].r<0) curr=-switches[curr].r;
				else{
					switches[IDX]=sw(switches[curr].r,arr[x]);
					switches[curr].r=-IDX;
					IDX++;
					break;
				}
			}
		}
	}
	
	vector<int> l;
	vector<int> r;
	
	rep(x,1,IDX) l.push_back(switches[x].l);
	rep(x,1,IDX) r.push_back(switches[x].r);
	
	//rep(x,1,IDX) cout<<switches[x].l<<" "<<switches[x].r<<endl;
	
	answer(dev,l,r);
}

• 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