Submission #1185946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185946		Noborita	Type Printer (IOI08_printer)	C++20	100 / 100	106 ms	99160 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define LOCAL
#define L(i, j, n) for (int i = (j); i < (int)n; i ++)
#define LI(i, j, n) for (int i = (j); i <= (int)n; i ++)
#define R(i, j, n) for (int i = (j); i > (int)n; i --)
#define RI(i, j, n) for (int i = (j); i >= (int)n; i --)
#define SZ(x) int((x).size())
#define ALL(x) begin(x),end(x)
#define IS_IN(x, v) ((x).find(v) != (x).end())
#define vec vector
#define pb push_back

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;


const int N = (int)2e5+5;
const int MOD = (int)1e9 + 7;
const int oo = (int)1e9;
vec<char> sol;
struct trie{
    trie* ch[26];
    int height;
    // int dp[26];
    bool eee;
    trie(){
        eee=0;
        height=0;
        L(i,0,26){
            ch[i]=0;
            // dp[i]=-oo;
        }
    }
    void insert(string &s, int i){
        if (SZ(s) == i){
            eee = 1;
            // dp[i] = max(1, dp[i]);
            height = max(height, 1);
            // cout << "H: " << height << "\n";
            return;
        }
        int id = s[i] - 'a';
        if (ch[id]==0) ch[id] = new trie;
        ch[id]->insert(s, i + 1);
        height = max(height, ch[id]->height + 1);
        // dp[id] = max(height + 1, height);
    }
    void insert(string &s){
        trie*cur=this;
        for(char c:s){
            int id=c-'a';
            if(cur->ch[id]==0)cur->ch[id]=new trie;
            cur=cur->ch[id];
        }
        cur->eee = 1;
    }
    void print(){
        if (eee){
            sol.pb('P');
        }
        vec<pii> ord;
        L(i,0,26){
            if (ch[i] != 0){
                ord.pb({ch[i]->height, i});
            }
        }
        if (SZ(ord))
            sort(ALL(ord));
        for (auto &[f,s]:ord) {
            sol.pb(char('a'+s));
            // cout << s << " -> " << f << "\n";
            ch[s]->print();
            sol.pb('-');
        }
    }
} *root;

void solve()
{
    int n; cin >> n;
    root = new trie;
    L(i,0,n){
        string s; cin >> s;
        root->insert(s, 0);
    }
    // cout << "PrePrint" << endl;
    root->print();
    // cout << "PosPrint" << endl;

    while(!sol.empty() && sol.back()=='-') sol.pop_back();
    cout << SZ(sol) << endl;
    for(char c: sol){
        cout << c << '\n';
    }
}


int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int TT = 1;
    //cin >> TT;
    while (TT--)
    {
        solve();
    }
}

• 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