oj.uz

Submission #229324

# Submission time Handle Problem Language Result Execution time Memory
229324 2020-05-04T08:18:40 Z andreiomd Type Printer (IOI08_printer) C++11
100 / 100
 66 ms 4208 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 25e3 + 1, LgMAX = 21;

int N;

struct Word
{
    char S[LgMAX];
};

Word A[NMAX];

int K;
char St[NMAX];

int Max;
char V[LgMAX];

vector < char > Sol;

static inline void Load ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for(int i = 1; i <= N; ++i)
        cin >> ((A[i].S) + 1);

    Max = (int)strlen(A[1].S + 1);
    for(int i = 1; i <= Max; ++i)
        V[i] = A[1].S[i];

    for(int i = 2; i <= N; ++i)
    {
        int Now = (int)strlen(A[i].S + 1);

        if(Now <= Max)
            continue;

        Max = Now;

        for(int j = 1; j <= Max; ++j)
            V[j] = A[i].S[j];
    }

    return;
}

static inline int Count (Word X)
{
    int r = 0;

    for(int i = 1; i <= Max; ++i)
        if(X.S[i] == V[i])
            ++r;
        else
            break;

    return r;
}

auto cmp = [] (Word A, Word B)
{
    int lcp_A = Count(A);
    int lcp_B = Count(B);

    if(lcp_A < lcp_B)
        return 1;

    if(lcp_A > lcp_B)
        return 0;

    if(strcmp(A.S + 1, B.S + 1) < 0)
        return 1;

    return 0;
};

static inline void Solve ()
{
    sort(A + 1, A + N + 1, cmp);

    for(int i = 1; i <= N; ++i)
    {
        int M = (int)strlen(A[i].S + 1);
        int Last = 0;

        for(int j = 1; j <= K; ++j)
            if(St[j] == A[i].S[j])
                ++Last;
            else
                break;

        while(K != Last)
        {
            Sol.push_back('-');

            --K;
        }

        for(int j = Last + 1; j <= M; ++j)
        {
            St[++K] = A[i].S[j];

            Sol.push_back(St[K]);
        }

        Sol.push_back('P');
    }

    return;
}

static inline void Write ()
{
    cout << (int)Sol.size() << '\n';

    for(auto it : Sol)
        cout << it << '\n';

    return;
}

int main()
{
    Load();

    Solve();

    Write();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 456 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 420 KB Output is correct
2 Correct 6 ms 512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 14 ms 1024 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1280 KB Output is correct
2 Correct 12 ms 896 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2148 KB Output is correct
2 Correct 55 ms 3564 KB Output is correct
3 Correct 38 ms 2548 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2036 KB Output is correct
2 Correct 66 ms 4208 KB Output is correct
3 Correct 45 ms 2804 KB Output is correct
4 Correct 62 ms 4080 KB Output is correct