Submission #867738

#	Time	Username	Problem	Language	Result	Execution time	Memory
867738		Dec0Dedd	Cave (IOI13_cave)	C++14	100 / 100	595 ms	856 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

void exploreCave(int n) {
    int ans[n]={}, d[n]={};
    memset(ans, -1, sizeof(ans));
    memset(d, -1, sizeof(d));

    for (int i=0; i<n; ++i) {
        int s[n+1]={};
        // check if i-th must be up

        for (int j=0; j<n; ++j) {
            if (ans[j] != -1) s[j]=d[j];
            else s[j]=0;
        }

        int k=0, x=tryCombination(s);
        if (x > i || x == -1) k=0;
        else k=1;

        int l=0, r=n-1, res=n-1;
        while (l <= r) {
            int m=(l+r)/2;

            int tp[n]={};
            for (int j=0; j<n; ++j) {
                if (ans[j] != -1) tp[j]=d[j];
                else {
                    if (j <= m) tp[j]=k;
                    else tp[j]=k^1;
                }
            }

            x=tryCombination(tp);
            if (x > i || x == -1) r=m-1, res=m;
            else l=m+1;
        } ans[res]=i, d[res]=k;
    }

    answer(d, ans);
}

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