Submission #508845

#	Time	Username	Problem	Language	Result	Execution time	Memory
508845		tabr	Cave (IOI13_cave)	C++17	100 / 100	560 ms	580 KiB

cave

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#include "cave.h"

void exploreCave(int n) {
    int a[5000] = {};
    int b[5000] = {};
    vector<int> c;
    for (int i = 0; i < n; i++) {
        c.emplace_back(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j : c) {
            a[j] = 0;
        }
        int k = 0;
        if (tryCombination(a) != i) {
            k = 1;
        }
        int lo = 0;
        int hi = n - i;
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            for (int j = 0; j < n - i; j++) {
                if (j < mid) {
                    a[c[j]] = k;
                } else {
                    a[c[j]] = k ^ 1;
                }
            }
            if (tryCombination(a) == i) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        a[c[lo]] = k ^ 1;
        b[c[lo]] = i;
        c.erase(c.begin() + lo);
    }
    assert(tryCombination(a) == -1);
    answer(a, b);
}

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