QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489273#8819. CNOI KnowledgeDEMONKILLERWA 0ms3896kbC++141.2kb2024-07-24 19:16:192024-07-24 19:16:20

Judging History

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

  • [2024-07-24 19:16:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3896kb
  • [2024-07-24 19:16:19]
  • 提交

answer

#include<bits/stdc++.h>
#define N 1010
using namespace std;
int query(int l,int r){
    printf("? %d %d\n",l,r);
    fflush(stdout);
    int x;
    scanf("%d",&x);
    return x;
}
int n,cnt,ans[N],sum[N],s[N],c[N],nxt[N],vis[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int l=1,r=i-1,Res=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(query(mid,i)-sum[mid]<=i-mid){
                l=mid+1;
                Res=mid;
            }
            else r=mid-1;
        }
        if(!Res)ans[i]=++cnt;
        else ans[i]=ans[Res];
        for(int j=1;j<=i;j++){
            s[i-j+1]=ans[i];
            vis[i]=0;
        }
        for(int j=2,k=0;j<=i;j++){
            while(k&&s[k+1]!=s[j])k=nxt[k];
            if(s[k+1]==s[j])k++;
            nxt[j]=k;
        }
        for(int j=2;j<=i;j++){
            if(nxt[j]&&!vis[nxt[j]]){
                c[j]=0;
                vis[nxt[j]]=true;
            }
            else c[j]=1;
        }
        for(int j=1;j<=i;j++){
            c[j]+=c[j-1];
            sum[i-j+1]+=c[j];
        }
    }
    putchar('!');
    for(int i=1;i<=n;i++)
        printf(" %d",ans[i]);
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3896kb

input:

12
3
6
6
10
10
15
10
21
15
27
14
26
34
20
34
43
19
42
52
25
51
62
25
50
72

output:

? 1 2
? 1 3
? 2 4
? 1 4
? 2 5
? 1 5
? 3 6
? 1 6
? 3 7
? 1 7
? 4 8
? 2 8
? 1 8
? 4 9
? 2 9
? 1 9
? 5 10
? 2 10
? 1 10
? 5 11
? 2 11
? 1 11
? 6 12
? 3 12
? 1 12
! 1 2 3 4 5 6 7 8 9 10 11 12

result:

wrong answer Wrong Answer.