Submission #536614

#	Time	Username	Problem	Language	Result	Execution time	Memory
536614		timreizin	Cave (IOI13_cave)	C++17	100 / 100	218 ms	476 KiB

cave

#include "cave.h"
#include <vector>
#include <numeric>
#include <iostream>

using namespace std;

void exploreCave(int n)
{
    int s[n], d[n];
    vector<int> left(n);
    iota(left.begin(), left.end(), 0);
    for (int i = 0; i < n; ++i)
    {
        for (int j : left) s[j] = 0;
        int res = tryCombination(s);
        if (res == -1) res = n + 1;
        if (res >= i + 1)
        {
            int l = 0, r = (int)left.size() - 1;
            while (l != r)
            {
                int m = (l + r) >> 1;
                for (int j = l; j <= r; ++j) s[left[j]] = j > m;
                res = tryCombination(s);
                if (res == -1) res = n + 1;
                if (res >= i + 1) r = m;
                else l = m + 1;
            }
            d[i] = left[l];
            left.erase(left.begin() + l);
            s[d[i]] = 0;
        }
        else
        {
            int l = 0, r = (int)left.size() - 1;
            while (l != r)
            {
                int m = (l + r) >> 1;
                for (int j = l; j <= r; ++j) s[left[j]] = j <= m;
                res = tryCombination(s);
                if (res == -1) res = n + 1;
                if (res >= i + 1) r = m;
                else l = m + 1;
            }
            d[i] = left[l];
            left.erase(left.begin() + l);
            s[d[i]] = 1;
        }
    }
    int nd[n];
    for (int j = 0; j < n; ++j) nd[d[j]] = j;
    answer(s, nd);
}

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