Submission #426664

#	Time	Username	Problem	Language	Result	Execution time	Memory
426664		Aldas25	Cave (IOI13_cave)	C++14	100 / 100	383 ms	584 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;
    FOR(i, 0, N-1) known[i] = false;

    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;
        }

        /*cout << " i = " << i << " mx = " << mx << " S: ";
        FOR(j, 0, N-1) cout << S[j] << " ";
        cout << endl;*/

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

        /*cout << "  notKnown: ";
        for (int x : notKnown) cout << x << " ";
        cout << endl;*/

        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, le, mid) tmpS[notKnown[j]] = !S[notKnown[j]];
            int cr = tryCombination(tmpS);
            //cout << "   le = " << le << " ri = " << ri << " mid = " << mid << " tryComb = " << cr << endl;
            if (cr == i) ri = mid;
            else le = mid+1;
        }

        int swId = notKnown[le];
        D[swId] = i;
        known[swId] = true;
        //cout << "  swId = " << swId << endl;
    }

    /*cout << " returnin S: ";
    FOR(i, 0, N-1) cout << S[i] << " ";
    cout << endl;

    cout << " returnin D: ";
    FOR(i, 0, N-1) cout << D[i] << " ";
    cout << endl;*/

    answer(S, D);
}

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