제출 #1178156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178156		giabao249	Type Printer (IOI08_printer)	C++20	0 / 100	20 ms	37956 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define el '\n'
const int N = 25005;
const int ALPHA_BET = 26;
const int inf = 2e9;
template<class T> bool ckmax(T& a, const T&b) {
    return a < b ? a = b, 1 : 0;
}
int n;
struct Node {
    Node*child[ALPHA_BET];
    int exits, best, isMax;
    Node() {
        for(int i = 0 ; i < ALPHA_BET ; i++) {
            child[i] = nullptr;
        }
        exits = 0, best = 0 , isMax = 0;
    }
};

struct state{

};
int cur = 0;
Node *root;
void addString(string s , bool maxString) {
    Node *p = root;
    for(char f : s) {
        int c = f - 'a';
        if(p->child[c] == nullptr) {
            p->child[c] = new Node();
//            p->child[c]->depth = p->depth + 1;
        }
        p = p->child[c];
        p->isMax = maxString;
    }
    p->isMax = maxString;
    p->exits++;
}
vector<char> ret;
struct State {
    Node* node;
    int idx;        // chỉ số của con đang được duyệt
    bool visited;   // dùng để đánh dấu sau khi đã thêm ký tự cho nút đó (nếu cần)
    bool chillUsed; // đánh dấu xem đã xử lý con 'chillGuy' hay chưa
};
string ans = "";
void solve_iterative(Node* root) {
    // Sử dụng stack để lưu trạng thái của các nút
    stack<State> st;
    st.push({root, 0, false, false});

    while(!st.empty()){
        State &curState = st.top();
        Node *curNode = curState.node;

        // Nếu nút hiện tại là nút kết thúc chuỗi
        if(curNode->exits > 0 && !curState.visited) {
            ans += 'P';
            st.pop();
            continue;
        }

        // Nếu đã duyệt hết các con của nút hiện tại
        if(curState.idx >= ALPHA_BET) {
            st.pop();
            if(!st.empty()){
                // Sau khi trở về nút cha, thêm dấu '-' nếu cần
                ans += '-';
            }
            continue;
        }

        // Duyệt con tại vị trí curState.idx
        Node *child = curNode->child[curState.idx];
        char letter = 'a' + curState.idx;
        curState.idx++; // tăng idx cho nút hiện tại

        if(child == nullptr)
            continue;  // bỏ qua nếu không tồn tại

        // Nếu con này là "chillGuy" (theo logic của bạn: có isMax = true)
        if(child->isMax && !curState.chillUsed) {
            // Đánh dấu đã dùng chillGuy để đảm bảo xử lý sau tất cả các con khác
            curState.chillUsed = true;
            ans += letter;
            st.push({child, 0, false, false});
        } else if(!child->isMax) {
            // Với các nút không phải chillGuy, xử lý ngay
            ans += letter;
            st.push({child, 0, false, false});
        }
    }
}


void solve(Node *p) {
    if(p->exits > 0){
        ans += ('P');
        return;
    }
    int chillGuy = -1;
    for(int i = 0 ; i < ALPHA_BET ; i++){
        if(p->child[i]){
            if(p->child[i]->isMax){
                chillGuy = i;
                continue;
            }
            ans += (char(i + 'a'));
            solve(p->child[i]);
            ans += ('-');
        }
    }
    if(chillGuy != -1){
        ans += (char(chillGuy + 'a'));
        solve(p->child[chillGuy]);
    }
}
void GOTO_OLP2025() {
    root = new Node();
    cin >> n;
    string maxString;
    int mx = 0;
    for(int i = 0 ; i < n ; i++) {
        string s ;
        cin >> s;
        addString(s , 0);
        if(ckmax(mx , (int)s.size())){
            maxString = s;
        }
    }
    addString(maxString , 1);
//    solve(root);
    solve_iterative(root);
    cout << ans.size() << el;
    for(char c : ans) cout << c << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("Task.in", "r", stdin);
    GOTO_OLP2025();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 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