QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#450285 | #6303. Inversion | nhuang685 | WA | 72ms | 19332kb | C++20 | 1.7kb | 2024-06-22 07:33:49 | 2024-06-22 07:33:50 |
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);
}
};
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
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: 72ms
memory: 19332kb
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 0 0 1 1 0 1 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 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 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.