Submission #1236366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236366		PlayVoltz	Mechanical Doll (IOI18_doll)	C++20	66.60 / 100	95 ms	12040 KiB

doll

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int counter=-1;
vector<int> x, y;

vector<pair<pii, int> > dnc(int d, int len){
	vector<pair<pii, int> > res;
	int node=++counter;
	if (!d){
		res.pb(mp(mp(node, 1), 2));
		if (len==2)res.pb(mp(mp(node, 0), 1));
		return res;
	}
	y[node]=-counter-2;
	vector<pair<pii, int> > l, r=dnc(d-1, min(len, 1<<d));
	if (len>(1<<d)){
		x[node]=-counter-2;
		l=dnc(d-1, len-(1<<d));
	}
	for (auto a:l)res.pb(mp(a.fi, a.se*2-1));
	for (auto a:r)res.pb(mp(a.fi, a.se*2));
	return res;
}

bool custom(pair<pii, int> a, pair<pii, int> b){
	return a.se<b.se;
}

void create_circuit(int m, vector<int> vect){
	vect.pb(0);
	vector<int> c(m+1, -1);
	int dep=ceil(log2(vect.size()));
	x.resize(2*vect.size(), -1);
	y.resize(2*vect.size(), -1);
	vector<pair<pii, int> > ord=dnc(dep, vect.size());
	sort(ord.begin(), ord.end(), custom);
	for (int i=0; i<vect.size(); ++i){
		if (ord[i].fi.se)y[ord[i].fi.fi]=vect[i];
		else x[ord[i].fi.fi]=vect[i];
	}
	while (x.back()==-1&&y.back()==-1)x.pop_back(), y.pop_back();
	answer(c, x, y);
}

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