Submission #1136817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136817		gustavo_d	Cave (IOI13_cave)	C++17	100 / 100	361 ms	528 KiB

cave

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

void exploreCave(int n) {
    int door_of_switch[n], switch_pos_ans[n];
    for (int i=0; i<n; i++) switch_pos_ans[i] = -1; // unknown

    for (int d=0; d<n; d++) {
        int switch_pos[n];
        
        int open_pos = -1;
        for (int i=0; i<n; i++) {
            if (switch_pos_ans[i] != -1) switch_pos[i] = switch_pos_ans[i];
            else switch_pos[i] = 1;
        }
        int first_closed = tryCombination(switch_pos); // -1 if all open
        if (first_closed == -1) first_closed = n;
        if (first_closed > d) open_pos = 1;
        else open_pos = 0;

        // for (int i=0; i<n; i++) cout << switch_pos[i] << ' ';
        // cout << endl;
        // cout << "Para " << d << ':' << open_pos << '\n';

        int l = 0, r=n-1; int s = -1;
        while (l <= r) {
            int m = (l + r) / 2;

            for (int i=0; i<n; i++) {
                if (switch_pos_ans[i] != -1) switch_pos[i] = switch_pos_ans[i];
                else if (i <= m) switch_pos[i] = open_pos;
                else switch_pos[i] = (!open_pos);
            }

            int first_closed = tryCombination(switch_pos); // -1 if all open
            if (first_closed == -1) first_closed = n;

            if (first_closed > d) {
                s = m;
                r = m-1;
            } else l = m+1;
        }
        // cout << s << endl;
        door_of_switch[s] = d;
        switch_pos_ans[s] = open_pos;
    }

    answer(switch_pos_ans, door_of_switch);
}

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