제출 #990760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990760		serkanrashid	Type Printer (IOI08_printer)	C++14	70 / 100	325 ms	106564 KiB

printer

#include<bits/stdc++.h>
#define endl "\n"

using namespace std;

int inf = 1e9;

struct Trie
{
    Trie *p[26];
    Trie *par;
    int is_end;
    int sub;
    Trie()
    {
        is_end = 0;
        sub = 0;
        par = nullptr;
        for(int i = 0; i < 26; i++) p[i] = nullptr;
    }
};

int n;
Trie *root = new Trie();
int br;
vector<char>ans;

void insert1(string s)
{
    Trie *beg = root;
    for(char c : s)
    {
        if(beg->p[c-'a']==nullptr) beg->p[c-'a'] = new Trie();
        (beg->p[c-'a']) -> par = beg;
        beg = beg->p[c-'a'];
    }
    (beg->is_end) ++;
    beg->sub = s.size();
    while(beg->par!=nullptr)
    {
        beg = beg->par;
        beg->sub = max((beg->sub),(int)s.size());
    }
}

void read()
{
    cin >> n;
    string s;
    for(int i = 1; i <= n; i++)
    {
        cin >> s;
        insert1(s);
    }
}

bool cmp(pair<Trie*,char> t1, pair<Trie*,char> t2)
{
    if(t1.first==nullptr||t2.first==nullptr) return t1.first != nullptr;
    return ((t1.first)->sub) < ((t2.first)->sub);
}

void rec(Trie *beg, int lvl)
{
    for(int i = 1; i <= (beg->is_end); i++)
    {
        ans.push_back('P');
        br++;
    }
    if(br==n)
    {
        cout << ans.size() << endl;
        for(char c : ans) cout << c << endl;
        exit(0);///VAZHNO
    }

    vector<pair<Trie*,char> >v;
    for(int i = 0; i < 26; i++) v.push_back({beg->p[i],i+'a'});
    /*for(int i = 0; i < 26; i++)
    {
        if(beg->p[i]==nullptr) continue;
        cout << ((beg->p[i])->sub) << " " << (char)(i+'a') << endl;
    }*/
    sort(v.begin(),v.end(),cmp);
    for(pair<Trie*,char> pom : v)
    {
        //cout << pom.second << " " << lvl << endl;
        if(pom.first==nullptr) return;
        ans.push_back(pom.second);
        rec(pom.first,lvl+1);
        ans.push_back('-');
    }
}

void solve()
{
    rec(root,0);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10