QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488988 | #8819. CNOI Knowledge | dalao_see_me | WA | 1ms | 3816kb | C++14 | 1.4kb | 2024-07-24 16:57:33 | 2024-07-24 16:57:34 |
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 = 1; j <= i; j++) d[j]++;
for (int j = 2; j <= i; j++) if (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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3816kb
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 9 6 3
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 ? 9 12 ? 10 12 ? 11 12 ! 1 2 3 4 5 6 2 5 5 5 5 5
result:
wrong answer Wrong Answer.