QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243618 | #6303. Inversion | Vengeful_Spirit# | WA | 56ms | 3404kb | C++14 | 1.3kb | 2023-11-08 15:05:56 | 2023-11-08 15:05:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int query(int l,int r){
assert(l<=r);
if(l==r)return 0;
cout<<"? "<<l<<" "<<r<<endl;
int res;
cin>>res;
return res;
}
int main(){
int n;
cin>>n;
vector<int>b(n);
for(int i=1;i<n;i++){
b[i]=query(i,i+1);
}
vector<int>pos(n+1);
pos[1]=1;
for(int i=2;i<=n;i++){
int l=1,r=i-1,res=0;
auto check=[&](int mid){
// cout<<"check "<<mid<<endl;
int x=query(pos[mid],i);
int y=query(pos[mid]+1,i);
return x^y^b[pos[mid]]^1;
};
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
res=mid;
l=mid+1;
}
else r=mid-1;
}
// cout<<"res > "<<res<<endl;
for(int j=i;j>res;j--){
pos[j]=pos[j-1];
}
pos[res+1]=i;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
a[pos[i]]=i;
// cout<<pos[i]<<" ";
}
// cout<<endl;
// for(int i=1;i<=n;i++)cout<<a[i]<<" ";
// cout<<endl;
}
vector<int>a(n+1);
for(int i=1;i<=n;i++){
a[pos[i]]=i;
}
cout<<"! ";
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3372kb
input:
3 0 1 0 0 1
output:
? 1 2 ? 2 3 ? 1 2 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=5
Test #2:
score: -100
Wrong Answer
time: 56ms
memory: 3404kb
input:
1993 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0...
output:
? 1 2 ? 2 3 ? 3 4 ? 4 5 ? 5 6 ? 6 7 ? 7 8 ? 8 9 ? 9 10 ? 10 11 ? 11 12 ? 12 13 ? 13 14 ? 14 15 ? 15 16 ? 16 17 ? 17 18 ? 18 19 ? 19 20 ? 20 21 ? 21 22 ? 22 23 ? 23 24 ? 24 25 ? 25 26 ? 26 27 ? 27 28 ? 28 29 ? 29 30 ? 30 31 ? 31 32 ? 32 33 ? 33 34 ? 34 35 ? 35 36 ? 36 37 ? 37 38 ? 38 39 ? 39 40 ? 40 ...
result:
wrong answer Wa.