Submission #1034322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034322		juicy	Library (JOI18_library)	C++17	100 / 100	213 ms	432 KiB

library

#include <bits/stdc++.h>

#include "library.h"

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

void Solve(int N) {
	vector<bool> vs(N);
	vector<int> M(N);
	auto qry = [&](vector<int> &que) {
		fill(M.begin(), M.end(), 0);
		for (int x : que) {
			M[x - 1] = 1;
		}
		return Query(M);
	};
	auto check = [&](vector<int> &que, int x) {
		int a = qry(que);
		que.push_back(x);
		int b = qry(que);
		return b <= a;
	};
	auto search = [&](int x) {
		vector<int> cands;
		for (int i = 0; i < N; ++i) {
			if (!vs[i]) {
				cands.push_back(i + 1);
			}
		}
		if (!cands.size()) {
			return 0;
		}
		int l = 0, r = int(cands.size()) - 1, res = -1;
		while (l <= r) {
			int md = (l + r) / 2;
			vector<int> que;
			for (int i = 0; i <= md; ++i) {
				que.push_back(cands[i]);
			} 
			if (check(que, x)) {
				res = md;
				r = md - 1;
			} else {
				l = md + 1;
			}
		}
		if (res != -1) {
			vs[cands[res] - 1] = 1;
			assert(0 < cands[res] && cands[res] <= N);
			return cands[res];
		}
		return 0;
	};
	if (N == 1) {
		Answer({1});
		return;
	} 
	deque<int> dq;
	vs[0] = 1;
	int l = 1, r = search(1);
	dq.push_front(l);
	dq.push_back(r);
	int cnt = N - 2;
	while (1) {
		l = search(l);
		if (l == 0) {
			break;
		}
		dq.push_front(l);
		--cnt;
	}
	while (cnt > 0) {
		r = search(r);
		dq.push_back(r);
		--cnt;
	}
	Answer(vector<int>(dq.begin(), dq.end()));
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81