QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488731#8819. CNOI KnowledgemaojunWA 1ms3904kbC++231.5kb2024-07-24 14:46:102024-07-24 14:46:11

Judging History

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

  • [2024-07-24 14:46:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3904kb
  • [2024-07-24 14:46:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int n,a[N];

int s[N],sa[N],ht[N];
inline void init(){
	static pair<int,int> bl[N];
#define fi first
#define se second
#define mp make_pair
	static int rk[N];
	static auto grk=[&](){
		static int c[N],x[N],y[N];
		memset(c,0,n+1<<2);
		for(int i=1;i<=n;i++)c[bl[i].se]++;
		for(int i=1;i<=n;i++)c[i]+=c[i-1];
		for(int i=n;i;i--)y[c[bl[i].se]--]=i;
		memset(c,0,n+1<<2);
		for(int i=1;i<=n;i++)c[bl[i].fi]++;
		for(int i=1;i<=n;i++)c[i]+=c[i-1];
		for(int i=n;i;i--)x[c[bl[y[i]].fi]--]=y[i];
		for(int i=1,j=0;i<=n;i++)rk[x[i]]=j+=bl[x[i]]!=bl[x[i-1]];
	};
	static int t[N];memcpy(t,s,sizeof t);sort(t+1,t+n+1);
	for(int i=1,j=0;i<=n;i++)rk[t[i]]=j+=t[i]!=t[i-1];
	for(int i=1;i<=n;i++)bl[i]=mp(rk[s[i]],0);
	for(int k=1;k<=n;k<<=1){grk();for(int i=1;i<=n;i++)bl[i]=mp(rk[i],i+k>n?0:rk[i+k]);}
	grk();for(int i=1;i<=n;i++)sa[rk[i]]=i;
	for(int i=1,h=0;i<=n;i++){h&&h--;for(int j=sa[rk[i]-1];i+h<=n&&j+h<=n&&s[i+h]==s[j+h];h++);ht[rk[i]]=h;}
}
inline int qry(int l,int r){
	if(!a[r]){
		printf("? %d %d\n",l,r);fflush(stdout);
		int x;scanf("%d",&x);return x;
	}
	int _n=n;n=r-l+1;
	init();
	int res=n*(n+1)>>1;
	for(int i=2;i<=n;i++)res-=ht[i];
	n=_n;
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1,j=0;i<=n;i++){
		int l=0,r=i-1,mid;
		while(l<r)qry(mid=l+r+1>>1,i)-qry(mid,i-1)^i-mid+1?l=mid:r=mid-1;
		a[i]=!l?++j:a[l];
	}
	printf("!");for(int i=1;i<=n;i++)printf(" %d",a[i]);fflush(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

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

result:

wrong answer Wrong Answer.