제출 #297780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297780		ChrisT	자동 인형 (IOI18_doll)	C++17	37 / 100	108 ms	8500 KiB

doll

#include <bits/stdc++.h> 
#include "doll.h"
using namespace std;
const int MN = 2e5 + 3;
void create_circuit (int m, vector<int> a) {
	a.push_back(0);
	int n = (int)a.size(), go = 1 << (__lg(n - 1) + 1), cur = 1; ++m;
	vector<int> c(m), x(1), y(1);
	iota(c.begin(),c.end(),0); c[0] = -1;
	auto build = [&] (int l, int r, int ind, int dep, const auto &ref) -> int {
		if (l == r) {
			if (ind - go + n < 0) return -1;
			c[a[ind-go+n]] = -1;
			return a[ind-go+n];
		}
		int mid = (l + r) / 2;
		int lc = ref(l,mid,ind,dep+1,ref), rc = ref(mid+1,r,ind | (1 << dep),dep+1,ref);
		if (lc == rc) return lc;
		x.push_back(lc); y.push_back(rc);
		return -(++cur);
	};
	x[0] = build(0,go/2-1,0,1,build); y[0] = build(go/2,go-1,1,1,build);
	answer(c,x,y);
}

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