Submission #1039103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039103		Ludissey	Type Printer (IOI08_printer)	C++17	20 / 100	59 ms	52796 KiB

printer

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

using namespace std;


struct trie{
    char c;
    trie* child[27];
    vector<bool> visited;
    trie* parent;
    trie(trie* root, char _c){
        for (int i = 0; i < 27; i++) child[i]=nullptr;
        this->visited.resize(27,0);
        c=_c;
        parent=root;
    }
};

void add(trie* root, string s, int i){
    if(i==sz(s)) return;
    if(root->child[s[i]-'a']==nullptr) root->child[s[i]-'a']=new trie(root,s[i]);
    add(root->child[s[i]-'a'],s,i+1);
}

trie* find_lowest_trie(trie* root, string s, int i){
    if(i==sz(s)) return root;
    return find_lowest_trie(root->child[s[i]-'a'],s,i+1);
}

void remove_exist(trie* root ,int last){
    if(root->c==' ') return;
    for (int i = 0; i < 27; i++) {
         if(root->child[i]!=nullptr&&i!=last) return;
    }
    int nl=root->c-'a';
    root->parent->visited[nl]=true;
    remove_exist(root->parent,nl);
}

vector<char> ops;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<string> a(N);
    trie* root=new trie(nullptr,' '); 
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < N; i++) add(root,a[i],0);
    sort(all(a), [](string &_a, string &b){return sz(_a)<sz(b);});
    trie* current=find_lowest_trie(root, a[N-1], 0);
    remove_exist(current,-1);
    while(true){
        bool b=true;
        for (int i=0; i<27; i++)
        {
            if(current->child[i]==nullptr||current->visited[i]) continue;
            current->visited[i]=true;
            current=current->child[i];
            ops.push_back('-');
            b=false;
        }
        if(b) {
            if(current->c==' ') break;
            else {
                current->parent->visited[current->c-'a']=true;
                ops.push_back(current->c);
                current=current->parent;
            }
        } else continue;
    }
    vector<char> ops2;
    for (int i = sz(ops)-1; i >= 0; i--) {
        ops2.push_back(ops[i]);
        if(ops[i]!='-'&&(i==0||ops[i-1]=='-')) ops2.push_back('P');
    }
    cout << sz(ops2) << "\n";
    for (int i = 0; i < sz(ops2); i++) {
        cout << ops2[i] << "\n";
    }
    return 0;
}

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