Submission #321975

#	Time	Username	Problem	Language	Result	Execution time	Memory
321975		grt	Counting Mushrooms (IOI20_mushrooms)	C++17	54.85 / 100	13 ms	492 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

const int B = 150;
vi a, b;

int use_machine(vi x);

int count_mushrooms(int n) {
    srand(time(NULL));
    if(n == 1) return 1;
    vi v(n-1);
    a = {};
    b = {};
    for(int i = 1; i < n; ++i) v[i - 1] = i;
    random_shuffle(v.begin(), v.end());
    a.PB(0);
    for(int i = 0; i < min(n - 1, B); ++i) {
        int w = use_machine({0, v[i]});
        if(w == 1) b.PB(v[i]);
        else a.PB(v[i]);
    }
    int ans = (int)a.size();
    bool inv = 0;
    if((int)a.size() < (int)b.size()) {
        swap(a, b);
        inv = 1;
    }
    for(int i = B; i < n - 1; i += (int)a.size()) {
        vi s = {};
        int nxt = 0, all = 0;
        for(int j = i; j < min(n - 1, i + (int)a.size()); ++j) {
            s.PB(a[nxt++]);
            s.PB(v[j]);
            all++;
        }
        int w = use_machine(s);
        if(!inv) {
            int cntB = w / 2 + (w % 2);
            ans += all - cntB;
        } else {
            ans += w/2 + (w%2);
        }
    }
    return ans;
}

• Subtask 1: 54.8544 / 100