Submission #1256325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256325		gelastropod	Library (JOI18_library)	C++20	100 / 100	111 ms	440 KiB

library

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

int sum(vector<int> V) {
	int ans = 0;
	for (int i : V) ans += i;
	return ans;
}

int qry(vector<int> V) {
	if (sum(V) == 0) return 0;
	return Query(V);
}

void Solve(int N) {
	vector<int> ans(N, 0), diffind, unknown;
	for (int i = 0; i < N; i++) unknown.push_back(i);
	for (int _ = 0; _ < (N + 1) / 2; _++) {
		diffind.clear();
		for (int i = 0; i < 10; i++) {
			vector<int> ask1(N, 0), ask2(N, 0);
			for (int j = 0; j < unknown.size(); j++) {
				ask1[unknown[j]] = (bool)(j & (1LL << i));
				ask2[unknown[j]] = !(bool)(j & (1LL << i));
			}
			int res1 = qry(ask1), res2 = qry(ask2);
			if (res1 == res2 + 1) {
				ans[_] += (1LL << i);
				ans[N - 1 - _] += (1LL << i);
			}
			else if (res1 == res2)
				diffind.push_back(i);
		}
		if (diffind.empty()) {
			ans[_] = unknown[ans[_]];
			break;
		}
		if (_) {
			vector<int> ask1(N, 0), ask2(N, 0);
			for (int i = 0; i < unknown.size(); i++) {
				ask1[unknown[i]] = (bool)(i & (1LL << diffind.back()));
				ask2[unknown[i]] = (bool)(i & (1LL << diffind.back()));
			}
			for (int i = 0; i < _; i++) ask1[ans[i]] = 1, ask2[ans[N - 1 - i]] = 1;
			int res1 = qry(ask1), res2 = qry(ask2);
			if (res2 == res1 + 1) ans[_] += (1LL << diffind.back());
			else ans[N - 1 - _] += (1LL << diffind.back());
		}
		else ans[N - 1 - _] += (1LL << diffind.back());
		for (int i = 0; i < diffind.size() - 1; i++) {
			vector<int> ask1(N, 0), ask2(N, 0);
			for (int j = 0; j < unknown.size(); j++) {
				if ((bool)(j & (1LL << diffind[i])) ^ (bool)(j & (1LL << diffind.back()))) ask1[unknown[j]] = 1;
				else ask2[unknown[j]] = 1;
			}
			int res1 = qry(ask1), res2 = qry(ask2);
			if (res1 == res2 - 1) {
				ans[_] += ((bool)(ans[_] & (1LL << diffind.back())) << diffind[i]);
				ans[N - 1 - _] += ((bool)(ans[N - 1 - _] & (1LL << diffind.back())) << diffind[i]);
			}
			else {
				ans[_] += (!(bool)(ans[_] & (1LL << diffind.back())) << diffind[i]);
				ans[N - 1 - _] += (!(bool)(ans[N - 1 - _] & (1LL << diffind.back())) << diffind[i]);
			}
		}
		ans[_] = unknown[ans[_]];
		ans[N - 1 - _] = unknown[ans[N - 1 - _]];
		for (int i = 0; i < unknown.size(); i++) {
			if (unknown[i] == ans[_] || unknown[i] == ans[N - 1 - _]) {
				unknown.erase(unknown.begin() + i);
				i--;
			}
		}
	}
	for (int i = 0; i < N; i++) ans[i]++;
	Answer(ans);
}

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