Submission #491282

#	Time	Username	Problem	Language	Result	Execution time	Memory
491282		AdamGS	Vim (BOI13_vim)	C++14	11.11 / 100	292 ms	19392 KiB

vim

#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.11111111111111 / 50
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40