QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489119#8819. CNOI Knowledgewhite_iceWA 1ms3912kbC++171.6kb2024-07-24 18:15:202024-07-24 18:15:20

Judging History

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

  • [2024-07-24 18:15:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3912kb
  • [2024-07-24 18:15:20]
  • 提交

answer

//2024.7.24
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn long long
const int oo=1003;

int st[oo],f[oo];
itn sp[oo];

int que1(int l){return f[l];}
int que2(int l,int r){
    printf("? %d %d\n",l,r);
    fflush(stdout);
    int x;scanf("%d",&x);
    return x;
}

int nxt[oo];

void get(int n){
    for(int i=1;i<=n;i++)
        sp[i]=st[n-i+1];

    nxt[1]=0;

    for(int i=2,j=0;i<=n;i++){
        while(j&&sp[i]!=sp[j+1])
            j=nxt[j];
        if(sp[i]==sp[j+1])
            j++;
        nxt[i]=j;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int n;
    cin >> n;    
    st[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(que1(mid)+i-mid+1==que2(mid,i))
                p=mid,r=mid-1;
            else l=mid+1;
        }

        if(p==1)
            st[i]=++tot;
        else st[i]=st[p-1];

        get(i);
        int len=0,mx=0;

        for(int j=i;j>=p;j--)
            f[j]+=i-j+1;

        for(int j=p-1;j;j--){
            while(len&&st[j]!=st[i-len])
                len=nxt[len];
            if(st[j]==st[i-len]){
                len++;
                mx=max(mx,len);
            }
            f[j]+=i-j+1-mx;
        }
    }

    cout << "! ";

    for(int i=1;i<=n;i++){
        if(i!=n)
            cout << st[i];
        else cout << st[i];
    }
    fflush(stdout);
    return 0;
}

詳細信息

Test #1:

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

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

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
! 123456257756

result:

wrong answer format  Expected int32, but "123456257756" found