Submission #529009

#	Time	Username	Problem	Language	Result	Execution time	Memory
529009		lcs147	동굴 (IOI13_cave)	C++17	100 / 100	719 ms	580 KiB

cave

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

void exploreCave(int n) {
    vector<int>correct(n, -1), switch_door(n, -1);
    
    for(int i=0; i<n; i++) {
        vector<int>s = correct;
        for(int &x:s) if(x == -1) x = 1;
        int ret = tryCombination(s.data());

        int open = -1;
        if(ret == -1 || ret > i) {
            open = 1;
        } else {
            open = 0;
        }

        vector<int>dknow;
        for(int j=0; j<n; j++) {
            if(correct[j] == -1) {
                dknow.push_back(j);
            }
        }
        
        auto check = [&](int l, int r) {
            s = correct;
            for(int j=0; j<dknow.size(); j++) {
                int id = dknow[j];
                if(j < l || j > r) s[id] = !open;
                else s[id] = open;
            }
            ret = tryCombination(s.data());
            return ret == -1 || ret > i;
        };

        int l = 0, r = dknow.size()-1, id = -1;
        while(l <= r) {
            int m = (l+r)/2;
            if(check(l, m)) {
                id = m;
                r = m - 1;
            } else l = m + 1;
        }
        id = dknow[id];
        switch_door[id] = i;
        correct[id] = open;
    }
    answer(correct.data(), switch_door.data());
}

Compilation message (stderr)

cave.cpp: In lambda function:
cave.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             for(int j=0; j<dknow.size(); j++) {
      |                          ~^~~~~~~~~~~~~

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