| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 243062 |
2020-06-30T08:37:54 Z |
ffao |
Vim (BOI13_vim) |
C++14 |
|
2000 ms |
71840 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 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++) {
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(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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
34304 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
34304 KB |
Output isn't correct |
| 3 |
Incorrect |
30 ms |
34168 KB |
Output isn't correct |
| 4 |
Incorrect |
34 ms |
34304 KB |
Output isn't correct |
| 5 |
Correct |
33 ms |
34304 KB |
Output is correct |
| 6 |
Incorrect |
43 ms |
34432 KB |
Output isn't correct |
| 7 |
Incorrect |
35 ms |
34304 KB |
Output isn't correct |
| 8 |
Correct |
22 ms |
33920 KB |
Output is correct |
| 9 |
Correct |
24 ms |
34040 KB |
Output is correct |
| 10 |
Incorrect |
23 ms |
33920 KB |
Output isn't correct |
| 11 |
Correct |
24 ms |
33920 KB |
Output is correct |
| 12 |
Correct |
23 ms |
33920 KB |
Output is correct |
| 13 |
Correct |
31 ms |
34304 KB |
Output is correct |
| 14 |
Incorrect |
26 ms |
34304 KB |
Output isn't correct |
| 15 |
Incorrect |
26 ms |
34304 KB |
Output isn't correct |
| 16 |
Incorrect |
26 ms |
34176 KB |
Output isn't correct |
| 17 |
Incorrect |
35 ms |
34424 KB |
Output isn't correct |
| 18 |
Incorrect |
30 ms |
34176 KB |
Output isn't correct |
| 19 |
Incorrect |
27 ms |
34176 KB |
Output isn't correct |
| 20 |
Correct |
32 ms |
34176 KB |
Output is correct |
| 21 |
Incorrect |
32 ms |
34304 KB |
Output isn't correct |
| 22 |
Correct |
34 ms |
34304 KB |
Output is correct |
| 23 |
Incorrect |
26 ms |
34304 KB |
Output isn't correct |
| 24 |
Incorrect |
32 ms |
34304 KB |
Output isn't correct |
| 25 |
Incorrect |
29 ms |
34304 KB |
Output isn't correct |
| 26 |
Incorrect |
31 ms |
34304 KB |
Output isn't correct |
| 27 |
Incorrect |
44 ms |
34424 KB |
Output isn't correct |
| 28 |
Incorrect |
43 ms |
34432 KB |
Output isn't correct |
| 29 |
Incorrect |
35 ms |
34304 KB |
Output isn't correct |
| 30 |
Incorrect |
28 ms |
34304 KB |
Output isn't correct |
| 31 |
Incorrect |
31 ms |
34304 KB |
Output isn't correct |
| 32 |
Incorrect |
31 ms |
34304 KB |
Output isn't correct |
| 33 |
Incorrect |
33 ms |
34304 KB |
Output isn't correct |
| 34 |
Incorrect |
44 ms |
34432 KB |
Output isn't correct |
| 35 |
Incorrect |
40 ms |
34424 KB |
Output isn't correct |
| 36 |
Incorrect |
35 ms |
34424 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
36860 KB |
Output isn't correct |
| 2 |
Incorrect |
292 ms |
36864 KB |
Output isn't correct |
| 3 |
Incorrect |
113 ms |
35832 KB |
Output isn't correct |
| 4 |
Incorrect |
191 ms |
36960 KB |
Output isn't correct |
| 5 |
Incorrect |
248 ms |
36736 KB |
Output isn't correct |
| 6 |
Incorrect |
173 ms |
36984 KB |
Output isn't correct |
| 7 |
Incorrect |
185 ms |
36856 KB |
Output isn't correct |
| 8 |
Incorrect |
193 ms |
36984 KB |
Output isn't correct |
| 9 |
Incorrect |
283 ms |
36856 KB |
Output isn't correct |
| 10 |
Incorrect |
210 ms |
36728 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1707 ms |
66036 KB |
Output isn't correct |
| 2 |
Incorrect |
1421 ms |
65220 KB |
Output isn't correct |
| 3 |
Incorrect |
1699 ms |
66292 KB |
Output isn't correct |
| 4 |
Incorrect |
1614 ms |
71840 KB |
Output isn't correct |
| 5 |
Execution timed out |
2059 ms |
70772 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2087 ms |
66468 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2083 ms |
67704 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2076 ms |
68472 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2096 ms |
70120 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2084 ms |
68704 KB |
Time limit exceeded |
| 11 |
Incorrect |
1589 ms |
71680 KB |
Output isn't correct |
| 12 |
Execution timed out |
2015 ms |
70900 KB |
Time limit exceeded |
| 13 |
Incorrect |
1890 ms |
69748 KB |
Output isn't correct |
| 14 |
Incorrect |
1624 ms |
70004 KB |
Output isn't correct |
| 15 |
Execution timed out |
2088 ms |
70772 KB |
Time limit exceeded |
| 16 |
Incorrect |
984 ms |
66408 KB |
Output isn't correct |
| 17 |
Incorrect |
1735 ms |
65928 KB |
Output isn't correct |
| 18 |
Incorrect |
1686 ms |
66168 KB |
Output isn't correct |
| 19 |
Incorrect |
1398 ms |
65144 KB |
Output isn't correct |
| 20 |
Execution timed out |
2083 ms |
65784 KB |
Time limit exceeded |
