QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #881956 | #8939. Permutation | sugar | WA | 3ms | 3584kb | C++14 | 833b | 2025-02-04 20:01:03 | 2025-02-04 20:01:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
mt19937 myrand(time(0));
int n;
void solve()
{
cin>>n;
int l=1,r=n,la=0;
cout<<'?'<<' '<<1<<' '<<n<<endl;
cin>>la;
while(l!=r)
{
// printf("sure %d-%d\n",l,r);
if(r==l+1)
{
if(l==la)l++;
else r--;
break;
}
int mid=(l+r)>>1,mi=0;
if(mi<la)mi=l+(r-l)*3/8;
else mi=l+(r-l)*5/8;
if(mi==l)mi++;
int num=(mi<la);
if(num)cout<<'?'<<' '<<mi+1<<' '<<r<<endl;
else cout<<'?'<<' '<<l<<' '<<mi<<endl;
int pos=0;
cin>>pos;
if(la==pos)
{
if(num) l=mi+1;
else r=mi;
}
else
{
if(num)cout<<'?'<<' '<<l<<' '<<mi<<endl;
else cout<<'?'<<' '<<mi+1<<' '<<r<<endl;
cin>>la;
if(num)r=mi;
else l=mi+1;
}
}
cout<<'!'<<' '<<l<<endl;
}
int main()
{
int tt=0;
cin>>tt;
while(tt--)solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
3 5 3 3 3 6 6 3 1 4 3 3
output:
? 1 5 ? 3 5 ? 3 4 ! 4 ? 1 6 ? 3 6 ? 1 2 ! 2 ? 1 4 ? 3 4 ! 4
result:
ok Correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3456kb
input:
10000 10 2 2 1 3 10 10 10 7 5 10 5 5 6 10 9
output:
? 1 10 ? 1 4 ? 1 2 ? 3 4 ! 4 ? 1 10 ? 5 10 ? 7 10 ? 5 6 ! 6 ? 1 10 ? 5 10 ? 5 6 ? 7 10 ? 9 10 ? 7 8
result:
wrong answer Too many queries , n = 10 , now_q 6 (test case 3)