QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488943#8819. CNOI KnowledgethomaswmyRE 0ms0kbC++14871b2024-07-24 16:33:582024-07-24 16:33:58

Judging History

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

  • [2024-07-24 16:33:58]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-24 16:33:58]
  • 提交

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;
			assert(cnt[j]==query(j,i));
		}
	}
	printf("! ");
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	fflush(stdout);
	return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

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

output:

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

result: