QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489574 | #8819. CNOI Knowledge | qL | WA | 1ms | 3824kb | C++14 | 1.2kb | 2024-07-24 21:32:39 | 2024-07-24 21:32:39 |
Judging History
answer
#include <algorithm>
#include <cstdio>
using i32 = int;
constexpr i32 N = 1000;
i32 aks(i32 l, i32 r) noexcept {
static i32 x;
printf("? %d %d\n", l, r), fflush(stdout);
return scanf("%d", &x), x;
}
i32 n, ans[N + 1], cur;
i32 suf[N + 1], vis[N + 1], pos[N + 1];
i32 cpy[N + 1], nxt[N + 1];
signed main() noexcept {
scanf("%d", &n);
for (i32 i = 1; i <= n; ++i) {
i32 l = 0, r = i - 1;
for (i32 mid; l < r;)
if (mid = (l + r + 1) >> 1, aks(mid, i) - suf[mid] <= i - mid)
l = mid;
else
r = mid - 1;
ans[i] = l ? ans[l] : ++cur;
// std::reverse_copy(ans + 1, ans + i + 1, cpy + 1);
std::copy(ans + 1, ans + i + 1, cpy + 1);
std::reverse(cpy + 1, cpy + i + 1);
nxt[1] = 0;
for (i32 k = 2, j = 0; k <= i; ++k) {
while (j && cpy[j + 1] != cpy[k]) j = nxt[j];
cpy[j + 1] == cpy[k] && ++j, nxt[k] = j;
}
std::fill(pos + 1, pos + i + 1, 1), std::fill(vis + 2, vis + i + 1, 0), vis[0] = 1;
for (i32 k = 1; k <= i; ++k)
if (!vis[nxt[k]]) vis[nxt[k]] = 1, --pos[k];
for (i32 k = 1; k <= i; ++k) pos[k] += pos[k - 1], suf[i - k + 1] += pos[k];
}
putchar('!');
for (i32 i = 1; i <= n; ++i) printf(" %d", ans[i]);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3824kb
input:
12 3 6 6 10 10 15 10 21 15 27 20 14 6 9 20 10 14 19 9 5 2 25 8 5 3 25 50 40 31
output:
? 1 2 ? 1 3 ? 2 4 ? 1 4 ? 2 5 ? 1 5 ? 3 6 ? 1 6 ? 3 7 ? 1 7 ? 2 7 ? 4 8 ? 6 8 ? 5 8 ? 4 9 ? 6 9 ? 5 9 ? 5 10 ? 7 10 ? 8 10 ? 9 10 ? 5 11 ? 8 11 ? 9 11 ? 10 11 ? 6 12 ? 3 12 ? 4 12 ? 5 12 ! 1 2 3 4 5 6 2 5 5 5 5 5
result:
wrong answer Wrong Answer.