oj.uz

Submission #867316

# Submission time Handle Problem Language Result Execution time Memory
867316 2023-10-28T07:23:54 Z Samrev Type Printer (IOI08_printer) C++14
100 / 100
 86 ms 59580 KB 
#include <bits/stdc++.h>
using namespace std;
#define LSOne(x) (x&(-x))
typedef long long int ll;
typedef long double ld;
ll t = 1;
const ll M = 1e9 + 7;
ll mod_add(ll a, ll b){
    return ((a%M) + (b %M))%M;
}
ll mod_minus(ll a , ll b){
    return ((a%M) - (b %M) + M)%M;
}
ll mod_mul(ll a, ll b){
    return ((a%M)*(b%M))%M;
}
ll power(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b % 2 == 1){
            ans = mod_mul(ans , a);
        }
        a = mod_mul(a , a);
        b = b/2;
    }
    return ans;
}
ll mod_inverse(ll a){
    return power(a, M-2);
}

ll mod_divide(ll a, ll b){
    return mod_mul(a , mod_inverse(b));
}



const ll MAX = 1e18;
 
ll lcm(ll a , ll b){
    return (a*b)/__gcd(a,b);
}
const ll N = 1e5 + 10;
const int K = 26;
int n ;
struct Vertex{
    int next[K];
    int cnt = 0;
    int height = 0;

    Vertex(){
        fill(begin(next), end(next), -1);
    }
};
vector<Vertex> trie(1);
void add_string(string &s){
    int v = 0;
    int k = s.size();
    trie[v].height = max(trie[v].height, k);
    for(int i = 0 ;i<s.size();i++){
        int c = s[i] - 'a';
        if(trie[v].next[c] == -1){
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next[c];
        trie[v].height = max(trie[v].height, k - (i + 1));
    }
    trie[v].cnt++;
}
void traverse(int v, vector<char> &out){
    if(trie[v].cnt){
        for(int i = 0;i<trie[v].cnt;i++){
            out.push_back('P');
        }
    }
    int maxih = -1,maxiv = -1;
    for(int i = 0;i<K;i++){
        if(trie[v].next[i] == -1) continue;
        if(trie[trie[v].next[i]].height > maxih){
            maxih = max(maxih, trie[trie[v].next[i]].height);
            maxiv = i;
        }
    }
    if(maxiv != -1){
        for(int i = 0 ; i<K;i++){
            if(trie[v].next[i] == -1 || i == maxiv) continue;
            out.push_back(i + 'a');
            traverse(trie[v].next[i],out);
            out.push_back('-');
        }
        out.push_back(maxiv + 'a');
        traverse(trie[v].next[maxiv],out);
        out.push_back('-');
    }
}
void solve(){
    cin>>n;
    for(int i = 0;i<n;i++){
        string s; cin>>s;
        add_string(s);
    }
    vector<char> ans;
    traverse(0, ans);
    while(ans.back() == '-'){
        ans.pop_back();
    }
    cout<<ans.size()<<"\n";
    for(auto x: ans){
        cout<<x<<"\n";
    }
    

}
int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt" , "r" , stdin);
    // freopen("output.txt" , "w", stdout);
    // cin>>t;
    while(t--){
        solve();
    }
}

Compilation message

printer.cpp: In function 'void add_string(std::string&)':
printer.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0 ;i<s.size();i++){
      |                    ~^~~~~~~~~

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 344 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
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 #4
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 #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 1020 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4044 KB Output is correct
2 Correct 11 ms 9676 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9164 KB Output is correct
2 Correct 6 ms 2388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 29380 KB Output is correct
2 Correct 75 ms 58812 KB Output is correct
3 Correct 42 ms 31424 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16328 KB Output is correct
2 Correct 86 ms 58556 KB Output is correct
3 Correct 44 ms 30916 KB Output is correct
4 Correct 80 ms 59580 KB Output is correct