oj.uz

답안 #491282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491282 2021-12-01T10:32:14 Z AdamGS Vim (BOI13_vim) C++14
11.1111 / 100
 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';
}

Subtask #1
11.1111111111 / 50.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 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