/*************************************
* author: marvinthang *
* created: 30.06.2023 10:50:39 *
*************************************/
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i--; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b) { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b) { if (a < b) { a = b; return true; } return false; }
// end of template
int count_mushrooms(int n) {
int nd = 8;
int mn = 203;
vector <vector <vector <int>>> ask{{{0}}};
vector <vector <int>> order {{0}};
vector <int> max_len {1}, min_last {3};
FOR(i, 1, nd) {
int last = max_len[i - 1];
int add = MASK(i - 1) - 1;
max_len.push_back(max_len.back() * 2 + add);
vector <vector <int>> nxt;
REP(j, add) {
vector <int> m = ask.back()[j];
vector <int> n = ask.back()[j];
int k = 0;
for (int x: ask.back()[j]) {
m.push_back(x + last);
while (k < x) n.push_back(last + k++);
k++;
}
while (k < last) n.push_back(last + k++);
m.push_back(2 * last + j);
nxt.push_back(m);
nxt.push_back(n);
}
vector <int> k;
REP(j, last) k.push_back(last + j);
nxt.push_back(k);
k.clear();
REP(j, last) k.push_back(j);
REP(j, add) k.push_back(2 * last + j);
nxt.push_back(k);
ask.push_back(nxt);
vector <int> ord(MASK(i));
iota(ALL(ord), 0);
sort(ALL(ord), [&] (int a, int b) { return nxt[a].size() < nxt[b].size(); });
order.push_back(ord);
int ml = 0;
REP(j, MASK(i)) maximize(ml, (int) nxt[ord[j]].size() * 2 + 1 - j);
min_last.push_back(ml);
}
vector <int> dp(mn + 1), trace(mn + 1);
dp[0] = 1;
dp[1] = 2;
dp[2] = 3;
int best = mn + 1, p = -1;
FORE(i, 2, mn) {
if (dp[i] > n) break;
int num_query = i;
int pos = dp[i];
int sz = dp[i];
while (pos < n) {
pos += (sz + 1) / 2;
sz++;
++num_query;
}
if (minimize(best, num_query)) p = i;
REP(j, nd) if (dp[i] >= min_last[j] && i + MASK(j) <= mn && maximize(dp[i + MASK(j)], dp[i] + max_len[j] + MASK(j)))
trace[i + MASK(j)] = j;
}
vector <int> t_add;
while (p > 2) {
t_add.push_back(trace[p]);
p -= MASK(trace[p]);
}
reverse(ALL(t_add));
vector <vector <int>> pos(2);
pos[0].push_back(0);
pos[use_machine(vector<int>{0, 1})].push_back(1);
if (n == 2) return pos[0].size();
pos[use_machine(vector<int>{0, 2})].push_back(2);
int i = 3;
function <vector<int>(int, vector<int>)> solve = [&] (int t, vector <int> cur) {
if (!t) return cur;
int n = cur.size();
vector <int> left, right, add;
int sum_left = cur[n - 1] - cur[n - 2];
int sum_right = cur[n - 2];
for (int i = 0; i + 2 < n; i += 2) {
left.push_back((cur[i] + cur[i + 1] - sum_right) / 2);
right.push_back((cur[i] - cur[i + 1] + sum_right) / 2);
add.push_back((cur[i] + cur[i + 1] + sum_right) & 1);
sum_left -= add.back();
}
left.push_back(sum_left);
right.push_back(sum_right);
left = solve(t - 1, left);
right = solve(t - 1, right);
left.insert(left.end(), ALL(right));
left.insert(left.end(), ALL(add));
return left;
};
for (int t: t_add) {
int sz = MASK(t);
int add = max_len[t];
vector <int> res(sz);
REP(_, sz) {
bool p = pos[0].size() < pos[1].size();
int k = order[t][_];
vector <int> v;
v.push_back(i + add + _);
v.push_back(pos[p][0]);
REP(j, ask[t][k].size()) {
v.push_back(i + ask[t][k][j]);
v.push_back(pos[p][j + 1]);
}
int cur = use_machine(v);
res[k] = p ? (int) ask[t][k].size() - cur / 2 : cur / 2;
pos[p ^ (cur & 1)].push_back(v[0]);
}
if (t) res[sz - 1] += res[sz - 2];
vector <int> v = solve(t, res);
REP(j, add) pos[v[j]].push_back(i + j);
i += add + sz;
}
int cnt_0 = pos[0].size();
for (; i < n; ) {
bool p = pos[0].size() < pos[1].size();
vector <int> v;
int j = 0;
for (; j < min(n - i, (int) pos[p].size()); ++j) {
v.push_back(i + j);
v.push_back(pos[p][j]);
}
int cur = use_machine(v);
cnt_0 += p ? (cur + 1) / 2 : j - (cur + 1) / 2;
pos[p ^ (cur & 1)].push_back(i);
i += j;
}
return cnt_0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Correct |
1 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
464 KB |
Output is correct |
| 4 |
Correct |
1 ms |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
464 KB |
Output is correct |
| 6 |
Correct |
1 ms |
464 KB |
Output is correct |
| 7 |
Correct |
6 ms |
464 KB |
Output is correct |
| 8 |
Correct |
6 ms |
464 KB |
Output is correct |
| 9 |
Correct |
6 ms |
464 KB |
Output is correct |
| 10 |
Correct |
5 ms |
464 KB |
Output is correct |
| 11 |
Correct |
5 ms |
464 KB |
Output is correct |
| 12 |
Correct |
7 ms |
480 KB |
Output is correct |
| 13 |
Correct |
5 ms |
464 KB |
Output is correct |
| 14 |
Correct |
3 ms |
464 KB |
Output is correct |
| 15 |
Correct |
5 ms |
464 KB |
Output is correct |
| 16 |
Correct |
6 ms |
464 KB |
Output is correct |
| 17 |
Correct |
3 ms |
464 KB |
Output is correct |
| 18 |
Correct |
5 ms |
464 KB |
Output is correct |
| 19 |
Correct |
6 ms |
464 KB |
Output is correct |
| 20 |
Correct |
5 ms |
464 KB |
Output is correct |
| 21 |
Correct |
6 ms |
464 KB |
Output is correct |
| 22 |
Correct |
6 ms |
464 KB |
Output is correct |
| 23 |
Correct |
7 ms |
464 KB |
Output is correct |
| 24 |
Correct |
3 ms |
464 KB |
Output is correct |
| 25 |
Correct |
5 ms |
464 KB |
Output is correct |
| 26 |
Correct |
6 ms |
464 KB |
Output is correct |
| 27 |
Correct |
5 ms |
464 KB |
Output is correct |
| 28 |
Correct |
7 ms |
464 KB |
Output is correct |
| 29 |
Correct |
6 ms |
464 KB |
Output is correct |
| 30 |
Correct |
6 ms |
464 KB |
Output is correct |
| 31 |
Correct |
7 ms |
464 KB |
Output is correct |
| 32 |
Correct |
6 ms |
464 KB |
Output is correct |
| 33 |
Correct |
5 ms |
464 KB |
Output is correct |
| 34 |
Correct |
5 ms |
464 KB |
Output is correct |
| 35 |
Correct |
6 ms |
464 KB |
Output is correct |
| 36 |
Correct |
5 ms |
464 KB |
Output is correct |
| 37 |
Correct |
5 ms |
464 KB |
Output is correct |
| 38 |
Correct |
6 ms |
464 KB |
Output is correct |
| 39 |
Correct |
6 ms |
464 KB |
Output is correct |
| 40 |
Correct |
6 ms |
464 KB |
Output is correct |
| 41 |
Correct |
6 ms |
464 KB |
Output is correct |
| 42 |
Correct |
6 ms |
464 KB |
Output is correct |
| 43 |
Correct |
7 ms |
464 KB |
Output is correct |
| 44 |
Correct |
6 ms |
464 KB |
Output is correct |
| 45 |
Correct |
5 ms |
464 KB |
Output is correct |
| 46 |
Correct |
5 ms |
464 KB |
Output is correct |
| 47 |
Correct |
6 ms |
464 KB |
Output is correct |
| 48 |
Correct |
6 ms |
464 KB |
Output is correct |
| 49 |
Correct |
5 ms |
464 KB |
Output is correct |
| 50 |
Correct |
5 ms |
464 KB |
Output is correct |
| 51 |
Correct |
5 ms |
464 KB |
Output is correct |
| 52 |
Correct |
5 ms |
464 KB |
Output is correct |
| 53 |
Correct |
7 ms |
464 KB |
Output is correct |
| 54 |
Correct |
5 ms |
464 KB |
Output is correct |
| 55 |
Correct |
5 ms |
464 KB |
Output is correct |
| 56 |
Correct |
5 ms |
464 KB |
Output is correct |
| 57 |
Correct |
5 ms |
464 KB |
Output is correct |
| 58 |
Correct |
6 ms |
420 KB |
Output is correct |
| 59 |
Correct |
7 ms |
464 KB |
Output is correct |
| 60 |
Correct |
7 ms |
464 KB |
Output is correct |
| 61 |
Correct |
5 ms |
464 KB |
Output is correct |
| 62 |
Correct |
1 ms |
464 KB |
Output is correct |
| 63 |
Correct |
1 ms |
464 KB |
Output is correct |
| 64 |
Correct |
1 ms |
464 KB |
Output is correct |
| 65 |
Correct |
1 ms |
464 KB |
Output is correct |
| 66 |
Correct |
1 ms |
464 KB |
Output is correct |
| 67 |
Correct |
1 ms |
464 KB |
Output is correct |
| 68 |
Correct |
1 ms |
464 KB |
Output is correct |
| 69 |
Correct |
1 ms |
464 KB |
Output is correct |
| 70 |
Correct |
1 ms |
464 KB |
Output is correct |
| 71 |
Correct |
1 ms |
464 KB |
Output is correct |
| 72 |
Correct |
1 ms |
464 KB |
Output is correct |
| 73 |
Correct |
0 ms |
464 KB |
Output is correct |
| 74 |
Correct |
1 ms |
464 KB |
Output is correct |
| 75 |
Correct |
1 ms |
464 KB |
Output is correct |
| 76 |
Correct |
1 ms |
464 KB |
Output is correct |
| 77 |
Correct |
1 ms |
464 KB |
Output is correct |
| 78 |
Correct |
1 ms |
464 KB |
Output is correct |
| 79 |
Correct |
1 ms |
464 KB |
Output is correct |
| 80 |
Correct |
1 ms |
464 KB |
Output is correct |
| 81 |
Correct |
1 ms |
464 KB |
Output is correct |
| 82 |
Correct |
1 ms |
464 KB |
Output is correct |
| 83 |
Correct |
1 ms |
464 KB |
Output is correct |
| 84 |
Correct |
0 ms |
464 KB |
Output is correct |
| 85 |
Correct |
1 ms |
464 KB |
Output is correct |
| 86 |
Correct |
1 ms |
444 KB |
Output is correct |
| 87 |
Correct |
1 ms |
464 KB |
Output is correct |
| 88 |
Correct |
1 ms |
464 KB |
Output is correct |
| 89 |
Correct |
1 ms |
464 KB |
Output is correct |
| 90 |
Correct |
1 ms |
464 KB |
Output is correct |
| 91 |
Correct |
1 ms |
464 KB |
Output is correct |
