oj.uz

Submission #954369

# Submission time Handle Problem Language Result Execution time Memory
954369 2024-03-27T17:22:01 Z Alan Library (JOI18_library) C++17
0 / 100
 21 ms 432 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);
	ans[N-1] = [&] {
		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;
	}();
	vector<int> hv;
	vector<bool> used (N+1);
	used[ans[N-1]] = true;
	for (int i = 1; i <= N; i++) hv.push_back(i);
	for (int i = 0; i < N-2; i++) {
		int l = 0, r = hv.size();
		while (l+1 < r) {
			int mid = (l+r)/2;
			vector<int> q (N);
			for (int j = 0; j < mid; j++) q[hv[j]-1] = 1;
			int res = Query(q);
			for (int j = 0; j < N; j++) q[j] = 0;
			for (int j = mid; j < r; j++) q[hv[j]-1] = 1;
			int res2 = Query(q);
			if (res > res2) r = mid; 
			else if (res < res2) l = mid;
			else {
				bool left = false;
				for (int j = 0; j < mid; j++) if (hv[j] == ans[N-1]) left = true;
				if (left) l = mid;
				else r = mid;
			}
		}
		ans[i] = hv[l];
		used[ans[i]] = true;
		swap(hv[l], hv.back());
		hv.pop_back();
	}
	for (int i = 1; i <= N; i++) if (!used[i]) ans[N-2] = i;
	Answer(ans);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 432 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 432 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -