QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#778876 | #6303. Inversion | liuwei# | TL | 1ms | 3544kb | C++14 | 1.5kb | 2024-11-24 16:40:19 | 2024-11-24 16:40:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a;i <= b;i++)
#define pre(i, a, b) for(int i = a;i >= b;i--)
#define pb push_back
const int N=2e3+5;
int ask(int l,int r){
if(l>=r)return 0;
cout<<"?"<<" "<<l<<" "<<r<<endl;
cout.flush();
int x;
cin>>x;
return x;
}
int get(int l,int r){//得到l和r的大小关系
int x=(ask(l,r)-ask(l+1,r)-ask(l,r-1)+ask(l+1,r-1)+4)%2;
// cout<<l<<" @@"<<r<<" "<<x<<endl;
return x;
}
int p[N];
void solve(int l,int r) {
if(l==r){
p[l]=l;
return;
}
int mid=(l+r)/2;
solve(1,mid);
solve(mid+1,r);
int len=r-l+1,x=mid,y=r;
vector<int>w;
//cout<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
pre(i,r,l){
if(x>=l&&y>mid)
{
//cout<<x<<" "<<y<<"!"<<endl;
if(get(p[x],p[y])){
w.pb(p[x]);
//cout<<p[x]<<"!"<<p[y]<<" "<<x<<"!!"<<endl;
x--;
}
else
{
w.pb(p[y]);
//cout<<p[x]<<"!"<<p[y]<<" "<<x<<"!!"<<endl;
y--;
}
}
else if(x>=l){
w.pb(p[x]);
x--;
}
else{
w.pb(p[y]);
y--;
}
}
rep(i,0,w.size()-1){
p[r-i]=w[i];
}
//rep(i,l,r)cout<<p[i]<<" "<<l<<" "<<r<<endl;
}
int q[2005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin>> t ;
while (t--) {
int n;
cin>>n;
solve(1,n);
cout<<"! ";
rep(i,1,n){
q[p[i]]=i;
//cout<<p[i]<<endl;
}
rep(i,1,n)cout<<q[i]<<" ";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3544kb
input:
3 0 1 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ? 1 2 ! 2 3 1
result:
ok OK, guesses=5
Test #2:
score: -100
Time Limit Exceeded
input:
1993 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0...
output:
? 1 2 ? 1 2 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 2 3 ? 2 3 ? 1 2 ? 2 3 ? 1 2 ? 2 3 ? 1 2 ? 1 2 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 2 3 ? 2 3 ? 4 5 ? 3 4 ? 3 5 ? 4 5 ? 3 4 ? 2 5 ? 3 5 ? 2 4 ? 3 4 ? 1 5 ? 2 5 ? 1 4 ? 2 4 ? 4 6 ? 5 6 ? 4 5 ? 3 6 ? 4 6 ? 3 5 ? 4 5 ? 2 4 ? 3 4 ? 2 3 ? 2 3 ? 2 6 ? 3 6 ? 2 5 ? 3 5 ? 1 6 ? 2 6 ...