oj.uz

Submission #588615

# Submission time Handle Problem Language Result Execution time Memory
588615 2022-07-03T17:02:01 Z leeh18 Type Printer (IOI08_printer) C++17
100 / 100
 193 ms 99124 KB 
// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());

void set_io(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

struct node {
    int max_len;
    bool check;
    array<unique_ptr<node>, 26> ch;
    node() : max_len(0), check(false) {}
    void insert(const string &s, int pos = 0) {
        if (sz(s) == pos) {
            check = true;
            return;
        }
        auto c = int(s[pos] - 'a');
        if (ch[c] == nullptr) {
            ch[c] = make_unique<node>();
        }
        ch[c]->max_len = max(ch[c]->max_len, sz(s));
        ch[c]->insert(s, pos + 1);
    }
    void dfs(vector<char>& ans) const {
        vector<pair<int, int>> pool;
        for (int i = 0; i < sz(ch); i++) {
            if (ch[i]) {
                pool.push_back({ch[i]->max_len, i});
            }
        }
        if (check) {
            ans.push_back('P');
        }
        sort(pool.begin(), pool.end());
        for (auto [val, idx] : pool) {
            ans.push_back(char('a' + idx));
            ch[idx]->dfs(ans);
            ans.push_back('-');
        }
    }
};

void solve() {
    int n;
    cin >> n;
    node trie;
    int mx = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        trie.insert(s);
        mx = max(mx, sz(s));
    }
    vector<char> ans;
    trie.dfs(ans);
    ans.resize(sz(ans) - mx);
    cout << ans.size() << '\n';
    for (auto x : ans) {
        cout << x << '\n';
    }
}

auto main() -> signed {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message

printer.cpp: In function 'void set_io(std::string)':
printer.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:34:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5972 KB Output is correct
2 Correct 22 ms 12472 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14680 KB Output is correct
2 Correct 8 ms 3244 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 36356 KB Output is correct
2 Correct 168 ms 83264 KB Output is correct
3 Correct 109 ms 42776 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 28424 KB Output is correct
2 Correct 193 ms 99124 KB Output is correct
3 Correct 110 ms 48980 KB Output is correct
4 Correct 188 ms 94020 KB Output is correct