QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489460#8819. CNOI KnowledgepeterWA 1ms3876kbC++141.2kb2024-07-24 20:24:372024-07-24 20:24:37

Judging History

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

  • [2024-07-24 20:24:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3876kb
  • [2024-07-24 20:24:37]
  • 提交

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=1;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;
}

詳細信息

Test #1:

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

input:

12
1

output:

? 1 1
1 
? 1 2

result:

wrong answer Invalid output.