Submission #698110

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698110	2023-02-12T10:56:34 Z	finn__	RLE (BOI06_rle)	C++17	25 / 100	983 ms	134956 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);
        }
    }

    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;
        while (dp[q.top().second] != q.top().first || q.top().second == l)
            q.pop();

        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] += 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

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	code is not the shortest
2	Incorrect	1 ms	212 KB	the output code does not encode the input sequence
3	Incorrect	1 ms	212 KB	code is not the shortest
4	Incorrect	1 ms	340 KB	code is not the shortest
5	Correct	1 ms	340 KB	Output is correct
6	Incorrect	14 ms	1488 KB	code is not the shortest
7	Incorrect	98 ms	7624 KB	code is not the shortest
8	Incorrect	131 ms	9880 KB	code is not the shortest
9	Incorrect	234 ms	35132 KB	code is not the shortest
10	Incorrect	97 ms	7092 KB	code is not the shortest
11	Incorrect	83 ms	7004 KB	code is not the shortest
12	Incorrect	187 ms	26924 KB	code is not the shortest
13	Correct	214 ms	17248 KB	Output is correct
14	Incorrect	97 ms	12848 KB	code is not the shortest
15	Incorrect	47 ms	8392 KB	code is not the shortest
16	Incorrect	229 ms	16872 KB	code is not the shortest
17	Incorrect	290 ms	25384 KB	code is not the shortest
18	Correct	293 ms	35364 KB	Output is correct
19	Correct	661 ms	91756 KB	Output is correct
20	Correct	983 ms	134956 KB	Output is correct