Submission #1316198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316198		pablo7948	Cave (IOI13_cave)	C++20	0 / 100	106 ms	540 KiB

cave

#include <vector> 

#include "cave.h" 

#include <unordered_set> 

  

using namespace std; 

  

void negatev(vector<int>& comb, const unordered_set<int>& known, int L, int R) { 

    for(int i = L; i < R; i++) { 

        if(known.count(i) == 0) { 

            comb[i] = 1 - comb[i]; 

        } 

    } 

} 

  

void exploreCave(int N) { 

    vector<int> comb(N, 0); 

    int current = 0; 

     

    vector<int> inter(N, -1); 

    vector<int> pos(N, -1); 

     

    unordered_set<int> known; 

    known.reserve(N); 

     

    int res = tryCombination(comb.data()); 

    bool prev = res != 0; 

     

    while(current < N) { 

        int L = 0, R = N - 1; 

         

        while(L != R) { 

            int mid = (L+R)/2 + 1; 

            negatev(comb, known, L, mid); 

            res = tryCombination(comb.data()); 

            bool open = res >= N || res == -1; 

            if(open != prev) { 

                R = mid - 1; 

            } else { 

                L = mid; 

            } 

            prev = open; 

        } 

         

        inter[current] = L; 

        if(!prev) comb[current] = 1 - comb[current]; 

        pos[current] = comb[current]; 

        prev = res >= N + 1 || res == -1; 

        known.insert(L);
        current++;

    } 

     

    answer(inter.data(), pos.data()); 

}

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