QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488788 | #8819. CNOI Knowledge | czc | WA | 1ms | 3812kb | C++14 | 957b | 2024-07-24 15:19:22 | 2024-07-24 15:19:23 |
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: 3812kb
input:
12
output:
?1 2
result:
wrong answer Invalid output.