Submission #1193918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193918		dong_gas	Counting Mushrooms (IOI20_mushrooms)	C++20	57.07 / 100	4 ms	432 KiB

mushrooms

#include <bits/extc++.h>
using namespace std;
int use_machine(vector<int> x);

int f(int n) {
    int b = 0;
    for (int i = 1; i + 1 < n; i += 2) b += use_machine({i, 0, i + 1});
    if ((n & 1) == 0) b += use_machine({0, n - 1});
    return n - b;
}

// sqrt(20000) = 141.xx

int count_mushrooms(int n) {
    if (n <= 450) return f(n);
    vector<int> a = {0}, b;
    int acnt = 1, bcnt = 0, idx = 1, s = sqrt(20000);
    while (max(a.size(), b.size()) < s && idx < n) {
        if (use_machine({idx, 0})) b.push_back(idx++), bcnt++;
        else a.push_back(idx++), acnt++;
    }
    while (idx < n) {
        vector<int> q, &c = (a.size() >= b.size()) ? a : b;
        int qcnt = 0;
        for (int i = 0; i < c.size() && idx < n; i++) q.push_back(c[i]), q.push_back(idx++), qcnt++;
        // for (auto qq: q) cout << qq << ' ';
        // cout << endl;
        int ret = use_machine(q);
        int p = ret / 2 + (ret & 1);
        if (a.size() >= b.size()) {
            if (ret & 1) b.push_back(idx - 1);
            else a.push_back(idx - 1);
            acnt += qcnt - p, bcnt += p;
        }
        else {
            if (ret & 1) a.push_back(idx - 1);
            else b.push_back(idx - 1);
            acnt += p, bcnt += qcnt - p;
        }
        // cout << acnt << ' ' << bcnt << endl;
    }
    return acnt;
}

• Subtask 1: 57.0707 / 100