Submission #556259

#	Time	Username	Problem	Language	Result	Execution time	Memory
556259		Zanite	Cave (IOI13_cave)	C++17	100 / 100	370 ms	468 KiB

cave

#include "cave.h"

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

void exploreCave(int N) {
    int toggle[N], correspondence[N];
    bool answered[N];

    memset(toggle, 0, sizeof(toggle));
    memset(correspondence, 0, sizeof(correspondence));
    memset(answered, 0, sizeof(answered));

    for (int i = 0; i < N; i++) {
        // check the correct position of the switch that handles the i-th door
        int correctPos = 0;
        for (int s = 0; s < N; s++) {
            if (!answered[s]) {toggle[s] = 0;}
        }
        if (tryCombination(toggle) == i) {
            for (int s = 0; s < N; s++) {
                if (!answered[s]) {toggle[s] = 1;}
            }
            correctPos = 1;
        }
        
        // search which switch connects to the i-th door
        deque<int> guesses;
        for (int s = 0; s < N; s++) {
            if (!answered[s]) {guesses.push_back(s);}
        }
        while (guesses.size() > 1) {
            // guess the left half of deque
            bool removeLeft = 0;
            for (int g = 0; g < (guesses.size() >> 1); g++) {
                toggle[guesses[g]] = 1 - correctPos;
            }
            if (tryCombination(toggle) != i) {
                removeLeft = 1;
            }
            for (int g = 0; g < (guesses.size() >> 1); g++) {
                toggle[guesses[g]] = correctPos;
            }

            int bound = guesses.size();
            if (removeLeft) {
                for (int g = 0; g < (bound >> 1); g++) {
                    guesses.pop_front();
                }   
            } else {
                for (int g = (bound >> 1); g < bound; g++) {
                    guesses.pop_back();
                }
            }
        }
        correspondence[guesses[0]] = i;
        answered[guesses[0]] = 1;
    }

    answer(toggle, correspondence);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:35:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for (int g = 0; g < (guesses.size() >> 1); g++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
cave.cpp:41:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (int g = 0; g < (guesses.size() >> 1); g++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~

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