Submission #1232497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232497		countless	Cave (IOI13_cave)	C++20	0 / 100	2095 ms	1092 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(bit, 0, sizeof(bit));
    memset(attempt, 0, sizeof(attempt));

    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) bit[i] = 1;

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

            for (int i = 0; i < m/2; i++) {
                auto it = use.begin();
                left.insert(*it);
                use.erase(it);
            }

            for (int i = 0; i < (m+1)/2; i++) {
                auto it = use.begin();
                right.insert(*it);
                use.erase(it);
            }

            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) {
                use = right;
            } else {
                use = left;
            }
        }

        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