Submission #1330738

#TimeUsernameProblemLanguageResultExecution timeMemory
1330738aren_danceType Printer (IOI08_printer)C++20
20 / 100
4 ms2252 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> solve(vector<string> s){
    if(s.empty()){
        return {};
    }
    if(s[0].size()==1){
        vector<int> p[27];
        for(int i=0;i<int(s.size());++i){
            int x=s[i][0]-'a';
            p[x].push_back(i);
        }
        vector<int> answ;
        for(int i=0;i<27;++i){
            for(auto j:p[i]){
                answ.push_back(j);
            }
        }
        return answ;
    }
    vector<int> p[27];
    int cur_mn=0;
    int id=0;
    for(int i=0;i<int(s.size());++i){
        int x=s[i][0]-'a';
        p[x].push_back(i);
        if(s[i].size()>cur_mn){
            cur_mn=s[i].size();
            id=x;
        }
    }
    vector<int> answ;
    for(int i=0;i<27;++i){
        vector<string> pj;
        if(i==id){
            continue;
        }
        for(auto j:p[i]){
            s[j].erase(s[j].begin());
            pj.push_back(s[j]);
        }
        vector<int> u=solve(pj);
        for(int j=0;j<int(u.size());++j){
            answ.push_back(p[i][u[j]]);
        }
    }
    int i=id;
    vector<string> pj;
        for(auto j:p[i]){
            s[j].erase(s[j].begin());
            pj.push_back(s[j]);
        }
        vector<int> u=solve(pj);
        for(int j=0;j<int(u.size());++j){
            answ.push_back(p[i][u[j]]);
        }
    return answ;
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<string> s(n);
    for(int i=0;i<n;++i){
        cin>>s[i];
    }
    vector<int> r=solve(s);
    vector<char> mas;
    for(auto j:s[r[0]]){
        mas.push_back(j);
    }
    mas.push_back('P');
    for(int i=1;i<n;++i){
        int v=min(int(s[r[i-1]].size()),int(s[r[i]].size()));
        for(int j=0;j<min(int(s[r[i-1]].size()),int(s[r[i]].size()));++j){
            if(s[r[i]][j]!=s[r[i-1]][j]){
                v=j;
                break;
            }
        }
        for(int j=v;j<s[r[i-1]].size();++j){
            mas.push_back('-');
        }
        for(int j=v;j<s[r[i]].size();++j){
            mas.push_back(s[r[i]][j]);
        }
        mas.push_back('P');
    }
    cout<<mas.size()<<'\n';
    for(auto i:mas){
        cout<<i<<'\n';
    }
    return 0;
} 
#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...