Submission #648499

#	Time	Username	Problem	Language	Result	Execution time	Memory
648499		ojoConmigo	Cave (IOI13_cave)	C++17	0 / 100	409 ms	460 KiB

cave

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

int interruptor(int puerta, int abrir, int N,int s[], int d[]){
    int ns[N];
    int lo = 0, hi = N-1,res = -1;
    while(lo <= hi){
        int mid = lo + (hi-lo)/2;
        for(int i=0; i<mid; i++){
            if(d[i] != -1){
                ns[i] = s[i];
            }else ns[i] = abrir;
        }
        for(int i=mid; i<N; i++){
            if(d[i] != -1){
                ns[i] = s[i];
            }else ns[i] = (1-abrir);
        }
        int temp = tryCombination(ns);
        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
    memset(s,0,sizeof(s));
    memset(d,-1,sizeof(d));
    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