Submission #824228

#	Time	Username	Problem	Language	Result	Execution time	Memory
824228		SoulKnight	Cave (IOI13_cave)	C++17	100 / 100	175 ms	748 KiB

cave

#include "cave.h"
#include <iostream>
using namespace std;

#define ll long long
#define ln '\n'

int n;
int s[5005], d[5005], t[5005], orig[5005], ans[5005];
bool hasOpen[5005];


int find(int door, int correct){
    // find which switch door i corresponds to
    // cout << "enter" << ln;
    // cout << door << ' ' << correct << ln;
    int l = 0, r = n-1;
    while (l < r){
        int mid = (l + r) / 2;
        for (int i = l; i <= r; i++) orig[i] = s[i];
        for (int i = l; i <= mid; i++) {
            if (hasOpen[i]) continue;
            s[i] = 1 - correct;
        }
        for (int i = mid+1; i <= r; i++){
            if (hasOpen[i]) continue;
            s[i] = correct;
        }
        // for (int i = 0; i < n; i++) cout << s[i] << ' ';
        // cout << ln;
        int res = tryCombination(s);
        if (res == -1) res = n;
        for (int i = l; i <= r; i++) s[i] = orig[i];

        if (res == door) r = mid;
        else l = mid+1;

    }
    // cout << "door " << door << " corresponds to switch " << l << ln;
    s[l] = correct; hasOpen[l] = 1;
    ans[l] = door;
    return d[door]=l;
}

void exploreCave(int N) {
    int idx = 0, correct;
    n = N;
    int glit = 0;

    while (idx < N){
        // cout << idx << ln;
        // for (int i = 0; i < n; i++) cout << s[i] << ' ';
        // cout << ln;
        int res = tryCombination(s);
        if (res == -1) res = n;
        if (res == idx) {
            correct = 1;
            find(idx, correct);
            idx++;
        }
        else {
            correct = 0;
            for (; idx < res; idx++) find(idx, correct);
        }
    }

    answer(s, ans);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:48:9: warning: unused variable 'glit' [-Wunused-variable]
   48 |     int glit = 0;
      |         ^~~~

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