Submission #668052

#	Time	Username	Problem	Language	Result	Execution time	Memory
668052		finn__	Cave (IOI13_cave)	C++17	13 / 100	796 ms	392 KiB

cave

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

void exploreCave(int n)
{
    if (n == 1)
    {
        int p = 0, comb = (int)(tryCombination({0}) == 0);
        answer(&comb, &p);
    }

    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 i = 0; i < n - i; i++)
            comb[x[i]] = 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;

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

            for (size_t j = 0; j <= mid; j++)
                comb[x[j]] = next_on;
        }

        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:15:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
cave.cpp:18:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
cave.cpp:23:46: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         bool next_on = (tryCombination(comb) == i);
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~
cave.cpp:33:38: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             if (tryCombination(comb) == i)
      |                 ~~~~~~~~~~~~~~~~~~~~~^~~~

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