Submission #1280353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280353		peanut	Type Printer (IOI08_printer)	C++20	100 / 100	61 ms	51420 KiB

printer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pb push_back

const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;
const int nodecnt = 500000;
const int alpha = 26;

struct node
{
    int child[alpha], exist;
} nodes[nodecnt];

struct trie
{
    int cur;
    trie(): cur(0)
    {
        memset(nodes[0].child, -1, sizeof nodes[0].child);
        nodes[0].exist = 0;
    }
    int new_node()
    {
        cur++;
        memset(nodes[cur].child, -1, sizeof nodes[cur].child);
        nodes[cur].exist = 0;
        return cur;
    }
    void add(string &s)
    {
        int pos = 0;
        for (auto c : s)
        {
            if (nodes[pos].child[c-'a'] == -1) nodes[pos].child[c-'a'] = new_node();
            pos = nodes[pos].child[c-'a'];
        }
        nodes[pos].exist++;
    }
    void dfs(int pos, string &s, int depth, vector<char> &res)
    {
        if (pos == -1) return ;
        int skipped = -1;
        if (nodes[pos].exist != 0) res.pb('P');
        for (int i = 0; i < alpha; i++)
        {
            if (nodes[pos].child[i] != -1)
            {
                if (i == s[depth] - 'a') skipped = i;
                else
                {
                    res.pb(char(i+'a'));
                    dfs(nodes[pos].child[i], s, depth + 1, res);
                }
            }
        }
        if (skipped != -1)
        {
            res.pb(char(skipped + 'a'));
            dfs(nodes[pos].child[skipped], s, depth + 1, res);
        }
        res.pb('-');
    }
};

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    int n; cin >> n;
    trie tr;
    vector<string> a(n);
    for (auto &i : a)
    {
        cin >> i;
        tr.add(i);
    }

    sort(all(a), [](string &a, string &b) {return a.size() > b.size();});

    vector<char> res;
    tr.dfs(0, a[0], 0, res);
    while (res.back() == '-') res.pop_back();
    cout << res.size() << '\n';
    for (auto i : res) cout << i << '\n';
    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