Submission #1165996

#TimeUsernameProblemLanguageResultExecution timeMemory
1165996pinrueiType Printer (IOI08_printer)C++20
40 / 100
17 ms2116 KiB
#pragma region//         
#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#define f2(i, m) for(int i=0; i<m; i++)
#define f21(i, m) for(int i=1; i<m; i++)
#define f3(i, n, m) for(int i=n; i<m; i++)
#define f2_(i, m) for(int i=m; i>-1; i--)
#define f21_(i, m) for(int i=m; i>0; i--)
#define f3_(i, n, m) for(int i=n; i>=m; i--)
#define travG(idx) for(int i : g[idx])
#define travG_(i, idx) for(int i : g[idx])
#define trav(loop) for(int i : loop)
#define trav_(i, loop) for(int i : loop)
#define trav2(loop, idx) for(int i : loop[idx])
#define trav2_(i, loop, idx) for(int i : loop[idx])
#define ll long long
#define bs bitset
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define ve vector<element>
#define ve_ vector<element_>
#define vpii vector<pair<int, int>>
#define qi queue<int>
#define qe queue<element>
#define qpii queue<pair<int, int>>
#define si stack<int>
#define se stack<element>
#define spii stack<pair<int, int>>
#define vb vector<bool>
#define pqi priority_queue<int>
#define pqi_ priority_queue<int, vi, greater<int>>
#define pqpii priority_queue<pair<int, int>>
#define pqpii_ priority_queue<pair<int, int>, vpii, greater<pii>>
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
#define len length()
#define elif else if
#define mod 1000000007
#pragma endregion
//#define debug
/*
#ifdef debug
#endif
#ifndef debug
#endif
*/
using namespace std;

signed main()//         https://oj.uz/problem/view/IOI08_printer
{   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin>>n;
    string longest;
    vector<string> a(n);
    f2(i, n)
    {
        string s; cin>>s;
        a[i] = s;
        if(a[i].length() > longest.length()) longest=a[i];
    }
    sort(begin(a), end(a));
    
    bool flag = 1;
    function<bool(pair<int, string>, pair<int, string>)> cmp = [](const pair<int, string> a, const pair<int, string> b)
    {
        return a.first>b.first;
    };
    priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(cmp)> final(cmp); 
    queue<char> ans;
    vector<char> work;
    f2(i, n)
    {
        string &s = a[i];
        if(flag&&s==longest) 
        {
            flag = 0;
            continue;
        }
        int sameDigit=0;
        for(; sameDigit<s.length(); sameDigit++)
            if(s[sameDigit]!=longest[sameDigit]) break;
        if(sameDigit)
        {
            final.push({sameDigit, a[i]});
            continue;
        }
        int idx=0;
        for(; idx<work.size(); idx++)
            if(work[idx]!=s[idx]) break;
        f2(j, work.size()-idx) ans.push('-');
        work.resize(idx);
        f3(j, idx, s.length())
        {
            ans.push(s[j]);
            work.pb(s[j]);
        }
        ans.push('P');
    }

    final.push({longest.length()+1, longest});
    while(!final.empty())
    {
        string s = final.top().second;
        int idx=0;
        for(; idx<work.size(); idx++)
            if(work[idx]!=s[idx]) break;
        f2(j, work.size()-idx) ans.push('-');
        work.resize(idx);
        f3(j, idx, s.length())
        {
            ans.push(s[j]);
            work.pb(s[j]);
        }
        final.pop();
        ans.push('P');
    }

    cout << ans.size() << '\n';
    while(!ans.empty())
    {
        cout << ans.front() << '\n';
        ans.pop();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...