oj.uz

Submission #434420

# Submission time Handle Problem Language Result Execution time Memory
434420 2021-06-21T09:17:55 Z Trunkty Type Printer (IOI08_printer) C++14
100 / 100
 298 ms 219672 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node{
    bool print;
    int arr[125];
};

int n,nextnode=1;
Node trie[500005]; 
int maxi;
string final,ans;

void build(int node, string a, int ind){
    if(ind==a.length()){
        trie[node].print = true;
        return;
    }
    if(trie[node].arr[a[ind]]==-1){
        trie[node].arr[a[ind]] = nextnode;
        for(int i='a';i<='z';i++){
            trie[nextnode].arr[i] = -1;
        }
        nextnode++;
    }
    build(trie[node].arr[a[ind]],a,ind+1);
}

void pnt(int node, int ind){
    if(trie[node].print){
        ans += 'P';
    }
    if(ind==final.length()){
        ans += 45;
        return;
    }
    for(char i='a';i<='z';i++){
        if(i==final[ind]){
            continue;
        }
        if(trie[node].arr[i]!=-1){
            ans += i;
            pnt(trie[node].arr[i],ind+1);
        }
    }
    if(trie[node].arr[final[ind]]!=-1){
        ans += final[ind];
        pnt(trie[node].arr[final[ind]],ind+1);
    }
    ans += 45;
}

int main(){
    cin >> n;
    for(int i='a';i<='z';i++){
        trie[0].arr[i] = -1;
    }
    for(int i=1;i<=n;i++){
        string a;
        cin >> a;
        build(0,a,0);
        if(a.length()>maxi){
            maxi = a.length();
            final = a;
        }
    }
    pnt(0,0);
    cout << ans.length()-final.length()-1 << "\n";
    for(int i=0;i<ans.length()-final.length()-1;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message

printer.cpp: In function 'void build(int, std::string, int)':
printer.cpp:17:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if(ind==a.length()){
      |        ~~~^~~~~~~~~~~~
printer.cpp:21:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |     if(trie[node].arr[a[ind]]==-1){
      |                             ^
printer.cpp:22:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |         trie[node].arr[a[ind]] = nextnode;
      |                              ^
printer.cpp:28:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |     build(trie[node].arr[a[ind]],a,ind+1);
      |                                ^
printer.cpp: In function 'void pnt(int, int)':
printer.cpp:35:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if(ind==final.length()){
      |        ~~~^~~~~~~~~~~~~~~~
printer.cpp:43:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |         if(trie[node].arr[i]!=-1){
      |                           ^
printer.cpp:45:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |             pnt(trie[node].arr[i],ind+1);
      |                                ^
printer.cpp:48:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |     if(trie[node].arr[final[ind]]!=-1){
      |                                 ^
printer.cpp:50:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         pnt(trie[node].arr[final[ind]],ind+1);
      |                                      ^
printer.cpp: In function 'int main()':
printer.cpp:64:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |         if(a.length()>maxi){
      |            ~~~~~~~~~~^~~~~
printer.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<ans.length()-final.length()-1;i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 300 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3532 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12620 KB Output is correct
2 Correct 38 ms 27220 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 31960 KB Output is correct
2 Correct 20 ms 6852 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 80256 KB Output is correct
2 Correct 236 ms 184560 KB Output is correct
3 Correct 142 ms 94752 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 62428 KB Output is correct
2 Correct 292 ms 219672 KB Output is correct
3 Correct 162 ms 107492 KB Output is correct
4 Correct 298 ms 207216 KB Output is correct