# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
811003 | sofija6 | Type Printer (IOI08_printer) | C++14 | 93 ms | 41020 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 ll long long
#define MAXC 1000010
using namespace std;
vector<ll> G[MAXC];
vector<char> ans;
char val[MAXC];
string s,maxx;
ll ind=2;
bool lastt[MAXC],endd[MAXC];
void Add(ll cur,ll pos)
{
if (pos==s.size())
{
endd[cur]=true;
return;
}
ll x=-1;
for (ll next : G[cur])
{
if (val[next]==s[pos])
x=next;
}
if (x==-1)
{
x=ind++;
val[x]=s[pos];
G[cur].push_back(x);
}
Add(x,pos+1);
}
void Find(ll cur,ll pos)
{
lastt[cur]=true;
if (pos==maxx.size())
return;
ll x=-1;
for (ll next : G[cur])
{
if (val[next]==maxx[pos])
x=next;
}
Find(x,pos+1);
}
void Solve(ll cur)
{
if (endd[cur])
ans.push_back('P');
for (ll next : G[cur])
{
if (!lastt[next])
{
ans.push_back(val[next]);
Solve(next);
}
}
for (ll next : G[cur])
{
if (lastt[next])
{
ans.push_back(val[next]);
Solve(next);
}
}
if (!lastt[cur])
ans.push_back('-');
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n;
cin >> n;
for (ll i=1;i<=n;i++)
{
cin >> s;
Add(1,0);
if (s.size()>maxx.size())
maxx=s;
}
Find(1,0);
Solve(1);
cout << ans.size() << "\n";
for (char i : ans)
cout << i << "\n";
return 0;
}
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... |