Submission #1188964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188964		salmakaram	Type Printer (IOI08_printer)	C++20	100 / 100	163 ms	105972 KiB

printer

#include <bits/stdc++.h>

#define Pc_champs ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;

#define ll long long
//#define int long long

int const N = 1e5 + 2, LOG = 17, N2 = 2 * N + 1, M = 1e9 + 7, SQ = 400;

int n;
struct Node {
    Node *link[26];
    int state[2] = {-1, -1};
    bool End{};
};

Node *root;

void init() {
    root = new Node();
}

void insert(string &s, bool isn) {
    Node *node = root;
    for (char &i: s) {
        if (node->link[i - 'a'] == NULL) node->link[i - 'a'] = new Node();
        node = node->link[i - 'a'];
    }
    node->End = true;
}


int dfs(Node *node, bool state) {
    int &ret = node->state[state];
    if (~ret) return ret;
    ret = 0;
    if (state) {
        for (int i = 0; i < 26; ++i) {
            if (node->link[i] != NULL) {
                ret += 2 + dfs(node->link[i], 1) + node->link[i]->End;
            }
        }
    } else {
        vector<int> _0, _1;
        int ones{};
        for (int i = 0; i < 26; ++i) {
            if (node->link[i] != NULL) {
                _0.emplace_back(1 + dfs(node->link[i], 0) + node->link[i]->End);
                _1.emplace_back(2 + dfs(node->link[i], 1) + node->link[i]->End);
                ones += _1.back();
            }
        }

        ret = ones;
        for (int i = 0; i < _0.size(); ++i) {
            ret = min(ret, _0[i] + ones - _1[i]);
        }
    }
    return ret;
}

vector<char> res;

void build(Node *node, bool state) {
    int op = dfs(node, state);
    if (state) {
        for (int i = 0; i < 26; ++i) {
            if (node->link[i] != NULL) {
                res.push_back((char) (i + 'a'));
                if (node->link[i]->End) res.push_back('P');
                build(node->link[i], 1);
                res.push_back('-');
            }
        }
    } else {
        vector<int> _0, _1;
        int ones{};
        for (int i = 0; i < 26; ++i) {
            if (node->link[i] != NULL) {
                _0.emplace_back(1 + dfs(node->link[i], 0) + node->link[i]->End);
                _1.emplace_back(2 + dfs(node->link[i], 1) + node->link[i]->End);
                ones += _1.back();
            }
        }

        int id = -1;
        for (int i = 0; i < _0.size(); ++i) {
            if (_0[i] + ones - _1[i] == op) id = i;
        }

        int j = -1;
        for (int i = 0; i < 26; ++i) {
            if (node->link[i] != NULL) {
                j++;
                if (j == id) continue;
                res.push_back((char) (i + 'a'));
                if (node->link[i]->End) res.push_back('P');
                build(node->link[i], 1);
                res.push_back('-');
            }
        }

        j = -1;
        for (int i = 0; i < 26; ++i) {
            if (node->link[i] != NULL) {
                j++;
                if (j != id) continue;
                res.push_back((char) (i + 'a'));
                if (node->link[i]->End) res.push_back('P');
                build(node->link[i], 0);
            }
        }
    }
}

void dowork() {
    cin >> n;
    init();
    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        insert(s, 1);
    }

    build(root, 0);
    cout << res.size() << '\n';
    for (auto i: res) cout << i << '\n';
}


signed main() {
    Pc_champs
    int t = 1;
    //cin >> t;
    while (t--) {
        dowork();
        //cout << "\n";
    }
}

• 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