oj.uz

Submission #235543

# Submission time Handle Problem Language Result Execution time Memory
235543 2020-05-28T13:25:02 Z nicolaalexandra Type Printer (IOI08_printer) C++14
0 / 100
 141 ms 262148 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 = 666013;
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 128 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 128 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 139 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -