# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
930245 | Aiperiii | Type Printer (IOI08_printer) | C++14 | 70 ms | 75192 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>
#define int long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=1e6;
struct Trie{
int out=0,last=0;
map <char,int> mp;
};
Trie t[N];
int cnt=0;
void insert(string s){
int p=0;
for(int i=0;i<s.size();i++){
if(t[p].mp[s[i]]==0){
cnt++;
t[p].mp[s[i]]=cnt;
}
p=t[p].mp[s[i]];
}
t[p].out=1;
}
void mark_last(string s){
int p=0;
for(int i=0;i<s.size();i++){
p=t[p].mp[s[i]];
t[p].last=1;
}
}
vector <char> ans;
void get(int p,char c){
if(p!=0)ans.pb(c);
for(auto i : t[p].mp){
if(!t[i.ss].last)get(i.ss,i.ff);
}
for(auto i : t[p].mp){
if(t[i.ss].last)get(i.ss,i.ff);
}
if(t[p].out==1)ans.pb('P');
ans.pb('-');
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector <string> s(n);
for(int i=0;i<n;i++){
cin>>s[i];
}
sort(all(s),[&](string a,string b){return a.size()<b.size();});
for(int i=0;i<s.size();i++){
insert(s[i]);
}
mark_last(s.back());
get(0,'S');
while(ans.back()=='-')ans.pop_back();
cout<<ans.size()<<"\n";
for(auto x : ans){
cout<<x<<"\n";
}
}
/*
*/
Compilation message (stderr)
# | 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... |