Submission #1256138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256138		CrabCNH	Type Printer (IOI08_printer)	C++20	0 / 100	36 ms	21956 KiB

printer

#include <bits/stdc++.h>

#define task     "BriantheCrab"

#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}

const int maxN = 1e5 + 5;
const int maxNode = 2e6 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

// khong tu code thi khong kha len duoc dau

int n;
string a[maxN];
string best;
vector <char> path;

struct Trie {
    struct Node {
        int child[26];
        int cnt;
        int ex;
    } node[maxNode];
    
    int cur = 0;
    
    Trie () : cur (0) {
        memset (node[0].child, -1, szf (node[0].child));
        node[0].cnt = node[0].ex = 0;
    };
    
    int newNode () {
        cur ++;
        memset (node[cur].child, -1, szf (node[0].child));
        node[cur].cnt = node[cur].ex = 0;
        return cur;
    }
    
    void addString (string s) {
        int pos = 0;
        for (auto f : s) {
            int c = f - 'a';
            if (node[pos].child[c] == -1) {
                node[pos].child[c] = newNode ();
            }
            pos = node[pos].child[c];
            node[pos].cnt ++;
        }
        node[pos].ex ++;
    }
    
    void dfs (int p, int curD) {
        int hc = -1;
        if (curD < sz (best)) {
            int c = best[curD] - 'a';
            hc = node[p].child[c];
        }
        for (int i = 0; i < 26; i++) {
            int c = node[p].child[i];
            if (c == -1 || c == hc) {
                continue;
            }
            path.push_back (char ('a' + i));
            while (node[c].ex > 0) {
                path.push_back ('P');
                node[c].ex --;
            }
            dfs (c, curD + 1);
            path.push_back ('-');
        }
        if (hc != -1) {
            path.push_back (best[curD]);     
            while (node[hc].ex > 0) {        
                path.push_back ('P');
                node[hc].ex --;
            }
            dfs (hc, curD + 1);
            path.push_back ('-');
        }
    }
} T;

void solve () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        T.addString (a[i]);
    }
    for (int i = 1; i <= n; i ++) {
        if (sz (best) < sz (a[i])) {
            best = a[i];
        }
    }
    T.dfs (0, 0);
    int cnt = 0;
    for (int i = sz (path) - 1; i >= 0; i --) {
        if (path[i] != '-') {
            break;
        }
        cnt ++;
    }
    cout << sz (path) - cnt << '\n';
    cnt = sz (path) - cnt;
    for (auto it : path) {
        if (cnt-- == 0) {
            break;
        }
        cout << it;
    }
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfv

Compilation message (stderr)

printer.cpp:23:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const int inf = 1e18 + 7;
      |                 ~~~~~^~~
printer.cpp: In function 'int main()':
printer.cpp:132:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:133:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10