Submission #1232519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232519		countless	Cave (IOI13_cave)	C++20	0 / 100	2094 ms	1108 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

void exploreCave(int N) {
    int flip[N], conn[N], attempt[N], bit[N];
    memset(flip, 0, sizeof(flip));
    memset(attempt, 0, sizeof(attempt));
    memset(bit, 0, sizeof(bit));

    set<int> avail;
    for (int i = 0; i < N; i++) {
        avail.insert(i);
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            attempt[j] = flip[j];
        }

        int query = tryCombination(attempt);
        if (query <= i and query != -1) bit[i] = 1;

        set<int> use = avail;
        while (use.size() >= 2) {
            set<int> left, right;
            int m = use.size();

            int jj = 0;
            for (auto &x : use) {
                if (jj++ < m/2) left.insert(x);
                else right.insert(x);
            }

            for (int j = 0; j < N; j++) {
                attempt[j] = flip[j];
            }

            for (auto &j : left) {
                attempt[j] = bit[i];
            }

            query = tryCombination(attempt);
            if (query <= i and query != -1) {
                use = right;
            } else {
                use = left;
            }
        }

        assert(use.size() == 1);
        int ind = *use.begin();
        flip[ind] = bit[i];
        conn[ind] = i;

        avail.erase(ind);
    }

    answer(flip, conn);
}

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