QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488995#8819. CNOI Knowledgedalao_see_meWA 3ms3964kbC++141.4kb2024-07-24 17:00:242024-07-24 17:00:24

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 17:00:24]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3964kb
  • [2024-07-24 17:00:24]
  • 提交

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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3964kb

input:

12
3
6
6
10
10
15
10
21
15
27
20
14
6
9
20
34
43
19
9
5
2
25
8
5
25
9
19

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
? 2 9
? 1 9
? 5 10
? 7 10
? 8 10
? 9 10
? 5 11
? 8 11
? 9 11
? 6 12
? 9 12
? 7 12
! 1 2 3 4 5 6 2 5 7 7 5 6

result:

ok Accepted. 27 queries used.

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 3892kb

input:

1000
3
5
2
3
2
7
11
8
5
2
11
3
2
11
5
7
15
8
5
3
15
33
41
19
7
3
2
19
4
3
2
23
5
3
2
20
5
3
2
23
5
3
2
23
9
13
15
31
14
8
5
3
31
15
23
27
41
93
71
61
51
45
95
73
62
51
55
110
156
172
58
21
8
5
2
68
21
8
5
69
21
8
5
2
80
26
12
5
8
79
24
12
5
2
89
24
12
5
8
87
26
54
36
31
100
32
11
5
2
100
31
11
5
8
1...

output:

? 1 2
? 1 3
? 2 3
? 2 4
? 3 4
? 2 5
? 1 5
? 3 6
? 4 6
? 5 6
? 3 7
? 5 7
? 6 7
? 4 8
? 6 8
? 5 8
? 4 9
? 6 9
? 7 9
? 8 9
? 5 10
? 2 10
? 1 10
? 5 11
? 8 11
? 9 11
? 10 11
? 6 12
? 9 12
? 10 12
? 11 12
? 6 13
? 9 13
? 11 13
? 12 13
? 7 14
? 10 14
? 12 14
? 13 14
? 7 15
? 11 15
? 13 15
? 14 15
? 8 16
?...

result:

wrong answer Wrong Answer.