이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
constexpr int NMAX = 200000;
constexpr int NORMIE_MAX = 460;
int lessLeft[NMAX];
int lessRight[NMAX];
int totalHigher = -1;
pair<int, int> query(int i) {
if (lessLeft[i] == -1) {
vector<int> ans = ask(i);
lessLeft[i] = ans[0];
lessRight[i] = ans[1];
}
return {lessLeft[i], lessRight[i]};
}
int higherThan(int i) {
auto [lx, ly] = query(i);
return lx + ly;
}
void findAllValuables(int i, int j, int valBefore, int valAfter, vector<int> &ans) {
if (i > j) return;
else {
int k = (i + j) / 2;
int nonValBefore, nonValAfter;
for (nonValAfter = k; nonValAfter <= j && higherThan(nonValAfter) != totalHigher; ++nonValAfter) {
ans.push_back(nonValAfter);
}
for (nonValBefore = k; nonValBefore >= i && higherThan(nonValBefore) != totalHigher; --nonValBefore) {
ans.push_back(nonValBefore);
}
if (lessLeft[nonValBefore] != valBefore) {
findAllValuables(i, nonValBefore - 1, valBefore, lessRight[nonValBefore], ans);
}
if (lessRight[nonValAfter] != valAfter) {
findAllValuables(nonValAfter + 1, j, lessLeft[nonValAfter], valAfter, ans);
}
}
}
int find_best(int n) {
memset(lessLeft, -1, sizeof lessLeft);
memset(lessRight, -1, sizeof lessRight);
if (n <= NORMIE_MAX) {
for (int i = 0; i < n - 1; ++i) {
if (higherThan(i) == 0) return i;
}
}
for (int i = 0; i < NORMIE_MAX; ++i) {
totalHigher = max(totalHigher, higherThan(i));
}
int firstNonValuable = -1;
for (int i = 0; i < n; ++i) {
if (higherThan(i) == totalHigher) {
firstNonValuable = i;
break;
}
}
vector<int> vToCheck;
for (int i = 0; i < firstNonValuable; ++i) vToCheck.push_back(i);
findAllValuables(firstNonValuable + 1, n - 1, query(firstNonValuable).second, 0, vToCheck);
for (int i : vToCheck) {
if (higherThan(i) == 0) return i;
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
prize.cpp: In function 'int higherThan(int)':
prize.cpp:24:7: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [lx, ly] = query(i);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |