oj.uz

Submission #857803

# Submission time Handle Problem Language Result Execution time Memory
857803 2023-10-07T02:23:46 Z sleepntsheep Type Printer (IOI08_printer) C++17
100 / 100
 99 ms 37472 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define N 200005
#define ALL(x) x.begin(), x.end()
vector<char> ans;
int cend2;

int n;
char s[21];
struct Trie
{
    int start = 0, end = 0, sz = 1;
    vector<tuple<int, char,Trie*>> sortbysz;
    
    Trie() {}

    void insert(char *s, int p = 0)
    {
        if (!*s) { ++end; return; }
        if (p == 1) ++start;
        char c = *s++;
        for (auto [sz, ch, n] : sortbysz)
            if (ch == c)
            { n->insert(s); return; }
        Trie *n = new Trie();
        sortbysz.emplace_back(1, c, n);
        n->insert(s);
    }

    void preprocess()
    {
        for (auto &[csz, c, n] : sortbysz)
        {
            n->preprocess();
            sz = max(sz, csz = n->sz+1);
        }
        sort(ALL(sortbysz));
    }

    void print()
    {
        while (end--)
        {
            ans.push_back('P');
            if (++cend2 == n) 
            {
                printf("%d\n", (int)ans.size());
                for (char c : ans) printf("%c\n", c);
                exit(0);
            }
        }
        for (auto [sz, c, n] : sortbysz)
        {
            ans.push_back(c);
            n->print();
        }
        ans.push_back('-');
    }
};


int main()
{
    scanf("%d", &n);
    Trie *t = new Trie();
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", s);
        t->insert(s);
    }

    t->preprocess();
    t->print();

    return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
printer.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%s", s);
      |         ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2396 KB Output is correct
2 Correct 10 ms 4956 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5848 KB Output is correct
2 Correct 5 ms 1624 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14088 KB Output is correct
2 Correct 75 ms 31540 KB Output is correct
3 Correct 41 ms 16584 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10964 KB Output is correct
2 Correct 99 ms 37472 KB Output is correct
3 Correct 56 ms 18780 KB Output is correct
4 Correct 74 ms 35536 KB Output is correct