QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488941#8819. CNOI KnowledgethomaswmyWA 6ms3868kbC++14839b2024-07-24 16:32:032024-07-24 16:32:03

Judging History

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

  • [2024-07-24 16:32:03]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3868kb
  • [2024-07-24 16:32:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=1010;

int query(int l,int r) {
	printf("? %d %d\n",l,r);
	fflush(stdout);
	int res;
	scanf("%d",&res);
	return res;
}

int n;
int a[N],tot;
int cnt[N];
int kmp[N];

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		if(query(1,i)-cnt[1]==i) {
			a[i]=++tot;
			for(int j=1;j<=i;j++) cnt[j]+=i-j+1;
			continue;
		}
		int L=2,R=i-1,mid,res=1;
		while(L<=R) {
			mid=L+R>>1;
			if(query(mid,i)-cnt[mid]<i-mid+1) res=mid,L=mid+1;
			else R=mid-1;
		}
		a[i]=a[res];
		cnt[i]++;
		kmp[i]=0;
		for(int j=i-1,k=0,s=1;j>=1;j--) {
			while(k && a[j]!=a[i-k]) k=kmp[i-k+1];
			if(a[j]==a[i-k]) k++;
			kmp[j]=k;
			if(!k) s++;
			cnt[j]+=s;
		}
	}
	printf("! ");
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	fflush(stdout);
	return 0;
}

详细

Test #1:

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

input:

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

output:

? 1 1
? 1 2
? 1 3
? 1 4
? 1 5
? 1 6
? 1 7
? 4 7
? 2 7
? 3 7
? 1 8
? 4 8
? 6 8
? 5 8
? 1 9
? 1 10
? 5 10
? 7 10
? 8 10
? 9 10
? 1 11
? 6 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. 28 queries used.

Test #2:

score: -100
Wrong Answer
time: 6ms
memory: 3868kb

input:

1000
1
3
5
2
7
3
2
11
5
7
16
8
5
2
21
7
3
2
27
34
11
5
3
41
15
26
19
48
15
7
3
2
57
19
4
3
2
66
17
4
3
2
75
20
5
3
2
84
15
5
3
2
96
23
9
13
15
108
23
11
5
3
124
31
15
23
27
140
36
81
61
51
41
156
45
95
73
62
51
172
48
98
140
156
188
58
112
156
172
208
59
127
174
191
229
69
143
193
211
251
69
144
194...

output:

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

result:

wrong answer Wrong Answer.