/* https://ioi2010.org/competitiontask/day1/hottercolder/index.html */
#include "grader.h"
#define K 30
int n, flip;
int guess(int x) {
return Guess(flip ? n + 1 - x : x);
}
int nn[K];
void init() {
int i;
nn[0] = 1, nn[1] = 3, nn[2] = 7;
for (i = 3; i < K; i++)
nn[i] = nn[i - 2] + (1 << i);
}
int search(int lower, int upper, int x) {
while (lower < upper) {
int g = guess(x = lower + upper - x);
if (g == 0)
return (lower + upper) / 2;
if ((lower + upper - x < x) == (g > 0))
lower = (lower + upper) / 2 + 1;
else
upper = (lower + upper + 1) / 2 - 1;
}
return lower;
}
int search_(int n, int k) {
int g, x;
if (n == 1)
return 1;
else if (n <= 3) {
g = guess(1);
return g == 0 ? 2 : (g > 0 ? 1 : n);
} else if (n <= 5) {
g = guess(n - 2);
if (g < 0)
return n;
if (g == 0)
return n - 1;
g = guess(1);
return g == 0 ? 2 : (g > 0 ? 1 : n - 2);
} else if (n <= 7) {
g = guess(1);
if (g > 0) {
g = guess(3);
return g == 0 ? 2 : (g > 0 ? 3 : 1);
} else if (g < 0) {
g = guess((n - 1) * 2 - 1);
return g == 0 ? n - 1 : (g > 0 ? n : n - 2);
} else
return 4;
}
if (n <= nn[k - 2])
return search_(n, k - 2);
g = guess(nn[k - 2] - 2);
if (g < 0) {
x = (nn[k - 2] - 2 + n) / 2 + 2;
g = guess(x * 2 - (nn[k - 2] - 2));
if (g == 0)
return x;
else if (g < 0)
return x - 1;
else
return search(x + 1, n, x * 2 - (nn[k - 2] - 2));
} else if (g > 0) {
g = guess(nn[k - 2]);
if (g < 0)
return search_(nn[k - 2], k - 2);
else if (g > 0)
return search(nn[k - 2], (nn[k - 2] - 2 + n + 1) / 2 - 1, nn[k - 2]);
else
return nn[k - 2] - 1;
} else
return (nn[k - 2] - 2 + n) / 2;
}
int HC(int N) {
int g, k;
n = N;
if (!nn[0])
init();
if (n == 1)
return 1;
else if (n == 2) {
Guess(1);
return Guess(2) < 0 ? 1 : 2;
} else if (n == 3) {
Guess(1), g = Guess(3);
return g == 0 ? 2 : (g < 0 ? 1 : 3);
} else {
Guess(n / 2), g = Guess(n / 2 + 1);
if (g < 0) {
k = 0;
while (nn[k] < n / 2 + 1)
k++;
flip = 0;
return search_(n / 2 + 1, k);
} else {
k = 0;
while (nn[k] < n - n / 2)
k++;
flip = 1;
return n + 1 - search_(n - n / 2, k);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
643 ms |
24392 KB |
Output is partially correct - alpha = 1.000000000000 |
