oj.uz

Submission #989823

# Submission time Handle Problem Language Result Execution time Memory
989823 2024-05-28T20:14:56 Z Ice_man Type Printer (IOI08_printer) C++14
100 / 100
 146 ms 99532 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 3 ms 2392 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5980 KB Output is correct
2 Correct 17 ms 12632 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14808 KB Output is correct
2 Correct 6 ms 3420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 36556 KB Output is correct
2 Correct 109 ms 83908 KB Output is correct
3 Correct 58 ms 43176 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 28388 KB Output is correct
2 Correct 146 ms 99532 KB Output is correct
3 Correct 61 ms 49100 KB Output is correct
4 Correct 104 ms 94036 KB Output is correct