Submission #1129681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129681		Captain_Georgia	Library (JOI18_library)	C++20	100 / 100	162 ms	424 KiB

library

#include "library.h"

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

void Solve (int N) {
	if (N == 1) {
		Answer ({1});
		return;
	}
	if (N == 2) {
		Answer ({1, 2});
		return;
	}

	vector<int> query(N, 1), border;
	for (int i = 0;i < N;i ++) {
		query [i] = 0;
		int tmp = Query (query);
		query[i] = 1;
		if (tmp == 1) {
			border.push_back (i);
		}
	}
	assert (border.size() == 2);

	vector<int> remaining;
	for (int i = 0;i < N;i ++) {
		query[i] = 0;
		if (i != border[0] && i != border[1]) {
			remaining.push_back (i);
		}
	}

	vector<int> answer;
	answer.push_back(border[0]);

	for (int i = 0;i + 3 < N;i ++) {
		int low = 0, high = remaining.size();
		while (low < high) {
			// cout << low << " " << high << "\n";
			int mid = (low + high) / 2;
			for (int j = 0;j < N;j ++) query[j] = 0;
			for (int j = 0;j < mid;j ++) query[remaining[j]] = 1;

			if (low + 1 == high && low == 0) break;

			int tmp1 = Query (query);
			query[answer[i]] = 1;
			int tmp2 = Query (query);
			if (tmp1 == tmp2) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}
		answer.push_back (remaining[high - 1]);
		remaining.erase (remaining.begin() + high - 1);
	}
	if (remaining.size() > 0) answer.push_back(*remaining.begin());
	answer.push_back(border[1]);
	for (auto &v : answer) v ++;
	Answer (answer);
}

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