Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
- namespace rngs = std::ranges;
- using ll = long long;
- using a2l = array<ll, 2>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- void solve()
- {
- string s;
- cin >> s;
- map<char, vl> pos;
- for (ll i = 0; i < s.size(); ++i) {
- char c = s[i];
- pos[c].push_back(i);
- }
- for (auto &[k, v] : pos)
- reverse(v.begin(), v.end());
- dbg(s, pos);
- ll sz = pos.size();
- string ans;
- for (ll i = 0, p = -1; i < sz; ++i) {
- char op = 'a';
- ll idx = -1;
- for (auto ch = 'a'; ch <= 'z'; ++ch) {
- if (pos.count(ch) == 0)
- continue;
- auto &v = pos[ch];
- while (!v.empty() && v.back() <= p)
- v.pop_back();
- ll id = v.back();
- bool valid = true;
- for (auto &[_, v2] : pos) {
- if (v2[0] < id) {
- valid = false;
- break;
- }
- }
- if (valid) {
- op = ch;
- idx = id;
- break;
- }
- }
- assert(idx != -1);
- dbg(op, pos);
- ans += op;
- pos.erase(op);
- p = idx;
- }
- dbg(ans);
- cout << ans << '\n';
- }
- int main(int argc, char **argv)
- {
- std::ios::sync_with_stdio(false);
- std::cin.tie(nullptr);
- solve();
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
