Submission #533536

#	Time	Username	Problem	Language	Result	Execution time	Memory
533536		speedyArda	Type Printer (IOI08_printer)	C++17	100 / 100	184 ms	56304 KiB

printer

#include "bits/stdc++.h"
#define pb push_back
#define vll vector<long long>
#define vb vector<bool>
#define vi vector<int>
#define vs vector<string>
#define vpii vector< pair<int, int> >
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vvi vector< vector<int> > 
#define ld long double
#define mp make_pair
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;

int next_pref = 0, moves = 0;
string res = "", forbidden = "";
struct trie_node 
{
    int next_node[26];
    bool end_word = false;

    trie_node() 
    {
        fill(next_node, next_node + 26, -1);
        end_word = false;

    };
};

vector<trie_node> trie;

void add(string inp) 
{
    int v = 0;
    for(int i = 0; i < inp.size(); i++) 
    {
        int ch = inp[i] - 'a';
        if(trie[v].next_node[ch] == -1)
        {
            trie[v].next_node[ch] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next_node[ch];
    }
    trie[v].end_word = true;
}
string curr_forbidden = "";
 
void dfs(int v, string curr_str) 
{

    int forbidden_pref  = -1;
    if(trie[v].end_word)
    {
        moves++;
        res += "P";
    }
    for(int i = 0; i < 26; i++)
    {
        if(trie[v].next_node[i] == -1)
            continue;
        curr_str += ('a' + i);

        if(next_pref < forbidden.size() && curr_forbidden + forbidden[next_pref] == curr_str) {
            forbidden_pref = i;

        }

        else
        {
            res += ('a' + i);
            moves++;

            dfs(trie[v].next_node[i], curr_str);

            moves++;
            res += "-";

        }
        curr_str.pop_back();
    }
    if(next_pref == forbidden.size() || forbidden_pref == -1)
        return;
    curr_forbidden += forbidden[next_pref];
    res += forbidden[next_pref];
    next_pref++;
 
    moves++;
    dfs(trie[v].next_node[forbidden_pref], curr_forbidden);
}   

int main() 
{
    trie_node root = trie_node();
    trie.pb(root);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        string temp;
        cin >> temp;
        if(temp.size() >= forbidden.size())
            forbidden = temp;
        add(temp);
    }

    dfs(0, "");
    cout << moves << "\n";

    for(char e : res)
    {
        cout << e << "\n";
    }
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::string)':
printer.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < inp.size(); i++)
      |                    ~~^~~~~~~~~~~~
printer.cpp: In function 'void dfs(int, std::string)':
printer.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if(next_pref < forbidden.size() && curr_forbidden + forbidden[next_pref] == curr_str) {
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
printer.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     if(next_pref == forbidden.size() || forbidden_pref == -1)
      |        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

• 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