Submission #698113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698113	2023-02-12T11:03:09 Z	finn__	RLE (BOI06_rle)	C++17	35 / 100	1006 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 c;
        if (a <= 3)
            c = a;
        else
            c = 3 * (a / (n + 3) + 1);
        additional_cost[i] = 3 * (a / (n + 1) + 1) - 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

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	code is not the shortest
2	Incorrect	0 ms	212 KB	code is not the shortest
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	13 ms	1508 KB	code is not the shortest
7	Incorrect	98 ms	7560 KB	code is not the shortest
8	Incorrect	130 ms	9872 KB	code is not the shortest
9	Incorrect	241 ms	35144 KB	code is not the shortest
10	Incorrect	98 ms	6988 KB	code is not the shortest
11	Incorrect	79 ms	7260 KB	code is not the shortest
12	Incorrect	185 ms	26840 KB	code is not the shortest
13	Correct	225 ms	17252 KB	Output is correct
14	Correct	92 ms	12956 KB	Output is correct
15	Incorrect	45 ms	8592 KB	code is not the shortest
16	Incorrect	250 ms	16636 KB	code is not the shortest
17	Correct	262 ms	25900 KB	Output is correct
18	Correct	288 ms	43412 KB	Output is correct
19	Correct	705 ms	93336 KB	Output is correct
20	Correct	1006 ms	138152 KB	Output is correct