#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include "prize.h"
std::mt19937 rng(123);
std::vector<std::pair<int, int>> memo;
int queries = 0;
int answer = -1;
std::pair<int, int> query(int i) {
if (memo[i].first != -1) {
return memo[i];
}
queries++;
assert(queries <= 10000);
auto aux = ask(i);
if (aux[0] == 0 && aux[1] == 0) {
answer = i;
}
return memo[i] = std::pair<int, int>{aux[0], aux[1]};
}
int total_less(int i) {
return query(i).first + query(i).second;
}
int countnonmax;
bool is_max(int i) {
if (total_less(i) == 0) {
answer = i;
}
return total_less(i) == countnonmax;
}
int find_best(int n) {
memo.resize(n, std::pair<int, int>{-1, -1});
// if (n <= 7) {
// for (int i = 0; i < n; i++) {
// if (total_less(i) == 0) {
// return i;
// }
// }
// }
auto get = [&](auto &self, int l, int r, int countLeft) { // countLeft = cate sunt bune in [0, l)
if (l == r) {
return l;
}
int mid = (l + r) / 2;
int p = mid;
while (p >= l && !is_max(p)) {
p--;
}
if (p <= l) {
return l;
}
int st = query(p).first;
// std::cout << " ! " << l << ' ' << r << ' ' << p << ' ' << st << '\n';
if (st == countLeft) {
if (p != mid) { // stiu sigur ca p + 1 e bun
return p + 1;
} else { // siu ca in [l..mid] nu e niciunul bun
return self(self, mid + 1, r, st);
}
} else {
return self(self, l, p, countLeft);
}
};
int p1 = rng() % n;
int p2 = rng() % n;
int p3 = rng() % n;
countnonmax = std::max({total_less(p1), total_less(p2), total_less(p3)});
std::vector<int> cand;
int l = 0, r = n - 1;
while (!is_max(l)) {
cand.push_back(l++);
}
while (!is_max(r)) {
cand.push_back(r--);
}
// stiu ca l si r sunt max
while (query(r).first > query(l).first) {
int p = get(get, l + 1, r - 1, query(l).first);
// std::cout << " ? " << l << ' ' << r << ' ' << p << '\n';
while (!is_max(p)) {
cand.push_back(p++);
}
l = p;
}
std::sort(cand.begin(), cand.end());
cand.erase(std::unique(cand.begin(), cand.end()), cand.end());
for (int &x : cand) {
if (total_less(x) == 0) {
return x;
}
}
}
Compilation message (stderr)
prize.cpp: In function 'int find_best(int)':
prize.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
110 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |