QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488827#8819. CNOI KnowledgeczcAC ✓153ms24352kbC++141.1kb2024-07-24 15:36:322024-07-24 15:36:33

Judging History

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

  • [2024-07-24 15:36:33]
  • 评测
  • 测评结果：AC
  • 用时：153ms
  • 内存：24352kb
查看
  • [2024-07-24 15:36:32]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
const ull p=131;
using namespace std;
int n;
inline int ask(int l,int r){
	cout<<"? "<<l<<" "<<r<<endl;
	int x; cin>>x;
	return x;
}
unordered_map<ull,int> mp;
const int maxn=1e3+5;
int s[maxn],cnt[maxn],tot;
ull h[maxn],pw[maxn];
inline int get(int l,int r){
	int ret=0;
	for(int i=l;i<=r;i++) ret+=cnt[i];
	return ret;
}
int main(){
	cin>>n;
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*p;
	for(int i=1;i<=n;i++){
		if(i==1 || get(1,i-1)+i==ask(1,i)){
			s[i]=++tot;
		}
		else{
			int l=2,r=i;
			while(l<r){
				int mid=(l+r)>>1;
				if(get(mid,i-1)+(i-mid+1)==ask(mid,i)) r=mid;
				else l=mid+1;
			}
			s[i]=s[l-1];
		}
		h[i]=h[i-1]*p+(ull)s[i];
		for(int j=1;j<=i;j++){
			if(!mp[h[i]-h[j-1]*pw[i-j+1]]){
				mp[h[i]-h[j-1]*pw[i-j+1]]=j;
				cnt[j]++;
			}
			else{
				cnt[mp[h[i]-h[j-1]*pw[i-j+1]]]--;
				mp[h[i]-h[j-1]*pw[i-j+1]]=j;
				cnt[j]++;
			}
		}
	}
	cout<<"! ";
	for(int i=1;i<=n;i++) cout<<s[i]<<" ";
	cout<<endl;
	return 0;
}
/*
1 2 3 4 5 6 2 5 7 7 2 6
*/
源文件, 语言: C++14

详细

Test #1:

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

input:

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

output:

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

result:

ok Accepted. 26 queries used.

Test #2:

score: 0
Accepted
time: 126ms
memory: 24060kb

input:

1000
3
5
2
7
2
11
5
7
16
5
2
21
7
2
27
7
16
11
34
11
5
3
41
11
5
2
48
15
3
2
57
14
3
2
66
17
4
2
75
13
4
2
84
15
4
2
96
15
47
31
23
108
23
11
5
3
124
27
11
5
3
140
36
11
5
2
156
39
11
3
2
172
48
15
5
7
11
188
50
16
5
2
208
59
16
5
8
229
59
16
5
2
251
69
20
8
3
5
273
67
20
8
2
295
76
20
8
3
5
319
76
...

output:

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

result:

ok Accepted. 9224 queries used.

Test #3:

score: 0
Accepted
time: 142ms
memory: 24044kb

input:

1000
2
3
2
7
11
5
2
15
3
2
21
7
11
27
8
2
33
11
3
2
40
9
3
2
47
11
3
2
54
6
3
2
61
7
4
2
71
13
32
15
23
81
20
8
2
94
24
8
3
5
107
31
12
5
2
120
32
11
3
2
133
38
9
3
2
148
38
9
20
14
163
44
14
5
2
179
47
15
3
2
199
56
14
3
2
219
56
11
3
2
240
66
17
7
9
11
261
65
17
8
2
285
76
20
8
3
5
309
76
21
8
2
3...

output:

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

result:

ok Accepted. 9234 queries used.

Test #4:

score: 0
Accepted
time: 143ms
memory: 24088kb

input:

1000
3
5
3
8
2
11
5
8
16
5
2
21
8
3
5
26
8
2
33
11
3
2
40
11
5
7
48
15
5
3
58
15
5
3
68
21
8
2
80
21
7
2
92
26
4
2
104
23
4
2
116
27
5
3
2
128
23
5
3
2
140
26
5
3
2
157
26
9
13
15
17
175
35
14
5
3
193
35
15
5
2
211
44
15
3
2
229
47
14
3
2
249
55
19
7
9
14
269
55
19
8
3
5
289
62
19
8
2
309
59
19
7
2
...

output:

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

result:

ok Accepted. 9247 queries used.

Test #5:

score: 0
Accepted
time: 143ms
memory: 23988kb

input:

1000
2
3
2
7
11
5
3
15
5
2
19
7
2
24
4
2
29
5
3
2
34
5
3
2
41
11
20
13
52
14
5
2
63
20
8
3
5
75
21
8
3
5
87
26
8
2
99
24
8
3
5
111
28
11
5
3
126
27
11
5
3
142
34
9
5
3
158
35
9
5
3
175
45
14
5
2
194
47
15
5
8
213
56
16
5
2
232
55
16
5
8
254
65
20
8
2
276
65
20
8
3
5
299
76
21
8
3
5
322
75
20
8
2
346...

output:

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

result:

ok Accepted. 9217 queries used.

Test #6:

score: 0
Accepted
time: 138ms
memory: 24032kb

input:

1000
2
5
8
2
12
5
8
16
5
2
20
8
3
5
24
8
2
28
12
5
8
32
12
5
2
36
16
5
8
46
16
5
3
57
21
7
3
5
68
19
7
3
5
79
23
7
3
5
90
20
7
3
5
104
27
11
5
2
118
27
11
5
8
132
34
11
5
3
146
35
11
5
3
160
41
14
5
3
174
41
11
5
3
194
52
14
5
2
216
55
15
3
2
238
66
20
7
11
260
67
21
8
2
285
79
21
7
2
310
79
21
7
11...

output:

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

result:

ok Accepted. 9214 queries used.

Test #7:

score: 0
Accepted
time: 146ms
memory: 24352kb

input:

1000
3
5
2
7
2
12
17
5
2
22
7
2
29
7
16
11
36
11
5
3
43
11
5
2
50
15
3
2
61
17
32
41
50
73
23
8
3
5
85
22
7
3
5
99
29
8
2
113
29
64
46
37
129
37
13
5
3
145
37
11
5
3
161
44
9
5
3
177
41
9
5
3
193
47
11
5
3
213
47
15
21
29
38
234
58
17
6
9
256
58
17
6
9
278
68
21
9
3
6
301
68
21
9
3
5
326
80
23
9
13
...

output:

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

result:

ok Accepted. 9330 queries used.

Test #8:

score: 0
Accepted
time: 150ms
memory: 24348kb

input:

1000
3
5
2
9
13
6
9
18
5
3
23
7
3
5
30
8
2
37
11
3
2
45
12
22
29
53
17
5
2
63
15
3
2
73
19
4
2
84
21
44
27
35
95
28
9
15
21
109
27
9
3
6
123
33
13
5
2
140
35
13
5
8
157
43
11
5
3
175
44
11
5
3
194
54
16
5
2
214
55
17
29
37
234
65
18
5
3
255
65
17
5
3
279
77
23
9
12
17
303
76
23
9
3
6
327
87
23
9
2
3...

output:

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

result:

ok Accepted. 9332 queries used.

Test #9:

score: 0
Accepted
time: 142ms
memory: 24316kb

input:

1000
3
6
9
2
13
5
8
18
5
2
24
9
13
18
31
8
2
39
13
24
18
48
13
5
3
57
17
5
3
67
17
37
23
77
23
9
2
89
22
7
2
101
27
4
2
113
25
4
2
125
29
5
3
2
137
24
5
3
2
153
33
9
13
15
24
171
33
12
18
21
24
189
42
17
6
9
207
42
17
5
2
226
51
17
5
9
13
245
56
18
5
2
268
67
23
7
2
292
71
23
7
11
317
83
21
8
2
342
...

output:

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

result:

ok Accepted. 9307 queries used.

Test #10:

score: 0
Accepted
time: 153ms
memory: 24284kb

input:

1000
2
5
9
13
6
9
17
5
2
22
7
2
27
7
17
12
35
11
5
3
43
11
5
3
51
17
29
22
62
17
5
2
73
23
9
13
86
24
8
3
5
99
30
8
2
112
28
8
3
5
125
33
11
5
3
141
32
11
5
3
158
41
12
22
27
32
177
41
13
5
2
196
51
18
5
8
216
53
18
6
9
13
236
62
18
5
2
259
64
18
5
9
13
282
75
23
9
13
305
76
23
9
3
5
329
88
23
7
3
5...

output:

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

result:

ok Accepted. 9309 queries used.

Test #11:

score: 0
Accepted
time: 148ms
memory: 24284kb

input:

1000
2
5
8
2
12
5
8
18
24
9
3
6
30
9
2
38
13
5
8
47
13
24
18
56
18
5
3
67
18
5
2
78
24
9
13
18
90
23
8
3
5
103
29
8
2
117
29
7
2
132
36
12
22
29
148
37
12
23
17
165
46
13
5
3
183
45
12
5
3
201
53
15
5
3
220
54
15
28
21
239
64
17
6
9
258
65
18
5
2
277
76
24
8
3
5
296
76
24
9
13
18
321
89
24
9
2
346
8...

output:

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

result:

ok Accepted. 9307 queries used.

Extra Test:

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

服务器时间: 2025-02-01 22:56:38 | 开源项目