IOI '08 P1 - Type Printer

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

size_t commonPrefix(const string &s1, const string &s2) {
    size_t i = 0;
    while (i < s1.size() && i < s2.size() && s1[i] == s2[i]) ++i;
    return i;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<string> v(1+n);
    int longest = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        if (v[i].size() > v[longest].size()) longest = i;
    }

    string maxString = v[longest];
    auto stringLess = [&](const string &s1, const string &s2) {
        for (size_t i = 0; i < s1.size() && i < s2.size(); ++i) {
            if (s1[i] != s2[i]) {
                if (s1[i] == maxString[i]) return false;
                if (s2[i] == maxString[i]) return true;
                return s1[i] < s2[i];
            }
        }
        return s1.size() < s2.size();
    };
    sort(v.begin()+1, v.end(), stringLess);

    string operations;
    for (int i = 1; i <= n; ++i) {
        size_t overlap = commonPrefix(v[i-1], v[i]);
        operations += string(v[i-1].size() - overlap, '-') + v[i].substr(overlap);
        operations.push_back('P');
    }
    cout << operations.size() << '\n';
    for (char c : operations) cout << c << '\n';
    return 0;
}