#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(s) ((int)s.size())
const int inf = 1e9;
int count_mushrooms(int n) {
if (n < 10) {
int s = 1;
for (int i = 0; i < n-1; i++) s += 1-use_machine(vector<int>({0, i+1}));
return s;
}
int bst = inf;
int num_it = -1;
for (int i = 0; i < n; i++) { // how many iterations to go through before starting main seq
int steps = i+2;
int found = 3+2*i;
int num_processed = 3+2*i;
while (found < n) {
steps++;
found += (1+num_processed)/2;
num_processed++;
}
if (steps < bst) {
bst = steps;
num_it = i;
}
}
vector<int> tp[2];
tp[0].push_back(0);
int cutoff = num_it + 2;
int l = 1;
for (; l < n && max(sz(tp[0]), sz(tp[1])) < cutoff; ) {
vector<int> m;
bool x = sz(tp[1])>sz(tp[0]);
m.push_back(tp[x][0]);
m.push_back(l++);
if (sz(tp[x]) > 1) {
m.push_back(tp[x][1]);
m.push_back(l++);
}
int v = use_machine(m);
if (sz(tp[x]) > 1) {
tp[x^(v&1)].push_back(l-2);
tp[x^((v/2)&1)].push_back(l-1);
}
else tp[x^(v&1)].push_back(l-1);
}
int s = 0;
while (l < n) {
bool x = sz(tp[1])>sz(tp[0]);
vector<int> m;
int num_processed = min(sz(tp[x]), n-l);
for (int i: tp[x]) {
m.push_back(i);
if (l < n) m.push_back(l++);
}
int v = use_machine(m);
int num_bs = (v+(v&1))/2;
s += x ? num_bs : (num_processed-num_bs);
if (l < n) {
tp[(v&1)^x^1].push_back(l-1);
s -= (v&1)^x;
}
}
return s + sz(tp[0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
344 KB |
Answer is not correct. |
| 6 |
Halted |
0 ms |
0 KB |
- |
