Submission #1292260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292260		hynmj	Cave (IOI13_cave)	C++20	100 / 100	379 ms	540 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int place[5005];
int correct[5005];
int done[5005];
int query[5005];
int n;
void exploreCave(int N)
{
    n = N;
    for (int door = 0; door < n; door++)
    {
        for (int i = 0; i < n; i++)
        {
            if (done[i])
                continue;
            else
                correct[i] = 1;
        }
        int k = tryCombination(correct);
        int right = (k > door or k == -1);
        int wrong = 1 - right;
        int l = -1, r = n + 1;
        while (r - l > 1)
        {
            int mid = (r + l) / 2;
            for (int i = 0; i < n; i++)
            {
                if (done[i])
                {
                    continue;
                }
                if (i <= mid)
                    correct[i] = right;
                else
                    correct[i] = wrong;
            }
            k = tryCombination(correct);
            (k > door or k == -1) ? (r = mid) : (l = mid);
        }
        // cout << "set door " << door << endl;
        correct[r] = right;
        place[r] = door;
        done[r] = 1;
    }
    answer(correct, place);
}

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