QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #666320 | #8939. Permutation | lytqwq# | WA | 2ms | 3712kb | C++14 | 832b | 2024-10-22 17:49:15 | 2024-10-22 17:49:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1000100;
int n,T;
map<pair<int,int> ,int> dk;
int ask(int l,int r){
if(dk.count(make_pair(l,r))){
return dk[make_pair(l,r)];
}
if(l==r)return -1;
cout<<"? "<<l<<" "<<r<<endl;
int x;
cin>>x;
dk[make_pair(l,r)]=x;
return x;
}
void calc(int l,int r){
if(l==r){
cout<<"! "<<l<<endl;
return ;
}
else if(l+1==r){
int v=ask(l,r);
cout<<"! "<<l+r-v<<endl;
return ;
}
int v=ask(l,r);
int mid=(l+r)>>1;
//l mid mid+1,r
if(v>=mid+1){
int kel=ask(mid+1,r);
if(kel==v){
calc(mid+1,r);
}
else{
calc(l,mid);
}
}
else{
int kel=ask(l,mid);
if(kel==v){
calc(l,mid);
}
else{
calc(mid+1,r);
}
}
}
int main(){
cin>>T;
while(T--){
dk.clear();
cin>>n;
calc(1,n);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
input:
3 5 3 2 5 6 6 5 3 1 4 3 3
output:
? 1 5 ? 1 3 ? 4 5 ! 4 ? 1 6 ? 4 6 ? 1 3 ? 1 2 ! 2 ? 1 4 ? 3 4 ! 4
result:
ok Correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3712kb
input:
10000 10 2 2 3 5 10 10 10 9 7 7 10 5 1 10 9 6
output:
? 1 10 ? 1 5 ? 1 3 ? 4 5 ! 4 ? 1 10 ? 6 10 ? 9 10 ? 6 8 ? 6 7 ! 6 ? 1 10 ? 1 5 ? 6 10 ? 9 10 ? 6 8 ? 6 7
result:
wrong answer Too many queries , n = 10 , now_q 6 (test case 3)