Submission #716348

#TimeUsernameProblemLanguageResultExecution timeMemory
716348kartapolovType Printer (IOI08_printer)C++14
100 / 100
374 ms119672 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #define print(x) cout << #x << " = " << x << endl; #define input(vec) for (size_t i = 0; i < vec.size(); i++) cin >> vec[i]; const long long MOD = 1000000000 + 7; using namespace std; using ll = long long; vector<char> ans; class BOR { struct Node { vector<Node*> kids = vector<Node*>(26, nullptr); bool isTerminal = false; bool isLeave = true; int length = 1000; }; public: Node *head = new Node(); void add(Node *cur, int i, string& s) { if (i == s.size()) { cur->isTerminal = true; return; } if (cur->kids[s[i] - 'a'] == nullptr) { cur->kids[s[i] - 'a'] = new Node(); cur->isLeave = false; } add(cur->kids[s[i] - 'a'], i + 1, s); } void output(Node *cur, char data) { if (cur == nullptr) return; for (int i = 0 ; i < 26; i++) output(cur->kids[i], 'a' + i); cout << data << "->"<<cur->isTerminal<<"->" << cur->length << ' '; } int whatLength(Node *cur) { return (cur == nullptr ? 0 : cur->length); } void count(Node *cur) { if (cur == nullptr) return; if (cur->isLeave) { cur->length = 1; return; } for (auto kid : cur->kids) count(kid); for (auto kid : cur->kids) cur->length = max(cur->length, whatLength(kid) + 1); return; } void count() { count(this->head); return; } void dfs(Node *cur, char data) { if (cur == nullptr) return; ans.push_back(data); if (cur->isTerminal) ans.push_back('P'); vector<pair<int, int>> fake(cur->kids.size()); for (int i = 0; i < cur->kids.size(); i++) fake[i] = {whatLength(cur->kids[i]), i}; sort(fake.begin(), fake.end()); for (int i = 0; i < fake.size(); i++) dfs(cur->kids[fake[i].second], 'a' + fake[i].second); ans.push_back('-'); return; } }; void solve(BOR& S) { int n, t; cin >> n; t = n; while (t--) { string s; cin >> s; S.add(S.head, 0, s); } S.count(); //S.output(S.head, '*'); cout << endl; S.dfs(S.head, '*'); int q = 0; for (int i = ans.size(); i >= 0 && ans[i] != 'P'; i--) q++; cout << ans.size() - q << '\n'; for (int i = 1; i <= ans.size() - q; i++) cout << ans[i] << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); BOR S; int t=1; //cin >> t; while (t--) solve(S); return 0; }

Compilation message (stderr)

printer.cpp: In member function 'void BOR::add(BOR::Node*, int, std::string&)':
printer.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             if (i == s.size()) {
      |                 ~~^~~~~~~~~~~
printer.cpp: In member function 'void BOR::dfs(BOR::Node*, char)':
printer.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BOR::Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i = 0; i < cur->kids.size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~
printer.cpp:82:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for (int i = 0; i < fake.size(); i++) dfs(cur->kids[fake[i].second], 'a' + fake[i].second);
      |                             ~~^~~~~~~~~~~~~
printer.cpp: In function 'void solve(BOR&)':
printer.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 1; i <= ans.size() - q; i++)
      |                     ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...