Submission #578824

#	Time	Username	Problem	Language	Result	Execution time	Memory
578824		jack715	Cave (IOI13_cave)	C++14	100 / 100	161 ms	428 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;


void exploreCave(int N) {
    int n;
    n = N;
    int comb[n], door[n];
    for (int i = 0; i < n; i++)
        comb[i] = 0, door[i] = -1;

    int now, ret;
    for (int i = 0; i < n; i++) {
        int l = 0, r = n-1;
        now = (tryCombination(comb) == i ? 1 : 0);
        while (l < r) {
            // cout << l << ' ';
            int mid = (l + r) / 2;
            for (int j = l; j <= mid; j++) {
                if (door[j] != -1) continue;
                comb[j] = 1-comb[j];
            } 
            ret = tryCombination(comb);
            if ((ret == i && !now) || (ret != i && now)) {
                r = mid, now = 1-now;
            } else {
                l = mid+1;
            }
        }
        // cout << '\n';
        door[l] = i;
        // ret = tryCombination(comb);
        // cout << ret << ' ';
        if (now) comb[l] = 1-comb[l];
    }
    // cout << '\n';
    answer(comb, door);
}

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