Submission #1176720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176720		qrn	Type Printer (IOI08_printer)	C++20	100 / 100	563 ms	61492 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

// #define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e18;
const intt mxN = 1e6 + 5;
const intt L = 21;

struct trie {
    map<intt, trie*> kids;
    intt data = 0;
    trie () {
        kids.clear();
        data = 0;
    }
};

void add(trie *& root, string s) {
    intt n = (intt) s.size();
    
    trie *node = root;
    for(intt i = 0; i < n; i++) {
        if(node->kids.find(s[i] - 'a') == node->kids.end()) {
            node->kids[s[i] - 'a'] = new trie();
        }
        node = node->kids[s[i] - 'a'];
        node->data++;
    }
}

intt get(trie *& root, string s) {
    intt n = (intt) s.size();
    intt ret = 0;
    
    trie *node = root;
    for(intt i =0 ; i < n; i++) {
        if(node->kids.find(s[i] - 'a') == node->kids.end() || node->kids[s[i] - 'a']->data <= 0) {
            break;
        }
        ret++;
        node = node->kids[s[i] - 'a'];
    }
    return ret;
}

void rem(trie *& root, string s) {
    intt n = (intt) s.size();
    
    trie *node = root;
    for(intt i = 0; i < n; i++) {
        node->kids[s[i] - 'a']->data--;
        node = node->kids[s[i] - 'a'];
    }
}

bool cmp(string &a, string &b) {
    if(a.size() == b.size()) {
        return a < b;
    }
    return a.size() < b.size();
}

void solve() {
    intt n;
    cin >> n;
    vector<string> a(n);
    for(string &s : a) cin >> s;
    
    sort(ALL(a), cmp);
    
    vector<pair<intt,string>> v;
    trie *root = new trie();
    add(root, a[n-1]);
    
    for(intt i = 0; i < n - 1; i++) {
        v.pb({get(root, a[i]), a[i]});
    }
    rem(root, a[n-1]);
    
    vector<char> ans;
    sort(ALL(v));
    
    // for(auto it : v) {
    //     cout << it.fi << " " << it.se << endl;
    //     cout << endl;
    // }
    
  
    v.pb({inf, a[n-1]});
    
    string last = v[0].second;
    for(intt i = 0; i < last.size(); i++) {
        ans.pb(last[i]);
    }
    ans.pb('P');
    
    add(root, last);
    
    for(intt i = 1; i < n; i++) {
        // cout << v[i].first << " " << v[i].second << endl;
        intt cp = get(root, v[i].second);
        for(intt j = 1; j <= last.size() - cp; j++) ans.pb('-');
       
        rem(root, last);
        last = v[i].second;
        add(root, last);
        
        for(intt j = cp; j < last.size(); j++) ans.pb(last[j]);
        ans.pb('P');
    } 
    
    
    cout << ans.size() << endl;
    for(char c : ans) {
        cout << c << endl;
    }
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

• 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