Submission #1098161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098161		rayan_bd	Type Printer (IOI08_printer)	C++17	100 / 100	167 ms	140740 KiB

printer

#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 (stderr)

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 / 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