# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
720340 | Yell0 | 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;
typedef long long ll;
const int MN=25002;
int N,ans=0;
string w[MN];
vector<string> ss;
map<string,int> wpos;
int main() {
ios::sync_with_stdio(0);cin.tie(0);
cin>>N;
for(int i=1;i<=N;++i) cin>>w[i];
sort(w+1,w+1+N);
int mx=0,mxi=0;
for(int i=1;i<=N;++i) {
wpos[w[i]]=i;
if((int)w[i].size()>mx) {
mx=w[i].size();
mxi=i;
}
}
int endp=N;
for(int i=1;i<=(int)w[mxi].size();++i)
for(int j=1;j<=N;++j) {
if((int)w[j].size()<i) continue;
if(w[j].substr(0,i)==w[mxi].substr(0,i)) wpos[w[j]]=++endp;
}
sort(w+1,w+1+N,[](string a,string b) {return wpos[a]<wpos[b];});
string ct="";
for(int i=1;i<=N;++i) {
string cw=w[i];
while(ct.size()>cw.size()) {
ct.pop_back();
++ans;
ss.push_back("-");
}
while(ct.size()<cw.size()) cw.pop_back();
while(ct!=cw) {
ct.pop_back();
cw.pop_back();
++ans;
ss.push_back("-");
}
while(ct.size()<w[i].size()) {
++ans;
ss.push_back(1,w[i][ct.size()]);
ct.push_back(w[i][ct.size()]);
}
++ans;
ss.push_back("P");
}
cout<<ans<<'\n';
for(string s:ss) cout<<s<<'\n';
return 0;
}