oj.uz

Submission #5390

# Submission time Handle Problem Language Result Execution time Memory
5390 2014-04-21T06:38:05 Z ecardenaz Cave (IOI13_cave) C
100 / 100
 748 ms 640 KB 
//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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 520 KB Output is correct
2 Correct 344 ms 456 KB Output is correct
3 Correct 676 ms 540 KB Output is correct
4 Correct 388 ms 520 KB Output is correct
5 Correct 634 ms 532 KB Output is correct
6 Correct 501 ms 640 KB Output is correct
7 Correct 609 ms 536 KB Output is correct
8 Correct 5 ms 456 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 487 ms 540 KB Output is correct
13 Correct 541 ms 512 KB Output is correct
14 Correct 498 ms 512 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 532 KB Output is correct
2 Correct 6 ms 324 KB Output is correct
3 Correct 528 ms 532 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 585 ms 640 KB Output is correct
7 Correct 572 ms 532 KB Output is correct
8 Correct 660 ms 512 KB Output is correct
9 Correct 690 ms 540 KB Output is correct
10 Correct 726 ms 540 KB Output is correct
11 Correct 499 ms 512 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 6 ms 452 KB Output is correct
11 Correct 5 ms 396 KB Output is correct
12 Correct 6 ms 464 KB Output is correct
13 Correct 5 ms 400 KB Output is correct
14 Correct 5 ms 288 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 292 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 71 ms 452 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 460 KB Output is correct
9 Correct 105 ms 460 KB Output is correct
10 Correct 90 ms 512 KB Output is correct
11 Correct 124 ms 448 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 396 KB Output is correct
14 Correct 87 ms 460 KB Output is correct
15 Correct 7 ms 512 KB Output is correct
16 Correct 80 ms 512 KB Output is correct
17 Correct 88 ms 512 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Correct 5 ms 396 KB Output is correct
20 Correct 6 ms 452 KB Output is correct
21 Correct 102 ms 512 KB Output is correct
22 Correct 103 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 512 KB Output is correct
2 Correct 355 ms 640 KB Output is correct
3 Correct 550 ms 536 KB Output is correct
4 Correct 308 ms 516 KB Output is correct
5 Correct 596 ms 548 KB Output is correct
6 Correct 470 ms 640 KB Output is correct
7 Correct 565 ms 536 KB Output is correct
8 Correct 5 ms 396 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 458 ms 640 KB Output is correct
11 Correct 530 ms 532 KB Output is correct
12 Correct 530 ms 556 KB Output is correct
13 Correct 576 ms 640 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 526 ms 512 KB Output is correct
17 Correct 527 ms 536 KB Output is correct
18 Correct 690 ms 532 KB Output is correct
19 Correct 741 ms 592 KB Output is correct
20 Correct 659 ms 640 KB Output is correct
21 Correct 553 ms 460 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 69 ms 512 KB Output is correct
24 Correct 475 ms 536 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 5 ms 332 KB Output is correct
27 Correct 118 ms 448 KB Output is correct
28 Correct 113 ms 384 KB Output is correct
29 Correct 93 ms 456 KB Output is correct
30 Correct 671 ms 640 KB Output is correct
31 Correct 748 ms 512 KB Output is correct
32 Correct 703 ms 536 KB Output is correct
33 Correct 6 ms 396 KB Output is correct
34 Correct 6 ms 384 KB Output is correct
35 Correct 494 ms 536 KB Output is correct
36 Correct 69 ms 384 KB Output is correct
37 Correct 520 ms 600 KB Output is correct
38 Correct 5 ms 512 KB Output is correct
39 Correct 80 ms 512 KB Output is correct
40 Correct 108 ms 512 KB Output is correct
41 Correct 464 ms 640 KB Output is correct
42 Correct 5 ms 384 KB Output is correct
43 Correct 5 ms 384 KB Output is correct
44 Correct 6 ms 384 KB Output is correct
45 Correct 91 ms 448 KB Output is correct
46 Correct 95 ms 448 KB Output is correct
47 Correct 645 ms 540 KB Output is correct
48 Correct 684 ms 536 KB Output is correct
49 Correct 5 ms 384 KB Output is correct