Submission #783480

#	Time	Username	Problem	Language	Result	Execution time	Memory
783480		mindiyak	Cave (IOI13_cave)	C++14	100 / 100	628 ms	448 KiB

cave

#include "cave.h"
#include <vector>
#include <iostream>

using namespace std;

int createQuestion(int N,int connectedDoor[],int doorActive[],int left,int right,int active){
    int question[N];
    for(int i=0;i<N;i++){
        if(connectedDoor[i] != -1){
            question[i] = doorActive[i];
        }else if(left <= i and i <= right){
            question[i] = active;
        }else{
            question[i] = 1-active;
        }
    }
    return tryCombination(question);
}

void exploreCave(int N) {
    int doorActive[N],connectedDoor[N];
    for(int i=0;i<N;i++){
        doorActive[i]=0;
        connectedDoor[i] = -1;
    }


    for(int i=0;i<N;i++){
        int question[N];
        int active = 0;
        
        int val = createQuestion(N,connectedDoor,doorActive,0,N-1,1);
        if(val == -1 or val > i){
            active = 1;
        }

        int left=0,right=N-1;
        while(right > left){
            int mid = (left+right)>>1;
            // cout << "search " << left << " " << mid << " " << right << endl;
            int val = createQuestion(N,connectedDoor,doorActive,left,mid,active);
            if(val == -1 or val > i){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        // cout << "end " << i << " " << left << " " << right << endl << endl;

        doorActive[left]=active;
        connectedDoor[left] = i;
    }

    answer(doorActive,connectedDoor);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:30:13: warning: unused variable 'question' [-Wunused-variable]
   30 |         int question[N];
      |             ^~~~~~~~

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