Submission #17461

#	Time	Username	Problem	Language	Result	Execution time	Memory
17461		kdh9949	Cave (IOI13_cave)	C++98	100 / 100	1685 ms	592 KiB

cave

#include "cave.h"

int ans[5010], sw[5010], chk[5010];

bool havethisbit(int x, int d){
    return (x & (1 << d)) != 0;
}

void exploreCave(int N) {
    int n = N;
    if(n == 1){
        ans[0] = 0;
        sw[0] = 0;
        if(tryCombination(sw) != -1) sw[0] = 1;
        answer(sw, ans);
        return;
    }
    int maxbit;
    for(maxbit = 0; (1 << maxbit) < n; maxbit++);
    int curans, cursw = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(chk[j]) continue;
            else sw[j] = 0;
        }
        if(tryCombination(sw) == i) curans = 1;
        else curans = 0;
        for(int j = 0; j < maxbit; j++){
            for(int k = 0; k < n; k++){
                if(chk[k]) continue;
                if(havethisbit(k, j)) sw[k] = curans;
                else sw[k] = !(curans);
            }
            if(tryCombination(sw) != i) cursw += (1 << j);
        }
        ans[cursw] = i;
        sw[cursw] = curans;
        chk[cursw] = 1;
        cursw = 0;
    }
    answer(sw, ans);
}

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