Submission #769368

#	Time	Username	Problem	Language	Result	Execution time	Memory
769368		boris_mihov	Cave (IOI13_cave)	C++17	100 / 100	449 ms	692 KiB

cave

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

typedef long long llong;
const int MAXN = 5000 + 10;
const int INF = 1e9;

int ans[MAXN];
int con[MAXN];
int val[MAXN];
int guess[MAXN];
std::vector <int> switchs;
void exploreCave(int n) 
{
    switchs.resize(n);
    std::iota(switchs.begin(), switchs.end(), 0);

    for (int i = 0 ; i < n ; ++i)
    {
        int setTo = 1;
        std::fill(guess, guess + n, 1);
        for (int j = 0 ; j < i ; ++j)
        {
            guess[ans[j]] = val[ans[j]];
        }

        int res = tryCombination(guess);
        if (res == i)
        {
            setTo = 0;
        }

        int l = -1, r = switchs.size() - 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            std::fill(guess, guess + n, setTo ^ 1);
            for (int j = 0 ; j < i ; ++j)
            {
                guess[ans[j]] = val[ans[j]];
            }   

            for (int j = 0 ; j <= mid ; ++j)
            {
                guess[switchs[j]] = setTo;
            }

            res = tryCombination(guess);
            if (res == i) l = mid;
            else r = mid;
        }

        ans[i] = switchs[r];
        val[switchs[r]] = setTo;
        switchs.erase(switchs.begin() + r);
    }

    for (int i = 0 ; i < n ; ++i)
    {
        con[ans[i]] = i;
    }

    answer(val, con);
}

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