Submission #1013038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013038		aufan	Cave (IOI13_cave)	C++17	100 / 100	264 ms	856 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

void exploreCave(int n) {
    int s[n], d[n];
    for (int i = 0; i < n; i++) {
        s[i] = 0;
        d[i] = -1;
    }

    for (int i = 0; i < n; i++) {
        int ret = tryCombination(s);
        if (ret == i) {
            // brrt 1
            vector<int> left;
            for (int j = 0; j < n; j++) if (d[j] == -1) left.push_back(j);

            int m = (int)left.size(), lf = 0, rg = m - 1, pos = -1;
            while (lf <= rg) {
                int md = (lf + rg) / 2;

                for (int j = 0; j < m; j++) {
                    if (j <= md) {
                        s[left[j]] = 1;
                    } else {
                        s[left[j]] = 0;
                    }
                }

                int ret = tryCombination(s);
                if (ret == i) {
                    lf = md + 1;
                } else {
                    pos = md;
                    rg = md - 1;
                }
            }

            for (int j = 0; j < m; j++) s[left[j]] = 0;
            s[left[pos]] = 1;
            d[left[pos]] = i;
        } else {    
            // brrt 0
            vector<int> left;
            for (int j = 0; j < n; j++) if (d[j] == -1) left.push_back(j);

            int m = (int)left.size(), lf = 0, rg = m - 1, pos = -1;
            while (lf <= rg) {
                int md = (lf + rg) / 2;

                for (int j = 0; j < m; j++) {
                    if (j <= md) {
                        s[left[j]] = 0;
                    } else {
                        s[left[j]] = 1;
                    }
                }

                int ret = tryCombination(s);
                if (ret == i) {
                    lf = md + 1;
                } else {
                    pos = md;
                    rg = md - 1;
                }
            }

            for (int j = 0; j < m; j++) s[left[j]] = 0;
            s[left[pos]] = 0;
            d[left[pos]] = i;
        }
    }

    answer(s, d);
}

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