Submission #443608

#	Time	Username	Problem	Language	Result	Execution time	Memory
443608		Lam_lai_cuoc_doi	Cave (IOI13_cave)	C++17	100 / 100	349 ms	672 KiB

cave

#define task ""

#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#include "cave.h"

constexpr int N = 5e3 + 5;
constexpr int Inf = 1e9 + 7;
int a[N], s[N], d[N];
int m, nn;

void Fill(int l, int r, int v)
{
    for (int i = l; i <= r; ++i)
        s[a[i]] = v;
}

int Guess(int l, int r, int v)
{
    Fill(l, r, v);
    int x = tryCombination(s);
    return (x == -1 ? Inf : x);
}

int Get(int l, int r, const int &v, const int &i)
{
    Fill(l, r, v);
    while (l != r)
    {
        if (Guess(l, (l + r) / 2, !v) == i)
        {
            Fill(l, r, v);
            r = (l + r) / 2;
        }
        else
        {
            Fill(l, r, v);
            l = (l + r) / 2 + 1;
        }
    }
    return l;
}

void exploreCave(int n)
{
    m = n;
    for (int i = 0; i < n; ++i)
        a[i] = i;

    for (int i = 0; i < n; ++i)
    {
        if (Guess(0, m - 1, 1) > i)
        {
            int tmp = Get(0, m - 1, 1, i);
            s[a[tmp]] = 1;
            d[a[tmp]] = i;
            a[tmp] = a[--m];
        }
        else
        {
            int tmp = Get(0, m - 1, 0, i);
            s[a[tmp]] = 0;
            d[a[tmp]] = i;
            a[tmp] = a[--m];
        }
    }
    answer(s, d);
}

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