oj.uz

Submission #652020

# Submission time Handle Problem Language Result Execution time Memory
652020 2022-10-21T06:56:32 Z Vladth11 Type Printer (IOI08_printer) C++14
100 / 100
 122 ms 49836 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"

using namespace std;

const int NMAX = 2000001;

string acum;

struct Node{
    int nxt[26];
    int cnt;
    void init(){
        cnt = 0;
        for(int i = 0; i < 26; i++){
            nxt[i] = -1;
        }
    }
}v[NMAX];

int cnt;

vector <char> sol;
string maxim;

void DFS(int node, int ramura, int k){
    if(v[node].cnt > 0) sol.push_back('P');
    if(k == maxim.size()) return;
    for(int i = 0; i < 26; i++){
        if(v[node].nxt[i] != -1){
            int param = ramura;
            if(param == 1 && i != maxim[k] - 'a')
                param = 0;
            if(param == 1) continue;
            sol.push_back('a' + i);
            DFS(v[node].nxt[i], param, k + 1);
            sol.push_back('-');
        }
    }
    if(ramura == 0 && k < maxim.size())
        return;
    int ch = maxim[k] - 'a';
    sol.push_back(maxim[k]);
    DFS(v[node].nxt[ch], ramura, k + 1);
}

void baga(int node, int k){
    if(k == acum.size()){
        v[node].cnt++;
        return;
    }
    int ch = acum[k] - 'a';
    if(v[node].nxt[ch] == -1){
        v[node].nxt[ch] = ++cnt;
        v[cnt].init();
    }
    baga(v[node].nxt[ch], k + 1);
}

int main()
{
    int sz = 0;
    int t;
    v[0].init();
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        if(s.size() > sz){
            sz = s.size();
            maxim = s;
        }
        acum = s;
        baga(0, 0);
    }
    DFS(0, 1, 0);
    cout << sol.size() << "\n";
    for(auto x : sol) cout << x << "\n";
    return 0;
}

Compilation message

printer.cpp: In function 'void DFS(int, int, int)':
printer.cpp:28:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if(k == maxim.size()) return;
      |        ~~^~~~~~~~~~~~~~~
printer.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(ramura == 0 && k < maxim.size())
      |                       ~~^~~~~~~~~~~~~~
printer.cpp: In function 'void baga(int, int)':
printer.cpp:48:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     if(k == acum.size()){
      |        ~~^~~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:69:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         if(s.size() > sz){
      |            ~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3156 KB Output is correct
2 Correct 15 ms 6468 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7632 KB Output is correct
2 Correct 11 ms 1956 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18512 KB Output is correct
2 Correct 106 ms 41892 KB Output is correct
3 Correct 65 ms 21768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14512 KB Output is correct
2 Correct 122 ms 49836 KB Output is correct
3 Correct 73 ms 24788 KB Output is correct
4 Correct 113 ms 47044 KB Output is correct