oj.uz

Submission #243064

# Submission time Handle Problem Language Result Execution time Memory
243064 2020-06-30T08:49:03 Z ffao Vim (BOI13_vim) C++14
73.2222 / 100
 2000 ms 72096 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;

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

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 <= 10; 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 <= 10; 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
47.2222222222 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 34424 KB Output is correct
2 Correct 25 ms 34304 KB Output is correct
3 Correct 26 ms 34176 KB Output is correct
4 Correct 32 ms 34304 KB Output is correct
5 Correct 34 ms 34304 KB Output is correct
6 Correct 42 ms 34432 KB Output is correct
7 Correct 35 ms 34304 KB Output is correct
8 Correct 22 ms 34048 KB Output is correct
9 Correct 23 ms 34040 KB Output is correct
10 Correct 22 ms 33920 KB Output is correct
11 Correct 22 ms 34048 KB Output is correct
12 Correct 22 ms 34048 KB Output is correct
13 Correct 30 ms 34304 KB Output is correct
14 Correct 25 ms 34176 KB Output is correct
15 Correct 26 ms 34304 KB Output is correct
16 Correct 26 ms 34176 KB Output is correct
17 Correct 34 ms 34432 KB Output is correct
18 Correct 31 ms 34304 KB Output is correct
19 Incorrect 27 ms 34176 KB Output isn't correct
20 Correct 31 ms 34304 KB Output is correct
21 Correct 33 ms 34304 KB Output is correct
22 Correct 34 ms 34424 KB Output is correct
23 Correct 25 ms 34304 KB Output is correct
24 Correct 33 ms 34304 KB Output is correct
25 Correct 30 ms 34304 KB Output is correct
26 Correct 33 ms 34432 KB Output is correct
27 Correct 43 ms 34432 KB Output is correct
28 Correct 43 ms 34552 KB Output is correct
29 Incorrect 35 ms 34432 KB Output isn't correct
30 Correct 27 ms 34304 KB Output is correct
31 Correct 32 ms 34304 KB Output is correct
32 Correct 33 ms 34304 KB Output is correct
33 Correct 34 ms 34304 KB Output is correct
34 Correct 41 ms 34424 KB Output is correct
35 Correct 41 ms 34432 KB Output is correct
36 Correct 35 ms 34304 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 36728 KB Output is correct
2 Correct 293 ms 36856 KB Output is correct
3 Correct 117 ms 35704 KB Output is correct
4 Correct 190 ms 36856 KB Output is correct
5 Correct 256 ms 36856 KB Output is correct
6 Correct 177 ms 36992 KB Output is correct
7 Correct 174 ms 36964 KB Output is correct
8 Correct 195 ms 36984 KB Output is correct
9 Correct 289 ms 36984 KB Output is correct
10 Correct 216 ms 36984 KB Output is correct

Subtask #3
16.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1745 ms 66168 KB Output is correct
2 Correct 1411 ms 65360 KB Output is correct
3 Correct 1712 ms 66352 KB Output is correct
4 Incorrect 1626 ms 72096 KB Output isn't correct
5 Execution timed out 2074 ms 71028 KB Time limit exceeded
6 Execution timed out 2088 ms 66680 KB Time limit exceeded
7 Execution timed out 2082 ms 68088 KB Time limit exceeded
8 Execution timed out 2087 ms 68976 KB Time limit exceeded
9 Execution timed out 2090 ms 70124 KB Time limit exceeded
10 Execution timed out 2088 ms 68728 KB Time limit exceeded
11 Incorrect 1642 ms 72004 KB Output isn't correct
12 Execution timed out 2053 ms 71092 KB Time limit exceeded
13 Correct 1924 ms 70000 KB Output is correct
14 Correct 1651 ms 70260 KB Output is correct
15 Execution timed out 2094 ms 70780 KB Time limit exceeded
16 Incorrect 1022 ms 67604 KB Output isn't correct
17 Correct 1750 ms 66168 KB Output is correct
18 Correct 1739 ms 66304 KB Output is correct
19 Correct 1426 ms 65500 KB Output is correct
20 Execution timed out 2090 ms 65912 KB Time limit exceeded