oj.uz

Submission #1087000

# Submission time Handle Problem Language Result Execution time Memory
1087000 2024-09-12T03:04:32 Z Drifter24 Type Printer (IOI08_printer) C++14
100 / 100
 80 ms 51664 KB 
#include <bits/stdc++.h>
using namespace std;
#define print(arr) for(auto& x:arr)cout<<x<<" ";cout<<"\n"
#define watch(x) cout<<#x<<"="<<x<<"\n"
#define all(x) x.begin(), x.end()
#define sz(x) ((int) x.size())
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const string ABC = "abcdefghijklmnopqrstuvwxyz";

const int maxn = 2e6+5;
const int alpha = 26; 
const int bits = 30;

int to[maxn][alpha],cnt[maxn],maxi[maxn],act;
int conv(char ch){return ((ch>='a' && ch<='z')?ch-'a':ch-'A'+26);} 
string bin(int num, int size){return bitset<bits>(num).to_string().substr(bits-size);}

void init(){ 
    for(int i=0;i<=act;++i){
        cnt[i]=0;
        maxi[i]=0;
        memset(to[i], 0, sizeof(to[i]));
    }
    act=0;
}

void add(const string &s){
    int u=0;
    int n=sz(s);
    for(char ch:s){
        int c=conv(ch);
        if(!to[u][c])to[u][c]=++act;
        u=to[u][c];
        maxi[u]=max(maxi[u], n);
    }
    cnt[u]++;
}

vector<char> ans;
void dfs(int u=0){
    if(cnt[u])ans.push_back('P');
    vii nodes;
    for(int i=0;i<alpha;++i){
        if(!to[u][i])continue;
        nodes.push_back({maxi[to[u][i]], i});
    }
    sort(all(nodes));
    for(auto x:nodes){
        ans.push_back(ABC[x.second]);
        dfs(to[u][x.second]);
        ans.push_back('-');
    }
}

int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;
    init();
    string s;
    while(n--){
        cin>>s;
        add(s);
    }
    dfs();
    while(ans.back()=='-')ans.pop_back();
    cout<<sz(ans)<<"\n";
    for(auto c:ans)cout<<c<<"\n";
    return 0;
}

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 1 ms 460 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 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 7 ms 3420 KB Output is correct
2 Correct 10 ms 6816 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7904 KB Output is correct
2 Correct 5 ms 2140 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 19152 KB Output is correct
2 Correct 72 ms 43560 KB Output is correct
3 Correct 42 ms 22740 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15060 KB Output is correct
2 Correct 80 ms 51664 KB Output is correct
3 Correct 41 ms 25816 KB Output is correct
4 Correct 71 ms 48844 KB Output is correct