#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n = 0;
int solve(int lo, int hi, int pre) {
if (lo == hi) return lo;
//cout << lo << " " << hi << " " << pre << "\n";
if (lo == 1) {
if (hi == 1) return 1;
Guess(1);
if (hi == 2) {
int g = Guess(2);
if (g == -1)
return 1;
return 2;
}
if (hi == 3) {
int g = Guess(3);
if (g == 0) return 2;
else if (g == 1) return 3;
return 1;
}
if (hi == 4) {
int g = Guess(3);
if (g == 0) return 2;
else if (g == -1) return 1;
g = Guess(4);
if (g == 1) return 4;
return 3;
}
if (hi == 5) {
int g = Guess(3);
if (g == 0) return 2;
else if (g == -1) return 1;
g = Guess(5);
if (g == 1) return 5;
else if (g == 0) return 4;
return 3;
}
if (hi == 6) {
int g = Guess(3);
if (g == 0) return 2;
else if (g == -1) return 1;
g = Guess(5);
if (g == 0) return 4;
else if (g == -1) return 3;
g = Guess(6);
if (g == 1) return 6;
return 5;
}
if (hi == 7) {
int g = Guess(3);
if (g == 0) return 2;
else if (g == -1) return 1;
g = Guess(5);
if (g == 0) return 4;
else if (g == -1) return 3;
g = Guess(7);
if (g == 1) return 7;
else if (g == 0) return 6;
return 5;
}
if (hi == 8) {
int g = Guess(6);
if (g == -1) return solve(1, 3, 6);
g = Guess(8);
if (g == 0) return 7;
else if (g == 1) return 8;
g = Guess(2);
if (g == 1) return 4;
else if (g == 0) return 5;
return 6;
}
int idx = (lo+hi+1) / 2;
int g = Guess(idx);
if (g == 0) return (idx+lo)/2;
else if (g == -1) return solve(lo, (idx+lo-1)/2, idx);
return solve((idx+lo)/2+1,hi, idx);
}
if (pre == lo) {
int g = Guess(hi);
if (g == 0)
return (lo + hi) / 2;
if (g < 0)
return solve(lo, (lo + hi - 1) / 2, hi);
return solve((lo + hi) / 2 + 1, hi, hi);
} else if (pre == hi) {
int g = Guess(lo);
if (g == 0)
return (lo + hi) / 2;
if (g > 0)
return solve(lo, (lo + hi - 1) / 2, lo);
return solve((lo + hi) / 2 + 1, hi, lo);
}
//cout << "next query: " << 2 * mi - pre << " " << mi << "\n";
int idx = (lo + hi - pre);
if (idx == pre)
idx++;
idx = max(1, min(n, idx));
int g = Guess(idx);
if (g == 0)
return (idx + pre) / 2;
if (g > 0 && idx > pre)
return solve((idx + pre) / 2 + 1, hi, idx);
if (g > 0 && idx < pre)
return solve(lo, (idx + pre - 1) / 2, idx);
if (g < 0 && idx > pre)
return solve(lo, (idx + pre - 1) / 2, idx);
if (g < 0 && idx < pre)
return solve((idx + pre) / 2 + 1, hi, idx);
}
int HC(int N) {
n = N;
int ans = solve(1, n, 0);
//cout << "answer: " << ans << "\n";
return ans;
}
Compilation message
hottercolder.cpp: In function 'int solve(int, int, int)':
hottercolder.cpp:112:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
814 ms |
8296 KB |
Output is partially correct - alpha = 0.750000000000 |
