Submission #803022

#	Time	Username	Problem	Language	Result	Execution time	Memory
803022		jakobrs	Cave (IOI13_cave)	C++17	100 / 100	103 ms	468 KiB

cave

#include <iostream>
#include <list>
#include <vector>

#include "cave.h"

std::vector<int> states;

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

int N;
int betterTryCombination(int S[]) {
    int a = tryCombination(S);
    return a >= 0 ? a : N;
}

int binarySearch(pos start, pos end, int n, int idx, int correctState,
                 int currentState) {
    if (n == 1) {
        states[*start] = correctState;
        int c = *start;
        *start = std::move(left.back());
        left.pop_back();
        return c;
    }

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

    bool open = betterTryCombination(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_) {
    N = N_;
    for (int i = 0; i < N; i++) {
        left.push_back(i);
    }
    states.resize(N);
    std::vector<int> positions(N, 0);

    std::cerr << N << '\n';

    for (int idx = 0; idx < N; idx++) {
        for (int j : left) {
            states[j] = 1;
        }
        bool correctState = betterTryCombination(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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24