Submission #698107

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698107	2023-02-12T10:54:22 Z	finn__	RLE (BOI06_rle)	C++17	15 / 100	994 ms	135028 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();
    cout << cost + q.top().first << '\n';
    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);
            }
        }
    }

    assert(code.size() == cost + q.top().first);
    for (unsigned const &x : code)
        cout << x << ' ';
    cout << '\n';
}

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	468 KB	Execution killed with signal 6
2	Runtime error	1 ms	468 KB	Execution killed with signal 6
3	Runtime error	1 ms	468 KB	Execution killed with signal 6
4	Runtime error	1 ms	596 KB	Execution killed with signal 6
5	Correct	1 ms	340 KB	Output is correct
6	Runtime error	10 ms	2484 KB	Execution killed with signal 6
7	Runtime error	54 ms	10884 KB	Execution killed with signal 6
8	Runtime error	71 ms	12932 KB	Execution killed with signal 6
9	Runtime error	204 ms	64712 KB	Execution killed with signal 6
10	Runtime error	51 ms	10312 KB	Execution killed with signal 6
11	Runtime error	45 ms	9688 KB	Execution killed with signal 6
12	Runtime error	139 ms	38908 KB	Execution killed with signal 6
13	Runtime error	118 ms	22204 KB	Execution killed with signal 6
14	Runtime error	83 ms	22120 KB	Execution killed with signal 6
15	Runtime error	39 ms	14788 KB	Execution killed with signal 6
16	Runtime error	130 ms	18588 KB	Execution killed with signal 6
17	Runtime error	156 ms	35204 KB	Execution killed with signal 6
18	Runtime error	239 ms	54696 KB	Execution killed with signal 6
19	Correct	639 ms	91816 KB	Output is correct
20	Correct	994 ms	135028 KB	Output is correct