#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;
template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
os << "{";
int g = size(o);
for (auto i : o) os << i << ((--g) == 0 ? "" : ", ");
os << "}";
return os;
}
void _print() {
cerr << "\n";
}
template<typename T, typename ...V>
void _print(T t, V... v) {
cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}
#ifdef LOCAL
#define cerr(x...) cerr << #x << " = "; _print(x);
#else
#define cerr(x...)
#define cerr if (0) std::cerr
#endif
/*
there are at most O(sqrt n) different types of prizes
constraints suggest 2 * sqrt(n) * log2(n)
we can differentiate levels of boxes based on sum of query results
there are at most sqrt non-complete-trash prizes
if we can isolate each "level" of prizes, we can work our way up to the top
consider only the worst type of prize
there are at most sqrt(n) connected components of prizes better than this
we can bsearch for these components
to find a l point, move it right while the # of better prizes to its left doesnt change
to find a r point, move it right while the # of better prizes to its right doesnt change
take these points, and squish the new array such that we only consider these indices now
do this recursively unitl we end up with an array of length 1
*/
map<int, pi> memo;
pi _query(int i) {
if (memo.count(i)) return memo[i];
vt<int> res = ask(i);
return memo[i] = {res[0], res[1]};
}
struct Array {
vt<int> actual;
void pb(int v) {
actual.pb(v);
}
pi query(int i) {
if (i < 0) return {0, 0};
return _query(actual[i]);
}
int operator[](int i) {
return actual[i];
}
int sz() {
return size(actual);
}
};
/*
to find a l point, move it right while the # of better prizes to its left doesnt change (so query res is equal or less than original)
take these points, and squish the new array such that we only consider these indices now
*/
void solve(Array& a, int tot) {
vt<pi> rngs; // inc, exc
int n = a.sz();
int l = -1, r;
while (l < n) {
int lo = -1, hi = n;
int bruh = a.query(l).f;
if (bruh > tot) {
solve(a, bruh);
return;
}
while (hi - lo > 1) {
int m = (lo + hi) / 2;
auto [x, y] = a.query(m);
if (x + y > tot) {
solve(a, x + y);
return;
}
if (m <= l || (x + y == tot && x <= bruh)) lo = m;
else hi = m;
}
l = lo + 1;
if (l == n) break; // reached end of arr
int r = l + 1; // exc
while (r < n) {
auto [lhs, rhs] = a.query(r);
if (lhs + rhs > tot) {
solve(a, lhs + rhs);
return;
}
if (lhs + rhs == tot) break;
else r++;
}
rngs.pb({l, r});
l = r;
}
Array narr;
for (auto [l, r] : rngs) {
FOR (i, l, r) {
narr.pb(a[i]);
}
}
a = narr;
}
int find_best(int _n) {
Array arr;
int n = _n;
F0R (i, n) {
arr.pb(i);
}
while (arr.sz() > 1) {
solve(arr, arr.query(0).f + arr.query(0).s);
}
auto [l, r] = _query(arr[0]);
assert(l + r == 0);
return arr[0];
}
Compilation message
prize.cpp:44: warning: "cerr" redefined
44 | #define cerr if (0) std::cerr
|
prize.cpp:43: note: this is the location of the previous definition
43 | #define cerr(x...)
|
prize.cpp: In function 'void solve(Array&, int)':
prize.cpp:101:14: warning: unused variable 'r' [-Wunused-variable]
101 | int l = -1, r;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1568 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1500 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1488 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1488 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1488 KB |
Output is correct |
| 14 |
Correct |
8 ms |
600 KB |
Output is correct |
| 15 |
Correct |
26 ms |
1608 KB |
Output is correct |
| 16 |
Correct |
25 ms |
1488 KB |
Output is correct |
| 17 |
Correct |
23 ms |
1488 KB |
Output is correct |
| 18 |
Correct |
35 ms |
1740 KB |
Output is correct |
| 19 |
Correct |
24 ms |
1988 KB |
Output is correct |
| 20 |
Correct |
16 ms |
980 KB |
Output is correct |
| 21 |
Correct |
26 ms |
1668 KB |
Output is correct |
| 22 |
Correct |
16 ms |
1488 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 25 |
Correct |
16 ms |
1488 KB |
Output is correct |
| 26 |
Correct |
24 ms |
1488 KB |
Output is correct |
| 27 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 28 |
Correct |
18 ms |
1488 KB |
Output is correct |
| 29 |
Correct |
23 ms |
1488 KB |
Output is correct |
| 30 |
Correct |
33 ms |
1768 KB |
Output is correct |
| 31 |
Correct |
36 ms |
1488 KB |
Output is correct |
| 32 |
Correct |
3 ms |
1740 KB |
Output is correct |
| 33 |
Correct |
1 ms |
344 KB |
Output is correct |
| 34 |
Correct |
25 ms |
1748 KB |
Output is correct |
| 35 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 36 |
Correct |
27 ms |
1488 KB |
Output is correct |
| 37 |
Correct |
4 ms |
1488 KB |
Output is correct |
| 38 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 39 |
Correct |
29 ms |
1488 KB |
Output is correct |
| 40 |
Correct |
20 ms |
1488 KB |
Output is correct |
| 41 |
Correct |
35 ms |
1488 KB |
Output is correct |
| 42 |
Correct |
26 ms |
1488 KB |
Output is correct |
| 43 |
Correct |
23 ms |
1488 KB |
Output is correct |
| 44 |
Correct |
24 ms |
1488 KB |
Output is correct |
| 45 |
Correct |
21 ms |
1752 KB |
Output is correct |
| 46 |
Correct |
25 ms |
1740 KB |
Output is correct |
| 47 |
Correct |
32 ms |
1484 KB |
Output is correct |
| 48 |
Correct |
34 ms |
1488 KB |
Output is correct |
| 49 |
Correct |
25 ms |
1488 KB |
Output is correct |
| 50 |
Correct |
24 ms |
1488 KB |
Output is correct |
| 51 |
Correct |
23 ms |
1488 KB |
Output is correct |
| 52 |
Correct |
27 ms |
1488 KB |
Output is correct |
| 53 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 54 |
Correct |
21 ms |
1488 KB |
Output is correct |
| 55 |
Correct |
24 ms |
1624 KB |
Output is correct |
| 56 |
Correct |
24 ms |
1488 KB |
Output is correct |
| 57 |
Correct |
28 ms |
1488 KB |
Output is correct |
| 58 |
Correct |
42 ms |
1488 KB |
Output is correct |
| 59 |
Correct |
26 ms |
1488 KB |
Output is correct |
| 60 |
Correct |
20 ms |
1604 KB |
Output is correct |
| 61 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 62 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 63 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 64 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 65 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 66 |
Correct |
5 ms |
1568 KB |
Output is correct |
| 67 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 68 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 69 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 70 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 71 |
Correct |
34 ms |
1748 KB |
Output is correct |
| 72 |
Correct |
3 ms |
1740 KB |
Output is correct |
| 73 |
Correct |
23 ms |
1488 KB |
Output is correct |
| 74 |
Correct |
39 ms |
1488 KB |
Output is correct |
| 75 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 76 |
Correct |
19 ms |
1488 KB |
Output is correct |
| 77 |
Partially correct |
25 ms |
1532 KB |
Partially correct - number of queries: 5004 |
| 78 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 79 |
Correct |
9 ms |
1488 KB |
Output is correct |
| 80 |
Correct |
35 ms |
1964 KB |
Output is correct |
| 81 |
Partially correct |
25 ms |
1584 KB |
Partially correct - number of queries: 5028 |
| 82 |
Correct |
35 ms |
1724 KB |
Output is correct |
| 83 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 84 |
Correct |
19 ms |
1488 KB |
Output is correct |
| 85 |
Correct |
40 ms |
1488 KB |
Output is correct |
| 86 |
Correct |
4 ms |
1488 KB |
Output is correct |
| 87 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 88 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 89 |
Correct |
4 ms |
1488 KB |
Output is correct |
| 90 |
Correct |
2 ms |
1488 KB |
Output is correct |
| 91 |
Correct |
4 ms |
1488 KB |
Output is correct |
| 92 |
Correct |
5 ms |
1488 KB |
Output is correct |
| 93 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 94 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 95 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 96 |
Correct |
3 ms |
1488 KB |
Output is correct |
| 97 |
Correct |
2 ms |
1488 KB |
Output is correct |
