Submission #824025

#	Time	Username	Problem	Language	Result	Execution time	Memory
824025		drdilyor	Counting Mushrooms (IOI20_mushrooms)	C++17	80.14 / 100	7 ms	464 KiB

mushrooms

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

int count_mushrooms(int n) {

    const int B = 285; // sqrt(4n)

    vector<int> t(n);
    t[1] = use_machine({0, 1});
    if (n == 2) return 2 - t[1] - t[0];
    t[2] = use_machine({0, 2});
    bool inv = false;
    int cmp1, cmp2;
    if (t[1] && t[2]) {
        cmp1 = 1;
        cmp2 = 2;
        inv = true;
        t[0] ^= 1;
        t[1] ^= 1;
        t[2] ^= 1;
    } else {
        cmp1 = 0;
        if (!t[1]) cmp2 = 1;
        else cmp2 = 2;
    }


    for (int i = 3; i < n-1 && i < B; i += 2) {
        int res = use_machine({cmp1, i, cmp2, i+1});
        t[i] = res / 2;
        t[i+1] = res % 2;
    }

    if (inv)
        for (int& i : t)
            i ^= 1;

    if (n < B && n % 2 == 0)
        t[n-1] = use_machine({0, n-1});

    int ans = 0;
    for (int i = 0; i < n && i < B; i++)
        if (t[i] == 0) ans++;
    if (n <= B) return ans;

    vector<int> As, Bs;
    for (int i = 0; i < B; i++) {
        if (t[i] == 0) As.push_back(i);
        else Bs.push_back(i);
    }
    vector<int> grp = As.size() > Bs.size() ? As : Bs;
    for (int j = B; j < n; j += B / 2) {
        vector<int> cur{grp.front()};
        int all_cnt = 0;
        for (int k = j; k < n && k < j + B / 2; k++) {
            cur.push_back(k);
            cur.push_back(grp[k - j + 1]);
            all_cnt++;
        }
        int cnt = use_machine(cur);
        assert(cnt % 2 == 0);
        cnt /= 2;
        if (grp == Bs) {
            ans += cnt;
        } else {
            ans += all_cnt - cnt;
        }
    }

    return ans;
}

• Subtask 1: 80.1418 / 100