QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489473 | #8819. CNOI Knowledge | yz_ly | WA | 1ms | 3812kb | C++14 | 2.6kb | 2024-07-24 20:30:39 | 2024-07-24 20:30:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
inline void work(int k){
if(k<0){
putchar('-');
k=-k;
}
if(k>9)
work(k/10);
putchar(k%10+'0');
}
/*
考虑在已知字符串后面加入一个字符,如果这个字符是一个新字符,那么新添加的本质不同的字符串就是前面的长度+1
前面已经知道了,所以本质不同的字符串可以算,只需要问一次就行了
那么我们二分满足增添的个数是长度+1的位置就能够确定这个字符串是什么就行了
每次暴力SA,时间复杂度O(sum(ilog^2i)),询问次数O(logi)
*/
int n,a[1005],now=1,sa[1005],rk[1005],y[2005],tot[1005],height[1005],m;
void SA(int a[],int n){
m=1e3;
for(int i=1;i<=m;i++){
rk[i]=sa[i]=tot[i]=0;
}
for(int i=1;i<=2*n;i++){
y[i]=0;
}
for(int i=1;i<=n;i++){
rk[i]=a[i];
tot[rk[i]]++;
}
for(int i=1;i<=m;i++){
tot[i]+=tot[i-1];
}
for(int i=n;i;i--){
sa[tot[rk[i]]--]=i;
}
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++){
y[++num]=i;
}
for(int i=1;i<=n;i++){
if(sa[i]>k)
y[++num]=sa[i]-k;
}
for(int i=1;i<=m;i++){
tot[i]=0;
}
for(int i=1;i<=n;i++){
tot[rk[y[i]]]++;
}
for(int i=1;i<=m;i++){
tot[i]+=tot[i-1];
}
for(int i=n;i;i--){
sa[tot[rk[y[i]]]--]=y[i];
}
for(int i=1;i<=n;i++){
swap(rk[i],y[i]);
}
num=rk[sa[1]]=1;
for(int i=2;i<=n;i++){
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])
rk[sa[i]]=num;
else
rk[sa[i]]=++num;
}
if(num==n)
break;
m=num;
}
}
void LCP(int a[],int n){
int k=0;
for(int i=1;i<=n;i++){
if(rk[i]==1)
continue;
if(k)
k--;
int last=rk[sa[i]-1];
while(last+k<=n&&i+k<=n&&a[i+k]==a[last+k]){
k++;
}
height[rk[i]]=k;
}
}
int solve(int l,int r){
SA(a+l-1,r-l+1);
LCP(a+l-1,r-l+1);
int sum=(r-l+1)*(r-l+2)/2;
for(int i=1;i<=r-l+1;i++){
sum-=height[i];
}
return sum;
}
int main(){
a[1]=1;
scanf("%d",&n);
for(int i=2;i<=n;i++){
int l=1,r=i;
while(l<r){
int mid=(l+r)>>1;
printf("? %d %d\n",mid,i);
fflush(stdout);
int val=0;
scanf("%d",&val);
if(solve(mid,i-1)+i-mid+1==val)
r=mid;
else
l=mid+1;
}
if(l==1)
a[i]=++now;
else
a[i]=a[l-1];
}
printf("! ");
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
putchar('\n');
fflush(stdout);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3812kb
input:
12 3 3 6 6 10 6 10 15 10 15 21 10 20 15 14 6 9 14 27 20 19 5 2 19 5 8 25 9 13 19
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 1 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 2 6 ? 1 6 ? 4 7 ? 2 7 ? 3 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 3 9 ? 4 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 8 11 ? 6 12 ? 9 12 ? 8 12 ? 7 12 ! 1 2 3 4 5 6 2 5 4 4 5 6
result:
wrong answer Wrong Answer.