oj.uz

Submission #1021675

# Submission time Handle Problem Language Result Execution time Memory
1021675 2024-07-13T02:21:05 Z TrendBattles Type Printer (IOI08_printer) C++14
100 / 100
 103 ms 56520 KB 
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

#define INFILE "printer.inp"
#define OUTFILE "printer.out"

const int MAX_AL = 26;
struct Node {
    int exist = 0;
    int child[MAX_AL];

    Node() {
        memset(child, -1, sizeof child);
    }
};
vector <Node> trie(1);

void add(const string& s) {
    int now = 0;
    for (char x : s) {
        int nxt = trie[now].child[x - 'a'];
        if (nxt == -1) {
            nxt = trie.size();
            trie[now].child[x - 'a'] = nxt;
            trie.emplace_back();
        }
        now = nxt;
    }

    trie[now].exist += 1;
}

string all_operations, longest_string;
void DFS(int u, int tight, int depth) {
    for (int i = 1; i <= trie[u].exist; ++i) {
        all_operations.push_back('P');
    }

    for (int i = 0; i < MAX_AL; ++i) {
        int v = trie[u].child[i];
        if (v == -1) continue;
        
        if (tight and depth < (int) longest_string.size() and longest_string[depth] - 'a' == i) continue;

        all_operations.push_back(i + 'a');
        DFS(v, 0, depth + 1);
        all_operations.push_back('-');
    }
    
    if (depth == (int) longest_string.size() or not tight) return;

    int v = trie[u].child[longest_string[depth] - 'a'];
    all_operations.push_back(longest_string[depth]);
    DFS(v, 1, depth + 1);
    all_operations.push_back('-');
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    int N; cin >> N;

    for (int i = 0; i < N; ++i) {
        string T; cin >> T;
        if (longest_string.empty()) longest_string = T;
        add(T);

        if ((int) longest_string.size() < (int) T.size()) longest_string = T;
    }

    DFS(0, 1, 0);

    while (all_operations.back() == '-') all_operations.pop_back();
    cout << (int) all_operations.size() << '\n';
    for (char x : all_operations) cout << x << '\n';
    return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
printer.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1324 KB Output is correct
2 Correct 3 ms 2164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3860 KB Output is correct
2 Correct 13 ms 7504 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7884 KB Output is correct
2 Correct 7 ms 2420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 28360 KB Output is correct
2 Correct 86 ms 56220 KB Output is correct
3 Correct 45 ms 28604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15032 KB Output is correct
2 Correct 103 ms 56448 KB Output is correct
3 Correct 48 ms 28616 KB Output is correct
4 Correct 92 ms 56520 KB Output is correct