oj.uz

Submission #929209

# Submission time Handle Problem Language Result Execution time Memory
929209 2024-02-17T23:28:41 Z AlphaMale06 Type Printer (IOI08_printer) C++17
100 / 100
 86 ms 59584 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

vector<char> ans;

string mxlenstr;

struct node{
    int v, cnt;
    int p[26];
};

vector<node> trie;

node nw(){
    node ret;
    ret.v=trie.size();
    ret.cnt=0;
    for(int i=0; i<26; i++)ret.p[i]=-1;
    return ret;
}

void add(string s){
    int v=0;
    for(char c : s){
        if(trie[v].p[c-'a']==-1){
            trie[v].p[c-'a']=trie.size();
            trie.pb({nw()});
        }
        v=trie[v].p[c-'a'];
    }
    trie[v].cnt++;
}

void dfs(int v, int dep){
    if(v){
        for(int i=0; i<trie[v].cnt; i++)ans.pb('P');
    }
    int avoid;
    if(dep<mxlenstr.size())avoid = mxlenstr[dep]-'a';
    else{
        ans.pb('-');
        return;
    }
    for(int i=0; i< avoid; i++){
        if(trie[v].p[i]!=-1){
            ans.pb(i+'a');
            dfs(trie[v].p[i], dep+1);
        }
    }
    for(int i=25; i>=avoid; i--){
        if(trie[v].p[i]!=-1){
            ans.pb(i+'a');
            dfs(trie[v].p[i], dep+1);
        }
    }
    ans.pb('-');
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    trie.pb({nw()});
    int mxlen=0;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        if(s.size()>mxlen){
            mxlen=s.size();
            mxlenstr=s;
        }
        add(s);
    }
    dfs(0, 0);
    while(ans.back()=='-')ans.pop_back();
    cout << ans.size() << '\n';
    for(char c : ans)cout << c << '\n';
}

Compilation message

printer.cpp: In function 'void dfs(int, int)':
printer.cpp:43:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     if(dep<mxlenstr.size())avoid = mxlenstr[dep]-'a';
      |        ~~~^~~~~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:74:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         if(s.size()>mxlen){
      |            ~~~~~~~~^~~~~~

Subtask #1
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 #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 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 1020 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4556 KB Output is correct
2 Correct 14 ms 9164 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8772 KB Output is correct
2 Correct 6 ms 2388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 31424 KB Output is correct
2 Correct 74 ms 58808 KB Output is correct
3 Correct 41 ms 30476 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16328 KB Output is correct
2 Correct 86 ms 59584 KB Output is correct
3 Correct 45 ms 30660 KB Output is correct
4 Correct 77 ms 58792 KB Output is correct