제출 #1217962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217962		The_Samurai	Library (JOI18_library)	C++20	100 / 100	121 ms	424 KiB

library

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

void Solve(int n) {
	vector<int> v = {1}, left;
	for (int i = 2; i <= n; i++) {
		vector<int> m(n);
		m[i - 1] = true;
		for (int x: v) m[x - 1] = true;
		if (Query(m) == 1) {
			if (v.size() == 1) v.emplace_back(i);
			else {
				m[v.back() - 1] = false;
				if (Query(m) == 1) v.insert(v.begin(), i);
				else v.emplace_back(i);
			}
		} else {
			left.emplace_back(i);
		}
	}
	// for (int x: v) cout << x << ' ';
	// cout << endl;
	for (int t = 0; t < 2; t++) {
		while (!left.empty()) {
			int lx = 0, rx = left.size() - 1, best = -1;
			while (lx <= rx) {
				int mid = (lx + rx) >> 1;
				vector<int> m(n);
				for (int x: v) m[x - 1] = 1;
				for (int i = 0; i <= mid; i++) m[left[i] - 1] = 1;
				int old = Query(m);
				m[v.back() - 1] = 0;
				if (old != Query(m)) {
					best = mid;
					rx = mid - 1;
				} else {
					lx = mid + 1;
				}
			}
			if (best == -1) break;
			v.emplace_back(left[best]);
			left.erase(left.begin() + best);
		}
		reverse(v.begin(), v.end());
	}
	Answer(v);
}

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