Submission #1161188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161188		Pwo	Library (JOI18_library)	C++20	100 / 100	113 ms	468 KiB

library

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

int n;
vector<int> lf;

int f(int j, int l, int r) {
	if (l == r) return lf[l];
	int m = (l + r) / 2;
	vector<int> q(n, 0);
	for (int i = l; i <= m; i++)
		q[lf[i]] = 1;
	q[j] = 0;
	int r1;
	if (lf[l] == j && lf[m] == j) r1 = 0;
	else r1 = Query(q);
	q[j] = 1;
	int r2 = Query(q);
	
	if (r2 <= r1) return f(j, l, m);
	return f(j, m + 1, r);
}

void Solve(int N) {
	n = N; int st = -1;
	if (n == 1) {
		Answer(vector<int>{1});
		return;
	}
	vector<int> q(n, 1);
	for (int i = 0; i < N; i++) {
		q[i] = 0;
		int res = Query(q);
		if (res == 1) {
			st = i;
			break;
		}
		q[i] = 1;
	}
	
	for (int i = 0; i < N; i++) lf.push_back(i);
	lf.erase(remove(lf.begin(), lf.end(), st), lf.end());
	
	vector<int> ans{st + 1};
	for (int i = 1; i < N; i++) {
		st = f(st, 0, lf.size() - 1);
		ans.push_back(st + 1);
		lf.erase(remove(lf.begin(), lf.end(), st), lf.end());
	}

	Answer(ans);
}

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