Submission #939804

#	Time	Username	Problem	Language	Result	Execution time	Memory
939804		codefox	Type Printer (IOI08_printer)	C++14	100 / 100	102 ms	34380 KiB

printer

#include<bits/stdc++.h>

using namespace std;

#define pii pair<char, int>

vector<vector<pii>> trie;
vector<int> tc;
vector<int> notgo;
vector<char> comm;

void dfs(int i)
{
    pii nogo = {0, -1};
    for (int j = 0; j < tc[i]; j++) comm.push_back('P');
    for (pii ele:trie[i])   
    {
        if (notgo[ele.second]) 
        {
            nogo = ele;
            continue;
        }
        comm.push_back(ele.first);
        dfs(ele.second);
        comm.push_back('-'); 
    }
    if (nogo.second==-1) return;
    comm.push_back(nogo.first);
    dfs(nogo.second);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n;

    trie.assign(n*20+1, vector<pii>());
    tc.assign(n*20+1, 0);
    notgo.assign(n*20+1, 0);
    int d = 0;

    vector<string> ns(n);
    int longest = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> ns[i];
        if (ns[i].size()>ns[longest].size()) longest = i;
    }

    for (int i =0 ; i < n; i++)
    {
        int curr = 0;
        for (char c:ns[i])
        {
            bool done = 0;
            for (pii ele:trie[curr])
            {
                if (ele.first == c)
                {
                    done = 1;
                    curr = ele.second;
                }
            }
            if (!done)
            {
                trie[curr].push_back({c, ++d});
                curr = d;
            }
            if (longest==i) notgo[curr] = 1;
        }
        tc[curr]++;
    }

    dfs(0);

    cout << comm.size() << "\n";
    for (char c:comm) cout << c << "\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