Submission #395964

#	Time	Username	Problem	Language	Result	Execution time	Memory
395964		phathnv	Cave (IOI13_cave)	C++11	100 / 100	1049 ms	652 KiB

cave

#include "cave.h"

void exploreCave(int n) {
    int res[n], s[n], d[n];
    for(int i = 0; i < n; i++)
        res[i] = -1;
    for(int pos = 0; pos < n; pos++){
        for(int i = 0; i < n; i++)
            s[i] = (res[i] != -1? res[i] : 0);
        int trueVal = (tryCombination(s) == pos);
        int l = 0, r = n - 1;
        while (l < r){
            int mid = (l + r) >> 1;
            for(int i = 0; i < n; i++)
                if (res[i] != -1)
                    s[i] = res[i];
                else if (l <= i && i <= mid)
                    s[i] = trueVal;
                else
                    s[i] = trueVal ^ 1;
            if (tryCombination(s) != pos)
                r = mid;
            else
                l = mid + 1;
        }
        res[l] = trueVal;
        d[l] = pos;
    }
    answer(res, d);
}

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