QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489469#8819. CNOI KnowledgepeterWA 1ms3892kbC++141.2kb2024-07-24 20:28:022024-07-24 20:28:03

Judging History

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

  • [2024-07-24 20:28:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3892kb
  • [2024-07-24 20:28:02]
  • 提交

answer

// Problem: CNOI Knowledge
// Contest: Virtual Judge - QOJ
// URL: https://vjudge.net/problem/QOJ-8819
// Memory Limit: 1014 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e3+5;
int a[maxn],c[maxn],f[maxn],cnt=0;
int nxt[maxn],g[maxn];
bool vis[maxn];

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

int main(){
	
	int n;
	
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++){
		int l=1,r=i,ret=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(ask(mid,i)-g[mid]<=i-mid){
				ret=mid;
				l=mid+1;
			}else r=mid-1;
		}
		if(!ret) a[i]=++cnt;
		else a[i]=a[ret];
		// for(int j=1;j<=i;j++) printf("%d ",a[j]);
		// puts("");
		for(int j=1;j<=i;j++){
			c[j]=a[i-j+1];
			vis[j]=0;
		}
		int now=0;
		for(int j=2;j<=i;j++){
			while(now&&c[now+1]!=c[j]) now=nxt[now];
			if(c[now+1]==c[j]) now++;
			nxt[j]=now;
		}
		for(int j=1;j<=i;j++){
			f[j]=f[j-1];
			if(nxt[j]&&vis[nxt[j]]) continue;
			f[j]++;
			vis[nxt[j]]=1;
		}
		for(int j=1;j<=i;j++) g[i-j+1]+=f[j];
	}
	
	printf("! ");
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	puts("");
	fflush(stdout);
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

12
1
3
3
6
6
10
6
15
10
21
10
20
15
14
6
9
14
6
10
19
5
2
1
19
5
3
25
9
3
6

output:

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

result:

wrong answer Wrong Answer.