// I stand with PALESTINE
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
// #define int long long
#define ff first
#define ss second
#define sz(a) (int) (a).size()
//template<class T, class C = null_type> using ordered_tree = tree<T, C, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long double ld;
namespace io {
template<typename F, typename S>
ostream &operator<<(ostream &os, const pair<F, S> &p) { return os << p.ff << " " << p.ss; }
template<typename F, typename S>
ostream &operator<<(ostream &os, const map<F, S> &mp) {
for (auto it: mp) { os << it << endl; }
return os;
}
template<typename F>
ostream &operator<<(ostream &os, const vector<F> &v) {
bool space = false;
for (F x: v) {
if (space) os << " ";
space = true;
os << x;
}
return os;
}
template<typename F>
ostream &operator<<(ostream &os, const deque<F> &d) {
bool space = false;
for (F x: d) {
if (space) os << " ";
space = true;
os << x;
}
return os;
}
template<typename F>
ostream &operator<<(ostream &os, const set<F> &st) {
bool space = false;
for (F x: st) {
if (space) os << " ";
space = true;
os << x;
}
return os;
}
template<typename F>
ostream &operator<<(ostream &os, const multiset<F> &st) {
bool space = false;
for (F x: st) {
if (space) os << " ";
space = true;
os << x << x;
}
return os;
}
template<typename F, typename S>
istream &operator>>(istream &is, pair<F, S> &p) { return is >> p.ff >> p.ss; }
template<typename F>
istream &operator>>(istream &is, vector<F> &v) {
for (F &x: v) { is >> x; }
return is;
}
long long fastread() {
char c;
long long d = 1, x = 0;
do c = getchar(); while (c == ' ' || c == '\n');
if (c == '-') c = getchar(), d = -1;
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return d * x;
}
static bool sep = false;
using std::to_string;
string to_string(bool x) {
return (x ? "true" : "false");
}
string to_string(const string &s) { return "\"" + s + "\""; }
string to_string(const char *s) { return "\"" + string(s) + "\""; }
string to_string(const char &c) {
string s;
s += c;
return "\'" + s + "\'";
}
template<typename Type>
string to_string(vector<Type>);
template<typename F, typename S>
string to_string(pair<F, S>);
template<typename Collection>
string to_string(Collection);
template<typename F, typename S>
string to_string(pair<F, S> p) { return "{" + to_string(p.ff) + ", " + to_string(p.ss) + "}"; }
template<typename Type>
string to_string(vector<Type> v) {
bool sep = false;
string s = "[";
for (Type x: v) {
if (sep) s += ", ";
sep = true;
s += to_string(x);
}
s += "]";
return s;
}
template<typename Collection>
string to_string(Collection collection) {
bool sep = false;
string s = "{";
for (auto x: collection) {
if (sep) s += ", ";
sep = true;
s += to_string(x);
}
s += "}";
return s;
}
void print() {
cout << endl;
sep = false;
}
template<typename F, typename... Other>
void print(F ff, Other... other) {
if (sep) cout << " | ";
sep = true;
cout << to_string(ff);
print(other...);
}
}
using namespace io;
namespace utils {
template<typename F, typename S>
inline void maxs(F &a, S b) { a = a > b ? a : b; }
template<typename F, typename S>
inline void mins(F &a, S b) { a = a < b ? a : b; }
template<typename F, typename S>
long long max(F a, S b) { return a > b ? a : b; }
template<typename F, typename S>
long long min(F a, S b) { return a < b ? a : b; }
constexpr long long operator "" _E(unsigned long long n) {
long long p = 1, a = 10;
for (int i = 0; i < n; i++) p *= a;
return p;
}
random_device rd;
mt19937 mt(rd());
template<typename T>
T rand(T l, T r) {
uniform_int_distribution<T> dist(l, r);
return dist(mt);
};
}
using namespace utils;
#ifdef sunnatov
#define print(...) cout << "[" << #__VA_ARGS__ << "]: "; io::print( __VA_ARGS__ );
#else
#define print( ... ) 42
#endif
const int mod = 9_E + 7;
const double EPS = 1e-7;
long long doxuya = 18_E + 10;
int INF = 9_E + 10;
const char nl = '\n';
int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
/*
*/
const int N = 5e5;
vector<vector<int>> out(N, vector(26, 0));
vector<int> par(N, -1), cnt(N), mx(N);
vector<bool> ex(N);
int z;
void add(const string &s) {
int x = 0;
cnt[0]++;
for (int i = 0; i < s.size(); i++) {
if (!out[x][s[i] - 'a']) {
out[x][s[i] - 'a'] = ++z;
par[z] = x;
}
x = out[x][s[i] - 'a'];
cnt[x]++;
mx[x] = max(mx[x], sz(s));
}
ex[x] = true;
}
void remove(const string &s) {
int x = 0;
cnt[0]--;
for (int i = 0; i < s.size(); i++) {
x = out[x][s[i] - 'a'];
cnt[x]--;
}
ex[x] = false;
}
void solution(istream &cin, ostream &cout, const int &test_case) {
int n;
cin >> n;
vector<string> s(n);
cin >> s;
for (int i = 0; i < n; i++) add(s[i]);
int x = 0;
vector<char> ans;
string way = "";
while (x != -1) {
if (!cnt[x]) {
x = par[x];
ans.emplace_back('-');
way.pop_back();
continue;
}
if (ex[x]) {
ans.emplace_back('P');
remove(way);
continue;
}
int best = -1;
for (int i = 0; i < 26; i++) {
if (!out[x][i] or !cnt[out[x][i]]) continue;
if (best == -1 or mx[out[x][i]] < mx[out[x][best]]) best = i;
}
x = out[x][best];
ans.emplace_back(best + 'a');
way += best + 'a';
}
while (!ans.empty() and ans.back() == '-') ans.pop_back();
cout << sz(ans) << nl;
for (char x: ans) cout << x << nl;
}
int32_t main() {
clock_t startTime = clock();
cin.tie(0)->sync_with_stdio(false);
srand(time(0));
std::istream &in(std::cin);
std::ostream &out(std::cout);
int32_t queries = 1;
#ifdef test_cases
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> queries;
#else
// cin >> queries;
#endif
for (int32_t test_case = 1; test_case <= queries; test_case++) {
print(test_case);
solution(cin, cout, test_case);
// cout << nl;
}
#ifdef sunnatov
cout << "Time: " << (int) ((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif
return EXIT_SUCCESS;
}
Compilation message
printer.cpp: In function 'constexpr long long int utils::operator""_E(long long unsigned int)':
printer.cpp:186:27: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
186 | for (int i = 0; i < n; i++) p *= a;
| ~~^~~
printer.cpp: In function 'void add(const string&)':
printer.cpp:231:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
231 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
printer.cpp: In function 'void remove(const string&)':
printer.cpp:246:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
246 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
printer.cpp: In function 'int32_t main()':
printer.cpp:206:22: warning: statement has no effect [-Wunused-value]
206 | #define print( ... ) 42
| ^~
printer.cpp:307:9: note: in expansion of macro 'print'
307 | print(test_case);
| ^~~~~
printer.cpp:289:13: warning: unused variable 'startTime' [-Wunused-variable]
289 | clock_t startTime = clock();
| ^~~~~~~~~
printer.cpp:293:19: warning: unused variable 'in' [-Wunused-variable]
293 | std::istream &in(std::cin);
| ^~
printer.cpp:294:19: warning: unused variable 'out' [-Wunused-variable]
294 | std::ostream &out(std::cout);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
72708 KB |
Output is correct |
| 2 |
Correct |
32 ms |
72784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
72792 KB |
Output is correct |
| 2 |
Correct |
37 ms |
72772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
72788 KB |
Output is correct |
| 2 |
Correct |
33 ms |
72824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
72796 KB |
Output is correct |
| 2 |
Correct |
31 ms |
72788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
72788 KB |
Output is correct |
| 2 |
Correct |
30 ms |
72932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
72796 KB |
Output is correct |
| 2 |
Correct |
37 ms |
73040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
73272 KB |
Output is correct |
| 2 |
Correct |
40 ms |
73552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
73684 KB |
Output is correct |
| 2 |
Correct |
38 ms |
73552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
74700 KB |
Output is correct |
| 2 |
Correct |
84 ms |
77256 KB |
Output is correct |
| 3 |
Correct |
61 ms |
76232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
74440 KB |
Output is correct |
| 2 |
Correct |
91 ms |
78020 KB |
Output is correct |
| 3 |
Correct |
67 ms |
76744 KB |
Output is correct |
| 4 |
Correct |
84 ms |
78024 KB |
Output is correct |
