제출 #648085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648085		ojoConmigo	동굴 (IOI13_cave)	C++17	0 / 100	432 ms	460 KiB

cave

#include "cave.h"

int interruptor(int puerta, int abrir, bool encontrado[],int N,int s[]){
    int lo = 0, hi = N-1,res = -1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0; i<mid; i++){
            if(encontrado[i])continue;
            s[i] = abrir;
        }
        for(int i=mid; i<N; i++){
            if(encontrado[i])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++){
        int temp = tryCombination(s);
        int sol = -1;
        if(temp == i){ //Se abre i con 1
            sol = interruptor(i,1,encontrado,N,s);
            s[sol] = 1;
        }else{//Se abre i con 0
            sol = interruptor(i,0,encontrado,N,s);
            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