QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#450286 | #6303. Inversion | nhuang685 | WA | 66ms | 19520kb | C++20 | 1.8kb | 2024-06-22 07:35:51 | 2024-06-22 07:35:51 |
Judging History
answer
/**
* @file qoj6303-1.cpp
* @author n685
* @brief
* @date 2024-06-21
*
*
*/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif
auto main() -> int {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> ind;
std::vector dp(n + 1, std::vector<int>(n + 1));
auto query = [&](int l, int r) -> int {
if (r > std::ssize(ind)) {
std::cout << "? " << l << ' ' << r << '\n' << std::flush;
int v;
std::cin >> v;
return v;
} else {
return dp[l][r] % 2;
}
};
auto gr = [&](int l, int r) -> bool {
if (r - l == 1) {
return query(l, r);
} else {
return ((query(l, r) - query(l + 1, r) - query(l, r - 1) +
query(l + 1, r - 1)) %
2 +
2) %
2;
}
};
for (int i = 1; i <= n; ++i) {
int l = 0, r = i - 2;
while (l < r) {
int mid = (l + r) / 2;
if (gr(ind[mid], i)) {
r = mid;
} else {
l = mid + 1;
}
}
if (l == i - 2 && !gr(ind[l], i)) {
l = i - 1;
}
ind.insert(ind.begin() + l, i);
std::vector<int> p(i + 1);
for (int j = 0; j < i; ++j) {
p[ind[j]] = j;
}
dp[i - 1][i] = (p[i - 1] > p[i]);
for (int j = i - 2; j >= 1; --j) {
dp[j][i] = (dp[j + 1][i] + dp[j][i - 1] - dp[j + 1][i - 1]) % 2;
if (dp[j][i] < 0) {
dp[j][i] += 2;
}
}
}
std::vector<int> p(n + 1);
for (int j = 0; j < n; ++j) {
p[ind[j]] = j;
}
std::cout << "! ";
for (int i = 1; i <= n; ++i) {
std::cout << p[i] + 1 << ' ';
}
std::cout << '\n' << std::flush;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
input:
3 0 0 1
output:
? 1 2 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 66ms
memory: 19520kb
input:
1993 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 2 4 ? 3 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 2 5 ? 2 6 ? 3 6 ? 3 6 ? 4 6 ? 4 6 ? 5 6 ? 2 7 ? 3 7 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 2 8 ? 3 8 ? 5 8 ? 6 8 ? 7 8 ? 1 9 ? 2 9 ? 8 9 ? 7 9 ? 8 9 ? 1 10 ? 2 10 ? 3 10 ? 4 10 ? 6 10 ? 7 10 ? 1 11 ? 2 11 ? 10 11 ? 6 11 ? 7 11 ? 2 12 ? 3 12 ? 11 12 ? ...
result:
wrong answer Wa.