Submission #222914

#	Time	Username	Problem	Language	Result	Execution time	Memory
222914		miello	Type Printer (IOI08_printer)	C++11	100 / 100	258 ms	101224 KiB

printer

#include <bits/stdc++.h>

using namespace std;
const int MXN = 25005;

struct node {
    bool finalword = false , need = false;
    struct node* alpha[26];
    node() {
        for(int i = 0 ; i < 26 ; i++){
            this->alpha[i] = nullptr;
        }
    }
};

vector<char> ans;
vector<string> s;

void insert(node* now , string s , int idx , bool fin) {
    if(s.size() == idx) {
        now->need = true;
        return;
    }
    if(now->alpha[s[idx] - 'a'] == nullptr){
        now->alpha[s[idx] - 'a'] = new node();
        now->alpha[s[idx] - 'a']->finalword = fin;
    }
    insert(now->alpha[s[idx] - 'a'] , s , idx + 1 , fin);
}   

void dfs(node* now) {
    if(now->need) {
        ans.push_back('P');
    }
    for(int i = 0 ; i < 26 ; i++){
        if(now->alpha[i] != nullptr) {
            if(!now->alpha[i]->finalword) {
                ans.push_back('a' + i);
                dfs(now->alpha[i]);
                ans.push_back('-');
            }
        }
    }
    for(int i = 0 ; i < 26 ; i++){
        if(now->alpha[i] != nullptr) {
            if(now->alpha[i]->finalword) {
                ans.push_back('a' + i);
                dfs(now->alpha[i]);
            }
        }
    }
}

int main(){
    int n;
    scanf("%d" ,&n);
    for(int i = 0 ; i < n ; i++){
        string a;
        cin >> a;
        s.push_back(a);
    }
    sort(s.begin() , s.end() , [](string a , string b) {
        return a.size() > b.size();
    });
    node* root = new node();
    for(int i = 0 ; i < n ; i++) {
        if(i == 0) {
            insert(root, s[i], 0, true);
            continue;
        }
        insert(root, s[i], 0, false);
    }
    // printf("%d" ,root->alpha['p' - 'a']->alpha['r' - 'a']->finalword);
    dfs(root);
    printf("%d\n", ans.size());
    for(auto i : ans) {
        printf("%c\n" ,i);
    }
}

Compilation message (stderr)

printer.cpp: In function 'void insert(node*, std::__cxx11::string, int, bool)':
printer.cpp:20:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s.size() == idx) {
        ~~~~~~~~~^~~~~~
printer.cpp: In function 'int main()':
printer.cpp:75:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", ans.size());
                    ~~~~~~~~~~^
printer.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d" ,&n);
     ~~~~~^~~~~~~~~~

• 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