oj.uz

Submission #809200

# Submission time Handle Problem Language Result Execution time Memory
809200 2023-08-05T21:18:21 Z finn__ Tortoise (CEOI21_tortoise) C++17
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -