QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#594953 | #6394. Turn on the Light | Carameow | RE | 0ms | 0kb | C++20 | 1.5kb | 2024-09-28 11:31:32 | 2024-09-28 11:31:33 |
answer
#include<bits/stdc++.h>
using namespace std;
int n;
void init() {
cin >> n;
}
int ask(int x) {
cout << "? " << x << "\n";
cout << flush;
int a; cin >> a;
return a;
}
void fav(int ans) {
cout << "! " << ans << "\n";
exit(0);
}
void range(int f1, int l1, int f2, int l2, int diff, int out, bool type) {
if(f1 > l1 || f2 > l2 || f1 > l2) assert(0);
if(type) {
int mid = f1 + l2 >> 1;
int val = ask(mid);
if(abs(out) == val) fav(mid);
if(out > 0) {
if(val > out) range(f1, 0, 0, mid - 1, 0, val, 1);
else range(mid + 1, 0, 0, l2, 0, val, 1);
}
else if(out < 0) {
if(val > - out) range(mid + 1, 0, 0, l2, 0, val, 1);
else range(f1, 0, 0, mid - 1, 0, val, 1);
}
else range(f1, mid - 1, mid + 1, l2, val, out, 0);
}
else {
if(l1 - f1 + 1 >= l2 - f2 + 1) {
int mid = l1 + f1 >> 1;
int val = ask(mid);
if(diff == val) fav(mid);
if(diff > val) range(mid + 1, 0, 0, l1, 0, out + val, 1);
else if(diff < val) range(f1, mid - 1, f2, l2, val, out, 0);
}
else {
int mid = l2 + f2 >> 1;
int val = ask(mid);
if(diff == val) fav(mid);
if(diff > val) range(f2, 0, 0, mid - 1, 0, out - val, 1);
else if(diff < val) range(f1, l1, mid + 1, l2, val, out, 0);
}
}
}
int main () {
init();
range(1, 0, 0, n, 0, 0, 1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3