Submission #565219

#	Time	Username	Problem	Language	Result	Execution time	Memory
565219		imtiyazrasool92	Cave (IOI13_cave)	C++17	100 / 100	895 ms	460 KiB

cave

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

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);

        A = (A == -1 ? N : A);

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

        return A >= pref;
    };

    for (int i = 0; i < N - 1; i++) {
        int pref = tryCombination(switchs);
        pref = (pref == -1 ? N : pref);
        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[R] = i;
        switchs[R] ^= 1;
        done[R] = true;
    }

    for (int i = 0; i < N; i++)
        if (!done[i]) {
            doors[i] = N - 1;
            if (tryCombination(switchs) != -1)
                switchs[i] ^= 1;
            break;
        }

    answer(switchs, doors);
}

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