This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5 + 10;
typedef pair < int, int > PII;
int mars[NMAX];
int find_best (int n)
{
vector < PII > Seg;
vector < int > Q;
for(int i = 0; i < n; ++i)
Q.push_back(i);
random_shuffle(Q.begin(), Q.end());
int Max = 0;
for(int i = 0; i < 49 && i < n; ++i)
{
int pos = Q[i];
vector < int > _temp = ask(pos);
if(_temp[0] + _temp[1] > Max)
Max = _temp[0] + _temp[1];
if(_temp[0] == 0 && _temp[1] == 0)
return pos;
}
for(int i = 0; i < n; ++i)
{
int left = i, right = n - 1, pos = -1;
vector < int > now = ask(i);
if(now[0] == 0 && now[1] == 0)
return i;
if((now[0] + now[1]) == Max)
{
while(left <= right)
{
int mid = ((left + right) >> 1);
vector < int > _temp = ask(mid);
if(_temp[0] == now[0])
left = mid + 1, pos = mid;
else right = mid - 1;
}
Seg.push_back({i, pos});
i = pos;
}
}
for(auto it : Seg)
++mars[it.first], --mars[it.second + 1];
for(int i = 1; i < n; ++i)
mars[i] += mars[i - 1];
for(int i = 0; i < n; ++i)
if(mars[i] == 0)
{
vector < int > now = ask(i);
if(now[0] == 0 && now[1] == 0)
return i;
}
}
Compilation message (stderr)
prize.cpp: In function 'int find_best(int)':
prize.cpp:14:20: warning: control reaches end of non-void function [-Wreturn-type]
14 | vector < PII > Seg;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |