| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 282371 | 2020-08-24T11:11:20 Z | Kastanda | Hotter Colder (IOI10_hottercolder) | C++11 | 0 ms | 0 KB |
// M
#include<bits/stdc++.h>
using namespace std;
int n;
int SolveType2(int l, int r)
{
assert(l - 1 >= r - l + 1);
assert(n - r >= r - l + 1);
int last = l;
Guess(l);
while (l < r)
{
int tobe = -1;
if (last <= l)
tobe = r + (l - last);
else if (last >= r)
tobe = l - (last - r);
else
assert(0);
assert(tobe >= 1 && tobe <= n);
int w = Guess(tobe);
if (w == 0)
return (last + tobe) / 2;
if (l + 1 == r)
{
if ((w == 1 && tobe > last) || (w == -1 && tobe < last))
return r;
return l;
}
if ((w == 1 && tobe > last) || (w == -1 && tobe < last))
l = (l + r) / 2 + 1;
else
r = (l + r - 1) / 2;
last = tobe;
}
assert(l == r);
return l;
}
int Brute(int l, int r)
{
int last = l;
while (l < r)
{
if (last != l && last != r)
last = r, Guess(last);
if (last == l)
{
int w = Guess(r);
last = r;
if (w == 0)
return (l + r) / 2;
else if (w == 1)
l = (l + r) / 2 + 1;
else
r = (l + r - 1) / 2;
continue;
}
assert(last == r);
if (last == r)
{
int w = Guess(l);
last = l;
if (w == 0)
return (l + r) / 2;
else if (w == 1)
r = (l + r - 1) / 2;
else
l = (l + r) / 2 + 1;
continue;
}
}
return l;
}
int SolveType1(int l, int r, int asked = 0)
{
if (r - l == 0)
return l;
if (!asked)
Guess(l);
if (r - l == 1)
{
int w = Guess(r);
if (w == 1)
return r;
return l;
}
if (r - l == 2)
{
int w = Guess(r);
if (w == 1)
return r;
if (w == 0)
return r - 1;
return l;
}
if (r - l <= 10)
return Brute(l, r);
int md = (r - l + 1) / 3 * 2 + l - 1;
int w = Guess(md);
if (w == 0)
return (l + md) / 2;
if (w == -1)
return SolveType1(l, (l + md - 1) / 2);
assert(md + 2 <= r);
w = Guess(md + 2);
if (w == 0)
return md + 1;
if (w == 1)
return SolveType1(md + 2, r, 1);
return SolveType2((l + md) / 2 + 1, md);
}
int HC(int _n)
{
n = _n;
return SolveType1(1, n);
}