Submission #235544

#	Time	Username	Problem	Language	Result	Execution time	Memory
235544		nicolaalexandra	Type Printer (IOI08_printer)	C++14	10 / 100	171 ms	80372 KiB

printer

#include <bits/stdc++.h>
//#define DIM 25010 nu inteleg de ce uneori iau eroare de la define
//#define MOD 666013
using namespace std;
const int MOD = 66617;
const int DIM = 25010;

char v[DIM][22],s[22];
vector <char> sol;
set <int> Hash[22][MOD+1];
int f[DIM];
pair <int,int> lg[DIM];
int n,i,j,cod,cnt,k;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    /// probabil nu e bn dar csf

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i]+1;
        lg[i] = make_pair(strlen (v[i]+1),i);
    }

    sort (lg+1,lg+n+1);

    for (i=1;i<=n;i++){
        int idx = lg[i].second, cod = 0;
        for (j=1;j<=lg[i].first;j++){
            cod = (1LL * cod * 27 + v[idx][j] - '0') % MOD;
            Hash[j][cod].insert(idx);
        }
    }

    for (i=1;i<=n;i++){
        int poz = lg[i].second;
        if (f[poz]) /// l am afisat deja
            continue;

        /// adaug toate literele din cuvantul asta si apoi il afisez
        k = 0, cod = 0;
        for (j=1;j<=lg[i].first;j++){
            sol.push_back(v[poz][j]);
            s[++k] = v[poz][j];

            cod = (1LL * cod * 27 + v[poz][j] - '0') % MOD;
            Hash[j][cod].erase (poz);
        }

        sol.push_back('P');
        f[poz] = 1;
        cnt++;

        if (cnt == n)
            break;

        while (k){

            k--;
            sol.push_back('-');
            int cod = 0;
            for (j=1;j<=k;j++)
                cod = (1LL * cod * 27 + s[j] - '0') % MOD;

            if (Hash[k][cod].size()){ /// exista un cuvant cu prefixul asta
                int idx = *Hash[k][cod].begin();

                /// adaug literele care mai trb
                for (j=k+1;v[idx][j] != NULL;j++){
                    s[++k] = v[idx][j];
                    sol.push_back(v[idx][j]);
                }

                sol.push_back('P');
                f[idx] = 1;
                cnt++;

                if (cnt == n)
                    break;

                cod = 0;
                for (j=1;v[idx][j] != NULL;j++){
                    cod = (1LL * cod * 27 + v[idx][j] - '0') % MOD;
                    Hash[j][cod].erase(idx);
                }}}

        if (cnt == n)
            break;

    }

    cout<<sol.size()<<"\n";
    for (auto it : sol)
        cout<<it<<"\n";


    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:24:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>v[i]+1;
              ~~~~^~
printer.cpp:72:41: warning: NULL used in arithmetic [-Wpointer-arith]
                 for (j=k+1;v[idx][j] != NULL;j++){
                                         ^~~~
printer.cpp:85:39: warning: NULL used in arithmetic [-Wpointer-arith]
                 for (j=1;v[idx][j] != NULL;j++){
                                       ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10