Submission #1231969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231969		kaltspielerhy	Cave (IOI13_cave)	C++20	0 / 100	1 ms	324 KiB

cave

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

void exploreCave(int N) {
    int result[N];
    int seen[N];
    fill(result, result+N, -1);
    fill(seen, seen+N, -1);

    for (int iDoor = 0; iDoor < N; iDoor++) {
        int list[N];
        for (int iVal = 0; iVal < N; iVal++) {
            if (seen[iVal] == -1) list[iVal] = 0;
            else list[iVal] = seen[iVal];
        }

        int zero = tryCombination(list);
        int num;
        if (zero > iDoor || zero == -1) {
            num = 0;
            for (int iVal = 0; iVal < N; iVal++) {
                if (seen[iVal] == -1) list[iVal] = 1;
                else list[iVal] = seen[iVal];
            }
        }
        else {
            num = 1;
        }

        int deb = 0, fin = N-1;
        while (deb <= fin) {
            int mid = (deb+fin)/2;

            for (int i = deb; i <= mid; i++) {
                if (seen[i] == -1) list[i] = num;
            }

            int result = tryCombination(list);
            if (result > iDoor || result == -1) {
                fin = mid;
                for (int i = deb; i <= mid; i++) {
                    if (seen[i] == -1) list[i] = (num+1)%2;
                }
            }
            else {
                deb = mid+1;
            }
        }

        seen[deb] = num;
        result[iDoor] = deb;
    }

    answer(seen, result);
}

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