Submission #931839

#	Time	Username	Problem	Language	Result	Execution time	Memory
931839		boris_mihov	Type Printer (IOI08_printer)	C++17	100 / 100	166 ms	56328 KiB

printer

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>

typedef long long llong;
const int MAXN = 25000 + 10;
const int ALPHABET = 26;
const int MAXLEN = 20;

std::string sol;
struct Trie
{
    struct Node
    {
        int children[ALPHABET];
        bool endHere;
        bool has;
        int dep;
    };

    int cnt;
    Node trie[MAXN * MAXLEN];

    void push(int node, int pos, const std::string &s)
    {
        trie[node].has = true;
        if (pos == s.size())
        {
            trie[node].endHere = true;
            return;
        }

        if (trie[node].children[s[pos] - 'a'] == 0)
        {
            trie[node].children[s[pos] - 'a'] = ++cnt;
        }

        push(trie[node].children[s[pos] - 'a'], pos + 1, s);
        for (int i = 0 ; i < ALPHABET ; ++i)
        {
            if (trie[trie[node].children[i]].has)
            {
                trie[node].dep = std::max(trie[node].dep, trie[trie[node].children[i]].dep + 1);
            }
        }
    }

    void solve(int node)
    {
        int perm[ALPHABET];
        std::iota(perm, perm + ALPHABET, 0);
        std::sort(perm, perm + ALPHABET, [&](int x, int y)
        {
            return trie[trie[node].children[x]].dep < trie[trie[node].children[y]].dep;
        });

        if (trie[node].endHere)
        {
            sol += 'P';
        }

        for (int idx = 0 ; idx < ALPHABET ; ++idx)
        {
            int i = perm[idx];
            if (!trie[trie[node].children[i]].has)
            {
                continue;
            }

            sol += char('a' + i);
            solve(trie[node].children[i]);
            sol += '-';
        }
    }

    Trie()
    {
        cnt = 1;
    }

    void push(const std::string &s)
    {
        push(1, 0, s);
    }
};

int n;
std::string s[MAXN];
Trie trie;

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        trie.push(s[i]);
    }

    trie.solve(1);
    while (sol.back() == '-') sol.pop_back();
    std::cout << sol.size() << '\n';
    for (const char &c : sol)
    {
        std::cout << c << '\n';
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> s[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

printer.cpp: In member function 'void Trie::push(int, int, const string&)':
printer.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if (pos == s.size())
      |             ~~~~^~~~~~~~~~~

• 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