이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll linf = ll(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
map<int, vi> cache;
vi q(int i)
{
if (cache.find(i) != cache.end()) return cache[i];
return cache[i] = ask(i);
}
int find_best(int n)
{
int lollipop_cnt = 0;
int i = 0;
rep(i, 500)
{
vi res = q(i);
ll s = res[0] + res[1];
if (s==0)
{
return i;
}
// assume that i is second most common
// then there are s^2 of type t[i], and s^4 of most common type
assert(s <= 500);
if (s*s*s*s>n)
{
lollipop_cnt = s;
break;
}
lollipop_cnt = max(lollipop_cnt, (int)s);
i++;
}
int jump = 220;
while (true)
{
vi base = q(i);
if (base[0]+base[1]==0)
{
return i;
}
if (base[0]+base[1]==lollipop_cnt)
{
if (i+ jump <n)
{
vi b2 = q(i + jump);
if (b2 == base)
{
i += jump;
continue;
}
}
int lo = i;
int hi = min(n, i+ jump);
while (lo+1<hi)
{
int mid = (lo + hi) / 2;
vi m = q(mid);
if (m == base)
{
lo = mid;
}
else hi = mid;
}
i = hi;
}
else
{
i++;
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |