QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488982 | #8819. CNOI Knowledge | dalao_see_me | WA | 1ms | 3900kb | C++14 | 1.4kb | 2024-07-24 16:55:11 | 2024-07-24 16:55:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 1005;
int n;
int a[N], b[N], c[N], d[N], nxt[N];
int ask(int l, int r) {
printf("? %d %d\n", l, r);
fflush(stdout); return read();
}
void Solve() {
n = read();
int tot = 0;
for (int i = 1; i <= n; i++) {
int L = 0, R = i - 1;
while (L < R) {
int mid = L + R + 1 >> 1;
if (ask(mid, i) - a[mid] <= i - mid) L = mid;
else R = mid - 1;
}
if (!L) b[i] = ++tot; else b[i] = b[L];
for (int j = 1; j <= i; j++) c[j] = b[j], d[j] = 0;
reverse(c + 1, c + i + 1);
for (int k = 2, j = 0; k <= i; k++) {
while (j && c[j + 1] != c[k]) j = nxt[j];
if (c[j + 1] == c[k]) j++; nxt[k] = j;
}
for (int j = 2; j <= i; j++) if (nxt[j]) {
d[nxt[j]]++;
d[j]--;
}
for (int j = 1; j <= i; j++) d[j] += d[j - 1], a[i - j + 1] += d[j];
}
putchar('!');
for (int i = 1; i <= n; i++) printf(" %d", b[i]); putchar('\n');
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int _ = 1;
while (_--) Solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3900kb
input:
12 3 6 6 10 10 15 10 21 15 27 14 26 34 20 34 43 19 42 52 25 51 62 25 50 72
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 ? 1 8 ? 4 9 ? 2 9 ? 1 9 ? 5 10 ? 2 10 ? 1 10 ? 5 11 ? 2 11 ? 1 11 ? 6 12 ? 3 12 ? 1 12 ! 1 2 3 4 5 6 7 8 9 10 11 12
result:
wrong answer Wrong Answer.