oj.uz

Submission #533998

# Submission time Handle Problem Language Result Execution time Memory
533998 2022-03-07T18:53:24 Z nemethm Type Printer (IOI08_printer) C++17
100 / 100
 191 ms 51492 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 288 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1052 KB Output is correct
2 Correct 4 ms 1228 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3140 KB Output is correct
2 Correct 20 ms 6520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7620 KB Output is correct
2 Correct 13 ms 1832 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 18932 KB Output is correct
2 Correct 138 ms 43252 KB Output is correct
3 Correct 94 ms 22472 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 14916 KB Output is correct
2 Correct 175 ms 51492 KB Output is correct
3 Correct 95 ms 25412 KB Output is correct
4 Correct 191 ms 48608 KB Output is correct