QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488951#8819. CNOI Knowledgemsk_samaAC ✓98ms21416kbC++201.5kb2024-07-24 16:36:022024-07-24 16:36:02

Judging History

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

  • [2024-07-24 16:36:02]
  • 评测
  • 测评结果：AC
  • 用时：98ms
  • 内存：21416kb
查看
  • [2024-07-24 16:36:02]
  • 提交

answer

#include <bits/stdc++.h>
#define MISAKA main
#define ll long long
using namespace std;
inline int read(){
   char ch=getchar();int f=1,x=0;
   while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
   return x*f;
}
const double eps=1e-9;
const int N=4e3+10,inf=1e9,mod=998244353;
int n,a[N],fa[N],len[N],ed=1,cnt=1,num=1,f[N][N],mx=1;
unordered_map<int,int> ch[N];
void insert(int c){
    int p=ed,np=++cnt;len[np]=len[p]+1;ed=np;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else{
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else{
            int nq=++cnt;fa[nq]=fa[q];len[nq]=len[p]+1;
            ch[nq]=ch[q];fa[q]=fa[np]=nq;
            for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}
int ask(int l,int r){cout<<"? "<<l<<' '<<r<<'\n'<<flush;return read();}
mt19937 rd(time(0));
signed MISAKA(){
    n=read();a[1]=f[1][1]=1;
    for(int i=2;i<=n;i++){
        if(ask(1,i)-f[1][i-1]==i) a[i]=++num;
        else{
            int l=1,r=i-1;
            while(r>=l){
                int mid=l+r>>1;
                if(ask(mid,i)-f[mid][i-1]==i-mid+1) r=mid-1;
                else l=mid+1;
            }
            a[i]=a[r];
        }
        for(int i=0;i<=cnt;i++) fa[i]=len[i]=0,ch[i].clear();
        int res=0;ed=cnt=1;
        for(int j=i;j>=1;j--) insert(a[j]),res+=len[ed]-len[fa[ed]],f[j][i]=res;
    }
    cout<<"! ";
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<flush;
    return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

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

input:

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

output:

? 1 2
? 1 3
? 1 4
? 1 5
? 1 6
? 1 7
? 3 7
? 1 7
? 2 7
? 1 8
? 4 8
? 6 8
? 5 8
? 1 9
? 1 10
? 5 10
? 7 10
? 8 10
? 9 10
? 1 11
? 5 11
? 8 11
? 9 11
? 1 12
? 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: 90ms
memory: 21236kb

input:

1000
3
5
5
2
7
3
2
11
7
11
16
8
5
2
21
11
3
2
27
11
5
7
34
15
8
5
3
41
15
8
5
2
48
19
7
3
2
57
19
4
3
2
66
23
5
3
2
75
20
5
3
2
84
23
5
3
2
96
23
9
13
15
108
31
14
8
5
3
124
31
15
7
5
3
140
41
16
8
5
2
156
45
15
7
3
2
172
55
20
7
15
11
188
58
21
8
5
2
208
68
21
8
5
229
69
21
8
5
2
251
80
26
12
5
8
2...

output:

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

result:

ok Accepted. 9878 queries used.

Test #3:

score: 0
Accepted
time: 87ms
memory: 21096kb

input:

1000
2
2
3
3
2
7
11
8
5
2
15
7
3
2
21
11
5
7
27
11
5
2
33
15
7
3
2
40
14
4
3
2
47
17
4
3
2
54
13
4
3
2
61
15
5
3
2
71
15
51
32
23
81
23
11
5
2
94
28
12
5
8
107
36
16
8
5
2
120
38
16
7
3
2
133
45
14
4
3
2
148
44
14
7
9
163
50
20
8
5
2
179
54
19
7
3
2
199
64
19
4
3
2
219
65
17
4
3
2
240
76
24
9
17
11
...

output:

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

result:

ok Accepted. 9876 queries used.

Test #4:

score: 0
Accepted
time: 92ms
memory: 20856kb

input:

1000
3
5
5
3
8
5
2
11
8
5
16
8
5
2
21
12
5
8
26
12
5
2
33
16
7
3
2
40
16
7
11
48
21
8
5
3
58
20
7
5
3
68
27
11
5
2
80
27
11
3
2
92
33
9
3
2
104
31
5
3
2
116
36
6
4
3
2
128
31
6
4
3
2
140
35
6
4
3
2
157
35
11
17
26
175
44
17
8
5
3
193
44
19
8
5
2
211
53
19
7
3
2
229
53
19
4
3
2
249
62
24
9
19
14
269
...

output:

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

result:

ok Accepted. 9880 queries used.

Test #5:

score: 0
Accepted
time: 71ms
memory: 21416kb

input:

1000
2
2
3
3
2
7
11
8
5
3
15
8
5
2
19
11
3
2
24
9
3
2
29
11
4
3
2
34
6
4
3
2
41
13
34
27
20
52
17
8
5
2
63
24
12
5
8
75
26
11
5
3
87
32
11
5
2
99
31
11
5
8
111
36
14
8
5
3
126
36
15
7
5
3
142
44
14
7
5
3
158
41
11
7
5
3
175
52
17
8
5
2
194
55
19
8
5
213
65
21
8
5
2
232
65
21
8
5
254
76
26
12
5
2
276...

output:

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

result:

ok Accepted. 9860 queries used.

Test #6:

score: 0
Accepted
time: 78ms
memory: 19424kb

input:

1000
2
2
5
8
5
2
12
8
5
16
8
5
2
20
12
5
8
24
12
5
2
28
16
8
5
32
16
8
5
2
36
20
8
5
46
21
8
5
3
57
27
11
5
3
68
26
9
5
3
79
31
9
5
3
90
27
9
5
3
104
34
14
8
5
2
118
34
15
8
5
132
41
14
8
5
3
146
41
15
7
5
3
160
48
19
7
5
3
174
48
17
7
5
3
194
60
17
8
5
2
216
63
19
7
3
2
238
75
25
11
5
7
260
77
27
1...

output:

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

result:

ok Accepted. 9883 queries used.

Test #7:

score: 0
Accepted
time: 68ms
memory: 20688kb

input:

1000
3
5
5
2
7
3
2
12
17
8
5
2
22
11
3
2
29
11
5
7
36
15
8
5
3
43
15
8
5
2
50
19
7
3
2
61
22
41
61
50
73
29
11
5
3
85
29
11
5
3
99
37
11
5
2
113
37
13
23
29
129
46
18
8
5
3
145
45
17
7
5
3
161
53
14
7
5
3
177
51
11
7
5
3
193
58
13
7
5
3
213
57
18
38
29
234
69
21
9
6
256
69
22
9
6
278
80
27
12
6
9
30...

output:

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

result:

ok Accepted. 9811 queries used.

Test #8:

score: 0
Accepted
time: 86ms
memory: 20580kb

input:

1000
3
5
5
2
9
13
9
13
18
9
5
3
23
12
5
3
30
11
5
2
37
15
7
3
2
45
17
37
29
22
53
23
8
5
2
63
22
7
3
2
73
27
9
3
2
84
27
63
44
35
95
35
12
21
15
109
35
13
6
9
123
42
17
9
5
2
140
42
18
8
5
157
51
17
8
5
3
175
52
15
7
5
3
194
63
21
8
5
2
214
65
23
46
37
29
234
76
23
8
5
3
255
76
23
7
5
3
279
89
30
12...

output:

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

result:

ok Accepted. 9819 queries used.

Test #9:

score: 0
Accepted
time: 98ms
memory: 20760kb

input:

1000
3
6
9
5
2
13
8
5
18
8
5
2
24
13
24
18
31
13
5
2
39
18
9
13
48
18
8
5
3
57
23
7
5
3
67
23
9
17
77
30
13
5
2
89
29
12
3
2
101
35
9
3
2
113
32
5
3
2
125
37
6
4
3
2
137
33
6
4
3
2
153
43
11
24
33
171
42
15
24
33
189
51
21
9
6
207
51
22
9
5
2
226
61
21
9
17
13
245
63
23
8
5
2
268
75
29
11
3
2
292
80...

output:

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

result:

ok Accepted. 9812 queries used.

Test #10:

score: 0
Accepted
time: 80ms
memory: 21168kb

input:

1000
2
2
5
9
13
9
6
17
9
5
2
22
12
3
2
27
12
22
17
35
17
8
5
3
43
15
7
5
3
51
22
43
36
29
62
23
9
5
2
73
30
13
5
9
86
30
13
5
3
99
37
11
5
2
112
36
11
5
8
125
42
14
8
5
3
141
41
15
7
5
3
158
50
17
32
41
177
51
17
9
5
2
196
62
23
8
5
216
61
23
9
18
13
236
71
24
9
5
2
259
74
24
9
18
13
282
86
30
13
6
...

output:

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

result:

ok Accepted. 9807 queries used.

Test #11:

score: 0
Accepted
time: 86ms
memory: 19520kb

input:

1000
2
2
5
8
5
2
12
8
5
18
24
13
6
9
30
13
5
2
38
18
8
5
47
18
9
13
56
23
9
5
3
67
24
8
5
2
78
30
13
24
18
90
30
13
5
3
103
37
11
5
2
117
36
11
3
2
132
44
17
29
22
148
45
17
9
12
165
55
17
9
5
3
183
55
17
7
5
3
201
64
21
7
5
3
220
64
21
9
15
239
75
21
9
6
258
76
23
9
5
2
277
88
30
13
5
8
296
88
31
1...

output:

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

result:

ok Accepted. 9800 queries used.

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2025-02-02 02:49:31 | 開源專案