Submission #698112

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698112	2023-02-12T11:01:04 Z	finn__	RLE (BOI06_rle)	C++17	35 / 100	2500 ms	138268 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 (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

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2590 ms	212 KB	Time limit exceeded
2	Execution timed out	2575 ms	212 KB	Time limit exceeded
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	Execution timed out	2590 ms	600 KB	Time limit exceeded
7	Incorrect	101 ms	7476 KB	code is not the shortest
8	Execution timed out	2593 ms	1464 KB	Time limit exceeded
9	Incorrect	283 ms	35188 KB	code is not the shortest
10	Incorrect	102 ms	7084 KB	code is not the shortest
11	Incorrect	79 ms	7212 KB	code is not the shortest
12	Incorrect	192 ms	26848 KB	code is not the shortest
13	Correct	225 ms	17180 KB	Output is correct
14	Correct	93 ms	12876 KB	Output is correct
15	Incorrect	48 ms	8584 KB	code is not the shortest
16	Execution timed out	2571 ms	952 KB	Time limit exceeded
17	Correct	268 ms	26048 KB	Output is correct
18	Correct	295 ms	43300 KB	Output is correct
19	Correct	668 ms	93184 KB	Output is correct
20	Correct	1048 ms	138268 KB	Output is correct