Submission #954495

# Submission time Handle Problem Language Result Execution time Memory
954495 2024-03-28T04:35:46 Z Alan Library (JOI18_library) C++17
100 / 100
153 ms 596 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));
			int res = none(q) ? 0 : Query(q);
			for (int k = 0; k < N; k++) if (!used[k+1]) q[k] = !((k+1) & (1<<j));
			int res2 = none(q) ? 0 : 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 21 ms 344 KB # of queries: 1899
2 Correct 15 ms 344 KB # of queries: 1953
3 Correct 19 ms 344 KB # of queries: 2096
4 Correct 17 ms 344 KB # of queries: 2059
5 Correct 15 ms 344 KB # of queries: 1995
6 Correct 13 ms 344 KB # of queries: 2031
7 Correct 17 ms 344 KB # of queries: 2057
8 Correct 16 ms 344 KB # of queries: 1929
9 Correct 13 ms 344 KB # of queries: 2031
10 Correct 8 ms 344 KB # of queries: 1258
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 69
16 Correct 2 ms 344 KB # of queries: 172
# Verdict Execution time Memory Grader output
1 Correct 21 ms 344 KB # of queries: 1899
2 Correct 15 ms 344 KB # of queries: 1953
3 Correct 19 ms 344 KB # of queries: 2096
4 Correct 17 ms 344 KB # of queries: 2059
5 Correct 15 ms 344 KB # of queries: 1995
6 Correct 13 ms 344 KB # of queries: 2031
7 Correct 17 ms 344 KB # of queries: 2057
8 Correct 16 ms 344 KB # of queries: 1929
9 Correct 13 ms 344 KB # of queries: 2031
10 Correct 8 ms 344 KB # of queries: 1258
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 69
16 Correct 2 ms 344 KB # of queries: 172
17 Correct 152 ms 344 KB # of queries: 13408
18 Correct 139 ms 344 KB # of queries: 12617
19 Correct 143 ms 344 KB # of queries: 12779
20 Correct 138 ms 344 KB # of queries: 12035
21 Correct 134 ms 344 KB # of queries: 11472
22 Correct 150 ms 344 KB # of queries: 12930
23 Correct 153 ms 344 KB # of queries: 12462
24 Correct 63 ms 344 KB # of queries: 6314
25 Correct 137 ms 344 KB # of queries: 12544
26 Correct 125 ms 596 KB # of queries: 11903
27 Correct 61 ms 344 KB # of queries: 5991
28 Correct 129 ms 344 KB # of queries: 12539
29 Correct 140 ms 344 KB # of queries: 12843
30 Correct 130 ms 344 KB # of queries: 12539