| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 491282 |
2021-12-01T10:32:14 Z |
AdamGS |
Vim (BOI13_vim) |
C++14 |
|
292 ms |
19392 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=7e4+7, INF=1e9+7;
vector<pair<int,int>>V[LIM];
int nxt[LIM][10], odl[LIM][10], odl2[LIM], kiedy[10];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, ans=INF, x=0;
string s;
cin >> n >> s;
rep(i, n) {
if(s[i]=='e') {
s[i]='a';
x=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];
odl[i][j]=INF;
if(j && kiedy[j]<INF) V[kiedy[j]].pb({i, 2});
}
odl2[i]=INF;
kiedy[s[i]-'a']=i;
}
rep(i, n-1) V[i].pb({i+1, 1});
priority_queue<pair<int,pair<int,int>>>q;
q.push({0, {x, 0}});
while(!q.empty()) {
int o=-q.top().st, p=q.top().nd.st; q.pop();
if(odl2[p]<=o) continue;
odl2[p]=o;
for(auto i : V[p]) if(odl2[i.st]>o+i.nd) {
q.push({-o-i.nd, {i.st, 0}});
}
}
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(o>=odl[a][b]) 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+odl2[a]+x-nxt[p][0]);
}
for(int i=1; i<10; ++i) if(nxt[a][i]<INF && nxt[a][i]>=p) {
if(nxt[p][0]>nxt[a][i]) {
if(odl[nxt[a][i]][i]==INF) q.push({-o-2, {nxt[a][i], 0}});
} else {
int mi=INF, c=i, jaki=-1;
for(int j=1; j<10; ++j) {
if(nxt[nxt[p][0]][j]<mi) {
mi=nxt[nxt[p][0]][j];
jaki=j;
}
}
if(nxt[a][i]==mi) c=0;
if(odl[mi][c]==INF) {
int xdd=0;
if(nxt[a][jaki]<nxt[p][jaki]) xdd=2;
q.push({-o-2-nxt[a][i]+nxt[p][0]-xdd, {mi, c}});
}
}
}
}
rep(i, n) if(s[i]=='a') ++ans;
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2124 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
1960 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 5 |
Correct |
3 ms |
2124 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
2112 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 8 |
Correct |
1 ms |
1868 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1968 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1868 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1960 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1948 KB |
Output is correct |
| 13 |
Incorrect |
3 ms |
2124 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 17 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 19 |
Correct |
2 ms |
1996 KB |
Output is correct |
| 20 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 21 |
Incorrect |
2 ms |
2092 KB |
Output isn't correct |
| 22 |
Correct |
3 ms |
2124 KB |
Output is correct |
| 23 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 24 |
Incorrect |
3 ms |
2124 KB |
Output isn't correct |
| 25 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 26 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 27 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 28 |
Incorrect |
3 ms |
2092 KB |
Output isn't correct |
| 29 |
Incorrect |
3 ms |
2092 KB |
Output isn't correct |
| 30 |
Incorrect |
2 ms |
1996 KB |
Output isn't correct |
| 31 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 32 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 33 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 34 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 35 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| 36 |
Incorrect |
3 ms |
1996 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
3020 KB |
Output isn't correct |
| 2 |
Incorrect |
24 ms |
3068 KB |
Output isn't correct |
| 3 |
Incorrect |
11 ms |
2660 KB |
Output isn't correct |
| 4 |
Incorrect |
18 ms |
3116 KB |
Output isn't correct |
| 5 |
Incorrect |
23 ms |
3212 KB |
Output isn't correct |
| 6 |
Incorrect |
19 ms |
3472 KB |
Output isn't correct |
| 7 |
Incorrect |
18 ms |
3276 KB |
Output isn't correct |
| 8 |
Incorrect |
18 ms |
3120 KB |
Output isn't correct |
| 9 |
Incorrect |
23 ms |
3020 KB |
Output isn't correct |
| 10 |
Incorrect |
19 ms |
3028 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
17436 KB |
Output isn't correct |
| 2 |
Incorrect |
149 ms |
13048 KB |
Output isn't correct |
| 3 |
Incorrect |
180 ms |
14040 KB |
Output isn't correct |
| 4 |
Incorrect |
193 ms |
18076 KB |
Output isn't correct |
| 5 |
Incorrect |
268 ms |
19352 KB |
Output isn't correct |
| 6 |
Incorrect |
207 ms |
15180 KB |
Output isn't correct |
| 7 |
Incorrect |
292 ms |
18368 KB |
Output isn't correct |
| 8 |
Incorrect |
268 ms |
18140 KB |
Output isn't correct |
| 9 |
Incorrect |
268 ms |
18352 KB |
Output isn't correct |
| 10 |
Incorrect |
245 ms |
15980 KB |
Output isn't correct |
| 11 |
Incorrect |
192 ms |
17972 KB |
Output isn't correct |
| 12 |
Incorrect |
272 ms |
19392 KB |
Output isn't correct |
| 13 |
Incorrect |
208 ms |
15464 KB |
Output isn't correct |
| 14 |
Incorrect |
169 ms |
14772 KB |
Output isn't correct |
| 15 |
Incorrect |
282 ms |
16612 KB |
Output isn't correct |
| 16 |
Incorrect |
162 ms |
15528 KB |
Output isn't correct |
| 17 |
Incorrect |
237 ms |
17452 KB |
Output isn't correct |
| 18 |
Incorrect |
182 ms |
13956 KB |
Output isn't correct |
| 19 |
Incorrect |
150 ms |
13044 KB |
Output isn't correct |
| 20 |
Incorrect |
249 ms |
14788 KB |
Output isn't correct |
