#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NMAX 100005
#define int long long
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define INF 1e18
#define MOD 1000000007
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ost tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define LSB(x) ((x)&-(x))
#define count_bits(x) __builtin_popcount(x)
#define leading_zeros(x) __builtin_clz(x)
#define trailing_zeros(x) __builtin_ctz(x)
#define all(x) begin(x),end(x)
#define pb push_back
#define eps 1e-9
struct node{
int id;
int cnt;
map<char,int>next;
node(){
id = -1;
cnt = 0;
next.clear();
}
};
vector<node>tri={node()};
int new_node(){
tri.pb(node());
return tri.size()-1;
}
void insere(string &s, int i){
int x = 0;
tri[x].cnt++;
for(auto ch:s){
if(tri[x].next.count(ch)==0){
tri[x].next[ch] = new_node();
}
x = tri[x].next[ch];
tri[x].cnt++;
}
tri[x].id = i;
}
int qtdd(string a, string b){
int n = a.size();
int m = b.size();
int qtd = 0;
for(int i=0;i<min(n,m);i++){
if(a[i]==b[i]) qtd++;
else break;
}
return qtd;
}
string ans ="";
void solve(int x){
if(tri[x].id!=-1){
ans.pb('P');
}
vector< pair<int,char> >v;
for(auto [ch,next_id]:tri[x].next){
v.pb({next_id,ch});
}
sort(all(v));
for(auto [next_id,ch]:v){
ans.pb(ch);
solve(next_id);
ans.pb('-');
}
}
int32_t main(){ faster
int n; cin >> n;
vector<string>v;
vector< pair<int,string> >vv;
int mx = 0; string s_mx;
for(int i=0;i<n;i++){
string s; cin >> s;
if( s.size() > mx ){
mx = s.size();
s_mx = s;
}
v.pb(s);
}
for(int i=0;i<n;i++){
int qtdcomum = qtdd(s_mx,v[i]);
vv.pb({qtdcomum,v[i]});
}
sort(all(vv));
for(int i=0;i<n;i++){
insere(vv[i].second,i);
}
solve(0);
while(ans.back()=='-') ans.pop_back();
cout << ans.size() << '\n';
for(auto it:ans) cout << it << '\n';
}
/*
int dp[estados]; //dp[i] é 1 se é um estado vencedor pro player1
int solve(int x){
if(dp[x]!=-1) return dp[x];
int turno = tri[x].nivel & 1;
dp[x] = 0;
if(tri[x].cnt[turno]==0) return 0;
for(auto [ch,next_id]:tri[x].next){
if(solve(next_id)==0){
dp[x] = 1;
}
}
return dp[x];
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |