#include "mushrooms.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
template<typename T> void show(std::vector<T> v) {
std::cout << "{";
for (int i = 0; i < v.size(); ++i) {
if (i > 0) std::cout << ", ";
std::cout << v[i];
}
std::cout << "}";
}
class Knowledge {
public:
std::array<int, 2> count{0, 0};
std::array<std::vector<int>, 2> indicesOfKnown;
void merge(Knowledge &other) {
for (int color = 0; color < count.size(); ++color) {
count[color] += other.count[color];
for (auto index : other.indicesOfKnown[color])
indicesOfKnown[color].push_back(index);
}
}
};
class AbstractEngine {
public:
virtual bool canRun(Knowledge& current) = 0;
virtual bool enoughUnknowns(std::vector<int>& indicesOfUnknown) = 0;
virtual int maxToTake(Knowledge& current) = 0;
virtual Knowledge run(Knowledge& current, std::vector<int>& indicesOfUnknown) = 0;
};
class CountEngine : public AbstractEngine {
public:
CountEngine(int varsCount) {
this->varsCount = varsCount;
}
virtual bool canRun(Knowledge& current) {
return current.indicesOfKnown[0].size() >= varsCount
|| current.indicesOfKnown[1].size() >= varsCount;
}
virtual bool enoughUnknowns(std::vector<int>& indicesOfUnknown) {
return true;
}
virtual int maxToTake(Knowledge& current) {
return std::max(current.indicesOfKnown[0].size(), current.indicesOfKnown[1].size());
}
virtual Knowledge run(Knowledge& current, std::vector<int>& indicesOfUnknown) {
const int color = (current.indicesOfKnown[0].size() > current.indicesOfKnown[1].size())
? 0 : 1;
const int querySize = std::min(indicesOfUnknown.size(),
current.indicesOfKnown[color].size());
auto arr = std::vector<int>(querySize * 2);
for (int index = 0; index < querySize; ++index) {
arr[index * 2] = current.indicesOfKnown[color][index];
arr[index * 2 + 1] = indicesOfUnknown[index];
}
int count = use_machine(arr);
Knowledge response;
if (color == 1) {
response.count[0] += count / 2;
response.count[1] += (int)(querySize - 1) - response.count[0];
} else {
response.count[1] += count / 2;
response.count[0] += (int)(querySize - 1) - response.count[1];
}
int lastValue = (color != 0 ? 1 : 0) ^ (count % 2 != 0 ? 1 : 0);
response.indicesOfKnown[lastValue].push_back(indicesOfUnknown.back());
response.count[lastValue]++;
return response;
}
private:
int varsCount;
};
class FullEngine : public AbstractEngine {
public:
FullEngine(int varsCount, int queriesCount, std::vector<std::vector<int>> queries) {
this->varsCount = varsCount;
this->queriesCount = queriesCount;
this->queries = queries;
determineReverseMap();
}
virtual bool canRun(Knowledge& current) {
for (int color = 0; color < current.count.size(); ++color)
if (current.indicesOfKnown[color].size() >= varsCount) {
return true;
}
return false;
}
virtual bool enoughUnknowns(std::vector<int>& indicesOfUnknown) {
return varsCount <= indicesOfUnknown.size();
}
virtual int maxToTake(Knowledge ¤t) {
return varsCount;
}
virtual Knowledge run(Knowledge& current, std::vector<int>& indicesOfUnknown) {
assert(canRun(current));
assert(indicesOfUnknown.size() == varsCount);
auto queryAnswers = std::vector<int>();
const int color = (current.indicesOfKnown[0].size() >= varsCount) ? 0 : 1;
auto& indicesOfKnown = current.indicesOfKnown[color];
for (auto query : queries) {
auto arr = std::vector<int>(query.size() * 2);
for (int index = 0; index < query.size(); ++index) {
arr[index * 2] = indicesOfKnown[index];
arr[index * 2 + 1] = indicesOfUnknown[query[index]];
}
queryAnswers.push_back(use_machine(arr));
}
assert(reverseMap[color].count(queryAnswers));
auto varsValues = reverseMap[color][queryAnswers];
assert(varsValues.size() == varsCount);
Knowledge response;
for (int index = 0; index < varsValues.size(); ++index) {
response.indicesOfKnown[varsValues[index]].push_back(indicesOfUnknown[index]);
response.count[varsValues[index]]++;
}
return response;
}
private:
void determineReverseMap() {
auto countDiffPairs = [&](std::vector<int> arr) {
int res = 0;
for (int i = 0; i < arr.size(); ++i) {
assert(arr[i] == 0 || arr[i] == 1);
if (i > 0 && arr[i] != arr[i - 1]) ++res;
}
return res;
};
for (int color = 0; color < 2; ++color) {
for (int varsSet = 0; varsSet < (1 << varsCount); ++varsSet) {
std::vector<int> varsValues;
for (int index = 0; index < varsCount; ++index)
varsValues.push_back((varsSet >> index) & 1);
std::vector<int> queryAnswers(queriesCount);
for (int query = 0; query < queriesCount; ++query) {
std::vector<int> arr(queries[query].size() * 2);
for (int index = 0; index < queries[query].size(); ++index) {
arr[index * 2] = color;
arr[index * 2 + 1] = varsValues[queries[query][index]];
}
queryAnswers[query] = countDiffPairs(arr);
}
assert(reverseMap[color].count(queryAnswers) == 0);
reverseMap[color][queryAnswers] = varsValues;
}
}
}
int varsCount;
int queriesCount;
std::vector<std::vector<int>> queries;
std::array<std::map<std::vector<int>, std::vector<int>>, 2> reverseMap;
};
std::vector<int> take(std::vector<int>& arr, int count) {
if (count >= arr.size())
count = arr.size();
assert(count <= arr.size());
std::vector<int> res;
while (count > 0) {
res.push_back(arr.back());
arr.pop_back();
count--;
}
return res;
}
int count_mushrooms(int n) {
Knowledge currentKnowledge;
currentKnowledge.indicesOfKnown[0].push_back(0);
currentKnowledge.count[0] = 1;
FullEngine oneBitEfficiency(1, 1, {{0}});
FullEngine twoBitEfficiency(2, 1, {{0, 1}});
FullEngine twoAndAThirdBitEfficiency(7, 3, {{0, 1, 4}, {0, 2, 5}, {1, 2, 3, 6}});
CountEngine countEfficiency(96);
auto engines = std::vector<AbstractEngine *>{&countEfficiency, &twoAndAThirdBitEfficiency,
&twoBitEfficiency, &oneBitEfficiency};
auto indicesOfUnknown = std::vector<int>(n - 1);
for (int index = 0; index < indicesOfUnknown.size(); ++index)
indicesOfUnknown[index] = index + 1;
std::reverse(indicesOfUnknown.begin(), indicesOfUnknown.end());
while (!indicesOfUnknown.empty()) {
auto curIndicesOfUnknown = std::vector<int>();
Knowledge derivedKnowledge;
for (auto* engine : engines) {
if (!engine->canRun(currentKnowledge)) continue;
if (!engine->enoughUnknowns(indicesOfUnknown)) continue;
const int maxToTake = engine->maxToTake(currentKnowledge);
auto indicesOfUnknownToTake = take(indicesOfUnknown, maxToTake);
derivedKnowledge = engine->run(currentKnowledge, indicesOfUnknownToTake);
break;
}
currentKnowledge.merge(derivedKnowledge);
}
return currentKnowledge.count[0];
}
Compilation message
mushrooms.cpp: In member function 'void Knowledge::merge(Knowledge&)':
mushrooms.cpp:25:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int color = 0; color < count.size(); ++color) {
| ~~~~~~^~~~~~~~~~~~~~
mushrooms.cpp: In member function 'virtual bool CountEngine::canRun(Knowledge&)':
mushrooms.cpp:47:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
47 | return current.indicesOfKnown[0].size() >= varsCount
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
mushrooms.cpp:48:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | || current.indicesOfKnown[1].size() >= varsCount;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
mushrooms.cpp: In member function 'virtual bool FullEngine::canRun(Knowledge&)':
mushrooms.cpp:93:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int color = 0; color < current.count.size(); ++color)
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:94:54: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
94 | if (current.indicesOfKnown[color].size() >= varsCount) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
mushrooms.cpp: In member function 'virtual bool FullEngine::enoughUnknowns(std::vector<int>&)':
mushrooms.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | return varsCount <= indicesOfUnknown.size();
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
from mushrooms.cpp:5:
mushrooms.cpp: In member function 'virtual Knowledge FullEngine::run(Knowledge&, std::vector<int>&)':
mushrooms.cpp:107:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
107 | assert(indicesOfUnknown.size() == varsCount);
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
mushrooms.cpp:109:61: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
109 | const int color = (current.indicesOfKnown[0].size() >= varsCount) ? 0 : 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
mushrooms.cpp:113:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int index = 0; index < query.size(); ++index) {
| ~~~~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
from mushrooms.cpp:5:
mushrooms.cpp:121:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
121 | assert(varsValues.size() == varsCount);
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
mushrooms.cpp:123:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for (int index = 0; index < varsValues.size(); ++index) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~
mushrooms.cpp: In lambda function:
mushrooms.cpp:133:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int i = 0; i < arr.size(); ++i) {
| ~~^~~~~~~~~~~~
mushrooms.cpp: In member function 'void FullEngine::determineReverseMap()':
mushrooms.cpp:148:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (int index = 0; index < queries[query].size(); ++index) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp: In function 'std::vector<int> take(std::vector<int>&, int)':
mushrooms.cpp:167:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | if (count >= arr.size())
| ~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
from mushrooms.cpp:5:
mushrooms.cpp:169:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | assert(count <= arr.size());
| ~~~~~~^~~~~~~~~~~~~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:192:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for (int index = 0; index < indicesOfUnknown.size(); ++index)
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
7 ms |
492 KB |
Output is correct |
| 8 |
Correct |
8 ms |
492 KB |
Output is correct |
| 9 |
Correct |
7 ms |
492 KB |
Output is correct |
| 10 |
Correct |
8 ms |
492 KB |
Output is correct |
| 11 |
Correct |
8 ms |
492 KB |
Output is correct |
| 12 |
Correct |
8 ms |
492 KB |
Output is correct |
| 13 |
Correct |
8 ms |
492 KB |
Output is correct |
| 14 |
Correct |
6 ms |
492 KB |
Output is correct |
| 15 |
Partially correct |
10 ms |
492 KB |
Output is partially correct |
| 16 |
Partially correct |
10 ms |
492 KB |
Output is partially correct |
| 17 |
Correct |
5 ms |
512 KB |
Output is correct |
| 18 |
Correct |
7 ms |
536 KB |
Output is correct |
| 19 |
Partially correct |
10 ms |
492 KB |
Output is partially correct |
| 20 |
Correct |
9 ms |
492 KB |
Output is correct |
| 21 |
Correct |
10 ms |
492 KB |
Output is correct |
| 22 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 23 |
Correct |
10 ms |
492 KB |
Output is correct |
| 24 |
Correct |
6 ms |
492 KB |
Output is correct |
| 25 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 26 |
Partially correct |
10 ms |
620 KB |
Output is partially correct |
| 27 |
Correct |
8 ms |
492 KB |
Output is correct |
| 28 |
Partially correct |
8 ms |
548 KB |
Output is partially correct |
| 29 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 30 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 31 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 32 |
Partially correct |
10 ms |
492 KB |
Output is partially correct |
| 33 |
Partially correct |
10 ms |
492 KB |
Output is partially correct |
| 34 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 35 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 36 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 37 |
Correct |
8 ms |
492 KB |
Output is correct |
| 38 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 39 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 40 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 41 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 42 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 43 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 44 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 45 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 46 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 47 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 48 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 49 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 50 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 51 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 52 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 53 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 54 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 55 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 56 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 57 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 58 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 59 |
Partially correct |
9 ms |
492 KB |
Output is partially correct |
| 60 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 61 |
Partially correct |
8 ms |
492 KB |
Output is partially correct |
| 62 |
Correct |
1 ms |
364 KB |
Output is correct |
| 63 |
Correct |
1 ms |
364 KB |
Output is correct |
| 64 |
Correct |
1 ms |
364 KB |
Output is correct |
| 65 |
Correct |
1 ms |
364 KB |
Output is correct |
| 66 |
Correct |
1 ms |
364 KB |
Output is correct |
| 67 |
Correct |
1 ms |
364 KB |
Output is correct |
| 68 |
Correct |
1 ms |
364 KB |
Output is correct |
| 69 |
Correct |
1 ms |
364 KB |
Output is correct |
| 70 |
Correct |
1 ms |
364 KB |
Output is correct |
| 71 |
Correct |
1 ms |
364 KB |
Output is correct |
| 72 |
Correct |
1 ms |
364 KB |
Output is correct |
| 73 |
Correct |
1 ms |
364 KB |
Output is correct |
| 74 |
Correct |
1 ms |
364 KB |
Output is correct |
| 75 |
Correct |
1 ms |
364 KB |
Output is correct |
| 76 |
Correct |
1 ms |
364 KB |
Output is correct |
| 77 |
Correct |
1 ms |
364 KB |
Output is correct |
| 78 |
Correct |
1 ms |
364 KB |
Output is correct |
| 79 |
Correct |
1 ms |
364 KB |
Output is correct |
| 80 |
Correct |
1 ms |
384 KB |
Output is correct |
| 81 |
Correct |
1 ms |
364 KB |
Output is correct |
| 82 |
Correct |
1 ms |
364 KB |
Output is correct |
| 83 |
Correct |
1 ms |
364 KB |
Output is correct |
| 84 |
Correct |
1 ms |
364 KB |
Output is correct |
| 85 |
Correct |
1 ms |
364 KB |
Output is correct |
| 86 |
Correct |
1 ms |
364 KB |
Output is correct |
| 87 |
Correct |
1 ms |
364 KB |
Output is correct |
| 88 |
Correct |
1 ms |
364 KB |
Output is correct |
| 89 |
Correct |
1 ms |
364 KB |
Output is correct |
| 90 |
Correct |
1 ms |
364 KB |
Output is correct |
| 91 |
Correct |
1 ms |
364 KB |
Output is correct |
