QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488943 | #8819. CNOI Knowledge | thomaswmy | RE | 0ms | 0kb | C++14 | 871b | 2024-07-24 16:33:58 | 2024-07-24 16:33:58 |
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;
assert(cnt[j]==query(j,i));
}
}
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
Runtime Error
input:
12 1 3 6 10 15 21 27 10 20 15 3 6 10 15 20 27 34 14 6 9 3 6 9 14 20 26 34 43 52 19 9 5 2 2 5 9 14 19 26 34 42 52 62 19 8 5 3 5 8 13 19 25
output:
? 1 1 ? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 4 7 ? 2 7 ? 3 7 ? 6 7 ? 5 7 ? 4 7 ? 3 7 ? 2 7 ? 1 7 ? 1 8 ? 4 8 ? 6 8 ? 5 8 ? 7 8 ? 6 8 ? 5 8 ? 4 8 ? 3 8 ? 2 8 ? 1 8 ? 1 9 ? 1 10 ? 5 10 ? 7 10 ? 8 10 ? 9 10 ? 9 10 ? 8 10 ? 7 10 ? 6 10 ? 5 10 ? 4 10 ? 3 10 ? 2 10 ? 1 10 ? 1 11 ? 6 11 ? 8 11 ? 9 11 ? 10 1...