Submission #1042894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042894		ReLice	Mechanical Doll (IOI18_doll)	C++17	100 / 100	110 ms	9836 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define ll int
#define vll vector<ll>
#define pb push_back
#define sz size()
using namespace std;
void create_circuit(int m, std::vector<int> a) {
	ll i;
	ll n = a.size();
	if(n==1){
		vll c(m+1,0);
		c[0]=a[0];
		answer(c,{},{});
		return;
	}
	vll c(m+1,-1);
	
	c[0]=a[0];
	a.erase(a.begin());
	a.pb(0);
	
	//~ for(auto i : a)cout<<i<<' ';
	//~ cout<<endl;
	
	ll bit=__lg(n);
	if((1ll<<bit) < n)bit++;
	
	vll x,y;
	auto get = [&](){
		x.pb(0);
		y.pb(0);
		return (ll)x.sz;
	};
	
	function<int(int,int,vector<int>)> build = [&](ll l,ll r,vll a){
		if(a.size()==0)return -1;
		if(l==r){
			assert(a.size()==1);
			return a[0];
		}
		ll m=(l+r)/2;
		ll goLeft=max(0,(ll)a.size()-(r-m));
		
		vll toL,toR;
		for(i=0;i<goLeft;i++){
			toL.pb(a[i]);
		}
		for(i=goLeft;i<(ll)a.size();i++){
			toR.pb(a[i]);
		}
		
		ll root=get();
		
		x[root-1]=build(l,m,toL);
		y[root-1]=build(m+1,r,toR);
		
		//~ cout<<-root<<' '<<x[root-1]<<' '<<y[root-1]<<endl;
		
		return -root; 
	};
	
	build(0,(1ll<<bit)-1,a);
	
	vector<bool> f((ll)x.size()+5,0);
	
	function<int(int, int)> simulate = [&](ll root,ll value){
		if(root>=0) return value;
		
		root=-root;
		
		f[root-1]=!f[root-1];
		if(f[root-1]){
			x[root-1]=simulate(x[root-1],value);
		}else{
			y[root-1]=simulate(y[root-1],value);
		}
		
		return -root;
	};
	
	for(i=0;i<n;i++){
		simulate(-1,a[i]);
	}
	
	answer(c, x, y);
}

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