QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488822#8819. CNOI Knowledge11d10xyWA 1ms3716kbC++14827b2024-07-24 15:33:282024-07-24 15:33:28

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 15:33:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3716kb
  • [2024-07-24 15:33:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using u64=unsigned long long;
int qry(int l,int r){
   cout<<"? "<<l<<' '<<r<<'\n',fflush(stdout);
   int x;cin>>x;return x;
}
int s[1010],b[1010],res[1010],tot=1;
unordered_map<u64,int>lst;
int main(){
   int n;cin>>n;
   s[1]=1,res[1]=1,lst[1]=1;
   for(int i=2;i<=n;i++){
      int l=0,r=i-1;
      while(l<r){
         int mid=l+r+1>>1;
         if(qry(mid,i)-res[mid]<i-mid+1)l=mid;
         else r=mid-1;
      }
      s[i]=l?s[l]:++tot;
      u64 h=0;
      memset(b,0,sizeof(b));
      for(int k=i;k>=1;k--){
         h=h*13331+s[k];
         int&p=lst[h];
         b[p+1]++,p=k;
      }
      for(int k=1;k<=i;k++)b[k]+=b[k-1],res[k]+=b[k];
   }
   printf("! ");
   for(int i=1;i<=n;i++)printf("%d ",s[i]);
   fflush(stdout);
   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3716kb

input:

12
3
6
6
3
10
6
3
10
6
3
15
6
3
14
6
3
20
10
6
3
19
9
5
2
25
8
5
3
25
9
6
3

output:

? 1 2
? 1 3
? 2 4
? 3 4
? 2 5
? 3 5
? 4 5
? 3 6
? 4 6
? 5 6
? 3 7
? 5 7
? 6 7
? 4 8
? 6 8
? 7 8
? 4 9
? 6 9
? 7 9
? 8 9
? 5 10
? 7 10
? 8 10
? 9 10
? 5 11
? 8 11
? 9 11
? 10 11
? 6 12
? 9 12
? 10 12
? 11 12
! 1 2 3 3 3 3 3 3 3 3 3 3 

result:

wrong answer Wrong Answer.