Submission #929209

#	Time	Username	Problem	Language	Result	Execution time	Memory
929209		AlphaMale06	Type Printer (IOI08_printer)	C++17	100 / 100	86 ms	59584 KiB

printer

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

vector<char> ans;

string mxlenstr;

struct node{
    int v, cnt;
    int p[26];
};

vector<node> trie;

node nw(){
    node ret;
    ret.v=trie.size();
    ret.cnt=0;
    for(int i=0; i<26; i++)ret.p[i]=-1;
    return ret;
}

void add(string s){
    int v=0;
    for(char c : s){
        if(trie[v].p[c-'a']==-1){
            trie[v].p[c-'a']=trie.size();
            trie.pb({nw()});
        }
        v=trie[v].p[c-'a'];
    }
    trie[v].cnt++;
}

void dfs(int v, int dep){
    if(v){
        for(int i=0; i<trie[v].cnt; i++)ans.pb('P');
    }
    int avoid;
    if(dep<mxlenstr.size())avoid = mxlenstr[dep]-'a';
    else{
        ans.pb('-');
        return;
    }
    for(int i=0; i< avoid; i++){
        if(trie[v].p[i]!=-1){
            ans.pb(i+'a');
            dfs(trie[v].p[i], dep+1);
        }
    }
    for(int i=25; i>=avoid; i--){
        if(trie[v].p[i]!=-1){
            ans.pb(i+'a');
            dfs(trie[v].p[i], dep+1);
        }
    }
    ans.pb('-');
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    trie.pb({nw()});
    int mxlen=0;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        if(s.size()>mxlen){
            mxlen=s.size();
            mxlenstr=s;
        }
        add(s);
    }
    dfs(0, 0);
    while(ans.back()=='-')ans.pop_back();
    cout << ans.size() << '\n';
    for(char c : ans)cout << c << '\n';
}

Compilation message (stderr)

printer.cpp: In function 'void dfs(int, int)':
printer.cpp:43:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     if(dep<mxlenstr.size())avoid = mxlenstr[dep]-'a';
      |        ~~~^~~~~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:74:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         if(s.size()>mxlen){
      |            ~~~~~~~~^~~~~~

• 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