| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 337109 | aanastasov | Counting Mushrooms (IOI20_mushrooms) | C++17 | 10 ms | 620 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||