QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489231#8819. CNOI Knowledgec20150005WA 1ms3776kbC++14856b2024-07-24 19:04:232024-07-24 19:04:24

Judging History

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

  • [2024-07-24 19:04:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3776kb
  • [2024-07-24 19:04:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;
int rd(int x=0,char c=getchar()){int f=1;while(!isdigit(c))f=(c^'-'?1:-1),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x*f;}
const int N=1e3+3;
int n,a[N],s[N],S,c[N];
using ull=unsigned long long;
const ull p=19260817;
ull h[N];
map<ull,int> mp;
int main(){
	n=rd();a[1]=s[1]=h[1]=++S;
	for(int i=2;i<=n;i++){
		int l=1,r=i-1,p=1;
		while(l<=r){
			int mid=(l+r)>>1;
			cout<<"? "<<mid<<" "<<i<<endl;
			int x=rd();
			if(x==s[mid]+i-mid+1)p=mid,r=mid-1;
			else l=mid+1;
		}
		if(p==1)a[i]=++S;
		else a[i]=a[p-1];
		for(int j=i;j>=1;j--){
			h[j]=h[j]*p+a[i];
			c[mp[h[j]]+1]++;
			c[j+1]--;
		}
		for(int j=1;j<=i;j++)c[j]+=c[j-1],s[j]+=c[j],mp[h[j]]=j;
	}
	cout<<"! ";
	for(int i=1;i<=n;i++)printf("%d ",a[i]);
	cout<<endl;
	return 0;
}

详细

Test #1:

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

input:

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

output:

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

result:

wrong answer Wrong Answer.