| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 5385 | ecardenaz | Cave (IOI13_cave) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "cave.h"
//Emmanuel Antonio Cardenaz Villalobos
// 20-Abril-2014
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() {
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 transform() {
}
void busquedaBinaria(swit* vec) {
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);
}else{
izquierda = mitad(vec, floor(size / 2), size);
complementa(vec, floor(size / 2), size);
busquedaBinaria(izquierda);
}
} else {
derecha = mitad(vec, 0, floor(size / 2));
complementa(vec, 0, floor(size / 2));
busquedaBinaria(derecha);
}
}
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);
}else{
derecha = mitad(vec, 0, floor(size / 2));
complementa(vec, 0, floor(size / 2));
busquedaBinaria(derecha);
}
} else {
izquierda = mitad(vec, floor(size / 2), size);
complementa(vec, floor(size / 2), size);
busquedaBinaria(izquierda);
}
}
if (size == 1) {
complementa(vec,0,size);
pos = vec[0].posicionSwitch;
codigo[pos].active = 1;
codigo[pos].puerta=t;
}
}
}
void exploreCave(int N) {
/* ... */
loadcode();
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);
}
for (i = 0; i < N; i++) {
code[i] = codigo[i].valorSwitch;
puerta[i] = codigo[i].puerta;
}
answer(code, puerta);
}