Submission #302120

#	Time	Username	Problem	Language	Result	Execution time	Memory
302120		UserIsUndefined	Cave (IOI13_cave)	C++14	0 / 100	49 ms	584 KiB

cave

#include "cave.h"

#include<bits/stdc++.h>


using namespace std;


bool visited[5005];

int doorIisOpendBy[5005];
int c[5005];


void exploreCave(int N) {
    int S[N];




    for (int i = 0 ; i < N ; i++){

        for (int j = 0 ; j < N ; j++){
            if (visited[j] == false){
                S[j] = 1;
            }
        }

        bool close = 0;

        int last = tryCombination(S);

        if (last == i){
            close = 1;
            for (int j = 0 ; j < N ; j++){
                if (visited[j] == false){
                    S[j] = 0;
                }
            }
        }


        int low = 0;
        int high = N - 1;


        while(low < high){
            int mid = (low + high)/2;

            for (int j = low ; j <= mid ; j++){
                if (visited[j] == false){
                    S[j] = close;
                }
            }

            for (int j = mid + 1 ; j <= high ; j++){
                if (visited[j] == false){
                    S[j] = (!close);
                }
            }

            last = tryCombination(S);

            if (last == i){
                high = mid;
            }

            else {
                low = mid + 1;
            }

        }



        visited[low] = true;
        doorIisOpendBy[low] = i;
        c[low] = (!close);






    }


    answer(c , doorIisOpendBy);



}

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