oj.uz

Submission #243065

# Submission time Handle Problem Language Result Execution time Memory
243065 2020-06-30T08:56:33 Z ffao Vim (BOI13_vim) C++14
72.6111 / 100
 2000 ms 251516 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 11

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
48.6111111111 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 123896 KB Output is correct
2 Correct 69 ms 123768 KB Output is correct
3 Correct 74 ms 123640 KB Output is correct
4 Correct 82 ms 123772 KB Output is correct
5 Correct 83 ms 123768 KB Output is correct
6 Correct 86 ms 123956 KB Output is correct
7 Correct 79 ms 123896 KB Output is correct
8 Correct 65 ms 122872 KB Output is correct
9 Correct 64 ms 122876 KB Output is correct
10 Correct 66 ms 122872 KB Output is correct
11 Correct 65 ms 123000 KB Output is correct
12 Correct 68 ms 122944 KB Output is correct
13 Correct 72 ms 123896 KB Output is correct
14 Correct 74 ms 123800 KB Output is correct
15 Correct 77 ms 123644 KB Output is correct
16 Correct 70 ms 123768 KB Output is correct
17 Correct 76 ms 124024 KB Output is correct
18 Correct 79 ms 123768 KB Output is correct
19 Correct 84 ms 123512 KB Output is correct
20 Correct 71 ms 123640 KB Output is correct
21 Correct 74 ms 123768 KB Output is correct
22 Correct 77 ms 123800 KB Output is correct
23 Correct 83 ms 123768 KB Output is correct
24 Correct 96 ms 123768 KB Output is correct
25 Correct 75 ms 123768 KB Output is correct
26 Correct 84 ms 123896 KB Output is correct
27 Correct 88 ms 124004 KB Output is correct
28 Correct 87 ms 124028 KB Output is correct
29 Incorrect 85 ms 123896 KB Output isn't correct
30 Correct 79 ms 123864 KB Output is correct
31 Correct 78 ms 123768 KB Output is correct
32 Correct 75 ms 123896 KB Output is correct
33 Correct 75 ms 123896 KB Output is correct
34 Correct 92 ms 123896 KB Output is correct
35 Correct 83 ms 124024 KB Output is correct
36 Correct 80 ms 123896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 132160 KB Output is correct
2 Correct 358 ms 132216 KB Output is correct
3 Correct 162 ms 128376 KB Output is correct
4 Correct 242 ms 132204 KB Output is correct
5 Correct 322 ms 132088 KB Output is correct
6 Correct 242 ms 132472 KB Output is correct
7 Correct 238 ms 132344 KB Output is correct
8 Correct 253 ms 132228 KB Output is correct
9 Correct 365 ms 132344 KB Output is correct
10 Correct 274 ms 132344 KB Output is correct

Subtask #3
14.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1889 ms 233272 KB Output is correct
2 Correct 1612 ms 230780 KB Output is correct
3 Correct 1905 ms 233596 KB Output is correct
4 Incorrect 1822 ms 251516 KB Output isn't correct
5 Execution timed out 2099 ms 250000 KB Time limit exceeded
6 Execution timed out 2099 ms 235128 KB Time limit exceeded
7 Execution timed out 2103 ms 239480 KB Time limit exceeded
8 Execution timed out 2054 ms 241908 KB Time limit exceeded
9 Execution timed out 2100 ms 242536 KB Time limit exceeded
10 Execution timed out 2100 ms 242168 KB Time limit exceeded
11 Incorrect 1914 ms 251372 KB Output isn't correct
12 Execution timed out 2077 ms 250096 KB Time limit exceeded
13 Execution timed out 2091 ms 246260 KB Time limit exceeded
14 Correct 1933 ms 247728 KB Output is correct
15 Execution timed out 2106 ms 249096 KB Time limit exceeded
16 Incorrect 1148 ms 233580 KB Output isn't correct
17 Correct 1908 ms 233204 KB Output is correct
18 Correct 1908 ms 233720 KB Output is correct
19 Correct 1611 ms 230776 KB Output is correct
20 Execution timed out 2061 ms 232184 KB Time limit exceeded