#include "grader.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int step = 0;
const int MX = 130;
const int C = 53;
int dp[MX][MX][MX];
int fr[MX][MX][MX];
int f(int a,int b,int c) {
if (a >= b)
return 0;
if (dp[a][b][c] != 1e9)
return dp[a][b][c];
int &ans = dp[a][b][c];
for (int k = a;k <= b;++k)
if (k != c) {
int l = min(k,c);
int r = max(k,c);
int m1 = (l + r - 1) / 2;
int m2 = (l + r) / 2 + 1;
if (ans > max(f(a,m1,k),f(m2,b,k)) + 1)
ans = max(f(a,m1,k),f(m2,b,k)) + 1,fr[a][b][c] = k;
}
return ans;
}
int HC(int N) {
if (N == 1)
return 1;
++step;
if (step == 1) {
for (int i = 1;i < C;++i)
for (int j = 1;j < C;++j)
for (int k = 1;k < C;++k)
dp[i][j][k] = 1e9;
}
srand(N * step);
int l = 1,r = N,was = 0;
while (l < r) {
int m = (l + r) / 2;
if (m == was) {
if (m + 1 <= r)
++m;
else
--m;
}
if (!was) {
Guess(m + 1);
was = m + 1;
}
int cnt = Guess(m);
if (!cnt)
return ((m + was) / 2);
int m1 = (m + was - 1) / 2;
int m2 = (m + was) / 2 + 1;
if (m > was)
cnt *= -1;
if (cnt == 1)
r = m1;
else
l = m2;
was = m;
}
return l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2351 ms |
9760 KB |
Output is partially correct - alpha = 0.500000000000 |
