제출 #1224331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224331		Muhammet	Type Printer (IOI08_printer)	C++20	100 / 100	75 ms	51132 KiB

printer

#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define SZ(s) (int)s.size()
#define ff first
#define ss second

const int N = (3e4 + 5);
const int M = 1e9 + 7;

int v[N * 26][26], T, cnt[N * 26], sz[N * 26];

string s;

vector <char> ans; 

void upd(int nd, int ind) {
    if(ind == SZ(s)) {
        cnt[nd]++;
        sz[nd] = max(sz[nd], SZ(s));
        return;
    }
    int t = (s[ind] - 'a');
    if(!v[nd][t]) v[nd][t] = ++T;
    upd(v[nd][t], ind+1);
    sz[nd] = max(sz[nd], sz[v[nd][t]]);
}

void fnd(int nd) {
    for(int i = 0; i < cnt[nd]; i++) {
        ans.push_back('P');
    }
    int mx = 0, x = -1, c;
    for(int i = 0; i < 26; i++) {
        if(v[nd][i]) {
            if(sz[v[nd][i]] > mx) {
                if(~x) {
                    ans.push_back(char('a' + c));
                    fnd(x);
                }
                mx = sz[v[nd][i]];
                x = v[nd][i];
                c = i;
            }
            else {
                ans.push_back(char('a' + i));
                fnd(v[nd][i]);
            }
        }
    }
    if(~x) {
        ans.push_back(char('a' + c));
        fnd(x);
    }
    ans.push_back('-');
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;
    while(n--) {
        cin >> s;
        upd(0, 0);
    }

    fnd(0);

    while(SZ(ans) and ans.back() == '-')
        ans.pop_back();

    cout << SZ(ans) << "\n";
    for(auto i : ans) {
        cout << i << "\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