Submission #1176711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176711		qrn	Type Printer (IOI08_printer)	C++20	10 / 100	1095 ms	40248 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;
    set<intt> idx;
    intt data = 0;
    trie() {
        kids.clear();
        idx.clear();
        data = 0;
    }
};

void add(trie *& root, string s, intt idxi) {
    intt n = (intt)s.size();
    trie *node = root;
    for(intt i = 0; i < n; i++) {
        // cout << s[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++;
        node->idx.insert(idxi);
    }
    // cout << endl;
}

void rem(trie *& root, string s, intt idxi) {
    intt n = (intt)s.size();
    trie* node = root;
    for(intt i = 0; i < n; i++) {
        // cout << s[i] << ": " << node->kids[s[i] - 'a']->data << " :: ";
        node->kids[s[i] - 'a']->data--;
        node = node->kids[s[i] - 'a'];
        // for(auto it : node->idx) cout << it << " ";
        // cout << endl;/
        node->idx.erase(node->idx.find(idxi));
    }
}

pair<intt,intt> get(trie *& root, string s) {
    intt n = (intt)s.size(), ret = 0, ret2 =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;
        } else {
            node = node->kids[s[i] - 'a'];
        }
        ret++;
        // cout << s[i] << ": ";
        // for(auto it : node->idx) cout << it << " ";
        // cout << endl;
        ret2 = *node->idx.begin();
    }
    return {ret, ret2};
}

void solve() {
    intt n;
    cin >> n;
    vector<string> a(n);
    for(string &s : a) cin >> s;
    
    trie *root = new trie();
    for(intt i = 0; i < n; i++) {
        add(root, a[i], i);
    }
    
    intt best = inf;
    vector<char> ans;
    set<intt> silinmedi;
    for(intt i = 0; i < n; i++) silinmedi.insert(i);
    for(intt i = 0; i < n; i++) {
        intt printed = 1, forthis = a[i].size() + 1;
        string curs = a[i];
        
        vector<char>forans;
        for(intt j = 0; j < a[i].size(); j++) forans.pb(a[i][j]);
        forans.pb('P');
        
        silinmedi.erase(i);
        
        intt curidx = i;
        while(printed != n) {
            silinmedi.erase(curidx);
            rem(root, curs, curidx);
            pair<intt,intt> kok = get(root, curs);
            
            
            for(intt j = 1; j <= curs.size() - kok.fi; j++) {
                forans.pb('-');
            }
            if(kok.fi == 0) {
                curidx = *silinmedi.begin();
                curs = a[curidx];
            }
            
            if(kok.fi != 0) {
                curs = a[kok.se];
                curidx = kok.se;
            }
            for(intt j = kok.fi; j < curs.size(); j++) {
                forans.pb(curs[j]);
            }
            forans.pb('P');
            printed++;
        }
        rem(root, curs, curidx);
        
        
        if(best > forans.size()) {
            best = forans.size();
            ans = forans;
        }
        for(intt j = 0; j < n; j++) {
            add(root, a[j], j);
            silinmedi.insert(j);
        }
    }
    cout << best << endl;
    for(char c : ans) {
        cout << c << endl;
    }
}

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


/*


poem
poek
poekler
elza
elzaklar




*/

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