oj.uz

Submission #716348

# Submission time Handle Problem Language Result Execution time Memory
716348 2023-03-29T17:58:07 Z kartapolov Type Printer (IOI08_printer) C++14
100 / 100
 374 ms 119672 KB 
#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

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++)
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 1236 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2132 KB Output is correct
2 Correct 8 ms 2644 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7028 KB Output is correct
2 Correct 47 ms 14924 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17636 KB Output is correct
2 Correct 16 ms 3820 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 43876 KB Output is correct
2 Correct 339 ms 100680 KB Output is correct
3 Correct 163 ms 51656 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 34340 KB Output is correct
2 Correct 374 ms 119672 KB Output is correct
3 Correct 181 ms 59180 KB Output is correct
4 Correct 326 ms 113460 KB Output is correct