Submission #989823

#	Time	Username	Problem	Language	Result	Execution time	Memory
989823		Ice_man	Type Printer (IOI08_printer)	C++14	100 / 100	146 ms	99532 KiB

printer

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>

#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;


typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , ll> pil;
typedef pair <ll , int> pli;
typedef long double pd;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


struct Node
{
    int endd , sz;
    Node* p[26];
    Node()
    {
        for(int i = 0; i < 26; i++)
            p[i] = NULL;
        endd = 0;
        sz = 1;
    }
};

void _insert(string &s , Node* root)
{
    Node* node = root;
    for(char &c : s)
    {
        if(node -> p[c - 'a'] == NULL)
            node -> p[c - 'a'] = new Node;
        node = node -> p[c - 'a'];
    }
    node -> endd++;
}

void calc_sz(Node* node)
{
    node -> sz = 1;
    for(int i = 0; i < 26; i++)
    {
        if(node -> p[i] == NULL)
            continue;
        calc_sz(node -> p[i]);
        node -> sz = max(node -> sz, node -> p[i] -> sz + 1);
    }
}

vector <char> v;
int br = 0 , n;
void traverse(Node* node)
{
    for(int i = 0; i < node -> endd; i++)
        v.pb('P') , br++;

    vector <pair <int , pair <Node* , int>>> pom;
    for(int i = 0; i < 26; i++)
    {
        if(node -> p[i] == NULL)
            continue;
        pom.push_back({node -> p[i] -> sz , {node -> p[i] , i}});
    }
    sort(pom.begin() , pom.end());
    //reverse(pom.begin() , pom.end());

    for(auto e : pom)
    {
        v.pb(e.Y.Y + 'a');
        traverse(e.Y.X);
        if(br < n)
            v.pb('-');
    }
}

string s;
Node* root;

void read()
{
    root = new Node;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> s , _insert(s , root);
    calc_sz(root);
    traverse(root);
    cout << v.size() << endl;
    for(char c : v)
        cout << c << endl;
}



int main()
{

/**#ifdef ONLINE_JUDGE /// promeni
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
#endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();



    return 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