QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492803 | #8819. CNOI Knowledge | hyxle | WA | 1ms | 3604kb | C++14 | 1.1kb | 2024-07-26 16:18:18 | 2024-07-26 16:18:20 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define R register
#define ull unsigned ll
using namespace std;
const int N=1e3+5,base=647;
unordered_map<ull,int> mp;
inline int ask(int l,int r){int _;cout<<'?'<<' '<<l<<' '<<r<<endl;cin>>_;return _;}
int f[N],ans[N],n,cntdiff,tag[N];
inline int getid(int l,int r){
int rr=r,res=r;
while(l<=r){
int mid=l+r+1>>1;
if(ask(mid,rr)-f[mid]==rr-mid+1)res=mid,r=mid-1;
else l=mid+1;
}
return res;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
ans[1]=f[1]=cntdiff=mp[1]=1;
for(R int i=2;i<=n;++i){
ull _h=0;
int id=getid(1,i);
if(!id)ans[i]=++cntdiff;
else ans[i]=ans[id];
for(R int j=1;j<=i;++j)tag[i]=0;
for(R int j=i;j>=1;--j){
_h=_h*base+ans[j];
++tag[mp[_h]+1],--tag[j+1];
mp[_h]=j;
}
for(R int j=1;j<=i;++j)tag[j]+=tag[j-1],f[j]+=tag[j];
}
cout<<"! ";for(R int i=1;i<=n;++i)cout<<ans[i]<<' ';
cout<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3604kb
input:
output:
!
result:
wrong answer format Unexpected end of file - int32 expected