Submission #788667

#	Time	Username	Problem	Language	Result	Execution time	Memory
788667		borisAngelov	Cave (IOI13_cave)	C++17	12 / 100	274 ms	688 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5005;

int n;

int ans[maxn];
int val[maxn];
int connection[maxn];

int guess[maxn];

void exploreCave(int N)
{
    n = N;

    vector<int> switches;

    for (int i = 0; i < n; ++i)
    {
        switches.push_back(i);
    }

    for (int i = 0; i < n; ++i)
    {
        int curr_code = 1;

        for (int j = 0; j < n; ++j)
        {
            guess[j] = 1;
        }

        for (int j = 0; j < i; ++j)
        {
            guess[ans[j]] = val[ans[j]];
        }

        if (tryCombination(guess) == i)
        {
            curr_code = 0;
        }

        int l = 0;
        int r = switches.size() - 1;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            for (int j = 0; j < i; ++j)
            {
                guess[ans[j]] = val[ans[j]];
            }

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

            if (tryCombination(guess) == i)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        ans[i] = switches[l];

        val[switches[l]] = curr_code;

        switches.erase(switches.begin() + l);
    }

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

    answer(val, connection);
}

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