Submission #1527259


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
int reader(string& c) { int i; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c.push_back(i); for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c.push_back(i); }; return sz(c); }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const string& x, char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerArr(vector<T>& x) { writerArr(x.data(), (int)x.size()); }

template<class T> void chmin(T& a, const T& b) { if (a > b) a = b; }
template<class T> void chmax(T& a, const T& b) { if (a < b) a = b; }

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
ll mod_pow(ll a, ll n, ll mod) {
	ll ret = 1;
	ll p = a % mod;
	while (n) {
		if (n & 1) ret = ret * p % mod;
		p = p * p % mod;
		n >>= 1;
	}
	return ret;
}
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }

const int MOD = ten(9) + 7;

bool chmin(int& a, int b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

bool chmin(Pii& a, Pii b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}


int dp[ten(5) * 2 + 10][26];
vector<int> nidx[26];

int main() {
	memset(dp, 0x2f, sizeof(dp));
	FOR(i, 26) dp[0][i] = 1;

	string s; reader(s);
	FOR(i, sz(s)) {
		nidx[s[i] -'a'].push_back(i);
	}

	reverse(s.begin(), s.end());
	FOR(i, sz(s)) {
		FOR(j, 26) FOR(k, 26) {
			int nxt;
			if (j == k) {
				if (s[i] == 'a' + j) {
					nxt = dp[i][j] + 1;
				} else {
					nxt = dp[i][j];
				}
			} else {
				nxt = dp[i][j] + 1;
			}
			chmin(dp[i + 1][k], nxt);
		}
	}

	int mn = sz(s);
	FOR(i, 26) {
		chmin(mn, dp[sz(s)][i]);
	}

	string ans;
	int cur = 0;
	while (cur <= sz(s)) {
		bool brk = false;

		FOR(i, 26) {
			auto it = lower_bound(nidx[i].begin(), nidx[i].end(), cur);
			if (it == nidx[i].end()) {
				ans.push_back('a' + i);
				cur = sz(s) + 1;
				break;
			}
			int ncur = *it + 1;

			int mn2 = ten(5) * 2;
			FOR(i, 26) {
				chmin(mn2, dp[sz(s) - ncur][i]);
			}
			if (sz(ans) + mn2 + 1 == mn) {
				ans.push_back('a' + i);
				cur = ncur;
				break;
			}
		}
	}
	cout << ans << endl;

	return 0;
}

Submission Info

Submission Time
Task E - Don't Be a Subsequence
User math
Language C++14 (GCC 5.4.1)
Score 600
Code Size 4972 Byte
Status
Exec Time 268 ms
Memory 21764 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 600 / 600 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 7 ms 20608 KB
10.txt 262 ms 21636 KB
11.txt 261 ms 21764 KB
12.txt 260 ms 21636 KB
13.txt 261 ms 21636 KB
14.txt 261 ms 21636 KB
15.txt 261 ms 21636 KB
16.txt 261 ms 21636 KB
17.txt 265 ms 21636 KB
18.txt 266 ms 21636 KB
19.txt 268 ms 21764 KB
2.txt 8 ms 20608 KB
20.txt 268 ms 21636 KB
21.txt 268 ms 21636 KB
22.txt 268 ms 21764 KB
23.txt 268 ms 21764 KB
24.txt 255 ms 21636 KB
25.txt 251 ms 21764 KB
26.txt 250 ms 21636 KB
27.txt 251 ms 21636 KB
28.txt 250 ms 21636 KB
29.txt 250 ms 21764 KB
3.txt 20 ms 20608 KB
30.txt 250 ms 21636 KB
4.txt 20 ms 20608 KB
5.txt 134 ms 21120 KB
6.txt 134 ms 21120 KB
7.txt 262 ms 21764 KB
8.txt 261 ms 21764 KB
9.txt 261 ms 21636 KB
sample1.txt 7 ms 20608 KB
sample2.txt 7 ms 20608 KB
sample3.txt 7 ms 20608 KB