Submission #1313535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313535		orgiloogii	동굴 (IOI13_cave)	C++20	100 / 100	320 ms	504 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tryCombination(int S[]);
void answer(int S[], int D[]);

void exploreCave(int n) {
    int res[n];
    int state[n];
    for (int i = 0;i < n;i++) {
        state[i] = -1;
        res[i] = -1;
    }
    int temp[n];
    for (int i = 0;i < n;i++) {
        int onstate = -1;
        for (int j = 0;j < n;j++) {
            if (state[j] == -1) temp[j] = 0;
            else temp[j] = state[j];
        }
        int block = tryCombination(temp);
        if (block > i || block == -1) {
            onstate = 0;
        }
        else {
            onstate = 1;
        }
        int l = -1, r = n;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            for (int j = 0;j <= mid;j++) {
                if (state[j] == -1) temp[j] = onstate;
                else temp[j] = state[j];
            }
            for (int j = mid + 1;j < n;j++) {
                if (state[j] == -1) temp[j] = 1 - onstate;
                else temp[j] = state[j];
            }
            block = tryCombination(temp);
            if (block > i || block == -1) {
                r = mid;
            }
            else {
                l = mid;
            }
        }
        state[r] = onstate;
        res[r] = i;
    }
    answer(state, res);
}

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