Submission #1231955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231955		badge881	Cave (IOI13_cave)	C++20	100 / 100	425 ms	516 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

void exploreCave(int N)
{
    vector<int> S(N, 0), D(N, 0);
    vector<bool> known(N, false);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            if (!known[j])
                S[j] = 0;
        int res = tryCombination(S.data());
        bool valTry = (res == i ? 1 : 0);
        int left = 0, right = N, ans = -1;
        while (left < right - 1)
        {
            int mid = (left + right) / 2;
            for (int j = 0; j < N; j++)
            {
                if (!known[j])
                {
                    if (j < mid)
                        S[j] = valTry;
                    else
                        S[j] = valTry ^ 1;
                }
            }
            int res = tryCombination(S.data());
            if (res == i)
                ans = mid, left = mid;
            else
                right = mid;
        }
        known[left] = 1;
        S[left] = valTry;
        D[left] = i;
    }
    answer(S.data(), D.data());
    return;
}

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