Submission #1138599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138599		Nelt	Type Printer (IOI08_printer)	C++20	100 / 100	67 ms	5056 KiB

printer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
ll lcp(string a, string b)
{
    for (ll i = 0; i < min(a.size(), b.size()); i++) if (a[i] != b[i]) return i;
    return min(a.size(), b.size());
}
void solve()
{
    ll n;
    cin >> n;
    string s[n];
    pair<ll, string> mx = make_pair(-1, "z");
    for (ll i = 0; i < n; i++) cin >> s[i], mx = max(mx, make_pair((ll)s[i].size(), s[i]));
    sort(s, s + n, [&](string &a, string &b)
    {
        return lcp(a, mx.second) == lcp(b, mx.second) ? a < b : lcp(a, mx.second) < lcp(b, mx.second);
    });
    vector<char> ans;
    string cur;
    for (string i : s)
    {
        while (lcp(cur, i) != cur.size()) cur.pop_back(), ans.push_back('-');
        while (cur.size() < i.size()) ans.push_back(i[cur.size()]), cur += ans.back();
        // cout << cur << endl;
        ans.push_back('P');
    }
    cout << ans.size() << endl;
    for (auto i : ans) cout << i << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\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