oj.uz

Submission #533536

# Submission time Handle Problem Language Result Execution time Memory
533536 2022-03-06T09:05:02 Z speedyArda Type Printer (IOI08_printer) C++17
100 / 100
 184 ms 56304 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 288 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 2 ms 844 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1304 KB Output is correct
2 Correct 4 ms 2148 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3808 KB Output is correct
2 Correct 21 ms 7356 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7680 KB Output is correct
2 Correct 16 ms 2252 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 28268 KB Output is correct
2 Correct 152 ms 56124 KB Output is correct
3 Correct 84 ms 28460 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 14844 KB Output is correct
2 Correct 184 ms 56256 KB Output is correct
3 Correct 89 ms 28584 KB Output is correct
4 Correct 162 ms 56304 KB Output is correct