Submission #523016

#	Time	Username	Problem	Language	Result	Execution time	Memory
523016		dxz05	Counting Mushrooms (IOI20_mushrooms)	C++14	83.70 / 100	11 ms	516 KiB

mushrooms

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

#include <random>

using namespace std;

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

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);

    shuffle(p.begin() + 1, p.end(), std::mt19937(std::random_device()()));

    vector<int> A = {0}, B;

    int k = 80;

    int i = 1;
    while (i < 3){
        if (use_machine({0, p[i]}) == 0) A.push_back(p[i]); else
            B.push_back(p[i]);
        i++;
    }

    if (A.size() >= 2){
        int cnt = use_machine({A[0], p[i], A[1], p[i + 1]});
        if (cnt & 2) B.push_back(p[i]); else
            A.push_back(p[i]);
        if (cnt & 1) B.push_back(p[i + 1]); else
            A.push_back(p[i + 1]);
    } else {
        int cnt = use_machine({B[0], p[i], B[1], p[i + 1]});
        if (cnt & 2) A.push_back(p[i]); else
            B.push_back(p[i]);
        if (cnt & 1) A.push_back(p[i + 1]); else
            B.push_back(p[i + 1]);
    }
    i += 2;

    while (i < 2 * k + 3){
        if (A.size() >= 3){
            int cnt = use_machine({A[0], p[i], A[1], p[i + 1], A[2], p[i + 2]});
            if (cnt / 2 != 1){
                if (cnt / 2 == 0) A.push_back(p[i]), A.push_back(p[i + 1]); else
                    B.push_back(p[i]), B.push_back(p[i + 1]);
            } else {
                if (use_machine({0, p[i]}) == 0) A.push_back(p[i]), B.push_back(p[i + 1]); else
                    B.push_back(p[i]), A.push_back(p[i + 1]);
            }
            if (cnt & 1) B.push_back(p[i + 2]); else
                A.push_back(p[i + 2]);
        } else {
            int cnt = use_machine({B[0], p[i], B[1], p[i + 1], B[2], p[i + 2]});
            if (cnt / 2 != 1){
                if (cnt / 2 == 0) B.push_back(p[i]), B.push_back(p[i + 1]); else
                    A.push_back(p[i]), A.push_back(p[i + 1]);
            } else {
                if (use_machine({0, p[i]}) == 0) A.push_back(p[i]), B.push_back(p[i + 1]); else
                    B.push_back(p[i]), A.push_back(p[i + 1]);
            }
            if (cnt & 1) A.push_back(p[i + 2]); else
                B.push_back(p[i + 2]);
        }
        i += 3;
    }

    int res = A.size();

    while (i < n){
        vector<int> r;
        if (A.size() > B.size()){
            for (int x : A){
                if (i >= n) break;
                r.push_back(x);
                r.push_back(p[i]);
                i++;
            }

            int cnt = use_machine(r);
            if (cnt & 1) B.push_back(r.back()); else
                A.push_back(r.back());
            res += r.size() / 2 - (cnt + 1) / 2;
        } else {
            for (int x : B){
                if (i >= n) break;
                r.push_back(x);
                r.push_back(p[i]);
                i++;
            }
            int cnt = use_machine(r);
            if (cnt & 1) A.push_back(r.back()); else
                B.push_back(r.back());
            res += (cnt + 1) / 2;
        }
    }

    return res;
}

• Subtask 1: 83.7037 / 100