Submission #5391

#	Time	Username	Problem	Language	Result	Execution time	Memory
5391		ecardenaz	Cave (IOI13_cave)	C11	100 / 100	753 ms	560 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 s[N];
    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;            
            complementa(izquierda,m);            
            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);
}

Compilation message (stderr)

cave.c: In function 'exploreCave':
cave.c:48:9: warning: unused variable 's' [-Wunused-variable]
     int s[N];
         ^
cave.c:46:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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