oj.uz

Submission #235576

# Submission time Handle Problem Language Result Execution time Memory
235576 2020-05-28T15:43:24 Z nicolaalexandra Type Printer (IOI08_printer) C++14
100 / 100
 221 ms 100332 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;

pair <int,int> lg[DIM];
int n,i,j,cod,cnt,k;

struct trie{
    int nr,maxi;
    trie *f[26];
    trie(){
        nr = maxi = 0;
        for (int i=0;i<26;i++)
            f[i] = 0;
    }
};
trie *rad = new trie;

void add_trie (trie *&rad, char *s){
    if (*s != 0){
        if (rad->f[*s - 'a'] == 0)
            rad->f[*s - 'a'] = new trie;

        add_trie (rad->f[*s - 'a'],s+1);

        rad->maxi = max (rad->maxi, rad->f[*s - 'a']->maxi + 1);
    } else rad->nr++;
}
void dfs (trie *&rad){

    while (rad->nr){
        sol.push_back('P');
        rad->nr--;
        cnt++;
    }

    if (cnt == n)
        return;

    int maxi = 0;
    for (int i=0;i<26;i++)
        if (rad->f[i] && rad->f[i]->maxi > maxi)
            maxi = rad->f[i]->maxi;

    for (int i=0;i<26;i++)
        if (rad->f[i] && rad->f[i]->maxi != maxi){
            sol.push_back('a' + i);
            dfs (rad->f[i]);
        }

    for (int i=0;i<26;i++)
        if (rad->f[i] && rad->f[i]->maxi == maxi){
            sol.push_back('a' + i);
            dfs (rad->f[i]);
        }

    if (cnt != n)
        sol.push_back('-');

}
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];
        lg[i] = make_pair(strlen (v[i]),i);
    }

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

    for (i=1;i<=n;i++){
        int idx = lg[i].second;
        add_trie (rad,v[idx]);
    }

    dfs (rad);

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


    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 384 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 4 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 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 4 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1920 KB Output is correct
2 Correct 9 ms 2304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6144 KB Output is correct
2 Correct 33 ms 12800 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15104 KB Output is correct
2 Correct 24 ms 3832 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 37236 KB Output is correct
2 Correct 191 ms 84516 KB Output is correct
3 Correct 115 ms 43888 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 29424 KB Output is correct
2 Correct 221 ms 100332 KB Output is correct
3 Correct 125 ms 49776 KB Output is correct
4 Correct 201 ms 94828 KB Output is correct