Submission #167356

#	Time	Username	Problem	Language	Result	Execution time	Memory
167356		DavidDamian	Cave (IOI13_cave)	C++11	100 / 100	453 ms	572 KiB

cave

#include "cave.h"
///Binary Search
///Determine the position of switch-door
int temp[5005];
int s[5005];
int d[5005];
void turn_on_off(int N,int L,int R,int op) ///Turns on/off the switches in a range
{
    for(int i=L;i<=R;i++){
        if(s[i]==-1)
            temp[i]=op;
        else
            temp[i]=s[i]; //If the door is already open, we
    }
}
bool door_changed(int i,int inicial,int actual) ///Determines if door i changed
{
    if(inicial==i){ //Initially closed
        if(actual!=i) //Door opened
            return true;
        else
            return false;
    }
    else{ //Initially open
        if(actual==i) //Door closed
            return true;
        else
            return false;
    }
}
void openDoor(int N,int i) ///Search for the switch that opens door i
{
    int L=0,R=N-1,mid;
    int inicial=tryCombination(temp);
    while(L<=R){
        mid=(L+R)/2;
        turn_on_off(N,L,mid,1); //Turn on
        int actual=tryCombination(temp);
        turn_on_off(N,L,mid,0); //Turn off
        if(door_changed(i,inicial,actual)) //As door changed, switch have to be in range [L,mid]
            R=mid-1;
        else
            L=mid+1;

    }
    d[L]=i; //Switch L opens door i
    if(inicial==i) //As with all off door was closed, we activate the switch
        s[L]=1;
    else
        s[L]=0; //Door was already open with switch off
    temp[L]=s[L];
}
void exploreCave(int N) {
	for(int i=0;i<N;i++){
        s[i]=-1;
	}
	for(int i=0;i<N;i++){ //Open all doors
        openDoor(N,i);
	}
	answer(s,d);
}

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