Submission #921206

#	Time	Username	Problem	Language	Result	Execution time	Memory
921206		Alihan_8	Type Printer (IOI08_printer)	C++17	100 / 100	119 ms	113256 KiB

printer

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

vector <char> op;

string t;

struct Trie{
    struct Info{
        int a[26];
        Info(int x = -1){
            memset(a, x, sizeof(a));
        }
    };

    vector <Info> T;
    vector <int> us;
    Trie() : T({Info()}), us({0}) {}

    void ins(string s){
        int rt = 0;
        for ( auto &i: s ){
            int x = i - 'a';
            if ( T[rt].a[x] == -1 ){
                T[rt].a[x] = (int)T.size();
                T.pb(Info());
                us.pb(0);
            } rt = T[rt].a[x];
        }
        us[rt] = true;
    }

    void dfs(int rt, int d){
        if ( us[rt] ){
            us[rt] = false;
            op.pb('P');
        }
        if ( d == t.size() ){
            return;
        }
        int x = t[d] - 'a';
        for ( int i = 0; i < 26; i++ ){
            if ( i != x && T[rt].a[i] != -1 ){
                op.pb(i + 'a');
                dfs(T[rt].a[i], d + 1);
                op.pb('-');
            }
        }
        if ( T[rt].a[x] != -1 ){
            op.pb(x + 'a');
            dfs(T[rt].a[x], d + 1);
            op.pb('-');
        }
    }
} tr;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <string> s(n);
    for ( auto &x: s ){
        cin >> x;
        if ( x.size() > t.size() ){
            t = x;
        } tr.ins(x);
    }
    tr.dfs(0, 0);
    while ( op.back() == '-' ){
        op.pop_back();
    }
    cout << op.size() << ln;
    for ( auto &x: op ){
        cout << x << ln;
    }

//    cout << '\n';
}

Compilation message (stderr)

printer.cpp: In member function 'void Trie::dfs(long long int, long long int)':
printer.cpp:65:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if ( d == t.size() ){
      |              ~~^~~~~~~~~~~

• 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