Submission #1225256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225256		chaeryeong	Library (JOI18_library)	C++20	100 / 100	60 ms	456 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
void Solve(int N)
{
	auto Query2 = [&] (int x, int y) -> bool {
		vector <int> P(N, 0);
		P[x] = P[y] = 1;
		return Query(P) == 1;
	};
	vector <vector <int>> comps;
	for (int i = 0; i < N; i++) {
		vector <int> P(N, 0);
		for (int j = 0; j <= i; j++) {
			P[j] = 1;
		}
		int x = Query(P);
		if (x == (int)comps.size() + 1) {
			comps.push_back({i});
			continue;
		}
		if (x == (int)comps.size()) {
			int l = 0, r = (int)comps.size() - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				vector <int> Q(N, 0);
				for (int j = 0; j <= mid; j++) {
					for (auto k : comps[j]) {
						Q[k] = 1;
					}
				}
				Q[i] = 1;
				if (Query(Q) == (mid + 1)) {
					r = mid - 1; ans = mid;
				} else {
					l = mid + 1;
				}
			}
			if (Query2(i, comps[ans].back())) {
				comps[ans].push_back(i);
			} else {
				comps[ans].insert(comps[ans].begin(), i);
			}
			continue;
		}
		int l = 0, r = (int)comps.size() - 1, ans = -1, ans2 = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			vector <int> Q(N, 0);
			for (int j = 0; j <= mid; j++) {
				for (auto k : comps[j]) {
					Q[k] = 1;
				}
			}
			Q[i] = 1;
			if (Query(Q) == (mid + 1) - 1) {
				r = mid - 1; ans = mid;
			} else {
				l = mid + 1;
			}
		}
		l = 0, r = ans - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			vector <int> Q(N, 0);
			for (int j = 0; j <= mid; j++) {
				for (auto k : comps[j]) {
					Q[k] = 1;
				}
			}
			Q[i] = 1;
			if (Query(Q) == (mid + 1)) {
				r = mid - 1; ans2 = mid;
			} else {
				l = mid + 1;
			}
		}
		vector <int> v = {i};
		if (!Query2(comps[ans][0], i)) {
			reverse(comps[ans].begin(), comps[ans].end());
		}
		for (auto i : comps[ans]) {
			v.push_back(i);
		}
		reverse(v.begin(), v.end());
		if (!Query2(comps[ans2][0], i)) {
			reverse(comps[ans2].begin(), comps[ans2].end());
		}
		for (auto i : comps[ans2]) {
			v.push_back(i);
		}
		comps.erase(comps.begin() + ans);
		comps.erase(comps.begin() + ans2);
		comps.push_back(v);
	}
	for (auto &i : comps.back()) {
		i++;
	}
	Answer(comps.back());
}

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