Submission #330632

#	Time	Username	Problem	Language	Result	Execution time	Memory
330632		Falcon	Cave (IOI13_cave)	C++17	100 / 100	631 ms	876 KiB

cave

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

using namespace std;

void exploreCave(int N) {
    int S[N]; fill(S, S + N, 0);
    bool can_flip[N]; fill(can_flip, can_flip + N, true);

    auto query = [&](int l) {
        for(int i{}; i < l; ++i) S[i] ^= can_flip[i];
        int x = tryCombination(S);
        for(int i{}; i < l; ++i) S[i] ^= can_flip[i];
        return x;
    };
    
    int D[N];
    for(int i{}; i < N; ++i) {
        int x{};
        if(tryCombination(S) != i) 
            for(int j{}; j < N; ++j)
                S[j] ^= can_flip[j];

        for(int k = 1 << __lg(N); k > 0; k >>= 1)
            if(k + x < N && query(k + x) == i)
                x += k;
        D[x] = i; S[x] ^= 1; can_flip[x] = false;
    }

    answer(S, D);
}

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