Submission #303621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
303621	2020-09-20T13:32:21 Z	alex_velea	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	2000 ms	388 KB

mushrooms

#include <bitset>
#include <array>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define DEBUG if(0)

int count_mushrooms(int n);

int use_machine(vector<int> x);

const int kMaxLen = 8;

struct Solver {
    int start, n;
    bool valid[1 << kMaxLen];

    Solver(int start, int n) : start(start), n(n) {
        for (int i = 0; i < (1 << n); i += 1) {
            valid[i] = true;
        }
    }

    void FixFirst() {
        int firstEl = use_machine({0, start});
        for (int i = 0; i < (1 << n); i += 1) {
            valid[i] = (i & 1) == firstEl;
        }
    }
    
    int GetCount(int mask) {
        int ans = 0;
        for (int i = 0; i < n; i += 1) {
            cerr << (!!(mask & (1 << i)));
            ans += (mask & (1 << i)) == 0;
        }
        return ans;
    }

    int GetCost(int state, vector<int> order) {
        int cost = 0;
        for (int i = 1; i < (int)order.size(); i += 1) {
            cost += (!!(state & (1 << order[i - 1]))) != (!!(state & (1 << order[i]))); 
        }
        return cost;
    }

    vector<int> GetBestMove() {
        vector<int> best;
        int best_cost = (1 << n);
        vector<int> current_order = {};
        for (int i = 0; i < n; i += 1) {
            current_order.push_back(i);
        }

        for (int i = 0; i < (1 << n); i += 1) {
            random_shuffle(current_order.begin(), current_order.end());
            
            array<int, kMaxLen> freq;
            for (int i = 0; i < kMaxLen; i += 1) {
                freq[i] = 0;
            }

            for (int i = 0; i < (1 << n); i += 1) {
                if (valid[i]) {
                    int cost = GetCost(i, current_order);
                    DEBUG cerr << cost << ' ';
                    freq[cost] += 1;
                }
            }

            int mx = 0;
            for (auto& itr : freq) {
                mx = max(mx, itr);
            }

            DEBUG cerr << "Current max = " << mx << '\n';

            if (best_cost > mx) {
                mx = best_cost;
                best = current_order;
            }
        }
        return best;
    }

    int Solve() {
        DEBUG cerr << "Solve .. " << start << '\t' << n << '\n';
        FixFirst();
        vector<int> available;
        while (1) {
            DEBUG cerr << "Run .. \n";
            available.clear();
            for (int i = 0; i < (1 << n); i += 1) {
                if (valid[i]) {
                    bitset<kMaxLen> b(i);
                    DEBUG cerr << "Ok .. " << b << "\n";
                    available.push_back(i);
                }
            }

            if (available.size() == 1) {
                return GetCount(available[0]); 
            }

            auto best = GetBestMove();
            DEBUG {
                cerr << "Best = \t";
                for (auto& itr : best) {
                    cerr << itr << '\t';
                }
                cerr << '\n';
            }
            auto q = best;
            for (auto& itr : q) {
                itr += start;
            }

            int ans = use_machine(q);
            DEBUG cerr << "Ans = " << ans << '\n';
            for (int i = 0; i < (1 << n); i += 1) {
                if (valid[i] and GetCost(i, best) != ans) {
                    valid[i] = false;
                }
            }
        }
    }
};

int count_mushrooms(int n) {
    int ans = 1;
    for (int i = 1; i < n; i += kMaxLen) {
        Solver s(i, min(kMaxLen, n - i));
        ans += s.Solve();
    }
    DEBUG cerr << "ans = " << ans << '\n';
    cerr << '\n';
    return ans;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	3 ms	256 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	73 ms	256 KB	Output is correct
6	Partially correct	636 ms	256 KB	Output is partially correct
7	Execution timed out	3008 ms	388 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-