Submission #1184641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184641		amm_oux	Type Printer (IOI08_printer)	C++20	100 / 100	129 ms	105852 KiB

printer

#include <bits/stdc++.h>

using namespace std ;
#ifdef LOCAL
#include "/Library/debug/debug.h"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define MAX                 2e9
#define MIN                 -2e9
#define PI                  acos(-1.0)
#define mid(s, e)           ((s) + ((e) - (s)) / 2)
#define clz(n)              __builtin_clzll(n)
#define nbOfBits(n)         __builtin_popcountll(n)
#define all(x)              (x).begin(), (x).end()
#define endl                '\n'
#define pb                  push_back
#define sz(a)               static_cast<int>((a).size())
#define double              long double
#define fi                  first
#define fill(n,arr) = for(int i=1;i<=n;i++){ll x;cin>>x;arr.pb(x);}
#define se                  second
#define getunique(v)        {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define getlower(s)         transform(s.begin(), s.end(), s.begin(), ::tolower)
#define getupper(s)         transform(s.begin(), s.end(), s.begin(), ::toupper)
#define sort(s)             sort(s.begin(), s.end())
#define reverse(s)          reverse(s.begin(), s.end())
#define getmax(ans)         *(all(ans));
#define getmin(ans)         *min_element(all(ans));

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpdd = vector<pdd>;
using si = set<int>;
using ssi = set<si>;
/*
struct trie {

    char ch ;
    bool flag = false ;
    trie* nexts[26] ;
};



trie* CreateNode (char letter){
trie * node = new trie ;
node->ch = letter ;
for (ll i = 0 ; i<26 ; i++ ) node->nexts[i] = NULL ;
return node ;
}

trie* root = CreateNode('0') ;

void InsertWord (string word){

    trie *Node = root ;

    for (ll i = 0 ; i<word.size() ; i++){
            if (Node->nexts[word[i]-'a'] == NULL){Node->nexts[word[i]-'a']=CreateNode(word[i]) ; }
            Node = Node->nexts[word[i]-'a'] ;
    }
    Node->flag = true ;
}

bool searchWord (string word){

    trie *Node = root ;

    for (ll i = 0 ; i<word.size() ; i++){
            if (Node->nexts[word[i]-'a'] == NULL) return 0 ;
            else
            Node = Node->nexts[word[i]-'a'] ;
    }
    if (Node->flag) return 1 ;
    else return 0 ;
}

void display (trie * ROOT , string saved){
    trie *node ;
    string s = saved ;

    for (ll i = 0 ; i < 26 ; i++){
        if (ROOT->nexts[i] != NULL) {node = ROOT->nexts[i] ; s +=node->ch ; if (node->flag) cout << s << endl ; display (node , s ) ; s = saved ;}
    }
}



void SOlve(){
    cout << "How many words to insert ? " << endl ;
    ll n ; cin >> n ; string word ;
    for (ll i = 0 ; i < n ; i++){
        cin >> word ;
         InsertWord (word) ;
    }

    display(root , "") ;

    cout << "how many words are u looking for ? " << endl ;
    cin >> n ;
    for (ll i = 0 ; i < n ; i++){
        cin >> word ;
         if (searchWord (word)) cout << " YES .. It is there !! " << endl ;
         else cout << " NO .. It isn't there !! " << endl ;

    }
   }

*/

string ans = "" ;
bool prefs [20] ;

struct trie {
    char l ;
    trie * child [26] ;
    ll wordend = 0 ;
};

trie* createNode (char ch){
    trie * node = new trie ;
    node->l = ch ;
    for (ll i = 0 ; i< 26 ; i++){
        node->child[i] = NULL ;
    }
    return node ;
}

trie * root = createNode ('0') ;

void insertWord (string word){
    trie * node = root ;
    for (ll i = 0 ; i < word.size() ; i++){
        if (node->child [word[i]-'a'] == NULL){node->child [word[i]-'a'] = createNode(word[i]) ; }
         node = node->child [word[i]-'a'] ;
    }
    node->wordend ++ ;
}


void carefulDfsOnTrie (trie * prevnode , char watchout ){
    trie* node ;
    for (ll i = 0 ; i < 26 ; i++){
            node = prevnode->child[i] ;
            if (i == watchout - 'a' ) continue ;
            if (node == NULL) continue ;
            else {
                ans += node->l ;
               for (ll k = 0 ; k < node->wordend ; k++ ) ans += 'P' ;
                carefulDfsOnTrie(node , '1' ) ;
                ans += '-' ;
            }
    }

}


void scanprefs ( string watchout  ){
    for (ll i = 0 ; i < 20 ; i++) prefs[i] = 0 ;
    trie* node = root ;

    for (ll i = 0 ; i < watchout.size() ; i++){
            node = node->child[watchout[i]-'a'] ;
            if (node->wordend) prefs[i] = 1 ;

            }
    }



void solve (){
    ll n ; cin >> n ;
    string s ; ll maxl = 0 ; string deepestw ;

    for ( ll i = 0 ; i < n ; i++){
        cin >> s ;
        if (s.size() > maxl) {maxl = s.size() ; deepestw = s ;}
        insertWord(s);
    }

    trie * nd = root ;

    scanprefs (deepestw) ;

    for ( ll j = 0 ; j < maxl ; j++){
        carefulDfsOnTrie(nd , deepestw[j] ) ;
        ans += deepestw[j] ;
        if (prefs[j]) ans +='P' ;
        nd = nd->child [deepestw[j]-'a'] ;
    }


    cout << ans .size()<< endl;

    for (ll i = 0 ; i < ans .size() ; i++ ){
        cout << ans [i] << endl ;
    }


}

signed main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    ll t;t= 1 ;
    while(t--)
    solve();
}

• 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