Submission #1303481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303481		the_commando_x	Cave (IOI13_cave)	C++17	100 / 100	132 ms	548 KiB

cave

#include "cave.h"
#include <vector>
#include <algorithm>

void exploreCave(int N)
{
    int S[5000], D[5000];

    std::vector<int> notAssigned;
    notAssigned.reserve(5000);

    for (int i = 0; i < N; ++i)
        notAssigned.push_back(i);

    for (int d = 0; d < N; ++d)
    {
        int curCfg[5000];
        for (int i = 0; i < N; ++i)
            curCfg[i] = S[i];

        for (int sw : notAssigned)
            curCfg[sw] = 0;

        int res = tryCombination(curCfg);

        int switchState;
        if (res == -1 || res > d)
            switchState = 0;
        else
            switchState = 1;

        std::vector<int> cand = notAssigned;

        while (cand.size() > 1)
        {
            int mid = cand.size() / 2;

            for (int i = 0; i < N; ++i)
                curCfg[i] = S[i];

            for (int i = 0; i < cand.size(); ++i)
                if (i < mid)
                    curCfg[cand[i]] = switchState;
                else
                    curCfg[cand[i]] = 1 - switchState;

            res = tryCombination(curCfg);

            if (res == -1 || res > d)
                cand.resize(mid);
            else
                cand.erase(cand.begin(), cand.begin() + mid);
        }

        int sw = cand[0];
        S[sw] = switchState, D[sw] = d;

        notAssigned.erase(find(notAssigned.begin(), notAssigned.end(), sw));
    }

    answer(S, D);
}

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