Submission #651945

#	Time	Username	Problem	Language	Result	Execution time	Memory
651945		_martynas	RLE (BOI06_rle)	C++11	15 / 100	647 ms	96108 KiB

rle

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 2e6+5;
const ll INF = 1e15;

int n, m, k;
pll A[MXN]; // {cnt, who}
ll cost[MXN];
int last[MXN/19];
ll dp[MXN];
int prev[MXN];
// {do what (-1 - come from left, other - swap to sth), from where (-1 ~ from the beginning)}
pii event[MXN+MXN/19];
int MQ[MXN]; int mq;

int main() {
    FASTIO();
    // solution for not encoded sequence:
    cin >> n >> m;
    int e = 0, b = -1;
    int which = 0;
    // 0 - nothing
    // 1 - e
    // 2 - ee
    // 3 - eb
    for(int i = 0; i < m; i++) {
        int c; cin >> c;
        if(which == 3) {
            if(c == 0) {
                e = b;
            }
            else {
                A[k++] = {c+3, b};
            }
            which = 0;
        }
        else if(which == 2) {
            A[k++] = {c+1, e};
            which = 0;
        }
        else if(which == 1) {
            if(c == e) {
                which = 2;
            }
            else {
                which = 3;
                b = c;
            }
        }
        else {
            if(c == e) {
                which = 1;
            }
            else {
                A[k++] = {1, c};
            }
        }
        dp[i] = INF;
        event[i] = {-100, -100};
    }
    {
        int j = 0;
        for(int i = 1; i < k; i++) {
            if(A[i].S == A[j].S) {
                A[j].F += A[i].F;
            }
            else {
                j++;
                A[j] = A[i];
            }
        }
        k = j+1;
    }

//    for(int i = 0; i < k; i++) {
//        cerr << A[i].S << " * " << A[i].F << "\n";
//    }

    for(int i = 0; i < n; i++) last[i] = -1;

    auto ceil_div = [](ll x, ll y){
        return (x+y-1)/y;
    };

    ll ans = 0;
    for(int i = 0; i < k; i++) {
        ll same = 3*ceil_div(A[i].F, n);
        ll diff = 3*(A[i].F/(n+2)) + min(A[i].F%(n+2), 3LL);
        ans += diff;
        cost[i] = same-diff;
        if(same > diff) {
            // don't swap since last same number interval
            int idx = last[A[i].S];
            if(idx == -1 && A[i].S == 0) {
                dp[i] = 0;
                event[i] = {-1, -1};
            }
            else if(idx != -1) {
                if(dp[idx]+cost[idx] < dp[i]) {
                    dp[i] = dp[idx]+cost[idx];
                    event[i] = {-1, idx};
                }
            }
            // do swap at some place after last same number position
            if(idx == -1) {
                if(3LL < dp[i]) {
                    event[i] = {A[i].S, -1};
                    dp[i] = 3LL;
                }
            }
            else {
                int l = 0, r = mq-1;
                while(l < r) {
                    int m = (l+r)/2;
                    if(MQ[m] <= idx) {
                        l = m+1;
                    }
                    else {
                        r = m;
                    }
                }
                if(l < mq && MQ[l] > idx) {
                    if(dp[MQ[l]]+3 < dp[i]) {
                        dp[i] = dp[MQ[l]]+3;
                        event[i] = {A[i].S, MQ[l]};
                    }
                }
            }
            while(mq > 0 && dp[MQ[mq-1]] > dp[i]) {
                mq--;
            }
            MQ[mq++] = i;
            last[A[i].S] = i;
        }
    }

    ll best = INF;
    int x = -1;
    for(int where = 0; where < n; where++) {
        ll curr = INF;
        // don't swap since last same number interval
        int idx = last[where];
        if(idx == -1 && where == 0) {
            curr = 0;
            event[k+where] = {-1, -1};
        }
        else if(idx != -1) {
            if(dp[idx]+cost[idx] < curr) {
                curr = dp[idx]+cost[idx];
                event[k+where] = {-1, idx};
            }
        }
        // do swap at some place after last same number position
        if(idx == -1) {
            if(3LL < curr) {
                event[k+where] = {where, -1};
                curr = 3LL;
            }
        }
        else {
            int l = 0, r = mq-1;
            while(l < r) {
                int m = (l+r)/2;
                if(MQ[m] <= idx) {
                    l = m+1;
                }
                else {
                    r = m;
                }
            }
            if(l < mq && MQ[l] > idx) {
                if(dp[MQ[l]]+3 < curr) {
                    curr = dp[MQ[l]]+3;
                    event[k+where] = {where, MQ[l]};
                }
            }
        }
        if(curr < best) {
            best = curr;
            x = k+where;
        }
    }
    cerr << ans << " " << best << "\n";
    cout << ans+best << "\n";
    vector<pii> E; // {where, swap to}

    while(event[x].S != -1) {
        if(event[x].F >= 0) E.PB({event[x].S, event[x].F});
        x = event[x].S;
    }
    reverse(all(E));

    e = 0;
    for(int i = 0, j = 0; i < k; i++) {
        if(j < E.size() && E[j].F == i) {
            cout << e << " " << E[j].S << " 0 ";
            e = E[j].S;
            j++;
        }
        while(A[i].F > 0) {
            if(A[i].S == e) {
                cout << e << " " << e << " " << min(A[i].F-1, n-1LL) << " ";
                A[i].F -= n;
            }
            else {
                if(A[i].F < 3) {
                    cout << A[i].S << " ";
                    A[i].F--;
                }
                else {
                    cout << e << " " << A[i].S << " " << min(A[i].F-3, n-1LL) << " ";
                    A[i].F -= min(A[i].F-3, n-1LL)+3;
                }
            }
        }
    }



    return 0;
}

/*



*/

Compilation message (stderr)

rle.cpp: In function 'int main()':
rle.cpp:214:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |         if(j < E.size() && E[j].F == i) {
      |            ~~^~~~~~~~~~

• Subtask 1: 15 / 100