Submission #1607787
Source Code Expand
#include <bits/stdc++.h> using namespace std; /** whole range */ #define whole(xs) (xs).begin(), (xs).end() namespace { string s; void input() { cin >> s; } const int INF = 1<<28; vector<int> first; vector<vector<int>> table; void construct_table(const string& s) { table = vector<vector<int>>(s.size(), vector<int>(26, INF)); vector<int> last(26, INF); for (int i = s.size() - 1; i >= 0; i--) { int cur_char = s[i] - 'a'; for (char c = 'a'; c <= 'z'; c++) { int next_char = c - 'a'; table[i][next_char] = last[next_char]; } last[cur_char] = i; } first = vector<int>(26, INF); for (int i = 0; i < s.size(); i++) { int cur_cindex = s[i] - 'a'; first[cur_cindex] = min(first[cur_cindex], i); } } /** output whole vector. ex) vector<int>{1, 2, 3} -> '1 2 3'. */ template<typename T> ostream& operator<<(ostream& os, const vector<T>& xs) { if (xs.empty()) return os; os << xs[0]; for (auto i = 1; i < xs.size(); i++) os << ' ' << xs[i]; return os; } void solve() { vector<int> found(26, false); int k = 1; int count = 0; for (int i = 0; i < s.size(); i++) { if (found[s[i] - 'a']) continue; found[s[i] - 'a'] = true; count++; if (count == 26) { k++; count = 0; fill(whole(found), false); } } construct_table(s); int n = s.size(); vector<int> dp(n + 1, INF); dp[n] = 0; for (int i = n - 1; i >= 0; i--) { auto& cur = dp[i]; for (int c = 0; c < 26; c++) { auto next_c = table[i][c]; if (next_c + 1 >= n) cur = 1; else cur = min(cur, dp[next_c + 1] + 1); } } int p = -1; string ans = ""; for (int i = 0; i < k; i++) { for (int c = 0; c < 26; c++) { auto next = p == -1 ? first[c] : table[p][c]; //cout << i << " : " << c << " " << next << endl; if (next >= INF) next = n; if (1 + i + dp[next] == k) { p = next + 1; ans.push_back(c + 'a'); break; } } } cout << ans << endl; assert(ans.size() == k); } } int main() { input(); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Don't Be a Subsequence |
User | izuru |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2689 Byte |
Status | RE |
Exec Time | 174 ms |
Memory | 27908 KB |
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 1 ms | 256 KB |
10.txt | RE | 174 ms | 27908 KB |
11.txt | RE | 139 ms | 27780 KB |
12.txt | RE | 137 ms | 27652 KB |
13.txt | RE | 137 ms | 27780 KB |
14.txt | RE | 137 ms | 27780 KB |
15.txt | RE | 137 ms | 27780 KB |
16.txt | RE | 136 ms | 27780 KB |
17.txt | RE | 143 ms | 27780 KB |
18.txt | RE | 144 ms | 27780 KB |
19.txt | RE | 139 ms | 27780 KB |
2.txt | WA | 1 ms | 384 KB |
20.txt | RE | 136 ms | 27780 KB |
21.txt | RE | 139 ms | 27780 KB |
22.txt | RE | 136 ms | 27780 KB |
23.txt | RE | 137 ms | 27780 KB |
24.txt | RE | 141 ms | 27780 KB |
25.txt | AC | 44 ms | 27780 KB |
26.txt | AC | 44 ms | 27780 KB |
27.txt | AC | 44 ms | 27780 KB |
28.txt | AC | 44 ms | 27780 KB |
29.txt | AC | 44 ms | 27780 KB |
3.txt | RE | 100 ms | 1664 KB |
30.txt | AC | 43 ms | 27780 KB |
4.txt | RE | 98 ms | 1664 KB |
5.txt | RE | 117 ms | 14080 KB |
6.txt | RE | 117 ms | 14080 KB |
7.txt | RE | 137 ms | 27780 KB |
8.txt | RE | 137 ms | 27780 KB |
9.txt | RE | 136 ms | 27780 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |