| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1290110 | Faisal_Saqib | Type Printer (IOI08_printer) | C++20 | 0 ms | 0 KiB |
/*
VENI VIDI VICI
*/
#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
using sll = set<ll>;
template<class T>
istream& operator>>(istream& is, vector<T>& v) {
for(auto &i:v) is>>i;
return is;
}
template<class T1,class T2>
istream& operator>>(istream& is, pair<T1,T2>& p) {
is>>p.fi>>p.se;
return is;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
for(const auto &i:v) os<<i<<' ';
return os;
}
template<class T1,class T2>
ostream& operator<<(ostream& os, const pair<T1,T2>& p) {
os<<p.fi<<' '<<p.se; return os;
}
void pyn(bool x)
{
cout<<(x?"YES":"NO")<<endl;
}
void pYN(bool x)
{
cout<<(x?"Yes":"No")<<endl;
}
void pAB(bool x)
{
cout<<(x?"Alice":"Bob")<<endl;
}
ll powmod(ll a,ll b,ll modulo)
{
if(b==0){
return 1;
}
ll temp=powmod(a,b/2,modulo);
if(b%2==0){
return (temp*temp)%modulo;
}
else{
return (a*((temp*temp)%modulo))%modulo;
}
}
bool Prime(ll n){
for (ll i = 2; i*i <= n; i++)
if (n % i == 0)
return false;
return (n>1);
}
void readIO() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
}
#endif
void solve();
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
readIO();
int uwu=1;
// cin>>uwu;
for(int tc=1;tc<=uwu;tc++) {
// cout<<"Case #"<<tc<<": ";
solve();
}
return 0;
}
const int N=1e6+100;
int nxt[N][26],lst=0,h[N];
bool ed[N];
void add(string s)
{
// cout<<"insert "<<s<<endl;
int rt=0;
for(int i=0;i<s.size();i++)
{
int j=s[i]-'a';
if(nxt[rt][j]==0)
{
nxt[rt][j]=++lst;
}
// cout<<rt<<' ';
rt=nxt[rt][j];
h[rt]=max(h[rt],(int)s.size()-i);
}
ed[rt]=1;
// cout<<rt<<endl;
}
vector<char> ans;
void print(int rt,bool keep)
{
// cout<<"At "<<rt<<endl;
if(ed[rt])
{
// cout<<'P'<<endl;
ans.pb(char('P'));
}
int mx=0,v=-1;
for(int j=0;j<26;j++)
{
if(h[nxt[rt][j]]>mx and nxt[rt][j]!=0)
{
mx=h[nxt[rt][j]];
v=j;
}
}
if(v==-1)return;
// cout<<"At "<<rt<<' '<<keep<<' '<<mx<<' '<<v<<endl;
for(int j=0;j<26;j++)
{
if(h[nxt[rt][j]]>0 and nxt[rt][j]!=0 and j!=v)
{
// cout<<char('a'+j)<<endl;
ans.pb(char('a'+j));
print(nxt[rt][j],0);
ans.pb('-');
// cout<<'-'<<endl;
}
}
ans.pb(char('a'+v));
// cout<<char('a'+v)<<endl;
print(nxt[rt][v],keep);
if(!keep)
{
ans.pb('-');
// cout<<'-'<<endl;
}
}
void solve()
{
int n;
cin>>n;
int len=0,mx=0;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
len+=2*s.size()+1;
mx=max(mx,(int)s.size());
// cout<<"cur "<<s<<endl;
add(s);
}
print(0,1);
cout<<ans.size()<<endl;
for(auto x:ans)cout<<x<<endl;
}