Submission #668054

#	Time	Username	Problem	Language	Result	Execution time	Memory
668054		finn__	Cave (IOI13_cave)	C++17	100 / 100	525 ms	460 KiB

cave

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

void exploreCave(int n)
{
    int p[n], comb[n];
    vector<int> x(n); // switches to be determined
    for (size_t i = 0; i < n; i++)
        x[i] = i;

    for (size_t i = 0; i < n; i++)
    {
        // First determine wheter the next switch must be on or off.
        for (size_t j = 0; j < n - i; j++)
            comb[x[j]] = 0;
        bool next_on = (tryCombination(comb) == i);

        size_t a = 0, b = n - i - 1;

        while (a < b)
        {
            size_t mid = (a + b) / 2;

            for (size_t j = 0; j <= mid; j++)
                comb[x[j]] = !next_on;
            for (size_t j = mid + 1; j < n - i; j++)
                comb[x[j]] = next_on;

            if (tryCombination(comb) == i)
                b = mid;
            else
                a = mid + 1;
        }

        p[x[a]] = i;
        comb[x[a]] = next_on;
        x.erase(x.begin() + a);
    }

    answer(comb, p);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:9:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
cave.cpp:12:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
cave.cpp:17:46: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         bool next_on = (tryCombination(comb) == i);
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~
cave.cpp:30:38: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             if (tryCombination(comb) == i)
      |                 ~~~~~~~~~~~~~~~~~~~~~^~~~

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