oj.uz

Submission #243095

# Submission time Handle Problem Language Result Execution time Memory
243095 2020-06-30T10:16:06 Z ffao Vim (BOI13_vim) C++14
62 / 100
 2000 ms 301800 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 124280 KB Output is correct
2 Correct 70 ms 124152 KB Output is correct
3 Correct 67 ms 123896 KB Output is correct
4 Correct 78 ms 124088 KB Output is correct
5 Correct 77 ms 124152 KB Output is correct
6 Correct 88 ms 124536 KB Output is correct
7 Correct 81 ms 124408 KB Output is correct
8 Correct 64 ms 123000 KB Output is correct
9 Correct 65 ms 123004 KB Output is correct
10 Correct 66 ms 122872 KB Output is correct
11 Correct 65 ms 123000 KB Output is correct
12 Correct 66 ms 123000 KB Output is correct
13 Correct 71 ms 124280 KB Output is correct
14 Correct 72 ms 124024 KB Output is correct
15 Correct 69 ms 124024 KB Output is correct
16 Correct 72 ms 124024 KB Output is correct
17 Correct 77 ms 124408 KB Output is correct
18 Correct 74 ms 124024 KB Output is correct
19 Correct 74 ms 123896 KB Output is correct
20 Correct 73 ms 123896 KB Output is correct
21 Correct 76 ms 124152 KB Output is correct
22 Correct 78 ms 124152 KB Output is correct
23 Correct 72 ms 124224 KB Output is correct
24 Correct 79 ms 124288 KB Output is correct
25 Correct 85 ms 124280 KB Output is correct
26 Correct 77 ms 124280 KB Output is correct
27 Correct 96 ms 124536 KB Output is correct
28 Correct 87 ms 124536 KB Output is correct
29 Correct 79 ms 124256 KB Output is correct
30 Correct 85 ms 124272 KB Output is correct
31 Correct 84 ms 124112 KB Output is correct
32 Correct 76 ms 124280 KB Output is correct
33 Correct 76 ms 124280 KB Output is correct
34 Correct 92 ms 124408 KB Output is correct
35 Correct 93 ms 124280 KB Output is correct
36 Correct 80 ms 124408 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 135800 KB Output is correct
2 Correct 368 ms 136032 KB Output is correct
3 Correct 170 ms 130424 KB Output is correct
4 Correct 251 ms 135800 KB Output is correct
5 Correct 355 ms 135680 KB Output is correct
6 Correct 251 ms 136184 KB Output is correct
7 Correct 259 ms 135804 KB Output is correct
8 Correct 266 ms 136096 KB Output is correct
9 Correct 362 ms 135928 KB Output is correct
10 Correct 301 ms 135928 KB Output is correct

Subtask #3
2.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 275828 KB Time limit exceeded
2 Execution timed out 2040 ms 272628 KB Time limit exceeded
3 Execution timed out 2102 ms 276632 KB Time limit exceeded
4 Execution timed out 2109 ms 301680 KB Time limit exceeded
5 Execution timed out 2110 ms 299504 KB Time limit exceeded
6 Execution timed out 2110 ms 278512 KB Time limit exceeded
7 Execution timed out 2107 ms 284656 KB Time limit exceeded
8 Execution timed out 2069 ms 287732 KB Time limit exceeded
9 Execution timed out 2099 ms 287976 KB Time limit exceeded
10 Execution timed out 2104 ms 288120 KB Time limit exceeded
11 Execution timed out 2102 ms 301800 KB Time limit exceeded
12 Execution timed out 2113 ms 299504 KB Time limit exceeded
13 Execution timed out 2105 ms 294256 KB Time limit exceeded
14 Execution timed out 2114 ms 295924 KB Time limit exceeded
15 Execution timed out 2115 ms 297844 KB Time limit exceeded
16 Correct 1691 ms 275600 KB Output is correct
17 Execution timed out 2115 ms 275956 KB Time limit exceeded
18 Execution timed out 2105 ms 276624 KB Time limit exceeded
19 Execution timed out 2041 ms 272444 KB Time limit exceeded
20 Execution timed out 2109 ms 274424 KB Time limit exceeded