Submission #745632

#	Time	Username	Problem	Language	Result	Execution time	Memory
745632		quochuy147	Type Printer (IOI08_printer)	C++14	100 / 100	101 ms	85828 KiB

printer

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define file "name" 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

int n, check[N], d, m[N];
vector <char> res;

struct trie
{
    struct node {
        int child[26];
        int cnt, exist;
    } nodes[N];

    int cur;
    trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof nodes[0].child);
        nodes[0].cnt = nodes[0].exist = 0;
    }

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof nodes[cur].child);
        nodes[cur].cnt = nodes[cur].exist = 0;
        return cur;
    }

    void insert(string s, bool check) {
        int id = 0;
        for(auto i : s) {
            int c = i - 'a';
            if(nodes[id].child[c] == -1) nodes[id].child[c] = new_node();
            id = nodes[id].child[c];
            if(check) m[id] = 1;
            nodes[id].cnt++;
        }
        nodes[id].exist++;
    }

    void dfs(int id) {
        if(d == n) {
            cout << res.size() << '\n';
            for(auto c : res) cout << c << '\n';
            exit(0);
        }
        int v_last = 0, i_last;
        for(int i = 0; i < 26; ++i) {
            int v = nodes[id].child[i];
            if(v == -1 || check[v]) continue;
            if(m[v]) {
                v_last = v;
                i_last = i;
                continue;
            }
            res.pb(i + 'a');
            for(int j = 1; j <= nodes[v].exist; ++j) {
                res.pb('P');
                d++;
            }
            check[v] = 1;
            dfs(v);
            res.pb('-');
        }
        if(v_last) {
            res.pb(i_last + 'a');
            for(int j = 1; j <= nodes[v_last].exist; ++j) {
                res.pb('P');
                d++;
            }
            check[v_last] = 1;
            dfs(v_last);
            res.pb('-');
        }
    }
};

trie T;
string s[N];
int id_mx;

void inp()
{
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        if(s[i].size() > s[id_mx].size()) id_mx = i; 
    }
    for(int i = 1; i <= n; ++i) {
        if(id_mx == i) T.insert(s[i], 1);
        else T.insert(s[i], 0);
    }
}

void solve()
{
    T.dfs(0);    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen(file".inp" , "r" , stdin);
    // freopen(file".out" , "w" , stdout);
    inp();
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10