QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492804#8819. CNOI KnowledgehyxleWA 1ms3532kbC++141.1kb2024-07-26 16:19:292024-07-26 16:19:30

Judging History

This is the latest submission verdict.

  • [2024-07-26 16:19:30]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3532kb
  • [2024-07-26 16:19:29]
  • Submitted

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]