QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489502 | #8819. CNOI Knowledge | yz_ly | AC ✓ | 54ms | 3972kb | C++14 | 2.6kb | 2024-07-24 20:44:26 | 2024-07-24 20:44:27 |
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=sa[rk[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;
}
/*
1 2 3 4 5 6 2 5 7 7 5 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3776kb
input:
12 3 3 6 6 10 6 10 15 10 15 21 10 20 15 14 6 9 14 27 34 43 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 ? 2 9 ? 1 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 7 7 5 6
result:
ok Accepted. 31 queries used.
Test #2:
score: 0
Accepted
time: 54ms
memory: 3880kb
input:
1000 3 2 3 2 5 7 11 8 2 7 2 11 5 7 11 5 3 15 5 2 15 3 2 19 4 2 17 4 2 20 4 2 15 4 2 23 9 13 15 23 11 5 3 31 11 5 3 36 11 5 2 45 15 3 2 48 15 5 7 11 58 16 5 2 59 16 5 8 69 21 8 2 69 20 8 3 5 79 20 8 2 76 20 8 3 5 87 26 8 3 5 88 26 8 2 100 24 8 3 5 98 24 8 2 111 31 11 3 2 108 33 11 5 7 120 33 11 5 2 1...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 11 14 ? 13 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 10 16 ? 9 16 ? 9 17 ? 13 17 ? 15 17 ? 16 17 ? 9...
result:
ok Accepted. 8229 queries used.
Test #3:
score: 0
Accepted
time: 41ms
memory: 3888kb
input:
1000 2 2 5 7 5 2 7 2 7 16 11 11 5 2 11 3 2 14 3 2 11 3 2 13 4 2 7 4 2 15 41 23 20 8 2 28 12 5 8 31 12 5 2 38 11 3 2 38 9 3 2 44 14 5 7 9 44 14 5 2 54 15 3 2 56 14 3 2 65 17 4 2 66 17 7 9 11 76 17 8 2 76 20 8 3 5 87 26 8 2 88 26 8 3 5 102 26 8 3 5 102 26 8 2 115 31 11 5 8 113 28 11 5 3 125 23 11 5 2 ...
output:
? 1 2 ? 2 3 ? 2 4 ? 1 4 ? 3 5 ? 4 5 ? 3 6 ? 5 6 ? 4 7 ? 2 7 ? 3 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 4 14 ? 6 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ? 15 17 ? 16 17 ? 9 ...
result:
ok Accepted. 8243 queries used.
Test #4:
score: 0
Accepted
time: 45ms
memory: 3824kb
input:
1000 3 3 5 5 2 5 8 8 2 8 3 5 12 5 2 11 3 2 16 5 7 11 15 5 3 20 7 3 5 21 8 2 27 7 2 26 4 2 31 5 3 2 27 5 3 2 31 5 3 2 26 5 3 2 35 11 15 17 26 35 14 5 3 44 15 5 2 44 15 3 2 53 19 4 2 55 19 7 9 14 63 19 8 3 5 62 19 8 2 69 24 7 2 70 23 7 15 11 81 23 8 3 5 83 25 7 3 5 99 33 11 5 2 105 34 11 5 8 120 33 11...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 7 10 ? 6 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 10 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 11 14 ? 13 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 15 16 ? 9 17 ? 13 ...
result:
ok Accepted. 8262 queries used.
Test #5:
score: 0
Accepted
time: 49ms
memory: 3832kb
input:
1000 2 2 5 7 5 3 8 2 7 2 9 3 2 5 3 2 6 3 2 11 27 13 20 17 8 2 20 8 3 5 26 8 3 5 26 8 2 31 11 5 8 28 11 5 3 36 11 5 3 34 9 5 3 41 11 5 3 45 14 5 2 55 15 5 8 56 16 5 2 65 21 8 3 5 65 20 8 2 75 20 8 3 5 76 21 8 3 5 87 26 8 2 85 24 8 3 5 95 24 8 2 92 26 8 3 5 101 32 12 5 2 95 31 12 5 8 103 31 11 5 3 103...
output:
? 1 2 ? 2 3 ? 2 4 ? 1 4 ? 3 5 ? 4 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 3 11 ? 5 11 ? 4 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 11 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ? ...
result:
ok Accepted. 8231 queries used.
Test #6:
score: 0
Accepted
time: 41ms
memory: 3972kb
input:
1000 2 3 5 5 2 5 8 8 2 8 3 5 12 5 2 12 5 8 16 5 2 16 5 8 21 8 3 5 21 7 3 5 26 7 3 5 23 7 3 5 27 9 5 3 27 11 5 2 34 11 5 8 34 11 5 3 41 15 5 3 41 14 5 3 48 11 5 3 52 14 5 2 63 19 7 2 66 20 7 11 77 21 8 2 79 21 7 2 91 27 7 16 11 91 27 8 2 104 26 8 3 5 103 26 8 2 115 31 11 3 2 115 32 9 3 2 129 31 5 3 2...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 6 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 8 11 ? 6 12 ? 9 12 ? 11 12 ? 10 12 ? 7 13 ? 10 13 ? 12 13 ? 11 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 13 15 ? 8 16 ? 12 16 ? 14 16 ? 15...
result:
ok Accepted. 8227 queries used.
Test #7:
score: 0
Accepted
time: 23ms
memory: 3968kb
input:
1000 3 2 3 2 5 7 12 8 2 7 2 11 5 7 11 5 3 15 5 2 15 3 2 22 41 50 61 23 8 3 5 29 7 3 5 29 8 2 37 13 23 29 37 13 5 3 45 11 5 3 44 9 5 3 51 11 5 3 47 11 5 3 57 15 29 38 58 17 6 9 69 22 9 3 6 68 21 9 3 6 80 21 9 3 5 80 23 9 13 94 30 9 3 6 94 31 9 2 108 30 9 17 13 110 28 9 17 13 126 36 13 5 2 128 36 13 5...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 3 12 ? 2 12 ? 1 12 ? 7 13 ? 10 13 ? 12 13 ? 11 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 10 16 ? 9 16 ? 9 17 ? 13 ...
result:
ok Accepted. 8343 queries used.
Test #8:
score: 0
Accepted
time: 28ms
memory: 3772kb
input:
1000 3 2 5 9 6 9 13 9 3 5 7 3 5 11 5 2 11 3 2 17 29 22 17 5 2 22 7 2 19 4 2 27 53 35 28 9 15 21 35 13 6 9 33 13 5 2 42 13 5 8 43 11 5 3 52 15 5 3 54 16 5 2 65 17 37 23 29 65 18 5 3 76 23 7 3 5 77 23 9 12 17 89 23 9 3 6 87 23 9 2 100 29 7 2 100 30 7 17 11 115 30 9 17 23 116 30 9 2 131 37 13 5 8 130 3...
output:
? 1 2 ? 2 3 ? 2 4 ? 1 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 5 6 ? 4 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 3 10 ? 4 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 4 14 ? 6 14 ? 8 15 ? 12 15 ? 10 15 ? 9 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ?...
result:
ok Accepted. 8343 queries used.
Test #9:
score: 0
Accepted
time: 35ms
memory: 3932kb
input:
1000 3 3 6 5 2 5 8 8 2 9 18 24 13 5 2 13 24 18 18 5 3 17 5 3 23 9 12 17 23 9 2 29 7 2 27 4 2 32 5 3 2 29 5 3 2 33 5 3 2 33 9 13 15 24 42 15 21 24 33 42 17 6 9 51 17 5 2 51 17 5 9 13 63 23 8 2 67 23 7 2 80 23 7 11 83 21 8 2 95 26 8 3 5 95 29 53 35 44 110 30 9 3 5 111 30 8 2 126 37 11 5 8 125 38 13 23...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 2 7 ? 1 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 3 9 ? 4 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 8 12 ? 7 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 11 14 ? 13 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 15 16 ? 9 17 ? 13 17 ? 15 1...
result:
ok Accepted. 8323 queries used.
Test #10:
score: 0
Accepted
time: 42ms
memory: 3968kb
input:
1000 2 3 5 6 9 6 9 9 2 7 2 12 22 17 11 5 3 15 5 3 17 36 22 29 23 9 2 23 9 13 30 8 3 5 30 8 2 36 11 5 8 33 11 5 3 41 11 5 3 41 12 22 27 32 51 17 5 2 51 18 5 8 61 18 6 9 13 62 18 5 2 74 24 9 13 75 23 9 13 87 23 9 3 5 88 23 7 3 5 100 28 7 3 5 101 28 9 15 21 115 27 9 3 5 115 28 8 2 129 35 13 23 18 127 3...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 1 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 2 8 ? 3 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 3 11 ? 5 11 ? 4 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 9 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ? 15 ...
result:
ok Accepted. 8319 queries used.
Test #11:
score: 0
Accepted
time: 30ms
memory: 3888kb
input:
1000 2 3 5 5 2 5 8 9 13 18 9 3 6 13 5 2 13 5 8 18 6 9 13 18 5 3 24 8 2 24 9 13 18 30 8 3 5 29 8 2 36 11 3 2 36 12 22 29 45 12 23 17 46 13 5 3 55 17 5 3 53 15 5 3 64 15 35 21 64 17 6 9 76 23 9 2 76 24 8 3 5 88 24 9 13 18 89 24 9 2 102 31 9 18 13 102 30 8 2 116 30 8 3 5 115 30 8 2 130 37 11 3 2 130 37...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 2 6 ? 1 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 6 9 ? 5 10 ? 8 10 ? 7 10 ? 6 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 9 13 ? 8 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 15 16 ...
result:
ok Accepted. 8322 queries used.
Extra Test:
score: 0
Extra Test Passed