제출 #1280349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280349		khoavn2008	Type Printer (IOI08_printer)	C++20	100 / 100	117 ms	82412 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld double
#define FOR(i,l,r) for(ll i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(ll i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(ll i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((ll)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)

const ll MOD = 1e9 + 7, N = 1e6 + 10, INF = 1e9, LOG = 21;
ll cntUsedNode = 1;
ll root = 0;
ll nxt[N][26],maHigh[N];
bool isEnd[N];
void addstr(string &s){
    ll p = root;
    for(char c : s){
        if(!nxt[p][c - 'a'])nxt[p][c - 'a'] = ++cntUsedNode;
        p = nxt[p][c - 'a'];
        maHigh[p] = max(maHigh[p], size(s));
    }
    isEnd[p] = 1;
}
ll n;
string s[N];
string ans;
void dfs(ll u){
    if(isEnd[u])ans += 'P';
    vector<pair<ll,ll>> vec;
    REP(c,26)if(nxt[u][c])vec.pb({maHigh[nxt[u][c]], c});
    sort(all(vec));
    for(auto [sl, c] : vec){
        ans += char('a' + c);
        dfs(nxt[u][c]);
    }
    ans += '-';
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    FOR(i,1,n)cin>>s[i],addstr(s[i]);
    dfs(0);
    while(ans.back() == '-')ans.pop_back();
    cout<<size(ans)<<endl;
    REP(i,size(ans))cout<<ans[i]<<endl;
}

• 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