Submission #1525166


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;
}

int dp[ten(5) * 2 + 10][26];
int pv[ten(5) * 2 + 10][26];

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

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

			if (swaped) {
				pv[i + 1][k] = j;
			}
		}
	}

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

	string ans;
	for (int i = sz(s); i > 0; i--) {
		int p = pv[i][idx];
		if (dp[i - 1][p] != dp[i][idx]) {
			ans.push_back('a' + idx);
		}
		idx = p;
	}
	ans.push_back('a' + idx);
	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 0
Code Size 4665 Byte
Status
Exec Time 240 ms
Memory 41220 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 0 / 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 22400 KB
10.txt 233 ms 41220 KB
11.txt 233 ms 41220 KB
12.txt 232 ms 41220 KB
13.txt 233 ms 41220 KB
14.txt 234 ms 41220 KB
15.txt 234 ms 41220 KB
16.txt 234 ms 41220 KB
17.txt 236 ms 41220 KB
18.txt 237 ms 41220 KB
19.txt 238 ms 41220 KB
2.txt 8 ms 22528 KB
20.txt 239 ms 41220 KB
21.txt 240 ms 41220 KB
22.txt 240 ms 41220 KB
23.txt 240 ms 41220 KB
24.txt 228 ms 41220 KB
25.txt 225 ms 41220 KB
26.txt 224 ms 41220 KB
27.txt 225 ms 41220 KB
28.txt 226 ms 41220 KB
29.txt 223 ms 41220 KB
3.txt 18 ms 23552 KB
30.txt 223 ms 41220 KB
4.txt 18 ms 23552 KB
5.txt 119 ms 32896 KB
6.txt 120 ms 32896 KB
7.txt 233 ms 41220 KB
8.txt 234 ms 41220 KB
9.txt 234 ms 41220 KB
sample1.txt 7 ms 22400 KB
sample2.txt 6 ms 22400 KB
sample3.txt 6 ms 22528 KB