제출 #1309645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309645		pedreitorzelda	Type Printer (IOI08_printer)	C++20	10 / 100	28 ms	21604 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct trie{
    vector<pair<map<char,int>,int>>children;
    void add(int ind,string &s,int pos){
        if(pos>=s.size())return;
        if(children[ind].first.find(s[pos])!=children[ind].first.end()){
            children[children[ind].first[s[pos]]].second++;
            add(children[ind].first[s[pos]],s,pos+1);
        }else{
            children[ind].first[s[pos]]=children.size();
            children.push_back({{},0});
            children[children[ind].first[s[pos]]].second++;
            add(children[ind].first[s[pos]],s,pos+1);
        }return;
    }void add(string &s){
        if(children.empty())children.push_back({{},0});
        add(0,s,0);
        return;
    }void quit(int ind,string &s,int pos){
        if(pos>=s.size())return;
        if(children[ind].first.find(s[pos])!=children[ind].first.end()){
            children[children[ind].first[s[pos]]].second--;
            quit(children[ind].first[s[pos]],s,pos+1);
            if(children[children[ind].first[s[pos]]].second==0)children[ind].first.erase(s[pos]);
        }//else{
        //    children[ind].first[s[pos]]=children.size();
        //    children.push_back({{},0});
        //    children[children[ind].first[s[pos]]].second++;
        //    quit(children[ind].first[s[pos]],s,pos+1);
        //}
        return;
    }
    pair<string,int> query(int ind,string &s,int pos){
        if(pos>=s.size())return {"",pos};
        if(children[ind].first.find(s[pos])!=children[ind].first.end()){
            pair<string,int>act = query(children[ind].first[s[pos]],s,pos+1);
            return {s[pos]+act.first,act.second};
        }else if(!children[ind].first.empty()){
            auto it = children[ind].first.begin();
            pair<string,int>act = query((*it).second,s,pos+1);
            return {(*it).first+act.first,pos};
        }else{
            return {"",pos};
        }
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    trie words;
    vector<string>a(n);
    ll sum = 0;
    int index = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        words.add(a[i]);
        sum+=a[i].size();
        if(a[i].size()>a[index].size())index = i;
    }
    vector<pair<string,int>>b(n);
    b[0]={a[index],0};
    words.quit(0,a[index],0);
    int j = 0;
    for(int i=1;i<n;i++){
        b[i] =words.query(0,b[i-1].first,0);
        words.quit(0,b[i].first,0);
    }
    reverse(b.begin(),b.end());
    vector<char>ans;
    for(int i=0;i<n;i++){
        if(i>0)for(int j=b[i-1].second;j<b[i-1].first.size();j++)ans.push_back('-');
        int st = 0;
        if(i>0)st=b[i-1].second;
        for(int j=st;j<b[i].first.size();j++)ans.push_back(b[i].first[j]);
        ans.push_back('P');
    }cout << ans.size() << '\n';
    for(auto it : ans)cout << it << '\n';
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10