제출 #235576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235576		nicolaalexandra	Type Printer (IOI08_printer)	C++14	100 / 100	221 ms	100332 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;

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