Submission #1279461

#TimeUsernameProblemLanguageResultExecution timeMemory
1279461adiatType Printer (IOI08_printer)C++20
40 / 100
400 ms15480 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<string,int> mp;
bool comp(string a, string b)
{
    int p=0;
    for(int i=0; i<min(a.size(),b.size()); i++)
    {
        if(a[i]!=b[i])
            break;
        p++;
    }
    if(a.size()==b.size() && p==a.size())
        return a<b;
    if(p==a.size())
    {
        for(int i=0; i<a.size(); i++)
            mp[a.substr(0,i+1)]=max(mp[a.substr(0,i+1)],(int)b.size()),mp[b.substr(0,i+1)]=max(mp[b.substr(0,i+1)],(int)a.size());
        return true;
    }
    if(p==b.size())
    {
        for(int i=0; i<b.size(); i++)
            mp[b.substr(0, i+1)]=max(mp[b.substr(0,i+1)],(int)a.size()),mp[a.substr(0,i+1)]=max(mp[a.substr(0,i+1)],(int)b.size());
        return false;
    }
    if(mp[a.substr(0, p+1)]<mp[b.substr(0, p+1)])
    {
        for(int i=0; i<p; i++)
            mp[a.substr(0,i+1)]=max(mp[a.substr(0,i+1)],(int)b.size()),mp[b.substr(0,i+1)]=max(mp[b.substr(0,i+1)],(int)a.size());
        return true;
    }
    else
    {
        for(int i=0; i<p; i++)
            mp[b.substr(0,i+1)]=max(mp[b.substr(0,i+1)],(int)a.size()),mp[a.substr(0,i+1)]=max(mp[a.substr(0,i+1)],(int)b.size());
        return false;
    }
}
signed main()
{
    int n;
    cin>>n;
    string s[n];
    for(string &i: s)
        cin>>i;
    for(auto &i: s)
    {
        for(int j=0; j<i.size(); j++)
        {
            mp[i.substr(0,j+1)]=max(mp[i.substr(0,j+1)],(int)i.size());
        }
    }
    sort(s,s+n, comp);
    // reverse(s,s+n);
    vector<char> ans;
    string x="";
    for(auto k: s)
    {
        int p=0;
        for(int i=0; i<min(k.size(),x.size()); i++)
        {
            if(k[i]!=x[i])
                break;
            p++;
        }
        for(int i=x.size()-1; i>=p; i--)
            ans.push_back('-'),x.pop_back();
        for(int i=p; i<k.size(); i++)
            ans.push_back(k[i]);
        ans.push_back('P');
        x=k;
        // for(int i=0; i<p; i++)
        //     ans.push_back('-'),x.pop_back();
        
    }
    cout<<ans.size()<<endl;
    for(auto i: ans)
        cout<<i<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...