이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
vector<vector<int>> cache;
vector<int> neoask(int i) {
if (cache[i].empty()) return cache[i] = ask(i);
return cache[i];
}
int minDeter = 0;
void solve(int s, int e, vector<bool> &mask) {
if (s > e) return;
auto vs = neoask(s);
if (vs[0] + vs[1] != minDeter) {
mask[s] = true;
solve(s + 1, e, mask);
return;
}
auto ve = neoask(e);
if (ve[0] + ve[1] != minDeter) {
mask[e] = true;
solve(s, e - 1, mask);
return;
}
if (e - s <= 1) return;
if (vs[0] == ve[0]) return;
int m = (s + e) >> 1;
auto vm = neoask(m);
if (vm[0] + vm[1] != minDeter) mask[m] = true;
solve(s, m, mask);
solve(m, e, mask);
}
int find_best(int n) {
if (n <= 5000) {
for (int i = 0; i < n; i++) {
auto v = ask(i);
if (v[0] + v[1] == 0) return i;
}
}
vector<bool> mask(n);
cache.resize(n);
// 473번 해보기
for (int i = 0; i < 473; i++) {
cache[i] = ask(i);
minDeter = max(minDeter, cache[i][0] + cache[i][1]);
}
solve(0, n - 1, mask);
for (int i = 0; i < n; i++) {
if (!mask[i]) continue;
auto v = neoask(i);
if (v[0] + v[1] == 0) return i;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |