Submission #921201

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921201	2024-02-03T13:39:16 Z	Alihan_8	Type Printer (IOI08_printer)	C++17	40 / 100	116 ms	113028 KB

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] ){
            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);
            }
        }
        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

printer.cpp: In member function 'void Trie::dfs(long long int, long long int)':
printer.cpp:64: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]
   64 |         if ( d == t.size() ){
      |              ~~^~~~~~~~~~~

Subtask #1
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Incorrect	344 KB	printed invalid word
3	Halted	0 KB	-

Subtask #2
10.0 / 10.0

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

Subtask #3
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 #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Incorrect	1 ms	1348 KB	printed invalid word
3	Halted	0 ms	0 KB	-

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	8408 KB	Output is correct
2	Incorrect	14 ms	15056 KB	printed invalid word
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	16080 KB	Output is correct
2	Incorrect	7 ms	5980 KB	printed invalid word
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	50 ms	57784 KB	printed invalid word
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	30416 KB	Output is correct
2	Incorrect	116 ms	113028 KB	printed invalid word
3	Halted	0 ms	0 KB	-