Submission #1027506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027506		onbert	Cave (IOI13_cave)	C++17	100 / 100	205 ms	600 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
    int corr[n], pos[n];
    for (int i=0;i<n;i++) corr[i] = 0, pos[i] = -1;
    for (int i=0;i<n;i++) {
        int cur = tryCombination(corr);
        bool down = (cur==i);
        int l = 0, r = n-1;
        while (l<r) {
            int a[n];
            for (int i=0;i<n;i++) a[i] = corr[i];
            int mid = (l+r)/2;
            for (int j=l;j<=mid;j++) if (pos[j]==-1) a[j] = 1;
            cur = tryCombination(a);
            if ((cur==i) ^ down) r = mid;
            else l = mid+1;
        }
        pos[l] = i;
        corr[l] = down;
    }
    answer(corr, pos);
}
 

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