QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253747 | #6303. Inversion | SATSKY | WA | 1ms | 3524kb | C++20 | 751b | 2023-11-17 13:46:14 | 2023-11-17 13:46:14 |
Judging History
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.