Submission #243095

#	Time	Username	Problem	Language	Result	Execution time	Memory
243095		ffao	Vim (BOI13_vim)	C++14	62 / 100	2115 ms	301800 KiB

vim

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n;
string s;

#define JMPS 14

int ccE;
int nxtnE[71000];
int nxt[71000][21];
int idxE[71000];
int jmp[71000][21][21];
int dist[71000][21][21];
int spt[71000][10][18];

priority_queue< pair<int, pair<int, pii> > > q;

void update(int nextE, int let, int idx, int curDist) {
    if (dist[nextE][let][idx] > curDist) {
        dist[nextE][let][idx] = curDist;
        q.push( {-curDist, {nextE, {let, idx}}} );
    }
}

void expand(int curPos, int nextE, int curDist) {
    // cout << "EXP" << endl;
    
    int addD = 0;
    for (int j = 0; j < 9; j++) {
        for (int t = 17; t >= 0; t--) {
            if (spt[curPos][j][t] <= nextE) {
                addD += (1<<t) * 2;
                curPos = spt[curPos][j][t];
            }
        }

        for (int letdst = 0; letdst < 10; letdst++) if (letdst != 4 && nxt[nextE][letdst] != n && nxt[curPos+1][letdst] == nxt[nextE][letdst]) {
            // if (curPos == 0) cout << curPos << " " << nextE << " " << curDist << " -> " << letdst << " " << nxt[curPos+1][letdst] << " " << curDist + addD << endl;
            update(nextE, letdst, 0, curDist + addD + 2);
        }
    }

    // for (int letdst = 0; letdst < 10; letdst++) if (letdst != 4 && nxt[nextE][letdst] != n) {
    //     int dest = nxt[nextE][letdst];
    //     int pos = curPos, tDist = curDist;
    //     while (pos < dest) {
    //         int nP = pos;
    //         for (int tt = 0; tt < 10; tt++) if (tt != 4) {
    //             if (nxt[pos+1][tt] <= dest) nP = max(nP, nxt[pos+1][tt]);
    //         }
    //         tDist+=2;
    //         pos = nP;
    //     }

    //     cout << curPos << " " << nextE << " " << curDist << " -> " << letdst << " " << dest << " " << tDist << endl;
    //     update(nextE, letdst, 0, tDist);
    // }
    
    // cout << "EXPD" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> s;

    int st = 0;
    while (st < n && s[st] == 'e') st++;

    int rem = st;
    s = s.substr(st);
    n = (int)s.size();

    memset(dist, 0x3f, sizeof(dist));

    for (int j = 0; j < 10; j++) nxt[n][j] = n;
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < 10; j++) nxt[i][j] = nxt[i+1][j];
        nxt[i][s[i]-'a'] = i;
    }

    for (int i = 0; i < n; i++) if (s[i] == 'e') {
        nxtnE[i] = n;
        for (int j = 0; j < 10; j++) if (j != 4) {
            nxtnE[i] = min(nxtnE[i], nxt[i][j]);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            jmp[i][j][0] = i;
            for (int k = 1; k <= JMPS; k++) {
                jmp[i][j][k] = jmp[i][j][k-1];
                if (jmp[i][j][k] < n) jmp[i][j][k] = nxt[jmp[i][j][k]+1][j];
            }
        }
    }

    for (int i = 0; i < n; i++) {
        vector<int> dests;
        for (int j = 0; j < 10; j++) if (j != 4) {
            dests.push_back(nxt[i+1][j]);
        }
        sort(all(dests));
        for (int j = 0; j < 9; j++) {
            spt[i][j][0] = dests[8-j];
        }
    }

    for (int j = 0; j < 9; j++) spt[n][j][0] = n;

    for (int k = 1; k < 18; k++) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 9; j++) {
                spt[i][j][k] = spt[ spt[i][j][k-1] ][j][k-1];
            }    
        }
    }

    int stE = nxt[0][4];
    if (stE == n) {
        cout << rem << endl;
        return 0;
    }

    int pE = stE;
    idxE[pE] = ccE++;
    while (pE < n) {
        pE = nxt[pE+1][4];
        idxE[pE] = ccE++;
    }

    expand(0, stE, 0);
    
    int ans = 1000000000;

    while (!q.empty()) {
        pair<int, pair<int, pii> > entry = q.top(); q.pop();
        int nextE = entry.second.first;
        int let = entry.second.second.first;
        int letidx = entry.second.second.second;
        int curDist = -entry.first;

        // cout << nextE << " " << let << " " << letidx << " " << curDist << endl;
        if (dist[nextE][let][letidx] != curDist) continue;

        int thisPos = jmp[nextE][let][letidx+1];

        // go back and fill up to nextE
        int nwNextE = nxt[thisPos+1][4];
        int cntEs = idxE[nwNextE] - idxE[nextE];

        if (nwNextE == n) {
            ans = min(ans, curDist + cntEs + (thisPos-nextE));
        }
        else {
            expand(nxtnE[nextE], nwNextE, curDist + cntEs + (thisPos-nextE));
        }

        // go forward
        for (int j = 0; j < 10; j++) if (j != 4) {
            int np = nxt[thisPos+1][j];
            if (np == n) continue;
            int nIdx = -1;
            for (int k = 1; k <= JMPS; k++) {
                if (jmp[nextE][j][k] == np) nIdx = k-1;
            }

            if (nIdx != -1) update(nextE, j, nIdx, curDist + 2);
        }
    }

    cout << ans + rem << endl;
    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 10 / 10
• Subtask 3: 2 / 40