답안 #698123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
698123 2023-02-12T12:29:06 Z finn__ RLE (BOI06_rle) C++17
35 / 100
978 ms 138228 KB
#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';
}
# 결과 실행 시간 메모리 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