Submission #1268613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268613		zulll	Type Printer (IOI08_printer)	C++20	100 / 100	89 ms	57972 KiB

printer

#include <bits/stdc++.h>

#define fi first 
#define se second 
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ld long double
#define ll long long int
#define eliminate(x, y) (x).erase(remove(all(x), (y)), (x).end())
#define make_unique(x) sort(all(x)), (x).erase(unique(all(x)), (x).end());
#define all_range(x) (x).begin(), (x).begin()
#define All(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define newl cerr << '\n'
#define endl '\n'

using namespace std;
template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;  
 
template<typename T>void prd(const T& x);
template<typename T, typename U>void prd(const pair<T, U>& x);
template<typename T, typename... A>void prd(const T& x, A... a);
template<typename... A>void debug(A... a);
template<typename T>void debug(const set<T>& c);
template<typename T>void debug(const vector<T>& c);
template<typename T>void debug(const vector<vector<T>> &c);
template<typename K, typename V>void debug(const map<K, V>& c);
void fail() {debug("DONE"); exit(0);}

const int MOD = 1e9 + 7;
const int mod = 998244353;
const int INF = 2e9 + 7;
const ll INFL = 2e18 + 7;
const double EPS = 1e-9;

void FastIO();

struct Trie {
    static const int K = 26;
    struct Node {
        int next[K], dp = 0;
        bool word = 0;

        Node() {fill(next, next + K, -1);}

        int &operator[](char c) {assert('a' <= c && c <= 'z'); return next[c - 'a'];}
    };

    vector<Node> trie;
    string ans;

    Trie() : trie(1) {}

    void insert(string &s) {
        int x = 0;

        for(char c : s) {
            if(trie[x][c] == -1){
                trie[x][c] = sz(trie);
                trie.pb(Node());
            }

            x = trie[x][c];
            trie[x].dp = max(trie[x].dp, sz(s));
        }

        trie[x].word = 1;
    }

    void dfs(int x) {
        if(trie[x].word)
            ans.pb('P');

        vector<pair<int, char>> next;
        for(char c = 'a'; c <= 'z'; c++)
            if(trie[x][c] != -1)
                next.pb({trie[x][c], c});
        
        sort(all(next), [&](pair<int, char> &a, pair<int, char> &b){
            return trie[a.fi].dp < trie[b.fi].dp;
        });
        // debug(next);
        
        for(auto &[y, c] : next){
            ans += c;
            dfs(y);
            ans += '-';
        }
    }
} trie;

int main(){
 
    FastIO();
    int n; cin >> n;
    string s; 

    for(int i = 0; i < n; i++){
        cin >> s;
        trie.insert(s);
    }

    trie.dfs(0);
    while(trie.ans.back() == '-') trie.ans.ppb();
    cout << sz(trie.ans) << endl;
    for(char c : trie.ans) cout << c << endl;

    return 0;
}
 
void FastIO(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
template<typename T> void prd(const T& x){cerr<<x;}
template<typename T, typename U>void prd(const pair<T, U>& x){cerr<<"(";prd(x.fi);cerr<<", ";prd(x.se);cerr<<")";}
template<typename T, typename... A>void prd(const T& x, A... a){prd(x);cerr<<", ";prd(a...);}
template<typename... A> void debug(A... a){cerr << "["; prd(a...);cerr<<"]\n";}
template<typename T> void debug(const set<T>& c){cerr<<'[';bool cm=0;for(const auto& st:c){if(cm)cerr<<", ";prd(st);cm=1;}cerr<<"]\n";}
template<typename T> void debug(const vector<T>& c){cerr<<'[';bool cm=0;for(const auto& v:c){if(cm)cerr<<", ";prd(v);cm=1;}cerr<<"]\n";}
template<typename T> void debug(const vector<vector<T>> &c){for(const auto &v: c)debug(v);cerr<<'\n';}
template<typename K, typename V> void debug(const map<K, V>& c){cerr<<'[';bool cm=0;for(auto[k, v]:c){if(cm)cerr<<", ";cerr<<'[';prd(k);cerr <<", ";prd(v);cerr<<']';cm = 1;}cerr<<"]\n";}

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