Submission #525591

#	Time	Username	Problem	Language	Result	Execution time	Memory
525591		AngusWong	Type Printer (IOI08_printer)	C++17	100 / 100	221 ms	72328 KiB

printer

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

int n;
string s[25001];
vector<pair<pair<char, int>, vector<int> > > trie;
vector<int> l, mx;
string ans;

void insert(string s, int p=0, int t=0){
    if (p==s.length()){
        trie[t].f.s=1;
        return;
    }
    if (!trie[t].s[s[p]-'a']){
        trie.push_back({{s[p], 0}, vector<int>(26, 0)});
        trie[t].s[s[p]-'a']=trie.size()-1;
    }
    insert(s, p+1, trie[t].s[s[p]-'a']);
}

void dfs(int x, int len=0){
    l[x]=len;
    for (int i=0; i<26; i++){
        if (!trie[x].s[i]) continue;
        dfs(trie[x].s[i], len+1);
        if (l[trie[x].s[i]]>=l[x]){
            l[x]=l[trie[x].s[i]], mx[x]=i;
        }
    }
}

void dfs2(int x){
    if (trie[x].f.f!='!') ans+=trie[x].f.f;
    if (trie[x].f.s) ans+='P';
    for (int i=0; i<26; i++){
        if (!trie[x].s[i]) continue;
        if (i!=mx[x]) dfs2(trie[x].s[i]);
    }
    if (mx[x]!=-1) dfs2(trie[x].s[mx[x]]);
    ans+='-';
}

int main() {
    trie.push_back({{'!', 0}, vector<int>(26, 0)});
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> s[i];
        insert(s[i]);
    }
    l=mx=vector<int>(trie.size(), -1);
    dfs(0);
    dfs2(0);
    while (ans.back()=='-') ans.pop_back();
    cout << ans.length() << "\n";
    for (char c: ans) cout << c << "\n";
    vector<string> v;
    string now;
    for (char c: ans){
        assert(c=='-' || c=='P' || (c>='a' && c<='z'));
        if (c=='-') now.pop_back();
        else if (c=='P') v.push_back(now);
        else now+=c;
    }
    assert(v.size()==n);
    sort(v.begin(), v.end());
    sort(s+1, s+n+1);
    for (int i=1; i<=n; i++) assert(v[i-1]==s[i]);
}

Compilation message (stderr)

printer.cpp: In function 'void insert(std::string, int, int)':
printer.cpp:13:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if (p==s.length()){
      |         ~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from printer.cpp:1:
printer.cpp: In function 'int main()':
printer.cpp:67:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |     assert(v.size()==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