QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488731 | #8819. CNOI Knowledge | maojun | WA | 1ms | 3904kb | C++23 | 1.5kb | 2024-07-24 14:46:10 | 2024-07-24 14:46:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N];
int s[N],sa[N],ht[N];
inline void init(){
static pair<int,int> bl[N];
#define fi first
#define se second
#define mp make_pair
static int rk[N];
static auto grk=[&](){
static int c[N],x[N],y[N];
memset(c,0,n+1<<2);
for(int i=1;i<=n;i++)c[bl[i].se]++;
for(int i=1;i<=n;i++)c[i]+=c[i-1];
for(int i=n;i;i--)y[c[bl[i].se]--]=i;
memset(c,0,n+1<<2);
for(int i=1;i<=n;i++)c[bl[i].fi]++;
for(int i=1;i<=n;i++)c[i]+=c[i-1];
for(int i=n;i;i--)x[c[bl[y[i]].fi]--]=y[i];
for(int i=1,j=0;i<=n;i++)rk[x[i]]=j+=bl[x[i]]!=bl[x[i-1]];
};
static int t[N];memcpy(t,s,sizeof t);sort(t+1,t+n+1);
for(int i=1,j=0;i<=n;i++)rk[t[i]]=j+=t[i]!=t[i-1];
for(int i=1;i<=n;i++)bl[i]=mp(rk[s[i]],0);
for(int k=1;k<=n;k<<=1){grk();for(int i=1;i<=n;i++)bl[i]=mp(rk[i],i+k>n?0:rk[i+k]);}
grk();for(int i=1;i<=n;i++)sa[rk[i]]=i;
for(int i=1,h=0;i<=n;i++){h&&h--;for(int j=sa[rk[i]-1];i+h<=n&&j+h<=n&&s[i+h]==s[j+h];h++);ht[rk[i]]=h;}
}
inline int qry(int l,int r){
if(!a[r]){
printf("? %d %d\n",l,r);fflush(stdout);
int x;scanf("%d",&x);return x;
}
int _n=n;n=r-l+1;
init();
int res=n*(n+1)>>1;
for(int i=2;i<=n;i++)res-=ht[i];
n=_n;
return res;
}
int main(){
scanf("%d",&n);
for(int i=1,j=0;i<=n;i++){
int l=0,r=i-1,mid;
while(l<r)qry(mid=l+r+1>>1,i)-qry(mid,i-1)^i-mid+1?l=mid:r=mid-1;
a[i]=!l?++j:a[l];
}
printf("!");for(int i=1;i<=n;i++)printf(" %d",a[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: 3904kb
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 3 25 9 6
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 ? 10 11 ? 6 12 ? 9 12 ? 10 12 ! 1 2 3 4 5 6 2 5 5 5 5 5
result:
wrong answer Wrong Answer.