제출 #954368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954368		Alan	도서관 (JOI18_library)	C++17	0 / 100	15 ms	436 KiB

library

#include <bits/stdc++.h>
using namespace std;

int Query(const vector<int>& M);
void Answer(const vector<int>& res);

void Solve (int N) {
	vector<int> ans (N);
	ans[N-1] = [&] {
		vector<int> q (N);
		for (int i = 0; i < N; i++) q[i] = 1;
		for (int i = 0; i < N-1; i++) {
			q[i] = 0;
			if (Query(q) == 1) return i+1;
			q[i] = 1;
		}
		return N;
	}();
	vector<int> hv;
	vector<bool> used (N+1);
	for (int i = 1; i <= N; i++) hv.push_back(i);
	for (int i = 0; i < N-2; i++) {
		int l = 0, r = hv.size();
		while (l+1 < r) {
			int mid = (l+r)/2;
			vector<int> q (N);
			for (int j = 0; j < mid; j++) q[hv[j]-1] = 1;
			int res = Query(q);
			for (int j = 0; j < N; j++) q[j] = 0;
			for (int j = mid; j < r; j++) q[hv[j]-1] = 1;
			int res2 = Query(q);
			if (res > res2) r = mid; 
			else if (res < res2) l = mid;
			else {
				bool left = false;
				for (int j = 0; j < mid; j++) if (hv[j] == ans[N-1]) left = true;
				if (left) l = mid;
				else r = mid;
			}
		}
		ans[i] = hv[l];
		used[ans[i]] = true;
		swap(hv[l], hv.back());
		hv.pop_back();
	}
	for (int i = 1; i <= N; i++) if (!used[i]) ans[N-2] = i;
	Answer(ans);
}

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