QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488899 | #8819. CNOI Knowledge | liujunyi123 | WA | 1ms | 3628kb | C++14 | 843b | 2024-07-24 16:11:12 | 2024-07-24 16:11:14 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1005,bs=100007;
int n,m,x,a[N],cnt[N];
ull hs[N],pw[N];
map<ull,int> mp;
int ask(int l,int r){
cout<<"? "<<l<<" "<<r<<endl;
return cin>>x,x;
}
int get(int l,int r){int sum=0;
for(int i=l;i<=r;i++)sum+=cnt[i];
return sum;
}
int main(){
cin>>n,a[1]=m=pw[0]=cnt[1]=1;
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*bs;
for(int i=2;i<=n;i++){
int l=1,r=i-1,res=i;
while(l<=r){int mid=(l+r)>>1;
if(get(mid,i-1)+(i-mid+1)==ask(mid,i))r=mid-1,res=mid;
else l=mid+1;
}
a[i]=res==1?++m:a[res-1];
hs[i]=hs[i-1]*bs+a[i];
for(int j=1;j<=i;j++){
ull x=hs[i]-hs[j-1]*pw[i-j+1];
if(mp.count(x))cnt[mp[x]]--;
mp[x]=j,cnt[j]++;
}
}
cout<<"!";
for(int i=1;i<=n;i++)cout<<" "<<a[i];
cout<<endl;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3628kb
input:
12 3 6 3 6 10 10 6 3 10 6 3 15 6 3 14 6 3 20 10 6 3 19 9 5 25 8 5 25 9 6 3
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 1 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 ? 5 11 ? 8 11 ? 9 11 ? 6 12 ? 9 12 ? 10 12 ? 11 12 ! 1 2 1 1 1 1 1 1 1 1 1 1
result:
wrong answer Wrong Answer.