Submission #1087000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087000		Drifter24	Type Printer (IOI08_printer)	C++14	100 / 100	80 ms	51664 KiB

printer

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