제출 #761498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
761498		Noble_Mushtak	동굴 (IOI13_cave)	C++14	0 / 100	2 ms	340 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: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24