Submission #5386

#	Time	Username	Problem	Language	Result	Execution time	Memory
5386		ecardenaz	Cave (IOI13_cave)	C11	0 / 100	166 ms	65540 KiB

cave

//Emmanuel Antonio Cardenaz Villalobos
//20 Abril 2014

#include "cave.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>


typedef struct {
    int valorSwitch;
    int posicionSwitch;
    int puerta;
    int active;
    int size;
} swit;

swit *zwitch;
swit * codigo;
int clos;
int v;
int t;

swit * mitad(swit* vec, int start, int end) {
    swit *nvect;
    nvect = (swit *) calloc(((end + 1) - start), sizeof (swit));
    int i, j = 0;
    for (i = start; i < end; i++) {
        nvect[j].active = vec[i].active;
        nvect[j].posicionSwitch = vec[i].posicionSwitch;
        nvect[j].puerta = vec[i].puerta;
        nvect[j].valorSwitch = vec[i].valorSwitch;
        nvect[j++].size = vec[i].size;
    }
    return nvect;
}

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

int leng(swit* vec) {
    int cn = 0;
    while (vec[cn].size > 0.0000) {
        cn++;
    }
    return cn;
}

void complementa(swit *vec, int ini, int fin) {
    int size = leng(vec);
    int i, pos;
    int j = 0;

    if (fin == 0||fin ==1) {
        pos = vec[0].posicionSwitch;
        if (codigo[pos].active == 0) {
            if (codigo[pos].valorSwitch == 0) {
                codigo[pos].valorSwitch = 1;
            } else {
                codigo[pos].valorSwitch = 0;
            }
        }
    } else {
        for (i = ini; i < fin; i++) {
            pos = vec[j++].posicionSwitch;
            if (codigo[pos].active == 0) {
                if (codigo[pos].valorSwitch == 0) {
                    codigo[pos].valorSwitch = 1;
                } else {
                    codigo[pos].valorSwitch = 0;
                }
            }
        }
    }

}

void busquedaBinaria(swit* vec,int N) {
    int size;
    swit *derecha, *izquierda;
    size = leng(vec);
    int pos;
    int i;
    printf("%d\n", v);
    complementa(vec, 0, floor(size / 2));
    int code[N];
    int puerta[N];
    for (i = 0; i < N; i++) {
        code[i] = codigo[i].valorSwitch;
        puerta[i] = codigo[i].puerta;
    }
    v = tryCombination(code);
    
     if (clos == 0) {
        if (size > 1) {
            if (v == t||v == -1) {
                if (v==-1){
                derecha = mitad(vec, 0, floor(size / 2));
                complementa(vec, 0, floor(size / 2));
                busquedaBinaria(derecha,N);
                }else{
                izquierda = mitad(vec, floor(size / 2), size);
                complementa(vec, floor(size / 2), size);
                busquedaBinaria(izquierda,N);
                }
            } else {
                derecha = mitad(vec, 0, floor(size / 2));
                complementa(vec, 0, floor(size / 2));
                busquedaBinaria(derecha,N);
            }
        }
        if (size == 1) {
                pos = vec[0].posicionSwitch;
                codigo[pos].active = 1;    
                codigo[pos].puerta=t;
           
        }

    } else { //close == 1

          if (size > 1) {
            if (v == t||v == -1) {
                if (v==-1){
               izquierda = mitad(vec, floor(size / 2), size);
                complementa(vec, floor(size / 2), size);
                busquedaBinaria(izquierda,N);
                }else{
                    derecha = mitad(vec, 0, floor(size / 2));
                complementa(vec, 0, floor(size / 2));
                busquedaBinaria(derecha,N);
                }
            } else {       
                izquierda = mitad(vec, floor(size / 2), size);
                complementa(vec, floor(size / 2), size);
                busquedaBinaria(izquierda,N);
            }
        }
        if (size == 1) {
            complementa(vec,0,size);
                pos = vec[0].posicionSwitch;
                codigo[pos].active = 1;      
                codigo[pos].puerta=t;          
        }
    }
}

void exploreCave(int N) {
    /* ... */
    loadcode(N);
    printf("%d\n", N);
    int i;
    int code[N];
    int puerta[N];
    int j;
    for (j = 0; j < N; j++) {
        for (i = 0; i < N; i++) {
            code[i] = codigo[i].valorSwitch;
            puerta[i] = codigo[i].puerta;
        }
        v = tryCombination(code);
        t = j;
        if (v == t) {
            clos = 0;
        } else {
            clos = 1;
        }
        busquedaBinaria(codigo,N);
    }
      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 'complementa':
cave.c:60:9: warning: unused variable 'size' [-Wunused-variable]
     int size = leng(vec);
         ^~~~
cave.c: In function 'busquedaBinaria':
cave.c:97:9: warning: variable 'puerta' set but not used [-Wunused-but-set-variable]
     int puerta[N];
         ^~~~~~

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