Submission #824005

#	Time	Username	Problem	Language	Result	Execution time	Memory
824005		drdilyor	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	2 ms	208 KiB

mushrooms

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

int count_mushrooms(int n) {

    const int B = 281; // 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 = n - accumulate(t.begin(), t.end(), 0);
    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> inter;
        for (int k = j; k < n && k < j + B / 2; k++)
            inter.push_back(j);
        vector<int> cur;
        for (int i = 0; i < (int)inter.size(); i++) {
            cur.push_back(grp[i]);
            cur.push_back(inter[i]);
        }
        cur.push_back(grp[inter.size()]);
        int cnt = use_machine(cur);
        assert(cnt % 2 == 0);
        cnt /= 2;
        if (grp == Bs) {
            ans += cnt;
        } else {
            ans += inter.size() - cnt;
        }
    }

    return ans;
}

• Subtask 1: 0 / 100