제출 #1032593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032593		sleepntsheep	버섯 세기 (IOI20_mushrooms)	C++17	50.33 / 100	7 ms	440 KiB

mushrooms

#include "mushrooms.h"
#include <cassert>

int count_mushrooms(int n) {
    if (n <= 227) {
        int count = 1, cur = 0;
        for (int i = 1; i < n; ++i) {
            cur ^= (use_machine({i - 1, i}));
            count += !cur;
        }
        return count;
    }

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

    int X = 101, reach = 0;

    for (int i = 1; B.size() < 2 && i < X; i += 2) {
        int y = use_machine({0, i, i + 1});
        if (y == 0) {
            A.push_back(i);
            A.push_back(i + 1);
        } else if (y == 2) {
            B.push_back(i);
            A.push_back(i + 1);
        } else if (y == 1) {
            if (use_machine({0, i})) {
                B.push_back(i);
                B.push_back(i + 1);
            } else {
                A.push_back(i);
                B.push_back(i + 1);
            }
        } else
            __builtin_unreachable();
        reach = i + 1;
    }

    for (int i = reach + 1; i < X; i += 2) {
        int y = use_machine({i, 0, B[0], i + 1, B[1]});
        if (y == 1) {
            A.push_back(i);
            B.push_back(i + 1);
        } else if (y == 2) {
            B.push_back(i);
            B.push_back(i + 1);
        } else if (y == 3) {
            A.push_back(i);
            A.push_back(i + 1);
        } else if (y == 4) {
            B.push_back(i);
            A.push_back(i + 1);
        } else
            __builtin_unreachable();
    }

    int count = A.size();

    int amogus = std::max(A.size(), B.size());
    int chosen = A.size() >= B.size() ? 0 : 1;

    int l = X;
    while (l < n) {
        int r = std::min(n, l + amogus - 1) - 1;

        std::vector<int> m;

        if (0 == chosen) {
            m = {A[0]};
            for (int j = l, k = 1; j <= r; ++j, ++k) {
                m.push_back(j);
                m.push_back(A[k]);
            }
            count += (r - l + 1) - use_machine(m) / 2;
        } else {
            m = {B[0]};
            for (int j = l, k = 1; j <= r; ++j, ++k) {
                m.push_back(j);
                m.push_back(B[k]);
            }
            count += use_machine(m) / 2;
        }

        l = r + 1;
    }


	return count;
}

• Subtask 1: 50.3341 / 100