QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488986#8819. CNOI KnowledgewcyQwQWA 62ms4092kbC++141.4kb2024-07-24 16:57:032024-07-24 16:57:04

Judging History

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

  • [2024-07-24 16:57:04]
  • 评测
  • 测评结果:WA
  • 用时:62ms
  • 内存:4092kb
  • [2024-07-24 16:57:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2010;
int num, a[N], f[N];

struct SAM {
  unordered_map<int, int> son[N];
  int fa[N], len[N], las, cnt;
  void clear() {
    for (int i = 1; i <= cnt; i++) son[i].clear();
    las = cnt = 1;
  }
  void insert(int c) {
    int p = las, cur = ++cnt;
    len[cur] = len[p] + 1, las = cur;
    while (!son[p][c]) son[p][c] = cur, p = fa[p];
    if (!p) fa[cur] = 1;
    else {
      int q = son[p][c];
      if (len[q] == len[p] + 1) fa[cur] = q;
      else {
        int nq = ++cnt;
        son[nq] = son[q];
        fa[nq] = fa[q], len[nq] = len[p] + 1, fa[cur] = fa[cur] = nq;
        while (son[p][c] == q) son[p][c] = nq, p = fa[p];
      }
    }
    num += len[cur] - len[fa[cur]];
  }
} S;

int main() {
  // cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  auto query = [&](int l, int r) {
    cout << "? " << l << ' ' << r << '\n';
    cout.flush();
    int x;
    cin >> x;
    return x;
  };
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    int l = 1, r = i - 1, p = i;
    while (l <= r) {
      int m = (l + r) / 2;
      if (query(m, i) != f[m] + i - m + 1) p = m, l = m + 1;
      else r = m - 1;
    }
    a[i] = p == i ? ++cnt : a[p];
    S.clear(), num = 0;
    for (int j = i; j >= 1; j--) S.insert(a[j]), f[j] = num;
  }
  cout << "! ";
  for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
  cout.flush();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3724kb

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: 0
Accepted
time: 51ms
memory: 3936kb

input:

1000
3
5
2
3
2
7
11
8
5
2
11
3
2
11
5
7
15
8
5
3
15
8
5
2
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
7
5
3
41
16
8
5
2
45
15
7
3
2
55
20
7
15
11
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
11
5
3
100
32
11
5
2
100
31
11
5
8
112
31
12
...

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
? 7 10
? 8 10
? 9 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
?...

result:

ok Accepted. 8880 queries used.

Test #3:

score: 0
Accepted
time: 55ms
memory: 3952kb

input:

1000
2
3
2
5
7
8
5
2
7
3
2
11
5
7
11
5
2
15
7
3
2
14
4
3
2
17
4
3
2
13
4
3
2
15
5
3
2
15
51
32
23
23
11
5
2
28
12
5
8
36
16
8
5
2
38
16
7
3
2
45
14
4
3
2
44
14
7
9
50
20
8
5
2
54
19
7
3
2
64
19
4
3
2
65
17
4
3
2
76
24
9
17
11
76
24
11
5
2
88
24
12
5
8
87
26
12
5
2
100
32
12
5
8
102
33
11
5
3
116
32
...

output:

? 1 2
? 1 3
? 2 3
? 2 4
? 1 4
? 2 5
? 3 5
? 4 5
? 3 6
? 4 6
? 5 6
? 3 7
? 5 7
? 4 7
? 4 8
? 6 8
? 7 8
? 4 9
? 6 9
? 7 9
? 8 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
? 6 13
? 9 13
? 11 13
? 12 13
? 7 14
? 3 14
? 5 14
? 6 14
? 7 15
? 11 15
? 13 15
? 14 1...

result:

ok Accepted. 8879 queries used.

Test #4:

score: 0
Accepted
time: 59ms
memory: 3888kb

input:

1000
3
5
3
5
2
8
5
8
5
2
12
5
8
12
5
2
16
7
3
2
16
7
11
21
8
5
3
20
7
5
3
27
11
5
2
27
11
3
2
33
9
3
2
31
5
3
2
36
6
4
3
2
31
6
4
3
2
35
6
4
3
2
35
11
17
26
44
17
8
5
3
44
19
8
5
2
53
19
7
3
2
53
19
4
3
2
62
24
9
19
14
63
24
11
5
3
71
24
11
5
2
69
24
11
3
2
81
29
11
5
7
81
27
11
5
3
96
30
11
5
3
99
...

output:

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

ok Accepted. 8882 queries used.

Test #5:

score: 0
Accepted
time: 53ms
memory: 3948kb

input:

1000
2
3
2
5
7
8
5
3
8
5
2
11
3
2
9
3
2
11
4
3
2
6
4
3
2
13
34
27
20
17
8
5
2
24
12
5
8
26
11
5
3
32
11
5
2
31
11
5
8
36
14
8
5
3
36
15
7
5
3
44
14
7
5
3
41
11
7
5
3
52
17
8
5
2
55
19
8
5
65
21
8
5
2
65
21
8
5
76
26
12
5
2
75
24
12
5
8
87
26
11
5
3
87
26
11
5
2
98
31
11
5
8
95
31
12
5
2
105
31
12
5
...

output:

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

result:

ok Accepted. 8863 queries used.

Test #6:

score: 0
Accepted
time: 57ms
memory: 4092kb

input:

1000
2
5
5
2
8
5
8
5
2
12
5
8
12
5
2
16
8
5
16
8
5
2
20
8
5
21
8
5
3
27
11
5
3
26
9
5
3
31
9
5
3
27
9
5
3
34
14
8
5
2
34
15
8
5
41
14
8
5
3
41
15
7
5
3
48
19
7
5
3
48
17
7
5
3
60
17
8
5
2
63
19
7
3
2
75
25
11
5
7
77
27
11
5
2
90
27
11
3
2
91
27
11
5
7
104
33
11
5
2
104
33
12
5
8
117
31
12
5
2
115
31...

output:

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

result:

ok Accepted. 8885 queries used.

Test #7:

score: -100
Wrong Answer
time: 62ms
memory: 3896kb

input:

1000
3
5
2
3
2
7
12
8
5
2
11
3
2
11
5
7
15
8
5
3
15
8
5
2
19
7
3
2
22
41
61
50
29
11
5
3
29
11
5
3
37
11
5
2
37
13
23
29
46
18
8
5
3
45
17
7
5
3
53
14
7
5
3
51
11
7
5
3
58
13
7
5
3
57
18
38
29
69
21
9
6
69
22
9
6
80
27
12
6
9
80
28
13
5
3
93
28
13
6
9
94
30
13
6
9
109
38
13
5
2
108
38
13
5
9
122
36
...

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

result:

wrong answer Wrong Answer.