Submission #547320

#	Time	Username	Problem	Language	Result	Execution time	Memory
547320		Monarchuwu	Cave (IOI13_cave)	C++17	100 / 100	759 ms	648 KiB

cave

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

const int MAXN = 5000 + 3;
int Switch[MAXN];
bool state[MAXN];
int n, tmp[MAXN];
int get(int num, int lim, int x) {
    fill(tmp, tmp + lim + 1, x);
    fill(tmp + lim + 1, tmp + n, x ^ 1);
    for (int i = 0; i < num; ++i) tmp[Switch[i]] = state[i];
    x = tryCombination(tmp);
    return ~x ? x : n + 1;
}
int a[MAXN], b[MAXN]; // switch i match with door b[i]
void print_answer() {
    for (int i = 0; i < n; ++i) {
        b[Switch[i]] = i;
        a[Switch[i]] = state[i];
    }
    answer(a, b);
}
void exploreCave(int MAXN) {
    n = MAXN;
    for (int i = 0; i < n; ++i) {
        state[i] = get(i, n - 1, 1) > i ? 1 : 0;
        int lo(0), hi(n - 2), m;
        while (lo <= hi) {
            m = (lo + hi) >> 1;
            if (get(i, m, state[i]) > i)
                hi = m - 1;
            else lo = m + 1;
        }
        Switch[i] = hi + 1; // door i match with switch hi+1
    }
    print_answer();
}

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