Submission #1260452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260452		kargneq	Type Printer (IOI08_printer)	C++20	100 / 100	34 ms	4936 KiB

printer

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

static int lcp(const string& a, const string& b) {
    int k = 0, m = min(a.size(), b.size());
    while (k < m && a[k] == b[k]) ++k;
    return k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // choose one deepest word W to end on
    string W = *max_element(a.begin(), a.end(),
                            [](const string& x, const string& y){
                                return x.size() < y.size();
                            });

    // sort by increasing LCP with W, then lexicographic
    sort(a.begin(), a.end(), [&](const string& x, const string& y){
        int lx = lcp(x, W), ly = lcp(y, W);
        if (lx != ly) return lx < ly;
        return x < y;
    });

    string cur;
    vector<char> ops;
    ops.reserve(1000000);

    for (const string& s : a) {
        int k = lcp(cur, s);
        while ((int)cur.size() > k) { cur.pop_back(); ops.push_back('-'); }
        while ((int)cur.size() < (int)s.size()) {
            char c = s[cur.size()];
            cur.push_back(c);
            ops.push_back(c);
        }
        ops.push_back('P');
    }

    cout << ops.size() << '\n';
    for (char c : ops) cout << c << '\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