Submission #850065

#	Time	Username	Problem	Language	Result	Execution time	Memory
850065		dshfjka	Type Printer (IOI08_printer)	C++14	0 / 100	195 ms	28352 KiB

printer

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MAX_N = 500001;
const int ALPHABET_SIZE = 26;

struct Trie {
    struct Node {
        int child[ALPHABET_SIZE];
        int cnt;
    };
    vector<Node> t;

    Trie() {
        t.emplace_back();
    }

    void insert(int depth, int pos, const string &s) {
        if (depth == s.length()) {
            t[pos].cnt++;
            return;
        }

        if (!t[pos].child[s[depth] - 'a']) {
            t[pos].child[s[depth] - 'a'] = t.size();
            t.emplace_back();
        }

        insert(depth + 1, t[pos].child[s[depth] - 'a'], s);
    }

    void query(int pos, vector<char> &v) {
        vector<int> stack;
        stack.push_back(pos);

        while (!stack.empty()) {
            int curPos = stack.back();
            stack.pop_back();

            for (int i = 0; i < ALPHABET_SIZE; i++) {
                if (t[curPos].child[i]) {
                    char ch = i + 'a';
                    v.push_back(ch);

                    if (t[curPos].cnt > 0)
                        v.insert(v.end(), t[curPos].cnt, 'P');

                    stack.push_back(t[curPos].child[i]);
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    Trie trie;

    for (int i = 0; i < n; i++) {
        string x;
        cin >> x;
        trie.insert(0, 0, x);
    }

    vector<char> v;
    trie.query(0, v);
    cout << v.size() << endl;

    for (char a : v)
        cout << a << endl;

    return 0;
}

Compilation message (stderr)

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

• 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