Submission #867296

#	Time	Username	Problem	Language	Result	Execution time	Memory
867296		Samrev	Type Printer (IOI08_printer)	C++14	20 / 100	14 ms	28964 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define LSOne(x) (x&(-x))
typedef long long int ll;
typedef long double ld;
ll t = 1;
const ll M = 1e9 + 7;
ll mod_add(ll a, ll b){
    return ((a%M) + (b %M))%M;
}
ll mod_minus(ll a , ll b){
    return ((a%M) - (b %M) + M)%M;
}
ll mod_mul(ll a, ll b){
    return ((a%M)*(b%M))%M;
}
ll power(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b % 2 == 1){
            ans = mod_mul(ans , a);
        }
        a = mod_mul(a , a);
        b = b/2;
    }
    return ans;
}
ll mod_inverse(ll a){
    return power(a, M-2);
}

ll mod_divide(ll a, ll b){
    return mod_mul(a , mod_inverse(b));
}



const ll MAX = 1e18;
 
ll lcm(ll a , ll b){
    return (a*b)/__gcd(a,b);
}
const ll N = 1e5 + 10;
const int K = 26;
int n ;
struct Vertex{
    int next[K];
    int cnt = 0;

    Vertex(){
        fill(begin(next), end(next), -1);
    }
};
vector<Vertex> trie(1);
void add_string(string &s){
    int v = 0;
    for(auto ch : s){
        int c = ch - 'a';
        if(trie[v].next[c] == -1){
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next[c];
    }
    trie[v].cnt++;
}
void traverse(int v, vector<char> &out){
    if(trie[v].cnt){
        for(int i = 0;i<trie[v].cnt;i++){
            out.push_back('P');
        }
        return;
    }
    for(int i = 0 ; i<K;i++){
        if(trie[v].next[i] == -1) continue;
        char c = i + 'a';
        out.push_back(c);
        traverse(trie[v].next[i],out);
        out.push_back('-');
    }
}
void solve(){
    cin>>n;
    for(int i = 0;i<n;i++){
        string s; cin>>s;
        add_string(s);
    }
    vector<vector<char>> res(K);
    for(int i = 0 ; i<K;i++){
        if(trie[0].next[i] == -1) continue;
        res[i].push_back(i + 'a');
        traverse(trie[0].next[i], res[i]);
    }
    sort(res.begin(),res.end(), [&](vector<char> &v1 , vector<char> &v2) -> bool {
        int sz1 = v1.size();
        int sz2 = v2.size();
        int rm1 = 0;
        int rm2 = 0;
        for(int i = sz1-1;i>=0;i--){
            if(v1[i] == 'P') break;
            rm1++;
        }
        for(int i = sz2-1;i>=0;i--){
            if(v2[i] == 'P') break;
            rm2++;
        }
        sz1-=rm1;
        sz2-=rm2;
        return (sz1<sz2);

    });
    vector<char> ans;
    for(int i = 0;i<K;i++){
        if(res[i].size() == 0) continue;
        for(auto x: res[i]) ans.push_back(x);
        ans.push_back('-');

    }
    while(ans.back() == '-'){
        ans.pop_back();
    }
    cout<<ans.size()<<"\n";
    for(auto x: ans){
        cout<<x<<"\n";
    }
    

}
int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt" , "r" , stdin);
    // freopen("output.txt" , "w", stdout);
    // cin>>t;
    while(t--){
        solve();
    }
}

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