Submission #1214385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214385		thangdz2k7	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 ms	424 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

const int needs = 125;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

int count_mushrooms(int n){
    if (n <= 227){
        int cntA = 1;
        for (int i = 1; i < n; ++ i){
            vector <int> ask = {0, i};
            if (use_machine(ask) == 0) cntA ++;
        }
        return cntA;
    }

    vector <int> ord(n);
    shuffle(ord.begin() + 1, ord.end(), rd);

    auto qry = [&](vector <int> tmp) -> int {
        vector <int> ask;
        for (int i : tmp) ask.push_back(ord[i]);
        return use_machine(ask);
    };

    vector <int> type(n, -1);
    vector <int> cnt(2, 0);
    vector <vector <int>> s(2);

    auto fix = [&](int i, int t) -> void {
        type[i] = t;
        cnt[t] ++;
        s[t].push_back(i);
    };

    fix(0, 0);

    for (int c : {1, 2}){
        vector <int> tmp = {0, c};
        if (qry(tmp) == 0) fix(c, 0);
        else fix(c, 1);
    }

    int cur = 0;
    if (cnt[1] == 2) cur = 1;
    int ptr = 3;

    while (max(cnt[0], cnt[1]) < needs){
        if (ptr == n - 1){
            vector <int> tmp = {0, ptr};
            if (qry(tmp) == 0) fix(ptr, 0);
            else fix(ptr, 1);
            return cnt[0];
        }

        vector <int> tmp = {s[cur][0], ptr, s[cur][1], ptr + 1};
        int rt = qry(tmp);

        fix(ptr + 1, cur ^ (rt & 1));
        fix(ptr, cur ^ (rt > 1));
        ptr += 2;
    }

    while (ptr < n){
        int cur = 0;
        if (s[1].size() > s[0].size()) cur = 1;
        if (s[cur].size() > n - ptr){
            vector <int> tmp = {s[cur][0]};
            for (int i = ptr; i < n; ++ i){
                tmp.push_back(i);
                tmp.push_back(s[cur][i - ptr + 1]);
            }
            int rt = qry(tmp);
            cnt[cur ^ 1] += rt / 2;
            cnt[cur] += (n - ptr - rt / 2);
            return cnt[0];
        }

        int siz = s[cur].size();
        vector <int> tmp;
        for (int i = 0; i < siz; ++ i){
            tmp.push_back(s[cur][i]);
            tmp.push_back(ptr + i);
        }
        int rt = qry(tmp);
        fix(ptr + siz - 1, cur ^ (rt & 1));
        cnt[cur ^ 1] += rt / 2;
        cnt[cur] += (siz - 1 - rt / 2);
        ptr += siz;
    }

    return cnt[0];
}

• Subtask 1: 0 / 100