Submission #1177233

#TimeUsernameProblemLanguageResultExecution timeMemory
1177233yousuf11Type Printer (IOI08_printer)C++20
10 / 100
64 ms59500 KiB
#include <unordered_map>
#include <unordered_set>
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Ishouldbeunrated ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int ll
typedef long long ll;
typedef long double ld;
const string Y[2] = {"NO\n", "YES\n"};
const int inf = 1e18;
const int mod = 1e9 + 7;
const ld pi = acos(-1);
const int SZ = 27;
struct Trie
{
    struct Node
    {
        int ch[SZ];
        int f = 0;
    };
    vector<Node> trie;
    Trie() { trie.emplace_back(); }
    void insert(string& s)
    {
        int node = 0;
        int d = 1;
        for (char&c : s)
        {
            int i = c - 'a';
            if (!trie[node].ch[i])
            {
                trie[node].ch[i] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].ch[i];
            ++trie[node].f;
            ++d;
        }
    }
    void remove(string& s)
    {
        int node = 0;
        for (char&c : s)
        {
            int i = c - 'a';
            int p = node;
            node = trie[node].ch[i];
            --trie[node].f;
        }
    }
    int query(string s)
    {
        int node = 0;
        int len = 0;
        for (char&c : s)
        {
            int i = c - 'a';
            if(trie[trie[node].ch[i]].f <= 1) return len;
            node = trie[node].ch[i];
            ++len;
        }
        return len;
    }
    vector<char> op;
    void print(int node)
    {
        bool f = false;
        vector<pair<int,int>> to;
        for(int i = 0; i < 26; ++i)
            if(trie[node].ch[i])
                to.emplace_back(trie[trie[node].ch[i]].f, i);
        if(to.empty()) op.push_back('P');
        sort(all(to));
        for(auto i : to)
        {
            op.push_back(i.second + 'a');
            print(trie[node].ch[i.second]);
            op.push_back('-');
        }
    }
};

void die()
{
    int n;
    cin >> n;
    string x;
    Trie tr;
    set<string> s;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        s.insert(x);
    }
    for(auto i : s) tr.insert(i);
    tr.print(0);
    while(tr.op.back() == '-') tr.op.pop_back();
    cout << tr.op.size() << "\n";
    for(auto i : tr.op) cout << i << "\n";
}

bool turnTheTestCasesOn = false;
signed main()
{
    Ishouldbeunrated
    int __testCases__ = 1;
    if(turnTheTestCasesOn)
        cin >> __testCases__;
    while (__testCases__--)
        die();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...