Submission #1289903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289903		kahoul	Cave (IOI13_cave)	C++20	100 / 100	277 ms	512 KiB

cave

#include <bits/stdc++.h>
using namespace std;
#include "cave.h"

const int maxn = 5005;
bool visited[maxn];
int s[maxn];
int lever_door[maxn];

void set_all_to (int l, int r, int x) {
    for (int i = l; i <= r; i++) {
        if (visited[i]) continue;
        s[i] = x;
    }
}

void divide (int l, int r, int d, bool act) {
    if (l == r) {
        s[l] = act;
        lever_door[l] = d;
        visited[l] = 1;
        return;
    }

    int m = (l + r) / 2;

    set_all_to(l, m, act);
    int door = tryCombination(s);

    if (door == d) {
        divide(m + 1, r, d, act);
    } else {
        set_all_to(l, m, act ^ 1);
        divide(l, m, d, act);
    }
}

void exploreCave (int n) {
    for (int i = 0; i < n; i++) {
        set_all_to(0, n - 1, 0);
        int door = tryCombination(s);
        if (door == i) {
            set_all_to(0, n - 1, 0);
            divide(0, n - 1, i, 1);
        }
        else {
            set_all_to(0, n - 1, 1);
            divide(0, n - 1, i, 0);
        }
    }

    answer(s, lever_door);
}

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