Submission #935218

#	Time	Username	Problem	Language	Result	Execution time	Memory
935218		asdasdqwer	Type Printer (IOI08_printer)	C++14	20 / 100	1096 ms	38096 KiB

printer

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char l;
    map<char,int> child;
};

vector<Node> trie(500001);
int last = 1;

void insWord(string &s) {
    int idx = 0;
    for (auto &x:s) {
        if (trie[idx].child.find(x) == trie[idx].child.end()) {
            trie[idx].child[x] = last;
            trie[last].l = x;
            last++;
        }
        idx = trie[idx].child[x];
    }
}

struct Operation {
    char chr;
    bool isPrint = false;
    bool isBack = false;
};

vector<Operation> out;

void traversal(int index) {
    bool foundOne = false;
    for (auto [chr, idx]:trie[index].child) {
        Operation op;op.chr = chr;
        out.push_back(op);
        traversal(idx);
        op.isBack = true;
        out.push_back(op);
        foundOne = true;
    }

    if (!foundOne) {
        Operation op;op.isPrint=true;
        out.push_back(op);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<string> v(n);
    for (auto &x:v)cin>>x;
    trie[0].l = ' ';

    for (auto x:v) {
        insWord(x);
    }

    // string s = "";
    // for (auto &x:v) {
    //     if (x.size() > s.size()) {
    //         s = x;
    //     }
    // }

    vector<Operation> vv;

    for (auto &s:v) {
        int index = 0;

        for (auto &x:s) {
            int nxt;
            for (auto [chr, idx] : trie[index].child) {
                if (chr != x) {
                    Operation op;op.chr=chr;
                    out.push_back(op);
                    traversal(idx);
                    op.isBack = true;
                    out.push_back(op);
                }

                else {
                    nxt = idx;
                }
            }

            Operation op;op.chr=x;
            out.push_back(op);
            index = nxt;
        }

        if (vv.size() == 0 || out.size() < vv.size()) {
            vv = out;
        }

        out.clear();
    }

    out = vv;

    Operation op;op.isPrint=true;
    out.push_back(op);

    cout<<out.size()<<"\n";
    for (auto &x:out) {
        if (x.isBack) {
            cout<<"-\n";
        }

        else if (x.isPrint) {
            cout<<"P\n";
        }

        else {
            cout<<x.chr<<"\n";
        }
    }
}

Compilation message (stderr)

printer.cpp: In function 'void traversal(int)':
printer.cpp:34:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for (auto [chr, idx]:trie[index].child) {
      |               ^
printer.cpp: In function 'int main()':
printer.cpp:76:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |             for (auto [chr, idx] : trie[index].child) {
      |                       ^
printer.cpp:76:46: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             for (auto [chr, idx] : trie[index].child) {
      |                                              ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10