Submission #1025449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025449		socpite	Cave (IOI13_cave)	C++17	100 / 100	553 ms	744 KiB

cave

#include "cave.h"

const int maxn = 5e3+5;

int pos[maxn], val[maxn];
int A[maxn];

int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);

void exploreCave(int N) {
    for(int i = 0; i < N; i++)val[i] = -1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(val[j] != -1)A[j] = val[j];
            else A[j] = 0;
        }
        int nw = tryCombination(A) == i, p = 0;
        for(int d = 0; (1<<d) < N; d++){
            for(int j = 0; j < N; j++){
                if(val[j] != -1)continue;
                A[j] = nw^((j>>d)&1);
            }
            if(tryCombination(A) == i)p^=(1<<d);
        }
        val[p] = nw;
        pos[p] = i;
    }
    answer(val, pos);
}

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