Submission #920082

#	Time	Username	Problem	Language	Result	Execution time	Memory
920082		tanprodium	Cave (IOI13_cave)	C++14	100 / 100	628 ms	744 KiB

cave

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

using namespace std;

// random
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// templates
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (y > x) {
            x = y;
            return (true);
        } else return (false);
    }

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (y < x) {
            x = y;
            return (true);
        } else return (false);
    }

// define
#define fi    first
#define se    second

#define pub   push_back
#define pob   pop_back
#define puf   push_front
#define pof   pop_front
#define eb    emplace_back
#define upb   upper_bound
#define lwb   lower_bound

#define left  VAN
#define right TAN

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).begin(),(a).end()
#define sort_and_unique(a) sort(all(a));(a).resize(unique(all(a))-a.begin())
#define max_ max_element
#define min_ min_element

// another define
using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

// limit
const int oo = 2e9;

// function
void yesno(bool x) {
    cout << (x ? "YES\n" : "NO\n");
}

void exploreCave(int N) {
    int S[N], D[N], done[N], out[N];
    for (int i = 0; i < N; i++)
        S[i] = D[i] = done[i] = out[i] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            if (!done[j])
                out[j] = 0;
        int ask = tryCombination(out);
        int stt;
        if (ask > i || ask == -1)
            stt = 0;
        else stt = 1;
        int l = 0, r = N - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            for (int j = 0; j < N; j++)
                if (!done[j])
                    out[j] = (stt ^ 1);
            for (int j = l; j <= mid; j++)
                if (!done[j])
                    out[j] = stt;
            int taken = tryCombination(out);
            if (taken > i || taken == -1)
                r = mid - 1;
            else l = mid + 1;
        }
        D[l] = i;
        S[l] = stt;
        out[l] = stt;
        done[l] = 1;
    }
    answer(S, D);
}

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