Submission #337110

# Submission time Handle Problem Language Result Execution time Memory
337110 2020-12-18T13:55:11 Z aanastasov Counting Mushrooms (IOI20_mushrooms) C++17
97.4138 / 100
10 ms 644 KB
#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 int minToTake() = 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 int minToTake() {
        return 0;
    }
    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 int minToTake() {
        return varsCount;
    }
    virtual int maxToTake(Knowledge &current) {
        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->minToTake() > indicesOfUnknown.size()) continue;
            if (!engine->canRun(currentKnowledge)) 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) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
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)
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:199:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |             if (engine->minToTake() > indicesOfUnknown.size()) continue;
      |                 ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# 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 7 ms 492 KB Output is correct
9 Correct 7 ms 540 KB Output is correct
10 Correct 8 ms 512 KB Output is correct
11 Correct 8 ms 512 KB Output is correct
12 Correct 9 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 8 ms 492 KB Output is partially correct
16 Partially correct 9 ms 492 KB Output is partially correct
17 Correct 5 ms 492 KB Output is correct
18 Correct 7 ms 512 KB Output is correct
19 Partially correct 8 ms 492 KB Output is partially correct
20 Correct 8 ms 492 KB Output is correct
21 Correct 8 ms 492 KB Output is correct
22 Partially correct 8 ms 492 KB Output is partially correct
23 Correct 8 ms 492 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Partially correct 8 ms 492 KB Output is partially correct
26 Partially correct 8 ms 492 KB Output is partially correct
27 Correct 8 ms 492 KB Output is correct
28 Partially correct 8 ms 492 KB Output is partially correct
29 Partially correct 10 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 8 ms 492 KB Output is partially correct
33 Partially correct 9 ms 492 KB Output is partially correct
34 Partially correct 8 ms 492 KB Output is partially correct
35 Partially correct 8 ms 492 KB Output is partially correct
36 Partially correct 8 ms 492 KB Output is partially correct
37 Correct 7 ms 628 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 10 ms 492 KB Output is partially correct
41 Partially correct 8 ms 492 KB Output is partially correct
42 Partially correct 8 ms 492 KB Output is partially correct
43 Partially correct 8 ms 492 KB Output is partially correct
44 Partially correct 8 ms 492 KB Output is partially correct
45 Partially correct 8 ms 492 KB Output is partially correct
46 Partially correct 9 ms 492 KB Output is partially correct
47 Partially correct 8 ms 492 KB Output is partially correct
48 Partially correct 8 ms 644 KB Output is partially correct
49 Partially correct 8 ms 492 KB Output is partially correct
50 Partially correct 8 ms 620 KB Output is partially correct
51 Partially correct 8 ms 492 KB Output is partially correct
52 Partially correct 8 ms 492 KB Output is partially correct
53 Partially correct 8 ms 492 KB Output is partially correct
54 Partially correct 8 ms 620 KB Output is partially correct
55 Partially correct 8 ms 492 KB Output is partially correct
56 Partially correct 8 ms 492 KB Output is partially correct
57 Partially correct 8 ms 492 KB Output is partially correct
58 Partially correct 8 ms 524 KB Output is partially correct
59 Partially correct 8 ms 492 KB Output is partially correct
60 Partially correct 8 ms 492 KB Output is partially correct
61 Partially correct 7 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 364 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 384 KB Output is correct
90 Correct 1 ms 364 KB Output is correct
91 Correct 1 ms 364 KB Output is correct