Submission #813306

#	Time	Username	Problem	Language	Result	Execution time	Memory
813306		Pikachu	Cave (IOI13_cave)	C++17	100 / 100	202 ms	436 KiB

cave

#include <stdio.h>
#include <stdbool.h>
#include "cave.h"

const int maxn = 5010;

void reverse(int l, int r, bool done[], int S[])
{
    for (int i = l; i <= r; i++) {
        if (!done[i]) S[i] = !S[i];
    }
}

void exploreCave(int n)
{
    int S[maxn], D[maxn];
    bool done[maxn];
    for (int i = 0; i < n; i++) {
        if (tryCombination(S) == i) reverse(0, n - 1, done, S);
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            reverse(l, mid, done, S);
            if (tryCombination(S) == i) {
                r = mid;
            }
            else l = mid + 1;
            reverse(l, mid, done, S);
        }
        done[l] = true;
        D[l] = i;
    }
    answer(S, D);
}

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