Submission #170112

#	Time	Username	Problem	Language	Result	Execution time	Memory
170112		buttercrab	Cave (IOI13_cave)	C++17	100 / 100	1426 ms	716 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

int s[5050], d[5050], t[5050], r[5050];

void exploreCave(int n) {
    for (int i = 0; i < n; i++) {
        int p = 0;
        fill(t, t + n, 0);
        for (int j = 0; j < i; j++) {
            t[r[j]] = s[j];
        }
        s[i] = tryCombination(t) == i;
        for (int j = 0; (1 << j) < n; j++) {
            fill(t, t + n, !s[i]);
            for (int k = 0; k < n; k++) {
                if((k & ((1 << (j + 1)) - 1)) == (p | (1 << j)))
                    t[k] = s[i];
            }
            for (int k = 0; k < i; k++) {
                t[r[k]] = s[k];
            }
            if(tryCombination(t) != i) p |= (1 << j);
        }
        d[p] = i;
        r[i] = p;
    }
    for(int i=0; i<n; i++) {
        t[r[i]] = s[i];
    }

    answer(t, d);
}

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