Submission #1236374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236374		PlayVoltz	Mechanical Doll (IOI18_doll)	C++20	100 / 100	109 ms	11568 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==1){
		res.pb(mp(mp(node, 1), 2));
		if (len!=1)res.pb(mp(mp(node, 0), 1));
		return res;
	}
	y[node]=-counter-2;
	vector<pair<pii, int> > l, r=dnc(d-1, len);
	if (len>(1<<(d-1))){
		x[node]=-counter-2;
		l=dnc(d-1, len-(1<<(d-1)));
	}
	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);
	x.resize(2*vect.size(), -1);
	y.resize(2*vect.size(), -1);
	vector<pair<pii, int> > ord=dnc(32-__builtin_clz(vect.size()-1), 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: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56