Submission #974619

#	Time	Username	Problem	Language	Result	Execution time	Memory
974619		megaminion	Type Printer (IOI08_printer)	C++17	30 / 100	62 ms	42440 KiB

printer

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e6+9;
const int B = 26;

int nxt[N][B], n, id; 
string s, t;
vector<vector<char>> ans;
bool isl[N];

void add(string s)
{
    int cur = 0;
    for(auto &ch : s)
    {
        int x = ch - 'a';
        if(nxt[cur][x] == 0)
            nxt[cur][x] = ++id;
        cur = nxt[cur][x];
    }
    isl[cur] = true;
}

void dfs(int u = 0)
{
    if(isl[u])
        ans.back().pb('P');
    for(int i = 0; i < B; ++i)
    {
        if(nxt[u][i])
        {
            if(u == 0)
                ans.emplace_back();
            ans.back().pb('a'+i);
            dfs(nxt[u][i]);
            ans.back().pb('-');
        }
    }
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i = 0; i < n; ++i)
        cin>>s, add(s);
    dfs();
    vector<pair<int, int>> v;
    int m = sz(ans);
    for(int i = 0; i < m; ++i)
    {
        int j = sz(ans[i]) - 1;
        while(j >= 0 && ans[i][j] == '-')
            --j;
        v.pb({sz(ans[i]) - j - 1, i});
    }
    sort(all(v));
    vector<char> pt;
    for(int i = 0; i < m-1; ++i)
        for(auto &c : ans[v[i].second])
            pt.pb(c);
    int t = v.back().second;
    int del = v.back().first;
    for(int i = 0; i < sz(ans[t]) - del; ++i)
    {
        pt.pb({ans[t][i]});
    }
    cout<<sz(pt)<<endl;
    for(auto &c : pt)
        cout<<c<<endl;
    return 0;
}

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