Submission #784727

#	Time	Username	Problem	Language	Result	Execution time	Memory
784727		vjudge1	Cave (IOI13_cave)	C++17	100 / 100	408 ms	516 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

void exploreCave(int n) {
    int guess[n], status[n], door[n];
    memset(status, 0, sizeof(status));
    memset(door, -1, sizeof(door));
    for (int i = 0; i < n; i++) {
        int l = 0, r = n - 1;
        int before = tryCombination(status);
        while (l < r) {
            int m = (l + r) / 2;
            bool flag = 0;
            for (int j = 0; j < n; j++) {
                if (l <= j && j <= m) {
                    if (door[j] != -1) guess[j] = status[j];
                    else {
                        guess[j] = !status[j];
                        flag = 1;
                    }
                }
                else guess[j] = status[j];
            }
            int cur = before;
            if (flag) cur = tryCombination(guess);
            if (before == i) {
                if (cur > i || cur == -1) r = m;
                else l = m + 1;
            }
            else {
                if (cur == i) r = m;
                else l = m + 1;
            }
        }
        door[l] = i;
        if (before == i) status[l] = !status[l];
    }
    answer(status, door);
}

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