제출 #954495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954495		Alan	Library (JOI18_library)	C++17	100 / 100	153 ms	596 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);
	vector<bool> used (N+1);
	ans[0] = [&] {
		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;
	}();
	used[ans[0]] = true;
	auto none = [&] (vector<int>& q) {
		for (auto& b : q) if (b) return false;
		return true;
	};
	for (int l = 1, r = N-1; l < r; l++, r--) {
		for (int j = 0; (1<<j) <= N; j++) {
			vector<int> q (N);
			for (int k = 0; k < N; k++) if (!used[k+1]) q[k] = !!((k+1) & (1<<j));
			int res = none(q) ? 0 : Query(q);
			for (int k = 0; k < N; k++) if (!used[k+1]) q[k] = !((k+1) & (1<<j));
			int res2 = none(q) ? 0 : Query(q);
			if (res > res2) {
				ans[l] += 1<<j;
				ans[r] += 1<<j;
			} else if (res == res2) {
				q[ans[l-1]-1] = 1;
				for (int k = 0; k < N; k++) if (!used[k+1]) q[k] = !!((k+1) & (1<<j)) ^ !(ans[l-1] & (1<<j));
				int res3 = Query(q);
				ans[l] += ((res == res3) ^ !(ans[l-1] & (1<<j))) << j;
				ans[r] += ((res == res3) ^ !!(ans[l-1] & (1<<j))) << j;
			}
		}
		used[ans[l]] = used[ans[r]] = true;
	}
	if (N % 2 == 0) for (int i = 1; i <= N; i++) if (!used[i]) ans[N/2] = i;
	Answer(ans);
}

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