답안 #698100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
698100 2023-02-12T10:31:14 Z finn__ RLE (BOI06_rle) C++17
15 / 100
1020 ms 146480 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)
            {
                if (!seq.empty() && seq.back().first == x)
                    seq.back().second += z + 1;
                else
                    seq.emplace_back(x, z + 1);
            }
            else
            {
                if (z)
                {
                    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;
        vector<pair<uint64_t, unsigned>> removed;
        while (1)
        {
            if (dp[q.top().second] == q.top().first && q.top().second == l)
            {
                removed.push_back(q.top());
                q.pop();
            }
            else if (dp[q.top().second] != q.top().first)
                q.pop();
            else
                break;
        }
        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] = dp[l] + additional_cost[i];

        for (auto const &p : removed)
            q.push(p);
        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 (int64_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].second <= 3)
        {
            if (seq[i].first != e)
            {
                for (size_t k = 0; k < seq[i].second; k++)
                    code.push_back(seq[i].first);
            }
            else
            {
                code.push_back(e);
                code.push_back(e);
                code.push_back(seq[i].second - 1);
            }
        }
        else
        {
            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)
                    i--;
            }
            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);
                }
            }
        }
    }

    for (unsigned const &x : code)
        cout << x << ' ';
    cout << '\n';
}

Compilation message

rle.cpp: In function 'int main()':
rle.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<unsigned int, long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int64_t i = 0; i < seq.size(); i++)
      |                         ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB the output code does not encode the input sequence
2 Incorrect 1 ms 212 KB Output is corrupted
3 Incorrect 1 ms 320 KB Unexpected end of file - int32 expected
4 Incorrect 1 ms 340 KB the output code does not encode the input sequence
5 Correct 1 ms 328 KB Output is correct
6 Incorrect 16 ms 1692 KB the output code does not encode the input sequence
7 Incorrect 120 ms 9800 KB the output code does not encode the input sequence
8 Incorrect 137 ms 12960 KB the output code does not encode the input sequence
9 Incorrect 271 ms 38996 KB Unexpected end of file - int32 expected
10 Incorrect 114 ms 9076 KB the output code does not encode the input sequence
11 Incorrect 102 ms 9296 KB the output code does not encode the input sequence
12 Incorrect 204 ms 29996 KB Unexpected end of file - int32 expected
13 Incorrect 243 ms 22800 KB the output code does not encode the input sequence
14 Incorrect 94 ms 14628 KB Unexpected end of file - int32 expected
15 Incorrect 47 ms 9348 KB the output code does not encode the input sequence
16 Incorrect 256 ms 24360 KB the output code does not encode the input sequence
17 Incorrect 333 ms 33028 KB the output code does not encode the input sequence
18 Incorrect 318 ms 43056 KB the output code does not encode the input sequence
19 Correct 702 ms 103368 KB Output is correct
20 Correct 1020 ms 146480 KB Output is correct