Submission #565122

#	Time	Username	Problem	Language	Result	Execution time	Memory
565122		imtiyazrasool92	Cave (IOI13_cave)	C++17	0 / 100	367 ms	392 KiB

cave

#include "cave.h"
#include<vector>

using namespace std;

void exploreCave(int N) {
    vector<bool> done(N);
    int switchs[N];
    int doors[N];

    for (int i = 0; i < N; i++)
        switchs[i] = doors[i] = 0;

    auto change = [&]()->void {
        for (int i = 0; i < N; i++)
            if (!done[i])
                switchs[i] ^= 1;
    };

    auto changed = [&](int mid, int pref)->bool {
        for (int i = 0; i <= mid; i++)
            if (!done[i])
                switchs[i] ^= 1;

        int A = tryCombination(switchs);

        for (int i = 0; i <= mid; i++)
            if (!done[i])
                switchs[i] ^= 1;

        return A >= pref;
    };

    for (int i = 0; i < N; i++) {
        int pref = tryCombination(switchs);
        if (pref > i) {
            change();
        }

        int L = 0, R = N - 1;
        while (L < R) {
            int mid = (L + R) / 2;
            if (changed(mid, i + 1)) {
                R = mid;
            } else {
                L = mid + 1;
            }
        }

        doors[i] = R;
        switchs[R] ^= 1;
        done[R] = true;
    }

    answer(switchs, doors);
}

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