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 endl '\n'
#define int long long
using namespace std;
const long long longlongmax=9223372036854775807;
const int modul=998244353;
const long long mod = 1e9 + 7;
int N=25000*20+9;
vector<char> rez(0);
vector<bool> kraj(N,0),drugi_krug(N,0);
vector<vector<int>> trie(N,vector<int>(26,0));
string odabrana;
int ind_c=0;
void ubaci(string&rec){
int node=0;
for(auto&x:rec){
int c=x-'a';
if(!trie[node][c]) trie[node][c]=++ind_c;
node=trie[node][c];
}
kraj[node]=true;
if(rec==odabrana){
node=0;
for(auto&x:rec){
int c=x-'a';
node=trie[node][c];
drugi_krug[node]=true;
}
}
}
void dfs1(int node){
if(kraj[node])
rez.push_back('P');
bool ok=false;
for(auto x:trie[node]){
if(x)
ok=true;
}
if(!ok) {rez.push_back('-');return;}
for(int i=0; i<26; i++){
if(!trie[node][i]) continue;
if(drugi_krug[trie[node][i]]) continue;
rez.push_back('a'+i);
dfs1(trie[node][i]);
}
if(node)
rez.push_back('-');
return;
}
void dfs2(int node,int ind,int odstup){
if(kraj[node])
rez.push_back('P');
bool ok=false;
for(auto x:trie[node]){
if(x)
ok=true;
}
if(!ok){rez.push_back('-');return;}
for(int i=0; i<26; i++){
if(!trie[node][i]) continue;
if(!odstup&&i==(odabrana[ind]-'a')) continue;
rez.push_back('a'+i);
dfs2(trie[node][i],ind,odstup+1);
}
if(!odstup){
rez.push_back(odabrana[ind]);
dfs2(trie[node][odabrana[ind]-'a'],ind+1,odstup);
}
if(node)
rez.push_back('-');
return;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("factory.in","r",stdin);
//freopen("factory.out","w",stdout);
int n;
cin >> n;
int maxsiz=0;
vector<string> niz(0);
for(int i=0; i<n; i++){
string rec;
cin >> rec;
niz.push_back(rec);
if(maxsiz<rec.size()){
odabrana=rec;
maxsiz=rec.size();
}
}
for(auto&x:niz)
ubaci(x);
dfs1(0);
rez.push_back(odabrana[0]);
dfs2(trie[0][odabrana[0]-'a'],1,0);
while(rez.back()=='-')
rez.pop_back();
cout << rez.size() << endl;
for(auto&x:rez)
cout << x << endl;
return 0;
}
Compilation message (stderr)
printer.cpp: In function 'int main()':
printer.cpp:95:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if(maxsiz<rec.size()){
| ~~~~~~^~~~~~~~~~~
# | 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... |