Submission #591399

#	Time	Username	Problem	Language	Result	Execution time	Memory
591399		shrimb	Cave (IOI13_cave)	C++17	100 / 100	535 ms	720 KiB

cave

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

using namespace std;


const int maxn = 5001;

int S[maxn], D[maxn], Q[maxn];
//   state    door     query


void exploreCave(int n) {
    vector<int> buffer;
    for (int i = 0 ; i < n ; i++) {
        buffer.push_back(i);
    }
    for (int i = 0 ; i < n ; i++) {
        for (int j : buffer) Q[j] = 0;
        int T = tryCombination(Q) == i;
        int sz = n - i;
        int l = -1, r = sz - 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            for (int j = 0 ; j < sz ; j++) {
                Q[buffer[j]] = T ^ (j > m);
            }
            if (tryCombination(Q) != i) r = m;
            else l = m;
        }
        D[buffer[r]] = i;
        Q[buffer[r]] = S[buffer[r]] = T;
        buffer.erase(buffer.begin() + r);
    }
    answer(S, D);
}

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