Submission #1094890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094890		4QT0R	Mechanical Doll (IOI18_doll)	C++17	25 / 100	99 ms	25732 KiB

doll

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

int iter;
vector<int> tab[200004];
pair<int,int> swt[300004];

void build(int v, vector<int> now){
	vector<int> sep[2];
	for (int i = 0; i<(int)now.size(); i++)sep[i&1].push_back(now[i]);
	if (sep[0].size()==1)swt[-v].first=sep[0][0];
	else{
		swt[-v].first=--iter;
		build(iter,sep[0]);
	}
	if (sep[1].size()==1)swt[-v].second=sep[1][0];
	else if (sep[1].size()){
		swt[-v].second=--iter;
		build(iter,sep[1]);
	}
}

void create_circuit(int m, vector<int> a){
	a.insert(a.begin(),0);
	a.push_back(0);
	int n=a.size();
	vector<int> trig(m+1,0);

	for (int i = 0; i<n-1; i++)tab[a[i]].push_back(a[i+1]);
	for (int i = 0; i<=m; i++){
		if (tab[i].size()==1)trig[i]=tab[i][0];
		else if (tab[i].size()>1){
			trig[i]=--iter;
			reverse(tab[i].begin(),tab[i].end());
			while(__builtin_popcount(tab[i].size())>1)tab[i].push_back(iter);
			reverse(tab[i].begin(),tab[i].end());
			build(iter,tab[i]);
		}
	}
	vector<int> x(-iter);
	vector<int> y(-iter);
	for (int i = 1; i+iter<=0; i++){
		x[i-1]=swt[i].first;
		y[i-1]=swt[i].second;
	}
	answer(trig,x,y);
}

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