Submission #388365

#	Time	Username	Problem	Language	Result	Execution time	Memory
388365		Joshc	Cave (IOI13_cave)	C++11	100 / 100	563 ms	616 KiB

cave

#include "cave.h"
#include <vector>
using namespace std;

void exploreCave(int N) {
    int guess[5000], known[5000], door[5000];
    for (int i=0; i<N; i++) known[i] = -1;
    for (int i=0; i<N; i++) {
        vector<int> unknown;
        for (int i=0; i<N; i++) {
            if (known[i] != -1) guess[i] = known[i];
            else guess[i] = 0, unknown.push_back(i);
        }
        int cur = tryCombination(guess), t=0;
        if (cur == i) t = 1;
        while (unknown.size() > 1) {
            vector<int> a, b;
            for (int i=0; i<unknown.size(); i++) {
                if (i*2<unknown.size()) a.push_back(unknown[i]);
                else b.push_back(unknown[i]);
            }
            unknown.clear();
            for (int i : a) guess[i] = t;
            for (int i : b) guess[i] = 1-t;
            int z = tryCombination(guess);
            if (z > i || z == -1) {
                for (int i : a) unknown.push_back(i);
            } else {
                for (int i : b) unknown.push_back(i);
            }
        }
        known[unknown[0]] = t;
        door[unknown[0]] = i; 
    }
    answer(known, door);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:18:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |             for (int i=0; i<unknown.size(); i++) {
      |                           ~^~~~~~~~~~~~~~~
cave.cpp:19:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |                 if (i*2<unknown.size()) a.push_back(unknown[i]);
      |                     ~~~^~~~~~~~~~~~~~~

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