Submission #680996

#	Time	Username	Problem	Language	Result	Execution time	Memory
680996		nutella	Cave (IOI13_cave)	C++17	100 / 100	716 ms	556 KiB

cave

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

using namespace std;

constexpr int N = 5001;

int S[N], D[N], T[N];

void exploreCave(int n) {
    for (int i = 0; i < n; ++i) {
        memset(T, 0, sizeof(T));
        for (int j = 0; j < i; ++j) {
            T[D[j]] = S[j];
        }

        int type;
        int got = tryCombination(T);
        if (got == -1 || got >= i + 1) {
            type = 0;
        } else {
            type = 1;
        }

        int lo = 0, hi = n;
        while (lo + 1 < hi) {
            int mid = (lo + hi) >> 1;

            for (int j = 0; j < mid; ++j) {
                T[j] = type;
            }
            for (int j = mid; j < n; ++j) {
                T[j] = type ^ 1;
            }
            for (int j = 0; j < i; ++j) {
                T[D[j]] = S[j];
            }

            got = tryCombination(T);
            if (got == -1 || got >= i + 1) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        S[i] = type, D[i] = lo;
    }

    for (int i = 0; i < n; ++i) {
        T[D[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        D[i] = S[T[i]];
    }

    answer(D, T);
}

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