Submission #1195820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195820		anonymous321	Type Printer (IOI08_printer)	C++20	100 / 100	100 ms	65664 KiB

printer

// https://oj.uz/problem/view/IOI08_printer
#include <bits/stdc++.h>
using namespace std;

struct node {
    vector<int> child = vector<int> (26, -1);
    int h = 0;
    bool mark = false;
};

vector<node> t {{}};

void insert (string &s, int id = 0, int i = 0) {
    t[i].h = max(t[i].h, (int) s.size() - id);
    if (id == s.size()) {
        t[i].mark = true;
        return;
    }
    int c = s[id] - 'a';
    if (t[i].child[c] == -1) {
        t.push_back({});
        t[i].child[c] = t.size() - 1;
    }
    insert(s, id+1, t[i].child[c]);
}

vector<char> sol {};

void comp (int i) {
    if (t[i].mark) {
        sol.push_back('P');
    }
    int maxi = -1;
    for (int c = 0; c < 26; c++) {
        if (t[i].child[c] == -1) continue;
        if (t[i].h - 1 == t[t[i].child[c]].h) {
            maxi = c;
        }
    }
    for (int c = 0; c < 26; c++) {
        if (t[i].child[c] == -1) continue;
        if (c == maxi) continue;
        sol.push_back(c + 'a');
        comp(t[i].child[c]);
        sol.push_back('-');
    }
    if (maxi != -1) {
        sol.push_back(maxi + 'a');
        comp(t[i].child[maxi]);
        sol.push_back('-');
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        insert(s);
    }

    comp(0);
    while (!sol.empty() && sol[sol.size() - 1] == '-') {
        sol.pop_back();
    }

    cout << sol.size() << "\n";
    for (auto &it : sol) {
        cout << it << "\n";
    }
    return 0;
}

• 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