Submission #17218

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
17218	2015-11-08 09:35:09	murat	Cave (IOI13_cave)	C++98	100 / 100	512 ms	568 KiB

cave

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "cave.h"
const int NN = 5001;
int S[NN], go[NN], col[NN], h[NN];
int find(int bas, int son, int ccc, int ind) {
    if(bas == son) return bas;
    int orta = (bas + son) >> 1;
    for(int j = bas; j <= orta; j++)
        if(h[j]) S[j] = col[j];
        else S[j] = ccc;
    for(int j = orta + 1; j <= son; j++)
        if(h[j]) S[j] = col[j];
        else S[j] = !ccc;
    if(tryCombination(S) != ind)
        return find(bas, orta, ccc, ind);
    return find(orta+1, son, ccc, ind);
}
void exploreCave(int N) {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++)
            if(h[j]) S[j] = col[j];
            else S[j] = 0;
        int ccc = 0;
        if(tryCombination(S) == i)
            ccc = 1;
        int index = find(0, N - 1, ccc, i);
        h[index] = 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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