Submission #546312

#	Time	Username	Problem	Language	Result	Execution time	Memory
546312		krit3379	Type Printer (IOI08_printer)	C++17	100 / 100	149 ms	94396 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define N 25

struct node{
    int nxt[26],dep[26];
    bool is_end;
}t[1000000];

struct A{
    int nxt,dep;
    char c;
    bool operator<(const A& o)const{
        return dep<o.dep;
    }
};

int sz;
char s[N];
vector<char> ans;

void add(int n){
    int i,now=0;
    for(i=1;i<=n;i++){
        int idx=s[i]-'a';
        if(!t[now].nxt[idx])t[now].nxt[idx]=++sz;
        t[now].dep[idx]=max(t[now].dep[idx],n);
        now=t[now].nxt[idx];
    }
    t[now].is_end=true;
}

void dfs(int now){
    if(t[now].is_end)ans.push_back('P');
    vector<A> temp;
    for(int i=0;i<26;i++){
        if(t[now].nxt[i]){
            temp.push_back({t[now].nxt[i],t[now].dep[i],'a'+i});
        }
    }
    sort(temp.begin(),temp.end());
    for(auto [nxt,dep,c]:temp){
        ans.push_back(c);
        dfs(nxt);
        ans.push_back('-');
    }
}

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf(" %s",s+1);
        add(strlen(s+1));
    }
    dfs(0);
    while(ans.back()=='-')ans.pop_back();
    printf("%d\n",ans.size());
    for(auto x:ans)printf("%c\n",x);
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void dfs(int)':
printer.cpp:38:60: warning: narrowing conversion of '(97 + i)' from 'int' to 'char' [-Wnarrowing]
   38 |             temp.push_back({t[now].nxt[i],t[now].dep[i],'a'+i});
      |                                                         ~~~^~
printer.cpp: In function 'int main()':
printer.cpp:58:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wformat=]
   58 |     printf("%d\n",ans.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<char>::size_type {aka long unsigned int}
      |             %ld
printer.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
printer.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf(" %s",s+1);
      |         ~~~~~^~~~~~~~~~~

• 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