QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456915#8819. CNOI KnowledgeJames1213WA 1ms3856kbC++14919b2024-06-28 16:59:232024-06-28 16:59:25

Judging History

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

  • [2024-06-28 16:59:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2024-06-28 16:59:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,num,p[N][N],val[N],s[N];
int query(int l,int r) {
	printf("? %d %d\n",l,r);
	fflush(stdout);
	int x; cin>>x; return x;
}
int main() {
	cin>>n; s[1]=num=val[1]=1;
	for (int i=2; i<=n; i++) {
		int l=1,r=i-1,res=-1;
		while (l<=r) {
			int mid=(l+r)>>1;
			if (query(mid,i)==val[mid]+i-mid+1) r=mid-1;
			else res=mid,l=mid+1;
		}
		s[i]=(res==-1?(++num):s[res]);
		val[i]=1; int maxx=0;
		for (int j=1; j<i; j++) {
			int len=p[j][i-1];
			while (len && s[i]!=s[j+len]) len=p[j][j+len-1];
			if (len || s[i]==s[j]) p[j][i]=len+1;
			maxx=max(maxx,p[j][i]);
			val[j]+=(i-j+1-maxx);
		}
//		cerr<<"!! "<<s[i]<<endl;
//		for (int j=1; j<=i; j++) printf("%d ",p[j][i]); puts("");
//		for (int j=1; j<=i; j++) printf("%d ",val[j]); puts("");
	}
	printf("! "); for (int i=1; i<=n; i++) printf("%d ",s[i]);
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3856kb

input:

12
3
6
6
10
10
15
10
21
15
27
20
14
26
20
20
10
6
3
19
9
5
2
25
8
5
3
25
9
6
3

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

result:

wrong answer Wrong Answer.