#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define ub upper_bound
/// #define int ll
const int oo = 1e9 + 7;
int Guess(int v);
map<int, int> m; bool first = 1;
void init() {
for(int l = 1; l < 30; l++) {
int i = ((1 << l + 1) + (l & 1 ? -1 : 1)) / 3;
int j = ((1 << l) + (l & 1 ? -1 : 1) * 2) / 3 + 1;
m[i] = j;
}
}
int solve(int lo, int hi, int pr, int N, bool state) {
if(state) return (lo + hi) / 2;
if(pr == 1 || pr == N) {
int calc;
if(pr == 1) calc = lo * 2 - 2 + m.ub(hi - lo)->ss;
if(pr == N) calc = hi * 2 - N + 1 - m.ub(hi - lo)->ss;
calc = max(calc, 1);
calc = min(calc, N);
return calc;
}
int res = lo + hi - pr;
res = max(res, 1); res = min(res, N);
if(lo <= res && res <= hi && (hi - lo + 1) & 2) {
if(res < pr && (res ^ lo) & 1 || res > pr && (res ^ hi) & 1) {
if(N - hi > lo - 1) res--;
else res++;
}
}
if(res == pr) {
if(N - hi > lo - 1) res--;
else res++;
}
return res;
}
int HC(int N) {
if(first) first = 0, init();
int lo = 1, hi = N, pr = (lo + hi) / 2 + 1;
pr = max(1, pr); pr = min(N, pr);
Guess(pr); bool state = 1;
while(lo < hi) {
int to = solve(lo, hi, pr, N, state);
if(state) state = 0;
if(to == pr && to - 1 >= lo) to--;
if(to == pr && to + 1 <= hi) to++;
if(to == pr) return to;
int r = Guess(to), md = abs(to - pr);
if(md & 1) md++;
if(r == 0) return (to + pr) / 2;
else if((r == 1 && to > pr) || (r == -1 && to < pr))
lo = max(lo, (to + pr) / 2 + 1);
else hi = min(hi, (to + pr + 1) / 2 - 1);
pr = to;
}
return lo;
}
Compilation message
hottercolder.cpp: In function 'void init()':
hottercolder.cpp:25:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
25 | int i = ((1 << l + 1) + (l & 1 ? -1 : 1)) / 3;
| ~~^~~
hottercolder.cpp: In function 'int solve(int, int, int, int, bool)':
hottercolder.cpp:44:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
44 | if(res < pr && (res ^ lo) & 1 || res > pr && (res ^ hi) & 1) {
| ~~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
643 ms |
8680 KB |
Output is partially correct - alpha = 1.000000000000 |
