Submission #996392

#	Time	Username	Problem	Language	Result	Execution time	Memory
996392		phoenix	Cave (IOI13_cave)	C++17	100 / 100	433 ms	748 KiB

cave

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

using namespace std;

void exploreCave(int n) {
    int s[n] = {}, d[n] = {};
    bool answered[n] = {};

    for (int door = 0; door < n; door++) {
        for (int i = 0; i < n; i++) {
            if (answered[i]) continue;
            s[i] = 0;
        }
        if (tryCombination(s) == door) {
            // [1]
            int l = -1, r = n - 1;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                for (int i = 0; i < n; i++) {
                    if (answered[i]) continue;
                    if (i <= mid) s[i] = 1;
                    else s[i] = 0;
                }
                if (tryCombination(s) == door) 
                    l = mid;
                else 
                    r = mid;
            }
            d[r] = door;
            s[r] = 1;
            answered[r] = true;
        } else {
            // [0]
            int l = -1, r = n - 1;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                for (int i = 0; i < n; i++) {
                    if (answered[i]) continue;
                    if (i <= mid) s[i] = 0;
                    else s[i] = 1;
                }
                if (tryCombination(s) == door)
                    l = mid;
                else 
                    r = mid;
            }
            d[r] = door;
            s[r] = 0;
            answered[r] = true;
        }
    }
    answer(s, d);
}

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