#include <bits/stdc++.h>
#include "library.h"
using namespace std;
void Solve(int N)
{
auto Query2 = [&] (int x, int y) -> bool {
vector <int> P(N, 0);
P[x] = P[y] = 1;
return Query(P) == 1;
};
vector <vector <int>> comps;
for (int i = 0; i < N; i++) {
vector <int> P(N, 0);
for (int j = 0; j <= i; j++) {
P[j] = 1;
}
int x = Query(P);
if (x == (int)comps.size() + 1) {
comps.push_back({i});
continue;
}
if (x == (int)comps.size()) {
int l = 0, r = (int)comps.size() - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
vector <int> Q(N, 0);
for (int j = 0; j <= mid; j++) {
for (auto k : comps[j]) {
Q[k] = 1;
}
}
Q[i] = 1;
if (Query(Q) == (mid + 1)) {
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
if (Query2(i, comps[ans].back())) {
comps[ans].push_back(i);
} else {
comps[ans].insert(comps[ans].begin(), i);
}
continue;
}
int l = 0, r = (int)comps.size() - 1, ans = -1, ans2 = -1;
while (l <= r) {
int mid = (l + r) / 2;
vector <int> Q(N, 0);
for (int j = 0; j <= mid; j++) {
for (auto k : comps[j]) {
Q[k] = 1;
}
}
Q[i] = 1;
if (Query(Q) == (mid + 1) - 1) {
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
l = 0, r = ans - 1;
while (l <= r) {
int mid = (l + r) / 2;
vector <int> Q(N, 0);
for (int j = 0; j <= mid; j++) {
for (auto k : comps[j]) {
Q[k] = 1;
}
}
Q[i] = 1;
if (Query(Q) == (mid + 1)) {
r = mid - 1; ans2 = mid;
} else {
l = mid + 1;
}
}
vector <int> v = {i};
if (!Query2(comps[ans][0], i)) {
reverse(comps[ans].begin(), comps[ans].end());
}
for (auto i : comps[ans]) {
v.push_back(i);
}
reverse(v.begin(), v.end());
if (!Query2(comps[ans2][0], i)) {
reverse(comps[ans2].begin(), comps[ans2].end());
}
for (auto i : comps[ans2]) {
v.push_back(i);
}
comps.erase(comps.begin() + ans);
comps.erase(comps.begin() + ans2);
comps.push_back(v);
}
for (auto &i : comps.back()) {
i++;
}
for (auto i : comps.back()) {
cout << i << " ";
}
cout << '\n';
Answer(comps.back());
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |