제출 #539429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
539429		joshualiu555	동굴 (IOI13_cave)	C++17	100 / 100	373 ms	556 KiB

cave

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

using namespace std;

const int INF = 5005;

#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define mem(a, x) memset(a, x, sizeof(a))

int s[INF], d[INF];
bool done[INF];

void exploreCave(int n) {
    FOR(i, 0, n - 1) {
        FOR(j, 0, n - 1) {
            if (!done[j]) s[j] = 1;
        }
        int closed = tryCombination(s);
        bool up = closed > i || closed == -1;
        FOR(j, 0, n - 1) {
            if (!done[j]) s[j] = !up;
        }

        int pos = -1;
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            FOR(j, l, m) {
                if (!done[j]) s[j] = up;
            }
            closed = tryCombination(s);
            FOR(j, l, m) {
                if (!done[j]) s[j] = !up;
            }
            if (closed > i || closed == -1) {
                pos = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        done[pos] = true;
        s[pos] = up;
        d[pos] = i;
    }

    answer(s, d);
}

/*
 * 70,000 queries = 5,000 * log2(5,000)
 * O(NlogN)
 * Once you solve a door in order, query it correctly
 * so it basically doesn't exist anymore.
 *
 * Subtask 1: Just try all 1 or all 0 to find the correct
 * switch orientation
 * Subtask 2: Split half one into all correct and the other
 * into all wrong. If half one opens, that's the new range.
 * If half one doesn't, half two is the new range.
 *
 * Combine these two subtasks to get the final answer
*/

//

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