Submission #761499

#	Time	Username	Problem	Language	Result	Execution time	Memory
761499		Noble_Mushtak	Cave (IOI13_cave)	C++14	100 / 100	181 ms	464 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(num i = a; i < (b); ++i)
#define REPI(t, n) for (num t = 0; t < n; ++t)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef TESTING
#define DEBUG(...) __VA_ARGS__
#else
#define DEBUG(...)
#endif

void exploreCave(int N) {
    vector<int> S(N);
    REPI(i, N) S[i] = 0;
    auto curClosestDoor = tryCombination(S.data());
    vector<int> D(N, -1);
    REPI(i, N) {
        int lo = 0, hi = N-1;
        while (lo < hi) {
            int mid = (lo+hi)/2;
            
            rep(j, lo, mid+1) {
                if (D[j] == -1) S[j] = 1;
            }
            auto newClosestDoor = tryCombination(S.data());
            rep(j, lo, mid+1) {
                if (D[j] == -1) S[j] = 0;
            }
            
            if ((newClosestDoor == i) ^ (curClosestDoor == i)) hi = mid;
            else lo = mid+1;
        }
        D[lo] = i;
        if (curClosestDoor == i) {
            S[lo] = 1;
            curClosestDoor = tryCombination(S.data());
        }
    }
    answer(S.data(), D.data());
}

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