QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
Tip: Click on the bar to expand more detailed information
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.