Submission #794641

#	Time	Username	Problem	Language	Result	Execution time	Memory
794641		vjudge1	Type Printer (IOI08_printer)	C++17	100 / 100	210 ms	153920 KiB

printer

#include <bits/stdc++.h>
using namespace std;

const int maxn=25e4+5;
int n, c=0;
int t[maxn];
string ans;
string s[maxn];
struct Trie
{
    Trie* child[26];
    set<int> s;
    Trie()
    {
        for (int i=0; i<26; ++i) child[i]=nullptr;
        s.clear();
    }
} root;

void add(int i)
{
    Trie* p=&root;
    p->s.insert(i);
    for (auto c : s[i])
    {
        int next=c-'a';
        if (p->child[next]==nullptr)
            p->child[next]=new Trie();
        p=p->child[next];
        p->s.insert(i);
    }
}

void del(int i)
{
    Trie* p=&root;
    p->s.erase(i);
    for (auto c : s[i])
    {
        int next=c-'a';
        p=p->child[next];
        p->s.erase(i);
    }
}

int lookup(int i)
{
    Trie* p=&root;
    for (auto c : s[i])
    {
        int next=c-'a';
        if (p->child[next]==nullptr || p->child[next]->s.empty())
            return *(p->s.begin());
        p=p->child[next];
    }
    return *(p->s.begin());
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    s[0].clear(); ans.clear();
    int mark=0;
    for (int i=1; i<=n; ++i)
    {
        cin >> s[i];
        add(i);
        if (s[i].size()>s[c].size()) c=i;
    }
    t[n]=c;
    for (int i=n-1; i>0; --i)
    {
        del(c);
        c=lookup(c);
        t[i]=c;
    }
    int cur=0;
    string a; a.clear();
    for (int i=1; i<=n; ++i)
    {
        int cnt=0;
        int x=min(a.size(), s[t[i]].size());
        for (int j=0; j<x; ++j)
            if (s[t[i]][j]==a[j]) ++cnt;
            else break;
        while (cur>cnt) --cur, ans+='-';
        while (cur<s[t[i]].size())
            ans+=s[t[i]][cur++];
        ans+='P';
        a=s[t[i]];
    }
    cout << ans.size() << '\n';
    for (auto c : ans) cout << c << '\n';
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         while (cur<s[t[i]].size())
      |                ~~~^~~~~~~~~~~~~~~
printer.cpp:65:9: warning: unused variable 'mark' [-Wunused-variable]
   65 |     int mark=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