제출 #1236373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236373		PlayVoltz	자동 인형 (IOI18_doll)	C++20	84 / 100	92 ms	11012 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()), 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: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56