oj.uz

Submission #243081

# Submission time Handle Problem Language Result Execution time Memory
243081 2020-06-30T09:16:26 Z ffao Vim (BOI13_vim) C++14
50 / 100
 2000 ms 266248 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) {
        for (int idx = 0; idx < JMPS; idx++) if (jmp[nextE][letdst][idx+1] != n) {
            int dest = jmp[nextE][letdst][idx+1];
            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, idx, 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));
        }
    }

    cout << ans + rem << endl;
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 124152 KB Output is correct
2 Correct 119 ms 124152 KB Output is correct
3 Correct 81 ms 123768 KB Output is correct
4 Correct 196 ms 124912 KB Output is correct
5 Correct 211 ms 125932 KB Output is correct
6 Correct 481 ms 128104 KB Output is correct
7 Correct 265 ms 124916 KB Output is correct
8 Correct 64 ms 122876 KB Output is correct
9 Correct 64 ms 122872 KB Output is correct
10 Correct 64 ms 123004 KB Output is correct
11 Correct 64 ms 122872 KB Output is correct
12 Correct 64 ms 122872 KB Output is correct
13 Correct 133 ms 124232 KB Output is correct
14 Correct 126 ms 124144 KB Output is correct
15 Correct 86 ms 123896 KB Output is correct
16 Correct 134 ms 124024 KB Output is correct
17 Correct 219 ms 125936 KB Output is correct
18 Correct 175 ms 124400 KB Output is correct
19 Correct 110 ms 123928 KB Output is correct
20 Correct 132 ms 124024 KB Output is correct
21 Correct 200 ms 124936 KB Output is correct
22 Correct 211 ms 125808 KB Output is correct
23 Correct 120 ms 124408 KB Output is correct
24 Correct 255 ms 125932 KB Output is correct
25 Correct 202 ms 125932 KB Output is correct
26 Correct 289 ms 125936 KB Output is correct
27 Correct 479 ms 128304 KB Output is correct
28 Correct 483 ms 128104 KB Output is correct
29 Correct 273 ms 125044 KB Output is correct
30 Correct 179 ms 124408 KB Output is correct
31 Correct 324 ms 125936 KB Output is correct
32 Correct 245 ms 125936 KB Output is correct
33 Correct 283 ms 125936 KB Output is correct
34 Correct 412 ms 128132 KB Output is correct
35 Correct 337 ms 125984 KB Output is correct
36 Correct 275 ms 125092 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 140388 KB Time limit exceeded
2 Execution timed out 2053 ms 140384 KB Time limit exceeded
3 Execution timed out 2091 ms 136664 KB Time limit exceeded
4 Execution timed out 2081 ms 140328 KB Time limit exceeded
5 Execution timed out 2088 ms 140400 KB Time limit exceeded
6 Execution timed out 2081 ms 148564 KB Time limit exceeded
7 Execution timed out 2092 ms 140280 KB Time limit exceeded
8 Execution timed out 2088 ms 140288 KB Time limit exceeded
9 Execution timed out 2090 ms 140384 KB Time limit exceeded
10 Execution timed out 2092 ms 136168 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 249464 KB Time limit exceeded
2 Execution timed out 2090 ms 238940 KB Time limit exceeded
3 Execution timed out 2099 ms 241704 KB Time limit exceeded
4 Execution timed out 2090 ms 258524 KB Time limit exceeded
5 Execution timed out 2089 ms 266248 KB Time limit exceeded
6 Execution timed out 2099 ms 243296 KB Time limit exceeded
7 Execution timed out 2112 ms 247312 KB Time limit exceeded
8 Execution timed out 2099 ms 257876 KB Time limit exceeded
9 Execution timed out 2097 ms 256836 KB Time limit exceeded
10 Execution timed out 2094 ms 250176 KB Time limit exceeded
11 Execution timed out 2104 ms 258576 KB Time limit exceeded
12 Execution timed out 2096 ms 266248 KB Time limit exceeded
13 Execution timed out 2104 ms 254248 KB Time limit exceeded
14 Execution timed out 2115 ms 251612 KB Time limit exceeded
15 Execution timed out 2113 ms 257012 KB Time limit exceeded
16 Execution timed out 2115 ms 248016 KB Time limit exceeded
17 Execution timed out 2091 ms 249500 KB Time limit exceeded
18 Execution timed out 2114 ms 241500 KB Time limit exceeded
19 Execution timed out 2105 ms 238812 KB Time limit exceeded
20 Execution timed out 2092 ms 240368 KB Time limit exceeded