QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488950 | #8819. CNOI Knowledge | msk_sama | RE | 1ms | 3780kb | C++20 | 1.5kb | 2024-07-24 16:35:25 | 2024-07-24 16:35:33 |
Judging History
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 ?...