Submission #197672

#	Time	Username	Problem	Language	Result	Execution time	Memory
197672		joylintp	Cave (IOI13_cave)	C++17	100 / 100	1287 ms	512 KiB

cave

#include"cave.h"
#include<bits/stdc++.h>

using namespace std;

void exploreCave(int n)
{
    int sta[5000] = {}, dor[5000] = {};
    for (int tar = 0; tar < n; tar++)
    {
        int ask[5000];
        for (int i = 0; i < 5000; i++)
            if (sta[i])
                ask[i] = sta[i] - 1;
            else
                ask[i] = 1;
        int ret = tryCombination(ask);

        bool suc;
        if (ret == -1 || ret > tar)
            suc = true;
        else
            suc = false;

        int l = 0, r = n - 1;
        while (l != r)
        {
            int m = (l + r) / 2;
            for (int i = 0; i < n; i++)
                if (sta[i])
                    ask[i] = sta[i] - 1;
                else if (l <= i && i <= m)
                    ask[i] = suc;
                else
                    ask[i] = !suc;

            ret = tryCombination(ask);

            if (ret == -1 || ret > tar)
                r = m;
            else
                l = m + 1;
        }
        sta[l] = suc + 1;
        dor[l] = tar;
    }
    for (int i = 0; i < n; i++)
        sta[i]--;
    answer(sta, dor);
}

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