oj.uz

Submission #847811

# Submission time Handle Problem Language Result Execution time Memory
847811 2023-09-10T13:10:03 Z borisAngelov Type Printer (IOI08_printer) C++17
0 / 100
 83 ms 69068 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 27600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 69068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 53728 KB Output isn't correct
2 Halted 0 ms 0 KB -