#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;
const int debugmode = 0;
const int more1 = 0;
const int more2 = 0;
const int L = 25;
int dp[2 * L + 2][L + 1][L + 1][2 * L + 2] = {};
int to[2 * L + 2][L + 1][L + 1][2 * L + 2] = {};
int calc(int sz, int l, int r, int prev, int change = 0) {
if (l >= r) return 1;
sz = min(sz, 2 * r);
prev = min(prev, 2 * r);
if (dp[sz][l][r][prev] != 0) return dp[sz][l][r][prev];
int &D = dp[sz][l][r][prev], &t = to[sz][l][r][prev];
int mn = md, tmp1, tmp2;
for (int i = 1; i <= 2 * r && i <= sz; i++)
if (i != prev) {
int mid1 = (prev + i - 1) / 2, mid2 = (prev + i) / 2 + 1;
if ((l <= mid1 && mid1 < r) || (l < mid2 && mid2 <= r)) {
tmp1 = calc(sz, l, mid1, i, 0);
tmp2 = calc(sz, mid2, r, i, 0);
if (mn >= max(tmp1, tmp2)) {
mn = max(tmp1, tmp2);
if (!change) t = i;
}
}
else if (change == 0) {
tmp1 = calc(sz, l, r, i, 1);
if (mn >= tmp1) {
mn = tmp1;
if (!change) t = i;
}
}
}
// printf("(%d, %d, %d, %d, %d) = %d\n", sz, l, r, prev, change, 1 + mn);
if (!change) D = 1 + mn;
return 1 + mn;
}
int goes(int sz, int l, int r, int prev) {
sz = min(sz, 2 * r);
prev = min(prev, 2 * r);
calc(sz, l, r, prev);
return to[sz][l][r][prev];
}
bool can(int l, int r) {
return r < L + 1;
}
void cut(int &l, int &r, int &prev, int &pos, int k) {
if ((k == -1) == (pos < prev)) {
l = max(l, (pos + prev) / 2 + 1);
}
else {
r = min(r, (pos + prev - 1) / 2);
}
}
//#include "grader.h"
int n;
bool rev;
int myans, myprev = -1, mycnt;
/*
int Guess(int G) {
mycnt++;
if (debugmode) {
cout << "? " << G << '\n';
int rtn;
cin >> rtn;
return rtn;
}
else {
int rtn;
if (myprev == -1) rtn = 0;
else {
if (abs(myans - G) == abs(myans - myprev)) rtn = 0;
else if (abs(myans - G) < abs(myans - myprev)) rtn = 1;
else rtn = -1;
}
myprev = G;
return rtn;
}
}
*/
int Guess(int G);
int ask(int x) {
if (rev) x = n + 1 - x;
return Guess(x);
}
int solve(int sz, int l, int r, int prev) {
sz = min(sz, 2 * r);
prev = min(prev, 2 * r);
while (l < r) {
if (more1) cout << "solve " << sz << " " << l << " " << r << " " << prev << '\n';
int pos = goes(sz, l, r, prev);
int k = ask(pos);
if (k == 0) {
if ((pos + prev) % 2 == 0 && l <= (pos + prev) / 2 && (pos + prev) / 2 <= r)
return (pos + prev) / 2;
else {
prev = pos;
continue;
}
}
cut(l, r, prev, pos, k);
prev = pos;
}
return l;
}
int HCr(int l, int r, int prev) {
int pos;
while (l < r) {
if (more1) cout << "HCr" << l << " " << r << '\n';
pos = l + r - prev;
while (pos < 1) pos++;
int k = ask(pos);
if (k == 0) return (pos + prev) / 2;
cut(l, r, prev, pos, k);
prev = pos;
}
return l;
}
int HC(int l, int r, int prev) {
if (more1) cout << "HC " << l << " " << r << '\n';
if (can(l, r)) return solve(n, 1, r, prev);
int pos = prev / 2;
int k = ask(pos);
if (k == 0) return (pos + prev) / 2;
cut(l, r, prev, pos, k);
if (l == 1) return HC(l, r, pos);
return HCr(l, r, pos);
}
int HC(int N) {
n = N;
rev = false;
if (can(1, N)) return solve(N, 1, N, md);
int p1 = n / 2, p2 = (n + 3) / 2;
ask(p1);
int k = ask(p2);
int l = 1, r = n;
if (k == 0) return (p1 + p2) / 2;
cut(l, r, p1, p2, k);
if (l > 1) {
rev = true;
swap(l, r);
l = n + 1 - l;
r = n + 1 - r;
p2 = n + 1 - p2;
}
if (more1) cout << "before " << l << " " << r << " " << rev << '\n';
if (more2 && can(l, r)) {
int rtn = solve(n, l, r, p2);
if (rev) rtn = n + 1 - rtn;
return rtn;
}
p1 = (r + 1) / 2;
k = ask(p1);
if (k == 0) {
if (!rev) return (p2 + p1) / 2;
return n + 1 - (p2 + p1) / 2;
}
cut(l, r, p2, p1, k);
int rtn = -1;
if (l == 1) rtn = HC(l, r, p1);
else rtn = HCr(l, r, p1);
if (rev) rtn = n + 1 - rtn;
return rtn;
}
/*
int main() {
ios::sync_with_stdio(0), cin.tie(0);
if (debugmode) {
while (1) {
cout << "x: ";
int x;
cin >> x;
int ans = HC(x);
cout << "ans: " << ans << '\n';
}
}
else {
for (int x = 1; x <= 500; x++) {
for (int i = 1; i <= x; i++) {
mycnt = 0;
myans = i;
myprev = -1;
int ans = HC(x);
if (ans != myans) {
cout << "WA on " << x << " " << i << '\n';
cout << "myans = " << myans << " provided = " << ans << '\n';
return 0;
}
if ((1LL << mycnt) > 3 * x) {
cout << "not good enough on " << x << " " << i << '\n';
cout << "did " << mycnt << '\n';
return 0;
}
}
}
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
6136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
6136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
6168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
872 ms |
13232 KB |
Output is partially correct - alpha = 0.714285714286 |
