Submission #229324

#	Time	Username	Problem	Language	Result	Execution time	Memory
229324		andreiomd	Type Printer (IOI08_printer)	C++11	100 / 100	66 ms	4208 KiB

printer

#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 / 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