Submission #809200

#	Time	Username	Problem	Language	Result	Execution time	Memory
809200		finn__	Tortoise (CEOI21_tortoise)	C++17	0 / 100	1 ms	340 KiB

tortoise

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

constexpr size_t N = 500000;

int32_t a[N], u[N], v[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    cin >> n;
    int32_t last_playground = -1, a_sum = 0;
    for (size_t i = 0; i < n; ++i)
    {
        cin >> a[i];
        if (a[i] >= 0)
            u[i] = last_playground, a_sum += a[i];
        else
            last_playground = i;
    }

    last_playground = n;
    for (size_t i = n - 1; i < n; --i)
    {
        if (a[i] >= 0)
            v[i] = last_playground;
        else
            last_playground = i;
    }

    int32_t candy_walks = 0;

    for (size_t i = 0; i < n;)
    {
        if (a[i] >= 0)
            ++i;
        else
        {
            size_t j = i + 1;
            while (j < n && a[j] >= 0)
                ++j;
            if (j == n)
                break;
            size_t least_rewarding = SIZE_MAX;
            for (size_t k = i + 1; k < j; ++k)
                if (a[k] > 0 && least_rewarding == SIZE_MAX || min(k - i, j - k) < min(least_rewarding - i, j - least_rewarding))
                    least_rewarding = k;
            if (least_rewarding != SIZE_MAX)
                a[least_rewarding]--, candy_walks++;
            i = j;
        }
    }

    priority_queue<tuple<int32_t, int32_t, int32_t>, vector<tuple<int32_t, int32_t, int32_t>>, greater<tuple<int32_t, int32_t, int32_t>>> q;
    for (int32_t i = 0; i < n; ++i)
        if (a[i] > 0)
        {
            if (u[i] != -1)
                q.emplace(abs(i - u[i]), i, u[i]);
            if (v[i] != n)
                q.emplace(abs(i - v[i]), i, v[i]);
        }

    multiset<pair<int32_t, int32_t>> taken; // (shop, playground)
    int32_t curr_playground = 0, curr_time = 0;

    auto check_validity = [&]()
    {
        curr_playground = a[0] < 0 ? 0 : v[0], curr_time = curr_playground;

        for (auto const &[shop, playground] : taken)
        {
            if (playground != curr_playground)
                curr_playground = playground, curr_time += playground - curr_playground;
            if (curr_time + abs(shop - playground) > shop << 1)
                return -1;
            curr_time += abs(shop - playground) << 1;
        }

        return curr_time;
    };

    while (!q.empty())
    {
        auto const [dis, shop, playground] = q.top();
        q.pop();
        auto it = taken.emplace(shop, playground);
        if (check_validity() != -1)
        {
            a[shop]--;
            if (a[shop])
                q.emplace(dis, shop, playground);
        }
        else
        {
            taken.erase(it);
        }
    }

    cout << a_sum - candy_walks - taken.size() << '\n';
}

Compilation message (stderr)

tortoise.cpp: In function 'int main()':
tortoise.cpp:49:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   49 |                 if (a[k] > 0 && least_rewarding == SIZE_MAX || min(k - i, j - k) < min(least_rewarding - i, j - least_rewarding))
      |                              ^
tortoise.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int32_t i = 0; i < n; ++i)
      |                         ~~^~~
tortoise.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if (v[i] != n)
      |                 ~~~~~^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27