#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define bk back()
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const ld PI = acos((ld)-1);
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
vi soFar, guess;
pi posi;
int N;
bool tri(int x) {
guess.pb(Guess(x));
if (guess.bk == 0) {
if (sz(soFar) && soFar.bk != x)
posi.f = posi.s = (soFar.bk+x)/2;
} else {
if (guess.bk == -1) {
if (x < soFar.bk) {
ckmax(posi.f,(soFar.bk+x)/2+1);
} else {
ckmin(posi.s,(soFar.bk+x-1)/2);
}
} else {
if (x < soFar.bk) {
ckmin(posi.s,(soFar.bk+x-1)/2);
} else {
ckmax(posi.f,(soFar.bk+x)/2+1);
}
}
}
soFar.pb(x); assert(posi.f <= posi.s);
return posi.f == posi.s;
}
int binSearch() {
while (1) {
int des = posi.f+posi.s-soFar.bk;
ckmax(des,1); ckmin(des,N);
if (tri(des)) return posi.f;
}
}
int HC(int _N) {
N = _N;
guess.clear(), soFar.clear(); posi = {1,N};
if (N == 1) return 1;
if (N == 2) {
tri(1); assert(tri(2));
return posi.f;
}
int m = (1+N)/2;
tri(m-1); if (tri(m+1)) return posi.f;
if (posi.s == m-1) {
while (posi.f == 1) {
int p = max(posi.f/4,1);
if (tri(p+2)) return posi.f;
if (posi.f != 1) return binSearch();
if (tri(p)) return posi.f;
if (posi.f != 1) return binSearch();
assert(posi.s == p);
}
} else {
assert(posi.f == m+1);
while (posi.s == N) {
int p = min(N+1-(N+1-posi.s)/4,N);
if (tri(p-2)) return posi.f;
if (posi.s != N) return binSearch();
if (tri(p)) return posi.f;
if (posi.s != N) return binSearch();
assert(posi.f == p);
}
}
}
Compilation message
hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:99:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
1376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
1400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
921 ms |
13184 KB |
Output is partially correct - alpha = 0.148148148148 |
