제출 #231057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231057		islingr	Mechanical Doll (IOI18_doll)	C++14	100 / 100	145 ms	13180 KiB

doll

// So annoying to implement
#include "doll.h"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
 
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
 
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define eb(x...) emplace_back(x)
#define sz(x) int((x).size())
 
using vi = vector<int>;
 
const int inf = 1e9;

vi x, y;

int p(const int& x) {
	int ret = 0;
	while ((1 << ret) < x) ++ret;
	return ret;
}

int cntr = 1;
template<class it>
void f(it st, it en, int i, int d, const vi &a) {
	int l = en - st;
	if (d == 1) {
		assert(l == 1 || l == 2);
		x[i] = l == 1 ? -1 : a[*(en - 2)];
		y[i] = a[*(en - 1)];
	} else if (p(l) == d) {
		int r = 1 << (d - 1);
		y[i] = -++cntr;
		f(en - r, en, cntr, d - 1, a);
		x[i] = -++cntr;
		f(st, en - r, cntr, d - 1, a);
	} else {
		assert(p(l) < d);
		y[i] = -++cntr;
		f(st, en, cntr, d - 1, a);
		x[i] = -1;
	}
}

void create_circuit(int m, vi a) {
	a.eb(0); int n = a.size();
 
	int k = p(n), sz = 1 << k;
	vi rev(sz);
	rep(i, 0, sz) rev[i] = rev[i >> 1] >> 1 | (i & 1) << (k - 1);
	reverse(all(rev));
	rev.resize(n);
	reverse(all(rev));
	vi tmp(rev); sort(all(tmp));
	trav(x, rev) x = lb(all(tmp), x) - begin(tmp);
	
	x.resize(2 * sz, inf); y.resize(2 * sz, inf);
	f(all(rev), 1, k, a);
	while (x.back() == inf) x.pop_back();
	while (y.back() == inf) y.pop_back();
	x.erase(begin(x)); y.erase(begin(y));
	
	vi c(m + 1); sort(all(a));
	c[0] = -1;
	rep(i, 0, m) c[i + 1] = binary_search(all(a), i + 1) ? -1 : 0;
	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