Submission #803008

#	Time	Username	Problem	Language	Result	Execution time	Memory
803008		jakobrs	Cave (IOI13_cave)	C++17	0 / 100	37 ms	560 KiB

cave

#include <list>
#include <vector>

extern "C" {
    int tryCombination(int S[/* who needs type safety */]);
    void answer(int S[], int D[]);

    void exploreCave(int N);
}

std::vector<int> states;

using pos = std::list<int>::iterator;
std::list<int> left;

int binarySearch(pos start, pos end, int n, int idx, int correctState, int currentState) {
    if (n == 1) {
        int c = *start;
        left.erase(start);
        return c;
    }

    int m = n / 2;
    auto mid = start;
    for (int i = 0; i < m; i++, mid++) {
        states[*mid] = !currentState;
    }

    bool open = tryCombination(states.data()) > idx;
    if (open == (currentState == correctState)) {
        return binarySearch(mid, end, n - m, idx, correctState, currentState);
    } else {
        return binarySearch(start, mid, m, idx, correctState, !currentState);
    }
}

void exploreCave(int N) {
    for (int i = 0; i < N; i++) {
        left.push_back(i);
    }
    states.resize(N);
    std::vector<int> positions(N, 0);

    for (int idx = 0; idx < N; idx++) {
        for (int j : left) {
            states[j] = 1;
        }
        bool correctState = tryCombination(states.data()) > idx;

        int c = binarySearch(left.begin(), left.end(), N - idx, idx, correctState, 1);
        positions[c] = idx;
    }

    answer(states.data(), positions.data());
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24