QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489496 | #8819. CNOI Knowledge | Edwin_VanCleef | WA | 1ms | 4060kb | C++14 | 1.7kb | 2024-07-24 20:41:55 | 2024-07-24 20:41:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n,sigma=1,a[maxn],len[maxn<<1],lnk[maxn<<1],lst,cnt,f[maxn<<1];
map<int,int> tr[maxn<<1];
int query(int x,int y){
printf("? %d %d\n",x,y);
fflush(stdout);
int res;
scanf("%d",&res);
return res;
}
void clear(int x){
len[x]=lnk[x]=f[x]=0;
tr[x].clear();
}
void insert(int c){
int cur=++cnt,p=lst;
clear(cnt);
len[cur]=len[lst]+1;
while(p&&tr[p].find(c)==tr[p].end()){
tr[p][c]=cur;
p=lnk[p];
}
if(!p) lnk[cur]=1;
else{
int q=tr[p][c];
if(len[q]==len[p]+1) lnk[cur]=q;
else{
int cln=++cnt;
len[cln]=len[p]+1;
lnk[cln]=lnk[q];
for(auto tmp:tr[q]) tr[cln][tmp.first]=tmp.second;
lnk[cur]=lnk[q]=cln;
while(p&&tr[p].find(c)!=tr[p].end()&&tr[p][c]==q){
tr[p][c]=cln;
p=lnk[p];
}
}
}
lst=cur;
}
int dfs(int u){
if(f[u]) return f[u];
for(auto tmp:tr[u]) f[u]+=dfs(tmp.second)+1;
return f[u];
}
int myquery(int l,int r){
cnt=lst=1;
clear(1);
for(int i=l;i<=r;i++) insert(a[i]);
return dfs(1);
}
int main(){
scanf("%d",&n);
a[1]=1;
for(int i=2;i<=n;i++){
int l=1,r=i-1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(myquery(mid,i-1)+i-mid+1!=query(mid,i)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
if(!ans) a[i]=++sigma;
else a[i]=a[ans];
}
cout<<"! ";
for(int i=1;i<=n;i++) printf("%d ",a[i]);
fflush(stdout);
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4060kb
input:
12 3 6 6 10 10 15 10 21 15 27 20 14 6 9 20 34 43 19 9 5 2 25 8 5 25 9 19 13
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 ? 2 9 ? 1 9 ? 5 10 ? 7 10 ? 8 10 ? 9 10 ? 5 11 ? 8 11 ? 9 11 ? 6 12 ? 9 12 ? 7 12 ? 8 12 ! 1 2 3 4 5 6 2 5 1 1 5 5
result:
wrong answer Wrong Answer.