oj.uz

Submission #794641

# Submission time Handle Problem Language Result Execution time Memory
794641 2023-07-26T17:45:54 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 210 ms 153920 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8156 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 5 ms 9316 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10324 KB Output is correct
2 Correct 7 ms 10972 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16592 KB Output is correct
2 Correct 29 ms 26332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 29948 KB Output is correct
2 Correct 33 ms 19056 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 62588 KB Output is correct
2 Correct 181 ms 130560 KB Output is correct
3 Correct 164 ms 81124 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 52240 KB Output is correct
2 Correct 210 ms 153920 KB Output is correct
3 Correct 174 ms 91112 KB Output is correct
4 Correct 175 ms 145956 KB Output is correct