QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #661312 | #8939. Permutation | DBsoleil# | WA | 6ms | 3672kb | C++23 | 1.5kb | 2024-10-20 15:46:25 | 2024-10-20 15:46:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int T,n;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>T;
while(T--){
cin>>n;
int x;
cout<<"? "<<1<<" "<<n<<endl;
cin>>x;
int l=1,r=n;
while(l<=r){
int len=r-l+1;
if(len==1){
cout<<"! "<<l<<endl;
break;
}else if(len==2){
if(x==l)cout<<"! "<<r<<endl;
else cout<<"! "<<l<<endl;
break;
}
int le=ceil(len*(sqrt(5)-1)/2);
if(x-l<=r-x){
int mid=l+le-1;
cout<<"? "<<l<<" "<<mid<<endl;
int u;
cin>>u;
if(u==x){
r=mid;
continue;
}else{
l=mid+1;
if(l==r)continue;
cout<<"? "<<l<<" "<<r<<endl;
cin>>x;
continue;
}
}else {
int mid=r-le+1;
cout<<"? "<<mid<<" "<<r<<endl;
int u;
cin>>u;
if(u==x){
l=mid;
continue;
}else{
r=mid-1;
if(l==r)continue;
cout<<"? "<<l<<" "<<r<<endl;
cin>>x;
continue;
}
}
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
input:
3 5 3 3 3 2 6 6 3 1 4 3 3 2
output:
? 1 5 ? 1 4 ? 2 4 ? 2 3 ! 4 ? 1 6 ? 3 6 ? 1 2 ! 2 ? 1 4 ? 2 4 ? 2 3 ! 4
result:
ok Correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 6ms
memory: 3672kb
input:
10000 10 2 2 2 2 3 10 10 10 10 7 10 5 5 5 4 10 4 4 4 4 4
output:
? 1 10 ? 1 7 ? 1 5 ? 1 4 ? 1 3 ! 4 ? 1 10 ? 4 10 ? 6 10 ? 7 10 ! 6 ? 1 10 ? 1 7 ? 3 7 ? 3 6 ! 7 ? 1 10 ? 1 7 ? 1 5 ? 2 5 ? 3 5 ? 3 4
result:
wrong answer Too many queries , n = 10 , now_q 6 (test case 4)