Submission #1129034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129034		Luvidi	Mechanical Doll (IOI18_doll)	C++20	53 / 100	132 ms	16356 KiB

doll

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

int ls;
vector<int> c,sw[2],st;

int cv(int x){
	return -x-1;
}

void build(int cr,int s){
	if(s==1)return;
	sw[0][cr]=cv(++ls);
	sw[0].push_back(0);sw[1].push_back(0);st.push_back(0);
	build(ls,s-1);
	sw[1][cr]=cv(++ls);
	sw[0].push_back(0);sw[1].push_back(0);st.push_back(0);
	build(ls,s-1);
}

int* sim(int cr,int s){
	st[cr]^=1;
	if(s==1)return &(sw[st[cr]^1][cr]);
	return sim(cv(sw[st[cr]^1][cr]),s-1);
}

void create_circuit(int m, std::vector<int> a) {
	int n=a.size();
	vector<int> ot[m+1];
	ot[0].push_back(a[0]);
	for(int i=0;i<n-1;i++)ot[a[i]].push_back(a[i+1]);
	ot[a[n-1]].push_back(0);
	c.resize(m+1);
	ls=-1;
	for(int i=0;i<=m;i++){
		if(ot[i].empty())c[i]=i;
		else if(ot[i].size()==1){
			c[i]=ot[i][0];
		}else{
			int s=1;
			while((1<<s)<ot[i].size())s++;
			c[i]=cv(++ls);
			sw[0].push_back(0);sw[1].push_back(0);st.push_back(0);
			int sr=ls;
			build(ls,s);
			for(int t=0;t<(1<<s);t++){
				int *x=sim(sr,s);
				if(t<ot[i].size()-1){
					*x=ot[i][t];
				}else if(t==(1<<s)-1){
					*x=ot[i].back();
				}else{
					*x=cv(sr);
				}
			}
		}
	}
	answer(c,sw[0],sw[1]);
}

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