QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #606966 | #8939. Permutation | liguo# | WA | 66ms | 3860kb | C++20 | 1.0kb | 2024-10-03 13:18:29 | 2024-10-03 13:18:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int ask(int l,int r){
printf("? %d %d\n",l,r);
fflush(stdout);
int res;scanf("%d",&res);
return res;
}
void solve(){
int n;scanf("%d",&n);
int l=1,r=n,sl;
int fl=1;
while(l<r){
if(fl==1){
sl=ask(l,r);fl=0;
}
if(l+1==r){
printf("! %d\n",r-sl+l);
fflush(stdout);
return;
}
else if(l+2==r){
int mid=(l+r)/2;
if(sl<=mid)
if(ask(l,mid)==sl)
printf("! %d\n",l+mid-sl);
else
printf("! %d\n",r);
else
if(ask(mid,r)==sl)
printf("! %d\n",mid+r-sl);
else
printf("! %d\n",l);
fflush(stdout);
return;
}
int mid=l+(r-l)/2;
int midl=l+(r-l)/3;
int midr=r-(r-l)/3;
if(l<=sl&&sl<=mid){
int res=ask(l,midr);
if(res==sl)
r=midr;
else
l=midr+1,fl=1;
}
else{
int res=ask(midl,r);
if(res==sl)
l=midl;
else
r=midl-1,fl=1;
}
}
printf("! %d\n",l);
fflush(stdout);
}
int main(){
int t;scanf("%d",&t);
while(t--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
3 5 3 3 3 2 6 6 6 3 4 3 3 2
output:
? 1 5 ? 1 4 ? 2 4 ? 2 3 ! 4 ? 1 6 ? 2 6 ? 3 6 ! 2 ? 1 4 ? 2 4 ? 2 3 ! 4
result:
ok Correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 66ms
memory: 3836kb
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)