Submission #859820

# Submission time Handle Problem Language Result Execution time Memory
859820 2023-10-10T18:11:41 Z blackslex Type Printer (IOI08_printer) C++17
80 / 100
1000 ms 111716 KB
#include<bits/stdc++.h>

using namespace std;
using tp = tuple<int, int, char>;

const int N = 3e4 + 5, C = 26;
int n, idx;
string s;
vector<char> ans;

struct node {
    int nxt[C], lv[C];
    bool end;
    node() {for (int i = 0; i < C; i++) nxt[i] = lv[i] = 0; end = 0;}
};

map<int, node> t;

void add (string s) {
    int cur = 0;
    for (auto &e: s) e -= 'a';
    for (auto &e: s) {
        if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
    }
    t[cur].end = 1;
}

void dfs (int cur) {
    if (t[cur].end) ans.emplace_back('P');
    vector<tp> v;
    for (int i = 0; i < C; i++) if (t[cur].nxt[i]) v.emplace_back(t[cur].lv[i], t[cur].nxt[i], i + 'a');
    sort(v.begin(), v.end());
    for (auto &[lv, nxt, c]: v) ans.emplace_back(c), dfs(nxt), ans.emplace_back('-');
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) cin >> s, add(s);
    dfs(0);
    while (ans.back() == '-') ans.pop_back();
    printf("%d\n", ans.size());
    for (auto &e: ans) printf("%c\n", e);
}

Compilation message

printer.cpp: In function 'void add(std::string)':
printer.cpp:23:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                         ^
printer.cpp:23:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                        ^
printer.cpp:23:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |         ^~
printer.cpp:23:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                    ^
printer.cpp:23:62: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                              ^
printer.cpp:23:81: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                                                 ^
printer.cpp:23:119: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                                                                                       ^
printer.cpp: In function 'int main()':
printer.cpp:41:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wformat=]
   41 |     printf("%d\n", ans.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<char>::size_type {aka long unsigned int}
      |             %ld
printer.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 7 ms 1372 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 11 ms 2140 KB Output is correct
2 Correct 15 ms 2652 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 53 ms 6736 KB Output is correct
2 Correct 146 ms 14108 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 174 ms 16600 KB Output is correct
2 Correct 67 ms 3620 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 471 ms 41340 KB Output is correct
2 Execution timed out 1018 ms 93740 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 384 ms 32412 KB Output is correct
2 Execution timed out 1065 ms 111716 KB Time limit exceeded
3 Halted 0 ms 0 KB -