Submission #587405

#	Time	Username	Problem	Language	Result	Execution time	Memory
587405		usuyus	Cave (IOI13_cave)	C++14	100 / 100	622 ms	588 KiB

cave

#include "cave.h"

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

const int MX = 5000;
int N;
int query[MX], open[MX], which[MX];


void exploreCave(int _N) {
    N = _N;
    
    memset(open, -1, sizeof(open));
    memset(which, -1, sizeof(which));

    for (int i=0; i<N; i++) {
        // cout << i << " ---" << endl;

        for (int j=0; j<N; j++) {
            if (open[j] != -1) query[j] = open[j];
            else query[j] = 0;
        }

        int door = tryCombination(query);
        int open_first = (door == i);
        // for (int i=0; i<N; i++) cout << query[i];
        // cout << " => " << door << endl;
        // cout << open_first << endl;

        vector<int> idx;
        for (int j=0; j<N; j++) {
            if (open[j] == -1) idx.push_back(j); // cout << j << ' ';
        }
        // cout << endl;
        int k = idx.size();

        int l = 0, r = k;
        while ((r-l) > 1) {
            int m = (l + r) / 2;

            // cout << l << ' ' << r << " -- " << m << endl;

            for (int j=0; j<l; j++) query[idx[j]] = open_first;
            for (int j=l; j<m; j++) query[idx[j]] = !open_first;
            for (int j=m; j<k; j++) query[idx[j]] = open_first;

            int door = tryCombination(query);
            // for (int i=0; i<N; i++) cout << query[i];
            // cout << " => " << door << endl;

            if (door == i) r = m;
            else l = m;
        }

        // cout << idx[l] << endl << endl;

        which[idx[l]] = i;
        open[idx[l]] = open_first;
    }

    answer(open, which);
}

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