Submission #1087507

#TimeUsernameProblemLanguageResultExecution timeMemory
1087507M4mouCounting Mushrooms (IOI20_mushrooms)C++17
92.24 / 100
6 ms704 KiB
/* * Solution with two mixed phases of fixed size * By "mixed" we mean that new types are also detected in the second phase. * By "fixed" we mean that #queries in the first phase is fixed from the beginning. * * Author: Kian Mirjalali */ #include "mushrooms.h" #include <cmath> #include <algorithm> #include <functional> using namespace std; #define allOf(c) ((c).begin()), ((c).end()) template<class C> inline int largest_element_index(const vector<C>& v) { return max_element(allOf(v), [](const C& c1, const C& c2) {return c1.size()<c2.size();}) - v.begin(); } /** * @returns ceil(a/b) for integers a, b */ template<class T> inline T ceildiv(T a, T b) { return (a+b-1)/b; } /** * Finds minimum input of a function in range [begin, end). * @param f a function : Integer -> Real * @param begin * @param end * @returns Integer input which minimizes f */ inline int functionMinInput(function<double(int)> f, int begin, int end) { int best = begin; double fbest = f(best); for (int i = begin+1; i < end; i++) { const double fi = f(i); if (fbest > fi) { best = i; fbest = fi; } } return best; } typedef int Index; typedef int SpeciesType; const SpeciesType TYPE_0 = 0; const SpeciesType TYPE_1 = 1; typedef vector<Index> Indices; class SpeciesTypes { vector<Indices> typesIndices; public: inline SpeciesTypes(): typesIndices(2) { } inline void add(SpeciesType type, Index index) { typesIndices[type].push_back(index); } inline const Indices& getIndices(SpeciesType type) const { return typesIndices[type]; } inline SpeciesType getLargestType() const { return largest_element_index(typesIndices); } }; class SpeciesCounts { vector<int> counts; public: inline SpeciesCounts(): counts({0, 0}) { } inline void add(SpeciesType type, int count=1, int otherCount=0) { counts[type] += count; counts[1-type] += otherCount; } inline int get(SpeciesType type) const { return counts[type]; } }; inline SpeciesType getType(Index i) { return use_machine({0, i}); } Index a, b; SpeciesType ta; inline vector<SpeciesType> getTypes(Index i, Index j) { const int d = use_machine({a, i, b, j}); return {(d>>1)^ta, (d&1)^ta}; } int count_mushrooms(int n) { SpeciesTypes knownSpeciesTypes; Index head = 0; if (n >= 1) { knownSpeciesTypes.add(TYPE_0, head); head++; if (n >= 2) { const SpeciesType t1 = getType(head); knownSpeciesTypes.add(t1, head); head++; if (n == 2 || t1 == TYPE_0) { a = 0; b = 1; ta = TYPE_0; } else {//n >= 3 && t1 == TYPE_1 const SpeciesType t2 = getType(head); knownSpeciesTypes.add(t2, head); head++; if (t2 == TYPE_0) { a = 0; b = 2; ta = TYPE_0; } else {//t2 == TYPE_1 a = 1; b = 2; ta = TYPE_1; } } } } const auto queries_func = [n, head] (int k)->double { int l = 0; for (int s = n-head-2*k; s > 0;) { s -= k+ceildiv(head+l, 2); l++; } return head-1+k+l; }; const int k = functionMinInput(queries_func, 0, int(2*sqrt(n))); for (int j = 0; j < k && head+2 <= n; j++) { const auto p = getTypes(head, head+1); knownSpeciesTypes.add(p[0], head); knownSpeciesTypes.add(p[1], head+1); head += 2; } SpeciesCounts speciesCounts; while (head < n) { const SpeciesType majType = knownSpeciesTypes.getLargestType(); const Indices& majIndices = knownSpeciesTypes.getIndices(majType); const int majSize = majIndices.size(); const int blockSize = min(majSize, n-head); Indices v(2*blockSize); for (int i = 0, j = 0; i < blockSize;) { v[j++] = head++; v[j++] = majIndices[i++]; } const int differences = use_machine(v); knownSpeciesTypes.add((differences&1)^majType, v[0]); const int differents = (differences>>1); const int same = blockSize-1-differents; speciesCounts.add(majType, same, differents); } return knownSpeciesTypes.getIndices(TYPE_0).size()+speciesCounts.get(TYPE_0); }
#Verdict Execution timeMemoryGrader output
Fetching results...