QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488950#8819. CNOI Knowledgemsk_samaRE 1ms3780kbC++201.5kb2024-07-24 16:35:252024-07-24 16:35:33

Judging History

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

  • [2024-07-24 16:35:33]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3780kb
  • [2024-07-24 16:35:25]
  • 提交

answer

#include <bits/stdc++.h>
#define MISAKA main
#define ll long long
using namespace std;
inline int read(){
   char ch=getchar();int f=1,x=0;
   while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
   return x*f;
}
const double eps=1e-9;
const int N=1e3+10,inf=1e9,mod=998244353;
int n,a[N],fa[N],len[N],ed=1,cnt=1,num=1,f[N][N],mx=1;
unordered_map<int,int> ch[N];
void insert(int c){
    int p=ed,np=++cnt;len[np]=len[p]+1;ed=np;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else{
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else{
            int nq=++cnt;fa[nq]=fa[q];len[nq]=len[p]+1;
            ch[nq]=ch[q];fa[q]=fa[np]=nq;
            for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}
int ask(int l,int r){cout<<"? "<<l<<' '<<r<<'\n'<<flush;return read();}
mt19937 rd(time(0));
signed MISAKA(){
    n=read();a[1]=f[1][1]=1;
    for(int i=2;i<=n;i++){
        if(ask(1,i)-f[1][i-1]==i) a[i]=++num;
        else{
            int l=1,r=i-1;
            while(r>=l){
                int mid=l+r>>1;
                if(ask(mid,i)-f[mid][i-1]==i-mid+1) r=mid-1;
                else l=mid+1;
            }
            a[i]=a[r];
        }
        for(int i=0;i<=cnt;i++) fa[i]=len[i]=0,ch[i].clear();
        int res=0;ed=cnt=1;
        for(int j=i;j>=1;j--) insert(a[j]),res+=len[ed]-len[fa[ed]],f[j][i]=res;
    }
    cout<<"! ";
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<flush;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3780kb

input:

12
3
6
10
15
21
27
15
27
20
34
14
6
9
43
52
19
9
5
2
62
25
8
5
72
25
9
19

output:

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

result:

ok Accepted. 27 queries used.

Test #2:

score: -100
Runtime Error

input:

1000
3
5
5
2
7
3
2
11
7
11
16
8
5
2
21
11
3
2
27
11
5
7
34
15
8
5
3
41
15
8
5
2
48
19
7
3
2
57
19
4
3
2
66
23
5
3
2
75
20
5
3
2
84
23
5
3
2
96
23
9
13
15
108
31
14
8
5
3
124
31
15
7
5
3
140
41
16
8
5
2
156
45
15
7
3
2
172
55
20
7
15
11
188
58
21
8
5
2
208
68
21
8
5
229
69
21
8
5
2
251
80
26
12
5
8
2...

output:

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

result: