QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488941 | #8819. CNOI Knowledge | thomaswmy | WA | 6ms | 3868kb | C++14 | 839b | 2024-07-24 16:32:03 | 2024-07-24 16:32:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int query(int l,int r) {
printf("? %d %d\n",l,r);
fflush(stdout);
int res;
scanf("%d",&res);
return res;
}
int n;
int a[N],tot;
int cnt[N];
int kmp[N];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
if(query(1,i)-cnt[1]==i) {
a[i]=++tot;
for(int j=1;j<=i;j++) cnt[j]+=i-j+1;
continue;
}
int L=2,R=i-1,mid,res=1;
while(L<=R) {
mid=L+R>>1;
if(query(mid,i)-cnt[mid]<i-mid+1) res=mid,L=mid+1;
else R=mid-1;
}
a[i]=a[res];
cnt[i]++;
kmp[i]=0;
for(int j=i-1,k=0,s=1;j>=1;j--) {
while(k && a[j]!=a[i-k]) k=kmp[i-k+1];
if(a[j]==a[i-k]) k++;
kmp[j]=k;
if(!k) s++;
cnt[j]+=s;
}
}
printf("! ");
for(int i=1;i<=n;i++) printf("%d ",a[i]);
fflush(stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
input:
12 1 3 6 10 15 21 27 10 20 15 34 14 6 9 43 52 19 9 5 2 62 19 8 5 72 25 9 19
output:
? 1 1 ? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 4 7 ? 2 7 ? 3 7 ? 1 8 ? 4 8 ? 6 8 ? 5 8 ? 1 9 ? 1 10 ? 5 10 ? 7 10 ? 8 10 ? 9 10 ? 1 11 ? 6 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. 28 queries used.
Test #2:
score: -100
Wrong Answer
time: 6ms
memory: 3868kb
input:
1000 1 3 5 2 7 3 2 11 5 7 16 8 5 2 21 7 3 2 27 34 11 5 3 41 15 26 19 48 15 7 3 2 57 19 4 3 2 66 17 4 3 2 75 20 5 3 2 84 15 5 3 2 96 23 9 13 15 108 23 11 5 3 124 31 15 23 27 140 36 81 61 51 41 156 45 95 73 62 51 172 48 98 140 156 188 58 112 156 172 208 59 127 174 191 229 69 143 193 211 251 69 144 194...
output:
? 1 1 ? 1 2 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 3 4 ? 1 5 ? 3 5 ? 2 5 ? 1 6 ? 3 6 ? 4 6 ? 5 6 ? 1 7 ? 4 7 ? 5 7 ? 6 7 ? 1 8 ? 1 9 ? 5 9 ? 7 9 ? 8 9 ? 1 10 ? 5 10 ? 3 10 ? 4 10 ? 1 11 ? 6 11 ? 8 11 ? 9 11 ? 10 11 ? 1 12 ? 6 12 ? 9 12 ? 10 12 ? 11 12 ? 1 13 ? 7 13 ? 10 13 ? 11 13 ? 12 13 ? 1 14 ? 7 14 ? 10 14 ?...
result:
wrong answer Wrong Answer.