oj.uz

Submission #53691

# Submission time Handle Problem Language Result Execution time Memory
53691 2018-07-01T04:49:59 Z 노영훈(#1436) Type Printer (IOI08_printer) C++11
30 / 100
 126 ms 47652 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;

int n;
struct node {
    bool end;
    char now;
    int nxt[30]; // 'a' ~ 'z'
} trie[MX]; // root : 1
int bck=1;

void put(char S[]){
    int v=1;
    for(int i=1; S[i]!=0; i++){
        node &nd=trie[v];
        int &nxt=nd.nxt[S[i]-'a'];
        if(nxt==0){
            nxt=++bck;
        }
        v=nxt;
        trie[v].now=S[i];
    }
    trie[v].end=true;
}

void debug(int v=1){
    node &nd=trie[v];
    for(int i=0; i<='z'-'a'; i++)
        if(nd.nxt[i]!=0)    
            cout<<char(i+'a')<<' ', debug(nd.nxt[i]);
    cout<<"OUT\n";
}

void solve(int v, deque<char>& ans){
    node &nd=trie[v];
    ans.push_back(nd.now);
    if(nd.end){
        ans.push_back('P');
    }
    for(int i=0; i<='z'-'a'; i++)
        if(nd.nxt[i]!=0){
            solve(nd.nxt[i], ans);
        }
    ans.push_back('-');
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    char S[30];
    for(int i=1; i<=n; i++){
        cin>>(S+1);
        put(S);
    }
    deque<char> R[30];
    for(int i=0; i<='z'-'a'; i++){
        int v=trie[1].nxt[i];
        if(v==0) continue;
        solve(v, R[i]);
    }
    int last=-1, mx=-1, sum=0;
    for(int i=0; i<='z'-'a'; i++){
        int now=0;
        for(int j=(int)R[i].size()-1; j>=0; j--){
            if(R[i][j]!='-') break;
            now++;
        }
        if(mx<now) last=i, mx=now;
    }
    while(!R[last].empty() && R[last].back()=='-') R[last].pop_back();
    for(int i=0; i<='z'-'a'; i++){
        sum+=R[i].size();
    }
    cout<<sum<<'\n';
    for(int i=0; i<='z'-'a'; i++){
        if(i==last) continue;
        for(char c:R[i]) cout<<c<<'\n';
    }
    for(char c:R[last]) cout<<c<<'\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 516 KB Output is correct
2 Incorrect 2 ms 596 KB Output isn't correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3772 KB Output is correct
2 Incorrect 29 ms 7416 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 8696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20976 KB Output is correct
2 Correct 126 ms 47652 KB Output is correct
3 Incorrect 66 ms 47652 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 47652 KB Output isn't correct
2 Halted 0 ms 0 KB -