Submission #742671

#	Time	Username	Problem	Language	Result	Execution time	Memory
742671		peteza	Cave (IOI13_cave)	C++14	100 / 100	860 ms	512 KiB

cave

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

void exploreCave(int N) {
    /* ok */
    bool vis[N] = {};
    int call[N] = {}, ans[N] = {}, connect[N];
    bool curdoor;
    int l, r, mid;
    std::vector<int> possibledoors;
    for(int i=0;i<N;i++) possibledoors.push_back(i);
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            if(vis[j]) call[j] = ans[j];
            else call[j] = 0;
        }
        if(tryCombination(call) == i) curdoor = 1;
        else curdoor = 0;
        l = 0; r = possibledoors.size()-1;
        while(l < r) {
            mid = (l+r) >> 1;
            for(int j=0;j<N;j++) {
                if(vis[j]) call[j] = ans[j];
                else {
                    if(possibledoors[l]<=j && j<=possibledoors[mid]) call[j] = curdoor;
                    else call[j] = !curdoor;
                }
            }
            if(tryCombination(call) != i) r = mid;
            else l = mid + 1;
        }
        int e = possibledoors[l];
        //std::cout << "switch " << e << " controls door " << i << '\n';
        connect[e] = i; vis[e] = 1; ans[e] = curdoor;
        possibledoors.erase(possibledoors.begin()+l);
    }
    answer(ans, connect);

}

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