Submission #787594

#	Time	Username	Problem	Language	Result	Execution time	Memory
787594		drdilyor	Cave (IOI13_cave)	C++17	100 / 100	525 ms	468 KiB

cave

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

void exploreCave(int n) {
    vector<int> door_of(n, -1);
    vector<int> correct(n, -1);
    for (int i = 0; i < n; i++) {
        
        vector<int> cur(n);
        for (int i = 0; i < n; i++) {
            if (door_of[i] == -1) {
                cur[i] = 1;
            } else {
                cur[i] = correct[i];
            }
        }

        int curcorrect = 0;
        if (tryCombination(cur.data()) == i) {
            curcorrect = 0;
        } else {
            curcorrect = 1;
        }


        int l = -1, r = n-1;
        while (l < r-1) {
            int mid = (l + r) / 2;
            vector<int> comb(n);
            for (int j = 0; j < n;j++) {
                if (door_of[j] == -1) {
                    comb[j] = curcorrect ^ (j <= mid);
                } else {
                    comb[j] = correct[j];
                }
            }
            if (tryCombination(comb.data()) == i) {
                r = mid;
            } else l = mid;
        }
        correct[r] = curcorrect;
        door_of[r] = i;
    }
    answer(correct.data(),door_of.data());
}

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