| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 491275 |
2021-12-01T09:40:46 Z |
AdamGS |
Vim (BOI13_vim) |
C++14 |
|
416 ms |
177452 KB |
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define st first
#define nd second
const int LIM=7e4+7, INF=1e9+7;
vector<pair<int,int>>S[LIM];
vector<pair<pair<int,int>,int>>V[LIM][10];
int kiedy[10], nxt[LIM][10], ostatni[LIM], odl[LIM][10];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, lst=-1;
string s;
cin >> n >> s;
rep(i, n) {
if(s[i]=='e') {
s[i]='a';
lst=i;
} else if(s[i]=='a') s[i]='e';
}
rep(i, 10) kiedy[i]=INF;
for(int i=n-1; i>=0; --i) {
rep(j, 10) nxt[i][j]=kiedy[j];
for(int j=1; j<10; ++j) if(kiedy[j]<INF) {
S[kiedy[j]].pb({j, 2});
}
if(i<n-1) S[i].pb({i+1, 1});
kiedy[s[i]-'a']=i;
ostatni[i]=INF;
}
priority_queue<pair<int,pair<int,int>>>q;
q.push({0, {lst, 0}});
while(!q.empty()) {
int o=-q.top().st, p=q.top().nd.st; q.pop();
if(ostatni[p]<=o) continue;
ostatni[p]=o;
for(auto i : S[p]) if(ostatni[i.st]>o+i.nd) {
q.push({-o-i.nd, {i.st, 0}});
}
}
rep(i, n) {
for(int j=1; j<10; ++j) if(nxt[i][j]<INF) {
if(nxt[i][0]>nxt[i][j]) {
V[i][0].pb({{nxt[i][j], 0}, 2});
} else {
int c=j;
if(nxt[i][0]+1==nxt[i][j]) c=0;
V[i][0].pb({{nxt[i][0]+1, c}, 2+nxt[i][j]-nxt[i][0]});
}
}
for(int j=1; j<10; ++j) if(nxt[i][j]<INF) {
for(int l=1; l<10; ++l) if(nxt[i][l]<INF) {
int p=nxt[i][j];
if(nxt[p][0]>nxt[i][l]) {
V[i][j].pb({{nxt[i][l], 0}, 2});
} else {
int c=l;
if(nxt[p][0]+1==nxt[i][l]) c=0;
V[i][j].pb({{nxt[p][0]+1, c}, 2+nxt[i][l]-nxt[p][0]});
}
}
}
}
int ans=INF;
rep(i, n) rep(j, 10) odl[i][j]=INF;
q.push({0, {0, 0}});
while(!q.empty()) {
int o=-q.top().st, a=q.top().nd.st, b=q.top().nd.nd; q.pop();
if(odl[a][b]<=o) continue;
odl[a][b]=o;
int p=nxt[a][b];
if(!b) p=a;
if(nxt[p][0]==INF) {
ans=min(ans, o);
} else {
ans=min(ans, o+ostatni[a]+lst-nxt[p][0]);
}
for(auto i : V[a][b]) if(odl[i.st.st][i.st.nd]>o+i.nd) {
q.push({-o-i.nd, {i.st.st, i.st.nd}});
}
}
rep(i, n) if(s[i]=='a') ++ans;
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
18656 KB |
Output isn't correct |
| 3 |
Incorrect |
11 ms |
18672 KB |
Output isn't correct |
| 4 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 5 |
Correct |
12 ms |
19276 KB |
Output is correct |
| 6 |
Incorrect |
13 ms |
19504 KB |
Output isn't correct |
| 7 |
Correct |
11 ms |
18920 KB |
Output is correct |
| 8 |
Incorrect |
9 ms |
18400 KB |
Output isn't correct |
| 9 |
Correct |
9 ms |
18380 KB |
Output is correct |
| 10 |
Correct |
9 ms |
18336 KB |
Output is correct |
| 11 |
Correct |
9 ms |
18380 KB |
Output is correct |
| 12 |
Correct |
10 ms |
18380 KB |
Output is correct |
| 13 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 14 |
Incorrect |
10 ms |
18736 KB |
Output isn't correct |
| 15 |
Incorrect |
10 ms |
18660 KB |
Output isn't correct |
| 16 |
Incorrect |
10 ms |
18636 KB |
Output isn't correct |
| 17 |
Correct |
11 ms |
19376 KB |
Output is correct |
| 18 |
Correct |
11 ms |
18836 KB |
Output is correct |
| 19 |
Incorrect |
10 ms |
18636 KB |
Output isn't correct |
| 20 |
Incorrect |
11 ms |
18764 KB |
Output isn't correct |
| 21 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 22 |
Correct |
13 ms |
19276 KB |
Output is correct |
| 23 |
Correct |
11 ms |
18892 KB |
Output is correct |
| 24 |
Correct |
13 ms |
19404 KB |
Output is correct |
| 25 |
Correct |
11 ms |
18892 KB |
Output is correct |
| 26 |
Correct |
11 ms |
18796 KB |
Output is correct |
| 27 |
Correct |
12 ms |
19404 KB |
Output is correct |
| 28 |
Incorrect |
13 ms |
19404 KB |
Output isn't correct |
| 29 |
Incorrect |
11 ms |
18884 KB |
Output isn't correct |
| 30 |
Incorrect |
11 ms |
18892 KB |
Output isn't correct |
| 31 |
Correct |
11 ms |
19296 KB |
Output is correct |
| 32 |
Incorrect |
11 ms |
18892 KB |
Output isn't correct |
| 33 |
Correct |
11 ms |
18892 KB |
Output is correct |
| 34 |
Correct |
12 ms |
19316 KB |
Output is correct |
| 35 |
Incorrect |
12 ms |
19276 KB |
Output isn't correct |
| 36 |
Correct |
12 ms |
18892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
29388 KB |
Output isn't correct |
| 2 |
Incorrect |
40 ms |
29516 KB |
Output isn't correct |
| 3 |
Incorrect |
24 ms |
24652 KB |
Output isn't correct |
| 4 |
Incorrect |
35 ms |
29392 KB |
Output isn't correct |
| 5 |
Incorrect |
38 ms |
29652 KB |
Output isn't correct |
| 6 |
Incorrect |
35 ms |
30048 KB |
Output isn't correct |
| 7 |
Incorrect |
32 ms |
26824 KB |
Output isn't correct |
| 8 |
Incorrect |
35 ms |
29300 KB |
Output isn't correct |
| 9 |
Incorrect |
39 ms |
29492 KB |
Output isn't correct |
| 10 |
Incorrect |
32 ms |
24300 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
326 ms |
156592 KB |
Output isn't correct |
| 2 |
Incorrect |
203 ms |
81240 KB |
Output isn't correct |
| 3 |
Incorrect |
251 ms |
90180 KB |
Output isn't correct |
| 4 |
Incorrect |
258 ms |
90652 KB |
Output isn't correct |
| 5 |
Incorrect |
383 ms |
177420 KB |
Output isn't correct |
| 6 |
Incorrect |
343 ms |
156500 KB |
Output isn't correct |
| 7 |
Incorrect |
391 ms |
164576 KB |
Output isn't correct |
| 8 |
Incorrect |
356 ms |
167028 KB |
Output isn't correct |
| 9 |
Incorrect |
368 ms |
146720 KB |
Output isn't correct |
| 10 |
Incorrect |
366 ms |
165216 KB |
Output isn't correct |
| 11 |
Incorrect |
244 ms |
90552 KB |
Output isn't correct |
| 12 |
Incorrect |
388 ms |
177452 KB |
Output isn't correct |
| 13 |
Incorrect |
261 ms |
98544 KB |
Output isn't correct |
| 14 |
Incorrect |
232 ms |
91096 KB |
Output isn't correct |
| 15 |
Incorrect |
416 ms |
173840 KB |
Output isn't correct |
| 16 |
Incorrect |
200 ms |
80940 KB |
Output isn't correct |
| 17 |
Incorrect |
345 ms |
157004 KB |
Output isn't correct |
| 18 |
Incorrect |
244 ms |
90180 KB |
Output isn't correct |
| 19 |
Incorrect |
207 ms |
81220 KB |
Output isn't correct |
| 20 |
Incorrect |
356 ms |
152932 KB |
Output isn't correct |
