| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1111186 | 2024-11-11T16:28:47 Z | pfv5068 | Type Printer (IOI08_printer) | C++14 | 61 ms | 34924 KB |
/*
given a N words you have to minimize the number of operations, printing can be
done in any order. Even if you have all words in a trie, how do you know from
where to start and how to traverse it. where I'm stuck is: after storing words
in trie, I found it is beneficial to print words that are near the parents
first before going down the path, since we remove letters unnecessarily.
if we assume the type printer should have no letters at the end, then the
number of operations are equal, we can use dfs without worrying about the
order.
*/
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
// ToDo: create a Trie Iterator
using namespace std;
vector<char> container;
struct Trie {
bool isEnd;
unordered_map<char, Trie *> next;
bool isSpecial;
public:
Trie() : isEnd(false), isSpecial(false), next() {}
Trie(const Trie &) = delete;
Trie(Trie &&) = delete;
void addWord(const string &word);
bool searchWord(const string &word);
void markNode(const string &word);
void dfs();
};
// O(length(word)) * N
void Trie::addWord(const string &word) {
Trie *curr = this;
for (auto &ch : word) {
auto it = curr->next.find(ch);
if (it == curr->next.end()) {
// create a new node.
Trie *node = new Trie();
curr->next[ch] = node;
}
curr = curr->next[ch];
}
curr->isEnd = true;
}
// O(length(word)) * N
bool Trie::searchWord(const string &word) {
Trie *curr = this;
for (auto &ch : word) {
auto it = curr->next.find(ch);
if (it == curr->next.end())
return false;
curr = it->second;
}
return curr->isEnd;
}
void Trie::markNode(const string &word) {
Trie *curr = this;
for (auto &ch : word) {
auto it = curr->next.find(ch);
if (it == curr->next.end())
assert(false);
curr = it->second;
curr->isSpecial = true;
}
}
void Trie::dfs() {
unordered_map<char, Trie *>::iterator specialChild = next.end();
if (isEnd)
container.push_back('P');
for (unordered_map<char, Trie *>::iterator it = next.begin();
it != next.end(); it++) {
if (it->second->isSpecial) {
specialChild = it;
continue;
}
container.push_back(it->first);
it->second->dfs();
}
if (specialChild != next.end()) {
container.push_back(specialChild->first);
specialChild->second->dfs();
}
container.push_back('-');
}
int main() {
Trie *root = new Trie();
/*
vector<const string> words{"canwatch", "watch", "prefix", "prefixOf"};
for (auto const &ch : words)
root->addWord(ch);
for (auto const &ch : words)
cout << root->searchWord(ch);
cout << root->searchWord("canw");
root->markNode("canwatch");
root->dfs();
*/
int n, len = 0;
cin >> n;
string word, bigword;
while(n-- > 0) {
cin >> word;
root->addWord(word);
if (word.size() > len) {
len = word.size();
bigword = word;
}
}
root->markNode(bigword);
root->dfs();
while (container.back() != 'P')
container.pop_back();
cout << container.size();
cout << "\n";
for (auto &p : container)
cout << p << " ";
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 336 KB | Line "t p t t t y k d u y v x j b z h q u p P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 504 KB | Line "n P - e e j z a t j m n q x c ... y o s s k u g b k i u f f d P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 336 KB | Line "r h p q t s l c P - - - - - - ... l m w f i r l g b d e v j d P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 336 KB | Line "s a c g o g p i y n P - - - - ... m s g e n n p d l u r n m v P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 336 KB | Line "g t m q p p k y P - - - - - - ... - - e y n o r w r b i z a i P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 3 ms | 1872 KB | Line "u P u d b w d m p n d k P - - ... v i w g d u d c y b a h u w P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 12 ms | 5712 KB | Line "i P x v f l k i b p f h j j a ... n i c j t u k m w m l d d z P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 30 ms | 13952 KB | Line "p P s o t w t q t P - - - - - ... k w z a k q u b h s t c d q P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 61 ms | 34924 KB | Line "d P d P e P - x P u w n p k e ... o b j b x u w l h z w c h f P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 52 ms | 26312 KB | Line "i P u P p l s q t P - - - - r ... P - - - j t e a r n h d j e P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 | Halted | 0 ms | 0 KB | - |