Submission #413340

#	Time	Username	Problem	Language	Result	Execution time	Memory
413340		phathnv	Counting Mushrooms (IOI20_mushrooms)	C++17	99.56 / 100	74 ms	416 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;

int count_mushrooms(int n) {
    vector<int> s[8], q1 = {0, 1, 5, 2, 6, 3, 7, 4}, q2[8];
    map<int, int> mp[8];
    for(int mask = 0; mask < 32; mask++) {
        vector<int> a(9);
        a[8] = 1;
        for(int i = 0; i < 5; i++)
            a[i] = mask >> i & 1;
        int sum = 0;
        for(int i = 1; i < 8; i++)
            sum += a[q1[i - 1]] ^ a[q1[i]];
        s[sum].push_back(mask);
    }
    for(int i = 0; i < 8; i++){
        vector<int> p(9);
        iota(p.begin(), p.end(), 0);
        bool ok = 0;
        do {
            map<int, int> sums;
            for(int mask : s[i]) {
                vector<int> a(9, 0);
                a[8] = 1;
                for(int i = 0; i < 5; i++)
                    a[i] = mask >> i & 1;
                int sum = 0;
                for(int i = 1; i < 9; i++)
                    sum += a[p[i - 1]] ^ a[p[i]];
                sums[sum] = mask;
            }
            if (s[i].size() == sums.size()) {
                ok = 1;
                q2[i] = p;
                mp[i] = sums;
                break;
            }
        } while (next_permutation(p.begin(), p.end()));
        assert(ok);
    }

    vector<int> type[2];
    type[0].push_back(0);
    int flag = 0, cur = 1, k = -1, best = 1e9, cnt[2] = {0, 0};
    for(int i = 0; i <= n / 5; i++) {
        int numQ = 3 + 2 * i, x = 5 + 5 * i, rem = n - x;
        while (rem > 0) {
            rem -= (x + 1) / 2;
            x++;
            numQ++;
        }
        if (numQ < best) {
            best = numQ;
            k = 5 + 5 * i;
        }
    }
    cerr << "k: " << k << endl;
    while (cur < n) {
        if (type[0].size() < type[1].size()) {
            flag ^= 1;
            swap(type[0], type[1]);
            swap(cnt[0], cnt[1]);
        }
        if ((int) cur < k) {
            int num = min(5, n - cur);
            if (num < 5 || (int) type[0].size() < 3 || (int) type[1].size() < 1) {
                num = min(num, min(2, (int) type[0].size()));
                vector<int> a;
                for(int i = 0; i < num; i++) {
                    a.push_back(cur + i);
                    a.push_back(type[0][i]);
                }
                int x = use_machine(a);
                for(int i = 0; i < num; i++)
                    type[(x >> i) & 1].push_back(cur + i);
                cur += num;
            } else {
                vector<int> pos;
                for(int i = 0; i < 5; i++)
                    pos.push_back(cur + i);
                for(int i = 0; i < 3; i++)
                    pos.push_back(type[0][i]);
                pos.push_back(type[1][0]);
                vector<int> a;
                for(int x : q1)
                    a.push_back(pos[x]);
                int res = use_machine(a);
                a.clear();
                for(int x : q2[res])
                    a.push_back(pos[x]);
                int mask = mp[res][use_machine(a)];
                for(int i = 0; i < 5; i++)
                    type[(mask >> i) & 1].push_back(cur + i);
                cur += num;
            }
        } else {
            int num = min(n - cur, (int) type[0].size());
            vector<int> a;
            for(int i = 0; i < num; i++) {
                a.push_back(cur + i);
                a.push_back(type[0][i]);
            }
            int x = use_machine(a);
            type[x & 1].push_back(cur);
            cnt[1] += x / 2;
            cnt[0] += (num - 1) - x / 2;
            cur += num;
        }
    }
    if (flag) {
        flag ^= 1;
        swap(type[0], type[1]);
        swap(cnt[0], cnt[1]);
    }
    return cnt[0] + type[0].size();
}

• Subtask 1: 99.5595 / 100