Submission #785501

#	Time	Username	Problem	Language	Result	Execution time	Memory
785501		Alfraganus	Cave (IOI13_cave)	C++17	51 / 100	414 ms	396 KiB

cave

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

void FillWithZero(vector<int> &a, vector<int> &used, int l, int r, bool flag)
{
    for (int i = l; i <= r; i++)
    {
        if (used[i] != -1)
            a[i] = used[i];
        else
            a[i] = flag;
    }
    for (int i = 0; i < l; i++)
    {
        if (used[i] != -1)
            a[i] = used[i];
        else
            a[i] = -1;
    }
    for (int i = r + 1; i < (int)a.size(); i++)
    {
        if (used[i] != -1)
            a[i] = used[i];
        else
            a[i] = -1;
    }
}

void exploreCave(int n)
{
    vector<int> a(n), used(n, -1);
    int ra[n], k, d[n];
    for (int j = 0; j < n; j++)
    {
        int l = 0, r = n - 1;
        bool flag = 0;
        while (l < r)
        {
            int m = (l + r) >> 1;
            FillWithZero(a, used, l, m, flag);
            for (int i = 0; i < n; i++)
                ra[i] = a[i];
            k = tryCombination(ra);
            if (k == j)
            {
                if (flag)
                {
                    l = m + 1;
                    continue;
                }
                FillWithZero(a, used, m + 1, r, flag);
                for (int i = 0; i < n; i++)
                    ra[i] = a[i];
                k = tryCombination(ra);
                if (k == j)
                    flag = 1;
                else
                    l = m + 1;
            }
            else
                r = m;
        }
        d[l] = j;
        used[l] = flag;
    }
    for (int i = 0; i < n; i++)
        ra[i] = used[i];
    answer(ra, d);
}

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