Submission #698100

#	Time	Username	Problem	Language	Result	Execution time	Memory
698100		finn__	RLE (BOI06_rle)	C++17	15 / 100	1020 ms	146480 KiB

rle

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

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

    size_t n, m;
    cin >> n >> m;

    vector<pair<unsigned, uint64_t>> seq;
    unsigned e = 0;

    for (size_t i = 0; i < m; i++)
    {
        unsigned x;
        cin >> x;
        if (x == e)
        {
            i += 2;
            unsigned y, z;
            cin >> y >> z;
            if (y == e)
            {
                if (!seq.empty() && seq.back().first == x)
                    seq.back().second += z + 1;
                else
                    seq.emplace_back(x, z + 1);
            }
            else
            {
                if (z)
                {
                    if (!seq.empty() && seq.back().first == y)
                        seq.back().second += z + 3;
                    else
                        seq.emplace_back(y, z + 3);
                }
                else
                    e = y;
            }
        }
        else
        {
            if (!seq.empty() && seq.back().first == x)
                seq.back().second++;
            else
                seq.emplace_back(x, 1);
        }
    }

    uint64_t cost = 0;
    vector<uint64_t> additional_cost(seq.size());

    for (size_t i = 0; i < seq.size(); i++)
    {
        auto const &[l, a] = seq[i];
        uint64_t c;
        if (a <= 3)
            c = a;
        else
            c = 3 * (a / (n + 3) + 1);
        additional_cost[i] = 3 * (a / (n + 1) + 1) - c;
        cost += c;
    }

    priority_queue<pair<uint64_t, unsigned>, vector<pair<uint64_t, unsigned>>, greater<pair<uint64_t, unsigned>>> q;
    vector<uint64_t> dp(n);
    vector<vector<unsigned>> prev_letter(n), position(n);
    q.emplace(0, 0);
    dp[0] = 0;
    for (unsigned i = 1; i < n; i++)
        q.emplace(3, i), dp[i] = 3;

    for (size_t i = 0; i < seq.size(); i++)
    {
        unsigned const l = seq[i].first;
        vector<pair<uint64_t, unsigned>> removed;
        while (1)
        {
            if (dp[q.top().second] == q.top().first && q.top().second == l)
            {
                removed.push_back(q.top());
                q.pop();
            }
            else if (dp[q.top().second] != q.top().first)
                q.pop();
            else
                break;
        }
        if (q.top().first + 3 < dp[l] + additional_cost[i])
        {
            dp[l] = q.top().first + 3;
            prev_letter[l].push_back(q.top().second);
            position[l].push_back(i); // Means switch directly after i.
        }
        else
            dp[l] = dp[l] + additional_cost[i];

        for (auto const &p : removed)
            q.push(p);
        q.emplace(dp[l], l);
    }

    while (q.top().first != dp[q.top().second])
        q.pop();
    cout << cost + q.top().first << '\n';
    vector<unsigned> code, switches, switch_positions;
    unsigned x = q.top().second, p = seq.size();
    while (1)
    {
        size_t i = lower_bound(position[x].begin(), position[x].end(), p) - position[x].begin();
        if (!i)
            break;
        unsigned y = prev_letter[x][i - 1];
        p = position[x][i - 1];
        switches.push_back(x);
        switch_positions.push_back(p);
        x = y;
    }

    reverse(switches.begin(), switches.end());
    reverse(switch_positions.begin(), switch_positions.end());
    e = 0;
    size_t j = 0;

    for (int64_t i = 0; i < seq.size(); i++)
    {
        if (j < switches.size() && switch_positions[j] < i)
        {
            code.push_back(e);
            code.push_back(switches[j]);
            code.push_back(0);
            e = switches[j];
            j++;
        }
        if (seq[i].second <= 3)
        {
            if (seq[i].first != e)
            {
                for (size_t k = 0; k < seq[i].second; k++)
                    code.push_back(seq[i].first);
            }
            else
            {
                code.push_back(e);
                code.push_back(e);
                code.push_back(seq[i].second - 1);
            }
        }
        else
        {
            if (seq[i].first != e)
            {
                while (seq[i].second > 3)
                {
                    code.push_back(e);
                    code.push_back(seq[i].first);
                    code.push_back(min(seq[i].second - 3, n - 1));
                    seq[i].second -= min(seq[i].second, n + 2);
                }
                if (seq[i].second)
                    i--;
            }
            else
            {
                while (seq[i].second)
                {
                    code.push_back(e);
                    code.push_back(e);
                    code.push_back(min(seq[i].second - 1, n - 1));
                    seq[i].second -= min(seq[i].second, n);
                }
            }
        }
    }

    for (unsigned const &x : code)
        cout << x << ' ';
    cout << '\n';
}

Compilation message (stderr)

rle.cpp: In function 'int main()':
rle.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<unsigned int, long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int64_t i = 0; i < seq.size(); i++)
      |                         ~~^~~~~~~~~~~~

• Subtask 1: 15 / 100