Submission #1965159
Source Code Expand
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <cmath> #include <queue> #include <map> #include <unordered_map> #include <set> #include <functional> using namespace std; typedef long long ll; int ap[200005][30]; string anc[200005]; bool comp(const string &s, const string &t) { if (s == "-1") return true; if (t == "-1") return false; if (s.length() != t.length()) return s.length() > t.length(); return s >= t; } int main() { string s; cin >> s; for (int c = 0; c <= 'z' - 'a'; ++c) ap[s.length()][c] = -1; for (int i = (int)s.length() - 1; i >= 0; --i) { for (int c = 0; c <= 'z' - 'a'; ++c) { ap[i][c] = ('a' + c == s[i]) ? i : ap[i + 1][c]; } } deque<int> que; for (int i = 0; i <= (int)s.length(); ++i) anc[i] = "-1"; for (int c = 0; c <= 'z' - 'a'; ++c) { if (ap[0][c] == -1) { cout << (char)('a' + c) << endl; return 0; } que.push_back(ap[0][c]); anc[ap[0][c]] = ""; } string ans = "-1"; while (!que.empty()) { int pos = que.front(); que.pop_front(); string t = anc[pos] + s[pos]; for (int c = 0; c <= 'z' - 'a'; ++c) { if (ap[pos + 1][c] == -1) { if (comp(ans, (t + (char)('a' + c)))) ans = (t + (char)('a' + c)); continue; } if (comp(t, anc[ap[pos + 1][c]])) continue; que.push_back(ap[pos + 1][c]); anc[ap[pos + 1][c]] = t; } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Don't Be a Subsequence |
User | yoshnary |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1442 Byte |
Status | AC |
Exec Time | 610 ms |
Memory | 197636 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 | 1792 KB |
10.txt | AC | 265 ms | 100484 KB |
11.txt | AC | 261 ms | 99716 KB |
12.txt | AC | 259 ms | 97668 KB |
13.txt | AC | 261 ms | 99332 KB |
14.txt | AC | 261 ms | 98820 KB |
15.txt | AC | 261 ms | 99460 KB |
16.txt | AC | 261 ms | 99844 KB |
17.txt | AC | 319 ms | 145668 KB |
18.txt | AC | 347 ms | 161028 KB |
19.txt | AC | 439 ms | 191748 KB |
2.txt | AC | 3 ms | 1920 KB |
20.txt | AC | 571 ms | 197636 KB |
21.txt | AC | 590 ms | 194692 KB |
22.txt | AC | 610 ms | 189444 KB |
23.txt | AC | 610 ms | 186756 KB |
24.txt | AC | 232 ms | 52356 KB |
25.txt | AC | 202 ms | 34948 KB |
26.txt | AC | 215 ms | 42628 KB |
27.txt | AC | 205 ms | 34948 KB |
28.txt | AC | 207 ms | 35972 KB |
29.txt | AC | 224 ms | 54788 KB |
3.txt | AC | 12 ms | 4864 KB |
30.txt | AC | 236 ms | 53636 KB |
4.txt | AC | 12 ms | 4864 KB |
5.txt | AC | 120 ms | 34048 KB |
6.txt | AC | 119 ms | 33792 KB |
7.txt | AC | 266 ms | 101252 KB |
8.txt | AC | 263 ms | 99332 KB |
9.txt | AC | 265 ms | 100612 KB |
sample1.txt | AC | 2 ms | 1792 KB |
sample2.txt | AC | 2 ms | 1792 KB |
sample3.txt | AC | 2 ms | 1792 KB |