Submission #1349917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349917		bozho	Cave (IOI13_cave)	C++20	0 / 100	261 ms	524 KiB

cave

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

void exploreCave(int n)
{
    int s[n], s2[n], d[n];
    bool known[n];
    for (int i = 0; i < n; i++)
    {
        s[i] = 1;
        known[i] = 0;
    }
    int og, op, bb = 0;
    for (int i = 0; i < n; i++)
    {
        if (bb)
            og = tryCombination(s);
        int l = -1, r = n, mid;
        while (r - l > 1)
        {
            mid = l + (r - l) / 2;
            for (int j = 0; j < n; j++)
            {
                s2[j] = s[j];
                if (j <= mid && !known[j])
                    s2[j] ^= 1;
            }
            op = tryCombination(s2);
            if ((bool)(og != i) != (bool)(op != i))
                r = mid;
            else
                l = mid;
        }
        for (int j = 0; j < n; j++)
        {
            s2[j] = s[j];
            if (j <= r && !known[j])
                s2[j] ^= 1;
        }
        op = tryCombination(s2);
        int dd = s[r];
        if (op == i)
            s[r] = s2[r] ^ 1;
        else
            s[r] = s2[r];
        if (dd == s[r])
        {
            bb = 1;
            og = op;
        }
        d[r] = i;
        known[r] = 1;
    }
    answer(s, d);
}

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