Submission #785553

#	Time	Username	Problem	Language	Result	Execution time	Memory
785553		Alfraganus	Cave (IOI13_cave)	C++17	12 / 100	431 ms	436 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;
    }
}

bool check(vector<int> &used, int l, int r){
    for(int i = l; i <= r; i ++){
        if(used[i] == -1){
            return false;
        }
    }
    return true;
}

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, x = 0;
        while (l < r)
        {
            int m = (l + r) >> 1;
            FillWithZero(a, used, l, m, flag);
            if(check(used, l, m)){
                // printf("%d", l);
                // printf(" ");
                // printf("%d", m);
                // printf("\n");
                l = m + 1;
                continue;
            }
            for (int i = 0; i < n; i++)
                ra[i] = a[i];
            // for(int i = 0; i < n; i ++){
            //     printf("%d", ra[i]);
            //     printf(" ");
            // }
            // printf("\n");
            k = tryCombination(ra);
            x |= 1;
            if (k == j)
            {
                if (flag)
                {
                    l = m + 1;
                    continue;
                }
                FillWithZero(a, used, m + 1, r, flag);
                if (check(used, m + 1, r))
                {
                    // printf("%d", m + 1);
                    // printf(" ");
                    // printf("%d", r);
                    // printf("\n");
                    r = m;
                    continue;
                }
                for (int i = 0; i < n; i++)
                    ra[i] = a[i];
                // for (int i = 0; i < n; i++)
                // {
                //     printf("%d", ra[i]);
                //     printf(" ");
                // }
                // printf("\n");
                k = tryCombination(ra);
                x |= 1;
                if (k == j)
                    flag = 1;
                else
                    l = m + 1;
            }
            else
                r = m;
        }
        d[l] = j;
        used[l] = flag;
        if(x == 0){
            for (int i = 0; i < n; i++)
                ra[i] = used[i];
            if(tryCombination(ra) != -1)used[l] = flag ^ 1;
        }
        // for (int i = 0; i < n; i++)
        // {
        //     printf("%d", d[i]);
        //     printf(" ");
        // }
        // printf("\n");
        // for (int i = 0; i < n; i++)
        // {
        //     printf("%d", used[i]);
        //     printf(" ");
        // }
        // printf("\n");
    }
    for (int i = 0; i < n; i++)
        ra[i] = used[i];
    answer(ra, d);
}

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