Submission #1306841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306841		KickingKun	Library (JOI18_library)	C++20	100 / 100	112 ms	492 KiB

library

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

int N;

vector <int> merge(vector <int> A, vector <int> B) {
	vector <int> ask(N); ask[A.back()] = ask[B.front()] = 1;
	if (Query(ask) == 1) {
		for (int x: B) A.emplace_back(x);
		return A;
	}
	
	ask[B.front()] = 0; ask[B.back()] = 1;
	if (Query(ask) == 1) {
		reverse(B.begin(), B.end());
		for (int x: B) A.emplace_back(x);
		return A;
	}

	ask[A.back()] = 0; ask[A.front()] = 1;
	if (Query(ask) == 1) {
		for (int x: A) B.emplace_back(x);
		return B;
	}

	reverse(B.begin(), B.end());
	for (int x: A) B.emplace_back(x);
	return B;
}

void Solve(int n) {
	N = n; vector <vector <int>> group(N);
	for (int i = 0; i < N; i++)
		group[i].emplace_back(i);

	for (int times = 1; times < N; times++) {
		int posL = 0, posR = group.size() - 1;
		int low = 1, high = group.size() - 2;
		while (low <= high) {
			int mid = (low + high) >> 1;
			vector <int> ask(N);
			for (int i = 0; i <= mid; i++)
				for (int p: group[i]) ask[p] = 1;

			if (Query(ask) == mid + 1) low = mid + 1;
			else high = (posR = mid) - 1; 
		}

		low = 1, high = posR - 1;
		while (low <= high) {
			int mid = (low + high) >> 1;
			vector <int> ask(N);
			for (int i = mid; i <= posR; i++)
				for (int p: group[i]) ask[p] = 1;
			
			if (Query(ask) == posR - mid + 1) high = mid - 1;
			else low = (posL = mid) + 1;
		}

		group[posL] = merge(group[posL], group[posR]);
		swap(group[posR], group.back()); group.pop_back();
	}

	// cerr << "Array: ";
	for (int &x: group[0]) {
		++x;
		// cerr << x << ' ';
	}

	Answer(group[0]);
} // Queries: 3(N - 1) + 2NlogN -> trung binh thap hon nhieu

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