Submission #847811

#	Time	Username	Problem	Language	Result	Execution time	Memory
847811		borisAngelov	Type Printer (IOI08_printer)	C++17	0 / 100	83 ms	69068 KiB

printer

#include <bits/stdc++.h>

using namespace std;

const int alphabet_size = 26;

int n;

struct trie_node
{
    trie_node *children[alphabet_size];
    pair<int, int> max_passing_length[alphabet_size];
    bool is_end_of_word;

    trie_node()
    {
        is_end_of_word = false;

        for (int i = 0; i < alphabet_size; ++i)
        {
            children[i] = NULL;
            max_passing_length[i].first = 0;
            max_passing_length[i].second = i;
        }
    }
};

trie_node *root = new trie_node;

void insert_word(trie_node *&curr, const string& s, int pos)
{
    if (curr == NULL)
    {
        curr = new trie_node;
    }

    if (pos == s.size())
    {
        //cout << "set end " << endl;
        curr->is_end_of_word = true;
        return;
    }

    curr->max_passing_length[(s[pos] - 'a')].first = max(curr->max_passing_length[(s[pos] - 'a')].first, int(s.size()));
    //cout << "for " << s << " on " << pos << " ::: " << curr->max_passing_length[(s[pos] - 'a')].first << endl;

    insert_word(curr->children[(s[pos] - 'a')], s, pos + 1);
}

vector<char> operations;
int cnt_oparations = 0;

void dfs(trie_node *&curr)
{
    sort(curr->max_passing_length, curr->max_passing_length + alphabet_size);

    if (curr->is_end_of_word == true)
    {
        ++cnt_oparations;
        operations.push_back('P');
    }

    for (int i = 0; i < alphabet_size; ++i)
    {
        if (curr->max_passing_length[i].first != 0 && curr->children[curr->max_passing_length[i].second] != NULL)
        {
            ++cnt_oparations;
            operations.push_back(char('a' + curr->max_passing_length[i].second));

            dfs(curr->children[curr->max_passing_length[i].second]);

            ++cnt_oparations;
            operations.push_back(char('-'));
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;
        insert_word(root, s, 0);
    }

    dfs(root);

    cout << cnt_oparations << endl;

    for (int i = 0; i < cnt_oparations; ++i)
    {
        cout << operations[i] << "\n";
    }

    return 0;
}

/*
3
print
the
poem
*/

Compilation message (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10