Submission #678736

#	Time	Username	Problem	Language	Result	Execution time	Memory
678736		speedyArda	Cave (IOI13_cave)	C++14	0 / 100	112 ms	416 KiB

cave

#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
// Sol: Binary search queries on every element. // Apply reverse on left half -> If our door's state is changed that means we have our door in the left side of the array else it's on the right side
const int MAXN = 5005;
int combination[MAXN];
int switch_door[MAXN];
int switch_status[MAXN];
void exploreCave(int N) {
    /* ... */
    vector<int> unused;
    for(int i = 0; i < N; i++) {
        unused.push_back(i);
        combination[i] = 0;
    }

    for(int door = 0; door < N; door++)
    {
        int tmp = tryCombination(combination);
        bool closed = false;
        if(tmp == door)
            closed = true;
        int l = 0, r = unused.size() - 1;
        int curr = 0;
        while(l <= r)
        {
            int m = (l + r) / 2;
            for(int i = l; i <= m; i++)
                combination[i] = 1;
            for(int i = m + 1; i <= r; i++)
                combination[i] = 0;
            int res = tryCombination(combination);
            if((!closed && res == door) || (closed && res != door))
            {
                r = m - 1;
                curr = m;
            } else
            {
                l = m + 1;
            }

        }

        switch_door[curr] = door;
        if(closed)
            switch_status[curr] = 1;
        else
            switch_status[curr] = 0;
        vector<int> temp;
        for(int e : unused)
        {
            if(e == curr)
                continue;
            temp.push_back(e);
        }
        unused = temp;
        for(int e : unused)
            combination[e] = 0;
    }


    answer(switch_status, switch_door);
}

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