Submission #1104113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104113		Kirill22	RLE (BOI06_rle)	C++17	100 / 100	1221 ms	93220 KiB

rle

#include "bits/stdc++.h"
 
using namespace std;
 
mt19937 gen(22);
 
void solve() {
    int m, n;
    m = gen() % 200000 + 2;
    n = gen() % 300000 + 1;
    cin >> m >> n;
    vector<int> a;
    if (1) {
        a.resize(n);
        for (int i = 0; i < n; i++) {
//        a[i] = gen() % (m - 1) + 1;
            cin >> a[i];
        }
    } else {
        cout << "start" << endl;
        for (int i = 0, cur = 0; i < n; i++) {
            int t = gen() % 4;
            int val = gen() % m;
            while (val == cur) val = gen() % m;
            if (t == 0) {
                a.push_back(val);
            } else if (t == 1) {
                a.push_back(cur); a.push_back(cur); a.push_back(gen() % m);
            } else if (t == 2) {
                a.push_back(cur); a.push_back(val); a.push_back(0);
                cur = val;
            } else {
                a.push_back(cur); a.push_back(val); a.push_back(gen() % (m - 1) + 1);
            }
        }
        cout << "end" << endl;
        n = (int) a.size();
    }
    if (0) {
//        cout << m << " " << n << endl;
//        for (auto &x: a) {
//            cout << x << " ";
//        }
//        cout << endl;
    }
    vector<pair<int, long long>> b;
    auto add = [&] (int x, int c) {
        if (!b.empty() && b.back().first == x) {
            b.back().second += c;
        } else {
            b.push_back({x, c});
        }
    };
    for (int l = 0, t = 0; l < n; ) {
        if (a[l] != t) {
            add(a[l], 1);
            l++;
        } else if (a[l] == a[l + 1]) {
            add(a[l], a[l + 2] + 1);
            l += 3;
        } else if (a[l + 2] == 0) {
            t = a[l + 1];
            l += 3;
        } else {
            add(a[l + 1], a[l + 2] + 3);
            l += 3;
        }
    }
    set<pair<int, int>> st;
    vector<int> dp(m, 3);
    int w = 0;
    dp[0] = 0;
    for (int i = 0; i < m; i++) {
        st.insert({dp[i], i});
    }
    vector<int> mem(b.size());
    for (int i = 0; i < (int) b.size(); i++) {
        auto [x, len] = b[i];
        // 4 ... m + 2
        int op = (int) 1e9;
        for (int d = 0; d <= min(len, 3ll); d++) {
            int k = (len - d + m + 1) / (m + 2);
            if (len - d >= k * 4) {
                op = min(op, k * 3 + d);
            }
        }
        int val1 = dp[x] + w + (len + m - 1) / m * 3;
        auto it = st.begin();
        if (it->second == x) {
            it = next(it);
        }
        int val2 = it->first + w + op + 3;
        st.erase({dp[x], x});
        w += op;
        dp[x] = min(val1, val2) - w;
        mem[i] = val1 < val2 ? x : it->second;
        st.insert({dp[x], x});
//        if (st.begin()->first + w < 0) {
//            cout << i << " " << len << " " << m << " " << val1 << " " << val2 << endl;
//            exit(0);
//        }
    }
//    cout << "F" << endl << endl << endl;
    int answer = st.begin()->first + w, last = st.begin()->second;
//    cout << answer << endl;
    vector<int> ans;
    for (int i = (int) b.size() - 1; i >= 0; i--) {
        auto [x, len] = b[i];
        if (last != x) {
            pair<int, int> op = {(int) 1e9, -1};
            for (int d = 0; d <= min(len, 3ll); d++) {
                int k = (len - d + m + 1) / (m + 2);
                if (len - d >= k * 4) {
                    op = min(op, {k * 3 + d, d});
                }
            }
            while (op.second) {
                ans.push_back(x);
                len--;
                op.first--;
                op.second--;
            }
            int k = op.first / 3;
            while (k) {
                // (len - cur) >= (k - 1) * 4
                int cur = min((long long) m + 2, len - (k - 1) * 4);
                ans.push_back(cur - 3);
                ans.push_back(x);
                ans.push_back(last);
                k--;
                len -= cur;
            }
        } else if (mem[i] != x) {
            last = mem[i];
            ans.push_back(0);
            ans.push_back(x);
            ans.push_back(last);
            pair<int, int> op = {(int) 1e9, -1};
            for (int d = 0; d <= min(len, 3ll); d++) {
                int k = (len - d + m + 1) / (m + 2);
                if (len - d >= k * 4) {
                    op = min(op, {k * 3 + d, d});
                }
            }
            while (op.second) {
                ans.push_back(x);
                len--;
                op.first--;
                op.second--;
            }
            int k = op.first / 3;
            while (k) {
                // (len - cur) >= (k - 1) * 4
                int cur = min((long long) m + 2, len - (k - 1) * 4);
                ans.push_back(cur - 3);
                ans.push_back(x);
                ans.push_back(last);
                k--;
                len -= cur;
            }
        } else {
            int k = (len + m - 1) / m;
            while (k) {
                int cur = min((long long) m, len);
                ans.push_back(cur - 1);
                ans.push_back(x);
                ans.push_back(x);
                k--;
                len -= cur;
            }
        }
    }
    if (last) {
        ans.push_back(0);
        ans.push_back(last);
        ans.push_back(0);
    }
    assert(answer == (int) ans.size());
    std::reverse(ans.begin(), ans.end());
    cout << answer << '\n';
    for (auto& x : ans) {
        cout << x << " ";
    }
    cout << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 100 / 100