Submission #5390

#	Time	Username	Problem	Language	Result	Execution time	Memory
5390		ecardenaz	Cave (IOI13_cave)	C11	100 / 100	748 ms	640 KiB

cave

//Emmanuel Antonio Cardenaz
//21 Abril 2014
 
#include "cave.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

typedef struct {
    int valorSwitch;
    int puerta;
    int active;
    int size;
} swit;
swit * codigo;

void loadcode(int N) {
    codigo = (swit *) calloc(N, sizeof (swit));
    int i;
    for (i = 0; i < N; i++) {
        codigo[i].size = 1;
        codigo[i].valorSwitch = 1;
        codigo[i].active = -1; 
        codigo[i].puerta = -1;
    }
}

void complementa(int ini, int fin) {
    int i;
    for (i = ini; i <= fin; i++) {
        if (codigo[i].active == -1) {
            if (codigo[i].valorSwitch == 1) {
                codigo[i].valorSwitch = 0;
            } else {
                codigo[i].valorSwitch = 1;
            }
        } else {
            codigo[i].valorSwitch = codigo[i].active;
        }

    }

}

void exploreCave(int N) {
    int i, j;
    int izquierda, derecha, m;
    int code[N];
    int puerta[N];
    loadcode(N);

    int t;
    int v;
    int x;

    for (i = 0; i < N; i++) {
        izquierda = 0;
        derecha = N - 1;


        complementa(0, N - 1);
        for (x = 0; x < N; x++) {
            code[x] = codigo[x].valorSwitch;
        }
        t = tryCombination(code);
        if (t == i) {
            complementa(0, N - 1);
        }

        while (izquierda < derecha) {
            m = (izquierda + derecha) / 2;
            for (j = izquierda; j <= m; j++) {
                if (codigo[j].active == -1)
                    codigo[j].valorSwitch ^= 1;
                else
                    codigo[j].valorSwitch = codigo[j].active;
            }
            for (x = 0; x < N; x++) {
                code[x] = codigo[x].valorSwitch;
            }
            v = tryCombination(code);

            if (v == i) {
                 complementa(izquierda,m);
                derecha = m;
            } else {    
                izquierda = m + 1;
            }
        }
        codigo[izquierda].active = codigo[izquierda].valorSwitch;
        codigo[izquierda].puerta = i;
    }
    
    for (i = 0; i < N; i++) {
        code[i] = codigo[i].valorSwitch;
        puerta[i] = codigo[i].puerta;
    }
    answer(code, puerta);
}

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