Submission #296134

#	Time	Username	Problem	Language	Result	Execution time	Memory
296134		errorgorn	Mechanical Doll (IOI18_doll)	C++14	100 / 100	215 ms	14660 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()

const int INF=1e9;

struct sw{
	int l=INF,r=INF;
	int num;
	bool flip=false;
};

int IDX=2;
sw sf[400005];

void simulate(int i){
	int curr=-1;
	while (true){
		sf[-curr].flip^=true;
		if (sf[-curr].flip){
			if (sf[-curr].l==INF){
				sf[-curr].l=i;
				break;
			}
			curr=sf[-curr].l;
		}
		else{
			if (sf[-curr].r==INF){
				sf[-curr].r=i;
				break;
			}
			curr=sf[-curr].r;
		}
	}
}

void create_circuit(int m, vector<int> arr) {
	int n=sz(arr);
	vector<int> dev={arr[0]};
	rep(x,0,m) dev.push_back(-1);
	
	if (sz(arr)==1){
		dev[arr[0]]=0;
		answer(dev,{0},{0});
		return;
	}
	else if (sz(arr)==2){
		answer(dev,{arr[1]},{0});
		return;
	}
	
	arr.erase(arr.begin());
	arr.push_back(0);
	
	sf[1].num=sz(arr);
	vector<int> layer={1};
	
	int ss=1;
	while (ss<sz(arr)) ss<<=1;
	
	while (ss>>=1){
		vector<int> temp;
		for (auto &it:layer){
			sw l,r;
			r.num=min(ss,sf[it].num);
			l.num=sf[it].num-r.num;
			
			//cout<<l.num<<" "<<r.num<<endl;
			
			if (l.num){
				if (ss==1) continue;
				temp.push_back(IDX);
				sf[IDX]=l;
				sf[it].l=-IDX;
				IDX++;
			}
			else{
				sf[it].l=-1;
			}
			if (ss==1) continue;
			temp.push_back(IDX);
			sf[IDX]=r;
			sf[it].r=-IDX;
			IDX++;
		}
		
		layer=temp;
	}
	
	rep(x,0,sz(arr)){
		simulate(arr[x]);
	}
	
	//rep(x,1,IDX) cout<<sf[x].l<<" "; cout<<endl;
	//rep(x,1,IDX) cout<<sf[x].r<<" "; cout<<endl;
	
	vector<int> l,r;
	
	rep(x,1,IDX) l.push_back(sf[x].l);
	rep(x,1,IDX) r.push_back(sf[x].r);
	
	answer(dev,l,r);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:48:6: warning: unused variable 'n' [-Wunused-variable]
   48 |  int n=sz(arr);
      |      ^

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