Submission #1627200

---

Source Code Expand

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;

signed main(){
	string s,ans = "";
	int k,n,pos = -1,sum = 0,dp[1000010] = {},su[1000010] = {};
	vector<int> ind[26];
	cin >> s >> k;
	n = s.length();
	dp[n + 1] = -1;
	for(int i = 0;i < n;i++) ind[s[i] - 'a'].push_back(i);
	for(int i = n - 1;i >= 0;i--){
		int next = upper_bound(ind[s[i] - 'a'].begin(),ind[s[i] - 'a'].end(),i) - ind[s[i] - 'a'].begin();
		if(next >= ind[s[i] - 'a'].size()) next = n;
		else next = ind[s[i] - 'a'][next];
		dp[i] = min((int)4e18,dp[i + 1] - dp[next + 1] + dp[i + 1]);
		su[i] = min((int)2e18,dp[i] - dp[i + 1] + su[next]);
		dp[i] = min((int)2e18,dp[i]);
	}
	while(1){
		if(sum >= k) break;
		bool flag = false;
		for(int i = 0;i < 26;i++){
			int next = upper_bound(ind[i].begin(),ind[i].end(),pos) - ind[i].begin();
			if(next >= ind[i].size()) continue;
			if(su[ind[i][next]] + sum >= k){
				ans += (char)('a' + i);
				pos = ind[i][next];
				flag = true;
				break;
			}
			sum = min((int)2e18,sum + su[ind[i][next]]);
		}
		if(!flag) break;
		sum++;
	}
	if(ans != "") cout << ans << endl;
	else cout << "Eel" << endl;
	return 0;
}

Submission Info

Judge Result