Submission #426596

#	Time	Username	Problem	Language	Result	Execution time	Memory
426596		Aldas25	Cave (IOI13_cave)	C++14	0 / 100	501 ms	480 KiB

cave

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;

void exploreCave(int N) {
    int S[N];
    int D[N];
    bool known[N];

    FOR(i, 0, N-1) S[i] = 0, D[i] = i;

    int mx = tryCombination(S);
    if (mx == -1) mx = N;

    FOR(i, 0, N-1) {
        if (mx == i) {
            FOR(j, 0, N-1) if (!known[j]) S[j] = !S[j];
            mx = tryCombination(S);
            if(mx==-1) mx = N;
        }

        vi notKnown;
        FOR(j, 0, N-1) if (!known[j]) notKnown.pb(j);

        int le = 0, ri = (int)notKnown.size()-1;
        while (le < ri) {
            int mid= (le+ri)/2;
            int tmpS[N];
            FOR(j, 0, N-1) tmpS[j] = S[j];
            FOR(j, 0, mid) tmpS[notKnown[j]] = !S[notKnown[j]];
            int cr = tryCombination(tmpS);
            if (cr == i) ri = mid;
            else le = mid+1;
        }

        int swId = le;
        D[swId] = i;
        known[swId] = true;
    }

    answer(S, D);
}

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