Submission #1100223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100223		KLKLK	Cave (IOI13_cave)	C++17	0 / 100	82 ms	520 KiB

cave

#include "cave.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

void exploreCave(int n)
{
    vector<bool> found(n);
    vector<bool> value(n);
    vector<int> chamber(n);

    int *guess = new int[n];

    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < n; ++i)
        {
            if (found[i]) guess[i] = value[i];
            else guess[i] = 0;
        }
        int this_value = tryCombination(guess) != k;
        for (int i = 0; i < n; ++i)
        {
            if (!found[i]) guess[i] = 1 - this_value;
        }

        int left = 0;
        int right = n - 1;
        int mid;

        while (left < right)
        {
            mid = (left + right) / 2;
            for (int i = left; i <= mid; ++i)
            {
                if (!found[i]) guess[i] = this_value;
            }
            int ans = tryCombination(guess);
            for (int i = left; i <= mid; ++i)
            {
                if (!found[i]) guess[i] = 1 - this_value;
            }

            if (ans == k) left = mid + 1;
            else right = mid;
        }

        value[left] = this_value;
        chamber[left] = k;
    }

    int *S = new int[n];
    int *D = new int[n];
    for (int i = 0; i < n; ++i) S[i] = value[i];
    for (int i = 0; i < n; ++i) D[i] = chamber[i];
    answer(S, D);
}

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