Submission #3582008
Source Code Expand
#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <cstdio>
#include <string>
#include <bitset>
#include <list>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <functional>
#include <queue>
#include <regex>
#include <cassert>
#include <map>
// #include "bits/stdc++.h"
using namespace std;
namespace {
#define rep(i, N, M) for(int i=N, i##_len=(M); i<i##_len; ++i)
#define rep_skip(i, N, M, ...) for(int i=N, i##_len=(M); i<i##_len; i+=(skip))
#define rrep(i, N, M) for(int i=(M)-1, i##_len=(N-1); i>i##_len; --i)
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tll;
typedef tuple<ll, ll, ll, ll> tll4;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
typedef priority_queue<ll> pqll;
typedef priority_queue<pll, vector<pll>> pqpll;
typedef priority_queue<ll, vll, greater<ll>> pqll_greater;
typedef priority_queue<pll, vector<pll>, greater<pll>> pqpll_greater;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vec(a) vector<a>
#define perm(c) sort(all(c));for(bool c##perm=1;c##perm;c##perm=next_permutation(all(c)))
template<class T, class S>
T atbit(T n, S i) {
return (n >> i) % i;
}
template<class T>
T getbit(T i) {
return 1LL << i;
}
constexpr ll POW(ll n, ll m) {
ll res = 1;
rep(i, 0, m) {
res *= n;
}
return res;
}
vll getDivisors(ll n) {
vll res;
ll i = 1;
for (; i*i < n; i++) {
if (n%i == 0) {
res.push_back(i);
res.push_back(n / i);
}
}
if (i*i == n)res.push_back(i);
sort(res.begin(), res.end());
return res;
}
vll getDivisors(ll n, ll m) {
if (n > m) swap(n, m);
vll res;
ll i = 1;
for (; i*i < n; i++) {
if (n%i == 0) {
if (m%i == 0) res.push_back(i);
if (m % (n / i) == 0) res.push_back(n / i);
}
}
if (i*i == n) if (m%i == 0) res.push_back(i);
sort(res.begin(), res.end());
return res;
}
ll gcd(ll a, ll b) {
if (a%b == 0) return b;
else return gcd(b, a%b);
}
template<
typename Inputs,
typename Functor,
typename T = typename Inputs::value_type>
void sort_by(Inputs& inputs, Functor f) {
std::sort(std::begin(inputs), std::end(inputs),
[&f](const T& lhs, const T& rhs) { return f(lhs) < f(rhs); });
}
template<int I>
vll proj(vpll v) {
vll res(v.size());
rep(i, 0, v.size()) {
if (!I) res[i] = v[i].first;
else res[i] = v[i].second;
}
return res;
}
template<int I, class T>
vll proj(T v) {
vll res(v.size());
rep(i, 0, v.size()) {
res[i] = get<I>(v[i]);
}
return res;
}
vector<pll >prime_factorize(ll n) {
vector<pll> res;
for (ll p = 2; p*p <= n; ++p) {
if (n%p != 0)continue;
ll num = 0;
while (n%p == 0) { ++num; n /= p; }
res.push_back({ p,num });
}
if (n != 1) res.push_back(make_pair(n, 1));
return res;
}
}
ll MOD = 1000000007;
ll INF = 1LL << 60;
string alph = "abcdefghijklmnopqrstuvwxyz";
void min_str(string& a, const string& b){
if (a == "") {
a = b;
}
else if (a.size() > b.size()) {
a = b;
}
else if (a.size() == b.size() && a > b) {
a = b;
}
};
int main() {
string A;
cin >> A;
ll n = A.size();
vector<string> dp(26, "");
vvll next(n, vll(26, n));
next[n - 1][A.back() - 'a'] = n - 1;
rrep(i, 0, n - 1) {
int chr = A[i] - 'a';
rep(j, 0, 26) {
if (j != chr) next[i][j] = next[i + 1][j];
else next[i][j] = i;
}
}
//dp[n - 1] = A.back()== 'a'? 'b':'a';
rep(c, 0, 26) {
if(A.back() != alph[c]) dp[c]=alph[c];
else dp[c] = alph.substr(c, 1) + 'a';
}
rrep(i, 0, n) {
int ch = A[i] - 'a';
string ret= A.substr(i, 1) + dp[0];
rep(c, 1, 26) {
min_str(ret, A.substr(i,1) + dp[c]);
}
dp[ch] = ret;
/*auto dp_b = dp;
rrep(c, 0, 26) {
if (A[i] == alph[c]) {
if (next[i][c] == n) {
if (dp[c] == "") dp[c] = alph.substr(c, 1);
}
else {
if (dp[c].size() == 0) {
auto k = next[i][c];
if (k + 1 < n) {
min_str(dp[c], dp[c]);
}
else {
min_str(dp[i], alph.substr(c, 1) + 'a');
}
}
}
}
}*/
}
string res=dp[0];
rep(i, 0, 26) min_str(res, dp[i]);
cout << res;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Don't Be a Subsequence |
User |
pontaryagin |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
4553 Byte |
Status |
AC |
Exec Time |
1869 ms |
Memory |
51076 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
1.txt |
AC |
2 ms |
256 KB |
10.txt |
AC |
987 ms |
48900 KB |
11.txt |
AC |
984 ms |
48900 KB |
12.txt |
AC |
976 ms |
48644 KB |
13.txt |
AC |
982 ms |
48900 KB |
14.txt |
AC |
988 ms |
50948 KB |
15.txt |
AC |
985 ms |
48900 KB |
16.txt |
AC |
1087 ms |
48900 KB |
17.txt |
AC |
1176 ms |
49028 KB |
18.txt |
AC |
1267 ms |
49028 KB |
19.txt |
AC |
1442 ms |
49156 KB |
2.txt |
AC |
4 ms |
512 KB |
20.txt |
AC |
1675 ms |
51076 KB |
21.txt |
AC |
1869 ms |
49156 KB |
22.txt |
AC |
1702 ms |
49156 KB |
23.txt |
AC |
1721 ms |
49156 KB |
24.txt |
AC |
712 ms |
48900 KB |
25.txt |
AC |
615 ms |
50948 KB |
26.txt |
AC |
602 ms |
48900 KB |
27.txt |
AC |
596 ms |
48900 KB |
28.txt |
AC |
603 ms |
48900 KB |
29.txt |
AC |
602 ms |
48900 KB |
3.txt |
AC |
32 ms |
2688 KB |
30.txt |
AC |
593 ms |
48900 KB |
4.txt |
AC |
32 ms |
2688 KB |
5.txt |
AC |
387 ms |
24576 KB |
6.txt |
AC |
386 ms |
24576 KB |
7.txt |
AC |
994 ms |
48900 KB |
8.txt |
AC |
985 ms |
48900 KB |
9.txt |
AC |
985 ms |
48900 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
2 ms |
256 KB |