Submission #1206057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206057		leandropina	Type Printer (IOI08_printer)	C++20	100 / 100	107 ms	58712 KiB

printer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NMAX 100005
#define int long long
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define INF 1e18
#define MOD 1000000007
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ost tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define LSB(x) ((x)&-(x))
#define count_bits(x) __builtin_popcount(x)
#define leading_zeros(x) __builtin_clz(x)
#define trailing_zeros(x) __builtin_ctz(x)
#define all(x) begin(x),end(x)
#define pb push_back
#define eps 1e-9

struct node{
    int id;
    map<char,int>next;
    node(){
        id = -1;
        next.clear();
    }
};
vector<node>tri={node()};

int new_node(){
    tri.pb(node());
    return tri.size()-1;
}

void insere(string &s, int i){
    int x = 0;
    for(auto ch:s){
        if(tri[x].next.count(ch)==0){
            tri[x].next[ch] = new_node();
        }
        x = tri[x].next[ch];
    }
    tri[x].id = i;
}

string ans="";
void solve(int x){
    if(tri[x].id != -1){
        ans.pb('P');
    }

    vector<pair<int,char>>v;
    for(auto [ch,next_ind]:tri[x].next){
        v.pb({next_ind,ch});
    }
    sort(all(v));
    for(auto [next_ind,ch]:v){
        ans.pb(ch);
        solve(next_ind);
        ans.pb('-');
    }
}

bool comp(pair<int,string> a, pair<int,string> b){
    if( a.first == b.first ) return a.second < b.second;
    return a.first < b.first;
}

int qtdd(string a, string b){
    int n = a.size();
    int m = b.size();
    int qtd = 0;
    for(int i=0;i<min(n,m);i++){
        if(a[i] == b[i]) qtd++;
        else break;
    }    
    return qtd;
}

int32_t main(){ faster
    int n; cin >> n;
    vector<pair<int,string>>vv;
    vector<string>v;
    int mx = 0; string s_mx="";
    for(int i=0;i<n;i++){
        string s; cin >> s;
        if( s.size() > mx ){
            s_mx = s; mx = s.size();
        }
        v.pb(s);
    }
    for(int i=0;i<n;i++){
        int qtdcomum = qtdd(s_mx,v[i]);
        vv.pb({qtdcomum,v[i]});
    }
    sort(all(vv),comp);
    for(int i=0;i<n;i++){
        insere(vv[i].second,i);
    }
    solve(0);
    while(ans.back()=='-') ans.pop_back();
    cout << ans.size() << '\n';
    for(auto ch:ans) cout << ch << '\n';
}
/*
7
bb
printt
the
poem
they
tt
poke

nina começa

n strings
m strings


*/

• 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