QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489569 | #8819. CNOI Knowledge | qL | TL | 0ms | 0kb | C++14 | 1.1kb | 2024-07-24 21:29:51 | 2024-07-24 21:29:52 |
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);
nxt[1] = 0;
for (i32 k = 2, j = 0; k <= i; ++k) {
while (j && cpy[j + 1] != cpy[k]) j = cpy[j];
cpy[j + 1] == cpy[k] && ++j, nxt[k] = j;
}
std::fill(pos + 1, pos + i + 1, 0);
for (i32 k = 1; k <= i; ++k) pos[k] = 1;
for (i32 k = 2; k <= i; ++k)
if (!vis[nxt[k]]) vis[nxt[k]] = 1, --pos[k];
for (i32 k = 2; 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
Time Limit Exceeded
input:
12 3 6 6 10 10 15 10 21 15 27 14 26 20 20 34 43 19 9 14 25 8 5
output:
? 1 2 ? 1 3 ? 2 4 ? 1 4 ? 2 5 ? 1 5 ? 3 6 ? 1 6 ? 3 7 ? 1 7 ? 4 8 ? 2 8 ? 3 8 ? 4 9 ? 2 9 ? 1 9 ? 5 10 ? 7 10 ? 6 10 ? 5 11 ? 8 11 ? 9 11