Submission #99273

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

cave

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

#include <iostream>
#include <cstdio>
#include <set>

#define TASK "Cave"

using namespace std;

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

#ifdef LHL
int tryCombination(int s[])
{
    int res = n;
    for (int i=0;i<n;++i)
        if (s[i] != reals[i])
            res = min(res,realval[i]);
    return res == n ? -1 : res;
}

void answer(int True[], int Val[])
{
    for (int i=0;i<n;++i)
        cout << True[i] << ' ';
    cout << '\n';
    for (int i=0;i<n;++i)
        cout << Val[i] << ' ';
}
#else
#include "cave.h"
#endif // LHL

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);
}

#ifdef LHL
void Enter()
{
    cin >> n;
    for (int i=0;i<n;++i)
        cin >> reals[i];
    for (int i=0;i<n;++i)
        cin >> realval[i];
}

void Init()
{

}

void Solve()
{
    exploreCave(n);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);

    Enter();
    Init();
    Solve();
}
#else
#endif //LHL

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