Submission #932006

#	Time	Username	Problem	Language	Result	Execution time	Memory
932006		rahidilbayramli	Type Printer (IOI08_printer)	C++17	100 / 100	96 ms	113336 KiB

printer

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

#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<char>res;
string maxs;

struct triee{
    struct tr{
        ll a[26];
        tr(ll x = -1){
            memset(a, x, sizeof(a));
        }
    };
    vl vis;
    vector<tr>v;
    triee() : v({tr()}), vis({0}) {}

    void add(string s)
    {
        ll node = 0;
        for(auto u : s)
        {
            ll ch = u - 'a';
            if(v[node].a[ch] == -1)
            {
                v[node].a[ch] = (ll)v.size();
                v.pb(tr());
                vis.pb(0LL);
            }
            node = v[node].a[ch];
        }
        vis[node] = 1;
    }

    void dfs(ll node, ll depth)
    {
        if(vis[node])
        {
            res.pb('P');
            vis[node] = 0;
        }
        if(depth == (ll)maxs.size())
            return;
        ll ch = maxs[depth] - 'a';
        for(ll i = 0; i < 26; i++)
        {
            if(i != ch && v[node].a[i] != -1)
            {
                res.pb(i + 'a');
                dfs(v[node].a[i], depth+1);
                res.pb('-');
            }
        }
        if(v[node].a[ch] != -1)
        {
            res.pb(ch + 'a');
            dfs(v[node].a[ch], depth+1);
            res.pb('-');
        }
    }
} y;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests = 1;
    //cin >> tests;
    while(tests--)
    {
        ll n, i;
        cin >> n;
        for(i = 0; i < n; i++)
        {
            string s;
            cin >> s;
            if(s.size() > maxs.size())
                maxs = s;
            y.add(s);
        }
        y.dfs(0LL, 0LL);
        while(res.back() == '-')
            res.pop_back();
        cout << (ll)res.size() << "\n";
        for(auto u : res)
            cout << u << "\n";
    }
}

Compilation message (stderr)

printer.cpp: In constructor 'triee::triee()':
printer.cpp:32:15: warning: 'triee::v' will be initialized after [-Wreorder]
   32 |     vector<tr>v;
      |               ^
printer.cpp:31:8: warning:   'std::vector<long long int> triee::vis' [-Wreorder]
   31 |     vl vis;
      |        ^~~
printer.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     triee() : v({tr()}), vis({0}) {}
      |     ^~~~~

• 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