Submission #652020

#	Time	Username	Problem	Language	Result	Execution time	Memory
652020		Vladth11	Type Printer (IOI08_printer)	C++14	100 / 100	122 ms	49836 KiB

printer

#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 (stderr)

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 / 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