Submission #99272

#	Time	Username	Problem	Language	Result	Execution time	Memory
99272		long10024070	Cave (IOI13_cave)	C++11	100 / 100	1201 ms	640 KiB

cave

#define Link "https://oj.uz/problem/view/IOI13_cave?fbclid=IwAR2HAQQWHxbplVnmFGboqMw4yr-N9sR3mRA2usvk6rTocr7u5QYaZIyHqxw"

#include <iostream>
#include <cstdio>

#define TASK "Cave"

using namespace std;

const int maxn = 5e3 + 10;
int n,Val[maxn];
int s[maxn],True[maxn];

#include "cave.h"

void Fill(int l, int r, int d)
{
    for (int i=l;i<=r;++i)
        if (Val[i] != -1)
            s[i] = True[i];
        else
            s[i] = d;
}

void exploreCave(int n)
{
    fill(Val,Val+n,-1);
    for (int i=0;i<n;++i) {
        Fill(0,n-1,0);
        bool fl = (i == tryCombination(s));
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            Fill(1,n-1,fl^1);
            Fill(l,m,fl);
            Fill(m+1,r,fl^1);
            if (tryCombination(s) == i)
                l = m + 1;
            else
                r = m - 1;
        }
        True[l] = fl;
        Val[l] = i;
    }
    answer(True,Val);
}

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