Submission #642782

#	Time	Username	Problem	Language	Result	Execution time	Memory
642782		Alexandruabcde	Cave (IOI13_cave)	C++14	100 / 100	1291 ms	552 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 5002;

int know[NMAX]; ///know[i] = pozitia buna a switchului i
int who[NMAX]; ///who[i] = switch-ul corespunzator usii i
int door[NMAX]; ///door[i] = usa corespunzatoare switchului i

int M;

int aux[NMAX];

int Check (int ask, int value, int cnt) {
    for (int i = 0; i < M; ++ i )
        aux[i] = -1;

    for (int i = 0; i < ask; ++ i )
        aux[who[i]] = know[who[i]];

    for (int i = 0; i <= cnt; ++ i )
        if (aux[i] == -1) aux[i] = value;

    for (int i = cnt+1; i < M; ++ i )
        if (aux[i] == -1) aux[i] = 1 - value;

    return tryCombination(aux);
}

void exploreCave(int N) {
    M = N;
    for (int i = 0; i < N; ++ i )
        who[i] = know[i] = -1;

    for (int i = 0; i < N; ++ i ) {
        int switch_state = 1;
        int verif = Check(i, 0, N-1);
        if (verif == -1 || verif > i) switch_state = 0;

        int st = 0, dr = N - 1;
        int which_switch = N;

        while (st <= dr) {
            int mij = (st + dr) / 2;

            int verif = Check(i, switch_state, mij);

            if (verif == -1 || verif > i) {
                which_switch = mij;
                dr = mij - 1;
            }
            else st = mij + 1;
        }

        who[i] = which_switch;
        know[which_switch] = switch_state;
    }

    for (int i = 0; i < N; ++ i )
        door[who[i]] = i;

    return answer(know, door);

}

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