Submission #1021675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021675		TrendBattles	Type Printer (IOI08_printer)	C++14	100 / 100	103 ms	56520 KiB

printer

#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 (stderr)

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 / 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