Submission #542746

#	Time	Username	Problem	Language	Result	Execution time	Memory
542746		collodel	Cave (IOI13_cave)	C++17	100 / 100	334 ms	460 KiB

cave

#include "cave.h"
#include <vector>
#include <iostream>

using namespace std;

void flip(int ask[], int ans[], int start, int end) {
    while(start != end) {
        if(ans[start] == -1)
            ask[start] ^= 1;
        start++;
    }
}

void unset(int ask[], int ans[], int start, int end) {
    while(start != end) {
        if(ans[start] == -1)
            ask[start] = 0; 
        start++;
    }
}

void exploreCave(int N) {
    int ans[N];
    int ask[N];
    int corr[N];

    for(int i = 0; i < N; ++i) {
        ans[i] = -1, ask[i] = 0, corr[i] = 0;
    }

    // per ogni porta
    for(int i = 0; i < N; ++i) {
        unset(ask, ans, 0, N); // imposta a 0, ignorando le risposte gia' trovate

        int q = tryCombination(ask); 
        bool state = 0;

        if(q <= i && q != -1) {
            // porta aperta
            state = 1;
            flip(ask, ans, 0, N);
        }

        // cambia lo stato di tutte le luci che non influenzano la porta corrente
        int l = 0, r = N;
        while(r - l > 1) {
            int m = (l + r) / 2;
            // cambia la sinistra
            flip(ask, ans, l, m);

            q = tryCombination(ask);

            if(q > i || q == -1) {
                // la porta e' ancora aperta
                l = m;
            } else {
                // la porta e' chiusa, flippa i range
                flip(ask, ans, l, r);
                r = m;
            }
        }

        ans[l] = i;
        corr[l] = state;
    }

    answer(corr, ans);
}

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