oj.uz

Submission #397447

# Submission time Handle Problem Language Result Execution time Memory
397447 2021-05-02T08:51:37 Z AugustinasJucas Type Printer (IOI08_printer) C++14
100 / 100
 169 ms 56440 KB 
#include <bits/stdc++.h>
using namespace std;
struct node {
    bool val = 0;
    int nei[26];
    node() {
        for (int i = 0; i < 26; i++) {
            nei[i] = -1;
        }
    }
};
const int dydis = 5e5 + 100;
node mas[dydis];
int dbInd = 0;
int newN() {
    node nd;
    mas[dbInd] = nd;
    return dbInd++;
}
vector<int> kur;
int mx = 0;
vector<int> ans;
void add(string a, int ind, int v, int lvl) {
    if (lvl > mx) {
        mx = lvl;
        ans = kur;
    }

    kur.push_back(v);

    if (ind == a.size()) {
        mas[v].val = 1;
        kur.pop_back();
        return;
    }

    int kas = a[ind] - 'a';

    if (mas[v].nei[kas] == -1) {
        mas[v].nei[kas] = newN();
    }

    add(a, ind + 1, mas[v].nei[kas], lvl + 1);
    kur.pop_back();

}
vector<char> ats;
void dfs(int v) {
    if (mas[v].val) {
        ats.push_back('P');
    }

    bool is = 0;
    int nex = -1;
    char kas;

    for (int i = 0; i < ans.size(); i++) if (ans[i] == v) {
            is = 1;
            nex = (i == ans.size() - 1 ? -1 : ans[i + 1]);
        }

    for (int i = 0; i < 26; i++) {
        if (mas[v].nei[i] == -1) {
            continue;
        }

        if (mas[v].nei[i] == nex) {
            kas = (char)(i + 'a');
            continue;
        }

        ats.push_back((char)(i + 'a'));
        dfs(mas[v].nei[i]);
        ats.push_back('-');
    }

    if (nex != -1) {
        ats.push_back(kas);
        dfs(nex);
        ats.push_back('-');
    }
}
#include <bits/stdc++.h>
#include <unistd.h>

using namespace std;

void ___signal_handler___(int s) {
    int ignored __attribute__((unused));

    if (s == SIGSEGV) {
        ignored = write(STDOUT_FILENO, "SEGFAULT\n", 9);
    }
    else if (s == SIGFPE) {
        ignored = write(STDOUT_FILENO, "FPEXCEPTION\n", 12);
    }
    else {
        ignored = write(STDOUT_FILENO, "ABORTCLD\n", 9);
    }

    return _Exit(s);
}

[[noreturn]]void no_answer() {
    int ignored __attribute__((unused)) = write(STDOUT_FILENO, "NOANSWER\n", 9);
    exit(0);
}

int main () {
    std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    signal(SIGSEGV, ___signal_handler___);
    signal(SIGFPE, ___signal_handler___);
    signal(SIGABRT, ___signal_handler___);

    newN();
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string a;
        cin >> a;
        add(a, 0, 0, 0);
    }

    dfs(0);

    while (ats.back() == '-') {
        ats.pop_back();
    }

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

    for (auto x : ats) {
        cout << x << "\n";
    }





    cout << flush;
}

Compilation message

printer.cpp: In function 'void add(std::string, int, int, int)':
printer.cpp:31:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if (ind == a.size()) {
      |         ~~~~^~~~~~~~~~~
printer.cpp: In function 'void dfs(int)':
printer.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < ans.size(); i++) if (ans[i] == v) {
      |                     ~~^~~~~~~~~~~~
printer.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             nex = (i == ans.size() - 1 ? -1 : ans[i + 1]);
      |                    ~~^~~~~~~~~~~~~~~~~
printer.cpp:53:10: warning: variable 'is' set but not used [-Wunused-but-set-variable]
   53 |     bool is = 0;
      |          ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 53104 KB Output is correct
2 Correct 35 ms 53112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 53072 KB Output is correct
2 Correct 36 ms 53052 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 53072 KB Output is correct
2 Correct 40 ms 53112 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 53080 KB Output is correct
2 Correct 37 ms 53060 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 53072 KB Output is correct
2 Correct 37 ms 53148 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 53188 KB Output is correct
2 Correct 41 ms 53160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 53292 KB Output is correct
2 Correct 51 ms 53668 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 53672 KB Output is correct
2 Correct 46 ms 53436 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 54220 KB Output is correct
2 Correct 148 ms 55888 KB Output is correct
3 Correct 105 ms 54876 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 54084 KB Output is correct
2 Correct 169 ms 56440 KB Output is correct
3 Correct 121 ms 55100 KB Output is correct
4 Correct 162 ms 56316 KB Output is correct