Submission #554897

#	Time	Username	Problem	Language	Result	Execution time	Memory
554897		alextodoran	Type Printer (IOI08_printer)	C++17	100 / 100	122 ms	99652 KiB

printer

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector <char> sol;

struct Trie {
    int depth; int cnt = 0;
    Trie* sons[26];
    Trie () {
        cnt = 0;
        depth = 0;
        for (int i = 0; i < 26; i++) {
            sons[i] = NULL;
        }
    }
    void add (char* str) {
        if (*str == '\0') {
            cnt++;
            return;
        }
        int i = (int) (*str - 'a');
        if (sons[i] == NULL) {
            sons[i] = new Trie();
        }
        sons[i]->add(str + 1);
        depth = max(depth, sons[i]->depth + 1);
    }
    void dfs (bool ret = false) {
        while (cnt--) {
            sol.push_back('P');
        }
        int last = -1;
        for (int i = 0; i < 26; i++) {
            if (sons[i] != NULL) {
                if (last == -1 || sons[i]->depth > sons[last]->depth) {
                    last = i;
                }
            }
        }
        if (last != -1) {
            for (int i = 0; i < 26; i++) {
                if (sons[i] != NULL && i != last) {
                    sol.push_back((char) ('a' + i));
                    sons[i]->dfs(true);
                }
            }
            sol.push_back((char) ('a' + last));
            sons[last]->dfs(ret);
        }
        if (ret == true) {
            sol.push_back('-');
        }
    }
};

Trie root;

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

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char str[21];
        cin >> str;
        root.add(str);
    }
    root.dfs(false);

    cout << (int) sol.size() << "\n";
    for (char x : sol) {
        cout << x << "\n";
    }

    return 0;
}

• 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