Submission #1176372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176372		kuroudo	Type Printer (IOI08_printer)	C++20	0 / 100	322 ms	68844 KiB

printer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define int int64_t
using namespace std;
using namespace __gnu_pbds;

template <typename T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10, mod = 1e9+7;

// This isn't part of my plan
struct Trie {
    struct Node {
        static const int MX = 29;
        int children[MX] = {};
        int f = 0;
    };

    vector<Node> trie;
    Trie() {
        trie.emplace_back();
    }

    void insert(string& s) {
        int idx = 0;
        for(auto i : s) {
            int nxt = i-'a';

            if(trie[idx].children[nxt] == 0) {
                trie[idx].children[nxt] = trie.size();
                trie.emplace_back();
            }
            idx = trie[idx].children[nxt];
            trie[idx].f++;
        }
    }

    void erase(string& s) {
        int idx = 0;
        for(auto i : s) {
            int nxt = i-'a';

            idx = trie[idx].children[nxt];
            trie[idx].f--;
        }
    }

    int query(string& s) {
        int idx = 0;
        int ret{};
        for(auto i : s) {
            int nxt = i - 'a';
            if(trie[trie[idx].children[nxt]].f == 0) return 0;
            idx = trie[idx].children[nxt];
        }
        return trie[idx].f;
    }
};

map<string ,int> ans;
bool comp(string x, string y){
    if(ans[x] == ans[y]) return x.size() < y.size();
    return ans[x] < ans[y];

}
int add(long long a, int b) {
    return (a + b + mod)%mod;
}

int mul(long long a, int b) {
    return (a*b)%mod;
}
// recursive
int fp(int b, int p) {
    if(!p) return 1;
    int hp = fp(b, p >> 1);
    hp = mul(hp, hp);
    return (p&1 ? mul(hp, b) : hp);
}
//iterative
int fp2(int b,int p){
   int ret=1;
   while(p){
       if(p&1) ret=mul(ret,b);
       p>>=1;
       b = mul(b,b);
    }
    return ret;
}

int Inv(int a) {
    return fp(a, mod-2);
}

int divi(int a, int b) {
    return mul(a, Inv(b));
}
const int BN = 2, ch_offset = 'a' - 1; 
const int base[BN] = { 31, 37 }; 
int pw[N][BN], inv[N][BN]; 
 
void initPows() { 
    for (int i = 0; i < BN; i++) { 
        pw[0][i] = inv[0][i] = 1; 
        int b_inv = fp(base[i], mod - 2); 
        for (int j = 1; j < N; j++) { 
            pw[j][i] = mul(pw[j - 1][i], base[i]); 
            inv[j][i] = mul(inv[j - 1][i], b_inv); 
        } 
    } 
} 
struct Hash { 
    array<int, BN> val; 
    int sz; 
 
    Hash(array<int, BN> val = {}, int sz = 0) : val(val), sz(sz) {} 
    Hash(char c) { 
        sz = 1; 
        for (int i = 0; i < BN; i++) 
            val[i] = c - ch_offset; 
    } 
 
    bool operator<(const Hash& other) const { 
        return val < other.val; 
    } 
    bool operator==(const Hash& other) const { 
        return sz == other.sz && val == other.val; 
    } 
    Hash operator+(const Hash& other) const { 
        Hash ret; 
        for (int i = 0; i < BN; i++) 
            ret.val[i] = add(val[i], mul(other.val[i], pw[sz][i])); 
        ret.sz = sz + other.sz; 
        return ret; 
    } 
    Hash operator-(const Hash& other) const { 
        Hash ret; 
        for (int i = 0; i < BN; i++) 
            ret.val[i] = mul(add(val[i], -other.val[i]), inv[other.sz][i]); 
        ret.sz = sz - other.sz; 
        return ret; 
    } 
}; 
struct RabinKarp { 
    //1-based 
    vector<Hash> hashes; 
    RabinKarp(string& s) { 
        hashes.resize(s.size() + 1); 
        hashes[0] = Hash(); 
        for (int i = 1; i <= s.size(); i++) 
            hashes[i] = hashes[i - 1] + Hash(s[i - 1]); 
    } 
 
    Hash getHash(int l, int r) { 
        return hashes[r] - hashes[l - 1]; 
    } 
}; 
void burn() {
    initPows(); 
    int n;
    cin >> n;
    // ans = vector<int>(n);

    Trie tr;
    vector<string > v(n);

    vector<RabinKarp> hshs;
    for(int i = 0;i < n;i++) {
        cin >> v[i];
        tr.insert(v[i]);
    }
    for(int i = 0;i < n;i++) {
        for(int j = 0 ;j < v[i].size()+1;j++) {
            string cur = v[i].substr(0,j);
            ans[v[i]] = max(ans[v[i]],tr.query(cur));
        }
    }
    
    sort(v.begin(),v.end(),comp);
    for(int i = 0;i < n;i++) {
        hshs.push_back(RabinKarp(v[i]));
    } 
    int strt{};

    string prnt;
    for(int i = 0 ; i < n-1;i++) {
        string x = v[i];
        
        cerr << x << ' ' << strt << '\n';

        for(int j = strt ; j  < x.size();j++) 
            prnt+=x[j]; //cout << x[j] << '\n';
        // cout << "P\n";
        prnt +="P";
        strt = x.size();
        cerr << strt << ' ';

        for(int j = strt-1; j >= 0; j--) {
            strt--;
            if(hshs[i].getHash(1,strt+1) == hshs[i+1].getHash(1,strt+1) ) break;
            // cout << "-\n";
            prnt += "-";
        }
        cerr << strt <<'\n';
    }
    string x = v[n-1];

    for(int  i = strt+1;i < x.size();i++)
        prnt += x[i];
        // cout << x[i] << '\n';
    // cout << "P\n";
    prnt += "P";

    cout << prnt.size() << '\n';

    for(auto c: prnt)
        cout << c << '\n';
}

int32_t main() {
    ios::sync_with_stdio(false);    
    cin.tie(nullptr);

    int t{1};
    // cin >> t;
    while (t--) 
        burn();    
    return 0;
}

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