QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489119 | #8819. CNOI Knowledge | white_ice | WA | 1ms | 3912kb | C++17 | 1.6kb | 2024-07-24 18:15:20 | 2024-07-24 18:15:20 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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