Submission #1304900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304900		kaloyan	Cave (IOI13_cave)	C++20	100 / 100	459 ms	532 KiB

cave

#include "cave.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

const int MAXN = 5000;

int n;
int answered[MAXN];
int bind[MAXN];
int lever[MAXN];

int tryCombination(int S[]);

void answer(int S[], int D[]);

void flip(int arr[], int idx)
{
    for(int i = 0 ; i <= idx ; ++i)
    {
        if(answered[i])
        {
            continue;
        }

        arr[i] ^= 1;
    }
}

bool f(int doorIdx, bool wasClosed, int leverIdx)
{
    flip(lever, leverIdx);
    int res = tryCombination(lever);
    flip(lever, leverIdx);

    if(wasClosed)
    {
        return res != doorIdx;
    }
    else
    {
        return res == doorIdx;
    }
}

void exploreCave(int N)
{
    n = N;
    std::fill(answered, answered + n, 0);
    std::fill(lever, lever + n, 0);

    for(int i = 0 ; i < n ; ++i)
    {
        bool isClosed = (tryCombination(lever) == i);

        int l = -1, r = n - 1;
        while(l + 1 < r)
        {
            int mid = (l + r) / 2;
            if(!f(i, isClosed, mid)) l = mid;
            else r = mid;
        }

        //std::cout << i << " " << r << "\n";

        answered[r] = 1;
        bind[r] = i;
        
        if(isClosed)
        {
            lever[r] ^= 1;
        }
    }

    answer(lever, bind);
}

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