답안 #651952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651952 2022-10-20T17:15:54 Z _martynas RLE (BOI06_rle) C++11
100 / 100
582 ms 100132 KB
#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};
    }

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

    {
        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(x != -1) {
        if(event[x].F >= 0) E.PB({event[x].S, event[x].F});
        x = event[x].S;
    }
    reverse(all(E));

    int verify = 0;
    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 ";
            verify += 3;
            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) << " ";
                verify += 3;
                A[i].F -= n;
            }
            else {
                if(A[i].F <= 3) {
                    cout << A[i].S << " ";
                    verify++;
                    A[i].F--;
                }
                else {
                    cout << e << " " << A[i].S << " " << min(A[i].F-3, n-1LL) << " ";
                    verify += 3;
                    A[i].F -= min(A[i].F-3, n-1LL)+3;
                }
            }
        }
    }

    return 0;
}

/*



*/

Compilation message

rle.cpp: In function 'int main()':
rle.cpp:221: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]
  221 |         if(j < E.size() && E[j].F <= i) {
      |            ~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 15 ms 3536 KB Output is correct
7 Correct 112 ms 24184 KB Output is correct
8 Correct 195 ms 33528 KB Output is correct
9 Correct 321 ms 65520 KB Output is correct
10 Correct 137 ms 25164 KB Output is correct
11 Correct 105 ms 19436 KB Output is correct
12 Correct 192 ms 41900 KB Output is correct
13 Correct 270 ms 52780 KB Output is correct
14 Correct 111 ms 18076 KB Output is correct
15 Correct 45 ms 9420 KB Output is correct
16 Correct 333 ms 54348 KB Output is correct
17 Correct 296 ms 61928 KB Output is correct
18 Correct 315 ms 61224 KB Output is correct
19 Correct 582 ms 100132 KB Output is correct
20 Correct 542 ms 96600 KB Output is correct