Submission #416391

#	Time	Username	Problem	Language	Result	Execution time	Memory
416391		mjhmjh1104	Cave (IOI13_cave)	C++17	100 / 100	672 ms	572 KiB

cave

#include "cave.h"
#include <vector>
using namespace std;

int tmp, s[5006], t[5006];

void exploreCave(int n) {
    vector<int> empty_list;
    for (int i = 0; i < n; i++) empty_list.push_back(i);
    for (int i = 0; i < n; i++) {
        for (int i = 0; i < (int)empty_list.size(); i++) s[empty_list[i]] = 0;
        tmp = tryCombination(s);
        bool zero = (tmp == -1) || (tmp >= i + 1);
        if (zero) {
            int l = 0, r = (int)empty_list.size() - 1;
            while (l < r) {
                int m = (l + r) / 2;
                for (int i = 0; i <= m; i++) s[empty_list[i]] = 0;
                for (int i = m + 1; i <= r; i++) s[empty_list[i]] = 1;
                tmp = tryCombination(s);
                if (tmp == -1 || tmp >= i + 1) r = m;
                else l = m + 1;
            }
            s[empty_list[l]] = 0;
            t[empty_list[l]] = i;
            empty_list.erase(empty_list.begin() + l);
        } else {
            int l = 0, r = (int)empty_list.size() - 1;
            while (l < r) {
                int m = (l + r) / 2;
                for (int i = 0; i <= m; i++) s[empty_list[i]] = 1;
                for (int i = m + 1; i <= r; i++) s[empty_list[i]] = 0;
                tmp = tryCombination(s);
                if (tmp == -1 || tmp >= i + 1) r = m;
                else l = m + 1;
            }
            s[empty_list[l]] = 1;
            t[empty_list[l]] = i;
            empty_list.erase(empty_list.begin() + l);
        }
    }
    answer(s, t);
}

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