이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}
컴파일 시 표준 에러 (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... |