Submission #968925

#	Time	Username	Problem	Language	Result	Execution time	Memory
968925		sleepntsheep	Cave (IOI13_cave)	C11	100 / 100	649 ms	812 KiB

cave

#include "cave.h"

#define NN 5005

void exploreCave(int n) {
    static int s2d[NN], isknown[NN], correct[NN];
    for (int i = 0; i < n; ++i)
        isknown[i] = 0;

    for (int i = 0; i < n; ++i)
    {
        static int s[NN];

        for (int j = 0; j < n; ++j)
        {
            s[j] = 0;
            if (isknown[j])
                s[j] = correct[j];
        }

        int first, correct_;

        first = tryCombination(s);
        if (first == -1 || first > i)
            correct_ = 0;
        else 
            correct_ = 1;

        int lower = -1, upper = n;
        while (upper - lower > 1)
        {
            int mid = lower+(upper-lower)/2;
            for (int j = 0; j < n; ++j)
            {
                if (isknown[j])
                    continue;
                if (j <= mid)
                    s[j] = correct_;
                else
                    s[j] = correct_^1;
            }

            int first = tryCombination(s);
            if (first == -1 || first > i)
                upper = mid;
            else
                lower = mid;
        }

        int sw = upper;

        s2d[sw] = i;
        isknown[sw] = 1;
        //known[ko++] = sw;
        correct[sw] = correct_;
    }


    answer(correct, s2d);
    /* ... */
}

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