Submission #120064

#	Time	Username	Problem	Language	Result	Execution time	Memory
120064		dolphingarlic	Type Printer (IOI08_printer)	C++14	100 / 100	198 ms	101760 KiB

printer

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for(int i = x; i < y; i++)
#define ALPHABET 26
typedef long long ll;
using namespace std;

vector<char> ops;
string longest = "", words[25000];

bool cmp(string a, string b) {
    return (a.length() < b.length());
}

struct TrieNode {
    TrieNode *children[ALPHABET];
    bool isEndOfWord, containsLongest;
};

TrieNode *getNode() {
    TrieNode *pNode = new TrieNode;
    pNode->isEndOfWord = false;
    pNode->containsLongest = false;
    FOR(i, 0, ALPHABET) pNode->children[i] = NULL;
    return pNode;
}

void insert(TrieNode *root, string key) {
    TrieNode *pCrawl = root;

    FOR(i, 0, key.length()) {
        int indx = key[i] - 'a';
        if (!pCrawl->children[indx]) pCrawl->children[indx] = getNode();
        pCrawl = pCrawl->children[indx];
    }
    pCrawl->isEndOfWord = true;
}

void insertLongest(TrieNode *root) {
    TrieNode *pCrawl = root;
    pCrawl->containsLongest = true;

    FOR(i, 0, longest.length()) {
        int indx = longest[i] - 'a';
        if (!pCrawl->children[indx]) pCrawl->children[indx] = getNode();
        pCrawl = pCrawl->children[indx];
        pCrawl->containsLongest = true;
    }
    pCrawl->isEndOfWord = true;
}

void dfs(TrieNode *root) {
    if (root->isEndOfWord) ops.push_back('P');
    if (root->containsLongest) {
        FOR(i, 0, ALPHABET) {
            if (root->children[i] && !(root->children[i]->containsLongest)) {
                ops.push_back(i + 'a');
                dfs(root->children[i]);
                ops.push_back('-');
            }
        }
        FOR(i, 0, ALPHABET) {
            if (root->children[i] && root->children[i]->containsLongest) {
                ops.push_back(i + 'a');
                dfs(root->children[i]);
            }
        }
    } else {
        FOR(i, 0, ALPHABET) {
            if (root->children[i]) {
                ops.push_back(i + 'a');
                dfs(root->children[i]);
                ops.push_back('-');
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

    TrieNode *root = getNode();
    FOR(i, 0, n) {
        cin >> words[i];
    }
    sort(words, words + n, cmp);
    FOR(i, 0, n - 1) {
        insert(root, words[i]);
    }
    longest = words[n - 1];
    insertLongest(root);

    dfs(root);
    cout << ops.size() << '\n';
    for (char i : ops) cout << i << '\n';
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void insert(TrieNode*, std::__cxx11::string)':
printer.cpp:3:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for(int i = x; i < y; i++)
printer.cpp:31:9:
     FOR(i, 0, key.length()) {
         ~~~~~~~~~~~~~~~~~~             
printer.cpp:31:5: note: in expansion of macro 'FOR'
     FOR(i, 0, key.length()) {
     ^~~
printer.cpp: In function 'void insertLongest(TrieNode*)':
printer.cpp:3:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for(int i = x; i < y; i++)
printer.cpp:43:9:
     FOR(i, 0, longest.length()) {
         ~~~~~~~~~~~~~~~~~~~~~~         
printer.cpp:43:5: note: in expansion of macro 'FOR'
     FOR(i, 0, longest.length()) {
     ^~~

• 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