Submission #302271

#	Time	Username	Problem	Language	Result	Execution time	Memory
302271		UserIsUndefined	Cave (IOI13_cave)	C++14	100 / 100	499 ms	632 KiB

cave

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


using namespace std;



int DontTouch[5005];

int correctpos[5005];
int switchIconnectedto[5005];


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


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

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




        bool close = 0;

        int last = tryCombination(S);

        if (last == Door){
            close = 1;

            for (int i = 0 ; i < N ; i++){
                if (DontTouch[i] == false){
                    S[i] = 0;
                }
            }

        }


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


        while(low < high){




            int mid = (low + high)/2;

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

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

            int last = tryCombination(S);


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

            else {
                low = mid + 1;
            }

        }


        DontTouch[low] = true;
        S[low] = (!close);
        correctpos[low] = (!close);
        switchIconnectedto[low] = Door;


    }

    answer(correctpos, switchIconnectedto);


}

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