Submission #698126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698126	2023-02-12T12:32:06 Z	finn__	RLE (BOI06_rle)	C++17	90 / 100	955 ms	138152 KB

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)
            { // Repeat e.
                if (!seq.empty() && seq.back().first == x)
                    seq.back().second += z + 1;
                else
                    seq.emplace_back(x, z + 1);
            }
            else
            {
                if (z)
                { // Repeat y.
                    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);
        }
    }

    vector<uint64_t> additional_cost(seq.size());

    for (size_t i = 0; i < seq.size(); i++)
    {
        auto const &[l, a] = seq[i];
        uint64_t b = a, c = 0;
        while (b > 3)
        {
            c += 3;
            b -= min(b, n + 2);
        }
        if (b)
            c += b;
        b = a;
        while (b)
        {
            additional_cost[i] += 3;
            b -= min(b, n);
        }
        additional_cost[i] -= c;
    }

    priority_queue<pair<uint64_t, unsigned>, vector<pair<uint64_t, unsigned>>, greater<pair<uint64_t, unsigned>>> q;
    vector<uint64_t> dp(n, UINT_MAX);
    vector<vector<unsigned>> prev_letter(n), position(n);
    q.emplace(0, 0);
    dp[0] = 0;

    for (size_t i = 0; i < seq.size(); i++)
    {
        unsigned const l = seq[i].first;
        while (!q.empty() && (dp[q.top().second] != q.top().first || q.top().second == l))
            q.pop();

        if (!q.empty() && 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] += additional_cost[i];

        q.emplace(dp[l], l);
    }

    while (q.top().first != dp[q.top().second])
        q.pop();
    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 (size_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].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)
            {
                for (size_t k = 0; k < seq[i].second; k++)
                    code.push_back(seq[i].first);
            }
        }
        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);
            }
        }
    }

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

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	16 ms	1528 KB	Output is correct
7	Correct	96 ms	7656 KB	Output is correct
8	Correct	177 ms	9800 KB	Output is correct
9	Correct	248 ms	35108 KB	Output is correct
10	Correct	97 ms	7112 KB	Output is correct
11	Correct	89 ms	7372 KB	Output is correct
12	Correct	189 ms	26924 KB	Output is correct
13	Correct	212 ms	17240 KB	Output is correct
14	Correct	91 ms	12912 KB	Output is correct
15	Incorrect	47 ms	8640 KB	code is not the shortest
16	Incorrect	233 ms	16660 KB	code is not the shortest
17	Correct	258 ms	25924 KB	Output is correct
18	Correct	291 ms	43380 KB	Output is correct
19	Correct	632 ms	93156 KB	Output is correct
20	Correct	955 ms	138152 KB	Output is correct