Submission #122190

#	Time	Username	Problem	Language	Result	Execution time	Memory
122190		thebes	Type Printer (IOI08_printer)	C++14	100 / 100	170 ms	51692 KiB

printer

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

const int MN = 3e4+4, MM = 5e5+5;
string s;
vector<char> mv;
int n, i, t[MM][26], lol[MM], len[MM], nxt, p;
int solve(int p){
    int mx=0, nx=-1, r;
    for(int i=0;i<26;i++){
        if(!t[p][i]) continue;
        if(len[t[p][i]]>mx){
            mx = len[t[p][i]];
            nx = i;
        }
    }
    if(lol[p]) mv.push_back('P');
    if(nx==-1) return 0;
    for(int i=0;i<26;i++){
        if(!t[p][i]||i==nx) continue;
        mv.push_back(i+'a');
        r = solve(t[p][i])+1;
        while(r--) mv.push_back('-');
    }
    mv.push_back('a'+nx);
    r=solve(t[p][nx])+1;
    return r;
}
int main(){
    for(scanf("%d",&n),i=1;i<=n;i++){
        cin >> s; p = 0;
        for(auto c : s){
            if(!t[p][c-'a']) t[p][c-'a']=++nxt;
            p = t[p][c-'a'];
            len[p] = max(len[p], (int)s.size());
        }
        lol[p] = 1;
    }
    solve(0);
    printf("%d\n",mv.size());
    for(auto v : mv) printf("%c\n",v);
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:40:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",mv.size());
                   ~~~~~~~~~^
printer.cpp:30:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d",&n),i=1;i<=n;i++){
         ~~~~~~~~~~~~~~^~~~

• 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