Submission #243098

#	Time	Username	Problem	Language	Result	Execution time	Memory
243098		ffao	Vim (BOI13_vim)	C++14	76 / 100	2100 ms	134524 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 12

int ccE;
int nxtnE[71000];
int nxt[71000][21];
int idxE[71000];
int jmp[71000][11][JMPS+1];
int dist[71000][11][JMPS+1];
int spt[71000][10][17];

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 = 16; t >= 0; t--) {
            if (spt[curPos][j][t] <= nextE) {
                addD += (1<<t) * 2;
                curPos = spt[curPos][j][t];
            }
        }

        for (int jj = 0; jj <= j; jj++) if (spt[curPos][jj][0] != n) {
            int letdst = s[ spt[curPos][jj][0] ] - 'a';
            update(nextE, letdst, 0, curDist + addD + 2);
        }
    }
    
    // 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 < 17; 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: 16 / 40