Submission #592734

#	Time	Username	Problem	Language	Result	Execution time	Memory
592734		DAleksa	동굴 (IOI13_cave)	C++17	100 / 100	203 ms	500 KiB

cave

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

using namespace std;

const int mxN = 5e3;

bool mark[mxN];

int N;
int Find(int l, int r, int finding, bool open, int S[]) {
    if(l == r) {
        if(!open) S[l] ^= 1;
        return l;
    }
    int mid = (l + r) >> 1;
    for(int i = l; i <= mid; i++) {
        if(mark[i]) continue;
        S[i] ^= 1;
    }
    bool open_left;
    int x = tryCombination(S);
    if(x == -1 || x > finding) open_left = true;
    else open_left = false;
    if(open ^ open_left) return Find(l, mid, finding, open_left, S);
    else return Find(mid + 1, r, finding, open_left, S);
}

void exploreCave(int n) {
    int S[n], D[n];
    for(int i = 0; i < n; i++) S[i] = 0;
    for(int finding = 0; finding < n; finding++) {
        bool open;
        int x = tryCombination(S);
        if(x == -1 || x > finding) open = true;
        else open = false;
        int fnd = Find(0, n - 1, finding, open, S);
        D[fnd] = finding;
        mark[fnd] = true;
    }
    answer(S, D);
}

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