Submission #108766

#	Time	Username	Problem	Language	Result	Execution time	Memory
108766		polyfish	Cave (IOI13_cave)	C++14	100 / 100	415 ms	640 KiB

cave

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

const int MAX_N = 5002;

int s[MAX_N], true_state[MAX_N], d[MAX_N];

void Find(int l, int r, int pos) {
    if (l==r) {
        d[l] = pos;
        s[l] ^= 1;
        true_state[l] = s[l];
        return;
    }

    int mid = (l + r) / 2;

    for (int i=l; i<=mid; ++i) {
        if (true_state[i]==-1)
            s[i] ^= 1;
    }

    int tmp = tryCombination(s);

    for (int i=l; i<=mid; ++i) {
        if (true_state[i]==-1)
            s[i] ^= 1;
    }

    if (tmp!=pos)
        return Find(l, mid, pos);

    return Find(mid+1, r, pos);
}

void exploreCave(int N) {
    memset(true_state, -1, sizeof(true_state));

    for (int i=0; i<N; ++i) {
        if (tryCombination(s)!=i) {
            for (int i=0; i<N; ++i) {
                if (true_state[i]==-1)
                    s[i] ^= 1;
            }
        }

        Find(0, N-1, i);
    }

    answer(true_state, d);
}

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