Submission #1369577

#TimeUsernameProblemLanguageResultExecution timeMemory
1369577musanna47Type Printer (IOI08_printer)C++20
100 / 100
85 ms50204 KiB
// Author: Muhtasim Hossain Musanna (Musanna47 / mhmusanna)

#include "bits/stdc++.h"

using namespace std;


#define nl "\n"
#define REPF(_i, _a, _b) for(int _i = _a; _i <= _b; _i++)
#define REPB(_i, _a, _b) for(int _i = _a; _i >= _b; _i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define sza(_x) ((int)_x.size())
#define all(_x) _x.begin(), _x.end()
#define sort_des(_x) sort(all(_x), greater())
#define min_heap(_T, _pq, _cmp) auto _cmp = greater(); priority_queue<_T, vector<_T>, decltype(_cmp)> _pq(_cmp)


template <typename T1, typename T2>
using P = pair<T1, T2>;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;
template <typename T>
using VVVV = V<V<V<V<T>>>>;


using S = string;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = P<int, int>;
using pll = P<ll, ll>;
using vi = V<int>;
using vvi = VV<int>;
using vll = V<ll>;
using vvll = VV<ll>;
using vpii = V<pii>;
using vpll = V<pll>;


template <typename T>
void pout(T a, string sep = " ", string fin = "\n") {
    cout << a.first << sep << a.second << fin;
}

template <typename T>
void print(T& a, ll l, ll r, string sep = " ", string fin = "\n") {
    for (ll i = l; i <= r; i++)
        cout << a[i] << sep;
    cout << fin;
}

template <typename T>
void printPairs(T& a, ll l, ll r, string fin = "\n") {
    for (ll i = l; i <= r; i++)
        pout(a[i]);
    cout << fin;
}

template <typename T>
void printAll(T& a, string sep = " ", string fin = "\n") {
    for (auto& ele : a)
        cout << ele << sep;
    cout << fin;
}

template <typename T>
void printPairsAll(T& a, string fin = "\n") {
    for (auto& ele : a)
        pout(ele);
    cout << fin;
}

template <typename... Args>
void read(Args&... args) {
    ((cin >> args), ...);
}

template <typename... Args>
void out(Args... args) {
    ((cout << args << " "), ...);
}

template <typename... Args>
void outln(Args... args) {
    ((cout << args << " "), ...);
    cout << nl;
}

template <typename T>
void vin(T& a, ll l, ll r) {
    for (ll i = l; i <= r; i++)
        cin >> a[i];
}

template <typename T>
void makeUnique(T& a) {
    a.erase(unique(all(a)), a.end());
}


using bll = __int128;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const double EPS = 1e-12;

mt19937_64 rnd(239);
//mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());


void prec() {
}


const int N = 5e5 + 10;
int trie[N][26];
int mx[N];
bool isWord[N];
char letter[N];
int tot = 0;
S ans;

inline namespace Trie {
    void add(S& s) {
        int u = 0;
        for (auto& c : s) {
            int x = c - 'a';
            if (!trie[u][x])
                trie[u][x] = ++tot;
            u = trie[u][x];
            letter[u] = c;
        }
        isWord[u] = true;
    }

    void dfs1(int u = 0) {
        mx[u] = 1;
        int cmx = 0;
        REPF(i, 0, 25) {
            if (trie[u][i]) {
                dfs1(trie[u][i]);
                cmx = max(cmx, mx[trie[u][i]]);
            }
        }
        mx[u] += cmx;
    }

    void dfs2(int u = 0) {
        if (u) {
            ans.push_back(letter[u]);
            if (isWord[u]) ans.push_back('P');
        }
        vpii a;
        REPF(i, 0, 25) {
            if (trie[u][i]) {
                a.emplace_back(mx[trie[u][i]], trie[u][i]);
            }
        }
        sort(all(a));
        for (auto& [x, v] : a) {
            dfs2(v);
        }
        if (u) {
            ans.push_back('-');
        }
    }
}

void solve() {
    int n;
    read(n);
    REPF(i, 1, n) {
        S s;
        read(s);
        add(s);
    }
    dfs1();
    dfs2();
    while (!ans.empty() && ans.back() == '-') ans.pop_back();
    cout << sza(ans) << nl;
    for (auto& c : ans) {
        cout << c << nl;
    }
}


void OJ() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

signed main() {
    // OJ();

    cin.tie(0)->sync_with_stdio(0);

    // cout << fixed << setprecision(10);

    // prec();

    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; i++) {
        // cout << "Case " << i << ": ";
        solve();
    }

    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void OJ()':
printer.cpp:198:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:199:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...