QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492808#8819. CNOI KnowledgehyxleWA 1ms3492kbC++141.1kb2024-07-26 16:20:472024-07-26 16:20:47

Judging History

This is the latest submission verdict.

  • [2024-07-26 16:20:47]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3492kb
  • [2024-07-26 16:20:47]
  • 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[j]=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: 3492kb

input:

12
1
3
3
6
3
6
6
1
3
6
1
3
10
3
6
9
3
6
14
3
6
14
2
1
19
5
8
19
6
9

output:

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

result:

wrong answer Integer 0 violates the range [1, 10^9]