Submission #698123

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698123	2023-02-12T12:29:06 Z	finn__	RLE (BOI06_rle)	C++17	35 / 100	978 ms	138228 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;
        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	0 ms	212 KB	code is not the shortest
2	Incorrect	0 ms	212 KB	code is not the shortest
3	Incorrect	0 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	1540 KB	code is not the shortest
7	Incorrect	96 ms	7532 KB	code is not the shortest
8	Incorrect	137 ms	9808 KB	code is not the shortest
9	Incorrect	235 ms	35124 KB	code is not the shortest
10	Incorrect	99 ms	6892 KB	code is not the shortest
11	Incorrect	79 ms	7024 KB	code is not the shortest
12	Correct	190 ms	26920 KB	Output is correct
13	Incorrect	214 ms	17108 KB	code is not the shortest
14	Correct	92 ms	12856 KB	Output is correct
15	Incorrect	48 ms	8624 KB	code is not the shortest
16	Incorrect	258 ms	16740 KB	code is not the shortest
17	Correct	264 ms	26148 KB	Output is correct
18	Correct	291 ms	43308 KB	Output is correct
19	Correct	660 ms	93268 KB	Output is correct
20	Correct	978 ms	138228 KB	Output is correct