QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488851#8819. CNOI KnowledgelefyWA 1ms3868kbC++14994b2024-07-24 15:50:092024-07-24 15:50:09

Judging History

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

  • [2024-07-24 15:50:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3868kb
  • [2024-07-24 15:50:09]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
int a[N],f[N];
int q1(int l){return f[l];}
int q2(int l,int r){
    printf("? %d %d\n",l,r);
    fflush(stdout);
    int x;scanf("%d",&x);
    return x;
}
int main(){
    int n;scanf("%d",&n);    
    a[1]=1;f[1]=1;int tot=1;
    for(int i=2;i<=n;i++){
        int l=1,r=i-1,p=i;
        while(l<=r){
            int mid=l+r>>1;
            if(q1(mid)+i-mid+1==q2(mid,i))p=mid,r=mid-1;
            else l=mid+1;
        }
        if(p==1)a[i]=++tot;
        else a[i]=a[p-1];

        int len=0,mx=0;
        for(int j=i;j>=p;j--)f[j]+=i-j+1;
        for(int j=p-1;j;j--){
            if(a[j]==a[i-len]){
                len++;mx=max(mx,len);
            }else len=0;
            f[j]+=i-j+1-len;
        }
    }
    printf("! ");
    for(int i=1;i<=n;i++){
        if(i!=n)printf("%d ",a[i]);
        else printf("%d\n",a[i]);
    }
    fflush(stdout);
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3868kb

input:

12
3
6
6
10
10
15
10
21
15
27
20
14
6
9
20
10
14
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
? 6 9
? 5 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 4 4 5 5

result:

wrong answer Wrong Answer.