Submission #1216801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216801		takoshanava	Cave (IOI13_cave)	C++20	51 / 100	155 ms	532 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int R[5000], D[5000];
bool vis[5000];

void exploreCave(int N) {
    for (int i = 0; i < N; ++i) {
        R[i] = 0;
        vis[i] = false;
    }

    for (int j = 0; j < N; ++j) {
        int base = tryCombination(R); 
        int tar = (base == -1 or base > j) ? 0 : 1;

        int l = 0, r = N - 1;
        while (l < r) {
            int mid = (l + r) / 2;

            int tmp[5000];
            for (int i = 0; i < N; ++i)
                tmp[i] = R[i];

            for (int i = l; i <= mid; ++i)
                if (!vis[i])
                    tmp[i] ^= 1;

            int res = tryCombination(tmp);
            int ntar = (res == -1 or res > j) ? 0 : 1;

            if (ntar != tar)
                r = mid;
            else
                l = mid + 1;
        }

        int idx = l;
        vis[idx] = true;

        R[idx] ^= 1;
        int test = tryCombination(R);
        int ans = (test == -1 or test > j) ? R[idx] : (R[idx] ^ 1);
        R[idx] = ans;

        D[idx] = j;
    }

    answer(R, D);
}

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