Submission #17218

#	Time	Username	Problem	Language	Result	Execution time	Memory
17218		murat	Cave (IOI13_cave)	C++98	100 / 100	512 ms	568 KiB

cave

#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;
        go[index] = i;
        col[index] = ccc;
    }
    answer(col, go);
}

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