QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488790 | #8819. CNOI Knowledge | czc | WA | 1ms | 3600kb | C++14 | 958b | 2024-07-24 15:19:43 | 2024-07-24 15:19:44 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
const ull p=131;
using namespace std;
int n;
inline int ask(int l,int r){
cout<<"? "<<l<<" "<<r<<endl;
int x; cin>>x;
return x;
}
unordered_map<ull,int> mp;
const int maxn=1e3+5;
int s[maxn],cnt[maxn],tot;
ull h[maxn],pw[maxn];
inline int get(int l,int r){
int ret=0;
for(int i=l;i<=r;i++) ret+=cnt[i];
return ret;
}
int main(){
cin>>n;
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*p;
for(int i=1;i<=n;i++){
if(i==1 || get(1,i-1)+i==ask(1,i)){
s[i]=++tot;
}
else{
int l=2,r=i-1;
while(l<r){
int mid=(l+r)>>1;
if(get(mid,i-1)+(i-mid+1)==ask(mid,i)) r=mid;
else l=mid+1;
}
s[i]=s[l-1];
}
h[i]=h[i-1]*p+(ull)s[i];
for(int j=1;j<=i;j++){
if(!mp[h[i]-h[j-1]*pw[i-j+1]]){
mp[h[i]-h[j-1]*pw[i-j+1]]=1;
cnt[j]++;
}
}
}
cout<<"! ";
for(int i=1;i<=n;i++) cout<<s[i]<<" ";
cout<<endl;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3600kb
input:
12 3 6 10 15 21 27 10 15 20 34 14 20 26 43 52 19 34 42 62 19 8 13 72 25 9 6
output:
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 4 7 ? 3 7 ? 2 7 ? 1 8 ? 4 8 ? 3 8 ? 2 8 ? 1 9 ? 1 10 ? 5 10 ? 3 10 ? 2 10 ? 1 11 ? 6 11 ? 8 11 ? 7 11 ? 1 12 ? 6 12 ? 9 12 ? 10 12 ! 1 2 3 4 5 6 2 2 7 2 2 2
result:
wrong answer Wrong Answer.