QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489496#8819. CNOI KnowledgeEdwin_VanCleefWA 1ms4060kbC++141.7kb2024-07-24 20:41:552024-07-24 20:41:55

Judging History

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

  • [2024-07-24 20:41:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4060kb
  • [2024-07-24 20:41:55]
  • 提交

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);
}

Details

Tip: Click on the bar to expand more detailed information

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.