QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492804 | #8819. CNOI Knowledge | hyxle | WA | 1ms | 3532kb | C++14 | 1.1kb | 2024-07-26 16:19:29 | 2024-07-26 16:19:30 |
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);
cin>>n;
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: 3532kb
input:
12 1 3 3 6 3 1 6 1 3 6 1 3 10 3 1 9 3 1 14 3 1 14 2 1 19 5 1 3 19 6 1 3
output:
? 2 2 ? 1 2 ? 2 3 ? 1 3 ? 3 4 ? 4 4 ? 3 5 ? 5 5 ? 4 5 ? 4 6 ? 6 6 ? 5 6 ? 4 7 ? 6 7 ? 7 7 ? 5 8 ? 7 8 ? 8 8 ? 5 9 ? 8 9 ? 9 9 ? 6 10 ? 9 10 ? 10 10 ? 6 11 ? 9 11 ? 11 11 ? 10 11 ? 7 12 ? 10 12 ? 12 12 ? 11 12 ! 1 1 1 0 0 0 0 0 0 0 0 0
result:
wrong answer Integer 0 violates the range [1, 10^9]