#include "mushrooms.h"
using namespace std;
vector<int> knownZeros;
vector<int> knownOnes;
vector<int> alternating;
void resolveAlternating(int lastVal) {
if (alternating.size() > 0) {
if (lastVal == -1) {
lastVal = use_machine({ 0, alternating[alternating.size()-1] });
}
else {
alternating.pop_back();
lastVal ^= 1;
}
while (alternating.size() > 0) {
if (lastVal) {
knownOnes.push_back(alternating[alternating.size() - 1]);
}
else {
knownZeros.push_back(alternating[alternating.size() - 1]);
}
lastVal ^= 1;
alternating.pop_back();
}
}
}
int count_mushrooms(int n) {
knownZeros.push_back(0);
// find one more, or two 1s
int i = 1;
while ((knownZeros.size() < 2) && (knownOnes.size() < 2)) {
int c = use_machine({ 0, i });
if (c) {
knownOnes.push_back(i);
}
else {
knownZeros.push_back(i);
}
++i;
if (i == n) {
return knownZeros.size();
}
}
vector<int> fives;
bool isZero = false;
if (knownZeros.size() == 2) {
fives.push_back(0);
fives.push_back(knownZeros[0]);
fives.push_back(0);
fives.push_back(knownZeros[1]);
fives.push_back(0);
isZero = true;
}
else {
fives.push_back(0);
fives.push_back(knownOnes[0]);
fives.push_back(0);
fives.push_back(knownOnes[1]);
fives.push_back(0);
}
while (((knownZeros.size() + (alternating.size() / 2)) < 100) &&
((knownOnes.size() + (alternating.size() / 2)) < 100)) {
if (i == n) {
resolveAlternating(-1);
return knownZeros.size();
}
if (i == (n - 1)) {
resolveAlternating(-1);
int c = use_machine({ 0, n - 1 });
return knownZeros.size() + 1 - c;
}
if (i == (n - 2)) {
resolveAlternating(-1);
int c1 = use_machine({ 0, n - 1 });
int c2 = use_machine({ 0, n - 2 });
return knownZeros.size() + 2 - (c1+c2);
}
fives[0] = i;
fives[2] = i + 1;
fives[4] = i + 2;
int c = use_machine(fives);
int inc = 0;
switch (c) {
case 0:
if (isZero) {
knownZeros.push_back(i);
knownZeros.push_back(i+1);
knownZeros.push_back(i+2);
resolveAlternating(0);
}
else {
knownOnes.push_back(i);
knownOnes.push_back(i + 1);
knownOnes.push_back(i + 2);
resolveAlternating(1);
}
i += 3;
break;
case 1:
if (isZero) {
knownZeros.push_back(i+1);
if (alternating.size() == 0) {
alternating.push_back(i);
}
alternating.push_back(i + 2);
}
else {
knownOnes.push_back(i + 1);
if (alternating.size() == 0) {
alternating.push_back(i);
}
alternating.push_back(i + 2);
}
i += 2;
break;
case 2:
if (isZero) {
if (alternating.size() == 0) {
alternating.push_back(i);
}
alternating.push_back(i + 1);
alternating.push_back(i + 2);
}
else {
if (alternating.size() == 0) {
alternating.push_back(i);
}
alternating.push_back(i + 1);
alternating.push_back(i + 2);
}
i += 2;
break;
case 3:
if (isZero) {
knownOnes.push_back(i+1);
if (alternating.size() == 0) {
alternating.push_back(i);
}
alternating.push_back(i + 2);
}
else {
knownZeros.push_back(i + 1);
if (alternating.size() == 0) {
alternating.push_back(i);
}
alternating.push_back(i + 2);
}
i += 2;
break;
case 4:
if (isZero) {
knownOnes.push_back(i);
knownOnes.push_back(i + 1);
knownOnes.push_back(i + 2);
resolveAlternating(1);
}
else {
knownZeros.push_back(i);
knownZeros.push_back(i + 1);
knownZeros.push_back(i + 2);
resolveAlternating(0);
}
i += 3;
break;
}
}
resolveAlternating(-1);
i = knownZeros.size() + knownOnes.size();
int totalZeros = knownZeros.size();
while (i < n) {
vector<int> m;
if (knownOnes.size() >= knownZeros.size()) {
for (int j = 0; j < knownOnes.size(); j++) {
if ((i + j) < n) {
m.push_back(knownOnes[j]);
m.push_back(i + j);
}
}
i += knownOnes.size();
int c = use_machine(m);
if (c & 1) {
++totalZeros;
--c;
knownZeros.push_back(m[m.size() - 1]);
}
else {
knownOnes.push_back(m[m.size() - 1]);
}
totalZeros += c / 2;
}
else {
for (int j = 0; j < knownZeros.size(); j++) {
if ((i + j) < n) {
m.push_back(knownZeros[j]);
m.push_back(i + j);
}
}
i += knownZeros.size();
int c = use_machine(m);
if (c & 1) {
++c;
knownOnes.push_back(m[m.size() - 1]);
}
else {
knownZeros.push_back(m[m.size() - 1]);
}
totalZeros += (m.size() - c) / 2;
}
}
return totalZeros;
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:91:7: warning: unused variable 'inc' [-Wunused-variable]
91 | int inc = 0;
| ^~~
mushrooms.cpp:187:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for (int j = 0; j < knownOnes.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
mushrooms.cpp:207:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for (int j = 0; j < knownZeros.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
256 KB |
Answer is not correct. |
| 5 |
Halted |
0 ms |
0 KB |
- |
