Submission #533998

#	Time	Username	Problem	Language	Result	Execution time	Memory
533998		nemethm	Type Printer (IOI08_printer)	C++17	100 / 100	191 ms	51492 KiB

printer

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <queue>

using namespace std;
using ll = long long int;
deque<char> sol;
struct trie
{
  map<char, trie> tr;
  int size = 0, ending = 0, maxl = 0;
  void insert(const string& str, int hol){
    ++size;
    if(hol == str.size()){
      ++ending;
      return;
    }
    tr[str[hol]].insert(str, hol + 1);
    maxl = max(maxl, tr[str[hol]].maxl + 1);
  }
  void erase(const string& str, int hol){
    --size;
    if(hol == str.size()){
      --ending;
      return;
    }
    tr[str[hol]].erase(str, hol + 1);
  }
  int index(const string& str, int hol){
    return 0;
  }
  void solve(){
    if(ending > 0){
      sol.push_back('P');
    }
    priority_queue<pair<int,char>> q;
    for(auto& i : tr){
      q.push({-i.second.maxl, i.first});
    }
    while(!q.empty()){
      char c = q.top().second; q.pop();
      sol.push_back(c);
      tr[c].solve();
      sol.push_back('-');
    }
  }
};


int main()
{
    trie t;
    int n;
    cin >> n;
    while(n--){
      string s;
      cin >> s;
      t.insert(s, 0);
    }
    t.solve();
    while(sol.back() == '-') sol.pop_back();
    cout << sol.size() << endl;
    for(auto i : sol){
      cout << i << "\n";
    }
    return 0;
}

Compilation message (stderr)

printer.cpp: In member function 'void trie::insert(const string&, int)':
printer.cpp:18:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if(hol == str.size()){
      |        ~~~~^~~~~~~~~~~~~
printer.cpp: In member function 'void trie::erase(const string&, int)':
printer.cpp:27:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(hol == str.size()){
      |        ~~~~^~~~~~~~~~~~~

• 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