Submission #678757

#	Time	Username	Problem	Language	Result	Execution time	Memory
678757		speedyArda	동굴 (IOI13_cave)	C++14	100 / 100	594 ms	600 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;
    int combination[N], switch_door[N], switch_status[N];
    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[unused[i]] = 1;
            for(int i = m + 1; i <= r; i++)
                combination[unused[i]] = 0;
            int res = tryCombination(combination);
            if((!closed && res == door) || (closed && res != door))
            {
                r = m - 1;
                curr = unused[m];
            } else
            {
                l = m + 1;
            }

            for(int e : unused)
                combination[e] = 0;

        }

        switch_door[curr] = door;
        if(closed) {
            switch_status[curr] = 1;
            combination[curr] = 1;
        }
        else {
            switch_status[curr] = 0;
            combination[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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24