Submission #3196301
Source Code Expand
#include <bits/stdc++.h> #define each(i, c) for (auto& i : c) #define unless(cond) if (!(cond)) using namespace std; typedef long long int lli; typedef unsigned long long ull; typedef complex<double> point; template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; } template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; } const int N = 2 * 1e5 + 5; const int M = 'z' + 5; int g[N][M]; const int inf = 1 << 28; int memo[N]; int path[N]; int rec(int curr) { int& ret = memo[curr]; if (ret != -1) return ret; int mn = inf; for (char c = 'a'; c <= 'z'; ++c) { if (!g[curr][c]) { path[curr] = -1 * int(c); return ret = 0; } int len = rec(g[curr][c]) + 1; if (len < mn) { mn = len; path[curr] = g[curr][c]; } } return ret = mn; } int main(int argc, char *argv[]) { ios_base::sync_with_stdio(0); cin.tie(0); string s; while (cin >> s) { s = "@" + s; fill(&g[0][0], &g[N - 1][M - 1] + 1, 0); for (int i = s.size() - 2; 0 <= i; --i) { for (char c = 'a'; c <= 'z'; ++c) { g[i][c] = g[i + 1][c]; } g[i][s[i + 1]] = i + 1; } fill(memo, memo + N, -1); fill(path, path + N, -1); rec(0); string t; for (int i = 0; ; i = path[i]) { if (i < 0) { t += abs(i); break; } t += s[i]; } cout << t.substr(1) << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Don't Be a Subsequence |
User | Johniel |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1655 Byte |
Status | AC |
Exec Time | 70 ms |
Memory | 101712 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 | 31 ms | 100992 KB |
10.txt | AC | 69 ms | 101712 KB |
11.txt | AC | 69 ms | 101712 KB |
12.txt | AC | 69 ms | 101712 KB |
13.txt | AC | 69 ms | 101712 KB |
14.txt | AC | 69 ms | 101712 KB |
15.txt | AC | 69 ms | 101712 KB |
16.txt | AC | 69 ms | 101712 KB |
17.txt | AC | 69 ms | 101712 KB |
18.txt | AC | 70 ms | 101712 KB |
19.txt | AC | 70 ms | 101712 KB |
2.txt | AC | 31 ms | 100992 KB |
20.txt | AC | 69 ms | 101712 KB |
21.txt | AC | 69 ms | 101712 KB |
22.txt | AC | 69 ms | 101712 KB |
23.txt | AC | 70 ms | 101712 KB |
24.txt | AC | 69 ms | 101712 KB |
25.txt | AC | 68 ms | 101712 KB |
26.txt | AC | 67 ms | 101712 KB |
27.txt | AC | 68 ms | 101712 KB |
28.txt | AC | 68 ms | 101712 KB |
29.txt | AC | 68 ms | 101712 KB |
3.txt | AC | 32 ms | 101120 KB |
30.txt | AC | 60 ms | 101712 KB |
4.txt | AC | 32 ms | 101120 KB |
5.txt | AC | 51 ms | 101356 KB |
6.txt | AC | 51 ms | 101356 KB |
7.txt | AC | 69 ms | 101712 KB |
8.txt | AC | 69 ms | 101712 KB |
9.txt | AC | 69 ms | 101712 KB |
sample1.txt | AC | 31 ms | 100992 KB |
sample2.txt | AC | 31 ms | 100992 KB |
sample3.txt | AC | 31 ms | 100992 KB |