Submission #648380

#	Time	Username	Problem	Language	Result	Execution time	Memory
648380		ojoConmigo	Cave (IOI13_cave)	C++17	0 / 100	307 ms	352 KiB

cave

#include "cave.h"

int interruptor(int puerta, int abrir, int N,int s[], int d[]){
    int lo = 0, hi = N-1,res = -1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0; i<mid; i++){
            if(d[i] != -1)continue;
            s[i] = abrir;
        }
        for(int i=mid; i<N; i++){
            if(d[i] != -1)continue;
            s[i] = (1 - abrir);
        }
        int temp = tryCombination(s);
        if(temp == puerta){
            hi = mid-1;
        }else{
            lo = mid+1;
            res = mid;
        }
    }
    return res;
}

void exploreCave(int N) {
    int s[N],d[N];
    //bool encontrado[N]; //swichts
    for(int i=0; i<N; i++){
        s[i] = 0;
        d[i] = -1;
    }
    for(int i=0; i<N; i++){
        int temp = tryCombination(s);
        int sol = -1;
        if(temp == i){ //Se abre i con 1
            sol = interruptor(i,1,N,s,d);
            s[sol] = 1;
        }else{//Se abre i con 0
            sol = interruptor(i,0,N,s,d);
            s[sol] = 0;
        }
        //el interruptor de la puerta i es sol
        d[sol] = i;
        //encontrado[sol] = true;
    }
    answer(s,d);
}

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