oj.uz

Submission #1031740

# Submission time Handle Problem Language Result Execution time Memory
1031740 2024-07-23T06:17:38 Z doducanh Type Printer (IOI08_printer) C++14
100 / 100
 73 ms 56848 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn=2e6+7;
string res="";string maxs="";
struct trie
{
    int cnt=0;
    int t[maxn][30];
    int stop[maxn];
    void add(string &s){
        int curr=0;
        for(char c:s){
            if(t[curr][c-'a'+1]==0)t[curr][c-'a'+1]=++cnt;
            curr=t[curr][c-'a'+1];
        }
        stop[curr]++;
    }
    void dfs(int curr,bool type,int depth=-1){
        while(stop[curr]--){
            res.push_back('P');
        }
        if(depth==maxs.size()-1)return;

        if(type==0){
            for(int i=1; i<=26; i++)
            {
                if(t[curr][i]) {
                    res.push_back((char)i-1+'a');
                    dfs(t[curr][i],0,depth+1);
                    res.push_back('-');
                }
            }
        }
        else{
            for(int i=1; i<=26; i++)
            {
                if(i==(maxs[depth+1]-'a'+1))continue;
                if(t[curr][i]) {
                    res.push_back((char)i-1+'a');
                    dfs(t[curr][i],0,depth+1);
                    res.push_back('-');
                }
            }
            if(depth+1<maxs.size())res.push_back(maxs[depth+1]);
            if(t[curr][maxs[depth+1]-'a'+1])dfs(t[curr][maxs[depth+1]-'a'+1],1,depth+1);
        }

    }
};
trie t;
int n;

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(s.size()>maxs.size())maxs=s;
        t.add(s);
    }
    t.dfs(0,1);
    cout<<res.size()<<"\n";
    for(char c:res)cout<<c<<"\n";
    return 0;
}

Compilation message

printer.cpp: In member function 'void trie::dfs(int, bool, int)':
printer.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(depth==maxs.size()-1)return;
      |            ~~~~~^~~~~~~~~~~~~~~
printer.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if(depth+1<maxs.size())res.push_back(maxs[depth+1]);
      |                ~~~~~~~^~~~~~~~~~~~
printer.cpp: At global scope:
printer.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main()
      | ^~~~

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

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

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

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3672 KB Output is correct
2 Correct 10 ms 7264 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8700 KB Output is correct
2 Correct 5 ms 2152 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21000 KB Output is correct
2 Correct 59 ms 47900 KB Output is correct
3 Correct 33 ms 24816 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16688 KB Output is correct
2 Correct 73 ms 56848 KB Output is correct
3 Correct 39 ms 28144 KB Output is correct
4 Correct 61 ms 53520 KB Output is correct