oj.uz

Submission #243082

# Submission time Handle Problem Language Result Execution time Memory
243082 2020-06-30T09:18:34 Z ffao Vim (BOI13_vim) C++14
60 / 100
 2000 ms 252504 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 20

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

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;
    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;
        }

        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];
            }
        }
    }

    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 86 ms 123896 KB Output is correct
2 Correct 78 ms 123768 KB Output is correct
3 Correct 70 ms 123640 KB Output is correct
4 Correct 81 ms 123768 KB Output is correct
5 Correct 83 ms 123896 KB Output is correct
6 Correct 104 ms 124152 KB Output is correct
7 Correct 88 ms 124024 KB Output is correct
8 Correct 66 ms 122872 KB Output is correct
9 Correct 66 ms 122872 KB Output is correct
10 Correct 69 ms 122872 KB Output is correct
11 Correct 66 ms 122872 KB Output is correct
12 Correct 68 ms 122872 KB Output is correct
13 Correct 76 ms 123900 KB Output is correct
14 Correct 72 ms 123768 KB Output is correct
15 Correct 69 ms 123692 KB Output is correct
16 Correct 73 ms 123768 KB Output is correct
17 Correct 91 ms 124152 KB Output is correct
18 Correct 80 ms 123772 KB Output is correct
19 Correct 76 ms 123556 KB Output is correct
20 Correct 76 ms 123640 KB Output is correct
21 Correct 82 ms 124028 KB Output is correct
22 Correct 87 ms 124024 KB Output is correct
23 Correct 77 ms 123896 KB Output is correct
24 Correct 84 ms 123900 KB Output is correct
25 Correct 81 ms 123896 KB Output is correct
26 Correct 90 ms 124152 KB Output is correct
27 Correct 102 ms 124152 KB Output is correct
28 Correct 110 ms 124280 KB Output is correct
29 Correct 86 ms 124028 KB Output is correct
30 Correct 78 ms 123896 KB Output is correct
31 Correct 87 ms 123896 KB Output is correct
32 Correct 82 ms 124024 KB Output is correct
33 Correct 83 ms 124024 KB Output is correct
34 Correct 102 ms 124152 KB Output is correct
35 Correct 102 ms 123896 KB Output is correct
36 Correct 87 ms 124152 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 132604 KB Output is correct
2 Correct 727 ms 132600 KB Output is correct
3 Correct 267 ms 128632 KB Output is correct
4 Correct 449 ms 132604 KB Output is correct
5 Correct 606 ms 132476 KB Output is correct
6 Correct 425 ms 133108 KB Output is correct
7 Correct 406 ms 132604 KB Output is correct
8 Correct 474 ms 132476 KB Output is correct
9 Correct 711 ms 132728 KB Output is correct
10 Correct 514 ms 132472 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 233836 KB Time limit exceeded
2 Execution timed out 2092 ms 230776 KB Time limit exceeded
3 Execution timed out 2097 ms 234412 KB Time limit exceeded
4 Execution timed out 2101 ms 252264 KB Time limit exceeded
5 Execution timed out 2089 ms 250844 KB Time limit exceeded
6 Execution timed out 2100 ms 235392 KB Time limit exceeded
7 Execution timed out 2102 ms 239496 KB Time limit exceeded
8 Execution timed out 2105 ms 242560 KB Time limit exceeded
9 Execution timed out 2099 ms 244684 KB Time limit exceeded
10 Execution timed out 2105 ms 242420 KB Time limit exceeded
11 Execution timed out 2093 ms 252504 KB Time limit exceeded
12 Execution timed out 2111 ms 250860 KB Time limit exceeded
13 Execution timed out 2094 ms 247148 KB Time limit exceeded
14 Execution timed out 2109 ms 247792 KB Time limit exceeded
15 Execution timed out 2110 ms 249328 KB Time limit exceeded
16 Execution timed out 2107 ms 235620 KB Time limit exceeded
17 Execution timed out 2109 ms 233840 KB Time limit exceeded
18 Execution timed out 2107 ms 234352 KB Time limit exceeded
19 Execution timed out 2098 ms 230776 KB Time limit exceeded
20 Execution timed out 2102 ms 232436 KB Time limit exceeded