Submission #597078

#	Time	Username	Problem	Language	Result	Execution time	Memory
597078		Lucpp	Mechanical Doll (IOI18_doll)	C++17	53 / 100	163 ms	15436 KiB

doll

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

int S = 0;
vector<int> X, Y;

int build(vector<int> v){
	int n = (int)v.size();
	if(n == 1) return v[0];
	vector<int> le, ri;
	for(int i = 0; i < n; i++){
		if(i%2==0)le.push_back(v[i]);
		else ri.push_back(v[i]);
	}
	int ind = S;
	int res = -(ind+1);
	if(le.size() != ri.size()){
		ri.push_back(le.back());
		le.back() = res;
	}
	S++;
	X.resize(S);
	Y.resize(S);
	X[ind] = build(le);
	Y[ind] = build(ri);
	return res;
}

void create_circuit(int M, vector<int> A) {
	int N = (int)A.size();
	vector<vector<int>> v(M+1);
	v[0].push_back(A[0]);
	for(int i = 0; i < N-1; i++){
		v[A[i]].push_back(A[i+1]);
	}
	v[A.back()].push_back(0);
	vector<int> C(M + 1);
	for(int i = 0; i <= M; i++){
		if(!v[i].empty()) C[i] = build(v[i]);
	}
	answer(C, 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: 28.0000000112 / 56