QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745914 | #9432. Permutation | guosoun | WA | 1ms | 3836kb | C++17 | 2.5kb | 2024-11-14 12:23:30 | 2024-11-14 12:23:30 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
struct hope {
int n;
std::vector<int> p;
hope(int n) : n(n), p(n) {
std::iota(p.begin(), p.end(), 0);
std::shuffle(p.begin(), p.end(), std::mt19937());
for (int i : p) std::cerr << i << ' ';
std::cerr << '\n';
}
int query(std::vector<int> a) {
auto na = a;
for (int i = 0; i < n; i++) na[p[i]] = a[i];
std::cout << 0 << ' ';
for (int i : na) std::cout << i << ' ';
std::cout << std::endl;
int ret;
std::cin >> ret;
return ret;
}
void answer(std::vector<int> a) {
auto na = a;
for (int i = 0; i < n; i++) na[p[i]] = a[i];
std::cout << 1 << ' ';
for (int i : a) std::cout << i << ' ';
std::cout << std::endl;
}
};
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n;
std::cin >> n;
hope ia(n);
if (n == 1) return ia.answer({1}), 0;
std::vector<int> a(n);
auto solve = [&](auto &self, int l, int r, std::vector<int> v) {
assert((int)v.size() == r - l + 1);
if (l == r) return a[l] = v[0], void();
int mid = (l + r) >> 1;
std::vector<std::vector<int>> cv;
std::vector<int> lv, rv;
for (int i : v) cv.push_back({i});
while (cv.size()) {
if (cv.size() == 1) {
auto a = cv[0];
cv.pop_back();
int ev = -1;
if (lv.size()) ev = lv[0];
else {
for (int i = 1; i <= n; i++)
if (std::find(v.begin(), v.end(), i) == v.end())
ev = i;
}
assert(ev != -1);
std::vector<int> q(n, ev);
for (int i = l; i <= mid; i++) q[i] = a[0];
if (ia.query(q))
lv.insert(lv.end(), a.begin(), a.end());
else
rv.insert(rv.end(), a.begin(), a.end());
continue;
}
auto a = cv.back();
cv.pop_back();
auto b = cv.back();
cv.pop_back();
std::vector<int> q(n, a[0]);
for (int i = mid + 1; i <= r; i++) q[i] = b[0];
if (int t = ia.query(q); t == 1) {
a.insert(a.end(), b.begin(), b.end());
cv.push_back(a);
} else if (t == 2) {
lv.insert(lv.end(), a.begin(), a.end());
rv.insert(rv.end(), b.begin(), b.end());
} else {
lv.insert(lv.end(), b.begin(), b.end());
rv.insert(rv.end(), a.begin(), a.end());
}
}
self(self, l, mid, lv);
self(self, mid + 1, r, rv);
};
std::vector<int> v(n);
std::iota(v.begin(), v.end(), 1);
solve(solve, 0, n - 1, v);
ia.answer(a);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3836kb
input:
5 2 0 1 1 2 0 2
output:
0 4 4 5 5 5 0 2 2 3 3 3 0 5 5 1 1 1 0 1 1 1 1 2 0 1 1 1 1 5 0 2 2 1 2 2 0 3 4 3 3 3 1 1 2 5 3 4
result:
wrong answer Wrong Anser