Submission #1349922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349922		bozho	Cave (IOI13_cave)	C++20	100 / 100	240 ms	608 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];
    vector<int> v, z;
    for (int i = 0; i < n; i++)
    {
        s[i] = 1;
        known[i] = 0;
        v.push_back(i);
    }
    int og, op;
    for (int i = 0; i < n; i++)
    {
        og = tryCombination(s);
        int l = -1, r = v.size(), mid;
        while (r - l > 1)
        {
            mid = l + (r - l) / 2;
            for (int j = 0; j < n; j++)
            {
                s2[j] = s[j];
                if (j <= v[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 <= v[r] && !known[j])
                s2[j] ^= 1;
        }
        op = tryCombination(s2);
        if (op == i)
            s[v[r]] = s2[v[r]] ^ 1;
        else
            s[v[r]] = s2[v[r]];
        d[v[r]] = i;
        known[v[r]] = 1;
        z.clear();
        for (int i = 0; i < v.size(); i++)
        {
            if (i != r)
                z.push_back(v[i]);
        }
        v = z;
    }
    answer(s, d);
}

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