Submission #648675

#	Time	Username	Problem	Language	Result	Execution time	Memory
648675		a_aguilo	Cave (IOI13_cave)	C++14	100 / 100	822 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;
        memset(ns,1-abrir,sizeof(ns));
        for(int i=lo; i<=mid; i++){
            if(d[i] != -1){
                ns[i] = s[i];
            }else ns[i] = abrir;
        }
		for(int i = 0; i < N; ++i){
          if(d[i] != -1){
                ns[i] = s[i];
            }
        }
        /*
        for(int i=mid; i<hi; i++){
            if(d[i] != -1){
                ns[i] = s[i];
            }else ns[i] = (1-abrir);
        }
        */
        int temp = tryCombination(ns);
        if(temp == puerta){
            lo = mid+1;
        }else{
            hi = 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 abrir = 0;
        if(temp == i) //Se abre i con 1
            abrir = 1;
        int sol = interruptor(i,abrir,N,s,d);
        s[sol] = abrir;
        //el interruptor de la puerta i es sol
        d[sol] = i;
        //encontrado[sol] = true;
    }
    answer(s,d);
}

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