QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243653 | #6303. Inversion | Vengeful_Spirit# | WA | 55ms | 3420kb | C++14 | 2.2kb | 2023-11-08 15:30:37 | 2023-11-08 15:30:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int A[10001];
/*
int query(int l,int r){
assert(l<=r);
if(l==r)return 0;
cout<<"? "<<l<<" "<<r<<endl;
int cnt=0;
for(int i=l;i<=r;i++){
for(int j=i+1;j<=r;j++){
if(A[i]>A[j])cnt++;
}
}
cout<<cnt%2<<endl;
return cnt%2;
}
*/
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(){
// srand(time(0));
int n;
cin>>n;
// for(int i=1;i<=n;i++)A[i]=i;
// random_shuffle(A+1,A+1+n);
// for(int i=1;i<=n;i++)cout<<A[i]<<" ";cout<<endl;
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 myque=[&](int lim){
int cnt=0;
for(int i=1;i<=n;i++){
if(i<lim&&pos[i]>pos[lim])cnt++;
}
return cnt&1;
};
auto check=[&](int mid){
int x=query(pos[mid],i);
int y=query(pos[mid]+1,i);
int z=myque(mid);
/* if(i>pos[mid]+1)cout<<"check "<<i<<" "<<pos[mid]<<" "<<(x^y^b[pos[mid]]^1)<<endl;
else cout<<"check "<<i<<" "<<pos[mid]<<" "<<(x^y^1)<<endl;
if(i>pos[mid]+1)return x^y^b[pos[mid]]^1;
else return x^y^1;
*/
// cout<<"check "<<i<<" "<<pos[mid]<<" "<<(x^y^z^1)<<endl;
return x^y^z^1;
};
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
res=mid;
l=mid+1;
}
else r=mid-1;
}
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<<"! ";
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: 3376kb
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: 55ms
memory: 3420kb
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 output format Unexpected end of file - int32 expected