Submission #954494

# Submission time Handle Problem Language Result Execution time Memory
954494 2024-03-28T04:31:30 Z Alan Library (JOI18_library) C++17
0 / 100
17 ms 344 KB
#include <bits/stdc++.h>
using namespace std;

int Query(const vector<int>& M);
void Answer(const vector<int>& res);

void Solve (int N) {
	vector<int> ans (N);
	vector<bool> used (N+1);
	ans[0] = [&] {
		vector<int> q (N);
		for (int i = 0; i < N; i++) q[i] = 1;
		for (int i = 0; i < N-1; i++) {
			q[i] = 0;
			if (Query(q) == 1) return i+1;
			q[i] = 1;
		}
		return N;
	}();
	used[ans[0]] = true;
	auto none = [&] (vector<int>& q) {
		for (auto& b : q) if (b) return false;
		return true;
	};
	for (int l = 1, r = N-1; l < r; l++, r--) {
		for (int j = 0; (1<<j) <= N; j++) {
			vector<int> q (N);
			for (int k = 0; k < N; k++) if (!used[k+1]) q[k] = !!((k+1) & (1<<j));
			if (none(q)) continue;
			int res = Query(q);
			for (int k = 0; k < N; k++) if (!used[k+1]) q[k] = !((k+1) & (1<<j));
			if (none(q)) continue;
			int res2 = Query(q);
			if (res > res2) {
				ans[l] += 1<<j;
				ans[r] += 1<<j;
			} else if (res == res2) {
				q[ans[l-1]-1] = 1;
				for (int k = 0; k < N; k++) if (!used[k+1]) q[k] = !!((k+1) & (1<<j)) ^ !(ans[l-1] & (1<<j));
				int res3 = Query(q);
				ans[l] += ((res == res3) ^ !(ans[l-1] & (1<<j))) << j;
				ans[r] += ((res == res3) ^ !!(ans[l-1] & (1<<j))) << j;
			}
		}
		used[ans[l]] = used[ans[r]] = true;
	}
	if (N % 2 == 0) for (int i = 1; i <= N; i++) if (!used[i]) ans[N/2] = i;
	Answer(ans);
}
# Verdict Execution time Memory Grader output
1 Correct 17 ms 344 KB # of queries: 1895
2 Incorrect 17 ms 344 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 17 ms 344 KB # of queries: 1895
2 Incorrect 17 ms 344 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -