QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557689 | #8939. Permutation | synonym | TL | 0ms | 0kb | C++17 | 1.4kb | 2024-09-11 10:57:54 | 2024-09-11 10:57:54 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define fnt long double
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
map<array<int,2>,int> answers;
int get_second(int l, int r) {
if (answers.count({l,r})) {
return answers[{l,r}];
}
cout<<"? "<<l<<" "<<r<<endl;
int res; cin>>res;
answers[{l,r}] = res;
return res;
}
int output_answer(int k) {
cout<<"! "<<k<<endl;
}
const fnt V = .618;
void solve() {
int n; cin>>n;
answers.clear();
int l=1,r=n;
int iter = 0;
while (l != r) {
assert(iter<100);
iter++;
int p = get_second(l,r);
if (l+2==r) {
if (p==l+1) {
int pp = get_second(l,l+1);
if (pp == p) {
output_answer(l);
return;
} else {
output_answer(r);
return;
}
}
if (p==l) {
l++;
} else {
r--;
}
continue;
}
if (l+1==r) {
output_answer(l+r-p);
return;
}
int lrp = l+V*(r-l+1);
int rrp = r-V*(r-l);
int p2 = -1;
if (p <= lrp) {
p2 = get_second(l,lrp);
if (p2 == p) {
r = lrp;
} else {
l = lrp+1;
}
} else {
assert(p >= rrp);
p2 = get_second(rrp,r);
if (p2 == p) {
l = rrp;
} else {
r = rrp-1;
}
}
}
output_answer(l);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
solve();//solve();solve();
// int t; cin>>t;
// while (t--) {
// solve();
// }
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 5 2 1
output:
? 1 3 ? 1 2 ! 1