Submission #867316

#	Time	Username	Problem	Language	Result	Execution time	Memory
867316		Samrev	Type Printer (IOI08_printer)	C++14	100 / 100	86 ms	59580 KiB

printer

#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 (stderr)

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 / 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