Submission #1217024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217024		lukasuliashvili	Cave (IOI13_cave)	C++20	0 / 100	431 ms	516 KiB

cave

#include "cave.h"
#include <vector>
using namespace std;

void exploreCave(int N) {
    vector<int> s(N, 0);         // current guess for switch states
    vector<int> finalSwitch(N);  // correct states of switches
    vector<int> doorToSwitch(N); // which switch controls each door
    vector<bool> used(N, false); // mark switches already assigned

    for (int d = 0; d < N; ++d) {
        int low = 0, high = N - 1, found = -1;

        // Binary search to find the switch controlling door d
        while (low <= high) {
            int mid = (low + high) / 2;
            for (int i = 0; i < N; ++i) {
                if (used[i]) continue;
                s[i] = 0;
            }
            for (int i = low; i <= mid; ++i) {
                if (!used[i]) s[i] = 1;
            }

            int res = tryCombination(s.data());

            if (res == d || res == -1) {
                // Found the switch in [low, mid]
                found = -1;
                for (int i = low; i <= mid; ++i) {
                    if (!used[i]) {
                        found = i;
                        break;
                    }
                }
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // Find correct state (0 or 1) for switch `found`
        s[found] = 0;
        for (int i = 0; i < N; ++i)
            if (!used[i] && i != found) s[i] = 0;

        int res0 = tryCombination(s.data());

        finalSwitch[found] = (res0 == d || res0 == -1) ? 0 : 1;
        doorToSwitch[found] = d;
        used[found] = true;
    }

    answer(finalSwitch.data(), doorToSwitch.data());
}

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