oj.uz

Submission #1098161

# Submission time Handle Problem Language Result Execution time Memory
1098161 2024-10-09T05:44:19 Z rayan_bd Type Printer (IOI08_printer) C++17
100 / 100
 167 ms 140740 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = (int)1e-9;

vector<char> ans;

struct Node
{
    Node *children[26];
    bool end;
    set<pair<int, char>> st;
    Node()
    {
        for (int i = 0; i < 26; ++i)
            children[i] = NULL;
        end = 0;
    };
};

Node *root = new Node();

struct Trie
{
    void insert(string str)
    {
        Node *curr_node = root;
        for (auto it : str)
        {
            if (curr_node->children[it - 'a'] == NULL)
            {
                curr_node->children[it - 'a'] = new Node();
            }
            vector<int> for_del;
            for (auto itt : curr_node->st)
            {
                if (itt.second == it)
                {
                    for_del.push_back(itt.first);
                }
            }
            int mx = INF;
            for (auto itt : for_del)
            {
                mx = max(mx, itt);
                curr_node->st.erase({itt, it});
            }
            curr_node->st.insert({max(mx, (int)str.size()), it});
            curr_node = curr_node->children[it - 'a'];
        }
        curr_node->end = 1;
    }
    void qry(Node *curr)
    {
        bool flag = 1;
        for (int i = 0; i < 26; ++i)
        {
            if (curr->children[i] != NULL)
            {
                flag = 0;
            }
        }
        if (curr->end == 1)
        {
            ans.push_back('P');
        }
        if (flag)
        {
            ans.push_back('-');
            return;
        }
        for (auto it : curr->st)
        {
            ans.push_back(it.second);
            qry(curr->children[it.second - 'a']);
        }
        ans.push_back('-');
    }
} t;

void solve()
{
    int n;
    cin >> n;
    string str;
    for (int i = 0; i < n; ++i)
    {
        cin >> str;
        t.insert(str);
    }
    Node *curr_node = root;
    t.qry(curr_node);
    int deletee = 0;
    for (int i = ans.size() - 1; i >= 0; --i)
    {
        if (ans[i] == '-')
        {
            ++deletee;
        }
        else
        {
            break;
        }
    }
    cout << ans.size() - deletee << '\n';
    for (int i = 0; i < ans.size() - deletee; ++i)
    {
        cout << ans[i] << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

Compilation message

printer.cpp: In function 'void solve()':
printer.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < ans.size() - deletee; ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 3160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8248 KB Output is correct
2 Correct 21 ms 17756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20688 KB Output is correct
2 Correct 18 ms 4804 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 51664 KB Output is correct
2 Correct 151 ms 118364 KB Output is correct
3 Correct 101 ms 60892 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 40136 KB Output is correct
2 Correct 167 ms 140740 KB Output is correct
3 Correct 119 ms 69384 KB Output is correct
4 Correct 119 ms 132808 KB Output is correct