Submission #1161998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161998		MrDogMeat	Cave (IOI13_cave)	C++20	100 / 100	109 ms	572 KiB

cave

#include"cave.h"
#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 5e3;

int S[MAX_N + 5], D[MAX_N + 5];
vector<int> Switches;

///find switch for first door of set
int solve(int l, int r, int pos, int numDoor) {
    if(l == r) {
        return Switches[l];
    }

    int mid = (l + r) / 2;

    for(int i = l; i <= mid; i++) S[Switches[i]] = pos;
    for(int i = mid + 1; i <= r; i++) S[Switches[i]] = 1 - pos;

    int door = tryCombination(S);

    if(door > numDoor || door == -1) return solve(l, mid, pos, numDoor);

    for(int i = l; i <= mid; i++) S[Switches[i]] = 1 - pos;
    for(int i = mid + 1; i <= r; i++) S[Switches[i]] = pos;
    return solve(mid + 1, r, pos, numDoor);
}

void exploreCave(int N) {
    for(int i = 0; i < N; i++) {
        Switches.push_back(i);
    }

    for(int numDoor = 0; numDoor < N; numDoor++) {
        for(auto e : Switches) {
            S[e] = 0;
        }

        int pos, door = tryCombination(S);

        if(door > numDoor || door == -1) {
            pos = 0;
        }
        else {
            pos = 1;
        }

        int numSwitch = solve(0, Switches.size() - 1, pos, numDoor);

        D[numSwitch] = numDoor;
        S[numSwitch] = pos;
        Switches.erase(lower_bound(Switches.begin(), Switches.end(), numSwitch));

        //cout << numSwitch << " " << numDoor << " " << pos << "\n";
    }

    answer(S, D);
}

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