제출 #1231527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231527		LucaIlie	Counting Mushrooms (IOI20_mushrooms)	C++17	79.30 / 100	3 ms	504 KiB

mushrooms

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

using namespace std;

int count_mushrooms(int n) {
    bool isA;
    const int k = min(n, max(3, ((int)sqrt(3 * n)) * 2 / 2 + 1)), a = 0, b = 1;
    int nrA, pos1, pos2, bs;
    vector <int> s(n), pos;

    if (n <= 10) {
        nrA = 1;
        for (int i = 1; i < n; i++)
            nrA += 1 - use_machine({0, i});
        return nrA;
    }

    s[0] = a;
    s[1] = use_machine({ 0, 1 }) == 0 ? a : b;
    s[2] = use_machine({ 0, 2 }) == 0 ? a : b;
    nrA = (s[0] == a) + (s[1] == a) + (s[2] == a);
    if (nrA == 1) {
        isA = false;
        pos1 = 1;
        pos2 = 2;
    } else {
        isA = true;
        pos1 = 0;
        pos2 = (s[1] == a ? 1 : 2);
    }

    for (int i = 3; i < k; i += 2) {
        int r = use_machine({pos1, i, pos2, i + 1});
        if (r == 0)
            s[i] = s[i + 1] = (isA ? a : b);
        else if (r == 1) {
            s[i] = (isA ? a : b);
            s[i + 1] = (isA ? b : a);
        } else if (r == 2) {
            s[i] = (isA ? b : a);
            s[i + 1] = (isA ? a : b);
        } else
            s[i] = s[i + 1] = (isA ? b : a);
    }
    for (int i = 3; i < k; i++)
        nrA += (s[i] == a);
    if (nrA > k / 2) {
        bs = nrA - 1;
        isA = true;
    } else {
        bs = k - nrA - 1;
        isA = false;
    }
    for (int i = 0; i < k; i++) {
        if (s[i] == (isA ? a : b))
            pos.push_back(i);
    }

    for (int i = k; i < n; i += bs) {
        int j;
        vector <int> m;

        for (j = 0; j + 1 < (int)pos.size() && i + j < n; j++) {
            m.push_back(pos[j]);
            m.push_back(i + j);
        }
        m.push_back(pos.back());

        if (isA)
            nrA += j - use_machine(m) / 2;
        else
            nrA += use_machine(m) / 2;
    }

    return nrA;
}

• Subtask 1: 79.2982 / 100