QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253747#6303. InversionSATSKYWA 1ms3524kbC++20751b2023-11-17 13:46:142023-11-17 13:46:14

Judging History

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

  • [2023-11-17 13:46:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3524kb
  • [2023-11-17 13:46:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int query(int L,int R){cout<<"? "<<L<<" "<<R<<endl;int x;cin>>x;return x;}
void solve()
{
    int n;cin>>n;
    vector<int>pos(n+1);pos[1]=1;
    for(int i=2,lo,hi;i<=n;i++)
    {
        for(lo=1,hi=i;lo<hi-1;)
        {
            int mid=(lo+hi)/2,cnt=0;for(int j=1;j<mid;j++)cnt+=(pos[j]>pos[mid]);
            (query(pos[mid],i)!=(query(pos[mid]+1,i)+cnt)%2)?hi=mid:lo=mid+1;//val[mid]>val[i]
        }
        for(int j=i-1;j>=lo;j--)pos[j+1]=pos[j];pos[lo]=i;//pre i pos valasc sort
    }
    vector<int>ans(n+1);for(int i=1;i<=n;i++)ans[pos[i]]=i;
    cout<<"! ";for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
}
int main(){ios_base::sync_with_stdio(0);cin.tie(0);solve();}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0
1

output:

? 1 3
? 2 3
! 2 1 3 

result:

wrong answer Wa.