oj.uz

Submission #1039103

# Submission time Handle Problem Language Result Execution time Memory
1039103 2024-07-30T12:53:35 Z Ludissey Type Printer (IOI08_printer) C++17
20 / 100
 59 ms 52796 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Incorrect 0 ms 348 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2652 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8596 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 21200 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 52796 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 41292 KB didn't print every word
2 Halted 0 ms 0 KB -