oj.uz

Submission #235544

# Submission time Handle Problem Language Result Execution time Memory
235544 2020-05-28T13:30:43 Z nicolaalexandra Type Printer (IOI08_printer) C++14
10 / 100
 171 ms 80372 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 69120 KB Output is correct
2 Correct 46 ms 69112 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 69112 KB Output is correct
2 Incorrect 44 ms 69112 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 69240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 69216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 69132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 69624 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 70936 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 73960 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 80372 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 79740 KB printed invalid word
2 Halted 0 ms 0 KB -