제출 #1134994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134994		em4ma2	Type Printer (IOI08_printer)	C++20	100 / 100	141 ms	96672 KiB

printer

//                          اللهم صل على محمد وعلى ال محمد كما صليت على ابراهيم وعلى ال ابراهيم انك حميد مجيد
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define pb push_back
#define endl '\n'
#define applejuice ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define fi first
#define se second

const int mod=1e9+7;
const int inf=LLONG_MAX;
const int mxsz=1e6+1;
int off=1;

int n;
int trie[mxsz][26],mx[mxsz];
char c[mxsz];
bool en[mxsz];
int cnt=0;

bool cmp(int a,int b){
    return mx[a]<mx[b];
}

void insert(string x){
    int node=0,size=x.size();
    for (int i=0;i<size;i++){
        mx[node]=max(mx[node],size-i);
        if (trie[node][x[i]-'a']==0){
            trie[node][x[i]-'a']=cnt+1;
            cnt++;
        }
        node=trie[node][x[i]-'a'];
        c[node]=x[i];
    }
    en[node]=true;
}

vector<char>ans;
int cur=0;
bool flag=false;
void dfs(int node=0){
    if (en[node]){
        ans.pb('P');
        cur++;
        if (cur==n)flag=true;
    }
    sort(trie[node],trie[node]+26,cmp);
    for (int i=0;i<26;i++){
        if (!trie[node][i])continue;
        ans.pb(c[trie[node][i]]);
        dfs(trie[node][i]);
    }
    if (!flag){
        ans.pb('-');
    }
}

signed main() {
    applejuice;

    cin>>n;
    for (int i=0;i<n;i++){
        string s;
        cin>>s;
        insert(s);
    }
    dfs();
    cout<<ans.size()<<endl;
    for (auto x:ans){
        cout<<x<<endl;
    }
    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