Submission #1031740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031740		doducanh	Type Printer (IOI08_printer)	C++14	100 / 100	73 ms	56848 KiB

printer

#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 (stderr)

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 / 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