Submission #1043036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043036		Zicrus	Type Printer (IOI08_printer)	C++17	100 / 100	196 ms	101304 KiB

printer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct node {
public:
    unordered_map<char, node*> adj;
    bool end;
};

node *trie;
vector<char> res;
string longest;

void dfs(node *cur, int id) {
    for (auto &e : cur->adj) {
        if (id != -1 && e.first == longest[id]) continue;
        res.push_back(e.first);
        if (e.second->end) res.push_back('P');
        dfs(e.second, -1);
    }
    if (id != -1 && cur->adj.count(longest[id])) {
        res.push_back(longest[id]);
        if (cur->adj[longest[id]]->end) res.push_back('P');
        dfs(cur->adj[longest[id]], id+1);
    }
    res.push_back('-');
}

void solve() {
    dfs(trie, 0);
}

int main() {
    ll n;
    cin >> n;
    trie = new node();
    longest = "";
    vector<node*> gc = {trie};
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s.size() > longest.size()) longest = s;
        node *cur = trie;
        for (int j = 0; j < s.size(); j++) {
            if (cur->adj.count(s[j])) {
                cur = cur->adj[s[j]];
            }
            else {
                cur = cur->adj[s[j]] = new node();
                gc.push_back(cur);
            }
        }
        cur->end = true;
    }

    res = vector<char>();
    solve();
    while (res.back() != 'P') res.pop_back();
    cout << res.size() << '\n';
    for (auto &e : res) cout << e << '\n';

    for (auto &e : gc) delete e;
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j = 0; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~

• 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