| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1040948 | ArthuroWich | Type Printer (IOI08_printer) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int trie[2500][26], le[2500][26], co = 1, en[2500];
vector<char> ans;
void insert(string s) {
int n = 0;
for (int i = 0; i < s.length(); i++) {
char c = s[i];
le[n][c-'a'] = max(le[n][c-'a'], s.length()-i);
if (!trie[n][c-'a']) {
trie[n][c-'a'] = co;
co++;
}
n = trie[n][c-'a'];
}
en[n] = 1;
}
void dfs(int a) {
if (en[a]) {
ans.push_back('P');
}
vector<pair<int, int>> v;
for (int i = 0; i < 26; i++) {
if (trie[a][i]) {
v.push_back({le[a][i], i});
}
}
sort(v.begin(), v.end());
for (auto [_, i] : v) {
ans.push_back((char)(i+'a'));
dfs(trie[a][i]);
ans.push_back('-');
}
}
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
insert(s);
}
dfs(0);
while(!ans.empty() && ans.back() == '-') {
ans.pop_back();
}
cout << ans.size() << endl;
for (char c : ans) {
cout << c << endl;
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
t = 1;
while(t--) {
solve();
}
}